[Patches] [Patch #101309] Specialization of dictionaries for strings.

[noreply@sourceforge.net]

Patch #101309 has been updated. 

Project: 
Category: core (C code)
Status: Open
Summary: Specialization of dictionaries for strings.

Follow-Ups:

Date: 2000-Aug-25 22:26
By: fdrake

Comment:
This patch introduces some changes to the builtin dictionary type.
These changes create a specialization of the type to better support
efficient use of dictionaries as a runtime implementation detail.

This patch causes all newly created dictionaries to be specialized for
string keys; dictionaries are converted (trivially) to handle
arbitrary keys as needed.  If a non-string is used as a key (even if
only doing a lookup and it fails), the dictionary is converted to a
normal dictionary.  To achieve faster performance, a specialized
version of the lookdict() function is used.  The specialized
implementation can assume two things that the "normal" implementation
cannot:

  - that all comparisons are always done using the
    PyString_Type.tp_compare function, avoiding some of the overhead
    of calling PyObject_Compare() and dereferencing the comparison
    function repeatedly, and

  - that the comparison function never raises an exception, since two
    strings can always be compared without an error.

Some debugging code added to dictobject.c shows that most dictionaries
created during the regression test are never converted to "normal"
dictionaries, but always only use strings as keys:

	created 115874 string dicts
	converted 2658 to normal dicts
	2.29% conversion rate

Additional performance tests should be made.  I expect that a patch
such as this is most valuable if additional code is needed to
robustify lookdict() to properly deal with exceptions from
user-defined comparison functions (tp_compare handlers of __cmp__()
functions in Python code).  The patch duplicates the logic of the
lookdict() function, which makes maintenance more tedious.

-------------------------------------------------------

-------------------------------------------------------
For more info, visit:

http://sourceforge.net/patch/?func=detailpatch&patch_id=101309&group_id=5470