libs/bitarray: Use []uint32 instead of []uint64 for the bits

[ValarDragon]

Currently we use []uint64 to store the bits of the bit array. Instead we should use []byte, for spatial efficiency. (Plus using []byte for bit arrays is standard)

With an []uint64 the number of elements in the list will be 8 times less than the number of elements in a list of []byte. This means that the prefix when amino encoded will require 3 less bits. (Perhaps 4 less bits, due to uint prefixing).

However if we wanted a random number of bits, we would expect on average that we would only need half of the last element to store it. So with an []uint64, this means that the last element uses 64 bits to specify what we could with 32 bits. Or in other words, we are wasting 4 bytes on average. With an []byte we are using a single byte to represent 4 bits, which means we are wasting 4 bits on average here.

This means that if we used []byte in encoding, we would save 3 bytes on average relative to the []uint64 case. Thus we should change the bit array to use []byte instead of []uint64.

• Note, I am assuming that there is no per-element bytes added for every element of the slice. I vaguely recall that such a thing may exist due to protobuf3 compatibility. If this is the case, we should keep on doing what we are doing, and just write this reasoning in the godoc or in an ADR.

[ValarDragon]

Talked to Jae a bit about this. He made the point that arithmetic operations using []uint64's are significantly faster than []byte, due to the processor being able to perform arithmetic 64 bits at a time, as opposed to 8. I do agree, and I don't think the spatial efficiency gains here (an additive constant) is worth the loss of a multiplicative factor for processing time gains.

He did suggest that we consider using uint32 instead of uint64 for better javascript compatibility. (Javascript doesn't have a 64 bit object, so uint64s are big ints) He had suggested this as something we relook at soon before launch if we have time.

[melekes]

Java does not have uint64 too.

[ebuchman]

As far as I can tell, the arithmetic ops (Or, And, Not, Sub) are only being used in the consensus reactor for tracking peer state (ie. how many and which votes and block parts peers have), and are not used in any essential way in marshalable form (ie over RPC, we show the bitarray string like __xx_xxx__), so it shouldn't be an issue for javascript. Please correct me if I'm wrong.

We are starting to use bitarrays for crypto though and for those we should use the more efficient form with bytes since we're not trying to do math. This includes multisig and the invalid txs bit array we want to put in the header.

[creachadair]

@ValarDragon Is this issue still relevant? The existing uses in the consensus engine are for "small" vectors, where space won't matter. Arguably anything that has more specific constraints should probably use its own bit vector implementation rather than depending on the TM one.

There's at least one generated file in the Cosmos SDK that still cares about the protobuf representation of this file, but I don't see any meaningful use of it in a cursory GitHub search. Would anything be meaningfully impacted if we made this package internal?

[ValarDragon]

Agreed, I don't think this really matters either. Theres other places to get much larger space savings