Skip to content

Draft: Link free blocks within a NonmovingSegment

alexbiehl-gc requested to merge alexbiehl/ghc:alex/link-blocks into master

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:

  1. block = getBlock(segment->next_free)
  2. segment->next_free += 1
  3. if segment->next_free points to a free block, return
  4. 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?

Edited by alexbiehl-gc

Merge request reports