5 ms·

Interning strings saves a ton of space. I wish more programmers would use it. Back in the 32-bit days I was working on a large (multi GB) distributed Oracle d

Interning strings saves a ton of space. I wish more programmers would use it. Back in the 32-bit days I was working on a large (multi GB) distributed Oracle database system but I couldn't use transaction log shipping (don't ask). Database A was the "main" system and database B was the "replica". To keep them in sync I needed a program that would compare the two databases and then generate an update script that would make B look like A. Complicating things was that, for some reason, floating point data in binary format would never match exactly between the two systems, so all floats had to be exported as text. The first attempt by a junior dev was implemented in C#. Not only was it terribly slow, but it also ran out of memory. I wrote a new version in C that interned all strings using a hash table and a custom bump-allocator. I also exported every field in the database as a string, so I didn't have to deal with native types. Using this technique meant that a database record could be represented as a plain array of pointers to the interned strings. Since each string was only recorded once, and every field was a pointer to a string, should two database records have the same values then they must by definition point to the same string. Comparing database rows was as easy as doing a memcmp() on the two pointer arrays, one being a record from database A and the other being a the record from database B. Not only was the system incredibly fast, but it never took more than 150MB of memory to run.

gopalv 2y ago
This is mostly the real reason why interning gets used, to avoid long string comparisons over saving memory as such. Interned strings tend to not have a good cleanup mechanism, in a system where a lot of them are churned through. So often they tend to actually use more memory as data patterns evolve in a system. I use the same trick when parsing json, where a large set of rows tend to have the keys repeated & the conversion to columnar is easier if the keys are interned.
- kazinator 2y ago
  In Lisp, interning is not only used for saving on string comparisons. It's the basis of the symbol abstraction. Or perhaps not the basis, but interning is the only way symbols can correspond to a printed representation. Without interning, we don't have it that A and A are the same object. A symbol being an object with a durable identity is important because it can have properties other than just the string which gives it a name.
- o11c 2y ago
  If your language supports good strong/weak references and containers thereof, cleaning up dead interned strings isn't hard. I'm not aware of any language that provides this out-of-the-box, unfortunately. Why do so many languages make weak references such second-class citizens? Why do all containers suck so much that you have to implement your own (and that's hoping the language is actually efficient enough to let you?)
  - rscho 2y ago
    > not aware of any language that provides this out-of-the-box, unfortunately. Many lisps. Racket, for example.
  - wongarsu 2y ago
    > I'm not aware of any language that provides this out-of-the-box, unfortunately The currently most prominent example would be Rust. Rc<T> is a simple generic container that implements reference counting, and any instance of it can be downgraded to a Weak<T>. Or Arc<T> and std::sync::Weak<T> if it needs to be thread safe.
    - o11c 2y ago
      I've done it in C++, so Rust is probably capable of it if you add enough layers of rc refcell and whatever else it requires to fit into its restricted worldview. Does Rust actually have container implementations that do all of the following: * When walking the container (either iterating or looking up, even through a non-mutable reference), call a user-provided predicate (not just builtin "weak" like many languages have via weakset/weakkeymap/weakvaluemap) to detect if a node should be considered "dead", and if so transparently remove the node. [In my experience this is relatively easy to add when you're implementing the container algorithms yourself, though I've never done it for bulk algorithms yet.] * When looking up a key (which may have different type or identity), the lookup returns the actual key the container had. [This may be impossible for container implementations that split the key.]
      - duped 2y ago
kccqzy 2y ago
Here's another perspective: I was once asked to improve a custom data caching system that took too much memory even though it had string interning. (At that time, eviction had to be used on factors other than memory used.) String interning certainly helped with memory use but it wasn't enough. Eventually my solution was to compress each record of the dataset in memory. I found that this saved more memory than interning individual strings within each record. At that time I picked Google's snappy compression algorithm since it was already a dependency of the project, but these days I might have picked zstd with a negative compression level or lz4. This just goes to show that if your primary goal is to save memory, you should consider storing it compressed and then decompress on the fly when used. Modern compression algorithms are good and fast on moderately sized textual data. You might be surprised to learn how fast decompression is. There are of course other benefits to interning like using pointer equality as string equality, but these aren't a factor in my project.
- nostrademons 2y ago
  Many compression algorithms are effectively string interning that works on general-purpose binary data and adaptively pick the common substrings that are most repeated and assign them the smallest bit representations. That's why formats like XML and JSON compress so well: all those repeated string keys get stored once and then become sub-byte entries in a lookup table.
  - kccqzy 2y ago
    Good point! And since we can have sub-byte entries in a lookup table, no wonder why a simplistic string interning solution using pointer-sized entries in a lookup might not work as effectively to reduce memory used.
- zerd 2y ago
  We did a very similar thing in a previous project. Used protostuff to serialize each object, and snappy at the time to compress it. And a small proxy class to access it that decompressed on demand. Costs a few microseconds on read, but saved 4x the space (20GiB -> 5GiB IIRC). This was after interning etc. I'm sure you can save a lot more space if you compress batches of objects and store it column oriented, but will take a bit longer to decompress individual objects.
kazinator 2y ago
> I wish more programmers would use it. For instance, people writing blogs to explain Lisp, who then present some Javascript crud in which symbols are just character strings.
viraptor 2y ago
So a fun story about how interning numbers can go wrong: When compiling the apple's ui designs from the xml based xib to a binary nib, their compiler uses lots of interning. It's pretty cool for avoiding 20 copies of an empty string for example. But then they messed up and did the same thing with numbers while ignoring the type... Which means if you have a value 5.0 as a size somewhere, then your sequentially assigned ids will be: 1, 2, 3, 4, 5.0, 6,...
MrLeap 2y ago
> Complicating things was that, for some reason, floating point data in binary format would never match exactly between the two systems, so all floats had to be exported as text. Floating point weirdsies between systems is a well encountered quirk in multiplayer gamedev. It's the source of many recommendations that you do physics in fixed point.
- nyrikki 2y ago
  In oracle, a float by default is 126 binary, or 22 bytes. Probably something to do with ANSI history. It is even more painful than IEEE 754 ambiguity.
galkk 2y ago
String.Intern existed since .net 1.1 . If that was the only problem, then one could’ve, you know, just read the docs? https://learn.microsoft.com/en-us/dotnet/api/system.string.intern?view=net-9.0 https://learn.microsoft.com/en-us/dotnet/api/system.string.i...
hobs 2y ago
That's funny because I just have the database hash the rows and move on with my life, but that might have been a PITA back then.
deleted 2y ago
[deleted]

gopalv 2y ago

This is mostly the real reason why interning gets used, to avoid long string comparisons over saving memory as such. Interned strings tend to not have a good cleanup mechanism, in a system where a lot of them are churned through. So often they tend to actually use more memory as data patterns evolve in a system. I use the same trick when parsing json, where a large set of rows tend to have the keys repeated & the conversion to columnar is easier if the keys are interned.

kazinator 2y ago
In Lisp, interning is not only used for saving on string comparisons. It's the basis of the symbol abstraction. Or perhaps not the basis, but interning is the only way symbols can correspond to a printed representation. Without interning, we don't have it that A and A are the same object. A symbol being an object with a durable identity is important because it can have properties other than just the string which gives it a name.
o11c 2y ago
If your language supports good strong/weak references and containers thereof, cleaning up dead interned strings isn't hard. I'm not aware of any language that provides this out-of-the-box, unfortunately. Why do so many languages make weak references such second-class citizens? Why do all containers suck so much that you have to implement your own (and that's hoping the language is actually efficient enough to let you?)
- rscho 2y ago
  > not aware of any language that provides this out-of-the-box, unfortunately. Many lisps. Racket, for example.
- wongarsu 2y ago
  > I'm not aware of any language that provides this out-of-the-box, unfortunately The currently most prominent example would be Rust. Rc<T> is a simple generic container that implements reference counting, and any instance of it can be downgraded to a Weak<T>. Or Arc<T> and std::sync::Weak<T> if it needs to be thread safe.
  - o11c 2y ago
    I've done it in C++, so Rust is probably capable of it if you add enough layers of rc refcell and whatever else it requires to fit into its restricted worldview. Does Rust actually have container implementations that do all of the following: * When walking the container (either iterating or looking up, even through a non-mutable reference), call a user-provided predicate (not just builtin "weak" like many languages have via weakset/weakkeymap/weakvaluemap) to detect if a node should be considered "dead", and if so transparently remove the node. [In my experience this is relatively easy to add when you're implementing the container algorithms yourself, though I've never done it for bulk algorithms yet.] * When looking up a key (which may have different type or identity), the lookup returns the actual key the container had. [This may be impossible for container implementations that split the key.]
    - duped 2y ago

kccqzy 2y ago

Here's another perspective: I was once asked to improve a custom data caching system that took too much memory even though it had string interning. (At that time, eviction had to be used on factors other than memory used.) String interning certainly helped with memory use but it wasn't enough. Eventually my solution was to compress each record of the dataset in memory. I found that this saved more memory than interning individual strings within each record. At that time I picked Google's snappy compression algorithm since it was already a dependency of the project, but these days I might have picked zstd with a negative compression level or lz4. This just goes to show that if your primary goal is to save memory, you should consider storing it compressed and then decompress on the fly when used. Modern compression algorithms are good and fast on moderately sized textual data. You might be surprised to learn how fast decompression is. There are of course other benefits to interning like using pointer equality as string equality, but these aren't a factor in my project.

nostrademons 2y ago
Many compression algorithms are effectively string interning that works on general-purpose binary data and adaptively pick the common substrings that are most repeated and assign them the smallest bit representations. That's why formats like XML and JSON compress so well: all those repeated string keys get stored once and then become sub-byte entries in a lookup table.
- kccqzy 2y ago
  Good point! And since we can have sub-byte entries in a lookup table, no wonder why a simplistic string interning solution using pointer-sized entries in a lookup might not work as effectively to reduce memory used.
zerd 2y ago
We did a very similar thing in a previous project. Used protostuff to serialize each object, and snappy at the time to compress it. And a small proxy class to access it that decompressed on demand. Costs a few microseconds on read, but saved 4x the space (20GiB -> 5GiB IIRC). This was after interning etc. I'm sure you can save a lot more space if you compress batches of objects and store it column oriented, but will take a bit longer to decompress individual objects.

kazinator 2y ago

> I wish more programmers would use it. For instance, people writing blogs to explain Lisp, who then present some Javascript crud in which symbols are just character strings.

viraptor 2y ago

So a fun story about how interning numbers can go wrong: When compiling the apple's ui designs from the xml based xib to a binary nib, their compiler uses lots of interning. It's pretty cool for avoiding 20 copies of an empty string for example. But then they messed up and did the same thing with numbers while ignoring the type... Which means if you have a value 5.0 as a size somewhere, then your sequentially assigned ids will be: 1, 2, 3, 4, 5.0, 6,...

MrLeap 2y ago

> Complicating things was that, for some reason, floating point data in binary format would never match exactly between the two systems, so all floats had to be exported as text. Floating point weirdsies between systems is a well encountered quirk in multiplayer gamedev. It's the source of many recommendations that you do physics in fixed point.

nyrikki 2y ago
In oracle, a float by default is 126 binary, or 22 bytes. Probably something to do with ANSI history. It is even more painful than IEEE 754 ambiguity.

galkk 2y ago

String.Intern existed since .net 1.1 . If that was the only problem, then one could’ve, you know, just read the docs? https://learn.microsoft.com/en-us/dotnet/api/system.string.intern?view=net-9.0 https://learn.microsoft.com/en-us/dotnet/api/system.string.i...

hobs 2y ago

That's funny because I just have the database hash the rows and move on with my life, but that might have been a PITA back then.

deleted 2y ago

[deleted]