View mode: basic / threaded / horizontal-split · Log in · Help
April 14, 2004
Re: [bug] static array slice as associative array index
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
April 14, 2004
Re: [bug] static array slice as associative array index - hash-test.zip
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
April 14, 2004
Re: [bug] static array slice as associative array index - hash-test.zip
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.
April 14, 2004
Re: [bug] static array slice as associative array index - hash-test.zip
> 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
April 16, 2004
Re: [bug] static array slice as associative array index - hash-test.zip
> 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.
April 16, 2004
Re: [bug] static array slice as associative array index - hash-test.zip
> 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.
Next ›   Last »
1 2
Top | Discussion index | About this forum | D home