Feature #19643
closedDirect primitive compare sort for Array#sort_by
Description
Also see https://github.com/ruby/ruby/pull/7805
Introduction¶
In most of case sort_by works on primitive type.
Using qsort_r
or qsort_s
with function pointer is much slower than compare data directly.
I implement a intro sort which compare primitive data directly for sort_by,
and check whether if given block produce primitive keys (Fixnum
, Float
, mixed Fixnum
Float
).
For example array.sort_by {|x| x.to_i}
, array.sort_by {|x| x.to_f}
and [1.0, 2, 3.0, 4, 5.0].sort_by {|x| x}
We can even afford a O(n) type check before primitive data sort.
It still go faster and even approximate to Array#sort when only primitive data need to be compared in default order.
Here is benchmark result for different length of array.
Small array Benchmark¶
prelude: |
fixnum_array = (1..10).map {rand(10000)}
float_array = (1..10).map {rand(10000.0).to_f}
string_array = (1..10).map {"r" * rand(1..10000)}
mix_array = a = (1..10).map {if rand(1..100) <= 50 then rand(1..10000).to_f else rand(1..10000) end}
benchmark:
fixnum_array: fixnum_array.sort_by {|a| a}
float_array: float_array.sort_by {|a| a}
string_lengtxh: string_array.sort_by {|a| a.length}
mix_array: mix_array.sort_by {|a| a}
Iteration per second (i/s)¶
Direct Compare | Ruby master | |
---|---|---|
fixnum_array | 1.081M | 895.466k |
1.21x | - | |
float_array | 944.780k | 836.161k |
1.13x | - | |
string_lengtxh | 1.070M | 897.508k |
1.19x | - | |
mix_array | 992.567k | 568.079k |
1.75x | - |
Medium array Benchmark¶
prelude: |
fixnum_array = (1..10000).map {rand(10000)}
float_array = (1..10000).map {rand(10000.0).to_f}
string_array = (1..10000).map {"r" * rand(1..10000)}
mix_array = a = (1..10000).map {if rand(1..100) <= 50 then rand(1..10000).to_f else rand(1..10000) end}
benchmark:
fixnum_array: fixnum_array.sort_by {|a| a}
float_array: float_array.sort_by {|a| a}
string_lengtxh: string_array.sort_by {|a| a.length}
mix_array: mix_array.sort_by {|a| a}
Iteration per second (i/s)¶
Direct Compare | Ruby master | |
---|---|---|
fixnum_array | 967.592 | 491.893 |
1.97x | - | |
float_array | 535.514 | 372.758 |
1.44x | - | |
string_lengtxh | 904.724 | 512.948 |
1.76x | - | |
mix_array | 367.114 | 186.771 |
1.97x | - |
Large array Benchmark¶
prelude: |
fixnum_array = (1..1000000).map {rand(10000)}
float_array = (1..1000000).map {rand(10000.0).to_f}
string_array = (1..1000000).map {"r" * rand(1..10000)}
mix_array = a = (1..1000000).map {if rand(1..100) <= 50 then rand(1..10000).to_f else rand(1..10000) end}
benchmark:
fixnum_array: fixnum_array.sort_by {|a| a}
float_array: float_array.sort_by {|a| a}
string_lengtxh: string_array.sort_by {|a| a.length}
mix_array: mix_array.sort_by {|a| a}
Iteration per second (i/s)¶
Direct Compare | Ruby master | |
---|---|---|
fixnum_array | 8.362 | 5.386 |
1.55x | - | |
float_array | 4.251 | 3.563 |
1.19x | - | |
string_lengtxh | 6.981 | 4.654 |
1.50x | - | |
mix_array | 2.975 | 1.691 |
1.76x | - |
Updated by nekoyama32767 (Jinsong Yu) over 1 year ago
- Description updated (diff)
Updated by nekoyama32767 (Jinsong Yu) over 1 year ago
- Description updated (diff)
Updated by nekoyama32767 (Jinsong Yu) over 1 year ago
- Description updated (diff)
Updated by nekoyama32767 (Jinsong Yu) over 1 year ago
- Description updated (diff)
Updated by nekoyama32767 (Jinsong Yu) over 1 year ago
- Description updated (diff)
Updated by nekoyama32767 (Jinsong Yu) over 1 year ago
- Status changed from Open to Closed
Applied in changeset git|87217f26f120611d009f1b178d3cc5eaf1b8b515.
[Feature #19643] Direct primitive compare sort for Array#sort_by
In most of case sort_by
works on primitive type.
Using qsort_r
with function pointer is much slower than compare data directly.
I implement an intro sort which compare primitive data directly for sort_by
.
We can even afford an O(n) type check before primitive data sort.
It still go faster.