On Sun, 8 Nov 2015 11:28 pm, Chris Angelico wrote: > On Sun, Nov 8, 2015 at 10:19 PM, BartC <b...@freeuk.com> wrote: >> I've never understood why this seems to be necessary in Python. Why do >> names have to be looked up? (I'm assuming this is searching by name in >> some sort of table.) > > Yes, if by "searching" you include hash-table lookup. A CPython > dictionary is a *highly* optimized data structure, specifically > because it's used virtually everywhere (I understand Lua's "table" > type has similar optimizations for the same reason). In the common > case, where your names come from literal text in the module, the > strings used for the lookup will be interned constants, and their > hashes will have been precalculated and stored, so the lookup is > pretty easy. So it's a constant-time operation, and while that > constant may be larger than a simple offset-and-fetch, it's still > pretty fast in the overall scheme of things.
*Usually*. There are pathological cases -- if you're unlucky enough, or malicious enough, to have a whole lot of names with the same hash value, the look-up degrades to a linear search. More importantly, consider the case of a function referring to a variable named "spam". In principle, at least, it may need to: - search the local namespace; - search the namespace of one or more enclosing functions; - search the global namespace; - search the built-in namespace; before locating the variable's value. In practice, most Python implementations will provide at least one optimization: local variables are recognised and searched using an offset-and-fetch model. Similarly for method calls: spam.eggs needs to: - search the instance dict and slots; - search the class dict; - search the dict for each additional superclass; where searching involves more than just a hash table lookup. It also involves checking the classes for __getattribute__ and __getattr__ methods, checking for descriptors, and more. The whole lookup process is quite complicated, and little of it can be done at compile time. -- Steven -- https://mail.python.org/mailman/listinfo/python-list
