[ruby-core:110729] [Ruby master Feature#19129] Radix_Sort for arrays of fixnums (implemented)

["e8c (Viktor Reznov)" <noreply@ruby-lang.org>]

Issue #19129 has been reported by e8c (Viktor Reznov).

----------------------------------------
Feature #19129: Radix_Sort for arrays of fixnums (implemented)
https://bugs.ruby-lang.org/issues/19129

* Author: e8c (Viktor Reznov)
* Status: Open
* Priority: Normal
----------------------------------------
Code 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..578d9443cd 100644
--- a/array.c
+++ b/array.c
@@ -3521,6 +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 + 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, *const P = p + l; p < P; p++) {
+        *p += (1UL << 63);
+        for (int i = 0; i < 8; i++)
+            F[i][(*p >> i * 8) & 255]++;
+    }
+
+    for (int i = 0; i < 8; i++) {
+        uint64_t x = 0, t, *o = F[i], flag = 0;
+        for (int j = 0; j < 256; j++) {
+            if ((t = o[j]) == (uint64_t)l) {
+                flag = 1;
+                break;
+            }
+            x = (o[j] = x) + t;
+        }
+        if (flag) continue;
+        for (uint64_t *p = a, *const P = p + l; p < P; p++) {
+            b[o[(*p >> i * 8) & 255]++] = *p;
+        }
+        o = a, a = b, b = o;
+    }
+
+    if (a != _p) {
+        memcpy(_p, 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 +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.



-- 
https://bugs.ruby-lang.org/