[API Proposal]: BitArray.AsBytes()

[stephentoub]

Background and motivation

In order to do custom, high-performance comparisons on the bits in a BitArray, I would like to be able to get a span to the data. This then enables that span to be used in operations like those on TensorPrimitives.

API Proposal

namespace System.Collections;

public class BitArray
{
+   public ReadOnlySpan<byte> AsBytes();
}

API Usage

BitArray array1 = ..., array2 = ...;
int distance = TensorPrimitives.HammingBitDistance(array1.AsBytes(), array2.AsBytes());

Alternative Designs

No response

Risks

The BitArray length isn't necessarily divisible by 8. For cases where it isn't, a consumer might need to mask off bits in the final byte, depending on the operation being performed. We would make this very clear in the docs for the method.

BitArray also exposes a settable Length, which could result in a new array being allocated. In that case, the span would be referencing an array that's no longer used by the BitArray. If that's deemed an issue, we could put the API onto CollectionsMarshal instead, moving BitArray down into corelib.

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

[tannergooding]

The premise seems reasonable, but I'd like to call out an implication here.

Namely, we have BitArray.CopyTo(Array array, int index) today which supports array being bool[], byte[], or int[]

For CopyTo, we have logic to ensure the backing storage is exposed to any array such that the bits remain ordered correctly. That is, for bool[] then index 0 represents bit 0, index 1 represents bit 1. For int[] then index 0 represents bits 0-31 where bit 0 of index 0 represents bit 0 of the collection. Likewise for byte[] then index 0 represents bits 0-7 where bit 0 of index 0 represents bit 0 of the collection, and so on.

Now the backing storage is currently int[], although this is an implementation detail and we are free to change it to another type, such as uint[] or nuint[] for additional performance if desired. Likewise, As*() methods are generally named because they imply a zero or near zero cost.

So in order for this to work, we'd need to update the implementation to ensure that the backing storage is always in little-endian format and have paths for big-endian machines to do reverse indexing of the bits stored in said buffer.

I think this is probably fine, especially given big-endian shouldn't be common, but it does impact things a bit.

BitArray also exposes a settable Length, which could result in a new array being allocated. In that case, the span would be referencing an array that's no longer used by the BitArray. If that's deemed an issue, we could put the API onto CollectionsMarshal instead, moving BitArray down into corelib.

I'd speculate that we'd want to do this for the same reason we did for List<T> and we'd want this as static Span<byte> CollectionsMarshal.AsBytes<byte>(System.Collections.BitArray? array) -- or maybe named AsSpan to match the List<T> API

The BitArray length isn't necessarily divisible by 8. For cases where it isn't, a consumer might need to mask off bits in the final byte, depending on the operation being performed. We would make this very clear in the docs for the method.

Agreed. But notably we need to determine if this means AsBytes() will slice down to the nearest multiple of 8 or if we simply return the whole backing storage and any bits beyond Count are undefined. -- This may also warrant a SetCount API, like we added for List<T>

[tfenise]

Why not just let it return (ReadOnly)Span<int>, so there won't be any trouble with endianness and the implementation can stay as is?

I don't feel it is very useful, though. If one wants to work with raw bytes, then just create an array of one's own. Why staying using BitArray? It is very easy to write GetBit SetBit helpers on byte arrays. It's not the case with the current CollectionsMarshal collections, List<> and Dictionary<,>, whose core functionalities (IList<>, IDictionary<,>) take much more lines to implement. By working with one's own array, one may also define customized rules around the extra bits in the last byte. If one really wants the best performance with vectorization, one may also want to use AlignedAlloc instead of managed arrays.

Some has also proposed BitArray.Slice() #84907. I don't know what they intend it to be, but if it is intended to behave like Span<>.Slice(), then it would create a BitArray with extra bits at the start of the array, which wouldn't be compatible with BitArray.AsBytes().

[tannergooding]

Why not just let it return (ReadOnly)Span, so there won't be any trouble with endianness and the implementation can stay as is?

This locks in the implementation and doesn't allow us to do things like change the backing implementation to be nuint[] so we get better performance on 64-bit machines without regressing performance on 32-bit machines.

It is very easy to write GetBit SetBit helpers on byte arrays.

Such custom types do not work well for interchange purposes.

By working with one's own array, one may also define customized rules around the extra bits in the last byte. If one really wants the best performance with vectorization, one may also want to use AlignedAlloc instead of managed arrays.

This is unlikely to benefit in common cases. Opportunistically aligning a managed array is cheap and is lost in the general noise of the system for any size of data that would benefit from said alignment.

Some has also proposed BitArray.Slice() #84907. I don't know what they intend it to be, but if it is intended to behave like Span<>.Slice(), then it would create a BitArray with extra bits at the start of the array, which wouldn't be compatible with BitArray.AsBytes().

Such an API would be required to allocate a new byte[] and copy the bytes over. Not all slices strictly produce views, this is the case for types like Span<T> because they are already a view.

[tfenise]

This locks in the implementation and doesn't allow us to do things like change the backing implementation to be nuint[] so we get better performance on 64-bit machines without regressing performance on 32-bit machines.

AsBytes() also locks in the implementation. Why would AsBytes() work if AsInt32s() does not?

Such custom types do not work well for interchange purposes.

General interchanging codes do not need the best performance anyway. It is common to make a copy of a collection argument of a public method to avoid problems if the caller later modifies the collection. If a copy is to be made anyway and they want a byte array, they can just call BitArray.CopyTo().

[tannergooding]

AsBytes() also locks in the implementation.

It does not, it simply locks in the endianness of the underlying storage. It is safe because you are only exposing the bytes, which do not themselves have an endianness

Why would AsBytes() work if AsInt32s() does not?
Because you can cheaply and efficiently guarantee the Span<byte> order is little-endian regardless of whether the storage is byte[], int[], nuint[], UInt128[], etc.

You cannot do the same for Span<int> for something like byte[] or nuint[], because endianness starts to matter when converting to a larger sized type.

General interchanging codes do not need the best performance anyway. It is common to make a copy of a collection argument of a public method to avoid problems if the caller later modifies the collection. If a copy is to be made anyway and they want a byte array, they can just call BitArray.CopyTo().

The API being proposed here is explicitly to allow avoiding unnecessary copying, unnecessary repeated overhead from things like bounds checks, etc. It servers much the same purpose as CollectionMarshal.AsSpan(List<T>)

[tfenise]

Because you can cheaply and efficiently guarantee the Span order is little-endian regardless of whether the storage is byte[], int[], nuint[], UInt128[], etc.

How to get an Span<byte> if the storage is int[] on a big-endian platform?

The API being proposed here is explicitly to allow avoiding unnecessary copying, unnecessary repeated overhead from things like bounds checks, etc. It servers much the same purpose as CollectionMarshal.AsSpan(List<T>)

1. This doesn't eliminate the need for the callee to make a copy if the callee is worried that the caller may modify the collection later.
2. CollectionMarshal.AsSpan(List<T>) returns an Span<T>, so it can be helpful if one wants to call an API that accepts a list-like argument but only (ReadOnly)Span<T> not List<T>. BitArray.AsBytes() would be less useful in this aspect as bridge to or between APIs because relatively rarely an API that accepts a bitarray-like argument accepts (ReadOnly)Span<byte>. BitArray.AsBytes() wouldn't offer the flexibility of item(here bit)-wise slicing that CollectionMarshal.AsSpan(List<T>) offers. The only scenario of BitArray.AsBytes() seems to be when one wants to accelerate some custom operations on BitArray, but then why not just use a byte array of one's own?

To summarize, BitArray.AsBytes() locks in the implementation, but does not seem very useful compared to something like CollectionMarshal.AsSpan(List<T>).

[tannergooding]

How to get an Span if the storage is int[] on a big-endian platform?

The backing storage has the bits written in little endian form and uses reverse indexing. This makes it safe and efficient for AsBytes() and requires a transform as part of CopyTo, which is fine for CopyTo because it is performing a copy operation and the endianness fixup and be done as part of the copy.

This doesn't eliminate the need for the callee to make a copy if the callee is worried that the caller may modify the collection later.

Nothing would eliminate that need, it isn't a consideration for whether an API like AsByte() should be exposed. Something simply having access to the BitArray gives the same risk that it could be modified later.

CollectionMarshal.AsSpan(List) returns an Span, so it can be helpful if one wants to call an API that accepts a list-like argument but only (ReadOnly)Span not List. BitArray.AsBytes() would be less useful in this aspect as bridge to or between APIs because relatively rarely an API that accepts a bitarray-like argument accepts (ReadOnly)Span.

This is one consideration, which equally applies to having a BitArray and wanting to call an API that takes Span<byte> but not BitArray.

BitArray.AsBytes() wouldn't offer the flexibility of item(here bit)-wise slicing that CollectionMarshal.AsSpan(List) offers.

You still get slicing flexibility, just in terms of multiples of 8. If you need to exclude all other bits, then yes a fixup operation may be needed.

The only scenario of BitArray.AsBytes() seems to be when one wants to accelerate some custom operations on BitArray, but then why not just use a byte array of one's own?

This is another scenario, which applies to wanting to extend or customize BitArray itself, which is an existing BCL type that many scenarios explicitly use so they don't need to roll their own logic for the most common cases.

To summarize, BitArray.AsBytes() locks in the implementation, but does not seem very useful compared to something like CollectionMarshal.AsSpan(List).

It doesn't lock in the implementation, it only requires that the backing storage have its bits in little-endian order even on a big-endian machine. That is a trivial thing to handle and doesn't add any unnecessary cost.

It allows and enables the same exact scenarios that CollectionMarshal.AsSpan(List<T>) enables, just enabling them for BitArray instead.