New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Improvements to slicing #83
Comments
I would imagine in typical usage, you're generally not going to want to write a literal slice in a 15 dimensional array. With that in mind, what about supplying overloads for a certain number of dimensions? Since there's two chocies for each parameter, it'd have to be 2*(dimensions) overloads, which limits the extent to which we could do it (and we'd need a vararg version to catch the remaining cases), but it would have the nice side effect of letting us automatically upconvert to matrix where apporpriate, e.g. operator fun NDArray<Double>.get(p1: Int, p2: IntRange, p3: IntRange, p4: Int): Matrix<Double> would be a possible overload we could provide. This would also eliminate the possibility of getting imports wrong and accidentally getting an NDArray out when calling get on a Matrix. The downside of course is all the extra bytecode. If we're doing 5 dimensions that's 63 fixed parameter and 32 |
@kyonifer any thoughts on these suggestions? If you agree with them I'd like to try implementing them. In addition to accepting |
I definitely agree this is ugly and we need something better.
As much as possible I'd like to retain type safety, as I think it's one of the primary strengths doing numerical work in Kotlin has over scripting languages. One annoyance with having
It wouldn't be unprecedented (consider kotlin's function overloads out to 23 parameters), so perhaps performance would be reasonable. We have more permutations though.
By this do you mean having overloads with varargs after 5 parameters? So for get/set with < 6 parameters it would be a compile-time error to use something other than an
I really like this idea. There's little reason for
Completely agree with these. |
To be clear, I'm envisioning something like this for the static dimensions = 2 case: operator fun <T> NDArray<T>.get(i1: Int, i2: Int): T
operator fun <T> NDArray<T>.get(i1: Int, i2: IntRange): Matrix<T>
operator fun <T> NDArray<T>.get(i1: IntRange, i2: Int): Matrix<T>
operator fun <T> NDArray<T>.get(i1: IntRange, i2: IntRange): Matrix<T>
operator fun <T> NDArray<T>.get(i1: Int, i2: Int, vararg iN: Any): NDArray<T>
operator fun <T> NDArray<T>.get(i1: Int, i2: IntRange, vararg iN: Any): NDArray<T>
operator fun <T> NDArray<T>.get(i1: IntRange, i2: Int, vararg iN: Any): NDArray<T>
operator fun <T> NDArray<T>.get(i1: IntRange, i2: IntRange, vararg iN: Any): NDArray<T> The obvious issue there is that all the operator fun <T> NDArray<T>.get(i1: IntRange, i2: Int, i3: Int, i4: IntRange, i5: Int): Matrix<T> wherein we can return |
I think the only performance impact would be on compile time. It shouldn't make any difference to runtime speed. What do you think about changing |
Yep, extension functions are resolved statically so the performance hit will be at compile time. At runtime the effect will be bytecode bloat. Both are acceptable tradeoffs to me.
Sounds good here. |
By my count, we'll need 89 versions of each function. That includes all combinations of up to 5 Ints or Iterables, plus another version that adds Are you sure that's ok? |
Since slicing is an aggregate operation (loop over all the elements you are copying/setting) we probably can avoid this, instead dispatching via our reified-at-runtime
That does seem excessive yes. 5 may not be the magic number. Another hybrid proposal that would further reduce the number of overloads we need: We set the number of static dimensions to 2 (similar to my previous comment) and by doing so we secure type safety for matrix operations but not for larger N-D arrays. We then add overloads for just the permutations which have > 2 dimensions but only 1-2 slices so that they return // 3 dim indexes with 1 or 2 slices in them
operator fun <T> NDArray<T>.get(i1: Int, i2: Int, i3: IntRange): Matrix<T>
operator fun <T> NDArray<T>.get(i1: Int, i2: IntRange, i3: Int): Matrix<T>
operator fun <T> NDArray<T>.get(i1: Int, i2: IntRange, i3: IntRange): Matrix<T>
operator fun <T> NDArray<T>.get(i1: IntRange, i2: Int, i3: Int): Matrix<T>
operator fun <T> NDArray<T>.get(i1: IntRange, i2: Int, i3: IntRange): Matrix<T>
operator fun <T> NDArray<T>.get(i1: IntRange, i2: IntRange, i3: Int): Matrix<T> That should greatly reduce the number of methods that are generated: none of these overloads would have val a = matrixOf(1,2,3)
val out1 = a[1..2, 1..5] // Matrix<Int>
val out2 = a[1,1,1] // NDArray<Int>
val out3 = a[1,1,1..5] // Matrix<Int>
val out4 = a[1..4,1..4,5] // Matrix<Int>
val out5 = a["a","b"] // Compilation error
val out6 = a[1,1,"a"] // NDArray<Int>, Runtime error Combined with reified-at-runtime We could make the codegen to generate these overloads take in the number of dimensions as a parameter, so we aren't stuck with our decision. However, I don't think it makes sense to write any more sophisticated codegen yet since I'm planning to close out #76 in the near future. Right now I'm waiting to start #76 until #77 is unblocked, so I can upgrade the build system all at once. Perhaps let's just start with the static dimensions=2 overloads. That will get us into "clearly better than what we have now" territory. We can open another issue to track adding some extensions that force returning a Does that sound reasonable to everyone? |
That sounds reasonable. Is this a correct summary of what you're describing?
I do see some potential problems with returning either Another issue is that Also, if the output only has one dimension, shouldn't it return a Given all these, I wonder if it wouldn't be more consistent and less confusing to always return |
Yeah that would work for all the slicing (aggregate) overloads. We'd still need to retain the non-boxing versions for single element access, as those will often be called in tight loops.
The idea of the extra overloads proposed here is that both of these would return operator fun <T> NDArray<T>.get(i1: Int, i2: IntRange, i3: IntRange): Matrix<T>
Good point-- there's a fundamental mismatch in the base case between NDArray and Matrix. Not sure what makes sense here. Matrix ops always want to return a (2D) matrix, but NDArrays want to have their dimension property set to how much data they actually have. I've always found things like
I'm wondering if we don't actually need Matrix and NDArray to have a base class they both inherit from and not have What I wouldn't give for some union types and value generics in kotlin... |
Another way to go is to have |
This might be a bit too radical of a suggestion, but I'll offer it in the spirit of brainstorming. Is there really a need for separate The other difference is in how they're implemented internally, but that doesn't require a different front end class. The factory could just create a different class for 2D arrays than for arrays of other shapes.
Agreed! |
Indexing is already a mess of weird edge cases: // Runtime vs compile time error seems pretty arbitrary.
eye(3)[10] // runtime error
eye(3)[5, 5] // runtime error
eye(3)[0 until 0, 0 until 0] // compiles just fine and returns eye(3), a result that seems
// completely insane until you read the source and figure out
// what on earth is going on.
eye(3)[1, 2, 3] // but this one is compile time
// Declared type already matters more than it should
eye(3)[1, 2, 3] // compile time
(eye(3) as NDArray<Double>)[1, 2, 3] // runtime
eye(3)[4] // magically row-major
(eye(3) as NDArray<Double>)[4] // runtime error And, the fact that a Matrix currently inherits from NDArray is immensely useful for writing generic data-marshaling functions. If when (it) {
is Matrix<*> -> it[2, 2]
is NDArray<*> -> it[2, 2]
else -> error("Woe is me; there is no such thing as a sealed interface.")
} Admittedly, all I'm doing lately is writing drive-by comments while my code compiles because I haven't had time to contribute properly, but I'd really like to advocate having a single set of indexing rules that behave consistently. How about this for a set of rules:
Or this. Making Matrix and NDArray into a single type would totally eliminate the risk of accidentally defining two incompatible APIs. The fact that they're currently split was originally my fault. The argument went vaguely like this: having a separate matrix type lets third-party libraries declare As long as we're brainstorming, we could go even more ridiculously far down the "refuse to admit kotlin can't do better than python" rabbit hole and have Vector, Matrix, FourDArray, FiveDArray, etc up to however many dimensions we're willing to codegen, so more of these things could be checked at compile time. I'd still advocate having a single set of indexing rules and a base class that is itself as useful as possible. |
It's certainly not an outrageous idea. We've had a few branches in the past where the types were unified (since deleted). Certainly many dynamically typed languages have a single N-D type. By my tally most of them do (Numpy, Julia, R, ...) with one notable language doing a NDArray/Matrix split (MATLAB). Static languages with more powerful templating have different types for every dimensionality (Eigen). Implementations in Java sometimes don't bother to be generic over the primitive type, often times don't bother to support more than two dimensions. Kotlin is trying to fit in a "statically typed but simple and expressive" category where the normal patterns on either side don't directly apply. We can't do expression templates in Kotlin, and I'd argue making everything fully dynamic would be a waste of the language (might as well just use Python then!). Unfortunately it leads us to the tradeoff space that we've all illuminated here. I think (with some ugliness certainly) we've been able to stay typesafe with respect to the element type, so that's at least something over a fully dynamic solution. But the part thats still uncertain is dimensional typesafety. The goal of the Probably the latter approach would be the path of least resistance, as it's what most other libraries do. The former would be useful feedback for a user building a system up until we can't make it work inside of Kotlin's type system and we are inconsistent. My instinct is to try and make everything statically resolvable that we can figure out how to get Kotlin's compiler to enforce, so I'm hesitant to give up on the
Fair enough, one way or another we'll these types unified for the sake of the user's sanity.
If I understand correctly, that would mean back-end implementation classes like |
Originally Python also had separate 2D is definitely an important special case, but it's less of a special case than the current API implies. For example, matrix multiplication is currently only available for I've worked with C++ codes that turned everything into template arguments. That lets you really do everything "correctly", including producing the right output types. For example, if you multiply a row vector by a column vector, the result should be a scalar. If you multiply a column vector by a row vector, the result should be a 2D matrix. And if you multiply a row vector by another row vector, it shouldn't compile. But to do that in Kotlin you would need separate classes for |
I'm aware of the
Yep thats what I meant by eigen's expression templates. It lets you specify not just the dimensions but lengths, and checks everything at compile time. This is virtually impossible in Kotlin's limited type system. |
Another data point in favor of unifying the types: the distinction between a row vector and a column vector isn't clear if we treat a matrix as having one dimension. To me that distinction strikes of a need for a matrix to be 2D (i.e. 1x5 vs 5x1), and thus reducing matrices to 1D in case of a NDArray slice is ambiguous: are we returning a row or column vector? Just returning a 1D NDArray would make this case more consistent, as the user would be forced to reshape to a 2D container to treat it as a matrix (or we'd just allow 1D NDArrays to be used as a column or row vector depending on the operation and operands). |
Upon consideration, I can't come up with a comprehensive resolution to this issue as there's too many factors at play. I'm therefore going to suggest my usual approach to these situations: find the minimal delta that will sufficiently address the original issue and then open a flurry of issues for the other good ideas that came up. In particular I propose closing this issue by:
We also probably need to either fix or open issues for the other good points brought up here, including but not limited to:
While incredibly useful, 1D row-major indexing of 2D containers might be too magical. I think we need to open a new issue to discuss this. In particular, we could always force users to use something more explicit like
This probably deserves an issue of its own to see how consistent we can get while maintaining the different semantics of Matrix and NDArray.
This definitely deserves an issue. I think we can fix up NDArray tensors while still maintaining the special cases like
There's a lot of methods like this that need to be added and deserve issues (also related to #29). |
That sounds like a good plan. I'll start on the changes to #90. |
It turns out the following doesn't work:
A public inline function isn't allowed to call non-public functions. That kind of makes sense, since inline code is effectively part of the code that calls it. But that leaves me a bit stuck as to how to implement this. If it's not inline, it can only call the generic version, not the type specific one. I could make |
Any thoughts about this? I haven't come up with any other solution. So I see two options. One is to have separate definitions for every set of arguments, for each function, for every data type. To statically type check the first two indices we need eight versions of each function, so a total of 168 functions. That's a bunch, though not nearly as bad as it would have been to check the first five indices. The other option is just to leave them as |
How about going with your two bullet points, but instead of an internal function called |
I'd like to suggest several improvements to slicing.
Matrix lets you use any combination of Ints and IntRanges for slicing. It does this by providing all combinations of them in
get()
andset()
:(Int, Int)
,(Int, IntRange)
,(IntRange, Int)
, and(IntRange, IntRange)
. That wouldn't be practical for NDArray, so instead it only has two versions. One takesvararg Int
and returns an element, and the other takesvararg IntRange
and returns an NDArray. That means you can't mix them. For example, if I want to extract a 1D slice from a 3D array I can't writeInstead I have to write
That's much less readable, and it creates more opportunities for errors. It also returns an array of the wrong shape. I wanted a 1D array, but instead it returns a 3D array of shape (1, 10, 1).
I suggest changing the signature form
vararg IntRange
tovararg Any
so the user can mix and match Ints and IntRanges. That will mean relying on runtime type checking to throw an exception if the user passes a value of any other type, which isn't ideal. But I think it's a minor tradeoff compared to the much more important benefits.Unlike Matrix, NDArray only supports slicing in
get()
, notset()
, so you can't use it on the left side of an assignment. It should be supported inset()
too.Matrix allows you to use a negative number for the upper bound of a range, which it interprets relative to the width of the matrix. But it doesn't support it for the lower bound, so you can't write
-5..-1
to get the last five elements. It also doesn't support negative values for specific indices passed as Ints, only for ranges. And NDArray doesn't support negative indices at all. I suggest allowing them everywhere in any method that takes an index.The text was updated successfully, but these errors were encountered: