Mercurial

comparison mrjunejune/src/blog/optimizing-data-structures/index.md @ 100:65e5a5b89a4e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[Seobeo] Migrated everything to this page.
author June Park <parkjune1995@gmail.com>
date Sat, 03 Jan 2026 07:48:07 -0800
parents
children 295ac2e5ec00
comparison
equal deleted inserted replaced
99:684edfaf93b7 100:65e5a5b89a4e
1 ### Optimizing Data Structures for Performance
2
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.
4
5 Let’s consider creating a simple entity for a video game:
6
7 ```c++
8 struct Entity {
9 Vector3* position;
10 Vector3* velocity;
11 int* id;
12
13 Entity();
14 ~Entity();
15
16 void update();
17 };
18 ```
19
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.
21
22 For example, in a 64-bit computer, the `Entity` struct might look like this in memory:
23
24 ```
25 | position (8 bytes) | velocity (8 bytes) | id (8 bytes) |
26 ```
27
28 However, the data the pointers reference could be scattered across the heap:
29
30 - `position` might point to memory at `0x1000`.
31 - `velocity` might point to memory at `0x2000`.
32 - `id` might point to memory at `0x3000`.
33
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.
35
36 Here’s an optimized version of the `Entity` struct:
37
38 ```c++
39 struct Entity {
40 char* memory_block = nullptr;
41 Vector3* position = nullptr;
42 Vector3* velocity = nullptr;
43 int* id = nullptr;
44
45 Entity();
46 ~Entity();
47
48 void update();
49 };
50 ```
51
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:
53
54 ```c++
55 Entity::Entity() {
56 memory_block = new char[sizeof(Vector3) * 2 + sizeof(int)];
57
58 position = new (memory_block) Vector3;
59 velocity = new (memory_block + sizeof(Vector3)) Vector3;
60 id = new (memory_block + sizeof(Vector3) * 2) int(10);
61 }
62 ```
63
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.
65
66 ### Performance Comparison
67
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:
69
70 ```
71 Updated Entities: 5,000,000
72
73 Heap-Allocated Entity
74 Time taken: 409.119 ms
75 Memory Block Entity
76 Time taken: 358.371 ms
77
78 Second run (reversed):
79 Memory Block Entity
80 Time taken: 353.688 ms
81 Heap-Allocated Entity
82 Time taken: 423.250 ms
83 ```
84
85 The second test measured the time taken to initialize and delete 100,000 entities:
86
87 ```
88 Number of Entities: 100,000
89
90 Heap-Allocated Entity
91 Time taken: 554.954 ms
92 Memory Block Entity
93 Time taken: 481.258 ms
94 ```
95
96 ### Observations
97
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.