Another thing that we noted is that sorting takes additional 14 milliseconds, which compared to much more sophisticated scoring is quite large. I thought that it should be due to cost of transition from native qsort code to JS code thats implements comparator function. And out of curiosity I've proposed trying pure JS sorting instead.
The results were interesting. At first it was much slower than built-in qsort, but Vlad then discovered that it's actually faster on random data (I haven't asked by how much, but that's not very important). All this led me to the following conclusions:
- Naive qsort on real world non-random data may be 100 times slower than proper qsort implementation. Which is understandable, but this is the first time I've met such case personally.
- I was right about pure JS qsort being able to beat C qsort, that has to use slow and barely optimize-able comparator.
- In general, state of the art javascript interpreters are indeed approaching speeds of optimized C. If only we had Ruby interpreter of same quality :)
So when next time your JS code will depend on fast sorting, consider picking pure JS sort implementation, but pick wisely. Also don't forget that there are still some very slow JS interpreters around (yes, I'm talking about 'the-cursed-browser').
BTW, I'm sure same applies to C standard qsort. In cases where comparator is quite simple, the implementation that is able to inline comparator should be much faster. For gpicker I've stolen source of glibc's qsort implementation and made sure that it's able to inline comparator.
No comments:
Post a Comment