Five Kinds of String: How V8 Keeps Strings Cheap

TL;DR: A V8 string is not a buffer of characters. It is one of five representations - sequential, cons, sliced, thin or external - tagged in three bits of its instance type. Concatenation builds a rope (a cons string) instead of copying; substring builds a view (a sliced string) instead of copying; internalization builds a pointer (a thin string) instead of copying. The characters are copied only when something actually needs a flat buffer, and String::Flatten is where that copy happens.

The naive way to implement JavaScript strings is to allocate a fresh buffer for every value, copy the characters in, and throw the old buffer away. Every + is an allocation and a memcpy. Every substring is an allocation and a memcpy. Every property lookup by string name is an allocation and a memcpy of the key.

V8 refuses to do that. A string in V8 is a small heap object with a shape, and the shape determines where the characters live - if they live anywhere at all. Five representations cover the cases, and each one exists to answer a specific question cheaply.

The tag: three bits in the instance type

The representation is not a field. It is three bits in the instance type, which means checking it is a mask of an integer that is already in a register:

cpp
// src/objects/string.tq:62
bitfield struct StringInstanceType extends uint16 {
  representation: StringRepresentationTag: 3 bit;
  is_one_byte: bool: 1 bit;
  is_uncached: bool: 1 bit;
  is_shared: bool: 1 bit;
  is_not_internalized: bool: 1 bit;
}

The tag itself:

cpp
// src/objects/string.tq:54
extern enum StringRepresentationTag extends uint32 {
  kSeqStringTag,
  kConsStringTag,
  kExternalStringTag,
  kSlicedStringTag,
  kThinStringTag
}

The is_one_byte bit is the other half of the story and it is not in the map - it is in the instance type, next to the representation. So the two questions “what kind of string is this?” and “is it Latin-1 or UTF-16?” are answered by a single load of one 16-bit field.

The five representations, as Torque sees them:

cpp
// src/objects/string.tq:140
extern class SeqOneByteString extends SeqString {
  const chars[length]: char8;
}

@doNotGenerateCast
@cppObjectLayoutDefinition
extern class SeqTwoByteString extends SeqString {
  const chars[length]: char16;
}

@doNotGenerateCast
@cppObjectLayoutDefinition
extern class SlicedString extends String {
  parent: String;
  offset: Smi;
}

@doNotGenerateCast
@cppObjectLayoutDefinition
extern class ThinString extends String {
  actual: InternalizedString;
}

Note what SeqString has that the others do not: the characters are in the object. SlicedString has a parent and an offset. ThinString has a pointer to the internalized version. ConsString (defined a few lines earlier in the same file) has first and second.

Sequential strings: the only ones with characters in them

A sequential string is the flat case: an object header, a length, and the characters. There are two flavours, one-byte (Latin-1, char8) and two-byte (UTF-16, char16), and the choice is made once, at creation, based on the source data.

The encoding matters a lot: a one-byte string uses half the memory of a two-byte string, and most real-world text - and all of ASCII - fits in one byte. But the choice is sticky. String::IsOneByteRepresentationUnderneath has to walk a cons string’s first half, or a thin string’s target, or a sliced string’s parent, to find the answer:

cpp
// src/objects/string.tq:25
  macro IsOneByteRepresentationUnderneath(): bool {
    let string = this;
    while (true) {
      typeswitch (string) {
        case (cons: ConsString): {
          dcheck(cons.IsFlat());
          string = cons.first;
        }
        case (thin: ThinString): {
          // Internalized strings can't change representation.
          dcheck(
              thin.IsOneByteRepresentation() ==
              thin.actual.IsOneByteRepresentation());
          return thin.IsOneByteRepresentation();
        }
        case (slice: SlicedString): {
          string = slice.parent;
        }
        case (str: String): {
          return str.IsOneByteRepresentation();
        }
      }
    }
    VerifiedUnreachable();
  }

The comment “internalized strings can’t change representation” is load-bearing: an internalized string is shared between contexts and threads, so its representation must never change under anyone’s feet.

Cons strings: concatenation without copying

"foo" + "bar" does not copy six characters. It allocates a ConsString - a header, a length, and two pointers - and points them at the two operands:

text

        +------------------+
        |   ConsString     |
        |  first  ---------+----> SeqOneByteString "foo"
        |  second ---------+----> SeqOneByteString "bar"
        |  length = 6
        +------------------+

The consequence is that concatenation is O(1) but the result is a tree. A loop that appends to a string ten thousand times builds a tree of depth logarithmic or linear depending on how the appends are associated, and any operation that needs the actual characters has to walk it.

ConsString::Get is the walk:

cpp
// src/objects/string.cc:2135
uint16_t ConsString::Get(
    uint32_t index, const SharedStringAccessGuardIfNeeded& access_guard) const {
  DCHECK(index >= 0 && index < this->length());

  // Check for a flattened cons string
  if (second()->length() == 0) {
    Tagged<String> left = first();
    return left->Get(index);
  }

  Tagged<String> string = Cast<String>(this);

  while (true) {
    if (StringShape(string).IsCons()) {
      Tagged<ConsString> cons_string = Cast<ConsString>(string);
      Tagged<String> left = cons_string->first();
      if (left->length() > index) {
        string = left;
      } else {
        index -= left->length();
        string = cons_string->second();
      }
    } else {
      return string->Get(index, access_guard);
    }
  }

That is str[0] on a cons string: descend the tree, subtracting lengths until you find the leaf that owns the index. Depth is O(log n) for a balanced tree, O(n) for a left-leaning one.

The 13-character threshold

Making a cons string is not free - it is a heap allocation and two write barriers. For short strings the copy is cheaper. V8 picks a threshold of 13 characters:

cpp
// src/objects/string.h:1099
  // Minimum length for a cons string.
  static const uint32_t kMinLength = 13;

and the built-in string-add honours it:

cpp
// src/builtins/builtins-string-gen.cc:518
    Label non_cons(this, {&var_left, &var_right});
    Label slow(this, Label::kDeferred);
    GotoIf(Uint32LessThan(new_length, Uint32Constant(ConsString::kMinLength)),
           &non_cons);

    result =
        AllocateConsString(new_length, var_left.value(), var_right.value());
    Goto(&done);

    BIND(&non_cons);

    Comment("Full string concatenate");

Below 13 characters, V8 allocates a sequential string and copies. At 13 and above, it allocates a cons string and does not. This is why "a" + "b" and "a" + "b" + "c" are cheap and why s += "x" in a loop eventually becomes expensive: it is not the copy, it is the tree.

Sliced strings: a substring is a view

str.substring(10, 20) does not copy either. A SlicedString holds a pointer to the parent and an offset:

cpp
// src/objects/string.tq:152
extern class SlicedString extends String {
  parent: String;
  offset: Smi;
}

The parent stays alive as long as the slice does, which is the price of the view. The offset is a Smi, so it is a tagged 32-bit integer - cheap to add to a base pointer.

Slices have their own 13-character threshold, for the same reason cons strings do - a slice of 3 characters is not worth a heap object plus keeping the parent alive:

cpp
// src/objects/string.h:1209
  // Minimum length for a sliced string.
  static const uint32_t kMinLength = 13;

cpp
// src/builtins/builtins-string-gen.cc:2164
      // Short slice.  Copy instead of slicing.
      GotoIf(IntPtrLessThan(substr_length,
                            IntPtrConstant(SlicedString::kMinLength)),
             &next);

There is one more subtlety in the Torque StringToSlice macro: a slice of a slice accumulates offsets rather than nesting, and the accumulated offset is clamped with 32-bit wrapping arithmetic to keep a corrupted offset from reading out of the sandbox:

cpp
// src/objects/string.tq:303
      case (s: SlicedString): {
        // Clamp accumulated offsets using 32-bit wrapping arithmetic to prevent
        // out-of-sandbox reads under memory corruption (see b/519768343).
        const slicedOffset: int32 =
            TruncateIntPtrToInt32(Convert<intptr>(s.offset));
        const newOffset: int32 = TruncateIntPtrToInt32(offset) + slicedOffset;
        offset = Convert<intptr>(Unsigned(newOffset));
        string = s.parent;

Thin strings: internalization without copying

When you use a string as a property name, V8 internalizes it - there must be exactly one object per unique name so that property lookups can compare pointers.

If the string can be internalized in place, V8 just changes its map and it becomes an InternalizedString. If it cannot - because it is in shared space, or because its buffer is already in use - the original is turned into a ThinString that points at the internalized copy. The original’s characters stay where they are; the object just becomes a pointer:

cpp
// src/objects/string.cc:139
void String::MakeThin(IsolateT* isolate,
                      Tagged<InternalizedString> internalized) {
  DisallowGarbageCollection no_gc;
  DCHECK_NE(this, internalized);

  SYNCHRONIZATION_POINT("MakeThinString");

  Tagged<Map> initial_map = map(kAcquireLoad);
  StringShape initial_shape(initial_map);

  DCHECK(!initial_shape.IsThin());

A thin string is, as the C++ header puts it, a “one-part cons string”: the same trick, with one operand.

The problem is that the hash field of a string is where the hash lives, and you cannot have both a hash and a “pointer to the internalized version” in the same 32 bits. V8 solves this with a forwarding table: the hash field stores an index, and a side table maps the index to the internalized string.

cpp
// src/objects/string-forwarding-table.h:16
// Mapping from forwarding indices (stored in a string's hash field) to
// internalized strings/external resources.
// The table is used to handle string transitions (temporarily until the next
// full GC, during which actual string transitions happen) that overwrite the
// string buffer. In particular these are Internalization and Externalization.
// The table is organised in "blocks". As writes only append new entries, the
// organisation in blocks allows lock-free writes. We need a lock only for
// growing the table (adding more blocks). When the vector holding the blocks
// needs to grow, we keep a copy of the old vector alive to allow concurrent
// reads while the vector is relocated.
class StringForwardingTable {

The blocks design is what makes it lock-free: writers only ever append, so they never need to take the mutex that the table-growth path holds.

The full GC is where the deferred transitions actually happen: the string’s hash field is overwritten with the real hash and the string becomes a thin string for real. Until then, a lookup of a forwarding index in the table gives you the internalized string.

External strings: characters that live outside the heap

An embedder can hand V8 a pointer to memory it owns and ask for a string that wraps it. That is an ExternalString: the characters are not in the V8 heap at all.

cpp
// src/objects/string.h:1257
V8_OBJECT class ExternalString : public UncachedExternalString {
  V8_IT_ABSTRACT;
  V8_IT_NO_AUTO_CHECKER;

 public:
  class BodyDescriptor;

  DECL_VERIFIER(ExternalString)

  inline void InitExternalPointerFields(Isolate* isolate);
  inline void VisitExternalPointers(ObjectVisitor* visitor);

Two details make external strings awkward in a moving GC: the resource pointer and the resource data pointer are ExternalPointers, which live in a separate indirection table so that a moving GC does not have to fix them up; and the string is always allocated in old space and registered with the heap’s external string table, because it must not move:

cpp
// src/heap/factory.cc:1534
  DirectHandle<Map> map = resource->IsCacheable()
                              ? external_one_byte_string_map()
                              : uncached_external_one_byte_string_map();
  Tagged<ExternalOneByteString> external_string =
      Cast<ExternalOneByteString>(New(map, AllocationType::kOld));
  DisallowGarbageCollection no_gc;
  external_string->InitExternalPointerFields(isolate());
  external_string->set_length(static_cast<int>(length));
  external_string->set_raw_hash_field(String::kEmptyHashField);
  external_string->SetResource(isolate(), resource);

  isolate()->heap()->RegisterExternalString(external_string);

The “cacheable” flag decides whether the data pointer is cached inside the string object or re-read from the resource on every access. Caching it is faster; not caching it means the embedder can mutate the buffer underneath V8 and have the change visible.

Why `str.length` is O(1) and `str[0]` might not be

This is the payoff of the whole design, and it falls straight out of it.

length is a field in the string header. Every representation has one, and for a cons string it is the sum of the two halves, maintained at construction. So str.length is a load, on every representation, always.

cpp
// src/objects/string.tq:51
  const length: int32;

str[0] is not a load. It is a dispatch:

sequential string: chars[offset] - a load.
sliced string: parent.Get(offset + index) - recurse.
cons string: walk the tree, subtracting lengths.
thin string: actual.Get(index) - one extra hop.

And the first thing most operations do is flatten. String::Flatten in C++ is the fast path plus the slow path:

cpp
// src/objects/string-inl.h:956
HandleType<String> String::Flatten(Isolate* isolate, HandleType<T> string,
                                   AllocationType allocation) {
  DisallowGarbageCollection no_gc;  // Unhandlified code.
  Tagged<String> s = *string;
  StringShape shape(s);

  // Shortcut already-flat strings.
  if (V8_LIKELY(shape.IsDirect())) return string;

  if (shape.IsCons()) {
    DCHECK(!HeapLayout::InAnySharedSpace(s));
    Tagged<ConsString> cons = Cast<ConsString>(s);
    if (!cons->IsFlat()) {
      AllowGarbageCollection yes_gc;
      DCHECK_EQ(*string, s);
      HandleType<String> result =
          SlowFlatten(isolate, Cast<ConsString>(string), allocation);
      DCHECK(result->IsFlat());
      DCHECK(string->IsFlat());  // In-place flattened.
      return result;
    }
    s = cons->first();
    shape = StringShape(s);
  }

The flattening is done in place: the cons string is mutated into a degenerate form where first points at the new flat string and second is the empty string. So the copy happens once, and every later access is cheap. The Torque version does the same thing:

cpp
// src/objects/string.tq:245
  let flat: String;
  if (cons.map == kConsOneByteStringMap) {
    const allocated = AllocateNonEmptySeqOneByteString(Unsigned(cons.length));
    StringWriteToFlatOneByte(
        cons, (&allocated.chars).GCUnsafeStartPointer(), 0, cons.length);
    flat = allocated;
  } else {
    const allocated = UnsafeCast<SeqTwoByteString>(
        AllocateNonEmptySeqTwoByteString(Unsigned(cons.length)));
    StringWriteToFlatTwoByte(
        cons, (&allocated.chars).GCUnsafeStartPointer(), 0, cons.length);
    flat = allocated;
  }
  cons.first = flat;
  cons.second = kEmptyString;
  return flat;

Note the dispatch on kConsOneByteStringMap - the flattening preserves the one-byte-ness of the original.

The string table

Everything above is about a single string. The string table is where V8 makes sure that two equal strings are the same object, which is what makes property lookup by name a pointer comparison.

The table is an open-addressed hash table with quadratic probing, held outside the V8 heap so that it can be rehashed without moving anything:

cpp
// src/objects/string-table.cc:77
// Data holds the actual data of the string table, including capacity and number
// of elements.
//
// It is a variable sized structure, with a "header" followed directly in memory
// by the elements themselves. These are accessed as offsets from the elements_
// field, which itself provides storage for the first element.
//
// The elements themselves are stored as an open-addressed hash table, with
// quadratic probing and Smi 0 and Smi 1 as the empty and deleted sentinels,
// respectively.
class StringTable::Data {

with a minimum capacity of 2048 entries and a load factor of at most 1/4:

cpp
// src/objects/string-table.cc:38
  static constexpr int kEntrySize = 1;
  static constexpr int kMaxEmptyFactor = 4;
  static constexpr int kMinCapacity = 2048;

The lookup is StringTable::LookupString, and the first thing it does is flatten:

cpp
// src/objects/string-table.cc:369
DirectHandle<InternalizedString> StringTable::LookupString(
    Isolate* isolate, DirectHandle<String> string) {

because you cannot hash a tree. Then it either finds the string already internalized, or resolves a forwarding index, or hashes it and probes:

cpp
// src/objects/string-table.cc:403
    uint32_t raw_hash_field = flat_string->raw_hash_field(kAcquireLoad);

    if (String::IsInternalizedForwardingIndex(raw_hash_field)) {
      const int index =
          String::ForwardingIndexValueBits::decode(raw_hash_field);
      result = direct_handle(
          isolate->string_forwarding_table()->GetForwardString(isolate, index),
          isolate);
    } else {

One nice detail: the hasher reports whether the content was entirely one-byte while it was hashing, so the table does not have to scan the string a second time to decide whether a one-byte internalized copy is needed:

cpp
// src/objects/string-table.cc:418
      bool one_byte_content = false;
      if (!Name::IsHashFieldComputed(raw_hash_field)) {
        raw_hash_field = flat_string->EnsureRawHash(&one_byte_content);
      } else if (Name::IsIntegerIndex(raw_hash_field)) {
        one_byte_content = true;
      }
      InternalizedStringKey key(flat_string, raw_hash_field, one_byte_content);
      result = LookupKey(isolate, &key);

Trade-offs

What it buys. Concatenation is O(1) instead of O(n). substring is O(1) instead of O(n). Internalization is O(1) instead of O(n). length is always a load. A program that builds large strings by appending never pays for a copy until something actually needs the flat buffer.

What it costs.

The copy is deferred, not avoided. Somebody eventually needs the characters, and then a copy happens - potentially a large one, at an unpredictable moment. String::Flatten allocating a multi-megabyte buffer in the middle of a request is a real failure mode.
Retained parents. A sliced string keeps its parent alive. Slicing a 10 MB string and keeping 3 characters keeps 10 MB alive.
Tree depth. str[0] on a deep cons tree is a walk. V8 mitigates this by flattening eagerly in the interpreter and in the parts of the runtime that need flat content, but the pathology exists for code that only ever indexes.
The forwarding table is a side channel. Every pending internalization costs a table entry and a hash-field encoding, and the transitions are only made real at the next full GC.
External strings escape the heap’s invariants. Their characters can be mutated underneath V8, and their lifetimes are the embedder’s problem.

The bottom line

A V8 string is a tagged union, and the tag is chosen so that the common operation is cheap: concatenation gets a cons string, slicing gets a sliced string, interning gets a thin string, and only genuine data gets a sequential string with the characters inside it.

The two invariants that make it all work: length is always a field, and flattening is done in place so it happens at most once per cons string. The memory model to keep is a string is a handle, not a buffer - and V8 only pays for the buffer when you ask for one.

The thing people get wrong

“Strings are immutable in JavaScript, so V8 can always share their buffers.” No. Immutability is a language guarantee about the characters. V8 still has to represent a string, and it represents it as a pointer to a rope, a slice of a bigger string, or another string entirely. The characters are copied when the rope is flattened, and the copy is not free.

The practical consequences are the ones worth internalising:

Building a string with += in a loop builds a rope, and the rope is flattened at some unpredictable later point. If you know the final length, build it in one go.
str.substring keeps the whole parent alive. If you keep a small piece of a large string, copy it out (str.slice() in some engines, or String(...)) rather than keeping the view.
str.length is cheap, str[0] might not be, and str === other is a pointer comparison only if both sides are internalized - which is why comparing two runtime-built strings is not as cheap as it looks.

The internalized strings the table hands out are exactly what the feedback vector stores: one canonical object per property name, so that the IC can compare pointers instead of characters.