Draft: Link free blocks within a NonmovingSegment
Just to try out an idea.
Currently, nonmovingAllocate searches for free blocks within a NonmovingSegment which might cause some churn for partially filled segments.
We now chain free blocks when sweeping a NonmovingSegment. This allows determining the next free block using a single lookup. nonmovingAllocate now works like this:
block = getBlock(segment->next_free)
segment->next_free += 1
- if
segment->next_free
points to a free block, return - else
segment->next_free = (struct VacantBlock*)block->next_free
;
Note that we only access the stored link in case the next_free + 1
is not a free block which allows us to avoid accessing the link for fresh NonmovingSegment's. It is actually unsafe to access the link in that case as blocks are only being linked during sweeping.
Let's see what people say, maybe this turns out to be too hacky and I have not benchmarked it yet. @bgamari what are you using to benchmark such changes?