Object pooling class BubbleList

Question

Please review C++ class BubbleList design with performance in mind.

Named BubbleList as pooled (unused) objects bubble to the high end of the vector, providing a continuouse set of active objects, delimited by BubbleList.count

It is designed to reduce memory allocation / free overheads of many short lived objects in game like environments (eg bullets, smoke FX, etc). Objects are pooled rather than deleted.

BubbleList maintains ownership of pooled objects, though this is not enforced.

Note there is no guard for the specialization calls bool BubbleList.Update() and bool BubbleList.Update(const bool updateFrame, Box2 *bounds) {

/** 
 * MSVS: Microsoft Visual Studio V17.6.5
 * Relevant compile / link flags: 
 * /std:c17 /std:c++20 /WX /W4 /sdl- /Ob2 /Oi /Ot /GS- 
 * /permissive- /Zc:rvalueCast- /OPT:REF /OPT:ICF 
 **/
/**
 * Use C style casts to reduce code noise. 
 * Compiler converts C Style `(target)expression` to C++ style `static_cast<target>(expression)`
 * See https://en.cppreference.com/w/cpp/language/explicit_cast#Explanation for detailed conversion rules
 **/ 
 
 
/* 
From global.h
#define BM67__FORCE_32_BIT_SIZE
From shorthandTypes.h
#ifdef BM67__FORCE_32_BIT_SIZE
 typedef uint32_t sZ;
#else
 typedef size_t sZ;
#endif
typedef uint32_t u32;
typedef int32_t i32;
typedef const uint32_t cu32;
*/
#pragma once
#include "global.h"
#include "shorthandTypes.h"
#include <vector>
#include "Box2.h"
template <typename Item>
class BubbleList {
public: 
 BubbleList() = default;
 ~BubbleList() noexcept { Clear(); }
 void Clear() noexcept {
 for (Item* item : items) { delete item; }
 items.clear();
 items.shrink_to_fit(); 
 dirty = true;
 count = 0;
 idx = 0;
 }
 void Trim() noexcept {
 sZ size = (sZ)items.size();
 while (size-- > count) {
 delete items[size];
 items.pop_back();
 }
 }
 Item* Spawn() noexcept {
 Item* item = nullptr;
 if ((sZ)items.size() > count) { item = items[count]; }
 else { items.push_back(item = new Item); }
 dirty = true;
 count++;
 return item;
 }
 void Start() noexcept { idx = 0; }
 Item* Next() noexcept { 
 if (idx < count) { return items[idx++]; }
 idx = 0;
 return nullptr;
 }
 Item* Next(cu32 type) noexcept { 
 while (idx < count) { 
 Item* item = items[idx++];
 if (type == (u32)it->type) { return item; }
 } 
 idx = 0;
 return nP;
 }
 void Update(const bool updateFrame, Box2* bounds) noexcept {
 sZ head = 0, tail = 0;
 while (head < count) {
 Item* item = items[head];
 if (item->Update(updateFrame, bounds)) {
 if (tail != head) {
 items[head] = items[tail];
 items[tail] = item;
 }
 tail++;
 }
 head++;
 }
 idx = 0;
 count = tail;
 }
 void Update() noexcept {
 sZ head = 0, tail = 0;
 while (head < count) {
 Item* item = items[head];
 if (item->Update()) {
 if (tail != head) {
 items[head] = items[tail];
 items[tail] = item;
 }
 tail++;
 }
 head++;
 }
 idx = 0;
 count = tail;
 }
private: 
 sZ idx{0};
public: 
 std::vector<Item *>items;
 sZ count{0};
 bool dirty{false}; 
};

Basic usage example.

/* 
 FXParticle lives for 10 - 100 frames
 With odds 1 in 10 of creating a new particle each frame.
 UpdateAndRender creates, updates, and draws particles.
 */
SpriteBuffer<spriteRenderer, spriteSheet> spriteBuf;
struct FXParticle {
 Vec2 position{0, 0};
 Vec2 delta{0, 0};
 u32 idx{0};
 i32 life{100};
 FXParticle* Init() noexcept {
 position.Set(Vec2::Rnd(200.0f, 200.0f)).Sub(100.0f, 100.0f);
 delta.Polar(Rnd(TAU), Rnd(1.0f, 2.0f));
 life = RndU(10, 100);
 return this;
 }
 bool Update() noexcept {
 position += delta;
 return life-- > 0;
 }
 void Render(SpriteBuffer<spriteRenderer, spriteSheet>* sB) noexcept {
 sB->DrawSprite(position, idx);
 }
};
BubbleList<FXParticle> fx;
void AddParticle(cu32 idx) noexcept {
 FXParticle* p = fx.Spawn().Init();
 p->idx = idx % 10;
}
void UpdateAndRender() { /* Would normally be two functions to handle many types of objects */
 if (ROdds(10)) { AddParticle(RndU(10)); }
 fx.Update(); 
 
 spriteBuf.Use();
 FXParticle* p = fx.Next();
 while (p) {
 p->Render(&spriteBuf);
 p = fx.Next();
 }
 // Or as most often used
 // sZ i = 0;
 // while (i < fx.count) {
 // fx.items[i++]->Render(&spriteBuf);
 // }
 spriteBuf.Flush();
 spriteBuf.Close();
}

As would be used to update and render particle FX via a main loop.

• J_H: This submission is about performance. It does not contain any timing measurements or descriptions of profiling hotspots. It does not use narrative or code snippets to contrast competing design decisions. There are no answers yet, so there is still time to revise this submission.
• greybeard: It's a pity the return value of item->Update() goes undocumented as well as unexplained; seems to be keep item.
• greybeard: (I rearranged Update() to not compare head and tail. GCC 13.2 compiles both to the exact same code. I can see count doesn't change unless Update() returns false at least once in one variant more easily than in the other.)

Answer 1

Simplify your code

There are various issues with your class. It's not truly generic; it depends on Box2 for example, just to be able to pass some parameter to an item's Update() function. You can avoid this by having the caller pass an arbitrary function to BubbleList::update().

You also could have avoided writing a lot of code by making use of the standard library; in particular, use std::unique_ptr to avoid the manual memory management, and use std::partition() to loop over the items in the list and partition the list into active and inactive items.

Consider this rewritten version of your class:

#include <algorithm>
#include <memory>
#include <functional>
#include <vector>
template <typename Item>
class BubbleList {
public:
 void Clear() {
 items.clear();
 count = 0;
 }
 void Trim() {
 items.resize(count);
 }
 Item* Spawn() {
 if (count == items.size()) {
 items.push_back(std::make_unique<Item>());
 }
 return items[count++].get();
 }
 template<typename Function>
 void Update(Function visitor) {
 auto end = std::partition(items.begin(), items.begin() + count, [&](auto& item) {
 return std::invoke(visitor, *item);
 });
 count = end - items.begin();
 }
private:
 std::vector<std::unique_ptr<Item>> items;
 std::size_t count;
};

Update() looks a bit complicated, but by writing it this way and using std::invoke() to call the visitor you give it, it can now take all kinds of invocable objects, including pointers to member functions. That allows you to use it like so:

BubbleList<FXParticle> fx;
...
fx.Update(&FXParticle::Update);

Now BubbList's Update() function doesn't need to know about FXParticle's Update(). You can also pass it a lambda function:

fx.Update([](FXParticle& particle){ particle.Update(); });

This is a bit longer to write, but it allows you to call any function you want, and maybe pass extra parameters as well, without BubbleList having to know about them.

All of the above shouldn't change the performance; it's doing the same thing as your code was doing. Since the class is a template, calls to its member functions can always be inlined, so even though it seems like passing a visitor function to BubbleList::Update() might be slow, the compiler will be able to optimize that away.

Performance

Depending on the size of the Items and how many items are made inactive in calls to Update(), you might want to consider storing the items in the vector by value. This avoids the overhead of all the invididual memory allocations, and the indirection when accessing them. If swapping deactived items to the tail is very expensive, you can also consider just keeping track of which items are active and which are not in a separate data structure (maybe a std::vector<bool>?), so you never have to move items around.

• Blindman67: Sadly std::remove_if illustrates the non obvious behaviour of some algorithms. Elements are not "removed", but moved. Even a tertiary reading (my lazy fault) of documentation does not make this obvious.
• G. Sliepen: I agree that std::remove_if() is badly named. And there's already std::partition(), which kind of does the same thing, maybe that would be a better choice. It even avoids having to negate the predicate.