5 ms·

I regularly see people make this mistake and don't grasp it after correction. You could make a hash table with a constant time lookup, but the hash takes 1 hou

I regularly see people make this mistake and don't grasp it after correction. You could make a hash table with a constant time lookup, but the hash takes 1 hour. Big oh only tells you how it scales, not it's performance (runtime).

TeMPOraL 7y ago
It's not even that. You could have a normal hash table with a decent hashing function, and you'll still get beaten by a flat array for small n (hundreds, low thousands), because the array is contiguous in memory - so operations like search or moving stuff around after addition make extremely good use of CPU's cache.
- dmoy 7y ago
  > the array is contiguous in memory - so operations like search or moving stuff around after addition make extremely good use of CPU's cache Also - if I see someone try to use a linked list for an enormous data structure again.... Wow it does not scale worth crap because it turns out that the hardware is actually important, and contiguous memory is amazing.
  - TeMPOraL 7y ago
    Oh god. Don't talk to me about linked lists. One of the bigger performance improvements I've made in a certain company is taking the code working with lots of numerical data in linked lists because they had easier syntax, and rewriting it using honest-to-god, contiguous-memory arrays of doubles. After that, we could process three orders of magnitude more numbers per operation, and one order of magnitude more of operations, and we still came ahead.
    - matwood 7y ago
      Maybe you knew the scale up front, but if you didn’t the easier syntax was the right first choice. It may have been the right first choice because it was easier to code even with the scale known up front. Only after measuring and understanding the trade offs should the easier to reason about code have been removed. IMO, thinking about and understanding these trade offs is one of the main differentiators between a junior and senior developer.
      - TeMPOraL 7y ago
        > IMO, thinking about and understanding these trade offs is one of the main differentiators between a junior and senior developer. I agree, but in a way opposite to what you intended. An experienced developer[0] should be able to look at a situation like this and realize that few more minutes of focus can yield a better (array-based vs. list-based) implementation[1]. There are no downsides to that (arrays were only slightly less convenient in that case, syntax-wise), improvements occur regardless of scale. The list-based solution was a bad one at the scale it was originally written for handling. I believe a hallmark of an experienced developer is writing performant code from the get-go; this is accomplished by not making stupid mistakes like this, and it costs pretty much nothing in terms of coding time or code complexity. All it takes is a little knowledge and caring about the product's performance. -- [0] - I hesitate to use the word "senior", because to me, whether it means anything depends on the company one works in. In many, a "senior" developer is just the one that came before all the "junior" hires, and it doesn't matter that that developer is a fresh bootcamp graduate. And once you can put "senior X developer" on your CV, it's likely your next job will give you seniorship immediately as well. [1] - and an extra few more minutes would give an implementation that doesn't allocate new memory unnecessarily - also a huge performance win.
        codr7 7y ago
        The most important lesson I've learned from 34 years of writing software, it's to stop pretending I know shit about the problem I'm trying to solve before I have written an actual working solution. Which means getting there asap is top priority and nothing else matters. Sometimes that code runs fast enough, often it turns out I'm solving the wrong problem which means performance doesn't matter at all.
  - alexis_fr 7y ago
    > if I see someone use a linked list Or a hashmap to prepare 3 variables to pass to Json serialization.
    - leetrout 7y ago
      I think that hits the human factor of software development where it is easier to conceptualize your hashmap will become that JSON object. Curious - what would be your solution? Just creating the json directly as strings / bytes?
      - dasyatidprime 7y ago
        Unsorted-array-based maps are sometimes used in the Java world, and for two or three elements will have much less overhead than hash tables. For instance, fastutil has http://fastutil.di.unimi.it/docs/it/unimi/dsi/fastutil/objects/Object2ObjectArrayMap.html http://fastutil.di.unimi.it/docs/it/unimi/dsi/fastutil/objec.... The map interface and encapsulation into a single “object” is the same. It occurs to me that I don't know whether any of the major dynamic language implementations with maps/dicts/hashes as a central data structure use a similar approach for very small ones… huh.
  - jayd16 7y ago
    In this case complexity analysis would tell you that.
- deathanatos 7y ago
  > by a flat array for small n (hundreds, low thousands) Some of us are working in, say, Python. A flat array can outperform at small n, yes, but people overestimate where the tradeoff point is. It's at <5 items: # A list of [0, 1, 2, 3, 4] In [10]: linear = list(range(5)) # A hash set, same thing. In [11]: hashing = set(range(5)) # 44ns / linear search In [12]: %timeit 3 in linear 44.2 ns ± 0.412 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each) # 25ns / hash search! In [13]: %timeit 3 in hashing 25 ns ± 0.6 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each) The hash set outperforms the linear search by nearly 2x, on a list of size 5! (The performance is similar for other common types that end up in hashes, like strings.) "It's Python!", you say. "Too much chasing of pointers to PyObjects destroy the cache!" And yes, they do; but many people are working in high-level languages like Python or Ruby. But, for those that aren't, if we repeat the above exercise in Rust, yes the tradeoff will move up, but only to ~60 items, not hundreds or low thousands: test tests::bench_hash_int ... bench: 14 ns/iter (+/- 1) test tests::bench_linear_int ... bench: 19 ns/iter (+/- 3) If you're thinking that somehow accessing the middle item each time bestows an unfair advantage to the hash table, randomizing the desired item doesn't help, either: test tests::bench_rng_hash_int ... bench: 19 ns/iter (+/- 2) test tests::bench_rng_linear_int ... bench: 24 ns/iter (+/- 2) And looking for an item not in the list is definitely not favorable to the linear search. (It's the worst case.) In my experience, it's almost always easiest to pay mild attention to big O concerns, and just use the appropriate data structure for the problem at hand. Cache effects mattering is either rare (you're writing a RESTful microserving to push cat pictures, a cache isn't going to matter once we hit this mobile devices 20 second network latency!) or highly context dependent (your line of work is always low-level, and these crop up more often, and you're consequently on the lookout for it; I don't think this applies to most of us, however). The code used, in case you wish to find fault with it: https://github.com/thanatos/hash-vs-linear https://github.com/thanatos/hash-vs-linear
- justinmeiners 7y ago
  I was using an extreme example to illustrate. I definitely agree.

TeMPOraL 7y ago

It's not even that. You could have a normal hash table with a decent hashing function, and you'll still get beaten by a flat array for small n (hundreds, low thousands), because the array is contiguous in memory - so operations like search or moving stuff around after addition make extremely good use of CPU's cache.

dmoy 7y ago
> the array is contiguous in memory - so operations like search or moving stuff around after addition make extremely good use of CPU's cache Also - if I see someone try to use a linked list for an enormous data structure again.... Wow it does not scale worth crap because it turns out that the hardware is actually important, and contiguous memory is amazing.
- TeMPOraL 7y ago
  Oh god. Don't talk to me about linked lists. One of the bigger performance improvements I've made in a certain company is taking the code working with lots of numerical data in linked lists because they had easier syntax, and rewriting it using honest-to-god, contiguous-memory arrays of doubles. After that, we could process three orders of magnitude more numbers per operation, and one order of magnitude more of operations, and we still came ahead.
  - matwood 7y ago
    Maybe you knew the scale up front, but if you didn’t the easier syntax was the right first choice. It may have been the right first choice because it was easier to code even with the scale known up front. Only after measuring and understanding the trade offs should the easier to reason about code have been removed. IMO, thinking about and understanding these trade offs is one of the main differentiators between a junior and senior developer.
    - TeMPOraL 7y ago
      > IMO, thinking about and understanding these trade offs is one of the main differentiators between a junior and senior developer. I agree, but in a way opposite to what you intended. An experienced developer[0] should be able to look at a situation like this and realize that few more minutes of focus can yield a better (array-based vs. list-based) implementation[1]. There are no downsides to that (arrays were only slightly less convenient in that case, syntax-wise), improvements occur regardless of scale. The list-based solution was a bad one at the scale it was originally written for handling. I believe a hallmark of an experienced developer is writing performant code from the get-go; this is accomplished by not making stupid mistakes like this, and it costs pretty much nothing in terms of coding time or code complexity. All it takes is a little knowledge and caring about the product's performance. -- [0] - I hesitate to use the word "senior", because to me, whether it means anything depends on the company one works in. In many, a "senior" developer is just the one that came before all the "junior" hires, and it doesn't matter that that developer is a fresh bootcamp graduate. And once you can put "senior X developer" on your CV, it's likely your next job will give you seniorship immediately as well. [1] - and an extra few more minutes would give an implementation that doesn't allocate new memory unnecessarily - also a huge performance win.
      - codr7 7y ago
        The most important lesson I've learned from 34 years of writing software, it's to stop pretending I know shit about the problem I'm trying to solve before I have written an actual working solution. Which means getting there asap is top priority and nothing else matters. Sometimes that code runs fast enough, often it turns out I'm solving the wrong problem which means performance doesn't matter at all.
- alexis_fr 7y ago
  > if I see someone use a linked list Or a hashmap to prepare 3 variables to pass to Json serialization.
  - leetrout 7y ago
    I think that hits the human factor of software development where it is easier to conceptualize your hashmap will become that JSON object. Curious - what would be your solution? Just creating the json directly as strings / bytes?
    - dasyatidprime 7y ago
      Unsorted-array-based maps are sometimes used in the Java world, and for two or three elements will have much less overhead than hash tables. For instance, fastutil has http://fastutil.di.unimi.it/docs/it/unimi/dsi/fastutil/objects/Object2ObjectArrayMap.html http://fastutil.di.unimi.it/docs/it/unimi/dsi/fastutil/objec.... The map interface and encapsulation into a single “object” is the same. It occurs to me that I don't know whether any of the major dynamic language implementations with maps/dicts/hashes as a central data structure use a similar approach for very small ones… huh.
- jayd16 7y ago
  In this case complexity analysis would tell you that.
deathanatos 7y ago
> by a flat array for small n (hundreds, low thousands) Some of us are working in, say, Python. A flat array can outperform at small n, yes, but people overestimate where the tradeoff point is. It's at <5 items: # A list of [0, 1, 2, 3, 4] In [10]: linear = list(range(5)) # A hash set, same thing. In [11]: hashing = set(range(5)) # 44ns / linear search In [12]: %timeit 3 in linear 44.2 ns ± 0.412 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each) # 25ns / hash search! In [13]: %timeit 3 in hashing 25 ns ± 0.6 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each) The hash set outperforms the linear search by nearly 2x, on a list of size 5! (The performance is similar for other common types that end up in hashes, like strings.) "It's Python!", you say. "Too much chasing of pointers to PyObjects destroy the cache!" And yes, they do; but many people are working in high-level languages like Python or Ruby. But, for those that aren't, if we repeat the above exercise in Rust, yes the tradeoff will move up, but only to ~60 items, not hundreds or low thousands: test tests::bench_hash_int ... bench: 14 ns/iter (+/- 1) test tests::bench_linear_int ... bench: 19 ns/iter (+/- 3) If you're thinking that somehow accessing the middle item each time bestows an unfair advantage to the hash table, randomizing the desired item doesn't help, either: test tests::bench_rng_hash_int ... bench: 19 ns/iter (+/- 2) test tests::bench_rng_linear_int ... bench: 24 ns/iter (+/- 2) And looking for an item not in the list is definitely not favorable to the linear search. (It's the worst case.) In my experience, it's almost always easiest to pay mild attention to big O concerns, and just use the appropriate data structure for the problem at hand. Cache effects mattering is either rare (you're writing a RESTful microserving to push cat pictures, a cache isn't going to matter once we hit this mobile devices 20 second network latency!) or highly context dependent (your line of work is always low-level, and these crop up more often, and you're consequently on the lookout for it; I don't think this applies to most of us, however). The code used, in case you wish to find fault with it: https://github.com/thanatos/hash-vs-linear https://github.com/thanatos/hash-vs-linear
justinmeiners 7y ago
I was using an extreme example to illustrate. I definitely agree.