Concurrent read/write support

[skiwi2]

Hello, I've been using BitVec for both a single-threaded and a multi-threaded version of the Sieve of Eratosthenes algorithm. Please note that I'm a beginner in the Rust language, so I might be doing things wrong.

In the documentation I haven't found anything indicating that this structure supports concurrent access and putting it in an Arc<Mutex<BitVec>> seems like a terrible idea when using multiple threads for computations as then it is effectively the same or worse than using a single thread.

Have I missed a part of the documentation where it says that concurrency is supported?
If not, are there plans to support concurrency?

To me it would seem most logical to put the BitBlock under a Mutex<BitBlock>, but that is just my beginner's view on this matter. On the other hand I could also hand out slices of the full vector to each thread and in that case I wouldn't even need a mutex conceptually to access the values safely, not sure how this is done in Rust though.

[pczarn]

Traditionally one would make an alternative implementation by the name ConcurrentBitVec. It's better to fork our code, especially given that concurrency is not the only tweakable aspect of storage, with other possible tweaks such as fixed length arrays, small-vec optimizations, etc.

One option is to have AtomicU32 as bit block. Then, with CAS loops, you may operate on individual bits.

Another option is to put a Mutex once every N bit blocks, possibly using parking_lot. You should take false sharing into consideration, so, most likely you would end up with one Mutex per 56 or 60 or 63 bytes (entire cache line minus a machine word or a byte).

I don't know enough about concurrency to describe what kind of tradeoffs are between these options.