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

struct Str {
    char* s;
    int len;
};

StrVec

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

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

StrVecPage

• we allocate a block of memory
• strings are allocated from the end of the memory block
• at the beginning of the memory block we build an index of strings. For each string we have:
  • u32 offset of the string within the block, counting from the start of the page
  • u32 size
  • optional dataSize bytes of extra data

• StrVecPage header (~32 bytes on 64-bit: next, pageSize, nStrings, dataSize, currEnd)
• struct { u32 offset; u32 size; u8 data[dataSize]; } [] growing forward
• … not yet used space
• strings packed from the end, each 0-terminated

struct StrVecPage {
    struct StrVecPage* next;
    int pageSize;
    int nStrings;
    int dataSize;
    u8* currEnd;
};

Extra data per string

template <typename T>
struct StrVecWithData : StrVec {
    StrVecWithData() : StrVec(sizeof(T)) {}
    T* AtData(int i) const;
    int Append(Str s, const T& data);
};

Implementing operations

Appending a string

• we calculate how much memory inside a page it’ll need: s.len + 1 + 8 + dataSize. +1 is for 0-termination for compatibility with C APIs that take char*, and 8 bytes for offset and size
• if last has enough space, we add offset and size at the end of the index and copy the string from the end i.e. currEnd - (s.len + 1)
• if there is not enough space in the last page, we allocate a new page, set last->next and last

• int indexSlot = 8 + dataSize;
• char* indexEnd = pageStart + sizeof(StrVecPage) + nStrings * indexSlot
• 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*

Sorting

Split and join

StrVec is a string pool allocator

• you allocate with malloc() or new
• when you no longer need the 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

• each slot can carry extra T (StrVecWithData)
• Append caches last so bulk append is linear
• SortIndex() sorts without moving slots
• the API is Str (pointer + length), so strings can contain embedded NULs
• files moved from src/utils/ to src/base/

Cost vs. benefit

References