3 ms·

Using sort to filter duplicates is horribly worse compared to hashing (javascript for instance). Is this really true? A sort plus a linear scan has very low c

by panic 12y ago

Using sort to filter duplicates is horribly worse compared to hashing (javascript for instance). Is this really true? A sort plus a linear scan has very low constant time factors, good cache locality (depending on the sorting algorithm used), and no need to allocate if you're sorting in place. I've seen good results using sort to filter duplicates in my own performance-sensitive code. Are you saying this technique is "horribly worse" based on your experience or intuition?

FreezerburnV 12y ago
Just to add to the discussion: you're likely correct, based on this SO question: http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array http://stackoverflow.com/questions/11227809/why-is-processin... It will likely get faster the more duplicates you have, as it allows the CPU to predict a branch more reliably several times before being wrong and having to re-do some of its prediction stuff. (note that I'm not experienced with optimizing stuff, dealing with cache optimizations, etc., but I have read a decent amount, and I did take a class about CPU architecture) I would also suspect that hashing might end up messing with memory all over the place, causing the cache to be partly useless.
- ygra 12y ago
  That question (and answer) is probably not relevant here. The important thing is likely cache locality, not branch prediction (as the test case is very different in that question, amplifying branch misprediction issues, which won't be the issue here).
chapel 12y ago
In the case of the JS solution, it runs horribly and is highly inefficient.[0] For non-hot code, it is perfectly fine, but in this case, inside of a main loop like this it is a waste of cpu cyles. Compare the amount of forests here: $ node orig-magicForest.js 117 155 106 total forests: 1522899 { goats: 0, wolves: 0, lions: 223 } total time: 816ms $ node new-magicForest.js 117 155 106 total forests: 428 { goats: 0, wolves: 0, lions: 223 } total time: 6ms [0] https://gist.github.com/chapel/1c038b2bf64b3037aaea https://gist.github.com/chapel/1c038b2bf64b3037aaea

by panic 12y ago

FreezerburnV 12y ago

Just to add to the discussion: you're likely correct, based on this SO question: http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array http://stackoverflow.com/questions/11227809/why-is-processin... It will likely get faster the more duplicates you have, as it allows the CPU to predict a branch more reliably several times before being wrong and having to re-do some of its prediction stuff. (note that I'm not experienced with optimizing stuff, dealing with cache optimizations, etc., but I have read a decent amount, and I did take a class about CPU architecture) I would also suspect that hashing might end up messing with memory all over the place, causing the cache to be partly useless.

ygra 12y ago
That question (and answer) is probably not relevant here. The important thing is likely cache locality, not branch prediction (as the test case is very different in that question, amplifying branch misprediction issues, which won't be the issue here).

chapel 12y ago

In the case of the JS solution, it runs horribly and is highly inefficient.[0] For non-hot code, it is perfectly fine, but in this case, inside of a main loop like this it is a waste of cpu cyles. Compare the amount of forests here: $ node orig-magicForest.js 117 155 106 total forests: 1522899 { goats: 0, wolves: 0, lions: 223 } total time: 816ms $ node new-magicForest.js 117 155 106 total forests: 428 { goats: 0, wolves: 0, lions: 223 } total time: 6ms [0] https://gist.github.com/chapel/1c038b2bf64b3037aaea https://gist.github.com/chapel/1c038b2bf64b3037aaea