New Grad vs. Senior Dev

No. You wouldn't want people slipping on stage.

I understand this as phenomenon as the new grad and the senior developer are optimizing for different things. The new grad is focused solely on the asymptotic complexity of the code. It doesn't matter how slow or how complicated it is in practice, they are solely focused on using the fastest data structure asymptotically.

The senior developer optimizes a different set of criteria:

  1) How hard is it to understand the code and make sure it's correct.
  2) How fast the algorithm in practice.

There are several different reasons why the performance of the algorithm in practice is different than the performance in theory. The most obvious reason is big-O notation does not capture lots of details that matter in practice. An L1 cache read and a disk IOP are both treated the same in theory.

A second reason is the implementation of a complex algorithm is more likely to be incorrect. In some cases this leads to bugs which you can find with good testing. In other cases, it leads to a performance degradation that you'll only find if you run a profiler.

I one time saw a case where a function for finding the right shard for a given id was too slow. The code needed to find from a list of id ranges, which one a given id fell into. The implementation would sort the id ranges once ahead of time and then run a binary search of the ranges to find the right shard for the id. One engineer took a look at this, realized that we were doing the shard lookups sequentially, and decided to perform the shard lookups in parallel. This made the code faster, but we still would have needed to double the size of our servers in order to provide enough additional CPU to make the code fast enough.

Another engineer hooked the code up into a profiler and made a surprising discovery. It turns out the implementation of the function was subtlety incorrect and it was sorting the id ranges on every call. This happened because the code sorted the id ranges inside of a Scala mapValues function. It turns out that mapValues does not actually map a function over the values of a hash table. It instead returns an object that when you look up a key, it will look up the value in the original hash table, then apply the function[0]. This results in the function being called on every read.

The solution was to replace mapValues with map. This dramatically improved the performance of the system and basically brought the CPU usage of the system down to zero. Notably, it would have been impossible to discover this issue without either knowing the difference between map and mapValues, or by using a profiler.

[0] https://blog.bruchez.name/2013/02/mapmap-vs-mapmapvalues.htm...

> 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

  # 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

I see it differently. Knowledge =/= understanding. There are plenty of ppl who know a lot but have little understanding.

Put another way, knowledge is the nodes. Understanding is grasping the connections. Understanding is the higher power. Understanding is where the magic happens.

Wisdom? Wisdom is next level understanding. It's the maturity of developing connection within the connections.

Shockingly,

    InStr(, "docum") = 0

I'm a dev with some grey hair who feels it would have been useful for all that fantastic domain knowledge from Paterson to get documented in a code comment.

I'd love to hear if either of them ever went back and did that?