Object pool
The object pool is a design pattern capable of reducing the allocation/deallocation overhead by reusing pre-instanced resources on demand and restricting their simultaneous usage at a given time. It is heavily employed when the bottleneck induced by the frequent creations/destructions of objects is a concern.
Practical implementation
In trilogy chapters, pools come with (note numerical fields are all 32-bit signed integers):
object_list
, an array of variable-sized slots of same type;byte_map
, an array of slot states each of which holds aseed
(in the lower 7 bits) to randomize handles (also known as references) by a conspicuous factor and afree_flag
(in the sign-bit, 8th bit) to signal the emptiness of the slot itself;count
, the number of slots;first_free
, a hint where to look from for free slot searching;initialized_state
, a flag indicating if arrays were allocated.
Pools are commonly implemented in the following way:
- On pool initialization –
Initialise(count)
:object_list
andbyte_map
are allocated with a fixed number of slots;count
is set accordingly whilefirst_free
becomes-1
;initialized_state
is switched to true andbyte_map
is cleared as below.
- On pool clean up –
Clear()
:- For each slot of
byte_map
,seed
is zeroed whilefree_flag
is set.
- For each slot of
- On pool shutdown –
Flush()
:- If
count
isn't equal to 0:- If
initialized_state
is true,object_list
andbyte_map
are deallocated and zeroed (null-pointer check involved); count
andfirst_free
are zeroed.
- If
- If
- On slot lookup –
GetSlot(index) -> object
:free_flag
nullity ofbyte_map[index]
is verified:- If true, the reference of
object_list[index]
is returned; - If false, a null-pointer is returned.
- If true, the reference of
- On slot lookup –
GetAt(handle) -> object
:index
is extracted fromhandle
byindex = handle >> 8
andbyte_map[index]
is compared to the lower 8 bits ofhandle
:- If equal, the reference of
object_list[index]
is returned; - If different, a null-pointer is returned.
- If equal, the reference of
- On slot index retrieval –
GetJustIndex(object) -> index
:index
is returned byindex = (object - object_list) / sizeof(object)
.
- On slot reference index retrieval –
GetIndex(object) -> handle
:index
is computed as above andhandle
is returned byhandle = (index << 8) | byte_map[index]
.
- On free slot request –
New() -> object
:- Inside loop:
first_free
is incremented at each iteration;- If
count
is reached,first_free
is zeroed and the loop continues below, till the top one more time again (pretty odd, stopping at initialfirst_free + 1
would have made more sense); free_flag
ofbyte_map[first_free]
is verified:- If true,
free_flag
is unset whileseed
is advanced (overflow is solved byseed = (seed + 1) % 128
) and the reference ofobject_list[first_free]
is returned; - If false, the loop continues to the next iteration.
- If true,
- Outside loop:
- No free slot was found, hence a null-pointer is returned.
- Inside loop:
- On slot reservation –
New(handle) -> object
:index
is extracted fromhandle
whilefree_flag
andseed
ofbyte_map[index]
are respectively unset and advanced (overflow solved as aforementioned);first_free
is then zeroed and incremented tillbyte_map[first_free]
withfree_flag
unset;- Lastly, the reference of
object_list[first_free]
is returned.
- On slot removal –
Delete(object)
:index
is extracted fromobject
whilefree_flag
ofbyte_map[index]
is set;- If
index
is lesser thanfirst_free
, the latter is updated.
Handle uniqueness
The probability to encounter an object with a non-unique handle after an undefined amount of new/delete requests is given by cost = 1 / ((free_slot_count * 128) + busy_slot_count)
.
In the worst case (assuming the last reserved object of a full pool is repeatedly released/re-added), it is cost = 1 / (128 + (object_count - 1))
.
In the best case (assuming an empty pool is filled up to the maximum with no release), it is cost = 1 / (object_count * 128)
.
See also
- GTAForums: [TUT|DOC] SCM functions (including TraversePoolEntities algorithms) – Multi-purpose tutorial also showing a scripted implementation of pool traversal to catch any type of entity by handle.