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:
Click to expand...

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
Click to expand...

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
}
Click to expand...


Maybe this looping is more efficient:

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

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')
Click to expand...

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
Click to expand...
 
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.
Click to expand...

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?
Click to expand...

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 :-(
Click to expand...

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 }
Click to expand...
Click to expand...
99
99
99
99
99
=> 5

i.e. you'd see this instead:
5.times { p 'abc'[1] += 1 }
Click to expand...
Click to expand...
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 :-(
Click to expand...

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.
Click to expand...

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).
Click to expand...

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 :-(
Click to expand...

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 }
Click to expand...
Click to expand...
Click to expand...

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 :-(
Click to expand...

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 }
Click to expand...

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 }
Click to expand...
Click to expand...

I see. Suddenly I want immutable strings like in Python.
Click to expand...

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...
Click to expand...

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? :)
Click to expand...

.... 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).
Click to expand...

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}
Click to expand...

# 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
Click to expand...

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

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.
Click to expand...

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 :)
Click to expand...

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
Click to expand...

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
Click to expand...

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

Similar Threads

I Need Help with making a function that draws in a canvas using location data. 1
Python code problem 2
first ruby program, how do I make it faster? 1
Help needed about Treetop::Runtime::SyntaxNode. 1
how do i configure this code 0
Exchange calendar to Ruby object. Please comment the code. 0
feedback on code design 23
Help, Ruby 1.8.6-p287 broke my "use" library and I don't know why 4

Members online

No members online now.
Total: 65 (members: 1, guests: 64)
Robots: 405

Forum statistics

Threads
473,982
Messages
2,570,185
Members
46,736
Latest member
AdolphBig6

Latest Threads

Top