Larry Hudson wrote:

>>     I just ran a quick test that shows that this algorithm is actually
 
>> 3 to 4 times *slower* than Kiss64. See attached source file. Test was 

>> run like this:
>>
>>  > gcc -O3 -lm -o random random.c
>>
>>  > ./random
>> Empty loop: 0ms
>> Kiss64 (int): 6622ms
>> Kiss64 (dbl): 5003ms
>> Alvo: 21021ms
>>
> Interesting...  I played with your test example on my system and got 
> rather different results.  My system is much older and slower -- 32-bit
 
> Athlon 2000+, old version of Linux & gcc.  (I won't bother going into 
> the reasons why I still use Fedora 3, I do have and use newer versions 

> of Linux.  But this is what I still use to read these newsgroups.)
> 
> Anyway, I had to reduce your loop count by a factor of 10 to get timing
s 
> similar to yours, but I found the Alvo was _faster_ than the Kiss64.
> 
> Then I made a couple changes, first, instead of the call to floor() I 
> used a simple type cast to int.  Second, since the original performs th
e 
> same multiplication twice, I changed it to use a temporary variable 
> instead.
> 
	Funny, I did try it with a temp variable instead of two mults. It 
didn't change the timings so I assumed that my version of gcc was 
able to optimize it and kept the one closest to the algorithm.

	I hadn't tried with a cast instead of "floor" and it is indeed 
faster, though still not as fast as Kiss64.

	As for the reason why Kiss64 is faster on my computer, I suppose 
it's due to the fact that it is 64 bits and therefore able to do 
some operations in one instruction while 32 bit computers need 
several instructions to do the same thing.

> The original relevant line:
>     alvo_x = (alvo_s * alvo_x) - floor (alvo_s * alvo_x);
> 
> My first change:
>     alvo_x = (alvo_s * alvo_x) - (int)(alvo_s * alvo_x);
> 
> My second change:  (Also adding "double alvo;" to the variable list)
>     alvo = alvo_s * alvo_x;
>     alvo_x = alvo - (int)alvo;
> 
> Here are the timings on my last run:
> 100000000 loops:
> Empty loop: 255ms
> Kiss64 (int): 4568ms
> Kiss64 (dbl): 8980ms
> Alvo: 3626ms
> Alvo: 2646ms:   (int with 2 mults)
> Alvo: 325ms:    (int with 1 mult)
> 
	Interesting that on your computer the dbl version of Kiss64 should 
be so much slower than the int version while on mine the results are 
comparable.

	By simple curiosity, I've also added Warp's implementation of Isaac 
and here is the result (see attached code):

 > g++ -O3 -lm -o random random.cc IsaacRand.cc

 > ./random
Empty loop:          0ms
Kiss64 (int):     6623ms
Kiss64 (dbl):     5003ms
Alvo (floor):    21539ms
Alvo (cast):     14608ms
Alvo (tmp+cast): 14664ms
Isaac:           10540ms

		Jerome
-- 
mailto:jeb### [at] freefr
http://jeberger.free.fr
Jabber: jeb### [at] jabberfr

Post a reply to this message

Attachments:
Download 'us-ascii' (2 KB)

>  > g++ -O3 -lm -o random random.cc IsaacRand.cc
> 
>  > ./random
> Empty loop:          0ms
> Kiss64 (int):     6623ms
> Kiss64 (dbl):     5003ms
> Alvo (floor):    21539ms
> Alvo (cast):     14608ms
> Alvo (tmp+cast): 14664ms
> Isaac:           10540ms
> 
	Upon reflection, those timing are ridiculous because there is no 
way to know what was optimized away by the compiler (like the empty 
loop: no matter how high I set LOOPS, that takes 0ms which is 
absurd). So here are the timings with no optimization (-O0):

Empty loop:       6324ms
Kiss64 (int):    13482ms
Kiss64 (dbl):    33679ms
Alvo (floor):    26223ms
Alvo (cast):     20113ms
Alvo (tmp+cast): 23512ms
Isaac:           33855ms

	Of course, this doesn't say anything about the quality of the 
random numbers generated.

		Jerome
-- 
mailto:jeb### [at] freefr
http://jeberger.free.fr
Jabber: jeb### [at] jabberfr

Post a reply to this message

Attachments:
Download 'us-ascii' (1 KB)

>         By simple curiosity, I've also added Warp's implementation of Isaac 
> and here is the result (see attached code):

>  > g++ -O3 -lm -o random random.cc IsaacRand.cc

  I suggest adding -march=native in order for gcc to fully optimize it for
your platform. It might make a big difference, especially with this type
of code.
  (Also -lm is probably not needed. At least I don't need it here.)

>  > ./random
> Empty loop:          0ms
> Kiss64 (int):     6623ms
> Kiss64 (dbl):     5003ms
> Alvo (floor):    21539ms
> Alvo (cast):     14608ms
> Alvo (tmp+cast): 14664ms
> Isaac:           10540ms

  I tried running the program on my Pentium4 (with g++ -O3 -march=native)
and got the following results:

Empty loop:          0ms
Kiss64 (int):     2669ms
Kiss64 (dbl):     2643ms
Alvo (floor):     2098ms
Alvo (cast):      1767ms
Alvo (tmp+cast):  1766ms
Isaac:             690ms

  The speed seems to be pretty dependant on the CPU type being used...

  Out of curiosity, I also tried adding -mfpmath=sse to the compiler options,
and the results changed a bit:

Empty loop:          0ms
Kiss64 (int):     2687ms
Kiss64 (dbl):     2640ms
Alvo (floor):     2424ms
Alvo (cast):      1294ms
Alvo (tmp+cast):  1335ms
Isaac:             685ms

-- 
                                                          - Warp

Post a reply to this message

> So here are the timings with no optimization (-O0):

  I think comparing speed of unoptimized code is rather absurd and
useless. :)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> "J�r�me M. Berger" <jeb### [at] freefr> wrote:
>>         By simple curiosity, I've also added Warp's implementation of 
Isaac 
>> and here is the result (see attached code):
> 
>>  > g++ -O3 -lm -o random random.cc IsaacRand.cc
> 
>   I suggest adding -march=native in order for gcc to fully optimize i
t for
> your platform. It might make a big difference, especially with this typ
e
> of code.
	It doesn't change anything here. Remember that the gcc shipped with 
most 32-bits linux distros is configured to generate code for the 
original Pentium! In this case, forcing the compiler to optimize for 
your machine is usually a big win. On 64-bits platforms however, 
there is not that much difference between the first generation 
Athlon64 and the current generation.

>   (Also -lm is probably not needed. At least I don't need it here.)
> 
	I originally didn't put it, but I added it because it was needed 
for the C version. Now that the code is compiled as C++, you're 
right it's not needed any more.

>>  > ./random
>> Empty loop:          0ms
>> Kiss64 (int):     6623ms
>> Kiss64 (dbl):     5003ms
>> Alvo (floor):    21539ms
>> Alvo (cast):     14608ms
>> Alvo (tmp+cast): 14664ms
>> Isaac:           10540ms
> 
>   I tried running the program on my Pentium4 (with g++ -O3 -march=nat
ive)
> and got the following results:
> 
> Empty loop:          0ms
> Kiss64 (int):     2669ms
> Kiss64 (dbl):     2643ms
> Alvo (floor):     2098ms
> Alvo (cast):      1767ms
> Alvo (tmp+cast):  1766ms
> Isaac:             690ms
> 
>   The speed seems to be pretty dependant on the CPU type being used...
> 
	So it seems...

>   Out of curiosity, I also tried adding -mfpmath=sse to the compiler 
options,
> and the results changed a bit:
> 
> Empty loop:          0ms
> Kiss64 (int):     2687ms
> Kiss64 (dbl):     2640ms
> Alvo (floor):     2424ms
> Alvo (cast):      1294ms
> Alvo (tmp+cast):  1335ms
> Isaac:             685ms
> 


-- 
mailto:jeb### [at] freefr
http://jeberger.free.fr
Jabber: jeb### [at] jabberfr

Post a reply to this message

Attachments:
Download 'us-ascii' (1 KB)

Warp wrote:
> "J�r�me M. Berger" <jeb### [at] freefr> wrote:
>> So here are the timings with no optimization (-O0):
> 
>   I think comparing speed of unoptimized code is rather absurd and
> useless. :)
> 
	In a way, that's true. However, it's not as useless as you imply. 
For example, in hindsight it is now obvious to me that the compiler 
removed the floating point division from Kiss64 (dbl), which 
explains why it was as fast as the integer version. So I've attached 
a new version of the benchmark that's specifically designed to foil 
these kind of optimizations that wouldn't happen in real life. And 
here are the timings (with -O3):

Empty loop:       3387ms	(was     0ms)
Kiss64 (int):     7348ms	(was  6623ms)
Kiss64 (dbl):    16045ms	(was  5003ms)
Alvo (floor):    22209ms	(was 21539ms)
Alvo (cast):     16258ms	(was 14608ms)
Alvo (tmp+cast): 15054ms	(was 14664ms)
Isaac:           10701ms	(was 10540ms)

	Notice how all tests except Isaac now take longer. I believe that 
the reason why Isaac isn't affected is because it calls a function 
that's in another file, which prevented gcc from optimizing as 
aggressively.

	This just goes to show that designing benchmarks is not as easy as 
it appears...

		Jerome
-- 
mailto:jeb### [at] freefr
http://jeberger.free.fr
Jabber: jeb### [at] jabberfr

Post a reply to this message

Attachments:
Download 'us-ascii' (3 KB)

Jérôme M. Berger wrote:
> Empty loop:       3387ms    (was     0ms)
> Kiss64 (int):     7348ms    (was  6623ms)
> Kiss64 (dbl):    16045ms    (was  5003ms)
> Alvo (floor):    22209ms    (was 21539ms)
> Alvo (cast):     16258ms    (was 14608ms)
> Alvo (tmp+cast): 15054ms    (was 14664ms)
> Isaac:           10701ms    (was 10540ms)
> 

	I just ran the tests on another computer with a Core2 duo and the 
results are rather interesting:

	With the same binary as above:
Empty loop:       2173ms
Kiss64 (int):     7541ms
Kiss64 (dbl):    15844ms
Alvo (floor):    24778ms
Alvo (cast):      8469ms
Alvo (tmp+cast):  8473ms
Isaac:            7810ms

	Notice how the last three are much faster?

	Recompiled with g++ 4.4 and -O3:
Empty loop:       1154ms
Kiss64 (int):     5944ms
Kiss64 (dbl):    12590ms
Alvo (floor):    22433ms
Alvo (cast):      7636ms
Alvo (tmp+cast):  8076ms
Isaac:            6428ms

	Slight improvement (10-20%) all around.

	Recompiled with g++ 4.4 and -O3 -ftree-vectorize:
Empty loop:       1085ms
Kiss64 (int):     5504ms
Kiss64 (dbl):    11663ms
Alvo (floor):    22039ms
Alvo (cast):      7730ms
Alvo (tmp+cast):  7730ms
Isaac:            5918ms

	Again, slight improvement all around except for Alvo. I'm not sure 
why Kiss64 gets improved though...

	And here is the system info:
 > uname -a
Linux rover 2.6.29-ARCH #1 SMP PREEMPT Sat May 9 14:09:36 CEST 2009 
x86_64 Intel(R) Core(TM)2 Duo CPU T5670 @ 1.80GHz GenuineIntel GNU/Linux

  > gcc --version
gcc (GCC) 4.4.0
Copyright (C) 2009 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There 
is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR 
PURPOSE.

		Jerome
-- 
mailto:jeb### [at] freefr
http://jeberger.free.fr
Jabber: jeb### [at] jabberfr

Post a reply to this message

Attachments:
Download 'us-ascii' (1 KB)

>         I just ran the tests on another computer with a Core2 duo and the 
> results are rather interesting:

>         With the same binary as above:
> Empty loop:       2173ms
> Kiss64 (int):     7541ms
> Kiss64 (dbl):    15844ms
> Alvo (floor):    24778ms
> Alvo (cast):      8469ms
> Alvo (tmp+cast):  8473ms
> Isaac:            7810ms

  One thing I can't understand: Why are the results *significantly* faster
in my Pentium4 (eg. the Isaac RNG seems to be 10 times faster, which is
a HUGE difference in speed), even though a Core2 duo should be faster
than a Pentium4? Something does not compute here.

-- 
                                                          - Warp

Post a reply to this message

Warp <war### [at] tagpovrayorg> wrote:
> http://warp.povusers.org/IsaacRand.zip

Just out of curiosity: Is that the same RNG that lives in MCPov?

I think I read something about you having supplied some RNG know-how or even
code to the montecarlo renderer.

Post a reply to this message

clipka <nomail@nomail> wrote:
> Warp <war### [at] tagpovrayorg> wrote:
> > http://warp.povusers.org/IsaacRand.zip

> Just out of curiosity: Is that the same RNG that lives in MCPov?

> I think I read something about you having supplied some RNG know-how or even
> code to the montecarlo renderer.

  Yes, I think the author used it when I suggested that he could use
something of higher quality than std::rand().

-- 
                                                          - Warp

Post a reply to this message