Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
some sort benchmarks
# Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz
# Arch Linux x86_64
# g++ (GCC) 6.2.1 20160830
# Crystal 0.19.4 (2016-10-07)
256 elements with original quick sort 702.73k (± 3.72%) 1.50× slower
256 elements with intro sort 1.05M (± 4.05%) fastest
256 elements with std::sort in cpp 845.94k (± 4.23%) 1.25× slower
256 elements with qsort in c 307.25k (± 5.24%) 3.43× slower
512 elements with original quick sort 320.05k (± 4.60%) 1.51× slower
512 elements with intro sort 483.13k (± 2.96%) fastest
512 elements with std::sort in cpp 368.24k (± 5.18%) 1.31× slower
512 elements with qsort in c 144.82k (± 2.49%) 3.34× slower
1024 elements with original quick sort 151.42k (± 2.52%) 1.46× slower
1024 elements with intro sort 221.27k (± 5.39%) fastest
1024 elements with std::sort in cpp 168.9k (± 3.60%) 1.31× slower
1024 elements with qsort in c 66.44k (± 3.24%) 3.33× slower
2048 elements with original quick sort 71.26k (± 1.54%) 1.47× slower
2048 elements with intro sort 104.46k (± 4.11%) fastest
2048 elements with std::sort in cpp 77.55k (± 1.82%) 1.35× slower
2048 elements with qsort in c 31.59k (± 3.29%) 3.31× slower
4096 elements with original quick sort 33.35k (± 2.99%) 1.49× slower
4096 elements with intro sort 49.7k (± 2.21%) fastest
4096 elements with std::sort in cpp 35.0k (± 3.80%) 1.42× slower
4096 elements with qsort in c 14.93k (± 3.42%) 3.33× slower
8192 elements with original quick sort 15.79k (± 2.93%) 1.48× slower
8192 elements with intro sort 23.38k (± 3.43%) fastest
8192 elements with std::sort in cpp 16.25k (± 4.94%) 1.44× slower
8192 elements with qsort in c 6.94k (± 4.09%) 3.37× slower
16384 elements with original quick sort 7.59k (± 1.69%) 1.45× slower
16384 elements with intro sort 10.99k (± 4.39%) fastest
16384 elements with std::sort in cpp 7.7k (± 1.92%) 1.43× slower
16384 elements with qsort in c 3.32k (± 4.44%) 3.30× slower
32768 elements with original quick sort 3.61k (± 2.24%) 1.48× slower
32768 elements with intro sort 5.34k (± 2.02%) fastest
32768 elements with std::sort in cpp 3.6k (± 3.06%) 1.48× slower
32768 elements with qsort in c 1.6k (± 1.50%) 3.33× slower
65536 elements with original quick sort 1.71k (± 3.12%) 1.50× slower
65536 elements with intro sort 2.55k (± 1.50%) fastest
65536 elements with std::sort in cpp 1.68k (± 5.23%) 1.52× slower
65536 elements with qsort in c 760.77 (± 1.61%) 3.36× slower
131072 elements with original quick sort 830.51 (± 1.42%) 1.45× slower
131072 elements with intro sort 1.2k (± 4.36%) fastest
131072 elements with std::sort in cpp 805.25 (± 2.16%) 1.49× slower
131072 elements with qsort in c 362.45 (± 1.70%) 3.32× slower
262144 elements with original quick sort 397.28 (± 1.93%) 1.45× slower
262144 elements with intro sort 577.56 (± 3.15%) fastest
262144 elements with std::sort in cpp 381.54 (± 2.12%) 1.51× slower
262144 elements with qsort in c 171.28 (± 2.74%) 3.37× slower
524288 elements with original quick sort 187.54 (± 4.03%) 1.48× slower
524288 elements with intro sort 277.4 (± 1.82%) fastest
524288 elements with std::sort in cpp 177.76 (± 3.75%) 1.56× slower
524288 elements with qsort in c 81.72 (± 2.55%) 3.39× slower
1048576 elements with original quick sort 90.75 (± 3.21%) 1.39× slower
1048576 elements with intro sort 125.85 (±10.65%) fastest
1048576 elements with std::sort in cpp 85.15 (± 3.06%) 1.48× slower
1048576 elements with qsort in c 39.37 (± 2.20%) 3.20× slower
2097152 elements with original quick sort 43.6 (± 1.22%) 1.42× slower
2097152 elements with intro sort 61.93 (± 4.73%) fastest
2097152 elements with std::sort in cpp 40.46 (± 2.13%) 1.53× slower
2097152 elements with qsort in c 18.69 (± 3.23%) 3.31× slower
4194304 elements with original quick sort 20.66 (± 3.98%) 1.45× slower
4194304 elements with intro sort 29.98 (± 3.41%) fastest
4194304 elements with std::sort in cpp 18.75 (± 6.48%) 1.60× slower
4194304 elements with qsort in c 8.93 (± 2.31%) 3.36× slower
8388608 elements with original quick sort 9.5 (± 5.99%) 1.49× slower
8388608 elements with intro sort 14.2 (± 2.72%) fastest
8388608 elements with std::sort in cpp 8.98 (± 4.58%) 1.58× slower
8388608 elements with qsort in c 4.17 (± 3.79%) 3.41× slower
16777216 elements with original quick sort 4.86 (± 2.00%) 1.43× slower
16777216 elements with intro sort 6.96 (± 2.89%) fastest
16777216 elements with std::sort in cpp 4.36 (± 2.67%) 1.59× slower
16777216 elements with qsort in c 1.97 (± 3.94%) 3.53× slower
// g++ -c -O3 -o sort.o sort.cpp
#include <cstdlib>
#include <algorithm>
extern "C" void std_sort(int *array, int size) {
std::sort(array, array + size);
}
# crystal build --release sort_benchmarks.cr
require "benchmark"
class Array
def intro_sort!
Array.intro_sort!(@buffer, @size)
self
end
protected def self.intro_sort!(a, n)
return if n < 2
quick_sort!(a, n, Math.log2(n).to_i * 2)
insertion_sort!(a, n)
end
protected def self.quick_sort!(a, n, d)
while n > 16
if d == 0
heap_sort!(a, n)
return
end
d -= 1
shift_median!(a, n)
c = partition!(a, n)
quick_sort!(c, n - (c - a), d)
n = c - a
end
end
protected def self.heap_sort!(a, n)
(n / 2).downto 0 do |p|
heapify!(a, p, n)
end
while n > 1
n -= 1
a.value, a[n] = a[n], a.value
heapify!(a, 0, n)
end
end
protected def self.heapify!(a, p, n)
v, c = a[p], p
while c < (n - 1) / 2
c = 2 * (c + 1)
c -= 1 if a[c] < a[c - 1]
break unless v < a[c]
a[p] = a[c]
p = c
end
if n & 1 == 0 && c == n / 2 - 1
c = 2 * c + 1
if v < a[c]
a[p] = a[c]
p = c
end
end
a[p] = v
end
protected def self.shift_median!(a, n)
b, c = a + n / 2, a + n - 1
if a.value < b.value
if b.value < c.value
a.value, b.value = b.value, a.value
elsif a.value < c.value
a.value, c.value = c.value, a.value
end
elsif a.value < c.value
return
elsif b.value < c.value
a.value, c.value = c.value, a.value
else
a.value, b.value = b.value, a.value
end
end
protected def self.partition!(a, n)
v, l, r = a.value, a + 1, a + n
loop do
while l.value < v
l += 1
end
r -= 1
while v < r.value
r -= 1
end
return l unless l < r
l.value, r.value = r.value, l.value
l += 1
end
end
protected def self.insertion_sort!(a, n)
(1...n).each do |i|
l = a + i
v = l.value
p = l - 1
while l > a && v < p.value
l.value = p.value
l, p = p, p - 1
end
l.value = v
end
end
end
@[Link(ldflags: "/path/to/sort.o")]
lib StdSort
fun std_sort(array : Int32*, size : Int32) : Void
fun qsort(array : Void*, size : LibC::SizeT, elm_size : LibC::SizeT, cmp : (Void*, Void*) -> Int32)
end
def generate_array(size)
random = Random.new
a = Array(Int32).new(size)
size.times do
a << random.next_int
end
a
end
size = 256
while size <= 16_777_216
Benchmark.ips do |x|
a = generate_array(size)
b, c, d = a.dup, a.dup, a.dup
x.report("#{size} elements with original quick sort") do
a.sort!
end
x.report("#{size} elements with intro sort") do
b.intro_sort!
end
x.report("#{size} elements with std::sort in cpp") do
StdSort.std_sort(c, size)
end
x.report("#{size} elements with qsort in c") do
StdSort.qsort(d, size, sizeof(Int32), -> (x : Void*, y : Void*){
x.as(Int32*).value - y.as(Int32*).value
})
end
end
size *= 2
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.