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

81–90 of 107 posts

Re: Diving into the world of hash tables

#81

Post by taeric »

yxhuvud wrote: post #76
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.

Fair. I was making a huge assumption that the alist would be implemented as you statically see it in code.

My point was supposed to be that an alist really has an obvious implementation, whereas a hashtable actually does not. My main objection being that there is a ton of glossing over what goes into an actual hashtable. While I would expect someone to be able to do a basic alist implementation, I have grown away from expecting folks to do a basic hash table.

Re: Diving into the world of hash tables

#82

Post by [deleted] »

rectangletangle wrote: post #71
hueving wrote: post #68

Earlier quoted context omitted.

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.

[deleted]

Re: Diving into the world of hash tables

#83

Post by adrian17 »

obstinate wrote: post #50
lsadam0 wrote: post #37

Earlier quoted context omitted.

Really. Hash tables are one of my most used data structures.

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…

> Well, I'm not an expert in this, but at a high level, each variable is assigned a location in memory or registers, and then future references to that variable are rewritten to refer to the memory location by register name or memory address. This takes the whole "looking up a name" issue out of the path of work that has to get done at runtime.

Python does this for local variable names in functions. Because of this, moving a tight loop from global scope to a function can make it a couple percent faster.

Re: Diving into the world of hash tables

#84

Post by mpweiher »

jcranberry wrote: post #75
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…

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.

That's because it is the hash tables.

You can have dynamic binding (assuming that's what you meant, dynamic linking is something else) with way fewer hash lookups.

Re: Diving into the world of hash tables

#85

Post by dang »

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.

OK, we changed the title to the first sentence of the article.

Re: Diving into the world of hash tables

#86

Post by flukus »

iainmerrick wrote: post #47
zzzcpan wrote: post #22

Earlier quoted context omitted.

Built-in implementations usually are kind of slow, waste memory, have broken iterators [1], even in modern languages. If either of those things are important - it's better to do some research and maybe even invent your own. [1] when you can't both iterate and insert items consistently in the same loop

"Usually", really? Which languages are you thinking of, and have you benchmarked them?

It's often true due to a few factors. One is that they are safe, whereas a specific use case may not need the same level of safety. They generally optimize for the general case as well, but in your own code you can optimize for the very specific use case you have. One I ran into many years ago was implementing my own singly linked list by adding the next pointer to another piece of data. In this one specific case it was worth removing another layer of indirection. I was still young though, so there were probably even better ways of handling it.

I have only encountered these scenarios a small handful of times, but I'm not a very low level developer.

Re: Diving into the world of hash tables

#87

Post by obstinate »

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…

Well of course. :) If you don't write perf sensitive code, don't worry about perf. But if you do, in many cases avoiding hash tables can become important.

Re: Diving into the world of hash tables

#88

Post by obstinate »

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.

To be clear, I don't think this is the only thing that makes python slow. It's probably one of the top five or ten things preventing it from being fast, though.

Re: Diving into the world of hash tables

#89

Post by panic »

VHRanger wrote: post #26

If you care about performance, it's important to note how the underlying representation of a dictionary data structure. For instance, the unordered_hash_map in C++ is based around a linked list of key/value pair buckets. This means iterating through the keys or values is very slow (lots of cache misses!), but insertion is fast. Retrieving a key is O(logn) but a very slow O(logn), because of the cache misses. Other im…

For instance, the unordered_hash_map in C++ is based around a linked list of key/value pair buckets. This means iterating through the keys or values is very slow (lots of cache misses!), but insertion is fast.

Has this changed recently? Last time I used unordered_map, insertion was also slow because it had to allocate a linked list entry for every item in the hash table.

Re: Diving into the world of hash tables

#90

Post by whatshisface »

hprotagonist wrote: post #4

"this is a data structure that is at the guts of basically every python object. Classes are dicts. Modules are dicts. Packages are probably dicts. Don't worry though, it's underrated!" @_@

Python has its own very cleverly optimized dict implementation:

http://pybites.blogspot.com/2008/10/pure-python-dictionary-i...

Post reply on HN