Object pool

From GTAMods Wiki
Jump to navigation Jump to 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 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