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 a seed (in the lower 7 bits) to randomize handles (also known as references) by a conspicuous factor and a free_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 and byte_map are allocated with a fixed number of slots;
  • count is set accordingly while first_free becomes -1;
  • initialized_state is switched to true and byte_map is cleared as below.
• On pool clean up – Clear():
  • For each slot of byte_map, seed is zeroed while free_flag is set.
• On pool shutdown – Flush():
  • If count isn't equal to 0:
    • If initialized_state is true, object_list and byte_map are deallocated and zeroed (null-pointer check involved);
    • count and first_free are zeroed.
• On slot lookup – GetSlot(index) -> object:
  • free_flag nullity of byte_map[index] is verified:
    • If true, the reference of object_list[index] is returned;
    • If false, a null-pointer is returned.
• On slot lookup – GetAt(handle) -> object:
  • index is extracted from handle by index = handle >> 8 and byte_map[index] is compared to the lower 8 bits of handle:
    • If equal, the reference of object_list[index] is returned;
    • If different, a null-pointer is returned.
• On slot index retrieval – GetJustIndex(object) -> index:
  • index is returned by index = (object - object_list) / sizeof(object).
• On slot reference index retrieval – GetIndex(object) -> handle:
  • index is computed as above and handle is returned by handle = (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 initial first_free + 1 would have made more sense);
    • free_flag of byte_map[first_free] is verified:
      • If true, free_flag is unset while seed is advanced (overflow is solved by seed = (seed + 1) % 128) and the reference of object_list[first_free] is returned;
      • If false, the loop continues to the next iteration.
  • Outside loop:
    • No free slot was found, hence a null-pointer is returned.
• On slot reservation – New(handle) -> object:
  • index is extracted from handle while free_flag and seed of byte_map[index] are respectively unset and advanced (overflow solved as aforementioned);
  • first_free is then zeroed and incremented till byte_map[first_free] with free_flag unset;
  • Lastly, the reference of object_list[first_free] is returned.
• On slot removal – Delete(object):
  • index is extracted from object while free_flag of byte_map[index] is set;
  • If index is lesser than first_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.