[Numpy-discussion] Index Array Performance

Marcel Oliver m.oliver@jacobs-university...
Tue Feb 14 17:23:53 CST 2012


Francesc Alted wrote:
 > On Feb 14, 2012, at 1:50 AM, Wes McKinney wrote:
 > [clip]
 > > But:
 > > 
 > > In [40]: timeit hist[i, j]
 > > 10000 loops, best of 3: 32 us per loop
 > > 
 > > So that's roughly 7-8x slower than a simple Cython method, so I
 > > sincerely hope it could be brought down to the sub 10 microsecond
 > > level with a little bit of work.
 > 
 > I vaguely remember this has shown up before.  My hunch is that
 > indexing in NumPy is so powerful, that it has to check for a lot of
 > different values for indices (integers, tuples, lists, arrays?),
 > and that it is all these checks what is taking time.  Your Cython
 > wrapper just assumed that the indices where integers, so this is
 > probably the reason why it is that much faster.

Thanks for all the replies.  Playing a bit with timeit, it is clear
that it cannot just be the overhead of checking the type of the index
array, as the overhead grows very roughly propertional to the size of
the index array, but remains independent of the size of the indexed
array.

In [1]: a=arange(1000000)

In [2]: i = arange(10)

In [3]: timeit a[i]
100000 loops, best of 3: 1.95 us per loop

In [4]: i = arange(100)

In [5]: timeit a[i]
100000 loops, best of 3: 4.07 us per loop

In [6]: i = arange(1000)

In [7]: timeit a[i]
10000 loops, best of 3: 23.3 us per loop

In [8]: timeit i+i
100000 loops, best of 3: 5.62 us per loop

In [9]: i = arange(10000)

In [10]: timeit a[i]
1000 loops, best of 3: 220 us per loop

In [11]: timeit i+i
10000 loops, best of 3: 28.1 us per loop

It would really be nice if this could be made more efficient as it's a
very nice and powerful construct.

Robert Kern wrote:
 > Other people have explained that yes, applying index arrays is slow. I
 > would just like to add the tangential point that this code does not
 > behave the way that you think it does. You cannot make histograms like
 > this. The statement "hist[i,j] += 1" gets broken down into three
 > separate statements by the Python compiler:
 > 
 >   tmp = hist.__getitem__((i,j))
 >   tmp = tmp.__iadd__(1)
 >   hist.__setitem__((i,j), tmp)
 > 
 > Note that tmp is a new array with copies of the data in hist at the
 > (i,j) locations, possibly multiple copies if the i index has
 > repetitions. Each one of these copies gets incremented by 1, then the
 > __setitem__() will apply each of those in turn to the appropriate cell
 > in hist, each one simply overwriting the previous one.

I know.  The posted code is correct because it updates only one bin in
each of the many histograms at a time, which is natural for that
particular example.

It would indeed be nice if the increment construct would result in
multiple increments work when indices repeat - I think that would be
generally more useful and expected.  But current behavior is
documented, so it's fine if only it was efficient...

Regards,
Marcel


More information about the NumPy-Discussion mailing list