Multidimensional arrays and ranges

[Herringway]

For a while now, D has supported multidimensional indexing and slicing, but the only way to take advantage of them is for the user to supply their own types implementing them. This is a huge shame, because they make any code thinking N-dimensionally incredibly elegant and easy to maintain!

There are several problems I wish to see addressed:

• Neither Phobos nor the language offers an N-dimensional array type. There is a partial implementation of a 2D array here, but there really should be full-featured implementations in std.array or the language itself. Ideally there would be a static flavour as well.
• Ranges are completely useless with N-dimensional ranges. empty, front, and popFront only consider single dimensions. Perhaps, in a similar fashion to opDollar, these may be expanded into templates like front(size_t dim)()?
• Algorithms should support N-dimensional ranges where possible. It may not make sense for sort() to operate on a 2D array, but cycle() and repeat(n) are immediately obvious.

[Herringway]

No interest whatsoever? That's disappointing, but consistent with my past proposals.

[LightBender]

I don't know that there is no interest. The fellow who is going to be doing most of the work on ranges doesn't really come around this repo much. @jmdavis any interest in looking into this?

[jmdavis]

Ranges are already arguably overly complex, so personally, I'm not interested in seeing them become even more complex to try to support multi-dimensional arrays if there is additional support needed for them. Though honestly, I do basically nothing with them in general, so I'm not well-suited for determining what would even be necessary. My gut reaction is that you'd just use a range of ranges, but either way if by multi-dimensional arrays, we're talking about multi-dimensional static arrays, they can't be ranges themselves pretty much no matter what we do, because you can't shrink them - just like static arrays can't be ranges. And if we're talking about multi-dimensional dynamic arrays, well, they're already ranges of ranges.

Either way, if a multi-dimensional array can be wrapped to become a range of ranges, then it should work just fine even with the current API. Then it's just a question of what we'd do with algorithms to support them, though for simplicity's sake, they'd probably need their own module of special algorithms if the normal ones don't work without special support. As we've already discussed in DLF meetings, the number of stray overloads that we have for the functions in std.algorithm is already problematic as it is, and if anything, we're looking to simplify the situation there. So, new functionality for existing functions would likely mean a separate set of functions with new names or a separate set of functions with the same names but in different modules.

If there are changes that need to happen to the range API to make them work better with multi-dimensional arrays, then someone who is far more familiar with them than I am would need to make concrete suggestions with clear explanations as to why those changes would be necessary, but if we do make them, they really need to be completely additive so that they do not affect normal range-based code. It's already hard enough to understand what's going on with opIndex after it was changed to better support multi-dimensional arrays, and I really do not want to see that kind of complication added to ranges in general.

We already have an annoyingly high level of complexity with regards to all of the stray abilities that ranges may or may not have, resulting in a large number of static ifs for generic ranges that are trying to support all of the various range abilities even if it's just to forward them from ranges being wrapped. And I think that we need to be very selective about adding anything more to that mess. It's already arguably too difficult to write range-based code that works with everything that the range API is supposed to be able to work with.

So, I won't say that we're definitely not going to do anything with multi-dimensional arrays, but I'm not going to be coming up with any suggestions for that myself, and if they really can't work as ranges of ranges, I'm inclined to argue that they should probably be there own thing with their own API which is then suited to whatever special things they need to do that they can't do as a range of ranges. And I don't see any reason why we couldn't then have a set of algorithms specialized for that. Then we could provide functionality for the multi-dimensional array use cases without complicating normal ranges. And if someone wants to propose containers of some kind that help out the folks who want better support for multi-dimensional stuff, then I see no reason why we can't do that too, though we'll need a lot of the core stuff in place before we get containers of any kind into Phobos v3.

Either way, as far as the level of feedback goes, I don't think that there are more than a handful of folks who have been interacting with the discussions in this repo, so feedback for most things is going to be low, and if the folks who have been interacting here aren't normally doing much with multi-dimensional arrays, then they won't have much to say on the matter.

[Herringway]

Ranges of ranges don't provide anywhere near the same level of functionality. Even simple multidimensional slicing can't be done. arr[0 .. $ -1, 1 .. $] is not equivalent to arr[1 .. $][0 .. $ - 1], for example. I would consider supporting these through ranges of ranges to be a downgrade from having no support at all.

As for feedback, I was not referring solely to this repo. The only way to get any sort of meaningful feedback in this community when you're a nobody like me seems to be starting a flame war in the forums, which I am entirely uninterested in doing.

[rikkimax]

I would've commented earlier, but I haven't got anything to add to this.

From my perspective, I haven't studied or used multi-dimensional arrays.
Let alone algorithms that operate on it.

I suspect the D community in general simply lacks such expertise to be able to figure out what is it even meant to do, let alone how.

Although I think that the functionality of operator overloads here is awesome!

[Herringway]

They're not terribly complicated, but the amount of support code required can be a little intimidating. I started using them for the raster rendering in my Gameboy/NES/SNES PPU implementations, and that resulted in a MASSIVE improvement in readability. SNES rendering in particular is actually very simple with the right representation, and a proper 2D array turned out to be that representation.

The SNES's rendering system is based on a 64x64 field of tiles, repeating infinitely on both planes. Those tiles are further divided into a 2x2 arrangement of 32x32 tile tilemaps, which may be configured in 4 different ways (single tilemap repeated on both planes, two tilemaps repeated vertically/horizontally, four tilemaps). On top of that, there's a 32x28 tile viewable area that may be positioned anywhere on the 64x64 field, with pixel resolution. It can be visualized something like this:

It sounds very complicated, and before I started representing it with 2D arrays, the code WAS extremely complicated. But now, that mess of modulos and additions have been reduced to simple range operations, at least on the horizontal plane. I have an Array2D!Tilemap that I can use joiner(), cycle(), and then take a simple 28 tile slice with. A horrific mess, reduced to a handful of simple operations. I now find myself wishing the tools to do this for BOTH planes were available.

[PetarKirov]

@Herringway are you familiar with mir.algorithm? It is by far the best multi-dimentional range implemention in D (probably many other languages). In case you haven't, check out:

• http://mir-algorithm.libmir.org/
• http://mir-algorithm.libmir.org/mir_ndslice.html

The ndslice part of Mir was initially added to Phobos std.experimental, but the author decided to move the development to a separate repo and GH org in order to speed up the development process, have more control and overall be able to grow it to a full blown library for scientific computing, which likely wouldn't have been possible in the confines of Phobos (at least at the time).

[jmdavis]

Then there's no need for the range API to worry about NDSlices at all. They can be their own thing which provides ranges where appropriate, and those ranges can then use the normal algorithms - just like range-based code in general doesn't have to care at all about what containers might exist. As long as those containers provide ranges in whatever fashion is appropriate to them, they can take advantage of all of the normal range-based algorithms, and they can then have whatever other functions are appropriate to them separate from the range API. And if someone wants to come up with a module or set of modules that provide NDSlices and are designed around them with additional functionality that's specific to them (including whatever algorithms they might need which won't work with the range API), that's fine with me. What I want to avoid is the range API and normal range-based code having to worry about any of that.

But either way, I'm not the person to design anything surrounding multi-dimensional types. I know that there are some domains that use such types heavily, but I have never worked in such a domain, and almost nothing I've done has dealt with multi-dimensional types.

I'm working on refining the current range API to fix some of the issues with it, but barring a very compelling argument that the core range API needs changes to support multi-dimensional types, I really don't want to see that complication added to the range API, and I'm not going to design anything around multi-dimensional types. As long as someone else can create the functionality for multi-dimensional types on top of the normal range API, that's good enough for me. I'll leave the design of such functionality to someone else who's actually familiar with those paradigms, just like I'm probably not going to be the person writing any of the various container types that we're going to need (though that's more likely to happen than me writing something like NDSlices). Then we can have a set of modules that provide that functionality for those who need it without affecting all of the range stuff.

Lots of things can be built on top of the range API without the range API needing to incorporate functionality specifically for those domains or types, and I would very much hope that multi-dimensional types would be in that boat. And based on what you're saying about NDSlices, it very much sounds like that's the case.

[PetarKirov]

@jmdavis

Then there's no need for the range API to worry about NDSlices at all. They can be their own thing which provides ranges where appropriate, and those ranges can then use the normal algorithms - just like range-based code in general doesn't have to care at all about what containers might exist. [..]

Yes, exactly.

[PetarKirov]

Perhaps there should be few places where ranges traits need to know about ndslices:

• ElementType!(NDSlice!(T, N)) -> NDSlice!(T, N - 1)
• DeepElementType!(NDSlice!(T, N)) -> T

but apart from that the rest of the standard range code should just work.

Edit:

Thinking more about this:
std.range.traits.ElementType doesn't need to know about NDSlices. It just needs to do typeof(range.front). DeepElementType can just work on top of std.range.traits.ElementType.

[jmdavis]

Thinking more about this: std.range.traits.ElementType doesn't need to know about NDSlices. It just needs to do typeof(range.front). DeepElementType can just work on top of std.range.traits.ElementType.

Yes, ElementType just needs to look at the type of front, so if NDSlice is a range, then that takes care of itself. And if an NDSlice is a container rather than a range, then it wouldn't be appropriate to use ElementType on it anyway, since it's a trait for getting the element type of a range, not a container.

Whatever additional traits that might be needed which are specific to NDSlices can be provided by the modules which are specific to NDSlices, and the normal range-based algorithms shouldn't need to care about them. As it is, any algorithms that are specific to NDSlices should probably be in a separate module or package specific to NDSlices anyway rather than be mixed in with the normal range-based algorithms - both for clarity, and because it will reduce issues with overloads (we want to be reducing those with Phobos v3, not increasing them). It'll also avoid having the modules for the range-based algorithms depending on the NDSlice modules. We would like to minimize the number of module interdependencies in Phobos v3 where we can reasonably do so (since Phobos v2 has a problem with that).

[Herringway]

In general, I think it's simpler in practice. ndslices are random access ranges in multiple dimensions. You can use std.algorithm on them without std.algorithm needing to know anything about ndslices. All you need to do is use a ndslice range selection function which will return a standard 1-D random access range (say given a 200x400 2-D matrix ndslice, iterate each column from top to bottom). Once you get the 1-D ndslice range, you can use std.range and std.algorithm on it as usual.

I want to be able to cycle() in both dimensions, not just one at a time. If the solution doesn't support simple things like my2DArray.cycle()[a .. b, c .. d], then I am not at all interested.

Is that complicated to support? Perhaps. But that complication doesn't go away by denying support for it in Phobos. It just means users like me will be required to bear the burden instead.