I've been fiddling with extending some of the strategies in PyPy. My first
port of call has been to provide fast paths in IntegerListStrategy.find,
which is the basis of "x in l" and "l.index(x)". Previously this was very
fast if you looked up an integer, but rather slow if you tried up looking
anything else. Since we know exactly what the type of every element in such a
list is, there seem to be quite a few opportunities for optimisation. I have
left the code for the common case (looking up an int in an int list) as
before; but have provided various fast paths. Looking up floats and longs is
now much faster; for many other types (e.g. strings or user objects whose
class does not override __eq__) these return immediately. I have modified
FloatListStrategy similarly.
I attach the simple benchmark I used to test the changes. Before the patch
here are the results:
===> Integer lists
1 in l: 6.935
's' in l: 10.585
0 in l: 0.002
1.0 in l: 22.527
1L in l: 70.244
object() in l: 10.587
t1() in l: 14.433
t2() in l: 181.644
===> Float lists
1 in l: 17.131
's' in l: 44.034
0.8 in l: 0.002
1.0 in l: 9.372
1L in l: 96.680
object() in l: 70.232
t1() in l: 165.662
t2() in l: 181.558
After applying the patch:
===> Integer lists
1 in l: 6.928
's' in l: 0.001
0 in l: 0.001
1.0 in l: 6.929
1L in l: 6.928
object() in l: 0.002
t1() in l: 17.411
t2() in l: 139.246
===> Float lists
1 in l: 9.387
's' in l: 0.001
0.8 in l: 0.001
1.0 in l: 9.388
1L in l: 9.388
object() in l: 0.002
t1() in l: 129.031
t2() in l: 139.265
There is one slowdown ("t1() in l" for integer lists), which I can't explain,
but overall the pattern of speed-ups is clear. As you might expect, this
patch doesn't make much difference to the speed.pypy.org benchmarks.
The patch itself is here:
https://bitbucket.org/pypy/pypy/commits/599ed4285a6de348c7e7e732e303336d3160ce78
I welcome any comments on this. I don't pretend to know PyPy's internals
inside out, and I may have made one or more stupid changes in doing this. If
I have made a mistake, I'd love to know before I press on with other possible
changes!
Laurie
_______________________________________________
pypy-dev mailing list
pypy-dev@python.org
https://mail.python.org/mailman/listinfo/pypy-dev
