Feature #19129
Updated by e8c (Viktor Reznov) almost 2 years ago
Code is already written, all in one listing (git diff, test file, and results of tests): ``` $ cat ../ruby_sort/test.rb #!/bin/ruby srand 0 r = Array.new 1e7.to_i do rand -2 ** 40...2 ** 40 end puts 5.times do a = r.clone t = Time.now a.sort! puts "\tRun ##{_1 + 1}: %.3f s" % [Time.now - t] end puts; exit unless $*[0] p (r.sort { _1 <=> _2 }) == (r.sort) puts $ ./miniruby ../ruby_sort/test.rb # qsort Run #1: 2.209 s Run #2: 2.259 s Run #3: 2.229 s Run #4: 2.196 s Run #5: 2.226 s $ ./miniruby ../ruby_sort/test.rb # rsort Run #1: 0.328 s Run #2: 0.351 s Run #3: 0.352 s Run #4: 0.323 s Run #5: 0.342 s $ git diff diff --git a/array.c b/array.c index a33c43bdbf..fe52291c21 a33c43bdbf..578d9443cd 100644 --- a/array.c +++ b/array.c @@ -3521,6 +3521,83 +3521,52 @@ sort_2(const void *ap, const void *bp, void *dummy) return n; } +#if __linux__ && __SIZEOF_POINTER__ == 8 + +static int rsort(void *const _p, const long l) { + + for (const VALUE *p = _p, *const P = p + 64; l; p < P;) + if (!FIXNUM_P(*p++)) return 1; + + uint64_t F[8][256] = {}, *a = _p, *b = malloc(8 * l); + if (b == NULL) return 1; + + for (uint64_t *p = a + 64, *p2 = b + 64, a, *const P = p + (l - 64); l; p < P; p2++) p++) { + *p2 = *p ^ += (1UL << 63); + for (int i = 0; i < 8; i++) + F[i][(*p2 F[i][(*p >> i * 8) & 255]++; + if (!FIXNUM_P(*p++)) { + free(b); + return 1; + } + } + + for (uint64_t *p = a, *p2 = b, *const P = p + 64; p < P; p2++) { + *p2 = *p++ ^ (1UL << 63); + for (int i = 0; i < 8; i++) + F[i][(*p2 >> i * 8) & 255]++; + } + + { uint64_t *t = a; a = b, b = t; } + + uint64_t skip[8] = {}; int last = 10; + + for (int i = 0; i < 8; i++) { + uint64_t x = 0, t, *o = F[i]; F[i], flag = 0; + for (int j = 0; j < 256; j++) { + if ((t = o[j]) == (uint64_t)l) { + skip[i] flag = 1; + break; + } + x = (o[j] = x) + t; + } + } + + for (int i = 7; i >= 0; --i) + if (skip[i] == 0) { + last = i; + break; + } + + if (last == 10) { + free(a); + return 0; + } + + for (int i = 0; i < 8; i++) { + if (skip[i]) (flag) continue; + uint64_t *o = F[i]; + if (i < last) + for (uint64_t *p = a, *const P = p + l; p < P; p++) { + b[o[(*p >> i * 8) & 255]++] = *p; + } + else + for (uint64_t *p = a, *const P = p + l; p < P; p++) { + b[o[(*p >> i * 8) & 255]++] = *p ^ (1UL << 63); + } + o = a, a = b, b = o; + } + + if (a != _p) { + memcpy(_p, a, b, 8 * l); + b = a; + } + + for (uint64_t *p = _p, *const P = p + l; p < P; p++) + *p -= (1UL << 63); + + free(b); + return 0; +} + +#endif + /* * call-seq: * array.sort! -> self @@ -3577,8 +3654,20 +3623,20 @@ rb_ary_sort_bang(VALUE ary) data.cmp_opt.opt_methods = 0; data.cmp_opt.opt_inited = 0; RARRAY_PTR_USE(tmp, ptr, { + +#if __linux__ && __SIZEOF_POINTER__ == 8 + + if ((len < 10000 || rb_block_given_p()) || rsort(ptr, len)) + ruby_qsort(ptr, len, sizeof(VALUE), + rb_block_given_p() ? sort_1 : sort_2, &data); + +#else + ruby_qsort(ptr, len, sizeof(VALUE), - rb_block_given_p()?sort_1:sort_2, &data); + rb_block_given_p() ? sort_1 : sort_2, &data); + +#endif + }); /* WB: no new reference */ rb_ary_modify(ary); if (ARY_EMBED_P(tmp)) { ``` From: https://github.com/alantudyk/xPNG/blob/ba93248b2dacb4607500b635456e96592b200503/until_fork/ruby_sort.txt No time to create a pull request.