News for hackers. Stuff that matters.
Re:New Grad vs. Senior Dev by TeMPOraL on Saturday March 28, 2020 @12:21PM (#22712110)
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.
Re:New Grad vs. Senior Dev by dmoy on Saturday March 28, 2020 @12:27PM (#22712152)
> 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.

Re:New Grad vs. Senior Dev by TeMPOraL on Saturday March 28, 2020 @12:32PM (#22712194)
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.
Re:New Grad vs. Senior Dev by matwood on Saturday March 28, 2020 @01:27PM (#22712648)
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.
Re:New Grad vs. Senior Dev by TeMPOraL on Saturday March 28, 2020 @01:37PM (#22712758)
> 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.

Re:New Grad vs. Senior Dev by codr7 on Saturday March 28, 2020 @04:14PM (#22713997)
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.
Re:New Grad vs. Senior Dev by jayd16 on Saturday March 28, 2020 @02:33PM (#22713228)
In this case complexity analysis would tell you that.
Re:New Grad vs. Senior Dev by alexis_fr on Saturday March 28, 2020 @12:54PM (#22712358)
> if I see someone use a linked list

Or a hashmap to prepare 3 variables to pass to Json serialization.

Re:New Grad vs. Senior Dev by leetrout on Saturday March 28, 2020 @01:22PM (#22712601)
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?

Re:New Grad vs. Senior Dev by dasyatidprime on Saturday March 28, 2020 @02:11PM (#22713030)
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/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.

Re:New Grad vs. Senior Dev by deathanatos on Saturday March 28, 2020 @01:45PM (#22712828)
> 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

Re:New Grad vs. Senior Dev by XelNika on Saturday March 28, 2020 @04:09PM (#22713960)
You only benchmarked the search itself, but in the real world it might also take time to set up the data. You can't really pinpoint a tradeoff point without knowing how many times a data structure will be used.

I ran your Python test on my machine and the hash set was faster in every case: 10x faster at size 50, 2x faster at size 5, 1.3x faster at size 3.

Re:New Grad vs. Senior Dev by deathanatos on Saturday March 28, 2020 @08:15PM (#22715310)
That's not a bad point, and perhaps I should test creation times too. (I wanted to ignore that s.t. the test isolated a single thing: searching / wasn't mixing two things together.) Both hashsets and vectors are O(n) in setup, and I'd mostly expect their real-world performance to be very similar: hash tables tend to use contiguous arrays for storage and vectors do by definition, both tend to overallocate (hash tables to prevent collisions, vectors to amortize appends to O(1)), so I'd expect the performance in the real-world to be similar. Vectors tend to insert in-order, though, whereas the insertions in hashsets would bounce around the table, so that might make it more interesting.
Re:New Grad vs. Senior Dev by XelNika on Saturday March 28, 2020 @08:33PM (#22715401)
Yes, it's always best to reduce the number of variables in benchmarking, but the setup makes a big difference when we are talking about tiny data sets.

I don't know how to test it properly, but I tried looping over both the initialisation and a single search, and the hash sets were much slower, so much so that hash sets trailed lists by microseconds at size 10000. In retrospect, making those data structures unsurprisingly dominated running time and the test kind of lost all meaning. It was clear, however, that it wouldn't take many searches for the hash sets to win, search times for lists were going through the roof.

Re:New Grad vs. Senior Dev by justinmeiners on Saturday March 28, 2020 @01:49PM (#22712857)
I was using an extreme example to illustrate. I definitely agree.