Epic: List unification

[robert3005]

All lists should be lists. Distinction between FixedSizedList and List was a mistake. The key part of what allows vortex to be powerful is ability to swap the physical representation of the array transparently depending on the operation, the problem with FixedSizedList is that its a purely physical encoding without meaningful logical difference.

You can express FixedSizedList array as a ListView with sequence offsets and constant sizes. This is a bit of additional metadata but not that much to forgo other benefits

Goal

The key issue with FixedSizedList is that it enforces certain kind of physical encoding logically and physically. The actual optimisation here is that the physical layout is so special that you promote it to the logical one. However, logically this is still a list. There's potential difference here if you were to forbid nested types as values but that's not the distinction vortex wants to enforce.

The particularly painful part here is that we want to support operations that lets us freely reorder/truncate/shuffle our arrays and FixedSizedList supports none of that. In order to workaround this limitation we have invented additional encodings like PiecewiseSequence which is a useful encoding to express operations on lists but a lot of operations are easier if the encoding natively supports reordering.

Additional problem is that FixedSizedListArray is not good at expressing sparse arrays since it's designed for dense values. There are cases where you want it but often you want the sparse variant, i.e. ListView.

The thing to liken it to is dynamic typing. I think Vortex needs more of it so array encodings are more broadly applicable. We can always specialise for cases where the array looks like a fixedsizedlist array but we don't need to require it

Alternatives

We could store DType in our ListView encoding and have it support both FixedSizedList DType and regular List DType, we would need to assert that sizes is a constantarray, while I think this is useful intermediary state this issue is here to track the ideal end state.

[connortsui20]

I feel like this needs much more justification. Maybe there is good reason for this, but just from reading the issue description, we are saying we need to make this massive change for the sake of take optimizations? I would say removing a DType is probably THE most breaking and destructive change we could possibly make in Vortex, and it is not clear to me why this specific operation is so important and unsolvable unless we completely remove FSL?

IIUC the issue here is that the canonical encoding of FSL is fully contiguous, and so any intermediate destructive operations like take and filter would have to make lots of memcpys. The solution this issue proposes is that we completely remove FSL and replace it with ListView so that we can reorder and overlap data internally in the type. But I guess my question is: why not just keep a DictArray on top of the FixedSizeList array tree and do our best not to apply the compute unless absolutely necessary? AFAICT that does the exact same thing (and really I think we want this functionality regardless of this specific issue, as it is generally useful to keep things encoded as Dict).

One of the other reasons I have such a visceral reaction to this proposal is that I like to compare Vortex's type system to how a standard type system in a statically-typed programming language is. To me, this proposal is akin to saying "we are going to remove fixed-length arrays ([T] in Rust) from this language because variable-size lists (Vec<T>) do a similar thing".

Removing FSL seems like a huge oversimplification of other issues in Vortex (lazy execution into specific physical encodings probably being the main one), and I would like to see some more justification and reasoning before we decide to move forwards with this massive change.

[robert3005]

@connortsui20 I have expanded the issue. The analogy here though is that DType is like a rust trait and encoding is an implementation of that and I am arguing that having FixedSizedList as an additional trait and not implementation of list is not that useful

[connortsui20]

I disagree even more if we say that DType is a trait. How do we bound a Tensor type with a fixed sized? And how would I express something like this:

trait ListType {}

type VariableHistogram: ListType

type HistogramWith10Buckets: ListType<???>

If we say that a DType is like a trait, then we need (even more than before) to have a way to constrain the types. Otherwise we might not be able to use an encoding that only works for fixed-size lists (for example, how would I store a matrix transposed if I didn't know it was fixed-size?). The only way to do that is if you have metadata stored in the type itself that changes the logical behavior, and in that case that is already a new logical type, so there's no semantic difference!

Now, if we say that we just want to change the encoding of FSL to look more like ListView, that is a different conversation (that has its own set of problems, but is orthogonal). That is a much more sound approach to this problem, in my opinion. If you look at #8864 where I unify the canonical encoding of Primitive and Decimal (as well as the canonical representation of both Binary and Utf8 being VarBinView), we could give FSL the same canonical representation as ListView.

Basically, I think it is very incorrect to say that DType::FixedSizeList has no logical difference between DType::List, which seems to be the core argument. I would argue that clearly there is a difference, otherwise no programming language would have a fixed-length array primitive separate from the variable-length arrays.

And I guess I still don't understand what this means:

The key issue with FixedSizedList is that it enforces certain kind of physical encoding logically and physically.

I don't understand why we are jumping to removing an entire DType instead of identifying a better way to do execution where we can execute into specific array trees (such that FSL does not have to canonicalize its children, which would solve the take and sparsity problem mentioned above).

Finally, ListView has caused us so many problems because we have chosen a canonical type that can have too many representations of the same thing, resulting in wildly different performance profiles. It really is just a physical encoding masquerading as a logical type (the logical type should just be List). I don't have a solution, but I have a feeling that if we kept List as the canonical encoding, built special compute arrays on top of it (I think nobody would be upset if we lost the gaps and partial overlap property of ListView), and figured out how to execute into something like Dict<List>, we wouldn't need to make ListView canonical.

I feel like there is an abstraction layer that we are missing, and removing FixedSizeList is not the solution.

[robert3005]

I don't think List is a good representation of the Tensor type, it's the minimum necessary type but I don't think that's what you actually want. You cannot forget that ExtensionDType can have arbitrary additional information and that's how you express your arbitrary constraint.

Better execution for FSL essentially means making it look EXACTLY like List type. I don't think it's worth it having be a type.