Object pool

From GTAModding
Jump to: navigation, search

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