-
Notifications
You must be signed in to change notification settings - Fork 513
Expand file tree
/
Copy pathobject-pool.html
More file actions
692 lines (648 loc) · 48.7 KB
/
object-pool.html
File metadata and controls
692 lines (648 loc) · 48.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
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
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
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
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8" />
<title>Object Pool · Optimization Patterns · Game Programming Patterns</title>
<!-- Tell mobile browsers we're optimized for them and they don't need to crop
the viewport. -->
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<link rel="stylesheet" type="text/css" href="style.css" />
<link href="https://fonts.googleapis.com/css?family=Merriweather:400,400italic,700,700italic|Source+Code+Pro|Source+Sans+Pro:200,300,400,600,400italic,600italic|Rock+Salt" rel="stylesheet" type="text/css">
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-42804721-1', 'gameprogrammingpatterns.com');
ga('send', 'pageview');
</script>
<script src="jquery-3.6.0.min.js"></script>
<script src="script.js"></script>
</head>
<body id="top">
<div class="page sidebar">
<span class="theme-toggler" title="dark theme" onclick="toggleTheme()"></span>
<div class="content">
<nav class="top">
<span class="prev">← <a href="dirty-flag.html">Previous Chapter</a></span>
<span class="next"><a href="spatial-partition.html">Next Chapter</a> →</span>
<span class="toc">≡ <a href="/">The Book</a></span>
</nav>
<h1>Object Pool</h1>
<h1 class="book"><a href="/">Game Programming Patterns</a><span class="section"><a href="optimization-patterns.html">Optimization Patterns</a></span></h1>
<h2><a href="#intent" name="intent">Intent</a></h2>
<p><em>Improve performance and memory use by reusing objects from a fixed pool instead
of allocating and freeing them individually.</em></p>
<h2><a href="#motivation" name="motivation">Motivation</a></h2>
<p>We’re working on the visual effects for our game. When the hero casts a spell,
we want a shimmer of sparkles to burst across the screen. This calls for a
<em>particle system</em>, an engine that spawns little sparkly graphics and animates
them until they wink out of existence.</p>
<p>Since a single wave of the wand could cause hundreds of particles to be spawned,
our system needs to be able to create them very quickly. More importantly, we
need to make sure that creating and destroying these particles doesn’t cause
<em>memory fragmentation</em>.</p>
<h3><a href="#the-curse-of-fragmentation" name="the-curse-of-fragmentation">The curse of fragmentation</a></h3>
<p>Programming for a game console or mobile device is closer to embedded
programming than conventional PC programming in many ways. Memory is scarce,
users expect games to be rock solid, and efficient compacting memory managers
are rarely available. In this environment, memory fragmentation is deadly.</p>
<p>Fragmentation means the free space in our heap is <span
name="park">broken</span> into smaller pieces of memory instead of one large
open block. The <em>total</em> memory available may be large, but the largest
<em>contiguous</em> region might be painfully small. Say we’ve got fourteen bytes free,
but it’s fragmented into two seven-byte pieces with a chunk of in-use memory
between them. If we try to allocate a twelve-byte object, we’ll fail. No more
sparklies on screen.</p>
<aside name="park">
<p>It’s like trying to parallel park on a busy street where the already parked cars
are spread out a bit too far. If they’d bunch up, there would be room, but the
free space is <em>fragmented</em> into bits of open curb between half a dozen cars.</p>
</aside>
<p><span name="heap"></span></p>
<p><img src="images/object-pool-heap-fragment.png" alt="A series of memory operations leading to fragmentation." /></p>
<aside name="heap">
<p>Here’s how a heap becomes fragmented and how it can cause an allocation to fail
even where there’s theoretically enough memory available.</p>
</aside>
<p>Even if fragmentation is infrequent, it can still <span
name="soak">gradually</span> reduce the heap to an unusable foam of open holes
and filled-in crevices, ultimately hosing the game completely.</p>
<aside name="soak">
<p>Most console makers require games to pass “soak tests” where they leave the game
running in demo mode for several days. If the game crashes, they don’t allow it
to ship. While soak tests sometimes fail because of a rarely occurring bug, it’s
usually creeping fragmentation or memory leakage that brings the game down.</p>
</aside>
<h3><a href="#the-best-of-both-worlds" name="the-best-of-both-worlds">The best of both worlds</a></h3>
<p>Because of fragmentation and because allocation may be slow, games are very
careful about when and how they manage memory. A simple solution is often best —
grab a big chunk of memory when the game starts, and don’t free it until the game
ends. But this is a pain for systems where we need to create and destroy things
while the game is running.</p>
<p>An object pool gives us the best of both worlds. To the memory manager, we’re
just allocating one big hunk of memory up front and not freeing it while the
game is playing. To the users of the pool, we can freely allocate and deallocate
objects to our heart’s content.</p>
<h2><a href="#the-pattern" name="the-pattern">The Pattern</a></h2>
<p>Define a <strong>pool</strong> class that maintains a collection of <strong>reusable objects</strong>.
Each object supports an <strong>“in use” query</strong> to tell if it is currently “alive”.
When the pool is initialized, it creates the entire collection of objects up
front (usually in a single contiguous allocation) and initializes them all to
the “not in use” state.</p>
<p>When you want a new object, ask the pool for one. It finds an available object,
initializes it to “in use”, and returns it. When the object is no longer needed,
it is set back to the “not in use” state. This way, objects can be freely
created and destroyed without needing to allocate memory or other resources.</p>
<h2><a href="#when-to-use-it" name="when-to-use-it">When to Use It</a></h2>
<p>This pattern is used widely in games for obvious things like game entities and
visual effects, but it is also used for less visible data structures such as currently
playing sounds. Use Object Pool when:</p>
<ul>
<li>
<p>You need to frequently create and destroy objects.</p>
</li>
<li>
<p>Objects are similar in size.</p>
</li>
<li>
<p>Allocating objects on the heap is slow or could lead to memory
fragmentation.</p>
</li>
<li>
<p>Each object encapsulates a resource such as a database or network connection
that is expensive to acquire and could be reused.</p>
</li>
</ul>
<h2><a href="#keep-in-mind" name="keep-in-mind">Keep in Mind</a></h2>
<p>You normally rely on a garbage collector or <code>new</code> and <code>delete</code> to handle
memory management for you. By using an object pool, you’re saying, “I know
better how these bytes should be handled.” That means the onus is on you to deal
with this pattern’s limitations.</p>
<h3><a href="#the-pool-may-waste-memory-on-unneeded-objects" name="the-pool-may-waste-memory-on-unneeded-objects">The pool may waste memory on unneeded objects</a></h3>
<p>The size of an object pool needs to be tuned for the game’s needs. When tuning,
it’s usually obvious when the pool is too <em>small</em> (there’s nothing like a crash
to get your attention). But also take care that the pool isn’t too <em>big</em>. A
smaller pool frees up memory that could be used for other fun stuff.</p>
<h3><a href="#only-a-fixed-number-of-objects-can-be-active-at-any-one-time" name="only-a-fixed-number-of-objects-can-be-active-at-any-one-time">Only a fixed number of objects can be active at any one time</a></h3>
<p>In some ways, this is a good thing. Partitioning memory into separate pools for
different types of objects ensures that, for example, a huge sequence of
explosions won’t cause your particle system to eat <em>all</em> of the available
memory, preventing something more critical like a new enemy from being created.</p>
<p>Nonetheless, this also means being prepared for the possibility that your
attempt to reuse an object from the pool will fail because they are all in use.
There are a few common strategies to handle this:</p>
<ul>
<li>
<p><em>Prevent it outright.</em> This is the most common “fix”: tune the pool sizes so
that they never overflow regardless of what the user does. For pools of
important objects like enemies or gameplay items, this is often the right
answer. There may be no “right” way to handle the lack of a free slot to
create the big boss when the player reaches the end of the level, so the
smart thing to do is make sure that never happens.</p>
<p>The downside is that this can force you to sit on a lot of memory for object
slots that are needed only for a couple of rare edge cases. Because of this,
a single fixed pool size may not be the best fit for all game states. For
instance, some levels may feature effects prominently while others focus on
sound. In such cases, consider having pool sizes tuned differently for each
scenario.</p>
</li>
<li>
<p><em>Just don’t create the object.</em> This sounds harsh, but it makes sense for
cases like our particle system. If all particles are in use, the screen is
probably full of flashing graphics. The user won’t notice if the next
explosion isn’t quite as impressive as the ones currently going off.</p>
</li>
<li>
<p><em>Forcibly kill an existing object.</em> Consider a pool for currently playing
sounds, and assume you want to start a new sound but the pool is full. You
do <em>not</em> want to simply ignore the new sound — the user will notice if their
magical wand swishes dramatically <em>sometimes</em> and stays stubbornly silent
other times. A better solution is to find the quietest sound already playing
and replace that with our new sound. The new sound will mask the audible
cutoff of the previous sound.</p>
<p>In general, if the <em>disappearance</em> of an existing object would be less
noticeable than the <em>absence</em> of a new one, this may be the right choice.</p>
</li>
<li>
<p><em>Increase the size of the pool.</em> If your game lets you be a bit more
flexible with memory, you may be able to increase the size of the pool at
runtime or create a second overflow pool. If you do grab more memory in
either of these ways, consider whether or not the pool should contract to
its previous size when the additional capacity is no longer needed.</p>
</li>
</ul>
<h3><a href="#memory-size-for-each-object-is-fixed" name="memory-size-for-each-object-is-fixed">Memory size for each object is fixed</a></h3>
<p>Most pool implementations store the objects in an array of in-place objects. If
all of your objects are of the same type, this is fine. However, if you want to
store objects of different types in the pool, or instances of subclasses that
may add fields, you need to ensure that each slot in the pool has enough memory
for the <em>largest</em> possible object. Otherwise, an unexpectedly large object will
stomp over the next one and trash memory.</p>
<p>At the same time, when your objects vary in size, you waste memory. Each slot
needs to be big enough to accommodate the largest object. If objects are rarely
that big, you’re throwing away memory every time you put a smaller one in that
slot. It’s like going through airport security and using a huge carry-on-sized
luggage tray just for your keys and wallet.</p>
<p>When you find yourself burning a lot of memory this way, consider splitting the
pool into <span name="pools">separate</span> pools for different sizes of
object — big trays for luggage, little trays for pocket stuff.</p>
<aside name="pools">
<p>This is a common pattern for implementing speed-efficient memory managers. The
manager has a number of pools of different block sizes. When you ask it to
allocate a block, it finds in an open slot in the pool of the appropriate size
and allocates from that pool.</p>
</aside>
<h3><a href="#reused-objects-aren't-automatically-cleared" name="reused-objects-aren't-automatically-cleared">Reused objects aren’t automatically cleared</a></h3>
<p>Most memory managers have a debug feature that will clear freshly allocated or
freed memory to some obvious magic value like <code>0xdeadbeef</code>. This helps you find
painful bugs caused by uninitialized variables or using memory after it’s freed.</p>
<p>Since our object pool isn’t going through the memory manager any more when it
reuses an object, we lose that safety net. Worse, the memory used for a “new”
object previously held an object of the exact same type. This makes it nearly
impossible to tell if you forgot to initialize something when you created the
new object: the memory where the object is stored may already contain <em>almost</em>
correct data from its past life.</p>
<p>Because of this, pay special care that the code that initializes new objects in
the pool <em>fully</em> initializes the object. It may even be worth spending a bit of
time adding a debug feature that <span name="clear">clears</span> the memory for
an object slot when the object is reclaimed.</p>
<aside name="clear">
<p>I’d be honored if you clear it to <code>0x1deadb0b</code>.</p>
</aside>
<h3><a href="#unused-objects-will-remain-in-memory" name="unused-objects-will-remain-in-memory">Unused objects will remain in memory</a></h3>
<p>Object pools are less common in systems that support garbage collection because
the memory manager will usually deal with fragmentation for you. But pools are
still useful there to avoid the cost of allocation and deallocation, especially
on mobile devices with slower CPUs and simpler garbage collectors.</p>
<p>If you do use an object pool in concert with a garbage collector, beware of a potential conflict. Since the
pool doesn’t actually deallocate objects when they’re no longer in use, they
remain in memory. If they contain references to <em>other</em> objects, it will prevent
the collector from reclaiming those too. To avoid this, when a pooled object is
no longer in use, clear any references it has to other objects.</p>
<h2><a href="#sample-code" name="sample-code">Sample Code</a></h2>
<p>Real-world particle systems will often apply gravity, wind, friction, and other
physical effects. Our much simpler sample will only move particles in a straight
line for a certain number of frames and then kill the particle. Not exactly film
caliber, but it should illustrate how to use an object pool.</p>
<p>We’ll start with the simplest possible implementation. First up is the little
particle class:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">Particle</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="n">Particle</span><span class="p">()</span>
<span class="o">:</span> <span class="n">framesLeft_</span><span class="p">(</span><span class="mi">0</span><span class="p">)</span>
<span class="p">{}</span>
<span class="kt">void</span> <span class="n">init</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">,</span>
<span class="kt">double</span> <span class="n">xVel</span><span class="p">,</span> <span class="kt">double</span> <span class="n">yVel</span><span class="p">,</span> <span class="kt">int</span> <span class="n">lifetime</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">x_</span> <span class="o">=</span> <span class="n">x</span><span class="p">;</span> <span class="n">y_</span> <span class="o">=</span> <span class="n">y</span><span class="p">;</span>
<span class="n">xVel_</span> <span class="o">=</span> <span class="n">xVel</span><span class="p">;</span> <span class="n">yVel_</span> <span class="o">=</span> <span class="n">yVel</span><span class="p">;</span>
<span class="n">framesLeft_</span> <span class="o">=</span> <span class="n">lifetime</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">void</span> <span class="n">animate</span><span class="p">()</span>
<span class="p">{</span>
<span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">inUse</span><span class="p">())</span> <span class="k">return</span><span class="p">;</span>
<span class="n">framesLeft_</span><span class="o">--</span><span class="p">;</span>
<span class="n">x_</span> <span class="o">+=</span> <span class="n">xVel_</span><span class="p">;</span>
<span class="n">y_</span> <span class="o">+=</span> <span class="n">yVel_</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">bool</span> <span class="n">inUse</span><span class="p">()</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">framesLeft_</span> <span class="o">></span> <span class="mi">0</span><span class="p">;</span> <span class="p">}</span>
<span class="k">private</span><span class="o">:</span>
<span class="kt">int</span> <span class="n">framesLeft_</span><span class="p">;</span>
<span class="kt">double</span> <span class="n">x_</span><span class="p">,</span> <span class="n">y_</span><span class="p">;</span>
<span class="kt">double</span> <span class="n">xVel_</span><span class="p">,</span> <span class="n">yVel_</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></div>
<p>The default constructor initializes the particle to “not in use”. A later call
to <code>init()</code> initializes the particle to a live state. Particles are animated
over time using the unsurprisingly named <code>animate()</code> function, which should be
called once per frame.</p>
<p>The pool needs to know which particles are available for reuse. It gets this
from the particle’s <code>inUse()</code> function. This function takes advantage of the fact that
particles have a limited lifetime and uses the <code>framesLeft_</code> variable to
discover which particles are in use without having to store a separate flag.</p>
<p>The pool class is also simple:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">ParticlePool</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="kt">void</span> <span class="n">create</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">,</span>
<span class="kt">double</span> <span class="n">xVel</span><span class="p">,</span> <span class="kt">double</span> <span class="n">yVel</span><span class="p">,</span> <span class="kt">int</span> <span class="n">lifetime</span><span class="p">);</span>
<span class="kt">void</span> <span class="nf">animate</span><span class="p">()</span>
<span class="p">{</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">POOL_SIZE</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">particles_</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">animate</span><span class="p">();</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="k">private</span><span class="o">:</span>
<span class="k">static</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">POOL_SIZE</span> <span class="o">=</span> <span class="mi">100</span><span class="p">;</span>
<span class="n">Particle</span> <span class="n">particles_</span><span class="p">[</span><span class="n">POOL_SIZE</span><span class="p">];</span>
<span class="p">};</span>
</code></pre></div>
<p>The <code>create()</code> function lets external code create new particles. The game calls
<span name="update"><code>animate()</code></span> once per frame, which in turn animates
each particle in the pool.</p>
<aside name="update">
<p>This <code>animate()</code> method is an example of the <a href="update-method.html"
class="pattern">Update Method</a> pattern.</p>
</aside>
<p>The particles themselves are simply stored in a fixed-size array in the class.
In this sample implementation, the pool size is hardcoded in the class
declaration, but this could be defined externally by using a dynamic array of a
given size or by using a value template parameter.</p>
<p>Creating a new particle is straightforward:</p>
<div class="codehilite"><pre><span></span><code><span class="kt">void</span> <span class="nf">ParticlePool::create</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">,</span>
<span class="kt">double</span> <span class="n">xVel</span><span class="p">,</span> <span class="kt">double</span> <span class="n">yVel</span><span class="p">,</span>
<span class="kt">int</span> <span class="n">lifetime</span><span class="p">)</span>
<span class="p">{</span>
<span class="c1">// Find an available particle.</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">POOL_SIZE</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">particles_</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">inUse</span><span class="p">())</span>
<span class="p">{</span>
<span class="n">particles_</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">init</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">xVel</span><span class="p">,</span> <span class="n">yVel</span><span class="p">,</span> <span class="n">lifetime</span><span class="p">);</span>
<span class="k">return</span><span class="p">;</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="p">}</span>
</code></pre></div>
<p>We iterate through the pool looking for the first available particle. When we
find it, we initialize it and we’re done. Note that in this implementation, if
there aren’t any available particles, we simply don’t create a new one.</p>
<p>That’s all there is to a simple particle system, aside from rendering the
particles, of course. We can now create a pool and create some particles using
it. The particles will automatically deactivate themselves when their lifetime
has expired.</p>
<p>This is good enough to ship a game, but keen eyes may have noticed that creating
a new particle requires <span name="create">iterating</span> through
(potentially) the entire collection until we find an open slot. If the pool is
very large and mostly full, that can get slow. Let’s see how we can improve
that.</p>
<aside name="create">
<p>Creating a particle has <em>O(n)</em> complexity, for those of us who remember our
algorithms class.</p>
</aside>
<h3><a href="#a-free-list" name="a-free-list">A free list</a></h3>
<p>If we don’t want to waste time <em>finding</em> free particles, the obvious answer is
to not lose track of them. We could store a separate list of pointers to each
unused particle. Then, when we need to create a particle, we remove the
first pointer from the list and reuse the particle it points to.</p>
<p>Unfortunately, this would require us to maintain an entire separate array with
as many pointers as there are objects in the pool. After all, when we first
create the pool, <em>all</em> particles are unused, so the list would initially have a
pointer to every object in the pool.</p>
<p>It would be nice to fix our performance problems <em>without</em> sacrificing any
memory. Conveniently, there is some memory already lying around that we can borrow —
the data for the unused particles themselves.</p>
<p>When a particle isn’t in use, most of its state is irrelevant. Its position and
velocity aren’t being used. The only state it needs is the stuff required to
tell if it’s dead. In our example, that’s the <code>framesLeft_</code> member. All those
other bits can be reused. Here’s a revised particle:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">Particle</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="c1">// ...</span>
<span class="n">Particle</span><span class="o">*</span> <span class="n">getNext</span><span class="p">()</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">state_</span><span class="p">.</span><span class="n">next</span><span class="p">;</span> <span class="p">}</span>
<span class="kt">void</span> <span class="n">setNext</span><span class="p">(</span><span class="n">Particle</span><span class="o">*</span> <span class="n">next</span><span class="p">)</span> <span class="p">{</span> <span class="n">state_</span><span class="p">.</span><span class="n">next</span> <span class="o">=</span> <span class="n">next</span><span class="p">;</span> <span class="p">}</span>
<span class="k">private</span><span class="o">:</span>
<span class="kt">int</span> <span class="n">framesLeft_</span><span class="p">;</span>
<span class="k">union</span>
<span class="p">{</span>
<span class="c1">// State when it's in use.</span>
<span class="k">struct</span>
<span class="p">{</span>
<span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">;</span>
<span class="kt">double</span> <span class="n">xVel</span><span class="p">,</span> <span class="n">yVel</span><span class="p">;</span>
<span class="p">}</span> <span class="n">live</span><span class="p">;</span>
<span class="c1">// State when it's available.</span>
<span class="n">Particle</span><span class="o">*</span> <span class="n">next</span><span class="p">;</span>
<span class="p">}</span> <span class="n">state_</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></div>
<p>We’ve moved all of the member variables except for <code>framesLeft_</code>
into a <code>live</code> struct inside a <code>state_</code> <span name="union">union</span>. This
struct holds the particle’s state when it’s being animated. When the particle is
unused, the other case of the union, the <code>next</code> member, is used. It holds a
pointer to the next available particle after this one.</p>
<aside name="union">
<p>Unions don’t seem to be used that often these days, so the syntax may be
unfamiliar to you. If you’re on a game team, you’ve probably got a “memory
guru”, that beleaguered compatriot whose job it is to come up with a solution
when the game has inevitably blown its memory budget. Ask them about unions.
They’ll know all about them and other fun bit-packing tricks.</p>
</aside>
<p>We can use these pointers to build a linked list that chains together every
unused particle in the pool. We have the list of available particles we need,
but we didn’t need to use any additional memory. Instead, we cannibalize the memory
of the dead particles themselves to store the list.</p>
<p>This clever technique is called a <a href="http://en.wikipedia.org/wiki/Free_list"><em>free
list</em></a>. For it to work, we need to make
sure the pointers are initialized correctly and are maintained when particles
are created and destroyed. And, of course, we need to keep track of the list’s
head:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">ParticlePool</span>
<span class="p">{</span>
<span class="c1">// ...</span>
<span class="k">private</span><span class="o">:</span>
<span class="n">Particle</span><span class="o">*</span> <span class="n">firstAvailable_</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></div>
<p>When a pool is first created, <em>all</em> of the particles are available, so our free
list should thread through the entire pool. The pool constructor sets that up:</p>
<div class="codehilite"><pre><span></span><code><span class="n">ParticlePool</span><span class="o">::</span><span class="n">ParticlePool</span><span class="p">()</span>
<span class="p">{</span>
<span class="c1">// The first one is available.</span>
<span class="n">firstAvailable_</span> <span class="o">=</span> <span class="o">&</span><span class="n">particles_</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
<span class="c1">// Each particle points to the next.</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">POOL_SIZE</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">particles_</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">setNext</span><span class="p">(</span><span class="o">&</span><span class="n">particles_</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]);</span>
<span class="p">}</span>
<span class="c1">// The last one terminates the list.</span>
<span class="n">particles_</span><span class="p">[</span><span class="n">POOL_SIZE</span> <span class="o">-</span> <span class="mi">1</span><span class="p">].</span><span class="n">setNext</span><span class="p">(</span><span class="nb">NULL</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div>
<p>Now to create a new particle, we jump directly to the <span
name="first">first</span> available one:</p>
<aside name="first">
<p><em>O(1)</em> complexity, baby! Now we’re cooking!</p>
</aside>
<div class="codehilite"><pre><span></span><code><span class="kt">void</span> <span class="nf">ParticlePool::create</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">,</span>
<span class="kt">double</span> <span class="n">xVel</span><span class="p">,</span> <span class="kt">double</span> <span class="n">yVel</span><span class="p">,</span>
<span class="kt">int</span> <span class="n">lifetime</span><span class="p">)</span>
<span class="p">{</span>
<span class="c1">// Make sure the pool isn't full.</span>
<span class="n">assert</span><span class="p">(</span><span class="n">firstAvailable_</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">);</span>
<span class="c1">// Remove it from the available list.</span>
<span class="n">Particle</span><span class="o">*</span> <span class="n">newParticle</span> <span class="o">=</span> <span class="n">firstAvailable_</span><span class="p">;</span>
<span class="n">firstAvailable_</span> <span class="o">=</span> <span class="n">newParticle</span><span class="o">-></span><span class="n">getNext</span><span class="p">();</span>
<span class="n">newParticle</span><span class="o">-></span><span class="n">init</span><span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">xVel</span><span class="p">,</span> <span class="n">yVel</span><span class="p">,</span> <span class="n">lifetime</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div>
<p>We need to know when a particle dies so we can add it back to the free list, so
we’ll change <code>animate()</code> to return <code>true</code> if the previously live particle gave
up the ghost in that frame:</p>
<div class="codehilite"><pre><span></span><code><span class="kt">bool</span> <span class="nf">Particle::animate</span><span class="p">()</span>
<span class="p">{</span>
<span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">inUse</span><span class="p">())</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span>
<span class="n">framesLeft_</span><span class="o">--</span><span class="p">;</span>
<span class="n">x_</span> <span class="o">+=</span> <span class="n">xVel_</span><span class="p">;</span>
<span class="n">y_</span> <span class="o">+=</span> <span class="n">yVel_</span><span class="p">;</span>
<span class="k">return</span> <span class="n">framesLeft_</span> <span class="o">==</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
<p>When that happens, we simply thread it back onto the list:</p>
<div class="codehilite"><pre><span></span><code><span class="kt">void</span> <span class="nf">ParticlePool::animate</span><span class="p">()</span>
<span class="p">{</span>
<span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">POOL_SIZE</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">if</span> <span class="p">(</span><span class="n">particles_</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">animate</span><span class="p">())</span>
<span class="p">{</span>
<span class="c1">// Add this particle to the front of the list.</span>
<span class="n">particles_</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">setNext</span><span class="p">(</span><span class="n">firstAvailable_</span><span class="p">);</span>
<span class="n">firstAvailable_</span> <span class="o">=</span> <span class="o">&</span><span class="n">particles_</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="p">}</span>
</code></pre></div>
<p>There you go, a nice little object pool with constant-time creation and
deletion.</p>
<h2><a href="#design-decisions" name="design-decisions">Design Decisions</a></h2>
<p>As you’ve seen, the simplest object pool implementation is almost trivial:
create an array of objects and reinitialize them as needed. Production code is
rarely that minimal. There are several ways to expand on that to make the pool
more generic, safer to use, or easier to maintain. As you implement pools in
your games, you’ll need to answer these questions:</p>
<h3><a href="#are-objects-coupled-to-the-pool" name="are-objects-coupled-to-the-pool">Are objects coupled to the pool?</a></h3>
<p>The first question you’ll run into when writing an object pool is whether the
objects themselves know they are in a pool. Most of the time they will, but you
won’t have that luxury when writing a generic pool class that can hold arbitrary
objects.</p>
<ul>
<li>
<p><strong>If objects are coupled to the pool:</strong></p>
<ul>
<li>
<p><em>The implementation is simpler.</em> You can simply put an “in use” flag or
function in your pooled object and be done with it.</p>
</li>
<li>
<p><em>You can ensure that the objects can only be created by the pool.</em> In
C++, a simple way to do this is to make the pool class a friend of the
object class and then make the object’s constructor private.</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">Particle</span>
<span class="p">{</span>
<span class="k">friend</span> <span class="k">class</span> <span class="nc">ParticlePool</span><span class="p">;</span>
<span class="k">private</span><span class="o">:</span>
<span class="n">Particle</span><span class="p">()</span>
<span class="o">:</span> <span class="n">inUse_</span><span class="p">(</span><span class="nb">false</span><span class="p">)</span>
<span class="p">{}</span>
<span class="kt">bool</span> <span class="n">inUse_</span><span class="p">;</span>
<span class="p">};</span>
<span class="k">class</span> <span class="nc">ParticlePool</span>
<span class="p">{</span>
<span class="n">Particle</span> <span class="n">pool_</span><span class="p">[</span><span class="mi">100</span><span class="p">];</span>
<span class="p">};</span>
</code></pre></div>
<p>This relationship documents the intended way to use the class and
ensures your users don’t create objects that aren’t tracked by the pool.</p>
</li>
<li>
<p><em>You may be able to avoid storing an explicit “in use” flag.</em> Many
objects already retain some state that could be used to tell whether it
is alive or not. For example, a particle may be available for reuse if
its current position is offscreen. If the object class knows it may be
used in a pool, it can provide an <code>inUse()</code> method to query that state.
This saves the pool from having to burn some extra memory storing a
bunch of “in use” flags.</p>
</li>
</ul>
</li>
<li>
<p><strong>If objects are not coupled to the pool:</strong></p>
<ul>
<li>
<p><em>Objects of any type can be pooled.</em> This is the big advantage. By
decoupling objects from the pool, you may be able to implement a generic
reusable pool class.</p>
</li>
<li>
<p><em>The “in use” state must be tracked outside the objects.</em> The simplest
way to do this is by creating a separate bit field:</p>
<div class="codehilite"><pre><span></span><code><span class="k">template</span> <span class="o"><</span><span class="k">class</span> <span class="nc">TObject</span><span class="o">></span>
<span class="k">class</span> <span class="nc">GenericPool</span>
<span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
<span class="k">static</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">POOL_SIZE</span> <span class="o">=</span> <span class="mi">100</span><span class="p">;</span>
<span class="n">TObject</span> <span class="n">pool_</span><span class="p">[</span><span class="n">POOL_SIZE</span><span class="p">];</span>
<span class="kt">bool</span> <span class="n">inUse_</span><span class="p">[</span><span class="n">POOL_SIZE</span><span class="p">];</span>
<span class="p">};</span>
</code></pre></div>
</li>
</ul>
</li>
</ul>
<h3><a href="#what-is-responsible-for-initializing-the-reused-objects" name="what-is-responsible-for-initializing-the-reused-objects">What is responsible for initializing the reused objects?</a></h3>
<p>In order to reuse an existing object, it must be reinitialized with new state. A
key question here is whether to reinitialize the object inside the pool class or
outside.</p>
<ul>
<li>
<p><strong>If the pool reinitializes internally:</strong></p>
<ul>
<li>
<p><em>The pool can completely encapsulate its objects</em>. Depending on the
other capabilities your objects need, you may be able to keep them
completely internal to the pool. This makes sure that other code doesn’t
maintain references to objects that could be unexpectedly reused.</p>
</li>
<li>
<p><em>The pool is tied to how objects are initialized</em>. A pooled object may
offer multiple functions that initialize it. If the pool manages
initialization, its interface needs to support all of those and forward
them to the object.</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">Particle</span>
<span class="p">{</span>
<span class="c1">// Multiple ways to initialize.</span>
<span class="kt">void</span> <span class="nf">init</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">);</span>
<span class="kt">void</span> <span class="nf">init</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">,</span> <span class="kt">double</span> <span class="n">angle</span><span class="p">);</span>
<span class="kt">void</span> <span class="nf">init</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">,</span> <span class="kt">double</span> <span class="n">xVel</span><span class="p">,</span> <span class="kt">double</span> <span class="n">yVel</span><span class="p">);</span>
<span class="p">};</span>
<span class="k">class</span> <span class="nc">ParticlePool</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="kt">void</span> <span class="n">create</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">)</span>
<span class="p">{</span>
<span class="c1">// Forward to Particle...</span>
<span class="p">}</span>
<span class="kt">void</span> <span class="n">create</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">,</span> <span class="kt">double</span> <span class="n">angle</span><span class="p">)</span>
<span class="p">{</span>
<span class="c1">// Forward to Particle...</span>
<span class="p">}</span>
<span class="kt">void</span> <span class="n">create</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">,</span> <span class="kt">double</span> <span class="n">xVel</span><span class="p">,</span> <span class="kt">double</span> <span class="n">yVel</span><span class="p">)</span>
<span class="p">{</span>
<span class="c1">// Forward to Particle...</span>
<span class="p">}</span>
<span class="p">};</span>
</code></pre></div>
</li>
</ul>
</li>
<li>
<p><strong>If outside code initializes the object:</strong></p>
<ul>
<li>
<p><em>The pool’s interface can be simpler.</em> Instead of offering multiple
functions to cover each way an object can be initialized, the pool can
simply return a reference to the new object:</p>
<div class="codehilite"><pre><span></span><code><span class="k">class</span> <span class="nc">Particle</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="c1">// Multiple ways to initialize.</span>
<span class="kt">void</span> <span class="n">init</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">);</span>
<span class="kt">void</span> <span class="nf">init</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">,</span> <span class="kt">double</span> <span class="n">angle</span><span class="p">);</span>
<span class="kt">void</span> <span class="nf">init</span><span class="p">(</span><span class="kt">double</span> <span class="n">x</span><span class="p">,</span> <span class="kt">double</span> <span class="n">y</span><span class="p">,</span> <span class="kt">double</span> <span class="n">xVel</span><span class="p">,</span> <span class="kt">double</span> <span class="n">yVel</span><span class="p">);</span>
<span class="p">};</span>
<span class="k">class</span> <span class="nc">ParticlePool</span>
<span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
<span class="n">Particle</span><span class="o">*</span> <span class="n">create</span><span class="p">()</span>
<span class="p">{</span>
<span class="c1">// Return reference to available particle...</span>
<span class="p">}</span>
<span class="k">private</span><span class="o">:</span>
<span class="n">Particle</span> <span class="n">pool_</span><span class="p">[</span><span class="mi">100</span><span class="p">];</span>
<span class="p">};</span>
</code></pre></div>
<p>The caller can then initialize the object by calling any method the
object exposes:</p>
<div class="codehilite"><pre><span></span><code><span class="n">ParticlePool</span> <span class="n">pool</span><span class="p">;</span>
<span class="n">pool</span><span class="p">.</span><span class="n">create</span><span class="p">()</span><span class="o">-></span><span class="n">init</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">);</span>
<span class="n">pool</span><span class="p">.</span><span class="n">create</span><span class="p">()</span><span class="o">-></span><span class="n">init</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mf">0.3</span><span class="p">);</span>
<span class="n">pool</span><span class="p">.</span><span class="n">create</span><span class="p">()</span><span class="o">-></span><span class="n">init</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mf">3.3</span><span class="p">,</span> <span class="mf">4.4</span><span class="p">);</span>
</code></pre></div>
</li>
<li>
<p><em>Outside code may need to handle the failure to create a new object.</em>
The previous example assumes that <code>create()</code> will always successfully
return a pointer to an object. If the pool is full, though, it may
return <code>NULL</code> instead. To be safe, you’ll need to check for that before
you try to initialize the object:</p>
<div class="codehilite"><pre><span></span><code><span class="n">Particle</span><span class="o">*</span> <span class="n">particle</span> <span class="o">=</span> <span class="n">pool</span><span class="p">.</span><span class="n">create</span><span class="p">();</span>
<span class="k">if</span> <span class="p">(</span><span class="n">particle</span> <span class="o">!=</span> <span class="nb">NULL</span><span class="p">)</span> <span class="n">particle</span><span class="o">-></span><span class="n">init</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">);</span>
</code></pre></div>
</li>
</ul>
</li>
</ul>
<h2><a href="#see-also" name="see-also">See Also</a></h2>
<ul>
<li>
<p>This looks a lot like the <a class="gof-pattern" href="flyweight.html">
Flyweight</a> pattern. Both maintain a collection of reusable objects. The
difference is what “reuse” means. Flyweight objects are reused by sharing
the same instance between multiple owners <em>simultaneously</em>. The Flyweight pattern avoids
<em>duplicate</em> memory usage by using the same object in multiple contexts.</p>
<p>The objects in a pool get reused too, but only over time. “Reuse” in the
context of an object pool means reclaiming the memory for an object <em>after</em>
the original owner is done with it. With an object pool, there isn’t any
expectation that an object will be shared within its lifetime.</p>
</li>
<li>
<p>Packing a bunch of objects of the same type together in memory helps keep
your CPU cache full as the game iterates over those objects. The <a
class="pattern" href="data-locality.html">Data Locality</a> pattern is all
about that.</p>
</li>
</ul>
<nav>
<span class="prev">← <a href="dirty-flag.html">Previous Chapter</a></span>
<span class="next"><a href="spatial-partition.html">Next Chapter</a> →</span>
<span class="toc">≡ <a href="/">The Book</a></span>
</nav>
</div>
</div>
<footer>© 2009-2021 Robert Nystrom</footer>
</body>
</html>