I came up with a kind of clever data type for storing short strings in a fixed size struct so they can be stored on the stack or inline without any allocations.
It’s always null-terminated so it can be passed directly as a C-style string, but it also stores the string length without using any additional data (Getting the length would normally have to iterate to find the end).
The trick is to store the number of unused bytes in the last character of the buffer. When the string is full, there are 0 unused bytes and the size byte overlaps the null terminator.
(Only works for strings < 256 chars excluding null byte)
Edit: Since a couple people don’t seem to understand the performance impact of this vs regular std::string, here’s a demo:
https://godbolt.org/z/34j7obnbs
This generates 10000 strings like “Hello, World! 00001” via concatenation. The effect is huge in debug mode, but still has performance benefits with optimizations turned on:
With -O3 optimization
std::string: 0.949216ms
char[256] with strlen: 0.88104ms
char[256] without strlen: 0.684734ms
With no optimization:
std::string: 3.5501ms
char[256] with strlen: 0.885888ms
char[256] without strlen: 0.687733ms
(You may need to run it a few times toget sample numbers due to random server load on godbolt)
Changing the buffer size to32 bytes has a negligible performance improvement over 256 bytes in this case, but might be slightly faster due to the whole string fitting in a cache line.
I came up with a kind of clever data type for storing short strings in a fixed size struct so they can be stored on the stack or inline without any allocations.
C++ already does that for short strings while seamlessly switching to allocation for long strings.
It’s always null-terminated so it can be passed directly as a C-style string, but it also stores the string length without using any additional data
(Getting the length would normally have to iterate to find the end).
Also the case in the standard library
The trick is to store the number of unused bytes in the last character of the buffer. When the string is full, there are 0 unused bytes and the size byte overlaps the null terminator.
Iirc, that trick was used in one implementation but discontinued because it was against the standard.
(Only works for strings < 256 chars excluding null byte)
If you need a niche for allocated string you can get to 254 but the typical choice seem to be around 16.
I’ve already been discussing this. Maybe read the rest of the thread.
Also the case in the standard library
I think you’re missing the point of why. I built this to be a nearly drop in replacement for the standard string. If this wasn’t the case it would need to do even more processing and work to pass the strings to anything.
discontinued because it was against the standard.
Standards don’t matter for an internal type that’s not exposed to public APIs. I’m not trying to be exactly compatible with everything under the sun. There’s no undefined behavior here so it’s fine
Interesting idea, but your trick is never really going to help (you can store up to 255 bytes instead of 254). Also always using 256 bytes for every string seems wasteful.
22 characters is significantly less useful than 255 characters. I use this for resource name keys, asset file paths, and a few other scenarios. The max size is configurable, so I know that nothing I am going to store is ever going to require heap allocations (really bad to be doing every frame in a game engine).
I developed this specifically after benchmarking a simpler version and noticed a significant amount of time being spent in strlen(), and it had real benefits in my case.
Admittedly just storing a struct with a static buffer and separate size would have worked pretty much the same and eliminated the 255 char limitation, but it was fun to build.
22 characters is significantly less useful than 255 characters.
You can still use more than 22 characters; it just switches to the heap.
nothing I am going to store is ever going to require heap allocations
I would put good money that using 256 bytes everywhere is going to be slower overall than just using the heap when you need more than 22 characters. 22 is quite a lot, especially for keys. ThisReallyLongKey is still only 17.
I don’t use 256 bytes everywhere. I use a mix of 64, 128, and 256 byte strings depending on the specific use case.
In a hot path, having the data inline is much more important than saving a few hundred bytes. Cache efficiency plus eliminating heap allocations has huge performance benefits in a game engine that’s running frames as fast as possible.
It’s not as simple as that, depending on the architecture. Typically they would fetch 64-byte cache lines so your 128 bytes aren’t going to be magically more cached than 128 bytes on the heap.
Avoiding allocations may help but also maybe not. This is definitely in “I don’t believe it until I see benchmarks” realm. I would be really really surprised if the allocation cost was remotely bad enough to justify the “sorry your file is too long” errors.
I came up with a kind of clever data type for storing short strings in a fixed size struct so they can be stored on the stack or inline without any allocations.
It’s always null-terminated so it can be passed directly as a C-style string, but it also stores the string length without using any additional data (Getting the length would normally have to iterate to find the end).
The trick is to store the number of unused bytes in the last character of the buffer. When the string is full, there are 0 unused bytes and the size byte overlaps the null terminator.
(Only works for strings < 256 chars excluding null byte)
Implementation in C++ here: https://github.com/frustra/strayphotons/blob/master/src/common/common/InlineString.hh
Edit: Since a couple people don’t seem to understand the performance impact of this vs regular std::string, here’s a demo: https://godbolt.org/z/34j7obnbs This generates 10000 strings like “Hello, World! 00001” via concatenation. The effect is huge in debug mode, but still has performance benefits with optimizations turned on:
With -O3 optimization std::string: 0.949216ms char[256] with strlen: 0.88104ms char[256] without strlen: 0.684734ms With no optimization: std::string: 3.5501ms char[256] with strlen: 0.885888ms char[256] without strlen: 0.687733ms (You may need to run it a few times to get sample numbers due to random server load on godbolt) Changing the buffer size to 32 bytes has a negligible performance improvement over 256 bytes in this case, but might be slightly faster due to the whole string fitting in a cache line.C++ already does that for short strings while seamlessly switching to allocation for long strings.
Also the case in the standard library
Iirc, that trick was used in one implementation but discontinued because it was against the standard.
If you need a niche for allocated string you can get to 254 but the typical choice seem to be around 16.
I’ve already been discussing this. Maybe read the rest of the thread.
I think you’re missing the point of why. I built this to be a nearly drop in replacement for the standard string. If this wasn’t the case it would need to do even more processing and work to pass the strings to anything.
Standards don’t matter for an internal type that’s not exposed to public APIs. I’m not trying to be exactly compatible with everything under the sun. There’s no undefined behavior here so it’s fine
Interesting idea, but your trick is never really going to help (you can store up to 255 bytes instead of 254). Also always using 256 bytes for every string seems wasteful.
I think LLVM’s small string optimisation is always going to be a better option: https://joellaity.com/2020/01/31/string.html
22 characters is significantly less useful than 255 characters. I use this for resource name keys, asset file paths, and a few other scenarios. The max size is configurable, so I know that nothing I am going to store is ever going to require heap allocations (really bad to be doing every frame in a game engine).
I developed this specifically after benchmarking a simpler version and noticed a significant amount of time being spent in strlen(), and it had real benefits in my case.
Admittedly just storing a struct with a static buffer and separate size would have worked pretty much the same and eliminated the 255 char limitation, but it was fun to build.
You can still use more than 22 characters; it just switches to the heap.
I would put good money that using 256 bytes everywhere is going to be slower overall than just using the heap when you need more than 22 characters. 22 is quite a lot, especially for keys.
ThisReallyLongKeyis still only 17.I don’t use 256 bytes everywhere. I use a mix of 64, 128, and 256 byte strings depending on the specific use case.
In a hot path, having the data inline is much more important than saving a few hundred bytes. Cache efficiency plus eliminating heap allocations has huge performance benefits in a game engine that’s running frames as fast as possible.
It’s not as simple as that, depending on the architecture. Typically they would fetch 64-byte cache lines so your 128 bytes aren’t going to be magically more cached than 128 bytes on the heap.
Avoiding allocations may help but also maybe not. This is definitely in “I don’t believe it until I see benchmarks” realm. I would be really really surprised if the allocation cost was remotely bad enough to justify the “sorry your file is too long” errors.
Check out the benchmark I edited in to my original post. These are not user-provided strings in my case.