[Patches] [ python-Patches-401394 ] lookdict optimizations
noreply@sourceforge.net
noreply@sourceforge.net
Fri, 18 May 2001 12:01:49 -0700
Patches item #401394, was updated on 2000-09-01 14:13
You can respond by visiting:
http://sourceforge.net/tracker/?func=detail&atid=305470&aid=401394&group_id=5470
Category: core (C code)
Group: None
Status: Open
>Resolution: Out of Date
Priority: 5
Submitted By: Vladimir Marangozov (marangoz)
Assigned to: Fred L. Drake, Jr. (fdrake)
Summary: lookdict optimizations
Initial Comment:
----------------------------------------------------------------------
>Comment By: Tim Peters (tim_one)
Date: 2001-05-18 12:01
Message:
Logged In: YES
user_id=31435
Marked Out of Date: I've fiddled the dict code quite a bit
in the meantime. Changing the computation of the initial
table index reduced the # of collisions, so the case this
is aiming at is probably less frequent now. The guts of
the loop have been reordered to check for dummy last in
every case, so "inlining the first collision probe"
probably doesn't buy anything anymore. Using a length
check is probably still helpful: you're effectively
creating a Py_EQ string richcmp here, but inlined. It will
be less helpful once strings grow a tp_richcompare slot,
because that will almost certainly do a Py_EQ length check
too (e.g., Martin's pending patch does).
----------------------------------------------------------------------
Comment By: Fred L. Drake, Jr. (fdrake)
Date: 2001-02-19 13:19
Message:
This patch optimizes what appears to be a small corner case (string keys in a string-only dict that have hash collisions), but the cause can indeed come up.
I need to spend a little time instrumenting the code to determine how often this corner case occurs, and haven't had time to do that yet.
----------------------------------------------------------------------
Comment By: Jeremy Hylton (jhylton)
Date: 2001-02-09 16:11
Message:
Is this patch still revelant?
----------------------------------------------------------------------
Comment By: Fred L. Drake, Jr. (fdrake)
Date: 2000-09-25 18:52
Message:
It's postponed since I've not had time to run performance tests to measure the corner case it aims to improve. It turns out that generating the test data I need takes a long time (I need hash collisions of identifier-like strings). I just need to be able to let my generator run for a long time (it was generating more collisions than I'd expected, but I don't know how many off-hand).
Another interesting metric would be to examine the .pyc files generated from the standard library and find out if there are any string hash collisions there -- if not, or if very few, it's not worth the added complexity.
----------------------------------------------------------------------
Comment By: Thomas Wouters (twouters)
Date: 2000-09-25 14:38
Message:
Shouldn't this patch be either postponed or checked in?
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2000-09-15 11:18
Message:
Accepted. Assuming you've tested this, it looks fine to me.
Can you time this a bit?
There's one niggling issue: some people think that before you do memcmp() you should manually compare the first character. Others think that's unnecessary (since a good compiler can inline memcmp anyway). (It's also a bit scary if the size is zero.) So please ignore this but keep it in mind for timing experiments. :)
----------------------------------------------------------------------
Comment By: Fred L. Drake, Jr. (fdrake)
Date: 2000-09-14 13:51
Message:
Guido, please review (since Vladimir's away).
----------------------------------------------------------------------
Comment By: Fred L. Drake, Jr. (fdrake)
Date: 2000-09-14 09:26
Message:
Revised patch:
Instead of defining a function to do the fast string comparison, use a macro, but let it use the documented string object API (PyString_GET_SIZE(), PyString_AS_STRING()) instead of breaking the encapsulation in the code. This avoids all function calls to do the string compare, except memcmp() (which good compilers can inline anyway).
Vladimir, take a look at this; if you're happy, I'm happy, and you can check it in. Thanks!
----------------------------------------------------------------------
Comment By: Vladimir Marangozov (marangoz)
Date: 2000-09-05 06:08
Message:
Argh! These Web interfaces strike again - forgot to login.
----------------------------------------------------------------------
Comment By: Nobody/Anonymous (nobody)
Date: 2000-09-05 06:05
Message:
Correct!
But then, aren't the current "else" if(cmp == 0) clauses risky after
PyObject_Compare()? An exception may be set in external code
while making Object_Compare() to return 0! Perhaps not in Python
source, but in buggy extensions. lookdict() will then overlook this "hit".
Patch updated, without "else" clauses and with the 1st char check in
string_compare_equal().
----------------------------------------------------------------------
Comment By: Guido van Rossum (gvanrossum)
Date: 2000-09-04 06:45
Message:
Quick comments: we should *always* call PyErr_Occurred() after PyObject_Compare() (and PyErr_Clear() if PyErr_Occurred() returned true). PyErr_Compare() really doesn't expect a pending exception coming in and so *not* clearing the error might break the *next* PyErr_Compare() call. (This doesn't happen typically but PyObject_Compare() can execute arbitrary code, some of which might call PyErr_Occurred() without calling PyErr_Clear() first.)
----------------------------------------------------------------------
Comment By: Vladimir Marangozov (marangoz)
Date: 2000-09-03 21:09
Message:
Let's add a comment, although this has been raised on python-dev.
This patch proposes a couple of ideas for optimizing & speeding dict
lookups -- not all of them need to be applied though.
- clear the eventual errors from Object_Compare only on need
(this logic needs to be double-checked once again to see whether it
really works)
- defer variable initializations after the most common return cases
- specialize string_compare() for lookdict_string. The test comparing
the first char, before calling memcmp(), can be added too.
- inline the first item probe in PyDict_GetItem. This saves a func call
for the most common case (common to lookdict & lookdict_string).
----------------------------------------------------------------------
You can respond by visiting:
http://sourceforge.net/tracker/?func=detail&atid=305470&aid=401394&group_id=5470