Thread Subject: Is subscript referencing slower than : ?

Hello all!

I was surprised to note that for a vector 'a' of some length 'N'
b = a(2:N-1);
is much faster than
idx = 2:N-1;
b = a(idx);

I did some timings with the following program:

%%%% BEGIN
N = 10000;
repetitions = 10000;

a = rand(N,1);
idx = 2:N-1;

tic

for k = 1:repetitions
b = a(2:N-1);
%b = a(idx);
end

toc
%%%% END

With b = a(2:N-1): 0.27 sec
With b = a(idx): 1.88 sec

Note that the assignment to idx is outside the repetition
loop, so the performance drop really is due to the
referencing in 'a'.

Can someone shine some light on this?

Thanks! /Dag Lindbo

Hi

I can reproduce your results. I think it has something to do
with the fact that idx is a vector, because if I use
a([2:N-1]) instead of a(2:N-1) it becomes as slow as idx.

Regards

"Dag Lindbo" <dag@csc.kth.se> wrote in message
<fmnfit$324$1@fred.mathworks.com>...
> Hello all!
>
> I was surprised to note that for a vector 'a' of some
length 'N'
> b = a(2:N-1);
> is much faster than
> idx = 2:N-1;
> b = a(idx);
>
> I did some timings with the following program:
>
> %%%% BEGIN
> N = 10000;
> repetitions = 10000;
>
> a = rand(N,1);
> idx = 2:N-1;
>
> tic
>
> for k = 1:repetitions
> b = a(2:N-1);
> %b = a(idx);
> end
>
> toc
> %%%% END
>
> With b = a(2:N-1): 0.27 sec
> With b = a(idx): 1.88 sec
>
> Note that the assignment to idx is outside the repetition
> loop, so the performance drop really is due to the
> referencing in 'a'.
>
> Can someone shine some light on this?
>
> Thanks! /Dag Lindbo

Hi!

I managed to shave most of the performance drop by casting
the index array to integer.
With idx = int32(2:N-1) : Time 0.55 sec

Still shy of the direct indexing case.

This smells platform dependent...
/Dag

"Kees van 't Slot" <kees.slot@mathworks.com> wrote in
message <fmnhob$70c$1@fred.mathworks.com>...
> Hi
>
> I can reproduce your results. I think it has something to do
> with the fact that idx is a vector, because if I use
> a([2:N-1]) instead of a(2:N-1) it becomes as slow as idx.
>
> Regards
>
> "Dag Lindbo" <dag@csc.kth.se> wrote in message
> <fmnfit$324$1@fred.mathworks.com>...
> > Hello all!
> >
> > I was surprised to note that for a vector 'a' of some
> length 'N'
> > b = a(2:N-1);
> > is much faster than
> > idx = 2:N-1;
> > b = a(idx);
> >
> > I did some timings with the following program:
> >
> > %%%% BEGIN
> > N = 10000;
> > repetitions = 10000;
> >
> > a = rand(N,1);
> > idx = 2:N-1;
> >
> > tic
> >
> > for k = 1:repetitions
> > b = a(2:N-1);
> > %b = a(idx);
> > end
> >
> > toc
> > %%%% END
> >
> > With b = a(2:N-1): 0.27 sec
> > With b = a(idx): 1.88 sec
> >
> > Note that the assignment to idx is outside the repetition
> > loop, so the performance drop really is due to the
> > referencing in 'a'.
> >
> > Can someone shine some light on this?
> >
> > Thanks! /Dag Lindbo
>

I tried with this:

>> [dummy,idxrand] = sort(rand(1,N-2));

'a(2:N-1)':
Elapsed time is 0.655753 seconds.
'a(idx)':
Elapsed time is 6.855326 seconds.
'a(idxrand)':
Elapsed time is 6.806539 seconds.

Random and sequential indexing do not differ, so I think
with vector indexing, Matlab uses a seperate fetch
instruction for each element.

Volkan

"Dag Lindbo" <no@spam.com> wrote in message
<fmo86d$odt$1@fred.mathworks.com>...
> Hi!
>
> I managed to shave most of the performance drop by casting
> the index array to integer.
> With idx = int32(2:N-1) : Time 0.55 sec
>
> Still shy of the direct indexing case.
>
> This smells platform dependent...
> /Dag
>
> "Kees van 't Slot" <kees.slot@mathworks.com> wrote in
> message <fmnhob$70c$1@fred.mathworks.com>...
> > Hi
> >
> > I can reproduce your results. I think it has something to do
> > with the fact that idx is a vector, because if I use
> > a([2:N-1]) instead of a(2:N-1) it becomes as slow as idx.
> >
> > Regards
> >
> > "Dag Lindbo" <dag@csc.kth.se> wrote in message
> > <fmnfit$324$1@fred.mathworks.com>...
> > > Hello all!
> > >
> > > I was surprised to note that for a vector 'a' of some
> > length 'N'
> > > b = a(2:N-1);
> > > is much faster than
> > > idx = 2:N-1;
> > > b = a(idx);
> > >
> > > I did some timings with the following program:
> > >
> > > %%%% BEGIN
> > > N = 10000;
> > > repetitions = 10000;
> > >
> > > a = rand(N,1);
> > > idx = 2:N-1;
> > >
> > > tic
> > >
> > > for k = 1:repetitions
> > > b = a(2:N-1);
> > > %b = a(idx);
> > > end
> > >
> > > toc
> > > %%%% END
> > >
> > > With b = a(2:N-1): 0.27 sec
> > > With b = a(idx): 1.88 sec
> > >
> > > Note that the assignment to idx is outside the repetition
> > > loop, so the performance drop really is due to the
> > > referencing in 'a'.
> > >
> > > Can someone shine some light on this?
> > >
> > > Thanks! /Dag Lindbo
> >
>

Dag Lindbo wrote:
> Hello all!
>
> I was surprised to note that for a vector 'a' of some length 'N'
> b = a(2:N-1);
> is much faster than
> idx = 2:N-1;
> b = a(idx);
>
> I did some timings with the following program:
>
> %%%% BEGIN
> N = 10000;
> repetitions = 10000;
>
> a = rand(N,1);
> idx = 2:N-1;
>
> tic
>
> for k = 1:repetitions
> b = a(2:N-1);
> %b = a(idx);
> end
>
> toc
> %%%% END
>
> With b = a(2:N-1): 0.27 sec
> With b = a(idx): 1.88 sec
>
> Note that the assignment to idx is outside the repetition
> loop, so the performance drop really is due to the
> referencing in 'a'.
>
> Can someone shine some light on this?

We're aware of this problem. Indexing is fast on an isolated colon.
Further, "A(1:n)" and "I = 1:n; A(I)" have different execution paths,
and the second can be slower. The reason is that the 1:n is physically
materialized in the second case, but not in the first. It is something
we plan to fix.

mike

Mike Karr <mkarr@mathworks.com> wrote in message
<fn2lqq$l52$1@fred.mathworks.com>...
> Dag Lindbo wrote:
> > Hello all!
> >
> > I was surprised to note that for a vector 'a' of some
length 'N'
> > b = a(2:N-1);
> > is much faster than
> > idx = 2:N-1;
> > b = a(idx);
> >
> > I did some timings with the following program:
> >
> > %%%% BEGIN
> > N = 10000;
> > repetitions = 10000;
> >
> > a = rand(N,1);
> > idx = 2:N-1;
> >
> > tic
> >
> > for k = 1:repetitions
> > b = a(2:N-1);
> > %b = a(idx);
> > end
> >
> > toc
> > %%%% END
> >
> > With b = a(2:N-1): 0.27 sec
> > With b = a(idx): 1.88 sec
> >
> > Note that the assignment to idx is outside the repetition
> > loop, so the performance drop really is due to the
> > referencing in 'a'.
> >
> > Can someone shine some light on this?
>
> We're aware of this problem. Indexing is fast on an
isolated colon.
> Further, "A(1:n)" and "I = 1:n; A(I)" have different
execution paths,
> and the second can be slower. The reason is that the 1:n
is physically
> materialized in the second case, but not in the first. It
is something
> we plan to fix.
>
> mike

Thank you Mike! It does not surprise me that the 'direct'
indexing, a(1:N), can be optimized further. Indeed, it is
good to see that it has been optimized to the extent
evident! IMHO it is not a terrible concern that a(idx) is
slower. However, it seems like a good recommendation that
pre-computed index vectors should be cast to an integer data
type (?).

/Dag

You can view it from the other side: It is nice that
b=a(1:n); is very fast compared to i=1:n; b=a(i);

Markus