On Sun, 11 Apr 2004 10:45:42 +0000 (UTC), serge@lxnt.info wrote:

>I have just found D language and was interested in its performance. I found this page http://www.functionalfuture.com/d/ and was not impressed by 'hash' benchmark performance, so I tried to make my own implementation.

Any luck improving the hash test performance?
Also I think the matrix mult test needs attention.
It should probably use the type
 int[30][30]
instead of
 int[][]


see multi-dimensional arrays in
 http://www.digitalmars.com/d/arrays.html

-Ben

In article <ibvp70hmjvjrj5kf17cajl7l3mesomtv5v@4ax.com>, Ben Hinkle says...

>On Sun, 11 Apr 2004 10:45:42 +0000 (UTC), serge@lxnt.info wrote:
>
>>I have just found D language and was interested in its performance. I found this page http://www.functionalfuture.com/d/ and was not impressed by 'hash' benchmark performance, so I tried to make my own implementation.
>
>Any luck improving the hash test performance?

Results are in the attached file.


>Also I think the matrix mult test needs attention.
>It should probably use the type
> int[30][30]
>instead of
> int[][]
>
>
>see multi-dimensional arrays in
> http://www.digitalmars.com/d/arrays.html
>
>-Ben

In article <c5k6vs$2l9u$1@digitaldaemon.com>, serge says...

>Results are in the attached file.

Well, I think these results need some comments. I compared performance of 4 programs, one compiled with GCC and 3 compiled with DMD.

hash.c - hash test in pure C (from http://www.bagley.org/~doug/shootout/)
hash.d - test.c ported to D
hash.native.old.d - hash test from http://www.functionalfuture.com/d/
hash.native.new.d - my attempt to improve performance of hash test

compiler command line options:

gcc: -O3 -fomit-frame-pointer
dmd: -O -release -inline

performance results for n=1000000 on Athlon 850:

hash.c            : 3.690 seconds
hash.d            : 4.580 seconds
hash.native.old.d : 26.110 seconds
hash.native.new.d : 13.000 seconds

So, hash.d and hash.c times differ not too much. They contain almost identical code and just compare the quality of optimizers in GCC and DMD. Given the fact that DMD is still not particularly optimized for performance, this result is very good.

But difference between hash.d and hash.native.new.d is very noticeable. This can be an indication of poor associative array performance (DMD native associative arrays are about 3 times slower than hand written hash implementation). I hope this is not a design flaw and can be fixed in the future.

> But difference between hash.d and hash.native.new.d is very noticeable. This can
> be an indication of poor associative array performance (DMD native associative
> arrays are about 3 times slower than hand written hash implementation). I hope
> this is not a design flaw and can be fixed in the future.

Interesting. I threw in some rehash calls during the first loop and it sped things up somewhat but not very close to hash.d - I wonder how much improvement there would be by prallocating the size by allowing the length to be set in associative arrays? It could even use the same prime number table in hash.d
It would also be fun to play around with the hashing function to see if it makes any difference. Or inlining. or the GC. or...
I wonder what a profiler like VTune says.

-Ben

> hash.c            : 3.690 seconds
> hash.d            : 4.580 seconds
> hash.native.old.d : 26.110 seconds
> hash.native.new.d : 13.000 seconds

I played around a bit and have some more data:
all code compiled with
 gcc -O3 -fomit-frame-pointer hash.c
 gdc -O3 -fomit-frame-pointer hash.d (same flags for phobos, too)

hash.c            3.06
hash.d            3.13
hash.native.new.d 9.4
 + pre-allocate   4.85
 + new hash fcn   4.68

by "pre-allocate" I mean the line in aaA.d
   *aa = new pa[10];
is replaced with
   *aa = new pa[1572869]; // magic number from hash.c for 1000000

by "new hash fcn" I mean the function getHash in ti_Aa.d  is replaced with (from www.cs.yorku.ca/~oz/hash.html)
uint getHash(void*p)
{ char[] s = *(char[]*)p;
  uint len = s.length;
  char *str = s;
  uint hash = 5381;
  while (len--) hash = hash*33 ^ *str++;
  return hash;
}

I'll keep investigating where the time is going. I think it makes sense to add some way to reserve a large hash table size like in the C code. Building the hash table up one element at a time and rehashing every now and then is slow when you know you want a big table.
-Ben

ps. a big hurrah for gdc - I love it! We aren't limited to just playing around with phobos - we can actually go in and try adding .reserve properties and such. And plus it is simple to compare C and D code side by side. very very cool.

> I'll keep investigating where the time is going.
Glad your on the job :).


> ps. a big hurrah for gdc - I love it!

Cool!  I havent played with it yet, is it pretty stable ?

C
On Thu, 15 Apr 2004 22:17:53 -0400, Ben Hinkle <bhinkle4@juno.com> wrote:

>
>> hash.c            : 3.690 seconds
>> hash.d            : 4.580 seconds
>> hash.native.old.d : 26.110 seconds
>> hash.native.new.d : 13.000 seconds
>
> I played around a bit and have some more data:
> all code compiled with
>   gcc -O3 -fomit-frame-pointer hash.c
>   gdc -O3 -fomit-frame-pointer hash.d (same flags for phobos, too)
>
> hash.c            3.06
> hash.d            3.13
> hash.native.new.d 9.4
>   + pre-allocate   4.85
>   + new hash fcn   4.68
>
> by "pre-allocate" I mean the line in aaA.d
>     *aa = new pa[10];
> is replaced with
>     *aa = new pa[1572869]; // magic number from hash.c for 1000000
>
> by "new hash fcn" I mean the function getHash in ti_Aa.d  is replaced with (from www.cs.yorku.ca/~oz/hash.html)
> uint getHash(void*p)
> { char[] s = *(char[]*)p;
>    uint len = s.length;
>    char *str = s;
>    uint hash = 5381;
>    while (len--) hash = hash*33 ^ *str++;
>    return hash;
> }
>
> I'll keep investigating where the time is going. I think it makes sense to add some way to reserve a large hash table size like in the C code. Building the hash table up one element at a time and rehashing every now and then is slow when you know you want a big table.
> -Ben
>
> ps. a big hurrah for gdc - I love it! We aren't limited to just playing around with phobos - we can actually go in and try adding .reserve properties and such. And plus it is simple to compare C and D code side by side. very very cool.
>



-- 
D Newsgroup.