Chapel: Array & Domain Concatenation

[ben-albrecht]

Currently, there is no elegant way to concatenate N-D arrays. This would be a nice feature to provide as part of the array and domain interface, similar to the numpy.concatenate function in Python.

The direction of concatenation could be specified by an axis argument similar to numpy.concatenate.

Simple example:

var A: [1..2, 1..4] int;
/*
0 0 0 0
0 0 0 0
*/

var B: [1..2, 1..4] int = 1;
/*
1 1 1 1
1 1 1 1
*/

// Default axis is 0, i.e. stacks vertically
var AB = concatenate(A, B);
/*
0 0 0 0
0 0 0 0
1 1 1 1
1 1 1 1
*/

This could work similarly for domains.

[Tshimanga]

sounds like something that ought to go in NumSuch

[Deeksha96]

hi @ben-albrecht, I tried implementing a function for this purpose. Here is the code:

proc concat(A:[?D1] int,B:[?D2] int,axis:int)
{
    var dimlist=D1.dims();
    var rank=D1.rank;
    var d1=dimlist(axis).size;
    dimlist=D2.dims();
    var d2=dimlist(axis).size;
    const r=1..d1+d2;
    dimlist(axis)=r;
    var newDomain:domain(3)=dimlist;
    var res:[newDomain] int;
    for ij in D1 do
        res[ij]=A[ij];
    for ij in D2
    {
        var x=ij;
        x[axis]+=d1;
        res[x]=B[ij];
    }
    return res;
}

I am facing a problem with specifying the rank of the new concatenated domain, as it can not be done using the rank variable defined above. Is there any way to handle this?

[bradcray]

@deeksha96: Generally speaking, the rank of a domain or array in Chapel must be a param value (one known at compile-time). I suspect changing your declaration to param rank = D1.rank; would make a big difference.

[LouisJenkinsCS]

Any chance that instead you could adopt a Copy-On-Write strategy for domains. The issue is that resizing an array will resize the domain and will propagate that effect to all arrays that share the domain, but why not create a new domain on demand based on the old one for the array that initiated the resize?

For example...

var x : [1..10] int;
var y : [1..10] int;
var z = x;
assert(z.domain == x.domain);
z.push_back(y);
assert(z.domain != x.domain);

This way you still get the benefit of sharing, but also make it possible to resize an array more intuitively without a runtime error. In terms of how it could be implemented...

proc push_back(x) {
   if isSharedDomain(this.domain) {
      this.domain = cloneDomain(this.domain);
   }

   // Perform push-back operation
}

I'm assuming we're using some kind of Shared reference-counted wrapper around it, and if not perhaps it should do so. That way lifetime management is handled and we get additional functionality.

[LouisJenkinsCS]

@mppf Any opinion on using Copy-On-Write + SharedObject (or equivalent memory management) for domains?

[mppf]

@LouisJenkinsCS - it's an interesting idea and might be a nicer path than the current story. But it seems unrelated to this issue. Could you make a new issue with that proposal? I'll note that we've also talked about possibly making push_back only work on arrays with a special domain map.

[bradcray]

See issue #9452 for an issue related to what Michael is talking about.

[ben-albrecht]

I think this feature would have a lot of value for 1D array concatenation as well. Currently, doing an out-of-place array append isn't very pretty:

var AB: [1..A.size] A.eltType = A; 
AB.push_back(B);

or:

var AB = [i in {1..A.size+B.size}] if i <=A.size then A[i] else  B[i-A.size];

In Python, this is:

AB = A + B

For an operation important enough to be Python's list.__add__() method, Chapel ought to have a clean way to express array concatenation.

[ben-albrecht]

@benharsh implicitly suggested concat to me in chat, which I like better than the more verbose variant originally proposed.

[bradcray]

My main reaction is to question whether Chapel's arrays should support concatenation natively or whether types that wrap arrays + domains for improved usability (like proposed types to support vectors/lists in issue #9452) should support them. My intuition is that these make more sense on a list type than on the array type itself.

[ben-albrecht]

My intuition is that these make more sense on a list type than on the array type itself.

I don't see a good reason not to include this functionality on native Chapel arrays. It doesn't require vector operations, and improves their usability.

Then again, I don't have a good understanding of what Chapel arrays will look like after splitting off the new wrapped types.

[mppf]

@ben-albrecht - you'd only be able to resize the array by updating the domain.
So, in that context, I think this issue would be solely about allowing domain concatenation. The elements would be updated by a slice assignment once the domain was updated.

[ben-albrecht]

To clarify, the proposal here is for an out-of-place operation, such that the original arguments remain untouched (consider them const). The array returned would have its own domain and would own all of its element with no references back to the original arguments, e.g.

const A = [1,2,3];
const B = [4,5];

var AB = concat(A,B);

writeln(AB.domain); // {1..5}
writeln(AB); // [1,2,3,4,5]

[ben-albrecht]

A design detail to consider is how to define the offset and stride of the new indices. It seems reasonable to always inherit from the first argument's domain, e.g.

var A: [0..#10] int;
var B: [2..8 by 2] int;

var AB = concat(A, B);
var BA = concat(B, A);

writeln(AB.domain); // {0..#14}
writeln(BA.domain); // {2..28 by 2}

This could work similarly for domain concatenation:

var domA = {1..10},
    domB = {0..#3};

var domAB = concat(domA, domB);
var domBA = concat(domB, domA);


writeln(domAB); // {1..13}
writeln(domBA); // {0..#13}

Another design detail: variadic args could be nice for combining several arrays at once:

var A = [1,2],
    B = [3,4],
    C = [5];

var ABC = concat(A, B, C); // [1,2,3,4,5]
// cleaner than:
var ABC = concat(concat(A, B), C); // [1,2,3,4,5]