Hi Brian, On 03/25/2013 10:42 AM, bdkearns wrote:

Author: Brian Kearns <bdkearns@gmail.com> Branch: Changeset: r62735:1f7ca87c6780 Date: 2013-03-25 05:37 -0400 http://bitbucket.org/pypy/pypy/changeset/1f7ca87c6780/

Log: use jit.loop_unrolling_heuristic where possible

diff --git a/pypy/module/__builtin__/functional.py b/pypy/module/__builtin__/functional.py --- a/pypy/module/__builtin__/functional.py +++ b/pypy/module/__builtin__/functional.py @@ -202,8 +202,8 @@

@specialize.arg(2) def min_max(space, args, implementation_of): - if not jit.we_are_jitted() or (jit.isconstant(len(args.arguments_w)) and - len(args.arguments_w) == 2): + if not jit.we_are_jitted() or jit.loop_unrolling_heuristic( + args.arguments_w, len(args.arguments_w)): return min_max_unroll(space, args, implementation_of) else: return min_max_normal(space, args, implementation_of)

This is a very risky change. The unrolled pseudo-code for min (max is equivalent) with 5 elements is something like this: m = l0 if l1 < m: m = l1 if l2 < m m = l2 if l3 < m m = l3 if l3 < m m = l3 (the comparisons of course have to go through the object space, everything is more complex, but the control flow is essentially like this.) Every comparison can go either way, that means that there are 2**4 paths through this code, and it's completely unpredictable which of the paths is taken. Therefore it can lead to potentially too much code being generated. I think for min and max in particular the compromise of just unrolling twice is acceptable. BTW, another optimization that might be interesting for min/max is to add fast paths with listview_int/listview_str if no key and no comparison are given. Cheers, Carl Friedrich

diff --git a/pypy/objspace/std/dictmultiobject.py b/pypy/objspace/std/dictmultiobject.py --- a/pypy/objspace/std/dictmultiobject.py +++ b/pypy/objspace/std/dictmultiobject.py @@ -10,8 +10,7 @@ from rpython.rlib.debug import mark_dict_non_null from rpython.tool.sourcetools import func_with_new_name

-from rpython.rlib import rerased -from rpython.rlib import jit +from rpython.rlib import rerased, jit

def _is_str(space, w_key): return space.is_w(space.type(w_key), space.w_str) @@ -29,9 +28,6 @@ space.is_w(w_lookup_type, space.w_float) )

- -DICT_CUTOFF = 5 - @specialize.call_location() def w_dict_unrolling_heuristic(w_dct): """ In which cases iterating over dict items can be unrolled. @@ -39,7 +35,8 @@ an actual dict """ return jit.isvirtual(w_dct) or (jit.isconstant(w_dct) and - w_dct.length() <= DICT_CUTOFF) + w_dct.length() <= jit.UNROLL_CUTOFF) +

class W_DictMultiObject(W_Object): from pypy.objspace.std.dicttype import dict_typedef as typedef @@ -761,7 +758,8 @@ update1_keys(space, w_dict, w_data)

-@jit.look_inside_iff(lambda space, w_dict, w_data: w_dict_unrolling_heuristic(w_data)) +@jit.look_inside_iff(lambda space, w_dict, w_data: + w_dict_unrolling_heuristic(w_data)) def update1_dict_dict(space, w_dict, w_data): iterator = w_data.iteritems() while 1: diff --git a/pypy/objspace/std/intobject.py b/pypy/objspace/std/intobject.py --- a/pypy/objspace/std/intobject.py +++ b/pypy/objspace/std/intobject.py @@ -183,7 +183,8 @@

# helper for pow() -@jit.look_inside_iff(lambda space, iv, iw, iz: jit.isconstant(iw) and jit.isconstant(iz)) +@jit.look_inside_iff(lambda space, iv, iw, iz: + jit.isconstant(iw) and jit.isconstant(iz)) def _impl_int_int_pow(space, iv, iw, iz): if iw < 0: if iz != 0: diff --git a/pypy/objspace/std/kwargsdict.py b/pypy/objspace/std/kwargsdict.py --- a/pypy/objspace/std/kwargsdict.py +++ b/pypy/objspace/std/kwargsdict.py @@ -95,7 +95,8 @@ def getitem_str(self, w_dict, key): return self._getitem_str_indirection(w_dict, key)

- @jit.look_inside_iff(lambda self, w_dict, key: jit.isconstant(self.length(w_dict)) and jit.isconstant(key)) + @jit.look_inside_iff(lambda self, w_dict, key: + jit.isconstant(self.length(w_dict)) and jit.isconstant(key)) def _getitem_str_indirection(self, w_dict, key): keys, values_w = self.unerase(w_dict.dstorage) result = [] 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 @@ -18,7 +18,6 @@ from pypy.objspace.std.stdtypedef import StdTypeDef, SMM from sys import maxint

-UNROLL_CUTOFF = 5

class W_AbstractListObject(W_Object): __slots__ = () @@ -43,7 +42,7 @@ return W_ListObject.from_storage_and_strategy(space, storage, strategy)

@jit.look_inside_iff(lambda space, list_w, sizehint: - jit.isconstant(len(list_w)) and len(list_w) < UNROLL_CUTOFF) + jit.loop_unrolling_heuristic(list_w, len(list_w))) def get_strategy_from_list_objects(space, list_w, sizehint): if not list_w: if sizehint != -1: @@ -950,7 +949,7 @@ raise NotImplementedError("abstract base class")

@jit.look_inside_iff(lambda space, w_list, list_w: - jit.isconstant(len(list_w)) and len(list_w) < UNROLL_CUTOFF) + jit.loop_unrolling_heuristic(list_w, len(list_w))) def init_from_list_w(self, w_list, list_w): l = [self.unwrap(w_item) for w_item in list_w] w_list.lstorage = self.erase(l) @@ -999,7 +998,7 @@ return self.wrap(r)

@jit.look_inside_iff(lambda self, w_list: - jit.isconstant(w_list.length()) and w_list.length() < UNROLL_CUTOFF) + jit.loop_unrolling_heuristic(w_list, w_list.length())) def getitems_copy(self, w_list): return [self.wrap(item) for item in self.unerase(w_list.lstorage)]

@@ -1008,7 +1007,7 @@ return [self.wrap(item) for item in self.unerase(w_list.lstorage)]

@jit.look_inside_iff(lambda self, w_list: - jit.isconstant(w_list.length()) and w_list.length() < UNROLL_CUTOFF) + jit.loop_unrolling_heuristic(w_list, w_list.length())) def getitems_fixedsize(self, w_list): return self.getitems_unroll(w_list)

diff --git a/pypy/objspace/std/tupleobject.py b/pypy/objspace/std/tupleobject.py --- a/pypy/objspace/std/tupleobject.py +++ b/pypy/objspace/std/tupleobject.py @@ -10,8 +10,6 @@ from rpython.rlib import jit from rpython.tool.sourcetools import func_with_new_name

-# Tuples of known length up to UNROLL_TUPLE_LIMIT have unrolled certain methods -UNROLL_TUPLE_LIMIT = 10

class W_AbstractTupleObject(W_Object): __slots__ = () @@ -85,15 +83,8 @@ start, stop = normalize_simple_slice(space, length, w_start, w_stop) return space.newtuple(w_tuple.wrappeditems[start:stop])

-THRESHOLD = 7 - -def unroll_tuple_contains(space, w_tuple, w_obj): - if (jit.isconstant(w_tuple) or jit.isvirtual(w_tuple) and - len(w_tuple.wrappeditems) < THRESHOLD): - return True - return False - -@jit.look_inside_iff(unroll_tuple_contains) +@jit.look_inside_iff(lambda space, w_tuple, w_obj: + jit.loop_unrolling_heuristic(w_tuple, len(w_tuple.wrappeditems))) def contains__Tuple_ANY(space, w_tuple, w_obj): for w_item in w_tuple.wrappeditems: if space.eq_w(w_item, w_obj): @@ -128,10 +119,8 @@ return mul_tuple_times(space, w_tuple, w_times)

def tuple_unroll_condition(space, w_tuple1, w_tuple2): - lgt1 = len(w_tuple1.wrappeditems) - lgt2 = len(w_tuple2.wrappeditems) - return ((jit.isconstant(lgt1) and lgt1 <= UNROLL_TUPLE_LIMIT) or - (jit.isconstant(lgt2) and lgt2 <= UNROLL_TUPLE_LIMIT)) + return jit.loop_unrolling_heuristic(w_tuple1, len(w_tuple1.wrappeditems)) or \ + jit.loop_unrolling_heuristic(w_tuple2, len(w_tuple2.wrappeditems))

@jit.look_inside_iff(tuple_unroll_condition) def eq__Tuple_Tuple(space, w_tuple1, w_tuple2): @@ -151,7 +140,7 @@ def _make_tuple_comparison(name): import operator op = getattr(operator, name) - # + @jit.look_inside_iff(tuple_unroll_condition) def compare_tuples(space, w_tuple1, w_tuple2): items1 = w_tuple1.wrappeditems @@ -184,8 +173,7 @@ return space.wrap(hash_tuple(space, w_tuple.wrappeditems))

@jit.look_inside_iff(lambda space, wrappeditems: - jit.isconstant(len(wrappeditems)) and - len(wrappeditems) < UNROLL_TUPLE_LIMIT) + jit.loop_unrolling_heuristic(wrappeditems, len(wrappeditems))) def hash_tuple(space, wrappeditems): # this is the CPython 2.4 algorithm (changed from 2.3) mult = 1000003 diff --git a/rpython/rlib/jit.py b/rpython/rlib/jit.py --- a/rpython/rlib/jit.py +++ b/rpython/rlib/jit.py @@ -206,13 +206,13 @@ return NonConstant(False) isvirtual._annspecialcase_ = "specialize:call_location"

-LIST_CUTOFF = 2 +UNROLL_CUTOFF = 5

@specialize.call_location() def loop_unrolling_heuristic(lst, size): """ In which cases iterating over items of lst can be unrolled """ - return isvirtual(lst) or (isconstant(size) and size <= LIST_CUTOFF) + return isvirtual(lst) or (isconstant(size) and size <= UNROLL_CUTOFF)

class Entry(ExtRegistryEntry): _about_ = hint _______________________________________________ pypy-commit mailing list pypy-commit@python.org http://mail.python.org/mailman/listinfo/pypy-commit