www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Associative array of strings perf

reply bearophile <bearophileHUGS lycos.com> writes:
Do you know why an associative array like this:
uint[immutable(char)[]] aa;

Is almost two times faster than a very similar associative array like this?
uint[immutable(E)[]] aa;

Where E is a named typed enum of chars like:
enum E : char { a='a', b='b', c='c', d='d', ... }

Testing code:
http://codepad.org/hzcRH8Bd

Bye,
bearophile
Nov 18 2011
next sibling parent reply "Daniel Murphy" <yebblies nospamgmail.com> writes:
Maybe different hash functions are used?

"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:ja76i7$1u3i$1 digitalmars.com...

 Do you know why an associative array like this:
 uint[immutable(char)[]] aa;

 Is almost two times faster than a very similar associative array like 
 this?
 uint[immutable(E)[]] aa;

 Where E is a named typed enum of chars like:
 enum E : char { a='a', b='b', c='c', d='d', ... }

 Testing code:
 http://codepad.org/hzcRH8Bd

 Bye,
 bearophile
Nov 18 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Daniel Murphy:


 Maybe different hash functions are used?


I presume that something somewhere uses some different function of a different
part of it, but then one of those functions has a significant amount of space
left for improvement.

The __Dmain produced by the two versions of the program are exactly the same,
minus some names, they call the same runtime functions like __aaInX and the
other functions too visible with obj2asm are the same.

---------------

Alex R. Petersen:


 With an enum, I assume the hashes can be precomputed.


This program doesn't use enum/chars but dynamic array of enums/chars, so you
can't precompute (it uses only 500 different strings, so again it can
precompute the hash of them all, but this just forces me to create a more
complex benchmark).


Regarding hashing of single enums, often enough (from ObjectPascal usage) I'd
like to use arrays with a small group of named indexes. D allows you to write
this, but it defines an associative array, this is a waste of memory and
performance:


enum Foo : size_t { A, B, C, D }
void main() {
    int[Foo] array;
    array[Foo.D] = 5;
    // array[2] = 1; // statically rejected
}


This alternative code works, but you lose all strong static typing:

enum : size_t { A, B, C, D }
void main() {
    int[4] array;
    array[D] = 5;
    array[2] = 1; // accepted
}

Bye,
bearophile
Nov 19 2011
prev sibling next sibling parent reply =?ISO-8859-1?Q?Alex_R=F8nne_Petersen?= <xtzgzorex gmail.com> writes:
On 19-11-2011 04:07, bearophile wrote:

 Do you know why an associative array like this:
 uint[immutable(char)[]] aa;

 Is almost two times faster than a very similar associative array like this?
 uint[immutable(E)[]] aa;

 Where E is a named typed enum of chars like:
 enum E : char { a='a', b='b', c='c', d='d', ... }

 Testing code:
 http://codepad.org/hzcRH8Bd

 Bye,
 bearophile


With an enum, I assume the hashes can be precomputed.

- Alex
Nov 18 2011
parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 19/11/11 4:34 AM, Alex Rønne Petersen wrote:

 On 19-11-2011 04:07, bearophile wrote:

 Do you know why an associative array like this:
 uint[immutable(char)[]] aa;

 Is almost two times faster than a very similar associative array like
 this?
 uint[immutable(E)[]] aa;

 Where E is a named typed enum of chars like:
 enum E : char { a='a', b='b', c='c', d='d', ... }

 Testing code:
 http://codepad.org/hzcRH8Bd

 Bye,
 bearophile


 With an enum, I assume the hashes can be precomputed.

 - Alex


Then shouldn't the enum be faster? :-)

alias immutable(char)[] MyString; // runtime 4.41 seconds
//alias immutable(E)[] MyString;  // runtime 7.92 seconds

My guess is that DMD has an optimised path for strings that isn't (but 
should be) used for char-typed enums.
Nov 19 2011
prev sibling parent "Martin Nowak" <dawg dawgfoto.de> writes:
On Sat, 19 Nov 2011 04:07:51 +0100, bearophile <bearophileHUGS lycos.com>  
wrote:


 Do you know why an associative array like this:
 uint[immutable(char)[]] aa;

 Is almost two times faster than a very similar associative array like  
 this?
 uint[immutable(E)[]] aa;

 Where E is a named typed enum of chars like:
 enum E : char { a='a', b='b', c='c', d='d', ... }

 Testing code:
 http://codepad.org/hzcRH8Bd

 Bye,
 bearophile


take a look at

     writeln(typeid(immutable(char)[]).classinfo.name); // TypeInfo_Aya  
 from rt.typeinfo.ti_Ag
     writeln(typeid(immutable(E)[]).classinfo.name);    // TypeInfo_Array  
 from object.d

The string typeinfos use a cheaper hash algorithm.
Nov 19 2011