Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why German Strings Are Everywhere?

cedardb.com

Post reply on HN
Print view View original

31–40 of 58 posts

Re: Why German Strings Are Everywhere?

#31

Post by StopDisinfo910 »

msichert wrote: post #22
StopDisinfo910 wrote: post #11

Earlier quoted context omitted.

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…

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 usual…

> 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.

Re: Why German Strings Are Everywhere?

#32

Post by msichert »

xnorswap wrote: post #7

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.

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".

Re: Why German Strings Are Everywhere?

#34

Post by masklinn »

kardianos wrote: post #17

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.

Re: Why German Strings Are Everywhere?

#35

Post by msichert »

StopDisinfo910 wrote: post #31
msichert wrote: post #22

Earlier quoted context omitted.

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 usual…

> 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.

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.

Re: Why German Strings Are Everywhere?

#36

Post by thaumasiotes »

> 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.

Re: Why German Strings Are Everywhere?

#37

Post by ahartmetz »

f1shy wrote: post #5
ahartmetz wrote: post #2

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.

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…

Doesn't seem nationalist to me because the name seems to have been coined by the people at Cedar, not TU Munich.

Re: Why German Strings Are Everywhere?

#38

Post by magnat »

maweki wrote: post #18
f1shy wrote: post #5

Earlier quoted context omitted.

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…

What do you like to call Hungarian notation?

Also:

* Reverse polish notation

* Chinese remainder theorem

* Byzantine generals problem

Re: Why German Strings Are Everywhere?

#39

Post by masklinn »

xnorswap wrote: post #12
WaitWaitWha wrote: post #10

> 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.

That's not what it's doing though. Pascal strings are: { length, pointer } In these strings: For short strings it's storing: { length, string value} for longer strings, it's storing {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).

    {length, pointer}
or

    {length, capacity, pointer}
is struct / record strings, and what pretty much every modern language does (possibly with optimisations e.g. SSO23 is basically a p-string when inline, but can move out of line into a full record string).

Re: Why German Strings Are Everywhere?

#40

Post by tracker1 »

aDyslecticCrow wrote: post #20

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 "pa…

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.
Post reply on HN