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 (see 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 – GetAt(index):
  • free-flag nullity of byte-map[index] is verified:
    • If true, object-list[index] is returned;
    • If false, a null-pointer is returned.
• On slot lookup – GetAtHandle(handle):
  • index is extracted from handle by index = handle >> 8 and byte-map[index] is compared to the lower 8 bits of handle:
    • If equal, object-list[index] is returned;
    • If different, a null-pointer is returned.
• On slot just-index retrieval – GetJustIndex(object):
  • slot-id is returned by slot_id = (object - object_list) / sizeof(object).
• On slot index retrieval – GetIndex(object):
  • slot-id is computed as above and handle is returned by handle = (slot_id << 8) | byte_map[slot_id].
• On free-slot request – New():
  • 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 null-pointer returned.
• On slot reservation – New(handle):
  • index is extracted from handle (see above) while free-flag and seed of byte-map[index] are respectively unset and advanced (overflow solved as mentioned);
  • first-free is then set to index of first byte-map[index] with free-flag unset.
• On slot removal – Delete(object):
  • slot-id is obtained as above while free-flag of byte-map[slot-id] is set;
  • If index is less 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 till 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.