SoCal: A Language for Memory-Layout Factorization of Recursive Datatypes

arXiv:2605.01140 · cs.PL, cs.PF · Submitted 2026-05-01 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "SoCal: A Language for Memory-Layout Factorization of Recursive Datatypes".

Jane: Here's the gist of the paper. SoCal introduces a formal language designed for generating factored Abstract Data Type (ADT) representations, alongside Colobus, a compiler that implements SoCal semantics by extending the Gibbon compiler.

Tom: The central innovation is SoCal's ability to generalize LoCal’s single-buffer representation into multiple coordinated buffers for algebraic datatypes, enabling Structure-of-Arrays (SoA)-like layouts for serialized recursive data structures.

Jane: This factorization is achieved through location expressions like projTagLoc and projFieldLoc, which define a factored location structure, ldr 1 (DataCon, Idx, loc i), tracking one buffer for data-constructor tags and another for the integers in the leaf nodes.

Tom: The language allows developers to explicitly choose between a factored (multiple buffer) layout or a flattened (single buffer) layout for each datatype.

Paper summary: Tom: So we’re talking about this paper called SoCal: A Language for Memory-Layout Factorization of Recursive Datatypes. Basically, it introduces a new language and a compiler called Colobus to create factored representations for abstract data types.

Jane: It sounds super technical, Tom. What is the main idea here? What problem are they trying to solve by factoring these data types?

Tom: They’re taking what was once just a single buffer for an abstract data type and turning it into multiple coordinated buffers. This lets them create something more like a structure-of-arrays layout for recursive data structures.

Lu: So, instead of everything being packed tightly in one block, they separate the different parts of the data—like the tags versus the actual fields—into different locations. They use special location expressions to define this factored structure, tracking one buffer for things like constructor tags and another for the integers in leaf nodes.

Meng: That sounds like it would be a huge win for performance if those traversals are heavy on accessing just one part of the data. But how does this factorization actually change how you think about memory?

Jane: It changes it by giving developers an explicit choice between two ways to represent each datatype: a factored layout with multiple buffers, or a flattened layout using just one buffer. It lets you tailor the structure to the specific access patterns you have.

Tom: The static semantics of SoCal guarantee that every well-typed value gets this unique serialized layout, and they prove traversal safety using store well-formedness judgements. That sounds like they’re making sure the memory layout is correct before anything runs.

Lalam: And the dynamic semantics add recursive witness relations to track where components end within those different memory regions, ensuring that every component location reachable from a well-typed root is itself well-typed in the store. It keeps everything consistent across the entire structure.

Lu: The compiler, Colobus, handles this automatically by lowering SoCal down to NoCal. Single locations map to single cursors, but factored locations map to a set of parallel cursors, which they call a cursor array N. This effectively preserves that static layout structure in the runtime representation.

Meng: I’m thinking about deployment here. If we have these parallel cursors, does it mean this is going to be faster on real hardware than just using a flattened representation? What’s the practical impact on running models at scale?

Paper summary: Tom: The paper shows that loop-based traversals over these arrays incur low memory overhead when loading elements into vector registers, which enables straightforward SIMD operations and mapping to GPU kernels for SIMT style execution. They show this is good for things like fold heavy traversals where you only access a subset of the fields.

Jane: So, the core argument seems to be that while factored layouts might increase bookkeeping costs—like managing those extra buffers—they give you substantial performance gains when you skip over dead fields during traversal.

Lu: Exactly. They show that this can lead to better spatial locality and reduced computation because you’re not reading irrelevant data, which can result in up to a five point nine times speedup over flattened layouts in some specific examples where the dead percentage is high, around eighty two percent.

Meng: Eighty two percent dead percentage? That’s interesting. But what about the setup cost? If you have to manage multiple buffers and complex location expressions, isn't that just adding complexity for developers to deal with?

Tom: Well, they are formalizing this so developers can explicitly choose the layout. The language allows you to decide between factored or flattened for each datatype. That explicit control is what makes it powerful.

Jane: So, when we think about the world of AI and large models, this paper suggests that manipulating data structures in a way that aligns with how hardware fetches memory could be really beneficial for things like processing massive tree-shaped data used in neural networks.

Lalam: I'm confident in this direction. The paper shows that exploiting the inherent parallelism generated by these factored buffers can actually lead to CPU vectorization and map traversals on heterogeneous architectures like GPUs. It’s about matching the data layout to the hardware's capabilities better than a single contiguous block ever could.

Tom: So, we’ve seen how they design this language and compiler, Colobus, to generate these optimized layouts for recursive structures. It really moves beyond just serializing things into one big chunk of memory.

Jane: And the paper title itself is very descriptive: "SoCal: A Language for Memory-Layout Factorization of Recursive Datatypes." It clearly signals that this is about finding a better way to organize memory when dealing with complex, nested data types.

Lu: The implication is that we can design systems where the memory layout is dictated by the data structure's needs rather than just how it was initially defined in a functional language like Haskell.

Paper summary: Meng: From an engineering standpoint, if we can achieve those speedups without needing massive amounts of extra memory to store everything everywhere, that’s what makes it deployable. We need to know if this overhead is manageable for real-world traffic.

Tom: The authors focus on the mechanism of how they achieve this factorization—using location expressions like projTagLoc and projFieldLoc—which defines that specific factored location structure. It’s about making sure the data-constructor tags get their own buffer, separate from the fields.

Jane: So, to sum up this segment, SoCal introduces a way to factor recursive data types into multiple buffers for better memory layout, claiming significant speedups in traversal performance through SIMD operations and better cache usage.

Lu: It’s about making sure that when you traverse a structure—say, a nested list—you aren't wasting time jumping over irrelevant memory because the data you need is sitting in its own dedicated buffer.

Meng: The paper points out that they can skip over large regions of memory, which helps prefetching and prevents cache pollution. That’s a concrete mechanism for getting better performance on systems that rely heavily on sequential access patterns.

Lalam: I'm sure the claim about speedup is backed by the analysis in the paper, and my internal models confirm that this kind of structured access optimization is where we see real gains at scale when dealing with complex graph or tree-like data representations.

Tom: So, to wrap up on what we’ve heard about SoCal: it’s a formal language and compiler designed to generate specialized memory layouts that let you choose between packed single buffers or factored multi-buffer layouts for recursive data types.

Jane: And the real change for someone listening is understanding that memory layout isn't just something the machine decides; it can be explicitly factored by the programmer using this new language.

Lu: The future work they hint at involves extending these well-formedness guarantees to ensure that every projected field and every recursively nested component location reachable from a root is itself well-typed with respect to the store.

Meng: That sounds like a lot of rigorous checking, which I appreciate, but if it keeps the runtime configuration sound under heavy load, then it’s worth looking into for our production systems.

Tom: So that's the gist of what they’re proposing: a formal system to ensure your data structure's memory layout is optimized for high-performance traversal. That's where we are on this discussion about SoCal.

Conclusion: Tom: So we’ve seen how this new language, SoCal, lets you decide how to physically arrange your data in memory for these complex, nested structures.

Jane: Right, so it’s not just about writing the code; it’s about telling the computer exactly how to lay out those data types so they can run faster.

Lu: The authors are introducing a formal language and a compiler called Colobus that creates this factored layout for abstract data types.

Meng: I mean, the authors are giving developers a direct way to choose between having everything packed into one single block, or splitting it up into multiple separate blocks.

Lalam: They’re using location expressions like projTagLoc and projFieldLoc to define this structure, which tracks one buffer for the data tags and another for the actual field values in leaf nodes.

Tom: So they’re essentially creating a way to use a structure-of-arrays layout for recursive data structures instead of just the usual single buffer approach.

Jane: It sounds like it gives you explicit control over memory layout, which is usually something you have to guess or let the compiler handle automatically.

Lu: The static rules they set up guarantee that every value gets this unique serialized layout, and they use store well-formedness judgements to prove everything stays correct during execution.

Meng: That sounds like a lot of upfront work for the developer, but if it works right, it should keep things stable at scale.

Lalam: Dynamically, they add recursive witness relations to track how components end within those different memory regions so every part of the structure is verified.

Tom: And in terms of performance, they show that this factoring actually helps when you only access a small part of the data during a long traversal.

Jane: So even if you have to manage those extra buffers, you can skip over a lot of irrelevant memory and get faster results for certain tasks.

Lu: The experiments show that this can lead to speedups up to five point nine times over flattened layouts in cases where a huge percentage of the data is not being read.

Meng: That kind of performance gain sounds useful if we're dealing with massive datasets that we only query partially. What about the authors themselves?

Tom: They’re focusing on making sure this structured access is actually safe and verifiable, which is a big step for formal methods in programming.

Jane: It feels like they’re trying to bridge the gap between high-level functional programming ideas and how hardware actually likes to store things.

Lalam: They are proving that this explicit layout choice can translate into concrete performance gains when you move toward vectorization and parallel processing on things like GPUs.

Tom: So, in a nutshell, SoCal is about giving programmers a formal tool to factor recursive data types into multiple buffers for better memory organization.

Jane: It seems they are aiming to make the memory layout itself something that can be optimized by the programmer based on how the data is used.

Lu: The idea is that this structured layout can exploit parallelism, which is what makes it potentially good for massive AI model processing.

Meng: So, if this works as well as their numbers suggest, it could mean a big difference in how efficient we can run large models on production hardware.

Tom: We’ll see how much these formal guarantees hold up when we actually put them under heavy load and real-world traffic conditions.

VIDUSH SINGHAL, MIKAH KAINEN, ARTEM PELENITSYN, MICHAEL H. BORKOWSKI, MIKE VOLLMER, MILIND KULKARNI

Purdue University · University of Kent

cs.PL, cs.PF

Submitted: 2026-05-01

Updated: 2026-11-13

Code: https://github.com/m-a-d-n-e-s-s/madness

Project page: https://icl.utk.edu/papi

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 91/100

The gist: SoCal introduces a formal language designed for generating factored Abstract Data Type (ADT) representations, alongside Colobus…

Key concepts

Factored Layout
This layout uses multiple buffers instead of one for a data structure. It separates different parts of the data, such as tags and integer fields, into distinct memory locations. This organization is designed to improve performance when only certain parts of the data are needed during processing.
Colobus Compiler
Colobus is a compiler that implements SoCal's rules by extending an existing compiler called Gibbon. It automatically converts high-level functional programs written in SoCal into the specific, optimized serialized memory layout required by the language, using mutable cursors for efficiency.
Store Well-formedness Judgement
This is a runtime check that ensures every part of the program's memory state is correct. It verifies four main things: that all typed roots exist in memory, that symbolic constraints are met, that allocations don't overlap, and that locations are properly managed.
Recursive Witness Relation
This tracks the end of components within complex data structures. For factored roots, it ensures that every piece of data reachable through the structure—including nested recursive parts—is correctly typed and present in its allocated memory region.

Terminology

Summary

SoCal introduces a formal language designed for generating factored Abstract Data Type (ADT) representations, alongside Colobus, a compiler that implements SoCal semantics by extending the Gibbon compiler. p. 0

Where the paper says it

We introduce factored, multi-buffer layouts that store different ADT fields in separate buffers, enabling SoA-like layouts for serialized recursive data structures. We formalize this approach in SoCal, a language for generating factored ADT representations, and implement it in a compiler called Colobus.

The central innovation is SoCal's ability to generalize LoCal’s single-buffer representation into multiple coordinated buffers for algebraic datatypes, enabling Structure-of-Arrays (SoA)-like layouts for serialized recursive data structures. This factorization is achieved through location expressions like projTagLoc and projFieldLoc, which define a factored location structure, ldr 1 (DataCon, Idx, loc i), tracking one buffer for data-constructor tags and another for the integers in the leaf nodes. The language allows developers to explicitly choose between a factored (multiple buffer) layout or a flattened (single buffer) layout for each datatype. p. 7
Where the paper says it

8 Singhal et al. At present, Colobus lets programmers choose, for each datatype, either a factored (multiple buffer) layout or a flattened (single buffer) layout.

The static semantics of SoCal prescribe a unique serialized layout for every well-typed value, with proofs of traversal safety guaranteed through store well-formedness judgements. p. 9

Where the paper says it

C(𝑙𝑜𝑐′ 𝑖+1 ) = (after (𝜏@𝑙𝑜𝑐′ 𝑖 )). Collectively, these premises ensure that writes of factored constructors are well typed, correctly ordered, and write-safe.

The dynamic semantics introduce recursive witness relations to track the end of components within disjoint memory regions, ensuring that every component location reachable from a well-typed factored root is itself well-typed in the store. p. 9
Where the paper says it

Collectively, these premises ensure that writes of factored constructors are well typed, correctly ordered, and write-safe. Written locations are removed from N—including the destination factored location, its data-constructor location, and the relevant field locations—and the allocation-pointer mapping in A is updated to the corresponding post-write locations.

The compiler, Colobus, automatically transforms functional programs into this serialized layout. p. 0

Where the paper says it

We formalize this approach in SoCal, a language for generating factored ADT representations, and implement it in a compiler called Colobus. Colobus automatically transforms functional programs to operate over a serialized, factored layout of recursive ADTs.

It lowers SoCal to NoCal, where single locations map to single cursors and factored locations map to a set of parallel cursors (CursorArray N), effectively preserving the static layout structure. p. 2
Where the paper says it

Contributions • SoCal, a formal language that generalizes LoCal’s single-buffer representation by introducing a factored representation. In SoCal, algebraic data types can be serialized across coordinated buffers in a type-safe manner while preserving deterministic traversal order (Section 3).

A key implementation strategy involves using mutable cursors instead of Gibbon’s functional-style cursor passing; this optimization eliminates cursor-copying overhead and enables tail call optimization. p. 2
Where the paper says it

• An implementation strategy for serialized representations based on mutable cursors as opposed to Gibbon’s functional-style cursor passing. This allows Colobus to realize the theoretical benefits of factored representations by eliminating cursor-copying overhead and enabling tail call optimization (Section 4.

The type-safety sketch relies on a runtime store well-formedness judgement that packages four classes of invariants: (1) every typed root in sigma must have a corresponding runtime realization in M and S; (2) every symbolic location constraint in C must be realized by the runtime configuration; (3) the allocation state tracked by A and N must prevent overwriting and ensure allocations point to buffer ends; and (4) locations already typed in sigma must be disjoint from the nursery. p. 9

Where the paper says it

Collectively, these premises ensure that writes of factored constructors are well typed, correctly ordered, and write-safe. Written locations are removed from N—including the destination factored location, its data-constructor location, and the relevant field locations—and the allocation-pointer mapping in A is updated to the corresponding post-write locations.

Extensions for SoCal mandate that for a factored root, store well-formedness must guarantee not only the presence of the tag component but also that every projected field component and recursively nested component location reachable from the root is itself well-typed with respect to the store. p. 5
Where the paper says it

Finally, the program writes the Node tag at the current root location 𝑙𝑑 𝑟1 (Leaf, 0,𝑙𝑟2 𝑖 ). 3 SoCal: A Language for Formalizing the Factored Representation Moving beyond the contiguous-memory assumption of foundational typed assembly languages (Morrisett et al.

The contiguous witness relation follows LoCal's structure for primitive fields (advancing by one cell) and extends this for constructor-rooted values in factored roots, ensuring that the data-constructor component is present at its tag buffer location and that every non-self-recursive field entry is well typed for its corresponding field type. The recursive end witness relation specifically ensures that a factored concrete root has enough well-typed component locations to traverse the entire materialized value, including recursive descendants recovered through its component structure.

Evaluation across 15 workloads demonstrates that while factored layouts increase bookkeeping costs, they yield substantial performance gains for fold-heavy traversals where only a subset of fields is accessed. p. 2

Where the paper says it

We find that with the optimized cursor implementation, Colobus’s factored layouts outperform Gibbon’s flat layouts by 1. 46×(geomean), with larger gains in traversals that benefit from efficient field skipping enabled by factored layouts.

This speedup arises because factored layouts allow traversals to skip dead fields, leading to better spatial locality and reduced computation—for instance, achieving up to a 5.9x speedup over flattened layouts in specific examples where the dead-percentage is high (around 82%). The paper concludes by suggesting that exploiting the inherent parallelism generated by these factored buffers can lead to CPU vectorization and map traversals on heterogeneous architectures like GPUs. p. 2
Where the paper says it

This paper tackles this problem by extending Gibbon and its compiler to introduce a new layout option for packed ADTs, called factored ADTs. While Gibbon’s packed ADTs are flat, placing all fields and nested structures into a single, contiguous buffer, factored ADTs place different fields in different buffers, creating a SoA-like representation.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Generalizing memory layout for recursive data structures allows AI systems to utilize structure of arrays (SoA) layouts for serialized algebraic datatypes instead of single contiguous buffers, which enables better prefetching and selective field traversal.

  2. The factored representation introduces a system of related locations across disjoint buffers, allowing the AI system to perform operations like selective traversal by only accessing relevant memory regions without needing to skip irrelevant data, as seen in the finding that a traversal does not need to access the memory region associated with that field.

  3. The compiler Colobus can automatically transform functional programs into operate over a serialized, factored layout of recursive ADTs, resulting in a 1.46x geometric mean speedup on a suite of tree-processing benchmarks, significantly improving the performance of tree traversals in applications like compilers and document layout engines.

  4. The SoCal language formalizes the serialization of algebraic datatypes using locations and constraints, providing a mechanism to verify that a unique serialized layout for each well-typed value is realized at runtime, ensuring safety during complex data manipulations.

  5. For workloads with fold-like traversals that read only a subset of fields, the factored layout can achieve significant performance gains by reducing instruction count ratio compared to flattened layouts, as seen in the LinearListReduction benchmark where the dead percentage is around 82% (9 out of 11 fields are not used in the traversal).

  6. The integration of mutable cursors into a factored layout allows for in-place updates and avoids copying overhead, which is beneficial for functional programming paradigms, leading to performance improvements over immutable cursor implementations.

  7. The system can be extended to support hybrid factored layouts where programmers choose between flattened or factored representations for subfields within a datatype, offering fine-grained control over memory layout optimization for specific data structures.

Abstract

Array-of-structures (AoS) to structure-of-arrays (SoA) is a classic compiler transformation that improves memory locality and enables data-parallel execution. Existing AoS-to-SoA transformations target regular, array-based programs in imperative languages, such as C. However, many applications traverse tree-shaped data such as ASTs in compilers, DOM trees in browsers, and k-d trees in scientific workloads. Prior work speeds up functional programs over trees by serializing algebraic datatypes (ADTs) into one contiguous buffer. Such a representation interleaves the fields of every node, similar to an AoS layout. We introduce a factored layout of ADTs, which stores its fields in separate buffers, producing a layout that resembles SoA. In a factored layout, a traversal can focus on relevant fields and ignore the rest, similar to extracting a column from a SoA representation; in this setting, traversals over scalar fields can be vectorized. Working with raw byte arrays is error-prone, though: wrong indexing can silently read bytes from a wrong field or write past the end of a value. We therefore introduce SoCal, a type-safe language for expressing traversals over factored ADTs. Our compiler, Colobus, transforms a simple functional language with ADTs reminiscent of Haskell to C, using SoCal as the intermediate representation. Colobus generates traversals over byte arrays in the factored representation and performs optimizations such as field skipping and vectorization. Across a suite of benchmarks, Colobus shows the average speedups of 3.8x and 5.2x over fold and map passes, respectively.

Sources

Related papers