diff options
| author | nekoyama32767 <[email protected]> | 2023-05-20 19:40:27 +0900 |
|---|---|---|
| committer | <[email protected]> | 2023-05-20 19:40:27 +0900 |
| commit | 87217f26f120611d009f1b178d3cc5eaf1b8b515 () | |
| tree | 076728143f2a038c0e953a85c9c14a3a11a6d7d6 | |
| parent | 892798cac8d025ad30a99fc2a0efa6b0a7a8dd0e (diff) | |
[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.
Notes: Merged: https://.com/ruby/ruby/pull/7805 Merged-By: nobu <[email protected]>
| -rw-r--r-- | benchmark/enum_sort_by.yml | 53 | ||||
| -rw-r--r-- | enum.c | 198 |
2 files changed, 247 insertions, 4 deletions
@@ -0,0 +1,53 @@ @@ -1334,10 +1334,12 @@ enum_sort(VALUE obj) } #define SORT_BY_BUFSIZE 16 struct sort_by_data { const VALUE ary; const VALUE buf; - long n; }; static VALUE @@ -1358,6 +1360,11 @@ sort_by_i(RB_BLOCK_CALL_FUNC_ARGLIST(i, _data)) rb_raise(rb_eRuntimeError, "sort_by reentered"); } RARRAY_ASET(data->buf, data->n*2, v); RARRAY_ASET(data->buf, data->n*2+1, i); data->n++; @@ -1385,6 +1392,179 @@ sort_by_cmp(const void *ap, const void *bp, void *data) return OPTIMIZED_CMP(a, b); } /* * call-seq: * sort_by {|element| ... } -> array @@ -1491,6 +1671,9 @@ enum_sort_by(VALUE obj) RB_OBJ_WRITE(memo, &data->ary, ary); RB_OBJ_WRITE(memo, &data->buf, buf); data->n = 0; rb_block_call(obj, id_each, 0, 0, sort_by_i, (VALUE)memo); ary = data->ary; buf = data->buf; @@ -1499,9 +1682,16 @@ enum_sort_by(VALUE obj) rb_ary_concat(ary, buf); } if (RARRAY_LEN(ary) > 2) { - RARRAY_PTR_USE(ary, ptr, - ruby_qsort(ptr, RARRAY_LEN(ary)/2, 2*sizeof(VALUE), - sort_by_cmp, (void *)ary)); } if (RBASIC(ary)->klass) { rb_raise(rb_eRuntimeError, "sort_by reentered"); |