Slicing support for multi-dimensional collections

[eiriktsarpalis]

In #7913 (comment) I proposed adding support for multi-dimensional collection literals. This would be an important addition facilitating usage of the new tensor library that we'll be working on for .NET 9.

One feature request that dovetails with the above is support for multi-dimensional slicing. In pytorch, it is possible to create slices using the following syntax:

tensor[:, 2:, :3, 5:10] # gets a view of the sub-tensor scoped to the specified dimensions

Slices can also be assigned to as the following example illustrates:

tensor[0, :] = torch.ones(3) # fill the first row of tensor with ones

Transcribing the above to C# slicing syntax might look as follows

Tensor<T> tensor = ...;
Tensor<T> view = tensor[.., 2.., ..3, 5..10];
tensor[0, ..] = Tensor<int>.Ones(3);

Sketch Design

A strawman implementation of multi-dimensional slicing on collection types of fixed rank might look as follows

public class Matrix2D<T>
{
    public Matrix2D<T> Get_Slice(Range range1, Range range2);
    public void Set_Slice(Range range1, Range range2, Matrix2D<T> value);
}

Whereas for variable rank types such as tensors it might look as follows:

public class Tensor<T>
{
    public Tensor<T> Get_Slice(ReadOnlySpan<Range> ranges);
    public void Set_Slice(ReadOnlySpan<Range> ranges, Tensor<T> value);
}

Given the above, the previous expressions should desugar into

Tensor<T> view = tensor.Get_Slice([(..), 2.., (..3), 5..10]);
tensor.Set_Slice([0..1, (..)], ones);

Thoughts? Is this something we could pursue for the next C#?

Bonus: The ellipsis operator

Python defines ... as a special constant that among other things can be passed as a parameter in indexer methods. The code

tensor[..., 0]

can be used as a synonym to writing

tensor[:, :, :, 0]

It would be nice if we could achieve something similar in C# slicers, however it should be noted that this cannot be implemented as syntactic sugar for the case of tensors -- the rank of the tensor cannot be known at compile time. Most likely it would require runtime representation (potentially as an augmentation of the System.Range type?) which the slicer can interpret accordingly.

[tannergooding]

This likely requires expansion to the System.Index and System.Range support to also include long and/or nint -- (ideally we could just support any numeric like type or type that follows a required shape)

[tannergooding]

It's unrelated to indexing / slicing, but would float ranges also have value, perhaps?

IMO, no. Floating-point values start getting into a lot of complexities that can't be trivially handled or explained.

This includes needing to track a step amount so that 0.5..0.75 could "make sense" and explaining concepts like what happens for 0..33554432.0f, given that once you hit 16777216 (2^24) integers aren't exactly representable anymore and thus 16777216 + 1 is 16777216, not 16777217. At that point, representable values are 2 apart; then 4 apart at 2^25, 8 apart at 2^26`, and so on.

[NiklasGustafsson]

It wouldn't deal with the step issue, just be a way to represent [a,b) in a nicer way, but if System.Range has to have enumeration semantics, then it clearly isn't applicable.

[eiriktsarpalis]

System.Range was very deliberately designed as a type meant to represent a range of (non-negative) indices. I think we might need a separate type to represent arbitrary numeric intervals such as [a, b). We might want to call it Interval<T>.

[tannergooding]

System.Range is specifically designed to coordinate with System.Index and has properties such as All or GetOffsetAndLength, which requires some interesting considerations when factoring in floating-point values and could potentially lead to issues.

So while it isn't strictly "needs enumeration", it isn't straightforward to support.

[NiklasGustafsson]

Some other languages conflate the two, but it makes sense given the design history of System.Range in .NET

Without syntactic sugar, intervals can just as well be represented by a tuple (a triple when you want to provide the step).

Sorry about the tangent... now back to regular programming! :-)

[NiklasGustafsson]

Python also has a value denoted '...' which is a wildcard over dimensions and allows you to write code that is generic over the number of dimensions.

It may be most useful for variable-rank types, but could also be used for something like:

tensor[...]  = Tensor<int>.Ones(3);

where it would overwrite the contents of 'tensor', rather than modify the variable 'tensor'

[CyrusNajmabadi]

Question. Why is

tensor[:, 2:, :3, 5:10] # gets a view of the sub-tensor scoped to the specified dimensions

that much better than:

tensor[.., 2.., ..3, 5..10];

Is it just to ape python? That's not hugely compelling to me. With the C# 13 work to support params collections, we should be able to have:

public Tensor<T> this(params ReadOnlySpan<Range> ranges);

so you would literally be able to write the latter and have it work.

[tannergooding]

Many other ecosystem don't support as many languages as .NET does and/or don't have the same level of care/concern around back/forward compat.

.NET is one of the few ecosystems where the same core that we shipped 20 years ago in .NET Framework 1.0 remains just as valid and good today as it was back then. We do make mistakes and there are places where we've opted to evolve things, but those are almost all considered extremely carefully and in the context of the broader ecosystem, where it's been, and where it's going.

What's "elegant" today can often lead to bugs, confusion, or errors 5 years down the road. So it's very important that we take in the broader context and understand what types of issues might crop up before doing something "new", even if its something that happens to work for another ecosystem today.

[tannergooding]

Consistency is also a major selling point for us. When we go and start supporting something new, we often want to ensure it can be integrated throughout the ecosystem cleanly and makes sense/works in most scenarios.

So, if we started saying that x[1..] = y (given Tensor<T> x; and Tensor<T> y; should work for Tensor<T>. Then you can expect that it needs to also work/make sense for T[], Span<T>, List<T>, and other collection types.

[eiriktsarpalis]

@NiklasGustafsson correct if I'm wrong, but such forms are already possible in TorchSharp right?

[NiklasGustafsson]

Yes.

TorchSharp was specifically designed to make code look as much like PyTorch code as possible, and since assigning to a slice is a common operation, it's supported. That includes assigning into a slice indexed by a Boolean tensor (a filter, in other words), which is far more useful in the target of an assignment than on the right-hand side.

You can do both:

t[0,..,..] = ...;

and

t[t < 5] = ...;

[eiriktsarpalis]

While I don't have a strong opinion on the matter, it might be worth considering that

• To my knowledge we have no precedent of assignable slice expressions, which should give us some flexibility wrt defining the appropriate convention.
• Conventions being followed around indexer implementations aren't universal. For example, it might be argued that a getter has dereferencing semantics and/or is idempotent, however that isn't the case with Slice methods in other collection types which have copy semantics. In other words

  List<int> list = [1, 2, 3];
  list[1..][0] = -1;
  list[1..][0]; // 2

  This would suggest to me that the semantics of slicing indexers in particular need to be considered to separately.
• I don't think pursuing consistency for the sake of consistency is necessarily beneficial. As mentioned, existing collection types (excluding span) use copy semantics for slicing, however doing the same thing for tensor types would be impractical.
• Finally, I want to echo @NiklasGustafsson's earlier point, it's worth considering whether the guidelines serve the scenarios. Slicing appears to be a core functionality of tensor libraries, and we would be offering this component either to data scientists already familiar with tensor libraries or people looking to port existing tensor code to .NET. In both cases maintaining a degree of mechanical sympathy seems like a good goal to me.

[NiklasGustafsson]

Note that this statement in Eirik's initial post:

tensor[0, ..] = Tensor<int>.Ones(3);

would require an implicit conversion from integer to System.Range, so that a is equivalent to a..(a+1)

[NiklasGustafsson]

But that's for tensors. Multi-dimensional arrays would need something with more tight language support, right? You'd want the compiler to check that it's got the right number of indices, for example.

[CyrusNajmabadi]

We're discussing md-arrays over in Collection-Exprs Next :)

[tannergooding]

Yes and ideally we don't have two separate types to support the general concept of multi-dimensional indexing/slicing.

One might get specialized language validation for MD arrays; but other types might not.

[NiklasGustafsson]

Yes, Eirik and I were having a conversation about collection expressions; slicing / ellipsis came up, which seemed orthogonal to that discussion, so Eirik started this.

[NiklasGustafsson]

BTW, the TensorIndex approach also addresses the ellipsis issue, since there can be a TensorIndex.Ellipsis singleton. Not as elegant and readable as '...', but good enough.