develooper Front page | | Postings from September 2000

Implementing RFC 272

Thread Next
Buddha Buck
September 23, 2000 22:07
Implementing RFC 272
Message ID:
This may be verging outside of the range of "language-data" and veering 
towards "internals", but I'd sort of like to hash out an idea to make 
sure that I'm thinking straight.

When I heard about transpose() (as well as reshape(), etc), I was 
concerned about the time it would take to execute these complex 
operations.  To wit, naively, I believed that a lot of data shuffling 
would be necessary.

Specifically, given the 2x3 array [[a,b,c],[d,e,f]], I had assumed that 
it would be stored in a structure roughly analogous to:

%a = { shape => [2, 3],
       data  => [a, b, c, d, e, f]

with position [i,j] being accessd as $a{data}[3*i+j].

(Note:  I wouldn't implement this at the Perl level, but at a lower 
level. I presume that in C the relevant structure would look something 

struct array { int dims; int *shape; int *data };

but even this is a rough prototype.  I'm just using Perl for clarity).

More generally, an AxBxCxDxE array would have position [a,b,c,d,e] 
accessed with $a{data}[a*B*C*D*E + b*C*D*E + c*D*E + d*E + e]

Transposing that 2x3 array into the 3x2 array [[a,d],[b,e],[c,f]] would 
require building:

%a = { shape => [3,2],
       data  => [a,d,b,e,c,f]

which would have [i,j] being accessed as $a{data}[2*i+j];

Obviously, this is slow, which is why the suggestion "do it lazily" 
comes up.

However, am I wrong in thinking that this representation is faster:

%a = { shape    => [2,3],
       accessor => [3,1],
       offset   => 0,
       data     => [a,b,c,d,e,f]

The idea is that element [i,j] would be accessed as 

  $a{data}[dotproduct([i,j],$a{accessor}) + $a{offset}]

In this case, this would translate to $a{data}[i*3+j+0], which is what 
we had before.

But transpose then wouldn't heve to shuffle data, just shuffle the 
shape and accessor vectors:

%a = { shape    => [3,2],
       accessor => [1,3],
       offset   => 0,
       data     => [a,b,c,d,e,f]

In the AxBxCxDxE array, it would (pre-transpose) look something like:

$data = [ ... ];
{ shape    => [A,       B,     C,   D, E],
  accessor => [B*C*D*E, C*D*E, D*E, E, 1],
  offset   => 0,
  data     => $data

After transposing the 2nd (B) and 3rd (C) dimensions, we'd get:

{ shape    => [A,       C,   B,     D, E],
  accessor => [B*C*D*E, D*E, C*D*E, E, 1],
  offset   => 0,
  data     => $data # unchanged from above

I can see other benefits to this idea as well.  The main theoretical 
benefit I can see is that it eliminates that need to worry about 
"row-major" v. "column major", etc.  All dimensions are treated equally.

It also means that if we wanted to take the 4 dimensional sub-array you 
get from the AxBxCxDxE array above when C is fixed at 4, it can be done 
semi-lazily to get:

{ shape    => [A,B,D,E],
  accessor => [B*C*D*E, C*D*E, E, 1],
  offset   => 4*D*E,
  data     => $data # again, unchanged from above

(This is where the "offset", which was always always 0 above, comes 
into play.)

Fixing the E dimension to 3 would get you:

{ shape    => [A,B,D]
  accessor => [B*C*D*E, C*D*E, E],
  offset   => 4*D*E + 3*1,
  data     => $data # no change yet

I'm expecting one of four basic reactions to this idea:

1)  That's neat and novel,
2)  That's what was already planned, it's the "obvious" way to do it,
3)  We tried that, here's why it doesn't work,
4)  It's stupid, and here's why,

I honestly don't know which is the "proper" response...

     Buddha Buck                   
"Just as the strength of the Internet is chaos, so the strength of our
liberty depends upon the chaos and cacophony of the unfettered speech
the First Amendment protects."  -- A.L.A. v. U.S. Dept. of Justice

Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About