Applying Data-Oriented Design in Practice

Introduction

• Speaker: Andrew Kelly, President and Lead Software Developer, Zig Software Foundation
• Objective: Discuss data-oriented design strategies to improve software performance by leveraging efficient memory utilization.

Personal Backstory

• Developed an interest in games early, favorite games involved creation (e.g., Tony Hawk Pro Skater 2)
• Began programming with Visual Basic 6, learned multiple languages (Python, Perl, C++, etc.)
• Experienced a plateau after 10 years, broke through by learning data-oriented programming

Data-Oriented Programming (DOP)

Resource & Learning Path

• Recommended resources: Talks on YouTube, Handmade Seattle conference, "Data-Oriented Design" book by Richard Fabian

Computer Memory Hierarchy

• Memory Structure: L1, L2, L3 caches, main memory
• Speed Trade-Offs: L1 (fastest, smallest), L2 (slower, larger), L3 (even slower, larger), Main Memory (slowest, largest)
• Cache Line: Typically 64 bytes, crucial to avoid cache misses
• Optimization Concept: Perform more operations on the CPU, minimize memory access

Practical Strategies for DOP

1. Struct Layout

   • Align data to minimize padding, keeping related data within the same cache line
   • Example: Reordering fields in structs to reduce size and improve alignment

2. Use Integers Instead of Pointers

   • Convert pointers to indexes, especially in arrays, to reduce size
   • Caution: Ensure type safety is maintained

3. Store Booleans Out-of-Band

   • Use separate structures to store Boolean values, reducing struct size
   • Only iterate over relevant parts (e.g., alive monsters only)

4. Eliminate Padding with Struct of Arrays

   • Separate arrays for each field instead of a single array of structs
   • Reduces memory overhead due to padding

5. Use Encodings Instead of Polymorphism

   • Encoding approach to represent data more compactly
   • Example: Represent state through tags and auxiliary structures

Case Studies: Zig Compiler

Token Struct Optimization

• Original: 64 bytes per token
• Optimized: 5 bytes per token (using out-of-band storage and computation over memoization)
• Result: Significant reduction in memory use

Abstract Syntax Node (AST)

• Original: 120 bytes average
• Optimized: 15.6 bytes average (using encoding strategy)
• Performance Improvement: 22% improvement in parsing time

Intermediate Representation (IR) Optimization

• Original: 54 bytes average
• Optimized: 20.3 bytes average (using encoding, indexed references)
• Result: 39% reduction in wall clock time for this phase

Embarrassingly Parallel Section

• Implemented parallel processing using a thread pool
• Performance: 8.9 million lines of code processed per second on a Dell Inspiron
  • Caveat: Data from only one part of the pipeline, further optimization needed for whole pipeline performance

Summary

• Core Lesson: CPU is fast, memory is slow—optimize memory usage to leverage CPU speed effectively.
• Tricks: Utilize encoding, align and pack data efficiently, use type-safe integers, store sparse data in hashmaps, separate Boolean data, and employ struct of arrays.
• Real-World Validation: Demonstrated marked performance improvements in Zig compiler by applying DOP strategies.

Conclusion

• Implementing data-oriented design can significantly enhance software performance by optimizing memory layout and access patterns.
• Encouragement to apply these principles in practice for observed benefits.

Thanks for listening!