Re: [pypy-dev] [pypy-commit] pypy default: Unroll list.count() when the list is virtual or very small and constant lenght
Hi Alex, please revert this change, it can lead to combinatorial explosion: it can give a bridge per pattern of where in the list the object is found. Cheers, Carl Friedrich On 29/08/13 23:47, alex_gaynor wrote:
Author: Alex Gaynor <alex.gaynor@gmail.com> Branch: Changeset: r66432:185512e0c4df Date: 2013-08-29 15:47 -0700 http://bitbucket.org/pypy/pypy/changeset/185512e0c4df/
Log: Unroll list.count() when the list is virtual or very small and constant lenght
diff --git a/pypy/module/pypyjit/test_pypy_c/test_containers.py b/pypy/module/pypyjit/test_pypy_c/test_containers.py --- a/pypy/module/pypyjit/test_pypy_c/test_containers.py +++ b/pypy/module/pypyjit/test_pypy_c/test_containers.py @@ -241,3 +241,22 @@ loop, = log.loops_by_filename(self.filepath) ops = loop.ops_by_id('getitem', include_guard_not_invalidated=False) assert log.opnames(ops) == [] + + def test_list_count_virtual_list(self): + def main(n): + i = 0 + while i < n: + i += [n].count(n) + return i + + log = self.run(main, [1000]) + assert log.result == main(1000) + loop, = log.loops_by_filename(self.filepath) + assert loop.match(""" + i7 = int_lt(i5, i6) + guard_true(i7, descr=...) + guard_not_invalidated(descr=...) + i9 = int_add(i5, 1) + --TICK-- + jump(..., descr=...) + """) diff --git a/pypy/objspace/std/listobject.py b/pypy/objspace/std/listobject.py --- a/pypy/objspace/std/listobject.py +++ b/pypy/objspace/std/listobject.py @@ -562,6 +562,8 @@ 'L.reverse() -- reverse *IN PLACE*' self.reverse()
+ @jit.look_inside_iff(lambda self, space, w_value: + jit.loop_unrolling_heuristic(self, self.length(), UNROLL_CUTOFF)) def descr_count(self, space, w_value): '''L.count(value) -> integer -- return number of occurrences of value''' _______________________________________________ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit
2013/8/30 Carl Friedrich Bolz <cfbolz@gmx.de>
Hi Alex,
please revert this change, it can lead to combinatorial explosion: it can give a bridge per pattern of where in the list the object is found.
Doesn't list.count() traverse all the list in all cases? -- Amaury Forgeot d'Arc
On 30/08/13 12:58, Amaury Forgeot d'Arc wrote:
2013/8/30 Carl Friedrich Bolz <cfbolz@gmx.de <mailto:cfbolz@gmx.de>>
Hi Alex,
please revert this change, it can lead to combinatorial explosion: it can give a bridge per pattern of where in the list the object is found.
Doesn't list.count() traverse all the list in all cases?
It looks like this: count = 0 i = 0 while i < self.length(): if space.eq_w(self.getitem(i), w_value): count += 1 i += 1 So there's a guard_true/false for every item. Note that even changing to: count += space.eq_w(self.getitem(i), w_value) does not fix this, because the guard is coming from inside space.istrue, or space.eq Cheers, Carl Friedrich
Hi Carl, I wonder if there's some sub-set of cases we can still unroll in. The particular code this was for is: https://bitbucket.org/pypy/pypy/src/default/lib-python/2.7/uuid.py#cl-130 . I wonder if there are cases where the list is both virtual *and* we aren't able to constant fold some of the space.eq_w()? Alex On Fri, Aug 30, 2013 at 5:31 AM, Carl Friedrich Bolz <cfbolz@gmx.de> wrote:
On 30/08/13 12:58, Amaury Forgeot d'Arc wrote:
2013/8/30 Carl Friedrich Bolz <cfbolz@gmx.de <mailto:cfbolz@gmx.de>>
Hi Alex,
please revert this change, it can lead to combinatorial explosion: it can give a bridge per pattern of where in the list the object is
found.
Doesn't list.count() traverse all the list in all cases?
It looks like this:
count = 0 i = 0 while i < self.length(): if space.eq_w(self.getitem(i), w_value): count += 1 i += 1
So there's a guard_true/false for every item.
Note that even changing to:
count += space.eq_w(self.getitem(i), w_value)
does not fix this, because the guard is coming from inside space.istrue, or space.eq
Cheers,
Carl Friedrich
_______________________________________________ pypy-dev mailing list pypy-dev@python.org http://mail.python.org/mailman/listinfo/pypy-dev
-- "I disapprove of what you say, but I will defend to the death your right to say it." -- Evelyn Beatrice Hall (summarizing Voltaire) "The people's good is the highest law." -- Cicero GPG Key fingerprint: 125F 5C67 DFE9 4084
On 30/08/13 15:09, Alex Gaynor wrote:
Hi Carl,
I wonder if there's some sub-set of cases we can still unroll in. The particular code this was for is: https://bitbucket.org/pypy/pypy/src/default/lib-python/2.7/uuid.py#cl-130 .
This is a completely indirect and way too clever way to express what is meant. I have absolutely no pity for this code being slow. Let's rewrite it to simply be more explicit, even if it's a few lines longer.
I wonder if there are cases where the list is both virtual *and* we aren't able to constant fold some of the space.eq_w()?
Yes, there can be, it's easy to write. Even the uuid case has the combinatorial problem, it's just that we expect people to not pass in random combinations of arguments. Cheers, Carl Friedrich
Fixing the code is fine with me, does someone want to help get that patch upstream into CPython so we don't have to worry about losing our modifications when we upgrade the stdlib? Alex On Fri, Aug 30, 2013 at 9:47 AM, Carl Friedrich Bolz <cfbolz@gmx.de> wrote:
On 30/08/13 15:09, Alex Gaynor wrote:
Hi Carl,
I wonder if there's some sub-set of cases we can still unroll in. The particular code this was for is:
https://bitbucket.org/pypy/pypy/src/default/lib-python/2.7/uuid.py#cl-130.
This is a completely indirect and way too clever way to express what is meant. I have absolutely no pity for this code being slow. Let's rewrite it to simply be more explicit, even if it's a few lines longer.
I wonder if there are cases where the list is both virtual *and* we aren't able to constant fold some of the space.eq_w()?
Yes, there can be, it's easy to write. Even the uuid case has the combinatorial problem, it's just that we expect people to not pass in random combinations of arguments.
Cheers,
Carl Friedrich
-- "I disapprove of what you say, but I will defend to the death your right to say it." -- Evelyn Beatrice Hall (summarizing Voltaire) "The people's good is the highest law." -- Cicero GPG Key fingerprint: 125F 5C67 DFE9 4084
participants (3)
-
Alex Gaynor -
Amaury Forgeot d'Arc -
Carl Friedrich Bolz