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