Repository: ParkMyCar/compact_str
Pull request #276 (2023-07-17 18:59:01)

Open up more niches
Before this change there is one nieche: The last byte could never have the value `255`. With this change all values in the range `217..=255` cannot occur in the last byte. Actually, these values were already impossible before, but we did not tell the compiler about it.


Kijewski: I wanted to post my benchmark results, but given that my change made creating `String`s 14% faster, I guess I should put too much stock in criterion's results.
Kijewski: Should I move the optimization for `Repr::len()` into its own PR?

I thought it was a low-hanging fruit, but I could not get the compiler to unconditionally read `self.1` without `asm!`, which is only stable since Rust 1.57. Even [`ptr::read_volatile()`](https://doc.rust-lang.org/stable/std/ptr/fn.read_volatile.html) gets optimized away. Using [`blackbox()`](https://doc.rust-lang.org/stable/std/hint/fn.black_box.html) works, but is only stable since 1.60, and results in needless writing to the stack.
ParkMyCar: Thanks @Kijewski this is great!

Patch:
diff --git a/README.md b/README.md
index da07d16a..d531783a 100644
--- a/README.md
+++ b/README.md
@@ -131,11 +131,10 @@ For **inline** strings we only have a 24 byte buffer on the stack. This might ma
 To do this, we utilize the fact that the last byte of our string could only ever have a value in the range `[0, 192)`. We know this because all strings in Rust are valid [UTF-8](https://en.wikipedia.org/wiki/UTF-8), and the only valid byte pattern for the last byte of a UTF-8 character (and thus the possible last byte of a string) is `0b0XXXXXXX` aka `[0, 128)` or `0b10XXXXXX` aka `[128, 192)`. This leaves all values in `[192, 255]` as unused in our last byte. Therefore, we can use values in the range of `[192, 215]` to represent a length in the range of `[0, 23]`, and if our last byte has a value `< 192`, we know that's a UTF-8 character, and can interpret the length of our string as `24`.
 
 Specifically, the last byte on the stack for a `CompactString` has the following uses:
-* `[0, 192)` - Is the last byte of a UTF-8 char, the `CompactString` is stored on the stack and implicitly has a length of `24`
+* `[0, 191]` - Is the last byte of a UTF-8 char, the `CompactString` is stored on the stack and implicitly has a length of `24`
 * `[192, 215]` - Denotes a length in the range of `[0, 23]`, this `CompactString` is stored on the stack.
-* `[215, 254)` - Unused
-* `254` - Denotes this `CompactString` is stored on the heap
-* `255` - Denotes the `None` variant for an `Option<CompactString>`
+* `216` - Denotes this `CompactString` is stored on the heap
+* `[217, 255]` - Unused, denotes e.g. the `None` variant for `Option<CompactString>`
 
 ### Testing
 Strings and unicode can be quite messy, even further, we're working with things at the bit level. `compact_str` has an _extensive_ test suite comprised of unit testing, property testing, and fuzz testing, to ensure our invariants are upheld. We test across all major OSes (Windows, macOS, and Linux), architectures (64-bit and 32-bit), and endian-ness (big endian and little endian).
diff --git a/compact_str/src/repr/nonmax.rs b/compact_str/src/repr/last_utf8_char.rs
similarity index 65%
rename from compact_str/src/repr/nonmax.rs
rename to compact_str/src/repr/last_utf8_char.rs
index 52353a34..903227a7 100644
--- a/compact_str/src/repr/nonmax.rs
+++ b/compact_str/src/repr/last_utf8_char.rs
@@ -1,14 +1,14 @@
-/// [`NonMaxU8`] is an unsigned 8-bit integer data type that has a valid range of `[0, 254]`.
-/// Excluding `255` allows the Rust compiler to use `255` as a niche.
+/// [`LastUtf8Char`] is an unsigned 8-bit integer data type that has a valid range of `[0, 216]`.
+/// Excluding `[217, 255]` allows the Rust compiler to use these values as niches.
 ///
-/// Specifically the compiler can use `255` to encode the `None` variant of `Option<NonMaxU8>`
-/// allowing `std::mem::size_of::<NonMaxU8> == std::mem::size_of::<Option<NonMaxU8>>()`
-#[allow(clippy::upper_case_acronyms)]
+/// Specifically the compiler can use a value in this range to encode the `None` variant of
+/// `Option<NonMaxU8>` allowing
+/// `std::mem::size_of::<NonMaxU8> == std::mem::size_of::<Option<NonMaxU8>>()`
 #[allow(dead_code)]
-#[allow(non_camel_case_types)]
 #[derive(Copy, Clone, Debug)]
 #[repr(u8)]
-pub enum NonMaxU8 {
+pub enum LastUtf8Char {
+    // single character, ASCII:
     V0 = 0,
     V1 = 1,
     V2 = 2,
@@ -137,6 +137,8 @@ pub enum NonMaxU8 {
     V125 = 125,
     V126 = 126,
     V127 = 127,
+
+    // trailing byte in a multi-byte UTF-8 sequence
     V128 = 128,
     V129 = 129,
     V130 = 130,
@@ -201,69 +203,40 @@ pub enum NonMaxU8 {
     V189 = 189,
     V190 = 190,
     V191 = 191,
-    V192 = 192,
-    V193 = 193,
-    V194 = 194,
-    V195 = 195,
-    V196 = 196,
-    V197 = 197,
-    V198 = 198,
-    V199 = 199,
-    V200 = 200,
-    V201 = 201,
-    V202 = 202,
-    V203 = 203,
-    V204 = 204,
-    V205 = 205,
-    V206 = 206,
-    V207 = 207,
-    V208 = 208,
-    V209 = 209,
-    V210 = 210,
-    V211 = 211,
-    V212 = 212,
-    V213 = 213,
-    V214 = 214,
-    V215 = 215,
-    V216 = 216,
-    V217 = 217,
-    V218 = 218,
-    V219 = 219,
-    V220 = 220,
-    V221 = 221,
-    V222 = 222,
-    V223 = 223,
-    V224 = 224,
-    V225 = 225,
-    V226 = 226,
-    V227 = 227,
-    V228 = 228,
-    V229 = 229,
-    V230 = 230,
-    V231 = 231,
-    V232 = 232,
-    V233 = 233,
-    V234 = 234,
-    V235 = 235,
-    V236 = 236,
-    V237 = 237,
-    V238 = 238,
-    V239 = 239,
-    V240 = 240,
-    V241 = 241,
-    V242 = 242,
-    V243 = 243,
-    V244 = 244,
-    V245 = 245,
-    V246 = 246,
-    V247 = 247,
-    V248 = 248,
-    V249 = 249,
-    V250 = 250,
-    V251 = 251,
-    V252 = 252,
-    V253 = 253,
-    V254 = 254,
+
+    // Cannot be last character of a UTF-8 sequence (leading byte of a sequence)
+    // V192 .. V244,
+    // Can never occur in UTF-8 (start for a codepoint > U+10FFFF)
+    // V245 .. 255,
+
+    // length marker:
+    L0 = 192,
+    L1 = 193,
+    L2 = 194,
+    L3 = 195,
+    L4 = 196,
+    L5 = 197,
+    L6 = 198,
+    L7 = 199,
+    L8 = 200,
+    L9 = 201,
+    L10 = 202,
+    L11 = 203,
+    L12 = 204,
+    L13 = 205,
+    L14 = 206,
+    L15 = 207,
+    L16 = 208,
+    L17 = 209,
+    L18 = 210,
+    L19 = 211,
+    L20 = 212,
+    L21 = 213,
+    L22 = 214,
+    L23 = 215,
+
+    Heap = 216,
 }
 
-static_assertions::assert_eq_size!(NonMaxU8, Option<NonMaxU8>, u8);
+static_assertions::assert_eq_size!(LastUtf8Char, Option<LastUtf8Char>, u8);
+static_assertions::const_assert!(std::mem::size_of::<String>() <= 24);
diff --git a/compact_str/src/repr/mod.rs b/compact_str/src/repr/mod.rs
index ca5266fa..e65b412e 100644
--- a/compact_str/src/repr/mod.rs
+++ b/compact_str/src/repr/mod.rs
@@ -14,23 +14,23 @@ mod capacity;
 mod heap;
 mod inline;
 mod iter;
-mod nonmax;
+mod last_utf8_char;
 mod num;
 mod traits;
 
 use capacity::Capacity;
 use heap::HeapBuffer;
 use inline::InlineBuffer;
-use nonmax::NonMaxU8;
+use last_utf8_char::LastUtf8Char;
 pub use traits::IntoRepr;
 
 /// The max size of a string we can fit inline
 pub const MAX_SIZE: usize = std::mem::size_of::<String>();
 /// Used as a discriminant to identify different variants
-pub const HEAP_MASK: u8 = 0b11111110;
+pub const HEAP_MASK: u8 = LastUtf8Char::Heap as u8;
 /// When our string is stored inline, we represent the length of the string in the last byte, offset
 /// by `LENGTH_MASK`
-pub const LENGTH_MASK: u8 = 0b11000000;
+pub const LENGTH_MASK: u8 = LastUtf8Char::L0 as u8;
 
 const EMPTY: Repr = Repr::new_inline("");
 
@@ -45,7 +45,7 @@ pub struct Repr(
     u16,
     u8,
     // ...so that the last byte can be a NonMax, which allows the compiler to see a niche value
-    NonMaxU8,
+    LastUtf8Char,
 );
 
 unsafe impl Send for Repr {}


Test patch:
diff --git a/compact_str/src/tests.rs b/compact_str/src/tests.rs
index dbabdefb..757acd40 100644
--- a/compact_str/src/tests.rs
+++ b/compact_str/src/tests.rs
@@ -1580,3 +1580,16 @@ fn test_from_string_buffer_inlines_on_clone() {
     // when cloning the CompactString we should inline it
     assert!(!b.is_heap_allocated());
 }
+
+#[test]
+fn multiple_nieches_test() {
+    #[allow(unused)]
+    enum Value {
+        String(CompactString),
+        Bool(bool),
+        Signed(isize),
+        Unsigned(usize),
+        Null,
+    }
+    assert_eq!(std::mem::size_of::<Value>(), std::mem::size_of::<String>());
+}