Mercurial

annotate mrjunejune/src/blog/optimizing-data-structures/index.md @ 126:e7899c93da77

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Remove playground.
author June Park <parkjune1995@gmail.com>
date Thu, 08 Jan 2026 18:03:34 -0800
parents 65e5a5b89a4e
children 295ac2e5ec00
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
100
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
1 ### Optimizing Data Structures for Performance
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
2
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
3 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
4
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
5 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
6
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
7 ```c++
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
8 struct Entity {
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
9 Vector3* position;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
10 Vector3* velocity;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
11 int* id;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
12
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
13 Entity();
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
14 ~Entity();
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
15
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
16 void update();
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 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
19
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
20 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
21
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
22 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
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 | position (8 bytes) | velocity (8 bytes) | id (8 bytes) |
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
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
28 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
29
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
30 - `position` might point to memory at `0x1000`.
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
31 - `velocity` might point to memory at `0x2000`.
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
32 - `id` might point to memory at `0x3000`.
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
33
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
34 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
35
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
36 Here’s an optimized version of the `Entity` struct:
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
37
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
38 ```c++
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
39 struct Entity {
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
40 char* memory_block = nullptr;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
41 Vector3* position = nullptr;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
42 Vector3* velocity = nullptr;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
43 int* id = nullptr;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
44
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
45 Entity();
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
46 ~Entity();
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
47
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
48 void update();
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 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
51
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
52 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
53
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
54 ```c++
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
55 Entity::Entity() {
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
56 memory_block = new char[sizeof(Vector3) * 2 + sizeof(int)];
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
57
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
58 position = new (memory_block) Vector3;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
59 velocity = new (memory_block + sizeof(Vector3)) Vector3;
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
60 id = new (memory_block + sizeof(Vector3) * 2) int(10);
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
61 }
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
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
64 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
65
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
66 ### Performance Comparison
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 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
69
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 Updated Entities: 5,000,000
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 Heap-Allocated Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
74 Time taken: 409.119 ms
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
75 Memory Block Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
76 Time taken: 358.371 ms
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 Second run (reversed):
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
79 Memory Block Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
80 Time taken: 353.688 ms
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
81 Heap-Allocated Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
82 Time taken: 423.250 ms
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
83 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
84
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
85 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
86
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
87 ```
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
88 Number of Entities: 100,000
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 Heap-Allocated Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
91 Time taken: 554.954 ms
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
92 Memory Block Entity
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
93 Time taken: 481.258 ms
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
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
96 ### Observations
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
97
65e5a5b89a4e [Seobeo] Migrated everything to this page.
June Park <parkjune1995@gmail.com>
parents:
diff changeset
98 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.