A benchmark

[Ivan Kazmenko]

Walter Bright:
>...
>7) Such arrays can easily be just allocated dynamically at runtime.
Thanks for the very detailed explanation! Actually, I checked the seventh
argument, and it worked for me, but gave me some interesting experience in the
process of investigation which I'd like to share.

First, I checked the example posted by Dave, the program compiled and ran, but I
found some oddity in its behaviour: after writing the output line, it still went
on working a bit and then terminated.

Then, I changed my sieve program to use dynamic array instead of static one.
Imagine my astonishment when it ran about 10 seconds, while the static array
version ran no more than a second! I checked different versions of my program
(such as manually working with a bit array stored in ubytes), and the results
were the same: they all ran 10-20 seconds. By redirecting the output from file
to the screen, I found out that the output was generated fast enough like
before, and the remaining time was used by the program to consume processor
resources for a purpose unknown.

I then remembered that in good old days I used no gc, and happily wrote a delete
line at the end of my program. Oh joy! its runtime got back to one second. Well,
I expected that gc is one of the main advantages of d over c++... but manually
deleting allocated objects currently does not pose a problem to me. Anyway, I
usually program for contests and research, not for large scale projects. But I
wonder what did it do in that ten seconds. Did it scan the array being deleted
for hidden pointers?

All that encouraged me to write a simple benchmark. Below is a simple
Eratosphenes sieve program. Thanks to the conditional compile capabilities of D,
I was able to maintain five versions in a small, simple, readable program.
-----
import std.stdio;

const int MaxN = 16_000_000;

version (Byte) {alias ubyte main_type;}
version (Int)  {alias int   main_type;}

version (Static)  {main_type [MaxN] a;}
version (Dynamic) {main_type []     a;}

int main ()
{
int i, j, s;
version (Dynamic) {a = new main_type [MaxN];}
a[2..MaxN - 1] = 1;
for (i = 2; i * i < MaxN; i++)
if (a[i])
for (j = i * i; j < MaxN; j += i)
a[j] = 0;
s = 0;
for (i = 0; i < MaxN; i++)
if (a[i])
s++;
version (Delete) {delete a;}
printf ("The number of primes is %d.\n", s);
return 0;
}
-----
The compile line then looks like "dmd -version=Byte -version=Static test.d".

Here is the run time for different versions of the program on my current
configuration - it's Athlon64 3200+ @2500 MHz (overclocked), 768 MB DDR, Windows
2003 Server (32-bit). I measured wall-clock time since I know no simple reliable
way to get process time under Windows. Didn't try dmd under Linux yet.
-----
Byte, Static:          1.44
Byte, Dynamic:         2.52
Byte, Dynamic, Delete: 1.41
Int,  Dynamic:         2.23
Int,  Dynamic, Delete: 2.17
-----
Interestingly, repetitive runs show that the dynamic version with delete is in
fact a little bit faster than the static version - I definitely didn't expect
such an effect! On the contrary, dynamic version without delete does the job in
the same time and then spends a second more doing some secret internal cleanup
work. Another interesting notion is that the int version behaves nearly the same
with or without delete, slightly faster than the dynamic byte version without
delete. Static int version doesn't compile, since it requires a ~64M array.

Ivan Kazmenko.