Skip to content

Instantly share code, notes, and snippets.

@firejox
Last active November 23, 2016 02:09
Show Gist options
  • Save firejox/4d300495811c1dda65fefc1b76fc57b6 to your computer and use it in GitHub Desktop.
Save firejox/4d300495811c1dda65fefc1b76fc57b6 to your computer and use it in GitHub Desktop.
# AMD Athlon(tm) II X2 270 Processor
# Arch Linux x86_64
# gcc (GCC) 6.2.1 20160830
# Crystal 0.19.4 (2016-10-07)
======== random2 2097152 =============
with intro sort 6.82 (± 7.91%) fastest
with another intro sort 6.22 (± 7.18%) 1.10× slower
with std::sort in cpp 6.74 (± 7.34%) 1.01× slower
with qsort in c 3.59 (± 5.62%) 1.90× slower
======== seq 2097152 =============
with intro sort 27.56 (± 8.05%) fastest
with another intro sort 18.64 (±11.13%) 1.48× slower
with std::sort in cpp 18.85 (± 9.71%) 1.46× slower
with qsort in c 10.83 (± 7.18%) 2.54× slower
======== rotated_seq 2097152 =============
with intro sort 18.64 (±10.24%) fastest
with another intro sort 4.99 (± 4.12%) 3.73× slower
with std::sort in cpp 6.01 (± 2.93%) 3.10× slower
with qsort in c 10.58 (± 8.31%) 1.76× slower
======== reversed 2097152 =============
with intro sort 25.68 (±12.16%) fastest
with another intro sort 22.22 (± 8.45%) 1.16× slower
with std::sort in cpp 22.2 (± 7.69%) 1.16× slower
with qsort in c 8.53 (± 5.00%) 3.01× slower
======== rotated_reversed 2097152 =============
with intro sort 17.8 (± 8.78%) fastest
with another intro sort 3.39 (± 8.02%) 5.26× slower
with std::sort in cpp 3.87 (± 7.21%) 4.60× slower
with qsort in c 8.34 (± 6.88%) 2.13× slower
======== random2 4194304 =============
with intro sort 3.35 (± 6.52%) fastest
with another intro sort 2.96 (± 7.37%) 1.13× slower
with std::sort in cpp 3.28 (± 6.09%) 1.02× slower
with qsort in c 1.75 (± 7.23%) 1.91× slower
======== seq 4194304 =============
with intro sort 13.13 (± 7.65%) fastest
with another intro sort 8.78 (± 6.49%) 1.49× slower
with std::sort in cpp 8.82 (± 8.90%) 1.49× slower
with qsort in c 4.88 (± 6.82%) 2.69× slower
======== rotated_seq 4194304 =============
with intro sort 7.69 (± 8.09%) fastest
with another intro sort 2.57 (± 7.92%) 3.00× slower
with std::sort in cpp 2.89 (± 5.92%) 2.66× slower
with qsort in c 4.86 (± 9.34%) 1.58× slower
======== reversed 4194304 =============
with intro sort 12.83 (± 8.07%) 1.02× slower
with another intro sort 12.35 (± 6.92%) 1.06× slower
with std::sort in cpp 13.11 (± 5.98%) fastest
with qsort in c 4.19 (± 4.69%) 3.13× slower
======== rotated_reversed 4194304 =============
with intro sort 7.92 (± 8.36%) fastest
with another intro sort 2.68 (± 5.63%) 2.96× slower
with std::sort in cpp 3.03 (± 5.56%) 2.62× slower
with qsort in c 3.91 (± 7.03%) 2.03× slower
======== random2 8388608 =============
with intro sort 1.57 (± 5.31%) 1.02× slower
with another intro sort 1.36 (± 5.06%) 1.18× slower
with std::sort in cpp 1.61 (± 6.65%) fastest
with qsort in c 0.87 (± 5.17%) 1.84× slower
======== seq 8388608 =============
with intro sort 6.41 (± 6.98%) fastest
with another intro sort 4.11 (± 7.46%) 1.56× slower
with std::sort in cpp 4.33 (± 7.08%) 1.48× slower
with qsort in c 2.5 (± 7.01%) 2.56× slower
======== rotated_seq 8388608 =============
with intro sort 4.04 (± 3.89%) fastest
with another intro sort 2.39 (± 4.76%) 1.69× slower
with std::sort in cpp 2.71 (± 4.62%) 1.49× slower
with qsort in c 2.29 (± 5.36%) 1.76× slower
======== reversed 8388608 =============
with intro sort 6.47 (± 6.25%) fastest
with another intro sort 5.6 (± 6.66%) 1.15× slower
with std::sort in cpp 6.21 (± 6.99%) 1.04× slower
with qsort in c 1.82 (± 7.07%) 3.56× slower
======== rotated_reversed 8388608 =============
with intro sort 3.95 (± 7.70%) fastest
with another intro sort 1.25 (± 6.38%) 3.15× slower
with std::sort in cpp 1.48 (± 4.72%) 2.67× slower
with qsort in c 1.9 (± 4.11%) 2.08× slower
======== random2 16777216 =============
with intro sort 0.75 (± 2.68%) 1.01× slower
with another intro sort 0.71 (± 4.48%) 1.07× slower
with std::sort in cpp 0.76 (± 3.27%) fastest
with qsort in c 0.42 (± 4.31%) 1.80× slower
======== seq 16777216 =============
with intro sort 3.02 (± 4.85%) fastest
with another intro sort 2.01 (± 4.13%) 1.50× slower
with std::sort in cpp 2.03 (± 6.83%) 1.49× slower
with qsort in c 1.15 (± 2.41%) 2.62× slower
======== rotated_seq 16777216 =============
with intro sort 1.78 (± 4.24%) fastest
with another intro sort 0.93 (± 3.38%) 1.92× slower
with std::sort in cpp 1.04 (± 3.41%) 1.71× slower
with qsort in c 1.08 (± 3.78%) 1.64× slower
======== reversed 16777216 =============
with intro sort 2.96 (± 5.49%) 1.00× slower
with another intro sort 2.71 (± 6.26%) 1.09× slower
with std::sort in cpp 2.96 (± 6.74%) fastest
with qsort in c 0.88 (± 3.88%) 3.35× slower
======== rotated_reversed 16777216 =============
with intro sort 1.7 (± 4.34%) fastest
with another intro sort 0.4 (± 1.55%) 4.23× slower
with std::sort in cpp 0.44 (± 2.45%) 3.86× slower
with qsort in c 0.92 (± 5.72%) 1.84× 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"
@[AlwaysInline]
def log(a : Int)
k = 0
while a > 0
k, a = k + 1, a >> 1
end
k - 1
end
struct Pointer
@[AlwaysInline]
def succ
self + 1
end
@[AlwaysInline]
def pred
self - 1
end
end
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, log(n) * 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
center_median!(a, n)
c = partition!(a, n)
quick_sort!(c, n - (c - a), d)
n = c - a
end
end
def heap_sort!
Array.heap_sort!(@buffer, @size)
self
end
protected def self.heap_sort!(a, n)
(n / 2).downto 0 do |p|
heapify!(a, p, n)
end
((a + 1)...(a + n)).reverse_each do |p|
a.value, p.value = p.value, a.value
heapify!(a, 0, p - a)
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.even? && 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.center_median!(a, n)
b, c = a + n / 2, a + n - 1
if a.value <= b.value
if b.value <= c.value
return
elsif a.value <= c.value
b.value, c.value = c.value, b.value
else
a.value, b.value, c.value = c.value, a.value, b.value
end
elsif a.value <= c.value
a.value, b.value = b.value, a.value
elsif b.value <= c.value
a.value, b.value, c.value = b.value, c.value, a.value
else
a.value, c.value = c.value, a.value
end
end
protected def self.partition!(a, n)
v, l, r = a[n / 2], a + 1, a + n - 1
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)
((a + 1)...(a + n)).each do |l|
v = l.value
(a...l).reverse_each do |p|
break unless v < p.value
l.value = p.value
l -= 1
end
l.value = v
end
end
def intro_sort2!
Array.intro_sort2!(@buffer, @buffer + @size)
self
end
protected def self.intro_sort2!(first, last)
n = last - first
return if n < 2
quick_sort2!(first, last, log(n) * 2)
insertion_sort2!(first, last)
end
protected def self.quick_sort2!(first, last, d)
while (last - first) > 16
if d == 0
heap_sort!(first, last - first)
return
end
d -= 1
cut = partition_pivot!(first, last)
quick_sort2!(cut, last, d)
last = cut
end
end
protected def self.partition_pivot!(first, last)
mid = first + (last - first)/2
move_median_to_first!(first, first + 1, mid, last - 1)
partition2!(first + 1, last, first)
end
protected def self.move_median_to_first!(result, a, b, c)
if a.value <= b.value
if b.value <= c.value
result.value, b.value = b.value, result.value
elsif a.value <= c.value
result.value, c.value = c.value, result.value
else
result.value, a.value = a.value, result.value
end
elsif a.value <= c.value
result.value, a.value = a.value, result.value
elsif b.value <= c.value
result.value, c.value = c.value, result.value
else
result.value, b.value = b.value, result.value
end
end
protected def self.partition2!(first, last, pivot)
v = pivot.value
loop do
while first.value < v
first += 1
end
last -= 1
while v < last.value
last -= 1
end
return first unless first < last
first.value, last.value = last.value, first.value
last += 1
end
end
protected def self.insertion_sort2!(first, last)
((first + 1)...last).each do |l|
v = l.value
(first...l).reverse_each do |p|
break unless v < p.value
l.value = p.value
l -= 1
end
l.value = v
end
end
end
@[Link(ldflags: "#{__DIR__}/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, style)
case style
when :random
random = Random.new
a = [] of Int32
a.fill(0...size) { |i| random.next_int }
when :random2
(0...size).to_a.shuffle
when :seq
(0...size).to_a
when :rotated_seq
(0...size).to_a.rotate(rand(size))
when :reversed
(0...size).to_a.reverse
when :rotated_reversed
(0...size).to_a.reverse.rotate(rand(size))
else
raise "unknown style #{style}"
end
end
module Benchmark
module IPS
class Job
def before_all(&bef)
@bef = bef
end
private def run_warmup
@items.each do |item|
GC.collect
before = Time.now
target = Time.now + @warmup_time
count = 0
while Time.now < target
@bef.as(->).call unless @bef.nil?
item.call
count += 1
end
after = Time.now
item.set_cycles(after - before, count)
end
end
private def run_calculation
@items.each do |item|
GC.collect
measurements = [] of Time::Span
target = Time.now + @calculation_time
loop do
@bef.as(->).call unless @bef.nil?
before = Time.now
item.call_for_100ms
after = Time.now
measurements << after - before
break if Time.now >= target
end
final_time = Time.now
ips = measurements.map { |m| item.cycles.to_f / m.total_seconds }
item.calculate_stats(ips)
if @interactive
run_comparison
report
print "\e[#{ran_items.size}A"
end
end
end
end
end
end
module Test
@@array : Array(Int32)
@@array = [] of Int32
def self.array=(a)
@@array = a
end
def self.array
@@array
end
end
size = 2097152
while size <= 16_777_216
[:random2, :seq, :rotated_seq, :reversed, :rotated_reversed].each do |style|
puts "======== #{style} #{size} ============="
a = generate_array(size, style)
sorted_a = a.sort
Benchmark.ips(10) do |x|
x.before_all do
Test.array.replace(a)
end
x.report("with intro sort") do
Test.array.intro_sort!
raise Exception.new "sort failed" unless Test.array == sorted_a
end
x.report("with another intro sort") do
Test.array.intro_sort2!
raise Exception.new "sort failed" unless Test.array == sorted_a
end
x.report("with std::sort in cpp") do
StdSort.std_sort(Test.array, size)
raise Exception.new "sort failed" unless Test.array == sorted_a
end
x.report("with qsort in c") do
StdSort.qsort(Test.array, size, sizeof(Int32), ->(x : Void*, y : Void*) {
x.as(Int32*).value - y.as(Int32*).value
})
raise Exception.new "sort failed" unless Test.array == sorted_a
end
end
end
size *= 2
end
@funny-falcon
Copy link

Not tested cases where values are heavily repeated:

  • few distinct values (for example, 5 differrent values in array)
  • one value consumed 90% of items,
  • etc.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment