Runtime: BigInteger should have a less strictly typed constructor

[bazzilic]

BigInteger should have a public BigInteger(IList<byte>) constructor instead of the existing public BigInteger(Byte[]) constructor.

Rationale

First, asking for an interface instead of a specific type seems more in line with the ideology of the language. Second, there are situations when this would have been more convenient.

As an example, we are implementing some public key cryptosystems and use big integers internally. Many PK cryptosystems (example) produce ciphertexts that are actually a pair of big integers, which are stored as a single concatenated byte array; e.g., a byte[96] stores two big integers, 48 bytes long each. Reconstructing these would require an extra step of copying first and second halves of the array into individual arrays — an expensive operation.

These add up when we are processing large data sets. Especially, considering that modern PK cryptosystems often work with ciphertexts 256 or 512 bytes long. Instead, if there was an IList<byte> constructor, we could have used ArraySegment<byte> and skip an unnecessary array copying.

Details

BigInteger from System.Numerics could be "serialized" to a byte array using .ToByteArray() method, and "deserialized" from a byte array using one of the constructors.

However, currently, it only has a constructor that takes byte[]. Since the constructor (according to the reference source) actually only uses .Length property and indexed access, it would have been enough to require IList<byte> as an argument.

The proposal is to replace an existing constructor with public BigInteger(IList<byte>). Since byte[] implements IList<byte>, I don't see any compatibility issues that could arise from that change. As I understand, just adding it to the list of constructors would create ambiguity, but I didn't verify that.

Hopefully, this could also be backported to the .NET Framework.

[svick]

Is ArraySegment<byte> actually the only type you're interested in? In that case, adding a Span<byte> overload might be a better choice than IList<byte>, since you can easily convert ArraySegment<byte> to Span<byte> (and especially considering it would be more efficient). In that case, this would become part of https://github.com/dotnet/corefx/issues/13892.

The proposal is to replace an existing constructor with public BigInteger(IList<byte>). Since byte[] implements IList<byte>, I don't see any compatibility issues that could arise from that change. As I understand, just adding it to the list of constructors would create ambiguity, but I didn't verify that.

It's the other way around: adding an IList<byte> overload would be fine (if you pass in byte[], the byte[] overload is more specific, so there is no ambiguity), but replacing it would be a binary breaking change (i.e. it would break code that's run against the updated version without being recompiled and also things like reflection).

[mellinoe]

Alternatively, we could consider just adding adding another byte[] overload, with additional startIndex and count parameters. I don't know how often we use ArraySegment as an exchange type; using "array-start-length" seems to be a more common pattern.

[mellinoe]

Hopefully, this could also be backported to the .NET Framework.

For an addition like this, that shouldn't be a problem. But keep in mind: it will take a lot longer for us to ship the addition in .NET Framework than it will for us to ship it in .NET Core.

[bazzilic]

@svick : Am I right in understanding that Span<> is only available in .NET Core? Then this feature won't be portable back to the .NET Framework.

@mellinoe : Yes, the framework seems to be leaning towards the array-offset-count paradigm but I feel that this is not how it is supposed to be. We have classes that take care of array slicing, such as Span and ArraySegment; we have interfaces that unite various implementations under same APIs, such as ICollection, IEnumerable and IList. Shouldn't we leverage this instead of reimplementing it in every API?

[svick]

@bazzilic I believe there are plans to bring Span<T> to .Net Framework too, so that shouldn't be a problem.

[bazzilic]

Apparently, Span<T> is already available in .NET Framework through a NuGet package.

According to the source, Span<T> doesn't implement any interfaces, so we could have two additional constructors for BigInteger:

public BigInteger(Span<byte>)
public BigInteger(IList<byte>)

Efficient construction of BigInteger requires random access to the collection of bytes, so adding IEnumerable or ICollection constructors as well doesn't look necessary.

[svick]

@bazzilic If the Span<byte> constructor is added, what is the point of also adding one for IList<byte>? You're generally not going to be using something like List<byte> to store a sequence of bytes, so I think Span<byte> should cover all the common use cases (including ArraySegment<byte> though AsSpan()).

[bazzilic]

I believe that in this case the more appropriate question is - why should we _not_ implement the IList<byte> constructor? Whenever possible, especially if this does not incur performance drops, we should go for higher abstractions; and in case of BigInteger I see the use of byte[] instead of (at least) IList<byte> as a design oversight

Generally, Span and IList are not interchangeable, as Span requires that there is an actual continuous array underneath somewhere, and IList doesn't.

I can imagine mathematical applications when people use data structures that expose IList interface and not necessarily have an array internally. Implementing AsSpan extension for such data structures would be expensive as it would actually require copying the array. An example (not directly related to BigInteger but still): a class Matrix that holds a mathematical matrix (stored in a one- or two-dimensional array) and a class MainMatrixDiagonal : IList that provides access to the main diagonal of the matrix without copying the values into a new array. There are applications that require enormous matrices, where this would make sense.

[svick]

especially if this does not incur performance drops

Except that's not true. Using IList<byte> requires a virtual call for every single byte, which will likely affect performance significantly here.

But OK, I understand your point of view (even if I disagree with it).

[bazzilic]

I didn't think of that. I ran a quick test (https://gist.github.com/bazzilic/8b0d8f753031b3fcb4ece17a3fcb89bd) and IList<byte> appears to be 5-6 times slower than byte[]. In this case, it makes perfect sense to keep a more specific constructor for byte[] since it's faster.

It still makes sense to me to have the IList<byte> constructor for situations that _could_ arise.

[stephentoub]

I've included the Span<byte> ctor in dotnet/corefx#21281

[tannergooding]

Going to close this as it hasn't garnered much attention and the primary scenario should be covered by the constructor overloads that take a Span<byte>.

If someone feels strongly about this, please feel free to open a new issue. Our API review process is detailed here with a "good example" being listed under step 1. Ideally the new issue would provide many of the sections given, but would at a minimum provide the base rationale and proposed API surface sections.

[bazzilic]

As I understand, neither Core nor .Net Framework support the Span<byte> constructor as of now, though?

[tannergooding]

It has existed since .NET Core 2.1: https://apisof.net/catalog/System.Numerics.BigInteger..ctor(ReadOnlySpan%3CByte%3E,Boolean,Boolean)

[tannergooding]

.NET Framework is not getting any new APIs as per https://devblogs.microsoft.com/dotnet/net-core-is-the-future-of-net