From: Christian Neukirchen <chneukirchen@...>
Date: 2006-01-06T22:23:31+09:00
Subject: Re: [SUMMARY] Numeric Maze (#60)

Kero <kero@chello.single-dot.nl> writes:

>> Tristan's solution makes use of bit operations, because they tend to be faster
>> than multiplication and division.  All you need to know about these is that n <<
>> 1 == n * 2 and n >> 1 == n / 2.
>
> Are they really faster? Ruby bits are not directly in CPU registers.

IIRC, a bitshift on modern Intel processors is extremely inefficient
because it has to throw-away all kind of assumptions.  I even think
n << 1 gets compiled to n+n by good compiler.  (Can't test at the moment,
I'm on PPC only here.)

> My rule of thumb is that every method call in Ruby takes a huge amount of
> time, whether it is a bitshift or a multiplication (or even a regexp check).
> For the record, I did a quick test:
>
> kero@pc67140460:~/tmp$ time ruby -e '1_000_000.times { |i|  i << 1 }'
> real    0m2.683s
> user    0m1.970s
> sys     0m0.710s
> kero@pc67140460:~/tmp$ time ruby -e '1_000_000.times { |i|  i << 1 }'
> real    0m2.687s
> user    0m1.880s
> sys     0m0.810s
> kero@pc67140460:~/tmp$ time ruby -e '1_000_000.times { |i|  i * 2 }'
> real    0m2.684s
> user    0m2.080s
> sys     0m0.600s
> kero@pc67140460:~/tmp$ time ruby -e '1_000_000.times { |i|  i * 2 }'
> real    0m2.689s
> user    0m2.060s
> sys     0m0.640s
>
> No significant differences whatsoever.

These microbenchmarks are totally pointless; you'd need to write them
in assembler since you don't know which code your compiler generated
for <<.

> Bye,
> Kero.
>
> PS: fun quiz, but that should be clear with all my postings :)

Absolutely, I enjoyed it, even if I didn't sent in my solution--a
breadth-first search like so many others.  (I used the cute trick of
int.send(X, 2) for X being :/, :* or :+, which I hadn't seen yet
anywhere...)

-- 
Christian Neukirchen  <chneukirchen@gmail.com>  http://chneukirchen.org