Project

General

Profile

Download (7.78 KB)

Feature #13884 » array_opt2.diff

DmitryBochkarev (Dmitry Bochkarev), 09/11/2017 04:11 PM

View differences:

array.c
#define ARY_DEFAULT_SIZE 16
#define ARY_MAX_SIZE (LONG_MAX / (int)sizeof(VALUE))
#define SMALL_ARRAY_LEN 16
# define ARY_SHARED_P(ary) \
(assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
......
}
VALUE
rb_ary_includes_by_eql(VALUE ary, VALUE item)
{
long i;
VALUE e;
for (i=0; i<RARRAY_LEN(ary); i++) {
e = RARRAY_AREF(ary, i);
if (rb_eql(e, item)) {
return Qtrue;
}
}
return Qfalse;
}
static VALUE
recursive_cmp(VALUE ary1, VALUE ary2, int recur)
{
......
VALUE hash;
long i;
hash = ary_make_hash(to_ary(ary2));
ary3 = rb_ary_new();
for (i=0; i<RARRAY_LEN(ary1); i++) {
if (st_lookup(rb_hash_tbl_raw(hash), RARRAY_AREF(ary1, i), 0)) continue;
rb_ary_push(ary3, rb_ary_elt(ary1, i));
if (RARRAY_LEN(ary2) <= SMALL_ARRAY_LEN) {
for (i=0; i<RARRAY_LEN(ary1); i++) {
VALUE elt = rb_ary_elt(ary1, i);
if (rb_ary_includes_by_eql(ary2, elt)) continue;
rb_ary_push(ary3, elt);
}
} else {
hash = ary_make_hash(to_ary(ary2));
for (i=0; i<RARRAY_LEN(ary1); i++) {
if (st_lookup(rb_hash_tbl_raw(hash), RARRAY_AREF(ary1, i), 0)) continue;
rb_ary_push(ary3, rb_ary_elt(ary1, i));
}
ary_recycle_hash(hash);
}
ary_recycle_hash(hash);
return ary3;
}
......
ary2 = to_ary(ary2);
ary3 = rb_ary_new();
if (RARRAY_LEN(ary2) == 0) return ary3;
hash = ary_make_hash(ary2);
table = rb_hash_tbl_raw(hash);
for (i=0; i<RARRAY_LEN(ary1); i++) {
v = RARRAY_AREF(ary1, i);
vv = (st_data_t)v;
if (st_delete(table, &vv, 0)) {
rb_ary_push(ary3, v);
if (RARRAY_LEN(ary1) <= SMALL_ARRAY_LEN && RARRAY_LEN(ary2) <= SMALL_ARRAY_LEN) {
for (i=0; i<RARRAY_LEN(ary1); i++) {
VALUE elt = rb_ary_elt(ary1, i);
if (!rb_ary_includes_by_eql(ary2, elt)) continue;
if (rb_ary_includes_by_eql(ary3, elt)) continue;
rb_ary_push(ary3, elt);
}
} else {
hash = ary_make_hash(ary2);
table = rb_hash_tbl_raw(hash);
for (i=0; i<RARRAY_LEN(ary1); i++) {
v = RARRAY_AREF(ary1, i);
vv = (st_data_t)v;
if (st_delete(table, &vv, 0)) {
rb_ary_push(ary3, v);
}
}
ary_recycle_hash(hash);
}
ary_recycle_hash(hash);
return ary3;
}
......
long i;
ary2 = to_ary(ary2);
hash = ary_make_hash(ary1);
for (i=0; i<RARRAY_LEN(ary2); i++) {
VALUE elt = RARRAY_AREF(ary2, i);
if (!st_update(RHASH_TBL_RAW(hash), (st_data_t)elt, ary_hash_orset, (st_data_t)elt)) {
RB_OBJ_WRITTEN(hash, Qundef, elt);
if (RARRAY_LEN(ary1) + RARRAY_LEN(ary2) <= SMALL_ARRAY_LEN) {
ary3 = rb_ary_new();
for (i=0; i<RARRAY_LEN(ary1); i++) {
VALUE elt = rb_ary_elt(ary1, i);
if (rb_ary_includes_by_eql(ary3, elt)) continue;
rb_ary_push(ary3, elt);
}
for (i=0; i<RARRAY_LEN(ary2); i++) {
VALUE elt = rb_ary_elt(ary2, i);
if (rb_ary_includes_by_eql(ary3, elt)) continue;
rb_ary_push(ary3, elt);
}
} else {
hash = ary_make_hash(ary1);
for (i=0; i<RARRAY_LEN(ary2); i++) {
VALUE elt = RARRAY_AREF(ary2, i);
if (!st_update(RHASH_TBL_RAW(hash), (st_data_t)elt, ary_hash_orset, (st_data_t)elt)) {
RB_OBJ_WRITTEN(hash, Qundef, elt);
}
}
ary3 = rb_hash_values(hash);
ary_recycle_hash(hash);
}
ary3 = rb_hash_values(hash);
ary_recycle_hash(hash);
return ary3;
}
benchmark/bm_array_small_and.rb
MIN_SIZE = ENV.fetch('SMALL_ARRAY_MIN', 0).to_i
MAX_SIZE = ENV.fetch('SMALL_ARRAY_MAX', 16).to_i
ITERATIONS = ENV.fetch('SMALL_ARRAY_ITERATIONS', 100).to_i
ARRAYS = (MIN_SIZE..MAX_SIZE).map do |size1|
(MIN_SIZE..MAX_SIZE).map do |size2|
[Array.new(size1) { rand(MAX_SIZE) }, Array.new(size2) { rand(MAX_SIZE) }]
end
end
ITERATIONS.times do
ARRAYS.each do |group|
group.each do |arr1, arr2|
arr1 & arr2
end
end
end
benchmark/bm_array_small_diff.rb
MIN_SIZE = ENV.fetch('SMALL_ARRAY_MIN', 0).to_i
MAX_SIZE = ENV.fetch('SMALL_ARRAY_MAX', 16).to_i
ITERATIONS = ENV.fetch('SMALL_ARRAY_ITERATIONS', 100).to_i
ARRAYS = (MIN_SIZE..MAX_SIZE).map do |size1|
(MIN_SIZE..MAX_SIZE).map do |size2|
[Array.new(size1) { rand(MAX_SIZE) }, Array.new(size2) { rand(MAX_SIZE) }]
end
end
ITERATIONS.times do
ARRAYS.each do |group|
group.each do |arr1, arr2|
arr1 - arr2
end
end
end
benchmark/bm_array_small_or.rb
MIN_SIZE = ENV.fetch('SMALL_ARRAY_MIN', 0).to_i
MAX_SIZE = ENV.fetch('SMALL_ARRAY_MAX', 16).to_i
ITERATIONS = ENV.fetch('SMALL_ARRAY_ITERATIONS', 100).to_i
ARRAYS = (MIN_SIZE..MAX_SIZE).map do |size1|
(MIN_SIZE..MAX_SIZE).map do |size2|
[Array.new(size1) { rand(MAX_SIZE) }, Array.new(size2) { rand(MAX_SIZE) }]
end
end
ITERATIONS.times do
ARRAYS.each do |group|
group.each do |arr1, arr2|
arr1 | arr2
end
end
end
test/ruby/test_array.rb
assert_equal(@cls[], @cls[ 1, 2, 3 ] & @cls[ 4, 5, 6 ])
end
def test_AND_big_array # '&'
assert_equal(@cls[1, 3], @cls[ 1, 1, 3, 5 ]*64 & @cls[ 1, 2, 3 ]*64)
assert_equal(@cls[], @cls[ 1, 1, 3, 5 ]*64 & @cls[ ])
assert_equal(@cls[], @cls[ ] & @cls[ 1, 2, 3 ]*64)
assert_equal(@cls[], @cls[ 1, 2, 3 ]*64 & @cls[ 4, 5, 6 ]*64)
end
def test_MUL # '*'
assert_equal(@cls[], @cls[]*3)
assert_equal(@cls[1, 1, 1], @cls[1]*3)
......
assert_equal(@cls[1, 2, 3], @cls[1, 2, 3] - @cls[4, 5, 6])
end
def test_MINUS_big_array # '-'
assert_equal(@cls[1]*64, @cls[1, 2, 3, 4, 5]*64 - @cls[2, 3, 4, 5]*64)
# Ruby 1.8 feature change
#assert_equal(@cls[1], @cls[1, 2, 1, 3, 1, 4, 1, 5]*64 - @cls[2, 3, 4, 5]*64)
assert_equal(@cls[1, 1, 1, 1]*64, @cls[1, 2, 1, 3, 1, 4, 1, 5]*64 - @cls[2, 3, 4, 5]*64)
a = @cls[]
1000.times { a << 1 }
assert_equal(1000, a.length)
#assert_equal(@cls[1], a - @cls[2])
assert_equal(@cls[1] * 1000, a - @cls[2])
end
def test_LSHIFT # '<<'
a = @cls[]
a << 1
......
assert_equal([obj1], [obj1]|[obj2])
end
def test_OR_big_in_order
obj1, obj2 = Class.new do
attr_reader :name
def initialize(name) @name = name; end
def inspect; "test_OR_in_order(#{@name})"; end
def hash; 0; end
def eql?(a) true; end
break [new("1"), new("2")]
end
assert_equal([obj1], [obj1]*64|[obj2]*64)
end
def test_OR_big_array # '|'
assert_equal(@cls[1,2], @cls[1]*64 | @cls[2]*64)
assert_equal(@cls[1,2], @cls[1, 2]*64 | @cls[1, 2]*64)
a = (1..64).to_a
b = (1..128).to_a
c = a | b
assert_equal(c, b)
assert_not_same(c, b)
assert_equal((1..64).to_a, a)
assert_equal((1..128).to_a, b)
end
def test_combination
a = @cls[]
assert_equal(1, a.combination(0).size)
(4-4/4)