MutBits class as a mutable Bits?

[scott-griffiths]

Motivation

I was hoping to not have a mutable bits at all (or perhaps only much later) as there are numerous advantages to the immutable class. However, after having done some speed tests I think it's going to be needed sooner.

The task I've profiled is the classic prime sieve for the first 100 million integers. There is example code for this on bitarray's site, so that's a good baseline. I can also compare to bitstring:

• bitarray (mutable) ~ 4s
• bitstring (mutable) ~ 5s
• bitformat (immutable) ~ 150s

This is clearly problematic!

I then compared it to a naive pure Rust implementation (using the bitvec crate) both with an immutable bitvec and one that gets mutated:

• rust (immutable) ~ 150s
• rust (mutable) ~ 4s

The immutable Rust code just has an extra clone() in the loop, but it's taking 95% of the time. This does suggest that using a mutable bits in bitformat could be 30x faster for this task, and quite possibly faster than other optimised libraries.

---

Things to think about:

Name:

I'm quite tempted to call it MutBits, which may be a bit too Rust-like, but the Pythonic name would be BitArray and I feel that name has been overloaded too much elsewhere already. MutBits also has a name that strongly suggests its difference to Bits, whereas BitArray isn't as clear.

Methods:

There are already a bunch of mutating methods on Bits, except of course the don't actually mutate it but just return a new instance instead. I don't want to remove these methods, so I think they just get reimplemented with MutBits. One question is whether MutBits should return None or self - the first makes it clear that it's mutating, but the second means that Bits code can be trivially changed to MutBits. There are probably lots of subtle and not so subtle bugs that could be introduced by mimicing the Bits API here so it might be best to return None at least in the first iteration?

we'd need:

• byte_swap
• insert
• invert
• overwrite
• replace
• reverse
• rol
• ror
• set

• This would also mean that the BitsProxy class wouldn't be needed at all as it could be replaced by MutBits.
• Should the Reader class use the MutBits and add some extra methods?

[scott-griffiths]

After some more thought and experimentation:

• Looking at MutableBits as the class name.
• It might be clearest to move all mutating methods over to MutableBits, rather than having Bits return a new instance for them.
• Conversion between classes with to_mutable() and freeze() methods (copying Rust again here).

This means that the methods in the list above would move out of Bits and only exist in MutableBits. If they are tried on Bits then a special AttributeError could explain the situation.

>>> a = Bits('0x123')
>>> a = a.set(0, [-1])
AttributeError: No method 'set' on 'Bits' class. This method is available for 'MutableBits' - perhaps use '.to_mutable().set(...)' instead of '.set(...)'.

Things would be chainable, allowing code like s = MutableBits.from_zeros(1000).set(1, [100]).ror(55).byte_swap()

• Should we add append and prepend methods? Probably, yes, as they would go very naturally in a chain.
• Perhaps add to_mutable and freeze to Reader class to change the underlying storage used?
• Also need to add __setitem__ and __delitem__ for MutableBits.