Make Option<TinyAsciiStr> be the same size as TinyAsciiStr

[sffc]

Previously, the tinystr crate used NonZeroU32 and friends to optimize Option<TinyStr4>. We have not yet replicated this optimization after the rewrite to TinyAsciiStr.

@Manishearth had some suggestions on how to go about this.

[Manishearth]

Did I? I don't recall having such suggestions, I don't think it's currently possible for the generic type.

[sffc]

I think the naive solution is to just make the first byte be NonZeroU8, such that we can't represent empty strings, but it creates the niche for Option to use.

A fancier solution is to recognize that 0xFF is never a valid ASCII byte (or UTF-8 byte) and use that as the niche somehow.

[sffc]

Here's how it works with the NonZeroU8 lead byte (it might be necessary to reduce the const N by 1, but this is OK especially if we make a new type for it): Playground

[sffc]

For the fancier solution, I think the safe way is to make an enum with a value for each valid ASCII char, and the internal representation is an array of those enums instead of an array of raw u8: Playground

[Manishearth]

Oh, huh. The N-1 thing was something I was trying earlier but there were const problems, I guess that works now

Honestly I'd prefer the enum solution since it keeps it clean. Might need to be careful about the repr (C can't use niches, unsure if u8 can, Rust is UB to use this way)

[robertbastian]

The const problem is still there, you cannot evaluate const generics, so you cannot write the type NonEmptyTinyAsciiStr<N-1>. playground

[robertbastian]

I tried to find some documentation on how to define a niche, but it seems like the niche optimizations are entirely compiler internals are thus not reference-guaranteed behaviour.

For the enum option, what's the plan wrt to getting a [u8; N] to work with? Transmute? Big match statement?

[Manishearth]

You cannot define niches beyond making your own enums.

Yes, transmute. If we can guarantee the repr we can transmute.

[sffc]

Right, the NonZeroU8 option involves a new type with the size offset by one. TinyAsciiStr<4> becomes NonEmptyTinyAsciiStr<3>, a new type to avoid confusion.

[robertbastian]

You cannot define niches beyond making your own enums.

But even that doesn't seem to be guaranteed iiuc

[robertbastian]

a new type to avoid confusion.

I think it will be very confusing to use N-1 in the public type.

[Manishearth]

But even that doesn't seem to be guaranteed iiuc

well, nothing in repr(Rust) is

Also yes, I agree about N-1

[Manishearth]

Also, uh, the other problem with N-1 is that (NonZero, [u8; N]) doesn't have a defined layout, and you will lose niche optimizations with repr(C). That's another reason why I abandoned that approach. Might work with packed.

[sffc]

Also, uh, the other problem with N-1 is that (NonZero, [u8; N]) doesn't have a defined layout, and you will lose niche optimizations with repr(C). That's another reason why I abandoned that approach. Might work with packed.

The playground link I posted earlier demonstrates that it works (with packed)

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ce619eb4e274017e6004a38ca211d4f3

[Manishearth]

If it works with packed that should be okay, packed is defined.

[sffc]

OK, should we vote?

• Option 1: NonZeroU8 with repr(packed) and N offset by 1
• Option 2: Internal repr(u8) enum with values 0x00 to 0x7F (or 0xFE), transmuting to [u8]

Note: This is intended as a future feature; I just want to record the conclusion so that it's ready for someone to get started.

[sffc]

Question: is there a code size risk with either of these choices? Will we not know until it is implemented? Would the enum compile down to a zero-cost abstraction?

[Manishearth]

Well, with the enum i suspect we won't ever access it as the enum, we'll always be transmuting

I hae a preference for Option 2

[robertbastian]

2 >> 1 because the N-1 is such a footgun. It also removes the distinction between empty string and no string because we use 0 as the niche, whereas with option two we use something that is actually a niche, the highest-order bit.

[Manishearth]

Also uh sorry my preference is for Option 2 I mistyped 😄

Also am 2>>1.

[robertbastian]

@zbraniecki found https://github.com/ParkMyCar/compact_str, which uses nonmax::NonMaxU8 to achieve the niche. Might be an alternative to the enum.

[sffc]

@zbraniecki found https://github.com/ParkMyCar/compact_str, which uses nonmax::NonMaxU8 to achieve the niche. Might be an alternative to the enum.

Looking at the implementation, it's storing values as NonZeroU8 and XORing them with ^ $primitive::max_value() in the .get() function. This suggests we most likely wouldn't be able to transmute the bytes to a string, since the byte representation is incorrect.

[robertbastian]

Oh I was hoping it's doing something cleverer

[sffc]

@Manishearth Do we need to define every value in the enum in order to prevent it from being used as the niche, or is setting a start and end range sufficient?

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=f6c980d29eb4f2f057469ce9470d3c11

[CAD97]

👋 I pushed the niche optimization for CompactString over the finish line. Stumbled into this at a useful time, it seems.

I don't see a get function in compact_str at all? @sffc (Though the implementation has changed a lot over the previous few versions, and I only hopped on board for the previous couple.) And yes, transmuting any integer not used as a discriminant to an enum in Rust is UB. (Try running the playground under miri: it shows the UB as "encountered 0x68, but expected a valid enum tag".)

The important part of CompactString w.r.t. inlining is the following:

#[cfg(target_pointer_width = "64")]
const MAX_SIZE: usize = 24;
#[cfg(target_pointer_width = "32")]
const MAX_SIZE: usize = 12;

const LENGTH_MASK: u8 = 0b11000000;

#[repr(C)]
#[derive(Debug, Copy, Clone)]
pub struct InlineString {
    buffer: [u8; MAX_SIZE],
}

impl InlineString {
    #[inline]
    pub fn new(text: &str) -> Self {
        debug_assert!(text.len() <= MAX_SIZE);

        let len = text.len();
        let mut buffer = [0u8; MAX_SIZE];

        // set the length
        buffer[MAX_SIZE - 1] = len as u8 | LENGTH_MASK;

        // copy the string
        //
        // note: in the case where len == MAX_SIZE, we'll overwrite the len, but that's okay because
        // when reading the length we can detect that the last byte is part of UTF-8 and return a
        // length of MAX_SIZE
        unsafe { std::ptr::copy_nonoverlapping(text.as_ptr(), buffer.as_mut_ptr(), len) };


        InlineString { buffer }
    }

CompactString stores length in the last byte (which is the NonMaxU8), mapping length values 0x0..0x18 to 0xC0..D8, which are not valid UTF-8 terminating bytes. The max length of 0x19 (24₁₀) is mapped to any ASCII byte 0x0..0xC0 to achieve maximum length inline strings, as the "length byte" is the final UTF-8 byte. compact_str's observation here is that the final byte of a UTF-8 string cannot be any value in the range 0xC0..=0xFF, and the simplest way to niche the inline length byte into that available range is to set/mask the most significant two bits. Final bytes in 0xD8..0xFF are used to mark an outlined string, and 0xFF is made unrepresentable so that it is used as a niche.

This representation should be 100% compatible with true-zero-copy usage.

Oh, our NonMaxU8 is just said enum, not the nonmax crate.

[Manishearth]

@sffc every undefined value is a niche, regardless of whether rustc currently uses it