Mercurial

annotate mrjunejune/src/blog/optimizing-data-structures/index.md @ 182:d6ab5921fedc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merging in changes I had on my mac related to JSON parser and MPC endpoints.
author June Park <parkjune1995@gmail.com>
date Fri, 23 Jan 2026 21:09:49 -0800
parents 295ac2e5ec00
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
169
295ac2e5ec00 [MrJuneJune] Created separate target for generating html from md.
MrJuneJune <me@mrjunejune.com>
parents: 100
diff changeset
1 ---
295ac2e5ec00 [MrJuneJune] Created separate target for generating html from md.
MrJuneJune <me@mrjunejune.com>
parents: 100
diff changeset
2 title: Optimizing Data Structures for Performance
295ac2e5ec00 [MrJuneJune] Created separate target for generating html from md.
MrJuneJune <me@mrjunejune.com>
parents: 100
diff changeset
3 description: Understanding how memory layout affects cache performance in C++ games, with examples of pointer indirection and contiguous data structures.
295ac2e5ec00 [MrJuneJune] Created separate target for generating html from md.
MrJuneJune <me@mrjunejune.com>
parents: 100
diff changeset
4 ---
295ac2e5ec00 [MrJuneJune] Created separate target for generating html from md.
MrJuneJune <me@mrjunejune.com>
parents: 100
diff changeset
5
100
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
6 ### Optimizing Data Structures for Performance
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
7
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
8 In my professional experience as a full-stack engineer, I primarily work with languages like Python, JavaScript, and Ruby, which don’t provide strict control over memory management. Contract work requiring languages like C or C++ is rare, as most clients prefer "modern" languages that prioritize ease of use over low-level control. Even on the few occasions when I did write C or C++ code, my focus was not on performance optimization. However, I recently observed some C++ code that changed my perspective.
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
9
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
10 Let’s consider creating a simple entity for a video game:
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
11
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
12 ```c++
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
13 struct Entity {
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
14 Vector3* position;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
15 Vector3* velocity;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
16 int* id;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
17
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
18 Entity();
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
19 ~Entity();
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
20
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
21 void update();
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
22 };
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
23 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
24
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
25 At first glance, this structure seems perfectly reasonable, especially if additional attributes are added later. However, if performance is a concern, this approach has significant drawbacks. While the pointers themselves are stored contiguously in memory, the data they point to may be dynamically allocated in disparate locations on the heap, leading to poor cache locality and slower performance.
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
26
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
27 For example, in a 64-bit computer, the `Entity` struct might look like this in memory:
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
28
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
29 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
30 | position (8 bytes) | velocity (8 bytes) | id (8 bytes) |
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
31 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
32
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
33 However, the data the pointers reference could be scattered across the heap:
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
34
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
35 - `position` might point to memory at `0x1000`.
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
36 - `velocity` might point to memory at `0x2000`.
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
37 - `id` might point to memory at `0x3000`.
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
38
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
39 Since these memory addresses are not contiguous or guaranteed to be close, accessing them involves additional overhead. To address this, we can allocate a centralized memory block to improve performance and cache locality.
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
40
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
41 Here’s an optimized version of the `Entity` struct:
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
42
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
43 ```c++
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
44 struct Entity {
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
45 char* memory_block = nullptr;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
46 Vector3* position = nullptr;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
47 Vector3* velocity = nullptr;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
48 int* id = nullptr;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
49
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
50 Entity();
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
51 ~Entity();
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
52
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
53 void update();
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
54 };
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
55 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
56
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
57 In this version, we allocate a single memory block for the entire `Entity` and assign pointers to the relevant sections within that block. Here’s an example of how this can be done:
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
58
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
59 ```c++
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
60 Entity::Entity() {
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
61 memory_block = new char[sizeof(Vector3) * 2 + sizeof(int)];
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
62
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
63 position = new (memory_block) Vector3;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
64 velocity = new (memory_block + sizeof(Vector3)) Vector3;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
65 id = new (memory_block + sizeof(Vector3) * 2) int(10);
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
66 }
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
67 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
68
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
69 Now, all attributes reside within a single, contiguous memory block. This improves cache locality and reduces the number of dynamic allocations, leading to better performance when constructing and accessing `Entity` objects.
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
70
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
71 ### Performance Comparison
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
72
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
73 I ran some simple tests to compare the performance of the two approaches. The first test involved updating 5,000,000 entities. The results are as follows:
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
74
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
75 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
76 Updated Entities: 5,000,000
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
77
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
78 Heap-Allocated Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
79 Time taken: 409.119 ms
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
80 Memory Block Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
81 Time taken: 358.371 ms
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
82
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
83 Second run (reversed):
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
84 Memory Block Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
85 Time taken: 353.688 ms
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
86 Heap-Allocated Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
87 Time taken: 423.250 ms
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
88 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
89
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
90 The second test measured the time taken to initialize and delete 100,000 entities:
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
91
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
92 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
93 Number of Entities: 100,000
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
94
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
95 Heap-Allocated Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
96 Time taken: 554.954 ms
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
97 Memory Block Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
98 Time taken: 481.258 ms
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
99 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
100
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
101 ### Observations
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
102
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
103 The results show a consistent ~20% performance improvement when using a centralized memory block. This difference is significant, especially in performance-critical applications like video games. In the future, I plan to share how I’ve applied similar optimization techniques to improve performance in JavaScript for network requests. These small changes can add up, making a big difference in real-world applications.