Andrew Reece on Architecting High-Performance Systems with Minimal Assumptions and the Xar Data Structure

Better Software Conference

Summary:

This talk by Andrew Reece, lead developer of WhiteBox, delves into practical software architecture patterns that optimize for both human readability and machine efficiency. Key takeaways include:

• Prioritizing Simplicity and Efficiency: Focus on straightforward, concrete solutions that are easy for both developers and CPUs to understand, avoiding unnecessary abstraction.
• Leveraging Stable Pointers and Arenas: Utilize memory allocation strategies like arenas to ensure stable pointers and manage memory lifetimes effectively, enabling cleaner code and preventing dangling pointers.
• Optimizing Type Systems with Bitwise Operations: Represent type information using bit flags and combine them into single values to enable fast, compile-time lookups and efficient handling of type hierarchies.
• Introducing the Xar (Exponential Array) Data Structure: A novel dynamic array design that uses exponentially sized chunks, allowing for stable pointers, random access, and efficient memory management with minimal overhead.
• Pipelining Dependencies for Clarity and Performance: Structure code to process dependencies in a linear, pipeline-like fashion, reducing nesting and improving readability and execution efficiency.
• Embracing "Byte-First Thinking": Understanding data at the byte level enables more direct and optimized code, bridging the gap between high-level logic and low-level machine execution.

Introduction to WhiteBox and Core Philosophy [0:01:27]

Andrew Reece, the creator and lead developer of WhiteBox, introduces his work on a debugger with a timeline for tracking data changes. The core premise of his talk is finding coding patterns that are friendly to both developers and machines. This involves identifying the intersection of capabilities between humans and CPUs to write code that is both understandable and performant.

Generalization vs. Abstraction [0:04:36]

• Generalization: Describing a problem space with an expanded vocabulary to cover more things, without losing detail for existing concepts. For example, a min function for two numbers generalized to finding the minimum in an array. Generalization usually avoids the indirection costs of abstraction.
• Abstraction: Creating a layer on top of an implementation, exposing only certain variables or features. It acts as a semi-permeable membrane, introducing indirection. The talk emphasizes favoring generalization over abstraction where possible for better performance and clarity.

Architectural Tool 1: Lifetimes & Stable Pointers [0:05:56]

Understanding Arenas [0:06:17]

• Arenas provide a block of bytes that can be allocated sequentially.
• Memory is allocated by "bumping" a pointer. (Image 41, 42, 43)
• Deallocation can involve popping back to a previous point or wiping the entire arena.
• Multiple arenas can be used simultaneously, creating conceptual hierarchies. (Image 44, 49)

The Advantage of Stable Pointers [0:08:31]

• If an inner arena holds a pointer to data in an outer arena, that pointer remains valid because the outer arena's lifetime is longer.
• This stability is crucial for long-lived references, such as those from an "event cache" into a "run" or "app" context. (Image 55, 58, 59)
• Stable pointers reduce the need for complex memory management and pointer validation.

Architectural Tool 2: Type Mappings with Bitwise Operations [0:09:58]

The Challenge of Type Representation [0:10:05]

• Early versions of WhiteBox used DWARF debug information, which is fully dynamic and determined at runtime. (Image 61, 65)
• Clang's internal type representation is a vast hierarchy of subclasses and multiple inheritance, making it complex. (Image 69, 70)
• To handle both DWARF and PDB formats for full executable debugging, a custom, intermediate representation was needed. (Image 72, 73)

Custom Type System Design [0:12:19]

• A simplified type system was developed with a limited number of main types (e.g., EnumVal, DbgFn, Member, Type, Var). (Image 71, 74)
• Each "Type" struct contains a TypeKind tag, name, size, and an inner_type pointer. (Image 85, 86)
• The inner_type recursively points to the underlying type (e.g., a pointer to an int points to the int). (Image 78, 79, 87)

The "Nil Type" and Safe Access [0:15:08]

• A special "nil type" entry in the type array points to itself. (Image 91, 92)
• This allows for safe dereferencing of inner_type even if there isn't one, avoiding null checks and simplifying code. (Image 93, 94)
• This is an example of a deliberate non-zero initialization for a specific, beneficial pattern. (Image 96)

Bitwise TypeKind Flags [0:17:46]

• Instead of simple enum values, TypeKind uses bit flags. (Image 119, 120, 121, 122)
• Each distinct type property (pointer, qualifier, struct, enum) is assigned a unique bit.
• These flags can be grouped for common checks (e.g., TYPE_GROUP_POINTER for pointers and arrays). (Image 123, 124, 125)
• This allows for efficient, single-operation lookups using bitwise AND and OR. (Image 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138)
• Compiler optimizes these bitwise operations at compile time.

Encoding Platform-Specific Information in Pointers [0:28:47]

• On x86-64, pointers are typically 48-bit, leaving 8 unused bits at the top. (Image 175, 176, 177, 178)
• These unused bits can be "stolen" to store additional information, like the TypeKind (which only needs 5 bits for 26 types). (Image 190, 191)
• This allows combining a pointer and its type kind into a single 64-bit value, reducing memory footprint and improving cache locality. (Image 192, 193)
• The Most Significant Bit (MSB) function (or BSR instruction) is used for efficient conversion. (Image 181, 182, 183, 184, 185, 186, 187)
• This technique is an example of making platform-specific assumptions to achieve performance benefits. (Image 194, 195, 196, 197, 198, 199, 200, 201, 202, 203)

Bits are High-Level: Dimensional Thinking for Base Types [0:34:10]

• A number can be interpreted as multiple fields or "dimensions". (Image 207, 208, 209)
• For base types, this means splitting a value into kind (e.g., signed, unsigned, float) and size (e.g., 1-byte, 2-byte, 4-byte). (Image 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228)
• This allows for rectangular mappings and product types, simplifying type logic. (Image 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250)
• Instead of N * M switch cases for N kinds and M sizes, one can process N cases for kind and M cases for size separately, resulting in N + M cases. (Image 251, 252, 253, 254, 255, 256)
• This "byte-first thinking" allows for creating composed types and performing operations like integer promotion efficiently without multiple lookups. (Image 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280)

The Xar (Exponential Array) Data Structure [0:46:51]

The Need for a New Dynamic Array [0:47:04]

• WhiteBox deals with large, dynamic data like profiler traces, with deep call stacks across multiple threads. (Image 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293)
• Traditional dynamic arrays (reallocating and copying) invalidate pointers, breaking the stable pointer guarantee. (Image 299, 300)
• Simple linked lists of chunks are slow for random access. (Image 309, 310, 311, 312, 313, 314, 315, 316)
• Trees of chunks introduce too much indirection. (Image 317, 318, 319)

Xar Design and Advantages [0:53:11]

• The Xar (Exponential Array) combines elements of reallocating arrays and chunked lists. (Image 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347)
• It uses a small, fixed-size metadata header and dynamically allocated chunks.
• Chunks grow exponentially (e.g., 2, 4, 8 elements), making it efficient for large data.
• All chunk sizes are powers of two, simplifying calculations with bitwise operations (log base 2 using MSB). (Image 363, 364, 365, 366, 367, 368)
• It provides stable pointers to elements within chunks and allows random access with logarithmic time complexity.
• A small, 8-byte metadata struct (shift, chunks_n, el_size) can be passed by register for performance. (Image 348, 349, 350, 351, 352, 353, 354, 355, 356)
• Xar elements are retrieved using bit shifts and additions, avoiding complex branches or lookups. (Image 358, 359, 360, 361, 362)

Application: Binary Search and Inverted Access [1:06:03]

• Data collected over time is naturally sorted, enabling efficient binary search. (Image 399, 400)
• Byte-first thinking allows a single generic binary search function to work across different data types by specifying the offset and size of the comparison key. (Image 406, 407, 408, 409, 410, 411, 412, 413, 414, 415)
• It supports "inverse parallel mappings," like accessing a call stack from either the root (level) or the leaf (depth). (Image 434, 435, 436, 437, 438, 439, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455, 456, 457)
• On two's complement machines, -(x+1) is equivalent to ~x (bitwise NOT), simplifying conversion between level and depth. (Image 459, 460, 461, 462, 463, 464, 465, 466, 467, 468, 469, 470)

Pipelining Dependencies [1:20:50]

Structuring Event Handling [1:21:03]

• Instead of branching logic for overlapping conditions, events can be processed in a pipeline. (Image 486, 487, 488, 489, 490, 491, 492, 493, 494, 495)
• Break down the problem into individual "jobs" to be done, represented by bit flags.
• Process event-specific logic to determine which jobs need to be done. (Image 500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512, 513, 514, 515, 516, 517, 518, 519, 520, 521, 522, 523, 524, 525, 526, 527, 528, 529, 530, 531, 532, 533, 534, 535, 536, 537, 538, 539, 540, 541, 542, 543, 544, 545, 546)
• Execute jobs in a defined order. This creates a Directed Acyclic Graph (DAG) of dependencies. (Image 496, 497)
• This approach makes code easier to read and maintain by localizing context and avoiding deep nesting. (Image 547, 548, 549, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565, 566, 567, 568)
• It allows separating platform-dependent input framing from platform-independent job execution.

General Principles for Robust and Performant Code [1:38:08]

• Make Assumptions Explicit: Clearly document and assert assumptions using static_assert, custom macros, and runtime assert statements. (Image 599, 600, 601, 602, 603, 604, 605, 606, 607, 608, 609, 610, 611, 612, 613)
• Prioritize Stable Pointers: They simplify memory management and reduce indirection. (Image 630, 631)
• Use Rectangular Dimensions for Data: Organize data into separable dimensions to reduce code complexity. (Image 633, 634, 635, 636, 637, 638, 639)
• Treat Bits as High-Level Concepts: Understand bitwise operations as mathematically precise tools for compact and efficient data manipulation. (Image 614, 615, 616, 617, 618, 619, 620, 621, 622, 623, 624, 625, 626, 627, 628, 629, 640, 641)
• Embrace Pipelining: Structure code for linear execution of interdependent tasks. (Image 642, 643, 644, 645)
• Minimize Indirection: Reduce unnecessary function calls and memory accesses. (Image 646, 647)
• Generalization over Abstraction: Opt for solutions that expand the problem-solving domain without hiding underlying details. (Image 648, 649, 650, 651, 652, 653, 654, 655, 656, 657, 658, 659)

Q&A Session [1:50:16]

• WhiteBox Future: Andrew mentions WhiteBox stopped using version numbers and now releases by date. Version 1.0 release is still pending. [1:50:47]
• Benefits of Bare Bitwise Operators: Keeping bitwise operators visible (e.g., ~x instead of a named function) helps developers compare and contrast different operations, leading to better understanding and fewer bugs, especially in performance-critical code. [1:55:01]
• Xar Data Structure Applicability: Xar is broadly applicable for dynamic arrays where stable pointers and random access are needed. Its main advantage comes from the constant-size header and chunks being pushed onto an arena, allowing interleaving operations and efficient cleanup. Pitfalls include handling partially valid states after popping and the overhead of pointers for very small, numerous data structures. [2:06:22]
• Holes in Parameter Space: It's acceptable to have "holes" (undefined combinations) in your parameter space if the overall model remains simple and consistent. The value comes from the consistent mapping and identity, even if it's slightly unbalanced. [2:12:17]
• Power of Two Sizes for Xar: It's important for chunk sizes to be powers of two to allow efficient bitwise operations for index calculations (e.g., log base 2 using MSB). Non-power-of-two sizes would require more complex arithmetic operations. [2:14:11]
• Byte-First vs. Type-First Thinking: Byte-first thinking acknowledges the fundamental reality of bytes and their bit patterns, allowing for flexible interpretation and direct manipulation. Types are useful abstractions but can introduce overhead and hide details. Thinking at the byte level empowers developers to find creative, efficient solutions. [2:18:10]
• Relevance to Other Languages: While many examples are C/C++ specific due to direct memory access, the underlying principles (stable pointers, rectangular dimensions, bitwise thinking, pipelines, minimizing indirection, generalization) are applicable to all languages. Scripting languages might abstract away direct bit manipulation, but understanding these concepts can still inform data structure design and optimization, even if JIT compilers handle the low-level details. [2:41:24]