Re:Blitsort: An ultra-fast in-place stable hybrid merge/quic...
by scandum on Friday December 02, 2022 @08:20AM
(#33830086)
>A nitpick, but my name is Orson Peters
I actually knew that, not sure what went wrong in my brain.
>I don't know, I only use a binary search when splitting up merges, and almost no time is spent in this routine.
You'll still get a definite speed-up, worth benching the difference just in case. I guess there's no easy way to avoid a binary search.
>I didn't do specific research into which effect it is, when I say ILP I also mean the memory effects of that.
They're indeed related. I did some empirical testing and I'm quite sure it's cache related. Thinking about it, one issue I may have had was not benching sorting 100M elements, which might be where a bidirectional partition might benefit on my system.
I actually knew that, not sure what went wrong in my brain.
>I don't know, I only use a binary search when splitting up merges, and almost no time is spent in this routine.
You'll still get a definite speed-up, worth benching the difference just in case. I guess there's no easy way to avoid a binary search.
>I didn't do specific research into which effect it is, when I say ILP I also mean the memory effects of that.
They're indeed related. I did some empirical testing and I'm quite sure it's cache related. Thinking about it, one issue I may have had was not benching sorting 100M elements, which might be where a bidirectional partition might benefit on my system.