SoCal: A Language for Memory-Layout Factorization of Recursive Datatypes
summary
The gist
SoCal introduces a formal language designed for generating factored Abstract Data Type (ADT) representations, alongside Colobus…
In short
SoCal introduces a formal language to create factored representations of Abstract Data Types, moving beyond single-buffer layouts. It enables multiple coordinated buffers for algebraic datatypes, creating Structure-of-Arrays (SoA)-like layouts. This allows developers to choose between factored or flattened memory arrangements, which significantly speeds up fold operations by skipping unused data.
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 used across episodes
This episode discusses
- SoCal: A Language for Memory-Layout Factorization of Recursive Datatypes · Paper Radio
- Annotation-guided AoS-to-SoA conversions and GPU offloading with data views in C++
The paper
SoCal: A Language for Memory-Layout Factorization of Recursive Datatypes · Read on arXiv
VIDUSH SINGHAL, MIKAH KAINEN, ARTEM PELENITSYN, MICHAEL H. BORKOWSKI, MIKE VOLLMER, MILIND KULKARNI
Purdue University · University of Kent
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.
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.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game