Mailman 3 May 2001 - Python-Dev

Special-casing "O"
by Martin v. Loewis 29 May '01

29 May '01

> Special-casing the snot out of "O" looks like a winner <wink>: I have a patch on SF that takes this approach: http://sourceforge.net/tracker/index.php?func=detail&aid=427190&group_id=54… The idea is that functions can be declared as METH_O, instead of METH_VARARGS. I also offer METH_l, but this is currently not used. The approach could be extended to other signatures, e.g. METH_O_opt_O (i.e. "O|O"). Some signatures cannot be changed into special-calls, e.g. "O!", or "ll|l". In the PyXML test suite, "O" is indeed the most frequent case (72%), and it is primarily triggered through len (26%), append (24%), and ord (6%). These are the only functions that make use of the new calling conventions at the moment. If you look at the patch, you'll see that it is quite easy to change a method to use a different calling convention (basically just remove the PyArg_ParseTuple call). To measure the patch, I use the script from time import clock indices = [1] * 20000 indices1 = indices*100 r1 = [1]*60 def doit(case): s = clock() i = 0 if case == 0: f = ord for i in indices1: f("o") elif case == 1: for i in indices: l = [] f = l.append for i in r1: f(i) elif case == 2: f = len for i in indices1: f("o") f = clock() return f - s for i in xrange(10): print "%.3f %.3f %.3f" % (doit(0),doit(1),doit(2)) Without the patch, (almost) stock CVS gives 2.190 1.800 2.240 2.200 1.800 2.220 2.200 1.800 2.230 2.220 1.800 2.220 2.200 1.800 2.220 2.200 1.790 2.240 2.200 1.790 2.230 2.200 1.800 2.220 2.200 1.800 2.240 2.200 1.790 2.230 With the patch, I get 1.440 1.330 1.460 1.420 1.350 1.440 1.430 1.340 1.430 1.510 1.350 1.460 1.440 1.360 1.470 1.460 1.330 1.450 1.430 1.330 1.420 1.440 1.340 1.440 1.430 1.340 1.430 1.410 1.340 1.450 So the speed-up is roughly 30% to 50%, depending on how much work the function has to do. Please let me know what you think. Regards, Martin

6 20

Special-casing "O"
by Martin v. Loewis 28 May '01

28 May '01

> How is METH_O different than METH_OLDARGS? METH_O will raise an exception if the function is called with more than one argument, without calling the function. METH_OLDARGS will pass a tuple in this case. I believe you cannot distinguish between a single tuple argument and an invocation with multiple arguments in a METH_OLDARGS function, is that true? Regards, Martin

3 2

Next dict crusade
by Tim Peters 27 May '01

27 May '01

I'm still trying to work off the backlog of ignored dict ideas. Way back here: http://mail.python.org/pipermail/python-dev/2000-December/011085.html Christian Tismer suggested using polynomial division instead of multiplication for generating the probe sequence, as a way to get all the bits of the hash code into play. The desirability of doing that is illustrated by, e.g., this program: def f(keys): from time import clock d = {} s = clock() for k in keys: d[k] = k f = clock() print "build time %.3f" % (f-s) s = clock() for k in keys: assert d.has_key(k) f = clock() print "search time %.3f" % (f-s) # Excellent performance. keys = range(20000) for i in range(5): f(keys) # Terrible performance; > 500x slower. keys = [i << 16 for i in range(20000)] for i in range(5): f(keys) Christian had a very clever (cheap and effective) solution: Old algortithm (multiplication): shift the index left by 1 if index > mask: xor the index with the generator polynomial New algorithm (division): if low bit of index set: xor the index with the generator polynomial shift the index right by 1 where "index" should really read "increment", and unlike today we do not mask off any of the bits of the initial increment (and that's what lets *all* the bits of the hash code come into play; there's no point to doing this otherwise). I've since discovered that it's got a fatal rare flaw: the new algorithm can generate a 0 increment, while the old algorithm cannot. Example: poly is 131 and hash is 145. Because we don't mask off any bits in computing the initial increment, the initial increment is computed as incr = hash ^ (hash >> 3) == 145 ^ (145 >> 3) == 145 ^ 18 == 131 == poly So if we don't hit on the first probe, the new if low bit of index set: xor the index with the generator polynomial shift the index right by 1 business sets incr to 0, and the result is an infinite loop (0 is a fixed point). I hate to add another branch to this. As is, the existing branch in both the old and new ways is of the worst possible kind: it's taken half the time, with a pseudo-random distribution. So there's not a branch-prediction gimmick on earth it won't fool. Note that there's no reasonable way to identify "bad values" for incr before the loop starts, either -- there's really no way to tell whether incr mod poly is 0 without a loop to do division steps until incr < poly (if incr < poly and incr != 0, incr can never become 0, so there's no more need to test after reaching that point). Such a "pre loop" would cost more than the existing loop in most cases, as we usually get out of the existing loop today on its first iteration. But in that case, what am I worried about <wink>? time-for-a-checkin-ly y'rs - tim

1 0

Scanner
by Paul Prescod 26 May '01

26 May '01

What ever happened to the sre Scanner? It seemed like a good idea but it was not documented and it doesn't work for me. Is it just a case of nobody got around to the documentation or have we decided against it? Here's the code that doesn't work for me: from sre import Scanner scanner = Scanner([ (r"[a-zA-Z_]\w*", None), (r"\d+\.\d*", None), (r"\d+", None), (r"=|\+|-|\*|/", None), (r"\s+", None), ]) tokens, tail = scanner.scan("sum = 3*foo + 312.50 + bar") Traceback (most recent call last): File "junk.py", line 11, in ? tokens, tail = scanner.scan("sum = 3*foo + 312.50 + bar") File "c:\program files\python21\lib\sre.py", line 254, in scan action = self.lexicon[m.lastindex][1] TypeError: sequence index must be integer m.lastindex is None -- Take a recipe. Leave a recipe. Python Cookbook! http://www.ActiveState.com/pythoncookbook

2 1

Time for the yearly list.append() panic
by Mark Favas 26 May '01

26 May '01

[Tim wants to know whether his patch to listobject.c slows anything down on anyone's "oddball box"...] While in no way admitting that mine is an oddball box <wink>, it being a Tru64 Unix alpha processor machine, I do see a slowdown after applying the patch (measured on the test suite and on pystone). However, it's only of the order of 0.5 to 1%. slightly-oddly y'rs - Mark -- Mark Favas - m.favas(a)per.dem.csiro.au CSIRO, Private Bag No 5, Wembley, Western Australia 6913, AUSTRALIA

2 2

Time for the yearly list.append() panic
by Tim Peters 25 May '01

25 May '01

c.l.py has rediscovered the quadratic-time worst-case behavior of list.append(). That is, do list.append(x) in a long loop. Linux users don't see anything particularly bad no matter how big the loop. WinNT eventually displays clear quadratic-time behavior. Win9x dies surprisingly early with a MemoryError, despite gobs of memory free: turns out Win9x allocates hundreds of virtual heaps, isn't able to coalesce them, and you actually run out of *address space* (the whole 2GB user space gets fragmented beyond hope). People on other platforms have reported other bad behaviors over the years. I don't want to argue about this again <wink>, I just want to know whether the patch below slows anything down on your oddball box. It increases the over-allocation amount in several more layers. Also replaces integer * and / in the over-allocation computation by bit operations (integer / in particular is very slow on *some* boxes). Long-term we should teach PyMalloc about Python's realloc() abuses and craft a cooperative solution. Index: Objects/listobject.c =================================================================== RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v retrieving revision 2.92 diff -c -r2.92 listobject.c *** Objects/listobject.c 2001/02/12 22:06:02 2.92 --- Objects/listobject.c 2001/05/25 19:04:07 *************** *** 9,24 **** #include <sys/types.h> /* For size_t */ #endif ! #define ROUNDUP(n, PyTryBlock) \ ! ((((n)+(PyTryBlock)-1)/(PyTryBlock))*(PyTryBlock)) static int roundupsize(int n) { ! if (n < 500) return ROUNDUP(n, 10); else ! return ROUNDUP(n, 100); } #define NRESIZE(var, type, nitems) PyMem_RESIZE(var, type, roundupsize(nitems)) --- 9,30 ---- #include <sys/types.h> /* For size_t */ #endif ! #define ROUNDUP(n, nbits) \ ! ( ((n) + (1<<(nbits)) - 1) >> (nbits) << (nbits) ) static int roundupsize(int n) { ! if ((n >> 9) == 0) ! return ROUNDUP(n, 3); ! else if ((n >> 13) == 0) ! return ROUNDUP(n, 7); ! else if ((n >> 17) == 0) return ROUNDUP(n, 10); + else if ((n >> 20) == 0) + return ROUNDUP(n, 13); else ! return ROUNDUP(n, 18); } #define NRESIZE(var, type, nitems) PyMem_RESIZE(var, type, roundupsize(nitems))

2 2

Vacation
by Guido van Rossum 25 May '01

25 May '01

I will be on vacation next week without net access. Back on June 4th! There's a bunch of stuff that happened on the mailing list that I expect I won't get to -- I've got to finish up some high priority work for Digital Creations before I can leave. --Guido van Rossum (home page: http://www.python.org/~guido/)

1 0

May 25 is Towel Day (towelday.org)
by Ka-Ping Yee 25 May '01

25 May '01

If you have enjoyed Douglas Adams' works, please consider carrying or wearing a towel with you everywhere today, May 25, as a tribute and in his memory. For more about Towel Day, visit http://www.towelday.org/. My apologies for being off-topic. -- ?!ng

1 0

Odd message from test_dbm
by skip＠pobox.com 24 May '01

24 May '01

I just noticed this message when running make test: test test_dbm skipped -- /home/skip/src/python/dist/src/build/build/lib.linux-i686-2.1/dbm.so: undefined symbol: dbm_firstkey I'm running a vanilla Mandrake 8.0 system. Unfortunately, I can't check libc.so or /usr/lib/libgdbm.so because the Mandrake folks saw fit to strip them... Anybody else seen this? Skip

2 1

IPv6
by Guido van Rossum 24 May '01

24 May '01

What's out IPv6 story? I recall that someone once sent me patches, but they didn't work for me. Is it time to try again? In certain circles IPv6 support in Python would be enough to switch programming languages... :-) --Guido van Rossum (home page: http://www.python.org/~guido/)

7 10