-
Notifications
You must be signed in to change notification settings - Fork 0
/
ruby_sort.txt
119 lines (105 loc) · 2.6 KB
/
ruby_sort.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
$ 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)) {