"Eyal Lotem" <eyal.lotem@gmail.com> wrote:
On 6/10/07, Josiah Carlson <jcarlson@uci.edu> wrote:
"Eyal Lotem" <eyal.lotem@gmail.com> wrote:
B. Some lookups use static "literal" keys, and could benefit from accessing a dict item directly (very fast O(1) _worst_ case, without even a function call when done from the C side).
[snip]
What you are proposing is to add a level of indirection between some pointer in the dictionary to some special PyDictItem object. This will slow Python execution when such a thing is used. Why? The extra level of indirection requires another pointer following, as well as a necessary check on the bitmap you are proposing, nevermind the additional memory overhead of having the item (generally doubling the size of dictionary objects that use such 'exported' items).
You don't mention what algorithm/structure will allow for the accessing of your dictionary items in O(1) time, only that after you have this bitmap and dictioanry item thingy that it will be O(1) time (where dictionaries weren't already fast enough natively). I don't believe you have fully thought through this, but feel free to post C or Python source that describes your algorithm in detail to prove me wrong.
Only access of exported items is O(1) time (when accessed via your PyDictItem_obj->value), other items must be accessed normally and they take just as much time (or as I explained and you reiterated, a tad longer, as it requires a bitmap check and in the case of exported items another dereference).
But you still don't explain *how* these exported keys are going to be accessed. Walk me through the steps required to improve access times in the following case: def foo(obj): return obj.foo
You should note that Python's dictionary implementation has been tuned to work *quite well* for the object attribute/namespace case, and I would be quite surprised if anyone managed to improve upon Raymond's work (without writing platform-specific assembly).
Ofcourse - the idea is not to improve dict's performance with the normal way it is accessed, but to change the way it is accessed for the specific use-case of accessing static values in a static dict - which can be faster than even a fast dict lookup.
If I have a dictionary X, and X has exported keys, then whenever I access exported values in the dictionary via X[key], your proposed indirection will necessarily be slower than the current implementation.
The dict lookups in globals, builtins are all looking for literal static keys in a literal static dict. In this specific case, it is better to outdo the existing dict performance, by adding a special way to access such static keys in dicts - which insignificantly slows down access to the dict, but significantly speeds up this very common use pattern.
Please benchmark before you claim "insignificant" performance degredation in the general case. I claim that adding a level of indirection and the accessing of a bit array (which in C is technically a char array with every bit getting a full char, unless you use masks and shifts, which will be slower still) is necessarily slower than the access characteristics of current dictionaries. We can see this as a combination of an increase in the number of operations necessary to do arbitrary dictionary lookups, increased cache overhad of those lookups, as well as the delay and cache overhead of accessing the bit array.
Attribute lookups in the class dict are all literal/static key lookups in a static dict (though in order for a code object to know that it is a static dict, a psyco-like system is required. If such a system is used, all of those dict lookups can be made faster as well).
No, attribute lookups are not all literal/static key lookups. See getattr/setattr/delattr, operations on cls.__dict__, obj.__dict__, etc. From what I can gather (please describe the algorithm now that I have asked twice), the only place where there exists improvement potential is in the case of global lookups in a module. That is to say, if a function/method in module foo is accessing some global variable bar, the compiler can replace LOAD_GLOBAL/STORE_GLOBAL/DEL_GLOBAL with an opcode to access a special PyDictItem object that sits in the function/method cell variables, rather than having to look in the globals dictionary (that is attached to every function and method). - Josiah