long(string, base) now takes time linear in len(string) when base is a

power of 2.  Enabled the tail end of test_long() in pickletester.py
because it no longer takes forever when run from test_pickle.py.

2 files changed, 2 insertions, 14 deletions

diff --git a/Lib/pickle.py b/Lib/pickle.py
index ba0e38b..4e80cca 100644
--- a/Lib/pickle.py
+++ b/Lib/pickle.py
@@ -1427,9 +1427,6 @@ def encode_long(x):
     binary = _binascii.unhexlify(ashex)
     return binary[::-1]
 
-# XXX OOPS!  This is still quadratic-time.  While hex(n) is linear-time
-# XXX in the # of digits in n, long(s, 16) is still quadratic-time
-# XXX in len(s).
 def decode_long(data):
     r"""Decode a long from a two's complement little-endian binary string.
 
@@ -1453,7 +1450,7 @@ def decode_long(data):
     if nbytes == 0:
         return 0L
     ashex = _binascii.hexlify(data[::-1])
-    n = long(ashex, 16) # quadratic time
+    n = long(ashex, 16) # quadratic time before Python 2.3; linear now
     if data[-1] >= '\x80':
         n -= 1L << (nbytes * 8)
     return n
diff --git a/Lib/test/pickletester.py b/Lib/test/pickletester.py
index 6615307..2a1ca17 100644
--- a/Lib/test/pickletester.py
+++ b/Lib/test/pickletester.py
@@ -247,7 +247,7 @@ class AbstractPickleTests(unittest.TestCase):
 
     def test_long(self):
         for proto in protocols:
-            # 256 bytes is where LONG4 begins
+            # 256 bytes is where LONG4 begins.
             for nbits in 1, 8, 8*254, 8*255, 8*256, 8*257:
                 nbase = 1L << nbits
                 for npos in nbase-1, nbase, nbase+1:
@@ -257,20 +257,11 @@ class AbstractPickleTests(unittest.TestCase):
                         self.assertEqual(n, got)
         # Try a monster.  This is quadratic-time in protos 0 & 1, so don't
         # bother with those.
-        # XXX Damn.  pickle.py is still quadratic-time here, due to
-        # XXX long(string, 16).  cPickle runs this in an eyeblink, but I
-        # XXX gave up waiting for pickle.py to get beyond "loading".  Giving
-        # XXX up for now.
-        return
-        print "building long"
         nbase = long("deadbeeffeedface", 16)
         nbase += nbase << 1000000
         for n in nbase, -nbase:
-            print "dumping"
             p = self.dumps(n, 2)
-            print "loading"
             got = self.loads(p)
-            print "checking"
             self.assertEqual(n, got)
 
     def test_reduce(self):