2d array indexing is very slow

[ViralBShah]

2d array indexing is significantly slower than matlab for us.

*** MATLAB ***

function t = mytranspose(x)
[m, n] = size(x);
t = zeros(n, m);
for i=1:n
for j=1:m
t(i,j) = x(j,i);
end
end
end

a = ones(2000,2000);
tic; mytranspose(a); toc
Elapsed time is 0.132217 seconds.

*** Julia ***

function transpose(a::Matrix)
m,n = size(a)
b = similar(a, n, m)
for i=1:m, j=1:n
b[j,i] = a[i,j]
end
return b
end

julia> x = ones(2000,2000);

julia> tic(); y = x'; toc();
elapsed time: 2.17426395416259766 sec

[JeffBezanson]

I would love to have a small suite of tests like this, comparing to matlab on things like a[:,i], a[a:b,c:d], etc. as well.

[JeffBezanson]

Another point: x' calls ctranspose, not the transpose function here. ctranspose uses a comprehension, which is slow due to tuple-allocation overhead. Compare again with x.'. I believe the performance bug is comprehensions, not 2d indexing.

[ViralBShah]

I did notice that the transpose performance test in perf.j is looking quite good. Also, replacing ctranspose implementation for now.

-viral

On Jul 12, 2011, at 5:03 AM, JeffBezanson wrote:

Another point: x' calls ctranspose, not the transpose function here. ctranspose uses a comprehension, which is slow due to tuple-allocation overhead. Compare again with x.'. I believe the performance bug is comprehensions, not 2d indexing.

Reply to this email directly or view it on GitHub:
#95 (comment)

[ViralBShah]

BTW, one of the things I have been trying for a while is to find a fast implementation of transpose. I just can't believe that they don't have it in BLAS. So far, it seems that transpose in FFTW is one we can try. Wonder if Bradley Kuzsmaul at MIT has a fast implementation - or if Charles Leiserson does.

-viral

On Jul 12, 2011, at 5:03 AM, JeffBezanson wrote:

Another point: x' calls ctranspose, not the transpose function here. ctranspose uses a comprehension, which is slow due to tuple-allocation overhead. Compare again with x.'. I believe the performance bug is comprehensions, not 2d indexing.

Reply to this email directly or view it on GitHub:
#95 (comment)

[ViralBShah]

See kernel/transpose.c in FFTW. The routines are also exposed in the library. Can't quite yet figure out what the arguments are.

void X(transpose_tiled)(R *I, INT n, INT s0, INT s1, INT vl)

-viral

On Jul 12, 2011, at 5:03 AM, JeffBezanson wrote:

Another point: x' calls ctranspose, not the transpose function here. ctranspose uses a comprehension, which is slow due to tuple-allocation overhead. Compare again with x.'. I believe the performance bug is comprehensions, not 2d indexing.

Reply to this email directly or view it on GitHub:
#95 (comment)

[StefanKarpinski]

Isn't it obvious? Documentation for the win :-P

[ViralBShah]

What? I didn't understand a word of what you said.

-viral

On Jul 12, 2011, at 7:43 AM, StefanKarpinski wrote:

Isn't it obvious? Documentation for the win :-P

Reply to this email directly or view it on GitHub:
#95 (comment)

[StefanKarpinski]

No, I mean that the arguments are completely opaquely named and there's no documentation. Complete transparency fail.

[JeffBezanson]

Fixed in commit 5bf4bce.
Now the two versions of transpose perform the same.