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.
immix::bucket::Bucketso it uses the
immix::block::Block::bump_allocateto determine if a hole is in use or not
- Verify changes using a (synthetic) benchmark
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
Block::request_pointerneeds 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
- Start a loop
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
- The code used for finding holes is not thread-safe, e.g. the
end_pointeris 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: thread
Bboth 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.