Project

General

Profile

Actions

Feature #19643

closed

Direct primitive compare sort for Array#sort_by

Added by nekoyama32767 (Jinsong Yu) over 1 year ago. Updated over 1 year ago.

Status:
Closed
Assignee:
-
Target version:
-
[ruby-core:<unknown>]

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 -
Actions #1

Updated by nekoyama32767 (Jinsong Yu) over 1 year ago

  • Description updated (diff)
Actions #2

Updated by nekoyama32767 (Jinsong Yu) over 1 year ago

  • Description updated (diff)
Actions #3

Updated by nekoyama32767 (Jinsong Yu) over 1 year ago

  • Description updated (diff)
Actions #4

Updated by nekoyama32767 (Jinsong Yu) over 1 year ago

  • Description updated (diff)
Actions #5

Updated by nekoyama32767 (Jinsong Yu) over 1 year ago

  • Description updated (diff)
Actions #6

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.

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0