4 ms·

High-performance analytic databases also do this. A common representation is to store the length in 4 bytes from a total of 16. Then if the length is <= 12 the

by orlp 3y ago

High-performance analytic databases also do this. A common representation is to store the length in 4 bytes from a total of 16. Then if the length is <= 12 the rest of the storage is used to store the string inline, otherwise only the first 4 bytes of the string are stored inline (this can drastically speed up sorts/comparisons by not having to do a non-local access), leaving the remaining 8 bytes for a pointer. This representation is also coming to arrow. But instead of 8 bytes for a pointer it will contain 4 bytes for a buffer index, and 4 bytes for an offset into that buffer. This allows reduced effort when concatenating/merging arrays (no need to copy the data section where the long strings are stored), while remaining a relocatable/serializable format (only offsets, no pointers).

xoranth 3y ago
An even better representation is the one from `folly::FBString`. There, the tag that indicates small string mode is not a particular bound on capacity, but the last byte of the struct that is set to zero. That way, the tag also acts as a null terminator for the stored string.
- orlp 3y ago
  I fail to see how that is better. Null-terminated strings are a terrible idea in the first place.
  - UncleEntity 3y ago
    If null-terminated strings are already a thing in your language and you can just pass an inlined string to whatever function without any bit manipulation I fail to see the downside.
  - xoranth 3y ago
    > I fail to see how that is better. Null-terminated strings are a terrible idea in the first place. TLDR: you get extra bytes in your small strings Long version: Copying from FBString code: struct MediumLarge { Char* data_; size_t size_; size_t capacity_; }; // sizeof(MediumLarge) == 24 struct FBString { union { // For accessing the last byte. uint8_t bytes_[sizeof(MediumLarge)]; Char small_[sizeof(MediumLarge) / sizeof(Char)]; MediumLarge ml_; }; }; Then `bytes_[23]` is set to `24 - size of small string` for a small string. You also "steal" a couple of bits from `capacity_` as a tag to see if a string is small or large. This has two advantages: - You get to reuse seven of the eight bytes of `capacity_` in your small string (i.e. your max small string size is 23, not 16 as it would be with a simpler scheme). - You get a null terminator "for free" (though, of course, you still have size and capacity). This is on top of size/capacity. This could be reduced to 16 bytes by making `size_` and `capacity_` uint32_t instead of size_t.

by orlp 3y ago

xoranth 3y ago

An even better representation is the one from `folly::FBString`. There, the tag that indicates small string mode is not a particular bound on capacity, but the last byte of the struct that is set to zero. That way, the tag also acts as a null terminator for the stored string.

orlp 3y ago
I fail to see how that is better. Null-terminated strings are a terrible idea in the first place.
- UncleEntity 3y ago
  If null-terminated strings are already a thing in your language and you can just pass an inlined string to whatever function without any bit manipulation I fail to see the downside.
- xoranth 3y ago
  > I fail to see how that is better. Null-terminated strings are a terrible idea in the first place. TLDR: you get extra bytes in your small strings Long version: Copying from FBString code: struct MediumLarge { Char* data_; size_t size_; size_t capacity_; }; // sizeof(MediumLarge) == 24 struct FBString { union { // For accessing the last byte. uint8_t bytes_[sizeof(MediumLarge)]; Char small_[sizeof(MediumLarge) / sizeof(Char)]; MediumLarge ml_; }; }; Then `bytes_[23]` is set to `24 - size of small string` for a small string. You also "steal" a couple of bits from `capacity_` as a tag to see if a string is small or large. This has two advantages: - You get to reuse seven of the eight bytes of `capacity_` in your small string (i.e. your max small string size is 23, not 16 as it would be with a simpler scheme). - You get a null terminator "for free" (though, of course, you still have size and capacity). This is on top of size/capacity. This could be reduced to 16 bytes by making `size_` and `capacity_` uint32_t instead of size_t.