Adopt Size-Based Range Allocator

[lightsighter]

There is a new size-based range allocator available in Realm as part of this merge request. However, it still needs to be evaluated. There are three questions that need answering:

1. Does the new allocator add measurable overhead to programs and if so how much?
2. Does the new allocator improve fragmentation for real Realm programs?
3. The new allocator provides both sorted and unsorted free lists. Sorted free lists guarantee the smallest hole always is used to satisfy an allocation, whereas the unsorted lists provide a looser bound guaranteeing only that a hole that is found is no more than 2X as large as the requested allocation. Is it better to have the sorted or unsorted versions of the size-based range allocator?

Assigning to @apryakhin to investigate. @manopapad can you triage this and place it on the priority list for Realm work as you deem appropriate?

[lightsighter]

Forgot to add that all you need to do to swap the kind of range allocator is toggle the comments on these lines:
https://gitlab.com/StanfordLegion/legion/-/blob/master/realm/src/realm/mem_impl.h?ref_type=heads#L401-403

[manopapad]

TBH I thought this was always the case, i.e. Realm's allocator always picked the smallest hole

[lightsighter]

Very much no. 😅 The current BasicRangeAllocator maintains a single free list of holes. The list is ordered by whatever order holes are made (new holes are prepended to the list). When Realm needs to do an allocation, the BasicRangeAllocator goes through the list from front to back and it greedily selects the first hole that it finds that satisfies an allocation, regardless of how well it fits. Holes that are multiple GBs could be used to satisfy very tiny single byte allocations. Now when that happens, the remainder of the hole remains in the list, but it means that that big hole was just made a tiny bit smaller so it could no longer be reused for another allocation of the same size. It would be better if the the allocator tried to find the smallest possible hole to satisfy an allocation request.

The SizedRangeAllocator does this by maintaining lists of holes sorted by powers of 2s. This shortens the search to finding an appropriate sized hole. If you keep the lists sorted, then the SizedRangeAllocator guarantees that you will also pick the smallest possible hole that is available to satisfy an allocation. If you keep the power of 2 lists unsorted, then the allocator will use the first hole it finds in the given list that works, which is guaranteed to be no worse than 2X as large as the size of the allocation you've requested (or the smallest possible hole that satisfies your allocation request).

[manopapad]

@apryakhin here is an early candidate to test this on: nv-legate/legate#985