Feature #16505
closedImprove preformance of `RubyVM::InstructionSequence#to_binary`
Description
Abstract¶
Within #to_binary, deduplication of objects output to binary is performed, but the current implementation is achieved by a linear search of an array of objects (=obj_list
). (https://github.com/ruby/ruby/blob/e288632f22b18b29efd20a1469292b0a3ba9b74c/compile.c#L9699-L9701)
On the other hand, iseq deduplication is faster because it is implemented using a hash. (https://github.com/ruby/ruby/blob/e288632f22b18b29efd20a1469292b0a3ba9b74c/compile.c#L9744-L9745)
This proposal speeds up object deduplication by using a hash.
This patch does not change the output binary.
Implementation¶
https://github.com/ruby/ruby/pull/2835
Evaluation¶
Environment:
- OS: macOS Catalina
- CPU: Intel Core i5
- Memory: 16GB
address_lists_parser.rb¶
address_lists_parser.rb
(https://github.com/mikel/mail/blob/master/lib/mail/parsers/address_lists_parser.rb) in mail
gem has an extremely huge array.
Call # to_binary
on the iseq of this file and check its execution time and MD5 of the output binary.
The benchmark code:
require 'benchmark'
require 'digest/md5'
F = 'address_lists_parser.rb'
N = 100
iseq = RubyVM::InstructionSequence.compile_file(F)
bin = iseq.to_binary
puts "md5 hash: #{Digest::MD5.hexdigest(bin)}"
Benchmark.bm(12) do |x|
x.report("to_binary x#{N}") {
N.times do ||
iseq.to_binary
end
}
end
-
master (
ruby 2.8.0dev (2020-01-12T10:54:59Z master e288632f22) [x86_64-darwin19]
)md5 hash: fd80e7c0c8da7a9044e89139c6078137 user system total real to_binary x100 27.162084 0.078262 27.240346 ( 27.675089)
-
Proposal (
ruby 2.8.0dev (2020-01-12T12:39:10Z improve-performanc.. e05ad5ef81) [x86_64-darwin19]
)md5 hash: fd80e7c0c8da7a9044e89139c6078137 user system total real to_binary x100 0.989403 0.036869 1.026272 ( 1.063335)
The same binary was output before and after the change.
Execution speed is 26 times faster.
Updated by NagayamaRyoga (Nagayama Ryoga) over 4 years ago
- Status changed from Open to Closed
Applied in changeset git|6e5e6a40c4c35aee1cfb7d0effa47354f80baa9e.
Deduplicate objects efficiently when dumping iseq to binary
We were inefficient in cases where there are a lot of duplicates due to
the use of linear search. Use a hash table instead.
These cases are not that rare in the wild.
[Feature #16505]