multidimensional lists/arrays

[Jos Hirth]

Prior to the v2 lib update, you could create 2 dimensional lists like this:

var twoDee = new List(2).map((_) => new List(3));

Now it looks like this:

var twoDee = new List(2).mappedBy((_) => new List(3)).toList();

However, I'd prefer something like this:

var twoDee = new List.dimensions([2, 3]);

On IRC, someone suggested to use try List.filled, but, as it turns out, that doesn't work since that just creates a list of references to one list (e.g.: listB = [listA, listA]).

[Yulian Kuncheff]

I think creating multi-dimensional arrays is a basic functionality of a language, I find it odd that its so verbose and weird to create a multi-dimensional array.

Are there any plans to incorporate this. I think i came to this problem before, and just resorted to some nested for-loops or something of the sort.

[Bob Nystrom]

Personally, I think this can be solved fairly well at the library level. I know I've written my own Array2D<T> class, and Kevin has too: https://github.com/kevmoo/bot.dart/blob/master/lib/src/bot/collection/array_2d.dart

For me, the only real pain point was that Dart doesn't let you define a subscript operator with arity > 1. So you can't do myArray[2, 3] like you could in other languages.

I also generally prefer my multidimensional arrays to be "flat": I want a multidimensional volume of contiguous elements, not an array of arrays. My use case here has always been games, so that may taint my worldview.

Cheers,

- bob

[Yulian Kuncheff]

Wouldn't games be the ideal place for Arrays of arrays? primarily for matrix transformations and other stuff like that? I think even in C, a multi-dimensional array internally is an array of pointers to arrays of numbers. I could be wrong though. Not a fan of C or C++.

Though your solution is pretty neat.

-Yulian

[Don Olmstead]

Hey Bob. Wasn't there some talk of being able to overload operator() in dart? In C++ I would overload operator() to access a matrix element.

--
Consider asking HOWTO questions at Stack Overflow: http://stackoverflow.com/tags/dart
 
 

[Bob Nystrom]

On Tue, Jan 22, 2013 at 2:46 PM, Don Olmstead <don.j.o...@gmail.com> wrote:

Hey Bob. Wasn't there some talk of being able to overload operator() in dart? In C++ I would overload operator() to access a matrix element.

Yup, there's an article on it here: http://www.dartlang.org/articles/emulating-functions/

I think there's still some back and forth on the syntax for declaring it, but I think it's an in-progress feature. The call operator (method?) is nice in that you can have whatever arity or signature you want unlike, [], but it lacks one thing [] has: assignability. You can overload []= in Dart to make settable subscripts. I don't think there's something analogous for the call operator.

- bob

 

[Jos Hirth]

>I think even in C, a multi-dimensional array internally is an array of pointers to arrays of numbers.

It has been quite a while, but I do remember that in TurboC 1.0 [x][y] was just syntactic sugar for [x+y*w]. It was one continuous chunk of memory. No idea where the dimensions were stored though. Compiler magic, I guess.

The square brackets itself were also just syntactic sugar for doing the same stuff via that pointer directly.

[Alan Knight]

You can also do

    new Iterable.generate(2, (i) => new List(3)).toList();

If we had that on List, and not just on Iterable, it might work reasonably well. Though you can also just define a function

listWithDimensions(sizes) => ...

to make it more compact.

--

[Jos Hirth]

This monstrosity actually works:

class Grid {
  int w, h;
  List data;
  List cols;
  Grid(this.w, this.h) {
    data = new List.fixedLength(w * h);
    cols = new List.fixedLength(w);
    for (int x = 0; x < w; x++) {
      cols[x] = new GridCol(data, x, w);
    }
  }
  GridCol operator [](int x) {
    return cols[x];
  }
}
class GridCol {
  int x, w;
  List data;
  GridCol(this.data, this.x, this.w);
  Object operator [](int y) {
    return data[x + y * w];
  }
  void operator []= (int y, var value) {
    data[x + y * w] = value;
  }
}

...

var g = new Grid(2, 3);
g[1][2] = 'foo';
print(g[1][2]);

But it really doesn't feel right. I guess I'll just stick to arrays of arrays.

[Justin Fagnani]

I don't know, it seems alright to me. If you want to further abstract storage to support spare matrices, this is what you'd need to do. The question is how much of Iterable or List GridCol should implement.

-Justin

[Alex Tatumizer]

You can override both

int operator [](List<int> ind) {...}

void operator[]=(List<int> ind, int value) {...}

so you can write

array[[10,20,30]]=5  

x=array[[10,20,30]]

[Alex Tatumizer]

array[[10,20,30]]=5  

x=array[[10,20,30]]

Patent? T-shirt? :)
 

[Jos Hirth]

I don't really like the idea of creating all those temporary arrays. Say, it's a small game with a tiny 640x480 resolution and fairly large 32x32 tiles, then you'd iterate over 16*21 tiles 60 times a second. 16*21*60=20160 and that's just for drawing. There could be also several layers. It also might be necessary to query it a lot for pathfinding or something like that.

2 years ago, you could create a million tiny objects per second with V8 running on a run-of-the-mill office PC. Well, a million objects is quite a lot. However, creating tiny objects was the only thing that micro benchmark did.

For example, if you bump those numbers up to 124x768 and 16x16 tiles, you end up with: 65*49*60=191100. Ouch. 3 layers, pathfinding, and maybe some other queries and then you'll have spent all of your per-frame budget on the overhead of those temporary arrays.

The second issue is the syntax. It looks really weird.

However, I do admit that this idea was pretty creative. ;)

[Alex Tatumizer]

> However, I do admit that this idea was pretty creative. ;)

this was the entire point of exercise :)
Certainly, performance-wise, it's a horrible idea.
For performance, you need a flat array, as mentioned above (not array of pointers! it has something to do with cache misses etc)
 

[Jos Hirth]

Arrays of arrays are okay if you don't jump from array to array with each step.

Basically, you just have to flip your x and y loops. The outer one should be the y one.

Well, of course this only helps if you just want to iterate over the whole thing. There isn't anything you can do to improve random access. (Except for using a 1D array, that is.)

[Alex Tatumizer]

> There isn't anything you can do to improve random access

Interestingly, from this observation we can deduce that in case of random access, the trick with passing indexes in a list like
var a=myArray[[x,y,z]]

doesn't noticeably affect overall performance.

It depends on how big the array is, and how random the access is.
I checked data on Inter Core i7, it has cache sizes:
L1: 64K
L2: 1MB
L3: 8MB

I couldn't find exact data on penalties, but I remember the order of magnitude is like 10 cycles for L1 miss, 100 for L2, and it might be 500 (?) for L3
(please correct me if I'm wrong).
So you start facing problems when array reaches 64K in size (in reality - even earlier), if random access is required.
Compared with that, overhead of dynamically constructing the "auxiliary" list of indexes [x,y,z] in L1 cache is really negligible. You won't notice much of a difference in performance between this version and carefully optimized C program.

In fact, I believe that the thing won't be as costly as I thought even in average use case, because multidimensional array rarely gets accessed in a linear manner anyway
 

  

[Alex Tatumizer]

And what is PROGRAM if not a multidimensional (fractal) array of functions, plus multidimensional (fractal) array of data?

Given huge (brutal) penalties for cache misses, VM faces a challenge of laying out both code and data to keep them in "clusters" to prevent randomness of cache access.

E.g. if function f1 calls f2 and f3, then compiled code of f1 should be kept close to compiled code of f2 and f3.

Questions: 

1. does dart VM try to layout the compiled code to minimize cache misses?

2. does dart VM try to automatically split data structures into "hot" and "cold" areas and keep them in different memory locations?

3. In general, how important the considerations related to cache use are for VM implementation?

[Ladislav Thon]

And what is PROGRAM if not a multidimensional (fractal) array of functions, plus multidimensional (fractal) array of data?

Each program is a compiler.

:-D

LT

[Alex Tatumizer]

YES!!!

This is very deep thought indeed, I was close to formulating it (remember example with phone number?), but you did it first.

Still, I'm curious to know what VM does cache-wise :)