From: Ryan Davis <ryand-ruby@...>
Date: 2007-03-12T07:00:06+09:00
Subject: Re: generate UUID


On Mar 8, 2007, at 5:38 PM, Aaron Smith wrote:

We're using uuidtools at work and it is quite possibly the worst code  
I've ever come across. Convoluted, obfuscated for the sake of  
"security" and slow as hell.

% ./blah.rb 100
...
uuidtools-original    0.130000   4.650000   4.780000 (  4.782855)

Yes, 21 uuids per second!

I got a 400x improvement out of it by dropping this into our config/ 
environment.rb:

def UUID.true_random
   (1..8).to_a.map { rand(0x10000) }.pack("n8")
end

% ./blah.rb 100000
./blah.rb:9: warning: redefine true_random
...
uuidtools-modified   11.470000   0.010000  11.480000 ( 11.490444)

> def rand_hex_3(l)
>   "%0#{l}x" % rand(1 << l*4)
> end
>
> def rand_uuid
>   [8,4,4,4,12].map {|n| rand_hex_3(n)}.join('-')
> end

This is clever. I really like it. To take the above solution a couple  
steps further:

% ./blah.rb 1000000
# of iterations = 1000000
                           user     system      total        real
null_time             0.120000   0.000000   0.120000 (  0.116494)
benchmark-1          28.370000   0.050000  28.420000 ( 28.628063) #  
original
benchmark-2          15.320000   0.010000  15.330000 ( 15.339800) #  
inline and remove join
benchmark-3          10.500000   0.000000  10.500000 ( 10.521271) #  
unroll the loop, fully
benchmark-4           8.600000   0.010000   8.610000 (  8.614185) #  
reorg to remove bignum

-----

require 'benchmark'

max = (ARGV.shift || 1_000_000).to_i

def rand_hex_3(l)
   "%0#{l}x" % rand(1 << l*4)
end

def rand_uuid # original
   [8,4,4,4,12].map {|n| rand_hex_3(n)}.join('-')
end

def rand_uuid2 # inline and remove join
   "%08x-%04x-%04x-%04x-%012x" % [8,4,4,4,12].map {|n| rand(1 << n*4) }
end

def rand_uuid3 # unroll the loop
   "%08x-%04x-%04x-%04x-%012x" % [
                                  rand(0x0000100000000),
                                  rand(0x0000000010000),
                                  rand(0x0000000010000),
                                  rand(0x0000000010000),
                                  rand(0x1000000000000),
                                 ]
end

def rand_uuid4 # remove bignums
   "%04x%04x-%04x-%04x-%04x-%06x%06x" % [
                                         rand(0x0010000),
                                         rand(0x0010000),
                                         rand(0x0010000),
                                         rand(0x0010000),
                                         rand(0x0010000),
                                         rand(0x1000000),
                                         rand(0x1000000),
                                        ]
end

puts "# of iterations = #{max}"
Benchmark::bm(20) do |x|
   x.report("null_time") do
     for i in 0..max do
       # do nothing
     end
   end

   x.report("benchmark-1") do
     for i in 0..max do
       rand_uuid
     end
   end

   x.report("benchmark-2") do
     for i in 0..max do
       rand_uuid2
     end
   end

   x.report("benchmark-3") do
     for i in 0..max do
       rand_uuid3
     end
   end

   x.report("benchmark-4") do
     for i in 0..max do
       rand_uuid4
     end
   end
end