3 ms·

Few major points: Using sort to filter duplicates is horribly worse compared to hashing (javascript for instance). Java version has rather poor impl, it's int

by xxs 12y ago

Few major points: Using sort to filter duplicates is horribly worse compared to hashing (javascript for instance). Java version has rather poor impl, it's interesting to see the GC+allocation cost and the GC type used. C++ version does not use really use func. prog in find_stable_forests and meal...

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 xxs 12y ago

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