Bug 255798

rdar://108377867

Currently, the JSC allocator has two modes:

1. When a block is known to be empty, like when it's initially allocated or if it's totally empty on sweep, we allocate by bumping a counter of the remaining bytes.

2. Otherwise, when a block is only partially empty, we install a free list through every dead cell and pop from that to allocate.

The hypothesis underpinning this is that bump allocations are faster than free list ones, and one of the major reasons for this overall is that avoiding installing a free list when sweeping saves us a lot of work installing the list into swept blocks. However, looking at some benchmarks, it looks like the amount we bump-allocate is highly program-dependent, and can sometimes be the minority of all allocations.

To try and improve this, we can replace free lists (which require one node per allocatable cell) with bumpable ranges of addresses. We construct linked lists of ranges for partially-full blocks, with one range per contiguous run of dead cells. Within each range, we can bump-allocate, and only when the range is exhausted do we follow the link to the next free interval. The hope is this doesn't incur much if any additional overhead relative to the status quo, but for cases where lots of objects die close together, we spend less time installing free lists and do more bump allocations.