google / google/flyweights

Squeezing the last byte out of the inline repr

Open
#4 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
2
Forks
5
PR merge metrics
No merged PRs in 30d

Description

I performed this storage optimization for rkyv with the release of 0.8 and it worked nicely.

UTF-8 encodes code points as follows (taken from [Wikipedia](https://en.wikipedia.org/wiki/UTF-8#Description)):

| First code point | Last code point | Byte 1 | Byte 2 | Byte 3 | Byte 4 |
| --: | --: | --: | --: | --: | --: |
| `U+0000` | `U+007F` | `0yyyzzzz` | | | |
| `U+0080` | `U+07FF` | `110xxxyy` | `10yyzzzz` | | |
| `U+0800` | `U+FFFF` | `1110wwww` | `10xxxxyy` | `10yyzzzz` | |
| `U+010000` | `U+10FFFF` | `11110uvv` | `10vvwwww` | `10xxxxyy` | `10yyzzzz` |

There are a few gaps in this encoding scheme, which we can use to our advantage:

1. Only continuation bytes are of the form `10xxxxxx` where the top two bits are `10`. No valid UTF-8 string will ever start with one of these continuation bytes. We can exploit this to detect whether a repr is inline or out-of-line.

2. `0xff` and a few other bytes never occur in UTF-8 streams. We can use one of these as a null terminator for inline strings. In the case where all inline bytes are used, we'll know the length is the max by the lack of a null terminator.

The bytes of the out-of-line representation inherit the alignment of the header structure, so the pointer to those bytes should be at least 4-aligned and have the bottom two bits unset. So for the out-of-line representation, we can encode it as (assuming little-endian):

| | Byte 1 | Byte 2 | Byte 3 | Byte 4 |
| --: | --: | --: | --: | --: |
| Pointer | `zzzzzz00` | `yyyyyyyy` | `xxxxxxxx` | `wwwwwwww` |
| Encoded | `10zzzzzz` | `yyyyyyyy` | `xxxxxxxx` | `wwwwwwww` |

A few arithmetic ops should recover the pointer without too much overhead.

## Summary

- < `MAX_INLINE_BYTES`: inline UTF-8 string with 0xff null terminator
- = `MAX_INLINE_BYTES`: inline UTF-8 string with no null terminator
- \> `MAX_INLINE_BYTES`: encoded 4-aligned payload; rotate the bottom two bits of the LSB to the top and set them to 10

## Limitations

Because byte strings don't have any exploitable gaps, we wouldn't be able to perform the same kind of optimization for them.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.