Why German Strings Are Everywhere?(cedardb.com)
cedardb.com
Why German Strings Are Everywhere?
https://cedardb.com/blog/german_strings/
57 comments
In case anyone wonders why they are called German strings: the article mentions the "research predecessor" of Cedar, Umbra. Umbra is a project of TU (technical university) Munich, Germany.
They maybe should be better called *Kemper Strings" then?
I'm gonna vote for KarlValentinStruempfe.
I knew the C++ strings were optimized so. I do not like calling them "German". First time I see them called so (I know it, you can search yourself, as SSO -short string opt.), and looks as some kind of nationalist pride thing to me. Is certainly not a unique or new idea, many scheme/lisps implementations do that for strings AND numbers.
Downvotes coming from other connationals :) love you! I know… never say anything bad about Vaterland
Downvotes coming from other connationals :) love you! I know… never say anything bad about Vaterland
What do you like to call Hungarian notation?
"System's Horrendous Pile Of Shit".
If anyone ever referred to Apps Hungarian that would be "Simonyi's Wish For A Proper Type System", but nobody ever does.
If anyone ever referred to Apps Hungarian that would be "Simonyi's Wish For A Proper Type System", but nobody ever does.
I don’t know any other name for it. While this strings are basically SSO (or a twist of it).
From TFA and AndyP's slides it seems to specifically refer to a variant of SSO where, for large strings, a fixed-sized prefix of the string is stored along-side the pointer, in the same location as that fixed-size prefix would be fore SSO strings. This means that strings lacking a common prefix can be quickly compared without pointer-chasing (or even knowing if they are small vs large).
Well read.
basically SSO (or a twist of it)
basically SSO (or a twist of it)
C++ strings are not "optimized so". C++ strings (generally) do SSO (up to 23 bytes depending on implementation), these also do SSO but only 8 bytes (to a total of 12), the first 4 bytes are always stored inline for fast lookup even when the rest of the string is on the heap (in which case they're duplicated), and the strings are limited to 4GB (32 bits length). IIRC they also have a bunch of other limitations (e.g. they're not really extensible, by design).
Which is why they're "everywhere"... in databases, especially columnar storage.
Which is why they're "everywhere"... in databases, especially columnar storage.
Yes. Sorry. That was not 100% correct. Still, your words (my emphasis)
>C++ strings are not "optimized so". C++ strings (generally) do SSO (up to 23 bytes depending on implementation), these also do SSO but only 8 bytes (to a total of 12)
That is what I meant. I would (like you did) call it SSO still.
>C++ strings are not "optimized so". C++ strings (generally) do SSO (up to 23 bytes depending on implementation), these also do SSO but only 8 bytes (to a total of 12)
That is what I meant. I would (like you did) call it SSO still.
According to TFA, the name was coined by Andy Pavlo, who did his undergrad in New York, Doctorate in Rhode Island, and now teaches in Pittsburgh. I see no indication that he is German.
[edit]
Lecture slide with the term is also linked from TFA: https://15721.courses.cs.cmu.edu/spring2024/slides/05-execut...
[edit]
Lecture slide with the term is also linked from TFA: https://15721.courses.cs.cmu.edu/spring2024/slides/05-execut...
Andy Pavlo, ask anybody who knows him, is a very interesting character. I’m not sure if he really coined the name, or ist just a joke, as the one about his daughter (which I do both find funny at all). The database world (in which I was, is very interesting!) ;)
Interesting to see a deepdive about string formats. I hadn't thought very deeply about it before.
I do agree with the string imutable argument. Mutable and imutable strings have different usecases and design tradeoffs. They perhaps shouldn't be the same type at all.
The transient string is particularly brilliant. Ive worked with some low level networking code in c, and being able to create a string containing the "payload" by pointing directly to an offset in the raw circular packet buffer is very clean. (the alternative is juggling offsets, or doing excessive memcpy)
So beyond the database usecase it's a clever string format.
It would be nice to have an ISO or equivalent specification on it though.
I do agree with the string imutable argument. Mutable and imutable strings have different usecases and design tradeoffs. They perhaps shouldn't be the same type at all.
The transient string is particularly brilliant. Ive worked with some low level networking code in c, and being able to create a string containing the "payload" by pointing directly to an offset in the raw circular packet buffer is very clean. (the alternative is juggling offsets, or doing excessive memcpy)
So beyond the database usecase it's a clever string format.
It would be nice to have an ISO or equivalent specification on it though.
> The transient string is particularly brilliant. Ive worked with some low level networking code in c, and being able to create a string containing the "payload" by pointing directly to an offset in the raw circular packet buffer is very clean. (the alternative is juggling offsets, or doing excessive memcpy)
It's not anything special? That's just `string_view` (C++17). Java also used to do that as an optimisation (but because it was implicit and not trivial to notice it caused difficult do diagnose memory leaks, IIRC it was introduced in Java 1.4 and removed in 1.7).
It's not anything special? That's just `string_view` (C++17). Java also used to do that as an optimisation (but because it was implicit and not trivial to notice it caused difficult do diagnose memory leaks, IIRC it was introduced in Java 1.4 and removed in 1.7).
> It's not anything special? That's just `string_view` (C++17)
Just because something already exists in some language doesn't make it less clever. It's not very widespread, and it's very powerful when applicable.
This format can handle "string views" with the same logic as "normal strings" without relying on interfaces or inheritance overhead.
it's clever.
Just because something already exists in some language doesn't make it less clever. It's not very widespread, and it's very powerful when applicable.
This format can handle "string views" with the same logic as "normal strings" without relying on interfaces or inheritance overhead.
it's clever.
> It's not very widespread
It is tho?
> and it's very powerful when applicable.
I don't believe I stated or even hinted otherwise?
> This format can handle "string views" with the same logic as "normal strings" without relying on interfaces or inheritance overhead.
"owned" and "borrowed" strings have different lifecycles and if you can't differentiate them easily it's very easy to misuse a borrowed string into an UAF (or as Java did into a memory leak). That is bad.
And because callees usually know whether they need a borrowed string, and they're essentially free, the utility of making them implicit is close to nil.
Which is why people have generally stopped doing that, and kept borrowed strings as a separate type. Without relying on interfaces or inheritance.
> it's clever.
The wrong type thereof. It's clever in the same way java 1.4's shared substring were clever, with worse consequences.
It is tho?
> and it's very powerful when applicable.
I don't believe I stated or even hinted otherwise?
> This format can handle "string views" with the same logic as "normal strings" without relying on interfaces or inheritance overhead.
"owned" and "borrowed" strings have different lifecycles and if you can't differentiate them easily it's very easy to misuse a borrowed string into an UAF (or as Java did into a memory leak). That is bad.
And because callees usually know whether they need a borrowed string, and they're essentially free, the utility of making them implicit is close to nil.
Which is why people have generally stopped doing that, and kept borrowed strings as a separate type. Without relying on interfaces or inheritance.
> it's clever.
The wrong type thereof. It's clever in the same way java 1.4's shared substring were clever, with worse consequences.
> "owned" and "borrowed"
> java 1.4's
You're getting into pedantics about specific languages and their implementation. I never made a statement about C++ or java. I work in primarily in c99 myself.
> the utility of making them implicit is close to nil. > Without relying on interfaces or inheritance.
Implement a function that takes three strings without 3! permutations of that function either explicitly or implicitly created.
You're getting into pedantics about specific languages and their implementation. I never made a statement about C++ or java. I work in primarily in c99 myself.
> the utility of making them implicit is close to nil. > Without relying on interfaces or inheritance.
Implement a function that takes three strings without 3! permutations of that function either explicitly or implicitly created.
> You're getting into pedantics about specific languages
No, I'm using terms which clearly express what I'm talking about, and referring to actual historical experience with these concerns.
> Implement a function that takes three strings without 3! permutations of that function either explicitly or implicitly created.
In the overwhelming majority of cases this is a nonsensical requirement, if the function can take 3 borrowed strings you just implement a single function which takes 3 borrowed strings.
In the (rare) situation where optimising for maybe-owned makes sense, you use a wrapper type over "owned or borrowed". Which still needs no "interface or inheritance".
No, I'm using terms which clearly express what I'm talking about, and referring to actual historical experience with these concerns.
> Implement a function that takes three strings without 3! permutations of that function either explicitly or implicitly created.
In the overwhelming majority of cases this is a nonsensical requirement, if the function can take 3 borrowed strings you just implement a single function which takes 3 borrowed strings.
In the (rare) situation where optimising for maybe-owned makes sense, you use a wrapper type over "owned or borrowed". Which still needs no "interface or inheritance".
I never really put much thought into it either, until I started playing with Rust, which pretty much supports every common way to use strings out there. Mostly for compatibility sake, but still, it's wild all the same.
Title should mention (2024). Some of the info was already outdated back then [1]
https://news.ycombinator.com/item?id=41176051
https://news.ycombinator.com/item?id=41176051
"Optimized" string types are everywhere and I bet that multiple people have already created string types almost identical to German strings. But the memory savings are small and they are not more efficient than ordinary strings. For string comparison you compare the pointers, which is cheaper than comparing two pairs of registers. If the pointers mismatch you compare the (cached) hashes and only if they match do you need to compare characters. For the prefix query, starts_with(content, 'http'), just store a string of the four-character prefix. With immutable strings the overhead is just one pointer.
Do you have a pointer to real world data about the effectiveness of these optimizations? I learned about it (SSO, in std lib which is basically the same) in an article which really made it look as that would make anything in C++ blazing fast. In the codebases I worked, a couple of times, I did measure (what you shoud do before optimizing) and the results where between absolutely negligible to worst when active. But that were 3 data points. Mind you one in a real time database.
[deleted]
> We would like to have a string that is very cheap to construct and points to a region of memory that is currently valid, but may become invalid later without the string having control over it.
> This is where transient strings come in. They point to data that is currently valid, but may become invalid later, e.g., when we swap out the page on which the payload is stored to disk after we’ve released the lock on the page.
> Creating them has virtually no overhead: They simply point to an externally managed memory location. No memory allocation or data copying is required during construction! When you access a transient string, the string itself won’t know whether the data it points to is still valid, so you as a programmer need to ensure that every transient string you use is actually still valid. So if you need to access it later, you need to copy it to memory that you control.
Hm. What if I don't bother with that and I just read from the transient string? It's probably still good.
> In C, strings are just a sequence of bytes with the vague promise that a \0 byte will terminate the string at some point.
> This is a very simple model conceptually, but very cumbersome in practice:
> What if your string is not terminated? If you’re not careful, you can read beyond the intended end of the string, a huge security problem!
This sounds like a problem that transient strings were designed to exemplify. How do they improve on the C model?
-----
I was interested that the short strings use a full 32-bit length field. That's a lot of potential length for a string of at most 12 characters.
If we shaved that down to the four bits necessary to represent a number from 0-12, we'd save 28 bits, which is 3.5 characters. Adding three characters to the content would bring the potential length of a short string up to 15, requiring 0 additional length bits. And we'd have four bits left over.
I assume we aren't worried about this because strings of length 13-15 are already rare and it adds a huge amount of complexity to parsing the string, but it was fun to think about.
> This is where transient strings come in. They point to data that is currently valid, but may become invalid later, e.g., when we swap out the page on which the payload is stored to disk after we’ve released the lock on the page.
> Creating them has virtually no overhead: They simply point to an externally managed memory location. No memory allocation or data copying is required during construction! When you access a transient string, the string itself won’t know whether the data it points to is still valid, so you as a programmer need to ensure that every transient string you use is actually still valid. So if you need to access it later, you need to copy it to memory that you control.
Hm. What if I don't bother with that and I just read from the transient string? It's probably still good.
> In C, strings are just a sequence of bytes with the vague promise that a \0 byte will terminate the string at some point.
> This is a very simple model conceptually, but very cumbersome in practice:
> What if your string is not terminated? If you’re not careful, you can read beyond the intended end of the string, a huge security problem!
This sounds like a problem that transient strings were designed to exemplify. How do they improve on the C model?
-----
I was interested that the short strings use a full 32-bit length field. That's a lot of potential length for a string of at most 12 characters.
If we shaved that down to the four bits necessary to represent a number from 0-12, we'd save 28 bits, which is 3.5 characters. Adding three characters to the content would bring the potential length of a short string up to 15, requiring 0 additional length bits. And we'd have four bits left over.
I assume we aren't worried about this because strings of length 13-15 are already rare and it adds a huge amount of complexity to parsing the string, but it was fun to think about.
I really enjoyed this article. The storing in-place of a prefix is a neat idea for faster matching/sorting.
I wonder if they also have the concept of a reverse string which stores the (reversed) suffix instead and stores the short strings backward.
Niche, but would be fast for heavy ends-with filters.
I wonder if they also have the concept of a reverse string which stores the (reversed) suffix instead and stores the short strings backward.
Niche, but would be fast for heavy ends-with filters.
If you want to improve equality matching for longer strings, you could even store a 4B hash of the entire string instead of the prefix. I guess that should work well if you equality match on URLs since their prefix is always "http".
This is actually really similar to how SQL Server has long encoded it's varchar(max) format as I understand it. Short text is stored on the row page, but longer text is bumped to a different page.
Postgres does the same thing, however AFAIK postgres does not use a fixed-size string which happens to have inline string data: text is always variable, and stored inline up to 127 bytes (after compression).
These are different because the inline segment is fixed-size, and always exposes a 4 bytes prefix inline even when the buffer is stored out of line.
These are different because the inline segment is fixed-size, and always exposes a 4 bytes prefix inline even when the buffer is stored out of line.
Joel had a very nice quote - the whole history of C/C++ is them trying to deal with strings. In a way it is both worrying and encouraging that 50 years in there is still development in the area.
The added question mark in the HN submission makes little sense.
It also makes it grammatically incorrect. If it were actually a question it should be, “Why are German strings everywhere?”
The other form seems to be an Indian English colloquialism.
Do you mean "Why German strings are everywhere?" as an interrogative form?
I doubt that's specific to India. I had a teacher in high school who was Greek and who characteristically asked us "what it could be?", meaning "what could it be?".
Questions in Mandarin Chinese use the same sentence structure as their related statements. I imagine this is really common across languages.
I doubt that's specific to India. I had a teacher in high school who was Greek and who characteristically asked us "what it could be?", meaning "what could it be?".
Questions in Mandarin Chinese use the same sentence structure as their related statements. I imagine this is really common across languages.
[deleted]
If I understood what I was reading about German Strings, I think UTF-8 could add complications to these things.
I think statistically still those short string fall in the lower 128 codes which is ascii.
Not really, no.
The main difference is that you don't know how many code points you have in the prefix as they use variable encoding so it can be up to four but as little as one. I imagine the choice of four bytes for the prefix was actually done specifically for this reason. That's the maximum length of a UTF-8 code point.
The length is not the number of characters anymore but just the size of the string.
Apart from that, it should work exactly the same.
The main difference is that you don't know how many code points you have in the prefix as they use variable encoding so it can be up to four but as little as one. I imagine the choice of four bytes for the prefix was actually done specifically for this reason. That's the maximum length of a UTF-8 code point.
The length is not the number of characters anymore but just the size of the string.
Apart from that, it should work exactly the same.
We chose 4B because that was the maximum number of bytes that would be unused otherwise (4B for the length, 8B for the pointer leaves 4B), the UTF8 encoding doesn't really matter.
Also, for UTF8 specifically, cutting code points in half is fine as long as all strings are valid UTF8. The UTF8 encoding is prefix free, i.e., no valid code point is a prefix of another valid code point, so for prefix matching we can usually just compare bytes.
It only gets more complicated if you add collations or want to match case-insensitively. But at that point you need to take into account all edge cases of the Unicode spec anyway.
Also, for UTF8 specifically, cutting code points in half is fine as long as all strings are valid UTF8. The UTF8 encoding is prefix free, i.e., no valid code point is a prefix of another valid code point, so for prefix matching we can usually just compare bytes.
It only gets more complicated if you add collations or want to match case-insensitively. But at that point you need to take into account all edge cases of the Unicode spec anyway.
> We chose 4B because that was the maximum number of bytes that would be unused otherwise
I'm sure you did but there is something funny reading this phrase while at the same time considering you have robbed two bits from your pointer to represent class - admittedly the only thing I find questionable in your design.
If that's the case it's a happy accident because having a full code point here is quite nice.
I'm sure you did but there is something funny reading this phrase while at the same time considering you have robbed two bits from your pointer to represent class - admittedly the only thing I find questionable in your design.
If that's the case it's a happy accident because having a full code point here is quite nice.
That's a good point. We just use pointer tagging in many different places (e.g. for pointer swizzling in our buffer pages), so including a few bits of information in a pointer just seemed obvious.
They just store bytes. A leading astral codepoint means your prefix store contains just one codepoint, but that doesn't really change anything per se.
> To solve these problems, Umbra, the research predecessor of CedarDB, invented what Andy Pavlo now affectionately (we assume ;)) calls “German-style strings”.
This is how Borland Turbo Pascal stored strings as far back as the first version in mid-80s.
Length followed by the string.
This is how Borland Turbo Pascal stored strings as far back as the first version in mid-80s.
Length followed by the string.
That's not what it's doing though.
Pascal strings are: { length, pointer }
In these strings:
For short strings it's storing:
Pascal strings are: { length, pointer }
In these strings:
For short strings it's storing:
{ length, string value}
{length, prefix, class, pointer }> Pascal strings are: { length, pointer }
The historical P-strings are just a pointer, with the length at the head of the buffer. Hence length-prefixed strings, and their limitation to 255 bytes (only one byte was reserved for the length, you can still see this in the most base string of freepascal: https://www.freepascal.org/docs-html/ref/refsu9.html).
The historical P-strings are just a pointer, with the length at the head of the buffer. Hence length-prefixed strings, and their limitation to 255 bytes (only one byte was reserved for the length, you can still see this in the most base string of freepascal: https://www.freepascal.org/docs-html/ref/refsu9.html).
{length, pointer}
{length, capacity, pointer}
I think is about the kind of union they use, to store it differently depending on the string length, not the fact of length+data. Anyway is/was also nothing remotely new (the idea) as many lisp and scheme implementations have done so for strings and numbers basically for ages.
Storing the prefix and the tagged union of pointer and inline data structure is big difference to Pascal strings though.
German-style strings is a way to store array of strings for columnar dbs. The idea is to have an array of metadata. Metadata has a fixed size (16 bytes) The metadata includes the string length and either a pair of pointer + string prefix or the full string for short strings. For some operations the string prefix is enough in many cases avoiding the indirection.
This is different from Pascal strings.
This is different from Pascal strings.