5 ms·

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 o

• shishy 9y ago
  The author of the article does not say underrated at all from what I can see; just something the OP included in his title. Your point still stands, though.
  • iainmerrick 9y ago
    Yeah, that's a weird title! I assumed it must be the actual title of the post, but no.
• lsadam0 9y ago
  Really. Hash tables are one of my most used data structures.
  • obstinate 9y ago
    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 terrible for performance, and that's a big part of why Python is slow. But how are other languages fast? Doesn't every language have to resolve variable names to memory locations? Well, yes, but fast languages do this mostly at compile time. How? 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. And you've switched from looking up things in tables to operating directly on registers and memory locations. BTW, this has nothing to do with high-versus-low level. It's more about how mutable the process of name resolution is after program compilation. One could theoretically write an assembly language where memory locations are names, not numbers. If reflective features like runtime scope editing are available, this would be a very low-level language that still requires some kind of dictionary lookup at runtime.
    • flukus 9y ago
      > 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. A lot of devs are completely unaware of what's happening at the layer of abstraction below them and this is one of the ways that comes out. The number of elements it takes before hash tables are faster than iterating through an array can be surprisingly large and yet it's one of the first "optimizations" that get made. Some other related problems are not knowing how expensive network calls are, not knowing what the ORM is doing, caching in memory even though the database already is and more. They just don't think about performance issues in code they don't write.
    • haburka 9y ago
      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 developers don't write compilers though.
      • adrianN 9y ago
        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 https://www.youtube.com/watch?v=fHNmRkzxHWs
      • obstinate 9y ago
        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.
    • hueving 9y ago
      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.
• Cyph0n 9y ago
  Agreed. I mean, for example, doesn't the entire Lua language revolve around hash tables?
  • throwaway2016a 9y ago
    Same with PHP.
• rectangletangle 9y ago
  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 = foo.bar.baz` in Python involves 3 hash gets (local scope, foo scope, then bar scope), and a single set operation (local scope). This is part of the reason Python programs can be optimized by assigning a deep attribute lookup to the local scope outside of a loop's scope, and it will yield improved performance relative to doing the deep attribute lookup inside the loop's scope. a = foo.bar.baz for _ in range(20): print(a) vs for _ in range(20): print(foo.bar.baz)
  • bogomipz 9y ago
    >"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.
    • rectangletangle 9y ago
      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 "<stdin>", line 1, in <module> 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 explicitly. For example: >>> locals()['foo-bar'] = 1 >>> locals()['foo-bar'] 1 >>> foo-bar Traceback (most recent call last): File "<stdin>", line 1, in <module> NameError: name 'foo' is not defined >>> The name `foo-bar` can't be literally referenced, because the interpreter attempts to interpret it as the subtraction operation `foo - bar`.
      • hueving 9y ago
        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.
• dang 9y ago
  OK, we changed the title to the first sentence of the article.