3 ms·

I benchmarked it several times in the past and couldn't replicate std::sort being faster (GCC with high optimization settings). Anyway both are slow. If you nee

I benchmarked it several times in the past and couldn't replicate std::sort being faster (GCC with high optimization settings). Anyway both are slow. If you need fast sort you need an implementation without any function calls (no recursive calls) and both the pivot choice and the chunk size at which insert sort kicks in optimized to your data and hardware. My experience is that you can beat built in sort by 2x to 3x.

lumost 6y ago
How would you perform this optimization? If it’s the same data getting sorted, why not put it in an ordered data structure?
- mhh__ 6y ago
  Andrei Alexanrescu has a talk on doing this - he calls them metaparameters e.g. where a hybrid sort chooses to change algorithm. One library I have exploits the fact that D templates are embarrassingly better than C++'s, so you can actually benchmark a template against it's parameters in a clean manner without overhead - that could be anything from a size_t parameter for a sort or a datastructure for example. enum cpuidRange = iota(1, 10).map!(ctfeRepeater).array; @TemplateBenchmark!(0, cpuidRange) @FunctionBenchmark!("Measure", iota(1, 10), (_) => [1, 2, 3, 4])(meas) static int sum(string asmLine)(inout int[] input) { int tmp; foreach (i; input) { tmp += i; mixin("asm { ", asmLine, ";}"); } return tmp; } This made-up (pointless) benchmark measures how insert a number of cpuid instructions into the loop of a summing function affects it's runtime. My library writes the code from your specification as above to generate the instantiations and loop to measure the performance. As you might guess, the answer is a lot (CPUID is slow and serializing). edit: https://github.com/maxhaton/chimpfella https://github.com/maxhaton/chimpfella - I haven't bothered to add pmc support yet

lumost 6y ago

How would you perform this optimization? If it’s the same data getting sorted, why not put it in an ordered data structure?

mhh__ 6y ago
Andrei Alexanrescu has a talk on doing this - he calls them metaparameters e.g. where a hybrid sort chooses to change algorithm. One library I have exploits the fact that D templates are embarrassingly better than C++'s, so you can actually benchmark a template against it's parameters in a clean manner without overhead - that could be anything from a size_t parameter for a sort or a datastructure for example. enum cpuidRange = iota(1, 10).map!(ctfeRepeater).array; @TemplateBenchmark!(0, cpuidRange) @FunctionBenchmark!("Measure", iota(1, 10), (_) => [1, 2, 3, 4])(meas) static int sum(string asmLine)(inout int[] input) { int tmp; foreach (i; input) { tmp += i; mixin("asm { ", asmLine, ";}"); } return tmp; } This made-up (pointless) benchmark measures how insert a number of cpuid instructions into the loop of a summing function affects it's runtime. My library writes the code from your specification as above to generate the instantiations and loop to measure the performance. As you might guess, the answer is a lot (CPUID is slow and serializing). edit: https://github.com/maxhaton/chimpfella https://github.com/maxhaton/chimpfella - I haven't bothered to add pmc support yet