Re: [pypy-dev] [pypy-commit] pypy default: use jit.loop_unrolling_heuristic where possible

Carl Friedrich Bolz Mon, 25 Mar 2013 05:26:39 -0700

Hi Brian,

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

Author: Brian Kearns <[email protected]>
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 isequivalent) 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)


[email protected]_inside_iff(lambda space, w_dict, w_data: 
w_dict_unrolling_heuristic(w_data))
[email protected]_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()
[email protected]_inside_iff(lambda space, iv, iw, iz: jit.isconstant(iw) and 
jit.isconstant(iz))
[email protected]_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
-
[email protected]_inside_iff(unroll_tuple_contains)
[email protected]_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
[email protected]
http://mail.python.org/mailman/listinfo/pypy-commit

        
_______________________________________________
pypy-dev mailing list
[email protected]
http://mail.python.org/mailman/listinfo/pypy-dev

Re: [pypy-dev] [pypy-commit] pypy default: use jit.loop_unrolling_heuristic where possible

Reply via email to