Use atomic operations for allocating objects, and remove bucket wide locking
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 theOption
returned byimmix::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
- Start a loop
- 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 - If no block was found, request a new one atomically, then restart the loop
- If a block was found, attempt to bump allocate into it
- If None is returned, restart
- If Some is returned, return the wrapped object pointer
Potential problems:
- 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) - 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: threadA
andB
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. - 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