6 ms·
> it would be pointless for me to try to code an optimized quick sort in it. Perhaps more so than you've realised. Hint: Rust's old unstable sort was its take
by tialaramex 1y ago
> it would be pointless for me to try to code an optimized quick sort in it.
Perhaps more so than you've realised. Hint: Rust's old unstable sort was its take on the pattern defeating quicksort. The article is talking about the new unstable sort which has better performance for most inputs.
Rust uses monomorphization and its function types are unique, so the trick you're used to with a macro is just how everything works all the time in Rust.
- bluecalm 1y agoThe trick is not about macros but about removing function calls altogether. Macros are there only to generate functions for specific types. The way the trick works is to implement the stack manually and put indexes there instead of passing them as function arguments. This removes a lot of overhead and makes the implementation I linked to significantly faster than C's and C++'s standard library implementation.
- tialaramex 1y agoBecause this function is internal Rust doesn't need to give it the Itanium ABI so the recursion won't incur the overhead you're imagining.
- bluecalm 1y agoIt's not my imagination. It's my experience with benchmarking it. The implementation I linked to is 2x (or even more on relatively short arrays) faster than standard library C++ sort. Is Rust sort as fast?