Skip to content

Use atomic operations for allocating objects, and remove bucket wide locking

Yorick Peterse requested to merge atomic-bump-allocation into master

This changes the bump allocation mechanism to use atomic operations. This in turn allows for multiple threads to allocate memory concurrently, without having to use a bucket-wide lock.

TODO

  • Change immix::bucket::Bucket so it uses the Option returned by immix::block::Block::bump_allocate to determine if a hole is in use or not
  • Verify changes using a (synthetic) benchmark
  • Make immix::block_list::BlockList::push_back() atomic, allowing multiple threads to add blocks to a bucket concurrently
  • Remove bucket wide locking
  • Verify if finding holes in buckets is still safe to use with atomic operations
  • Verify if Block::request_pointer needs to use atomic loads for getting the free pointer, somehow.
  • Try to get rid of the locking in Bucket::allocate(), in favour of some sort of atomic operation

Rough idea

  1. Start a loop
  2. In Bucket::allocate(), find the first block (relative to the current one) that is not full or fragmented, but don't compare the free/end pointers just yet
  3. If no block was found, request a new one atomically, then restart the loop
  4. If a block was found, attempt to bump allocate into it
  5. If None is returned, restart
  6. If Some is returned, return the wrapped object pointer

Potential problems:

  1. The code used for finding holes is not thread-safe, e.g. the end_pointer is set at some point without locking/atomic operations. Atomic operations would probably make this safe, though multiple threads might end up doing the exact same work, which seems a bit wasteful (and might actually be slower than just waiting for another thread to finish)
  2. When using atomic operations for requesting blocks, multiple threads may request a block and attempt to store it in Bucket::current_block, even when just a single block would suffice. Example: thread A and B both can't find a hole, request a new block (atomically, without locking), then attempt to add it to the list. We now have two blocks, even though one would fit. Worse, all but the last block would be ignored.
  3. Considering requesting blocks is pretty fast, we might as well just lock the bucket while doing this. This will make requesting blocks a bit more expensive though.
Edited by Yorick Peterse

Merge request reports