Much ado about the strings

No STL for you

• ³²⁄₂₄ bytes for the header
• memory allocator overhead
  • allocator metadata
  • padding due to rounding allocations to at least 16 bytes

Design and implementation of StrVec

• per-string overhead of only 8 bytes
• strings are laid out next to each other in memory

StrVec

• backing memory is allocated in singly-linked pages
• similar to std::vector, we start with small page and increase the size of the page. This strikes a balance between speed of accessing a string at random index and wasted space
• unlike std::vector we don’t reallocate memory (most of the time). That saves memory copy when re-allocating backing space

struct StrVec {
    StrVecPage* first = nullptr;
    int nextPageSize = 256;
    int size = 0;
}

StrVecPage

• we allocate a block of memory
• strings are allocated from the end of memory block
• at the beginning of the memory block we build and index of strings. For each string we have:
  • u32 size
  • u32 offset of the string within memory block, counting from the beginning of the block

• StrVecPage
• struct { size u32; offset u32 } []
• … not yet used space
• strings

struct StrVecPage {
    struct StrVecPage* next;
    int pageSize;
    int nStrings;
    char* currEnd;
}

Implementing operations

Appending a string

• we calculate how much memory inside a page it’ll need: str::Len(string) + 1 + sizeof(u32) + sizeof(u32). +1 is for 0-termination for compatibility with C APIs that take char*, and 2xu32 for size and offset.
• If we have enough space in last page, we add size and offset at the end of index and append a string from the end i.e. `currEnd - (str::Len(string) + 1).
• If there is not enough space in last page, we allocate new page

• int indexEntrySize = sizeof(u32) + sizeof(u32); // size + offset
• char* indexEnd = (char*)pageStart + sizeof(StrVecPage) + nStrings*indexEntrySize
• int nBytesFree = (int)(currEnd - indexEnd)

Removing a string

Replacing a string or inserting in the middle

Iteration

struct iterator {
  const StrVec* v;
  int idx;
  
  // perf: cache page, idxInPage from prev iteration
  int idxInPage;
  StrVecPage* page;
}

Optimized search

Compacting

Representing a nullptr char*

StrVec is a string pool allocator

• you allocate with malloc() or new
• when you no longer need to object, you call free() or delete

Testing

Potential tweaks and optimization

Interleaving index and strings

Varint encoding of size and offset

Implicit size

Storing index separately

The evolution of StrVec

Cost vs. benefit

References