help on making ruby code faster

D

David Garamond

I use 128bit GUID values a lot, and on my Guid class there's the
Guid.from_base36 constructor and Guid#to_base36 instance method.

Base36 is a representation of GUID value using the digits "a".."z",
"0".."9" (in that particular order). Some of the nice properties of this
representation:

- shorter than the hexdigit representation (25 chars instead of 32/36).

- can be conveniently used as identifiers (variable & function names,
URL query parameters, table & column names, etc); note that the
first digit always falls between "a".."p", because 36**25 > 2**128.

- can be conveniently used as filenames (even on Windows, since it
does not depend on case differences).

The Guid class stores the GUID value as 16-byte string (@val). Here's
the conversion code mentioned above:

def Guid.from_base36(val)
val = val.downcase
raise ArgumentError unless val =~ /\A[a-z][a-z0-9]{24}\z/
n = 0
mult = 1
val.reverse.each_byte {|c|
n += @@rd36[c] * mult
mult *= 36
}
Guid.from_i(n)
end

def to_base36
self.to_i.to_s(36).tr('0-9a-z', 'a-z0-9').rjust(25, 'a')
end

Benchmark.measure shows that, on my box, I can do around 2000-2500 of
roundtrip conversions per second, which is not too bad. But I wonder if
it can be made more efficient. The Ruby profiler shows the top 4 methods:

% cumulative self self total
time seconds seconds calls ms/call ms/call name
33.59 0.43 0.43 50 8.60 17.60 String#each_byte
14.06 0.61 0.18 1550 0.12 0.17 Fixnum#*
9.38 0.73 0.12 1900 0.06 0.06 Bignum#*
8.59 0.84 0.11 50 2.20 3.00 Guid#to_i

which is kind of disappointing since I was hoping to still be able to
store GUID values as 16-byte strings, for compactness. Here's the
complete code (91 lines, hope it's not too long...)

===================================================================
class Guid
@@d36 = ('a'..'z').to_a + ('0'..'9').to_a
@@rd36 = {}
@@d36.each_with_index {|d, i| @@rd36[d[0]] = i}

attr_reader :val

def initialize(val=nil)
if val
raise ArgumentError unless val.length==16
else
val = (1..16).collect{|c| rand(256).chr}.join
end
@val = val
end

def to_s
self.to_hex
end

def ==(other)
@val == other.val
end

def Guid.from_hex(val)
h = '[0-9A-Fa-f]'
raise ArgumentError unless
val =~ /\A#{h}{8}-#{h}{4}-#{h}{4}-#{h}{4}-#{h}{12}\z/
val.gsub! /-/, ''
Guid.new([val].pack('H32'))
end

def to_hex
@val.unpack('H8H4H4H4H12').join '-'
end

def Guid.from_i(val)
Guid.new([
(val & 0xffffffff000000000000000000000000) >> 96,
(val & 0x00000000ffffffff0000000000000000) >> 64,
(val & 0x0000000000000000ffffffff00000000) >> 32,
(val & 0x000000000000000000000000ffffffff)
].pack('NNNN'))
end

def to_i
(@val[ 0 .. 3].unpack('N')[0] << 96) +
(@val[ 4 .. 7].unpack('N')[0] << 64) +
(@val[ 8 .. 11].unpack('N')[0] << 32) +
(@val[12 .. 15].unpack('N')[0])
end

def Guid.from_base36(val)
val = val.downcase
raise ArgumentError unless val =~ /\A[a-z][a-z0-9]{24}\z/
n = 0
mult = 1
val.reverse.each_byte {|c|
n += @@rd36[c] * mult
mult *= 36
}
Guid.from_i(n)
end

def to_base36
self.to_i.to_s(36).tr('0-9a-z', 'a-z0-9').rjust(25, 'a')
end
end

guids = [
#'00000000-0000-0000-0000-000000000000',
#'ffffffff-ffff-ffff-ffff-ffffffffffff',
#'00000000-0000-0000-0000-000000000001',
#'10000000-0000-0000-0000-000000000000',
'7d77a27f-542c-4edb-9642-f0e324ae23a2',
'c44e6638-ed47-4ce9-9bb6-ba41bca2e535',
'aae9946e-64b2-4628-8f57-d0da26d29c86',
'6cf2eba1-2f9d-463d-8538-6396f00b3f68',
'6c518ced-1d56-46f9-af24-dd82726502ef',
].collect {|h| Guid.from_hex(h)}

require 'benchmark'

puts Benchmark.measure {
1000.times {
guids.each {|g|
raise SystemError unless g == Guid.from_base36(g.to_base36)
}
}
}
===================================================================

Regards,
dave
 
S

Stefan Schmiedl

Benchmark.measure shows that, on my box, I can do around 2000-2500 of
roundtrip conversions per second, which is not too bad. But I wonder if
it can be made more efficient. The Ruby profiler shows the top 4 methods:

I'm not sure on the effects it will have, but try extracting
the constants from your often-called methods. You're repeatedly
creating "the same objects" which might slow you down due to
unnecessary garbage collection.

s.
 
R

Robert Klemme

David Garamond said:
I use 128bit GUID values a lot, and on my Guid class there's the
Guid.from_base36 constructor and Guid#to_base36 instance method.

Base36 is a representation of GUID value using the digits "a".."z",
"0".."9" (in that particular order). Some of the nice properties of this
representation:

- shorter than the hexdigit representation (25 chars instead of 32/36).

- can be conveniently used as identifiers (variable & function names,
URL query parameters, table & column names, etc); note that the
first digit always falls between "a".."p", because 36**25 > 2**128.

- can be conveniently used as filenames (even on Windows, since it
does not depend on case differences).

The Guid class stores the GUID value as 16-byte string (@val). Here's
the conversion code mentioned above:

def Guid.from_base36(val)
val = val.downcase

The general rule is that object creation is quite expensive. So it's
always good to try to avoid it if possible.

You can save the downcase if you add values for lower and upper case
characters to @@rd36 (if it's an array, maybe make it a hash).
raise ArgumentError unless val =~ /\A[a-z][a-z0-9]{24}\z/
n = 0
mult = 1
val.reverse.each_byte {|c|
n += @@rd36[c] * mult
mult *= 36
}


Maybe this looping is more efficient:

(val.length - 1).downto(0) {|i|
n += @@rd36[val[c]] * mult
mult *= 36
}
Guid.from_i(n)

Not a performance thingy but you can omit "Guid." here. This is less
error prone if you rename the class.
end

def to_base36
self.to_i.to_s(36).tr('0-9a-z', 'a-z0-9').rjust(25, 'a')

tmp = to_i.to_s(36)
tmp.tr!('0-9a-z', 'a-z0-9')
tmp.rjust(25, 'a')

Maybe this can be even further optimized if you can save instance
creations.

Kind regards

robert

end

Benchmark.measure shows that, on my box, I can do around 2000-2500 of
roundtrip conversions per second, which is not too bad. But I wonder if
it can be made more efficient. The Ruby profiler shows the top 4 methods:

% cumulative self self total
time seconds seconds calls ms/call ms/call name
33.59 0.43 0.43 50 8.60 17.60 String#each_byte
14.06 0.61 0.18 1550 0.12 0.17 Fixnum#*
9.38 0.73 0.12 1900 0.06 0.06 Bignum#*
8.59 0.84 0.11 50 2.20 3.00 Guid#to_i

which is kind of disappointing since I was hoping to still be able to
store GUID values as 16-byte strings, for compactness. Here's the
complete code (91 lines, hope it's not too long...)

===================================================================
class Guid
@@d36 = ('a'..'z').to_a + ('0'..'9').to_a
@@rd36 = {}
@@d36.each_with_index {|d, i| @@rd36[d[0]] = i}

attr_reader :val

def initialize(val=nil)
if val
raise ArgumentError unless val.length==16
else
val = (1..16).collect{|c| rand(256).chr}.join
end
@val = val
end

def to_s
self.to_hex
end

def ==(other)
@val == other.val
end

def Guid.from_hex(val)
h = '[0-9A-Fa-f]'
raise ArgumentError unless
val =~ /\A#{h}{8}-#{h}{4}-#{h}{4}-#{h}{4}-#{h}{12}\z/
val.gsub! /-/, ''
Guid.new([val].pack('H32'))
end

def to_hex
@val.unpack('H8H4H4H4H12').join '-'
end

def Guid.from_i(val)
Guid.new([
(val & 0xffffffff000000000000000000000000) >> 96,
(val & 0x00000000ffffffff0000000000000000) >> 64,
(val & 0x0000000000000000ffffffff00000000) >> 32,
(val & 0x000000000000000000000000ffffffff)
].pack('NNNN'))
end

def to_i
(@val[ 0 .. 3].unpack('N')[0] << 96) +
(@val[ 4 .. 7].unpack('N')[0] << 64) +
(@val[ 8 .. 11].unpack('N')[0] << 32) +
(@val[12 .. 15].unpack('N')[0])
end

def Guid.from_base36(val)
val = val.downcase
raise ArgumentError unless val =~ /\A[a-z][a-z0-9]{24}\z/
n = 0
mult = 1
val.reverse.each_byte {|c|
n += @@rd36[c] * mult
mult *= 36
}
Guid.from_i(n)
end

def to_base36
self.to_i.to_s(36).tr('0-9a-z', 'a-z0-9').rjust(25, 'a')
end
end

guids = [
#'00000000-0000-0000-0000-000000000000',
#'ffffffff-ffff-ffff-ffff-ffffffffffff',
#'00000000-0000-0000-0000-000000000001',
#'10000000-0000-0000-0000-000000000000',
'7d77a27f-542c-4edb-9642-f0e324ae23a2',
'c44e6638-ed47-4ce9-9bb6-ba41bca2e535',
'aae9946e-64b2-4628-8f57-d0da26d29c86',
'6cf2eba1-2f9d-463d-8538-6396f00b3f68',
'6c518ced-1d56-46f9-af24-dd82726502ef',
].collect {|h| Guid.from_hex(h)}

require 'benchmark'

puts Benchmark.measure {
1000.times {
guids.each {|g|
raise SystemError unless g == Guid.from_base36(g.to_base36)
}
}
}
===================================================================

Regards,
dave
 
D

David Garamond

Stefan said:
I'm not sure on the effects it will have, but try extracting
the constants from your often-called methods. You're repeatedly
creating "the same objects" which might slow you down due to
unnecessary garbage collection.

By constants, do you mean literal constants like '0-9a-z', 'a-z0-9', and
'a' in the code below?

def to_base36
self.to_i.to_s(36).tr('0-9a-z', 'a-z0-9').rjust(25, 'a')
end

Can't Ruby currently optimize those? I frankly don't want to have to do
those kinds of optimization myself :-(

Regards,
dave
 
R

Robert Klemme

Good point, Stefan!
By constants, do you mean literal constants like '0-9a-z', 'a-z0-9', and
'a' in the code below?

Yes, I think so.
def to_base36
self.to_i.to_s(36).tr('0-9a-z', 'a-z0-9').rjust(25, 'a')
end

Can't Ruby currently optimize those? I frankly don't want to have to do
those kinds of optimization myself :-(

It does (by sharing the internal string buffer) but it still has to create
new String instances on each run:
134947060
134946988
134696172
134690592
134690544
=> 5

If it would not do this, code like this would yield unexpected results:
5.times { p 'abc'[1] += 1 }
99
99
99
99
99
=> 5

i.e. you'd see this instead:
5.times { p 'abc'[1] += 1 }
99
100
101
102
103
=> 5


Kind regards

robert
 
R

Robert Klemme

Can't Ruby currently optimize those? I frankly don't want to have to do
those kinds of optimization myself :-(

One more remark: you're optimizing - doing these kind things is all
optimizing is about. For example: although the Java VM's of today do a
lot optimizations, deciding when to create an instance and when not is not
one of these AFAIK. Only the developer can decide which instances can be
reused.

Kind regards

robert
 
D

David Garamond

Robert said:
The general rule is that object creation is quite expensive. So it's
always good to try to avoid it if possible.

I applied your suggestions below and it got slightly worse. So I guess
object creation has been pretty optimized in Ruby? :)
You can save the downcase if you add values for lower and upper case
characters to @@rd36 (if it's an array, maybe make it a hash).

I do get slightly better performance by making @@rd36 an array instead
of a hash (originally it's a hash).

Regards,
dave
 
D

David Garamond

Robert said:
Can't Ruby currently optimize those? I frankly don't want to have to do
those kinds of optimization myself :-(

It does (by sharing the internal string buffer) but it still has to create
new String instances on each run:

134947060
134946988
134696172
134690592
134690544
=> 5

If it would not do this, code like this would yield unexpected results:
5.times { p 'abc'[1] += 1 }

I see. Suddenly I want immutable strings like in Python.

Hm, it seems optimizing Ruby programs is pretty tedious? One has to
scorch through every string literal...

Regards,
dave
 
R

Robert Klemme

David Garamond said:
Robert said:
Can't Ruby currently optimize those? I frankly don't want to have to do
those kinds of optimization myself :-(

It does (by sharing the internal string buffer) but it still has to create
new String instances on each run:
5.times { p 's'.id }

134947060
134946988
134696172
134690592
134690544
=> 5

If it would not do this, code like this would yield unexpected results:
5.times { p 'abc'[1] += 1 }

I see. Suddenly I want immutable strings like in Python.

At least there is freeze. In such a situation I do typically this:

class SillyExample
FOO = "my prefix".freeze

def prefix(s)
FOO + s
end
end
Hm, it seems optimizing Ruby programs is pretty tedious? One has to
scorch through every string literal...

No, only those that are performance critical. :)

Regards

robert
 
R

Robert Klemme

David Garamond said:
I applied your suggestions below and it got slightly worse. So I guess
object creation has been pretty optimized in Ruby? :)

.... or I introduced another slow operation that evens out the effect of
the saved creations...
I do get slightly better performance by making @@rd36 an array instead
of a hash (originally it's a hash).

Does freezing the array make a difference? Nah, probably not...

robert
 
I

Ilmari Heikkinen

Hello, here's some precalc to speed up the lots-of-conversions case
It makes the only-few-conversions case slower and by uses some more
(25*36 numbers) memory. So if you have a shell script that converts a
single guid, this'll just slow it down.
===================================================================
class Guid
@@d36 = ('a'..'z').to_a + ('0'..'9').to_a
@@rd36 = {}
@@d36.each_with_index {|d, i| @@rd36[d[0]] = i}

# add these
@@exp_a = (0..24).to_a.reverse.map{|i| 36**i}
@@exps = {}
@@rd36.map{|char,index|
@@exps[char] = @@exp_a.map{|e| index*e}
}
def Guid.from_base36(val)
val = val.downcase
raise ArgumentError unless val =~ /\A[a-z][a-z0-9]{24}\z/
n = 0

mult = 0
val.each_byte {|c|
n += @@exps[c][mult]
mult += 1
}
Guid.from_i(n)
end

Got around 35% speedup in the 1000 conversions benchmark.

-Ilmari
 
D

David Garamond

Ilmari said:
Hello, here's some precalc to speed up the lots-of-conversions case
It makes the only-few-conversions case slower and by uses some more
(25*36 numbers) memory.

Thanks! I missed that.

Regards,
dave
 
M

martinus

Hi! I have played a bit with your code, the result is now about 55%
faster. I have replaced your internal string representation (the @Val)
with an integer, wich makes the code both simpler and faster. The
from_base36 method has also changed, it now looks like this:

def self.from_base36(val)
val = val.downcase
raise ArgumentError unless val =~ /\A[a-z][a-z0-9]{24}\z/
n = 0
val.each_byte do |c|
n = n*36 + @@rd36[c]
end
Guid.new(n)
end

Now the most time consuming task is each_byte, which takes about 60% of
the CPU.

Here is the full sourcecode:
http://martinus.geekisp.com/files/guid.rb

Martin
 
M

martinus

ops, I should have read your first post with more attention :)
forget the @val representation thing, but the from_base36 method might
still help a bit.

Martin
 
M

martinus

This is even faster:

def self.from_base36(val)
Guid.from_i(val.downcase.tr('a-z0-9', '0-9a-z').to_i(36))
end

martinus
 
D

David Garamond

martinus said:
ops, I should have read your first post with more attention :)

Well, depending on the situation, I now will reconsider storing the GUID
value as 16-byte string as well as Bignum. And perhaps optionally do
some 'memoization' too. It's basically the traditional space vs
computation trade-off.
forget the @val representation thing, but the from_base36 method might
still help a bit.

Martin

Thanks to all responses.

Regards,
dave
 
D

David Garamond

martinus said:
This is even faster:

def self.from_base36(val)
Guid.from_i(val.downcase.tr('a-z0-9', '0-9a-z').to_i(36))
end

Hey, didn't know that String#to_i takes an argument. Cool...

Regards,
dave
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top