Feature #19643: Direct primitive compare sort for Array#sort_by

• Status: Closed
• Assignee: -
• Target version: -

[nekoyama32767 (Jinsong Yu)]

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	-

[nekoyama32767 (Jinsong Yu)]

• Description updated (diff)

[nekoyama32767 (Jinsong Yu)]

• Description updated (diff)

[nekoyama32767 (Jinsong Yu)]

• Description updated (diff)

[nekoyama32767 (Jinsong Yu)]

• Description updated (diff)

[nekoyama32767 (Jinsong Yu)]

• Description updated (diff)

[nekoyama32767 (Jinsong Yu)]

• 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.