libstringintern

A thread safe lock free C++ library for interning strings to save heap space. Smaller heaps generally mean faster applications due to cache locality and less swapping to disk. The other upside is you can store more stuff in RAM.

Use case

You have an in-memory database with 100 million customer records with associated address details. You therefore have 100 million state and country strings associated with those records. That will use a lot of memory.

When strings are interned you only ever have one instance of the string plus a reference instance per record which is 4 bytes in size.

Let's do the math(s)

32bit: 100m * 'Mississippi\0' = 1144MB, 100m * 4B = 381MB, total = 1525MB
64bit: 100m * 'Mississippi\0' = 1144MB, 100m * 8B = 762MB, total = 1907MB
Interned: 1 * 'Mississippi\0' = 12B, 100m * 4B = 381MB

This example is for a fairly short string, but the saving is still valuable. Larger strings have an even bigger pay-off.

How it works

Interned strings are stored in pages, grouped by string size, a bit like tcmalloc
Pages are 2MB in size to take advantage of THP
Each string is hashed using XX64 with the low order bytes used as an index into the page
If the index refers to a location in the page that is free the string and hash are committed to the page and the caller gets a reference to the string
If the index is already taken then we compare the hashes and if they match we return a reference to the entry
If the hashes did not match then allocate a new page and add the string and hash returning the string reference
The host application turns the reference into a real pointer to use the string, a bit like std::weak_ptr
References are 32bit values made up from PAGE(16):INDEX(16). On 64bit systems these use half the storage space of a pointer.
Interned strings are immutable

Code example

  StringIntern intern;
  auto ref1 = intern.Add("Mississippi");
  std::cout << intern.ToString(ref1) << std::endl;
  
  auto ref2 = intern.Add("Mississippi");
  std::cout << ref1 == ref2 ? "Match" : "Doesn't match" << std::endl;

Testing