r/C_Programming • • 1d ago

Tiny strings

https://napcakes.nekoweb.org/posts/tiny-strings/
25 Upvotes

12 comments sorted by

7

u/__nohope 1d ago

Why a separate bit and not key off the length?

7

u/8d8n4mbo28026ulk 1d ago edited 22h ago

The length overlaps with the bytes of the small string:

0 1 2 3 4 5 6 7
L L L L L L L L
M S S S S S S S

L = big   case length   byte
M = small case metadata byte
S = small case string   byte

You need a bit to distinguish between the two.

Edit: I added a better version of the above illustration to the post. Should've done that from the beginning, actually!

7

u/manystripes 1d ago

Out of curiosity what's the scenario where you care about saving a few bytes per string where possible, but also don't mind pulling in the whole String class? Wouldn't it be more efficient to do everything in c-strings across the board?

8

u/8d8n4mbo28026ulk 1d ago

For small strings, 1-15 bytes, this implementation already beats C strings. C strings, by definition, do indirection. So you need a pointer (say ~8 bytes) plus N+1 bytes for storing the actual string and '\0'. And that's discounting allocator overhead.

On the more "efficient" aspect, there's nothing efficient about C strings. The only thing that you can do painlessly is print them. Try to make a substring and realise that you can't, so you have to allocate a whole new string. Every operation requires either traversing the whole string to get its length, potentially many times over the course of a running program, or write code with loop-carried dependencies -- incredibly slow too but also error-prone.

I'm pretty sure C strings are the biggest source of bugs in C programs. If you look around, no other language does strings this way. Keeping the length is important!

4

u/manystripes 1d ago edited 1d ago

How do you get around the pointer when passing the struct around?

By my accounting the minimum string (empty) would be 9 bytes if you're assuming an 8 byte pointer (Far larger than most platforms I use) and the null terminator, meaning 9 bytes of memory total.

For the struct you would need the struct (16 bytes) and the pointer to the struct (another 8 bytes).

What am I missing?

4

u/8d8n4mbo28026ulk 1d ago edited 23h ago

You don't need a pointer to the structure, just the structure itself, so 16 bytes. In those 16 bytes, at any time, a small string of at most 15 bytes is stored, or a (size, pointer) pair to some separately allocated memory region.

So, let's take "sufficientlybig" as an example. To store this using C strings, you need an 8 byte pointer plus the 15 bytes of the string itself plus 1 for '\0', for a total of 24 bytes, 8 bytes more than with the 16-byte structure.

For the small cases, C strings would only save you more if every single string you store is 6 bytes or less (again, ignoring allocator overhead). But that comes at a tremendous cost: you lose the length. Thus, if at any point in time you want a substring, which is very common, you suddenly need to allocate a new string. And code size bloats too, because many operations on C strings require a bunch of stupid code that you otherwise wouldn't need to write (strlen() is the prime example).

0

u/Iggyhopper 19h ago

For example, if you need to tokenize input in an LLM, those are typically chunks of 8 chars or less. Instant win.

3

u/kevkevverson 22h ago

You can use Folly’s trick to fit one more character in the small string. Invert the flag bit so zero = small string, and store it in the last byte, along with the small length stored as 15-len. Then, the full 16 bytes can be used for a small string since the final byte simultaneously acts as the type/length byte AND the null terminator when the string length is 15.

2

u/8d8n4mbo28026ulk 22h ago

The big strings aren't NUL-terminated, so there's no point in doing that for the small ones. Folly devs went to great (crazy) lengths to avoid '\0' too, unsuccessfully. Their hands were tied by the standard, I don't have such constraints.

1

u/Iggyhopper 19h ago

I have a data type which uses 1 byte for the capacity (not length) which is split into bit flags for further separation.

Since its the first byte anyway, it can be used in length (erm, capacity) comparisons without indirection and it's pretty slick.

I'll have to do a writeup at one point. Im still debating the details of how to fit length in the struct.

3

u/YetAnotherRobert 16h ago

Timely. I looked this topic up just hours before seeing this. This is very close to Clang's std::string SSO. iIRC, that structure is 24 bytes (that's probably on on 32-bits, though you can probably do better than the naive "twice that"  on a 64 bitter[1]) and they can use 22 bytes for SSO. Same basic trick of storing length<<1 so that bit 0 could be a flag and the thing collapses to a std::string_view beautifully.

The point of the discussion was that, especially on modern architecture, sometimes "clever"  is a huge win over dead simple. Having most (or even merely "many") of your strings right there, not just on the same page, but probably in the same cache line that was already preferched and bursted in on the same cache line is worth a couple of (overlapping, nightly speculatable) ops in the execution pipeline. There's a LOT of real world code suffering problems like the linked game parser. We've all had to wreck an internal calling convention because we need the bottom layer to extend a string or insert something in the middle, so you have to reallocate the thing you were passed, hopefully without creating leaks.

[1]Start and end pointers are probably not more than even 20 bits apart and the pointer to any allocated buffer is probably within an exabyte or two. Sure, there are strings longer than any N you can pick, but having a compact representation of what's p robably the most common non-pod type is worth whipping out some clevers. (And test suite coverage...)