String representation and performance

Prismio represents every String as a 16-byte pair. The same pair can hold a short string directly, own a heap allocation, or view a range inside another string. This page explains the representation, the invariants that make it sound, and the measurements that led to it.

This is an implementation deep dive for compiler and runtime contributors. It describes Prismio 0.1 at compiler commit 0064491c6338, not a stable ABI promise. Application developers should use the source-level standard-library boundary; code cannot select or observe a storage class.

What application developers need to know

• A String has the same source-level behavior in all three storage classes.
• Length, indexing, iteration, comparison, and slicing are byte-oriented in Prismio 0.1. Application-facing behavior belongs to the language documentation.
• A long substring can share the source string's storage internally. Prismio's ownership analysis keeps that source alive for as long as the substring needs it.
• Containers and foreign calls receive owned or temporary copies when their ownership or NUL-termination rules require one.
• The 16-byte layout and 2 GiB implementation limit described below apply to current 64-bit targets and may change in a later compiler version.

Representation at a glance

Tag bits in the length word select one of four storage classes:

The word, for a pair that is not inline: bits 0–30 are the length, bit 31 is INLINE, bit 32 VIEW, bit 33 marks an owned block whose capacity grew geometrically (the s = s + x append path), and bit 34 BORROWED. For an inline pair, bits 32–63 are string bytes, so every other tag is meaningful only when INLINE is clear — which is why the release mask tests them all at once.

A borrowed pair reads exactly like an owned long string: its pointer goes to C as it is, with no copy. It differs in two places only. Every release skips it, and str_own copies it, because a container slot or a String? keeps only the pointer and would release it. The tag is what lets a literal sit in a field, a Vec or a return beside owned Strings (added 2026-09-30). Before it, the ownership analysis had to decline the release of any place a literal could reach, and every owned String stored there leaked.

// PRISMIO_STR_UNOWNED = 0x1_8000_0000
free(word & PRISMIO_STR_UNOWNED
         ? NULL : ptr)

The design belongs to the family introduced in the Umbra: A Disk-Based System with In-Memory Performance paper and often called a German string or StringView. Prismio's additional property is that the view lifetime is carried by the ownership analysis instead of being left as a programmer obligation.

On the maintained tokenization benchmark—54,000 tokens of one to eight bytes cut from a 204 KB buffer—the complete sequence of changes measured as follows:

That is a 4.86× end-to-end improvement from the original representation. The final binary measured at 0.84× the C++ time and 0.23× the Rust owned-string time. At benchmark scale 1, Prismio's --verify ledger fell from 13,502 allocations to 2.

These figures are local microbenchmarks, not portable performance guarantees. They were collected in 31-sample alternating A/B runs on an Apple M5 system with 10 CPU cores, 16 GB of memory, macOS 25.5, and LLVM 23.1.1. The maintained suite builds C++ with clang++ -O3 -std=c++20 and Rust with rustc -C opt-level=3. Checksums are compared before timings are accepted.

The measured problem

The initial decision was driven by a profile rather than by the shape of another language's String. tokenization was the slowest row in Prismio's cross-language suite at 3.4× the C++ time.

Removing token materialization and moving input construction outside the timed region separated scanning from producing each token:

The scanner already matched the generated clang -O3 loop. charIsSpace inlined to a 64-bit bitmask test, byte access was a GEP followed by a load, and the copy loop vectorized. Producing a token accounted for the gap.

Interposing malloc showed the same boundary:

The interposed malloc count and the --verify count in the summary use different counters and benchmark scales; they should not be compared directly. The former includes allocator traffic from the whole process. The latter counts Prismio-managed allocations in the scale-1 workload.

C++ was faster because it usually did not allocate. On the measured platform, libc++'s std::string held each token in its small-string buffer. Prismio and the Rust owned-string version allocated once per token. A profile placed 67% of the Prismio run in the macOS allocator's free path, with over half of that time inside mach_absolute_time used by allocator quarantine bookkeeping.

This supported two independent changes: improve small-block recycling, then change the string representation so the common case does not allocate.

Why this representation family

Common string representations make different size and capability tradeoffs:

The exact capacities depend on implementation and target ABI. The comparison is about the design space, not an API compatibility claim. Raymond Chen's std::string implementation comparison describes the 22-byte libc++ form, and the string-rosetta-rs project collects the Rust representation variants.

Two properties made the German-string family a good fit for Prismio.

First, it remains 16 bytes. String was already a {ptr, i64} pair, so a local, parameter, or structure field containing one does not grow.

Second, the tags leave room for an unowned long form. A tokenizer can represent a token as a pointer and length into its input instead of allocating a separate buffer. Umbra calls this form a transient string and requires callers to copy it when it must outlive the source. Prismio uses the compiler's ownership analysis to prove the required lifetime instead.

This choice was not treated as an automatic win. Apache DataFusion reported that a direct StringView implementation initially slowed down almost every query until its construction and use paths were specialized. Each Prismio change was therefore measured against the preceding stage, and changes that measured flat or worse were removed.

Choosing the inline capacity from Prismio workloads

Copying Umbra's 12-byte choice without checking Prismio's allocation mix would have borrowed somebody else's workload. The compiler's str_with_capacity path was instrumented instead, then the compiler was run on its own front end.

The run observed 444,798 string allocations during prismio check src/main.psm:

More than half of the strings allocated by the compiler were four bytes or shorter. Any inline representation captures most of that traffic. The difference between 12, 14, and 22 bytes concerns the next fifteen percentage points, and many values beyond twelve bytes are substrings that the view class can represent without copying.

An allocator-wide histogram gave a misleading answer: 47.9% of requests at 16 bytes or less and 35.3% at 64 bytes or less. It mixed AST nodes and list blocks with strings. Only instrumentation at str_with_capacity measured the relevant population.

The 16-byte layout

The LLVM-level value remains a two-field pair:

%prismio.str = type { ptr, i64 }

; field 1, bits  0..30   byte length (maximum 2 GiB)
; field 1, bit      31   INLINE
; field 1, bits 32..63   INLINE ? data[8..11]
;                               : bit 32 = VIEW, bit 33 = GEOMETRIC,
;                                 bits 34..63 reserved
; field 0                INLINE ? data[0..7]
;                               : data pointer

Bit 32 is text data when INLINE is set and the VIEW flag when it is clear. The tests are unambiguous because every consumer checks INLINE first. Bit 33 is not a storage class: it marks a long owned string whose capacity follows the consuming-append growth policy described in Growing an owned string in place.

Three choices in this layout are load-bearing.

The inline tag is bit 31

Putting the tag in bit 63 would make it share a byte with the twelfth inline character. The inline form would then cover about 80% rather than 81.3% of the measured allocation population. Using bit 31 caps the byte length at just under 2 GiB instead of 4 GiB and adds one mask operation to .length.

The tag is explicit

The compiler cannot use length <= 12 as the discriminant. fatFromPtr wraps a char* returned by C and may produce a short string whose bytes still live on the heap. Reading that value as inline would interpret text bytes as an address.

The long form remains compatible with the previous compiler

An untagged long pair is bit-for-bit identical to the representation emitted before the inline form existed. Producers could be migrated incrementally: unchanged producers kept making valid owned strings, while readers used the new path only when INLINE was set.

The implementation is in runtime/llvm-api-backend.c.

Why Prismio does not store a four-byte prefix

German strings commonly store the first four bytes of a long string beside its length. Equality can reject many mismatches before dereferencing the pointer.

Prismio's long-string construction model does not have a single point at which that prefix can reliably be stamped. str_with_capacity returns an uninitialized buffer, and callers fill it incrementally through operations such as strCopyRangeInto and the builders in std/string.psm. Database engines often materialize a value in one operation and can compute a prefix as the bytes pass through; Prismio's current builders do not provide that hook.

Bits 34–63 remain available for future measurements. They do not contain a prefix today.

Representation invariants

The implementation depends on eight invariants:

The first invariant enables the short-string equality fast path. If lengths and text are equal and every byte beyond the length is zero, the complete 16-byte values are identical. Equality therefore becomes two integer comparisons in registers, without a pointer dereference or function call. Four million short-string comparisons measured at 193 µs, compared with 9.35 ms through strcmp: a 48× improvement on that microbenchmark.

The same invariant lets two short strings order from their pairs. Byte-swapping field 0 and each half of field 1 in place turns the pair into one 128-bit unsigned integer holding the twelve bytes most significant first, with the length below them, so compare is one integer comparison in registers (ir_str_compare). Over the sort_strings keys that measured 1.13 ns per call, against 3.28 ns for the byte loop it replaced and 1.53 ns for libc++'s std::string::compare.

The same zero-tail rule constrains the copy ladder. For lengths from 8 through 12, the intervals [0, 8) and [n-8, n) cover exactly the initialized range; the equivalent four-byte case follows the same rule. Overlapping loads and stores do not disturb the zeroed tail.

The second invariant also lets one mask answer whether the deallocator owns anything. word & (INLINE | VIEW) is nonzero for both unowned forms. When INLINE is set, bit 32 may be text data, but either result still correctly says that there is no external block to release.

Why a view is safe

A view contains a pointer into storage owned by another string. The compiler must keep that base storage alive for every use of the view.

__builtin_string_view(source, start, count) is declared to alias its first argument by aifFfiAliasOf. This is Prismio's existing FFI alias contract: the return value reaches memory through an argument rather than introducing a fresh allocation.

Two properties follow:

• The view has no allocation site of its own, so nothing releases it as an independent heap block.
• The view carries the base string's allocation provenance. A use that outlives the immediate expression extends the required lifetime of that base.

strSubstring returns __builtin_string_view on its long path. The analysis then marks strSubstring as a function that may return a view of its parameter (aif_fn_may_return_view_of_param), and propagates that fact through compiler and standard-library callers. When the view class landed, the self-hosted compiler reached a fixpoint, the full suite passed 285/285 tests, and the verification ledger balanced. These are practical implementation checks; they are not presented as a formal proof of the entire runtime.

For the broader lifetime model, see AIF overview and regions, views, and provenance.

Costs at ownership and ABI boundaries

A view has no terminator of its own. Its logical end can occur in the middle of a buffer that continues, so three boundaries require special handling.

Equality uses the known length

strcmp cannot compare a view safely because it waits for a terminator. The slow equality path calls str_equals_n after the fast path has established that both strings have the same length.

A Vec<String> stores the pair itself

Until 2026-09-11 a container slot was one word. A short string had no stable address to put there, so every push copied it to the heap through str_own, and every read rebuilt the pair by measuring the buffer with strlen. Interposing the C library on the maintained suite showed what that cost:

A Vec whose static type is Vec<String> is now constructed with a 16-byte element, the same %prismio.str pair a local holds, which is what libc++'s vector<string> gets from its small-string buffer. A push stores an inline or owned pair as it is and copies a view out, because the view borrows storage the list does not own. A read is two curated runtime calls that answer the pair's two halves, not a 16-byte struct, because that aggregate is returned in registers on arm64 and SysV x86-64 but through a hidden pointer on Windows x64. Teardown frees an owned long form's block and skips an inline one, under an element mode (AIF_ELEM_STRING) that code generation stamps in place of the analysis's OBJECT answer.

Every entry point still serves a list built with pointer slots. list_new() with no element type is born that way, yet the handle can reach code typed Vec<String>, most often through a struct field initialised with it. That fallback keeps the old str_own and strlen path.

Phase timings from one run of each workload, minimum of nine alternating runs:

The join phase also depended on a library fix: strJoin read its parts with list_get once per byte rather than once per part.

Two related corrections landed with the change. A string literal stored into a container used to be stored as it was, an untagged pair pointing at read-only data, so teardown handed .rodata to the deallocator. It is now copied into an owned or inline value first. And strSplit, strSplitOn, strSplitWhitespace and strLines keep a part of twelve bytes or fewer in the pair rather than allocating it, and so does strClone. That last one matters beyond the allocation: a Map<String, V> stores its keys through it, and a heap copy of a short key never matched an inline lookup key bit for bit, so every successful probe fell through to memcmp -- 47,992 of them in word_frequency, and none now.

Neither a view nor an inline string can be copied with str_clone, which searches for a NUL terminator. Both copies go by length.

C receives a temporary NUL-terminated copy

When a view crosses a C FFI boundary, code generation creates a terminated copy behind a branch and releases it after the call. Inline and owned strings do not pay for the view-specific branch body. Swift takes the same shape for its own small-string form when a String reaches a C parameter. See AIF foreign-function contracts for the source-level contract rules.

The copy is a stack slot wherever it fits. Measured on the compiler compiling itself, 73,735 views cross into C per build and 1.3 MB is copied, averaging 17.6 bytes: 52.7% are 16 bytes or shorter and 99.4% are 32 or shorter. Nearly all are AST names on their way into the symbol table, which are views into the source buffer by construction. A 64-byte entry-block scratch takes all but the tail, leaving 170 heap copies and 13.5 KB. It is not a wall-clock win — the front end measures 0.998× against the heap-only form, because 73.5k allocations is about 0.09% of a four-second compile — but it removes that allocator traffic entirely.

The scratch is sound because no callee may retain the pointer: the heap path freed its copy the moment the call returned, so anything that held one was already broken. alias externs never reach this path.

The bytes contract removes the copy rather than shrinking it. A parameter declared bytes promises the callee was given the count separately and reads no terminator, so the view's own pointer crosses. This is what makes a retry loop over write expressible in Prismio: the loop advances by taking a view of the remainder, and under borrow each pass copied the whole remainder.

One rule that costs a leak if missed: a view bound to a local escapes. Because the view aliases its base's storage — the property the previous section exists to establish — let rest = __builtin_string_view(text, …) raises text's escape to Caller, and every caller's drop of the value it passed in is declined with it. Writing the view directly into the call argument keeps it Local. The symptom is a --verify ledger imbalance rather than a diagnostic; aif --why reports it as an E-BIND at the binding.

Byte access and owned-string release required no further representation change: a view supplies a usable data pointer in field 0, while its tag already tells the release path that the allocation belongs to its base.

Growing and producing strings without extra allocation

Growing an owned string in place

Ordinary concat stays immutable: it builds an independent result and copies its arguments. One assignment shape carries stronger information. s = s + suffix says the old s is dead at the store, and AIF can prove whether that slot owns its value. For that shape, and for a chain s = s + a + b … of up to five suffixes, code generation calls str_append_reuse / str_append_reuse_many; every other spelling keeps the ordinary concat path. A chain grows once for its total, which is a correctness requirement as well as a saving: a later suffix can point into the old buffer, and one call per suffix would read it after the previous call's realloc had freed it.

The 16-byte pair has nowhere to store a capacity word, so bit 33 records a narrower fact: this long string was allocated by the consuming-append growth policy. For such a value the capacity is exactly bit_ceil(length + 1), with a minimum of 16, derived with five shifts and ORs. An inline accumulator promotes directly to that form, and an unmarked long owner is reallocated and marked on its first consuming append. Repeated append is therefore amortized O(1) per byte instead of copying the whole prefix on every iteration, without widening every String, struct field, Vec element, or call boundary to 24 bytes.

The marker replaced an earlier correct but slower implementation that queried malloc_size, malloc_usable_size, or _msize on every append. The macOS query measured about 14 ns, which is visible ten thousand times in csv_parse. The logical-capacity marker is allocator-independent and ABI-neutral.

This combines Prismio's representation with the growth rule that Swift uses for uniquely owned contiguous String storage and Rust uses for String::push_str. The ownership proof is the boundary: capacity is an implementation detail of a value with one owner, never permission to mutate a value another binding can observe.

Short results stay in the pair

Small-string storage only pays when producers use it. Three general producers do:

• mutable string literals of at most twelve bytes are stored inline rather than cloned;
• every 32-bit Int.toString() is formatted directly into the pair with a two-digit lookup table (including Int.min, at eleven bytes); and
• every fixed-arity String.concat of two through six operands first sums the lengths and builds the result inline when the total is at most twelve.

The concat size test stays in std/string.psm; its __builtin_string_concat_inline2 through __builtin_string_concat_inline6 builtins emit only the copies. Longer results keep the ordinary exact-size allocation.

Results

Tokenization breakdown

With input construction outside the timed region, one 54,000-token pass measured:

The “before” column begins after the small-block recycler had already landed; that is why its 450 µs materialization figure differs from the original 777 µs measurement. The final 202 µs and the 218.750 µs median in the summary also come from related but separately recorded breakdown and alternating-suite runs. They should be used for ratios within their own table, not mixed as one sample set.

Token materialization became cheaper than C++'s on this workload. libc++ still copies each token into its small-string buffer, while a Prismio view copies no bytes.

Effect on the maintained suite

Across all 34 implemented workloads, measured against the commit immediately before the final view-class change, every checksum stayed unchanged:

• tokenization became 1.31× faster.
• 31 workloads remained within 3%.
• fft measured at 0.91× and knapsack at 0.90×.

The 1.31× result uses the immediately preceding implementation as its baseline; the 4.86× result in the summary spans the entire sequence from the original heap representation. They answer different questions.

The two apparent numeric regressions did not touch strings, and their generated instruction sequences were byte-identical in the compared builds. Only function addresses moved to a different 64-byte alignment. On this host, code placement moved tight numeric loops by approximately ±10%, while the practical noise floor for a single pass was about ±4%.

Supporting measurements

Repeated append and csv_parse

The scale-4 CSV workload builds 10,000 rows (327,647 final bytes) with csvData = csvData + line, then parses them. Before consuming append, construction copied 1,637,899,970 cumulative bytes, about 4,999 times the final size, and accounted for 99.7% of the row.

Medians on the same host, from a nine-run baseline and 21-run stage comparisons:

The final implementation is 96.7× faster than the starting Prismio row, 19.8% faster than C++, and 44.5% faster than Rust. Every row returned checksum 664934317, and the tracked benchmark sources were unchanged.

Under --verify, the complete workload reports 23,218 allocations and 23,218 releases, with no leaks, no invalid or double releases, and 786 KB of peak live memory. tests/test_100_string_append_reuse.psm keeps the complexity check deterministic: 9,192 logical appends plus 1,000 integer conversions must stay at or below 80 allocations (currently 40), rather than timing a noisy CI host.

Experiments that were rejected

Recording negative results prevents attractive but ineffective changes from being repeated.

Region placement around tokenization

Prismio's existing region syntax placed zero token objects in the arena. The allocation occurred inside str_with_capacity, an external function with 80 call sites in the measured binary, so the relevant call-site bracketing obligations did not hold. AIF reported 100% T2 for the program: ownership was statically known, but allocation was not cheap.

Routing generated allocations through the runtime seam

Emitting rt_base_alloc beside rt_free appeared symmetrical but did not help the string allocations, which were already made inside the runtime. It also hid information from LLVM: TargetLibraryInfo recognizes malloc and supplies attributes such as noalias and allocsize, while an opaque runtime symbol must be treated more conservatively. tree_traversal measured at 0.88× with the swap and 1.00× without it, so the change was reverted.

Curating rt_free into the generated module

Inlining the release gate removed one call per release but did not produce a measurable improvement: tokenization measured at 1.67× versus 1.72× uncurated, and tree_traversal at 0.953× versus 0.960×. Both differences were inside the noise floor, while the change required exporting three runtime-private symbols.

Caching the canonical pointer per SSA value

Each variable use emits a separate load of the pair, so a cache keyed by SSA value missed every later use. Computing the pointer at the pair's definition then produced invalid control flow in an early implementation. The successful design keys the result by source binding: a let or parameter resolves the representation once at its binding, which dominates all of its uses.

Branching around short-string materialization

Unconditional writes into scratch storage prevent loop-invariant code motion because the selected pointer may refer to that same scratch. A branch removed the aliasing concern but measured at 328 µs versus 262 µs; its control-flow cost was greater than the stores it avoided.

Selecting between both byte reads

A single byte does not need materialization at all: it can be read from the pair with a shift, or from the heap pointer. The first store-free form computed both reads and chose one with select, loading the heap arm through the scratch slot when the string was inline. Where LICM lifted the loop-invariant half, this cost nothing. In the tokenizer, where charAt is inlined into a loop too large to unswitch, both arms ran on every character: 209 µs against 150 µs for the materializing form it replaced.

ir_str_byte_at now branches on the inline tag, with !prof weights that make the heap arm the fall-through. That measured 178 µs (medians throughout), and the vectorised byte loops were unchanged. The rest came from charAt. With the branch, the index < 0 half of its two-sided range check stayed in the loop as a sign test per character. One unsigned comparison covers both ends and measured 156 µs. Under the select form the same rewrite changed no instruction, so it only mattered once the read was a branch.

The branch still costs one predicted test per byte when a loop reads a let mut string through byteAt, because nothing resolves that binding's pointer. csv_parse is about 3% slower than it was with scratch stores. Forcing LLVM to unswitch the loop removes the test but does not recover the 3%.

Masking the copy length before llvm.memcpy

Masking count to four bits made the maximum length visible to LLVM, but the generated code still called memcpy. The mask was removed. The explicit overlapping-load copy ladder is what eliminated the call.

Removing charAt bounds checks

C++ indexed without a bounds check, making charAt an obvious suspect for the remaining scan difference. Replacing it with unchecked byteAt produced paired measurements of 229/214, 229/229, and 194/194 µs. LLVM had already proved the index from the loop guard, so removing the source-level check did not help.

Reproducing the maintained measurements

Run the current cross-language workload with:

prismio bench --only tokenization --runs 9

The historical A/B figures on this page did not come from one invocation of that command. Two compiler revisions were built and their outputs run in alternating sample order. Running one complete binary and then the other allowed machine drift to exceed the differences being measured.

Count Prismio-managed allocations for the string test with:

prismio build tests/test_09_strings.psm -o /tmp/prismio-string-probe --verify
/tmp/prismio-string-probe

The tokenization history on this page is tied to commit 43107cff86c1. The maintained runner, language build flags, workload catalog, checksum policy, and output files are documented in benchmarks/README.md.

The allocation-length histogram was produced by temporary instrumentation in str_with_capacity and is not part of the maintained harness. It cannot be reproduced from the two commands above without restoring that instrumentation.

After editing runtime/*.c, rebuild the toolchain before measuring generated programs. A program links the runtime as installed bitcode, so an edit to the C does not reach it until that bitcode is rebuilt — prismio build refreshes a project-local toolchain, and tools/package.py a packaged one.

Open work

The scan remains slower than C++

The measured scan is 150 µs versus C++'s 123 µs. Bounds checks and conditional short-string materialization have both been eliminated as explanations. Three materialization stores remain visible in benchTokenization's inner digit loop, but their cost has not been isolated.

Views begin above twelve bytes

Results of twelve bytes or less stay inline. They already copy into registers and do not create a lifetime dependency, so preferring a view below the inline threshold is not clearly beneficial and has not been measured.

LLVM captures(none) is not emitted

LLVM 23 spells the former nocapture concept as captures(none). The old name does not map through LLVMGetEnumAttributeKindForName, so Prismio skips that attribute. readonly, the property required for the measured loop hoisting, does map correctly.

Most reserved bits remain unused

Bit 33 records the consuming-append growth policy; bits 34–63 of a long string's length word are available. The incremental construction path prevents a reliable prefix, but a cached hash is a possible future experiment rather than a committed design.

References

• Thomas Neumann and Michael Freitag, Umbra: A Disk-Based System with In-Memory Performance, CIDR 2020—the original layout.
• CedarDB, Why German Strings are Everywhere and A Deep Dive into German Strings—storage classes and prefix comparisons.
• Apache DataFusion, Using StringView to Make Queries Faster—benefits and construction-path pitfalls.
• Polar Signals, Das Problem mit German Strings—the memory-overhead counterargument.
• string-rosetta-rs—sizes and inline capacities across Rust string implementations.
• musl's AArch64 memcpy and Folly's memcpy—examples of overlapping-load small-copy strategies.
• Raymond Chen, An informal comparison of the three major implementations of std::string—the measured platform's libc++ small-string capacity.
• LLVM libc++, basic_string—the inline/long union representation and growth machinery behind the C++ comparison.
• David Tolnay, itoa—allocation-free integer formatting into caller-owned storage.
• Swift, String.swift and StringDesign.rst—value semantics, unique-buffer mutation, small strings, and exponential growth.
• Rust, String and RawVec—push_str, reserve checks, and amortized growth.