Not actually lock-free

[Diggsey]

This crate is now used in rustc as of rust-lang/rust#108300

However, it seems to be making some misleading claims about the LockFreeFrozenVec:

The spinlocks are really rare as they only happen on reallocation due to a push going over the capacity.

However, when looking at the source code it appears to take the lock on every push:

elsa/src/sync.rs

Line 371 in ea7576f

self.lock(|ptr| {

And it also takes the lock on reads as well!

[Manishearth]

https://github.com/Manishearth/elsa/blob/ea7576fe1603acac877b7622ef8c7920c46e2332/src/sync.rs#LL294C18-L294C18

It explicitly says that it will rarely spinlock.

It does take the lock on every push, but the critical section is small.

@oli-obk wrote this for the needs of rustc and considered it sufficiently lock-free enough to work for that use case. I do agree the name is misleading, it's really more of an RwLock<Vec>.

I feel like it could be made lock free except in the double-push case? You just have to update the reallocated pointer first.

[Diggsey]

it's really more of an RwLock.

Well, strictly speaking it's equivalent to a Mutex<Vec<_>>. It's replacing an RwLock<Vec<_>> in rustc, so I'm wondering if the performance improvement is just from the overhead of an RwLock compared to a spin-lock-based Mutex... Given that, it seems like it would make more sense to just wrap the original Vec in a parking_lot::Mutex instead...

But yeah it should be possible to make this mostly lock-free.

[Diggsey]

@Manishearth I made a version which trades off some space in exchange for being not just lock-free, but wait-free as well:

https://gist.github.com/Diggsey/c6a6ac87cf6516b05b5aaee183048177

[Manishearth]

@oli-obk do you want to review that code first^ ?

[Diggsey]

(To be clear, this is not necessarily faster for the specific use-case in the compiler, but it does prove that it's possible to avoid locking here)

[oli-obk]

• https://gist.github.com/Diggsey/c6a6ac87cf6516b05b5aaee183048177#file-lock_free_append_only_vec-rs-L41
  • should probably make it a const generic, as having the LockFreeAppendOnlyVec take ptr_size^2 bytes is probably overkill for almost all use cases.
• the double indirection is probably a no-go for our use case. We mostly store u32s or wrappers around that
  • could probably avoid that by storing an Option instead of a pointer

I had considered a similar design: Basically only have a single pointer for the backing memory and then doing the allocation and replace dance you're doing, but with copying the entire array first

[Diggsey]

should probably make it a const generic, as having the LockFreeAppendOnlyVec take ptr_size^2 bytes is probably overkill for almost all use cases.

Yeah, if you know the max size then you can certainly save some space this way.

could probably avoid that by storing an Option instead of a pointer

Yeah, it can work for any NonZero<T> where sizeof(T) <= ptr_size. You could extend it further if necessary to any type by storing a separate bit-array for "value presence", but it does add complexity.

I had considered a similar design: Basically only have a single pointer for the backing memory and then doing the allocation and replace dance you're doing, but with copying the entire array first

The problem with any approach where you resize the array is that you need readers to at least take a read-lock, at which point there shouldn't be much benefit over just using an RwLock<Vec<T>> - unless you mean that you keep around the original array as well, making copies of all the elements, and chaining those buffers together in a linked list? I think that approach could potentially work.

Out of interest, did you try benchmarking parking_lot::RwLock<Vec<T>> instead of the std RwLock<Vec<T>> before looking for a lock-free solution?

Or was the performance issue from the double indirection rather than the lock contention?

[oli-obk]

It must be from the lock, as we went from a Vec to a RwLock<Vec> without any other changes effectively.

But I should rebenchmark, as there were quite a few changes that happened since then to simplify things