Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Diving into the world of hash tables

zeroequalsfalse.press

Post reply on HN
Print view View original

71–80 of 107 posts

Re: Diving into the world of hash tables

#71

Post by rectangletangle »

hueving wrote: post #68
rectangletangle wrote: post #56

Earlier quoted context omitted.

When the name `a` is assigned the value of `baz`, Python is setting a key name `a` in the local dictionary (hash table) `locals()`. Basically `a = 1` is syntactic sugar for `locals()['a'] = 1` >>> a Traceback (most recent call last): File " ", line 1, in NameError: name 'a' is not defined >>> locals()['a'] = 113 >>> a 113 >>> One interesting side-effect of this is you can assign names that are not valid Python syntax…

locals() is presented to the user as a dictionary, but is that the way cpython actually works with it internally? I've run into weird GC issues that imply it's not a normal dictionary and it's just presented to the user as one for programattic access.

That's a good question, I'm pretty sure it's not a normal dictionary. However, I'd have to go through the CPython source to confirm. Maybe someone who's more familiar with CPython's implementation will chime in.

Re: Diving into the world of hash tables

#72

Post by ubernostrum »

bogomipz wrote: post #53
rectangletangle wrote: post #42

Earlier quoted context omitted.

Nearly every expression in high-level languages relies on multiple hash lookups. This is part of the reason these languages are regarded as "slow." I suppose you could use a tree in place, and get reasonable performance. However the hash table's nature allows you to pretty much throw more memory at the problem in exchange for speed (though this is hardly unique to this particular data structure). For instance `a = fo…

>"For instance `a = foo.bar.baz` in Python involves 3 hash gets (local scope, foo scope, then bar scope), and a single set operation (local scope)" Can you explain where exactly and why a set operation is performed? Thanks.

It's easier if you look at the bytecode produced for the expression, which is:

    1           0 LOAD_NAME                0 (foo)
                2 LOAD_ATTR                1 (bar)
                4 LOAD_ATTR                2 (baz)
                6 STORE_NAME               3 (a)
                8 LOAD_CONST               0 (None)
               10 RETURN_VALUE
The CPython implementation is a stack-based virtual machine. The first instruction here, LOAD_NAME, pushes co_names['foo'] (basically, whatever 'foo' is bound to in local scope) to the top of the stack. That's at least one hash table lookup, since the scope is a hash table mapping names to values. Then LOAD_ATTR replaces the top-of-stack value with the value of its 'bar' attribute. That's another hash table lookup, since attributes are a hash table mapping names to values. Then another LOAD_ATTR to get to 'baz', that's another hash table lookup. Then STORE_NAME binds the value at the top of the stack to the name given as an argument ('a'). That's an insert or update of a hash table.

So, the expression 'a = foo.bar.baz' involves at least three hash table lookups and one insert or update.

Re: Diving into the world of hash tables

#73

Post by adrianN »

hueving wrote: post #67
obstinate wrote: post #50

Earlier quoted context omitted.

In fact, what performance oriented devs need to be taught about these days is how to not use hash tables, or, more generally, dictionaries. They are a super-easy data structure to reach for, but often it is possible to arrange your data such that their use is unnecessary. One example that was brought up elsewhere in the thread is the way python looks up variables in successive scope dictionaries. This is obviously te…

99.999% of projects are not going to have any meaningful hot path in variable resolution. If your program is sensitive to that, even a simple GC pause is going to destroy your performance and you need to be out of managed memory languages at that point. There are a lot of reasons python can be slow, but this is far from one of them.

Eh, one of the standard performance tips for hot loops is to store everything relevant, including functions, in local variables because the interpreter looks in the local dictionary first. The last time I optimized Python code that made a significant difference.

Re: Diving into the world of hash tables

#74

Post by adrianN »

haburka wrote: post #64
obstinate wrote: post #50

Earlier quoted context omitted.

In fact, what performance oriented devs need to be taught about these days is how to not use hash tables, or, more generally, dictionaries. They are a super-easy data structure to reach for, but often it is possible to arrange your data such that their use is unnecessary. One example that was brought up elsewhere in the thread is the way python looks up variables in successive scope dictionaries. This is obviously te…

Are you serious that dictionaries are a problem for performance oriented developers? Performance oriented devs should be concerned with bottlenecks, not incredibly minute details. There's almost no situation I can think of where smallish dictionaries are much better or worse than any other data structure when it comes to performance. Of course, if you're writing a compiler then it can be a serious difference. Most de…

Yes, if you write performance sensitive code you have to be very careful with dictionaries. See for example this nice talk by Chandler Carruth https://www.youtube.com/watch?v=fHNmRkzxHWs

Re: Diving into the world of hash tables

#75

Post by jcranberry »

rectangletangle wrote: post #42
mabbo wrote: post #5

I think when the author says "underrated", what they mean is "I didn't realize how important this is". Hash tables are used everywhere, by everyone, for a lot of things. Maybe they don't give it enough time in school for people to realize it is the king of practical software development.

Nearly every expression in high-level languages relies on multiple hash lookups. This is part of the reason these languages are regarded as "slow." I suppose you could use a tree in place, and get reasonable performance. However the hash table's nature allows you to pretty much throw more memory at the problem in exchange for speed (though this is hardly unique to this particular data structure). For instance `a = fo…

The way you phrase that makes it seem as if the language being slow is somehow the fault of hash tables when it's the use of dynamic linking.

Re: Diving into the world of hash tables

#76

Post by yxhuvud »

taeric wrote: post #12

Hash Table has basically been elevated to a general idea lately. Pretty much anyone that is looking for an association between keys and values is using what they will call a hash table. To that end, few people actually know anything about how they are implemented. (And apologies if this comes across as negative, I do not mean it as a value judgement.) This was different back when you would pick something like an alis…

Depends on implementations of the alist and of the hash table. It is even fully possible that the small hash table will use an alist for the cases with few (and small) elements.

Re: Diving into the world of hash tables

#77

Post by flukus »

hueving wrote: post #67
obstinate wrote: post #50

Earlier quoted context omitted.

In fact, what performance oriented devs need to be taught about these days is how to not use hash tables, or, more generally, dictionaries. They are a super-easy data structure to reach for, but often it is possible to arrange your data such that their use is unnecessary. One example that was brought up elsewhere in the thread is the way python looks up variables in successive scope dictionaries. This is obviously te…

99.999% of projects are not going to have any meaningful hot path in variable resolution. If your program is sensitive to that, even a simple GC pause is going to destroy your performance and you need to be out of managed memory languages at that point. There are a lot of reasons python can be slow, but this is far from one of them.

> 99.999% of projects are not going to have any meaningful hot path in variable resolution.

It won't show up in the hot path because the performance cost so pervasive that profiling tools will ignore it, it's everywhere and you can't escape it without compiler optimizations. This cost will be in the hot and cold paths. This and data locality are the two biggest performance issues in dynamic languages and a lot of effort goes into compiling it out.

Here is a good article on how V8 tries to deal with it: https://www.html5rocks.com/en/tutorials/speed/v8/

For statically compiled languages it can show up but often you'll have to write a dictionary free version to see it. Some profiling I've done with c# at various times over the years shows that it's slower than a list until you have more than 50 to 100 items. The caveat is that I normally keep the dictionary version because it's more semantically correct.

Re: Diving into the world of hash tables

#78

Post by klodolph »

hueving wrote: post #68
rectangletangle wrote: post #56

Earlier quoted context omitted.

When the name `a` is assigned the value of `baz`, Python is setting a key name `a` in the local dictionary (hash table) `locals()`. Basically `a = 1` is syntactic sugar for `locals()['a'] = 1` >>> a Traceback (most recent call last): File " ", line 1, in NameError: name 'a' is not defined >>> locals()['a'] = 113 >>> a 113 >>> One interesting side-effect of this is you can assign names that are not valid Python syntax…

locals() is presented to the user as a dictionary, but is that the way cpython actually works with it internally? I've run into weird GC issues that imply it's not a normal dictionary and it's just presented to the user as one for programattic access.

No, that's not how it works internally. The Python compiler resolves all local variables at compile-time. You can see this for yourself by defining a simple function f, import dis, and calling dis.dis(f).

Global variables use a dictionary, however. The disassembly actually looks similar for both.

Re: Diving into the world of hash tables

#79

Post by adrian17 »

rectangletangle wrote: post #56
bogomipz wrote: post #53

Earlier quoted context omitted.

>"For instance `a = foo.bar.baz` in Python involves 3 hash gets (local scope, foo scope, then bar scope), and a single set operation (local scope)" Can you explain where exactly and why a set operation is performed? Thanks.

When the name `a` is assigned the value of `baz`, Python is setting a key name `a` in the local dictionary (hash table) `locals()`. Basically `a = 1` is syntactic sugar for `locals()['a'] = 1` >>> a Traceback (most recent call last): File " ", line 1, in NameError: name 'a' is not defined >>> locals()['a'] = 113 >>> a 113 >>> One interesting side-effect of this is you can assign names that are not valid Python syntax…

This only works in global scope. It won't work in a function:

    def f():
        a = 5
        locals()['a'] = 6
        print(a) # 5
Inside a function, accesses/writes of locals use an internal array of local variables, to skip dicts. Same with constants. See:

https://github.com/python/cpython/blob/master/Python/ceval.c...

Post reply on HN