www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Performance of hashes and associative arrays

reply =?UTF-8?B?IlJhcGhhw6ts?= Jakse" <raphael.jakse gmail.com> writes:
Hello everybody,

we had a conversation with Ali Cehreli about the right ways of 
hashing values / objects. This is related to the D language when 
using associative arrays but applies for any language as well.

One of the points was, we have the following class:

==
class Student // class representing a student
{
     string firstName; // the first name of the student
     string lastName; // the last name of the student
}
==

Let s be a Student:

==
auto s = new Student("Jean", "Martin");
==

We want to be able to get the hash of s. Therefore, we 
re-implement the toHash method of the Student class :

==
class Student
{
     string firstName;
     string lastName;

     override size_t toHash() const
     {
         //...
     }
}
==

The original solution proposed was:

==
     override size_t toHash() const
     {
         return (typeid(firstName).getHash(&firstName) +
                 typeid(lastName).getHash(&lastName));
     }
==

However, with this solution, we get the same hash for new 
Student("Jean", "Martin") and new Student("Martin", "Jean"). We 
did an experiment of performance of associative arrays in D when 
the hash function is not well designed (returning the same hash 
for too many values). When the hash function returns the same 
hash for too many values, performance are dramatic (See the end 
of the post for more information).

So here is the second solution that was proposed and that avoids 
having the same hash for two different names:

==
     override size_t toHash() const
     {
         auto h = firstName ~ ":" ~ lastName; // we suppose that 
":" is not a valid character in a name
         return typeid(h).getHash(&h);
     }
==

A ":" was added so new Student("Martin", "Jean") gets a different 
hash than new Student("Mar", "tinJean")).
Let's call the following solution "second bis solution" :

==
     override size_t toHash() const
     {
         auto h = firstName ~ lastName;
         return typeid(h).getHash(&h);
     }
==

This solution suppose that being named Mar tinJean instead of 
Martin Jean is really strange and therefore quite unusual.
However, these two solutions imply string concatenations each 
time we need the hash.
Ali agreed that concatenating strings each time would indeed be 
inefficient. He thought we might cache the value (third solution) 
:

==
class Student
{
     string firstName;
     string lastName;
     size_t cachedHash;

     override size_t toHash() const
     {
         if(cachedHash is null)
         {
             auto h = firstName ~ ":" ~ lastName;
             cachedHash = typeid(h).getHash(&h);
         }
         return cachedHash;
     }
}
==

This solution doesn't make compromise on the "quality" of the 
hash and is fast after the first usage but needs to keep the hash 
as part of the class. The hash is calculated for each new object 
that is used as index in an associative array, even if the hash 
for this specific name has already been calculated in another 
object.

Questions are :
  - what is the most efficient solution, and in which case ?
  - Is it preferable to try to make the hash unique (second bis 
solution), or to try to make the hash easier to evaluate and risk 
in rare case to get the same hashes for two different objects 
(second solution)?
  - Is solution 3 a good practice? Preferable to the others 
solutions? When?
  - Is solution 1 preferable to the others solutions, given that 
first name / last name inversions are quite "rare" ?
  - how compares solution 1 to solution 2 bis ?

It would also be interesting to have ideas for the general case, 
i.e. random objects and not just names that have particularities 
like "First names are not often last names and vice versa", or 
for other specific situations.
Questions are oriented for usage in associative arrays in D, but 
still apply to other use cases of hashes.


For those who are interested, here is Ali's experiment on 
performance of associative arrays in D depending on the design of 
the hash function (I took the liberty to modify it slightly).

==
import std.stdio;
import std.random;
import std.string;

class Clock
{
     int hour;
     int minute;
     int second;

     static size_t opCmpCount = 0;
     static size_t opEqualsCount = 0;
     static size_t toHashCount = 0;

     override equals_t opEquals(Object o) const
     {
         ++opEqualsCount;

         auto rhs = cast(const Clock)o;

         return (rhs &&
                 (hour == rhs.hour) &&
                 (minute == rhs.minute) &&
                 (second == rhs.second));
     }

     override int opCmp(Object o) const
     {
         ++opCmpCount;

         /* Taking advantage of the automatically-maintained
          * order of the types. */
         if (typeid(this) != typeid(o)) {
             return typeid(this).opCmp(typeid(o));
         }

         auto rhs = cast(const Clock)o;
         /* No need to check whether rhs is null, because it is
          * known on this line that it has the same type as o. */

         return (hour != rhs.hour
                 ? hour - rhs.hour
                 : (minute != rhs.minute
                    ? minute - rhs.minute
                    : second - rhs.second));
     }

     override string toString() const
     {
         return format("%02s:%02s:%02s", hour, minute, second);
     }

     this(int hour, int minute, int second)
     {
         this.hour = hour;
         this.minute = minute;
         this.second = second;
     }

     override hash_t toHash() const
     {
         ++toHashCount;
         return hour + minute + second; // method 1
         // return hour + 60 * minute + 3600 * second; // method 2
     }

     static void printCounts()
     {
         writefln("opEquals: %8s", opEqualsCount);
         writefln("opCmp   : %8s", opCmpCount);
         writefln("toHash  : %8s", toHashCount);
     }
}

Clock randomClock()
{
     return new Clock(uniform(0, 24), uniform(0, 60), uniform(0, 
60));
}

void main()
{
     enum count = 10_000;
     Clock[Clock] aa;

     foreach (i; 0 .. count) {
         auto entry = randomClock();
         aa[entry] = entry;
     }

     foreach (i; 0 .. count) {
         auto result = (randomClock() in aa);
     }

     Clock.printCounts();
}
==

We both get the following results for the method 1:

opEquals:        0
opCmp   :  1438438
toHash  :    20000


and the following results for the method 2:

opEquals:        0
opCmp   :     1681
toHash  :    20000

Apart from the fact associative arrays in gdc and dmd don't use 
the opEquals method, we see that using method 1 implies approx. 
856 times more comparisons than method 2. I calculated that 
method 1 gives 139 different hashes for 80063 different elements, 
which means each hash represents an average of approx. 576 
elements. Method 2 gives exactly one hash for one element.
This seems to be an extreme case, we might think results would be 
completely different from a function giving hashes that 
"sometimes" represents 2 elements.
Nov 06 2012
next sibling parent reply "Dan" <dbdavidson yahoo.com> writes:
On Wednesday, 7 November 2012 at 06:38:32 UTC, Raphaël Jakse 
wrote:

 ==
     override size_t toHash() const
     {
         return (typeid(firstName).getHash(&firstName) +
                 typeid(lastName).getHash(&lastName));
     }
 ==

Isn't the real problem the addition. You want to mix the bits together in a consistent way that does not have associativity. I've seen things like: result = 37 * first + 17 * second I've incorporated this functionality in a toHash that can be mixed in. Any feedback on it would be great. See: http://forum.dlang.org/post/tbjrqaogxegtyexnfags forum.dlang.org https://github.com/patefacio/d-help/blob/master/d-help/opmix/mix.d It only supports structs, but the hashing could be made to support classes. It allows for the following code for your example. It provides toHash, opEquals and opCmp. Below the hashcodes for s1 and s2 are different, the instances are not equal and s1 is less than s2 which is what you want. import std.stdio; import opmix.mix; struct Student // class representing a student { mixin(HashSupport); string firstName; // the first name of the student string lastName; // the last name of the student } void main() { auto s1 = Student("Jean", "Martin"); auto s2 = Student("Martin", "Jean"); writeln(s1.toHash(), " vs ", s2.toHash()); writeln(s1 == s2); writeln(s1 < s2); }
 However, with this solution, we get the same hash for new 
 Student("Jean", "Martin") and new Student("Martin", "Jean"). We 
 did an experiment of performance of associative arrays in D 
 when the hash function is not well designed (returning the same 
 hash for too many values). When the hash function returns the 
 same hash for too many values, performance are dramatic (See 
 the end of the post for more information).

This makes sense and is not particular to D.
 Ali agreed that concatenating strings each time would indeed be 
 inefficient. He thought we might cache the value (third 
 solution) :

Interesting about caching the hashcode and on large classes could save you. But isn't the signature shown const? Would that compile? Also, what if you change the strings - you get the wrong hash? I suppose you could limit writes to properties and null the hashcode on any write.
 Questions are :
  - what is the most efficient solution, and in which case ?

No string concatenation is good. I think a single pass on all important data (in most cases is all the data) is the goal.
 This seems to be an extreme case, we might think results would 
 be completely different from a function giving hashes that 
 "sometimes" represents 2 elements.

Very true. If I increase to 10_000_000 I see opCmp:1913600 for the smart method and (several minutes later) opCmp:907216764 for the simple addition (method 1). In this case you know something special about the data and can take advantage of it. If I run the example using the mixin(HashSupport) it does opCmp:7793499 which is about 4 times as many compares as the smart one. The simple addition does 474 times as many compares as the smart one - so it is clearly very bad. So, if you know something special about the data, like it can easily be converted into a single number such as seconds, by all means include that. But remember, next time you add something to the class, if you don't have some "automated" way of pulling in info from all fields you need to revisit the hash (and opCmp and opEquals). Thanks Dan
Nov 07 2012
parent reply =?UTF-8?B?UmFwaGHDq2wgSmFrc2U=?= <raphael.jakse gmail.com> writes:
Hello,

Thanks for this complete answer. I will take a look to your code.
Additionally, Ali gave me a really interesting link about hashing, good 
practices, what is efficient, etc. If you didn't read it, it might 
interest you. Here it is:

http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

Le 07/11/2012 13:10, Dan a écrit :
 On Wednesday, 7 November 2012 at 06:38:32 UTC, Raphaël Jakse wrote:
 [...]
 Ali agreed that concatenating strings each time would indeed be
 inefficient. He thought we might cache the value (third solution) :

Interesting about caching the hashcode and on large classes could save you. But isn't the signature shown const? Would that compile?

Indeed, I didn't tested this code, I just wanted to explicit what I wanted to say. Thank you for the notice.
 Also, what
 if you change the strings - you get the wrong hash? I suppose you could
 limit writes to properties and null the hashcode on any write.

Yes, good question and good idea, I think I would do it this way. I didn't think about it.
 Questions are :
  - what is the most efficient solution, and in which case ?

No string concatenation is good. I think a single pass on all important data (in most cases is all the data) is the goal.

I'm not sure I understood well. You wanted to say that string contatenations are good, right ? I was thinking about a hash function that would take several arguments and hash them together. That would let take in account more than one string in the hash while avoiding concatenation.
[...]

 Thanks
 Dan

Nov 09 2012
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 11/10/2012 05:17 AM, Dan wrote:

 I just meant string concatenation is likely unnecessary. Imagine two one
 megabyte strings. It is easy to concat them and call the string hash
 function on the result but you have to create a 2Mb string first.

Just a random thought: std.range.chain can obviate that copy: http://dlang.org/phobos/std_range.html#chain Ali
Nov 10 2012
prev sibling next sibling parent "Dan" <dbdavidson yahoo.com> writes:
On Saturday, 10 November 2012 at 07:55:18 UTC, Raphaël Jakse 
wrote:
 Hello,

 Thanks for this complete answer. I will take a look to your 
 code.

Ok - good. I've been using 2.061 which I just realized allows "dup" on an associative array, a feature which was not available in 2.060. So mixin(Dup) and the unit tests require 2.061.
 If you didn't read it, it might interest you. Here it is:

I had not seen it and will read - thanks.
 Questions are :
 - what is the most efficient solution, and in which case ?

No string concatenation is good. I think a single pass on all important data (in most cases is all the data) is the goal.

I'm not sure I understood well. You wanted to say that string contatenations are good, right ?

I just meant string concatenation is likely unnecessary. Imagine two one megabyte strings. It is easy to concat them and call the string hash function on the result but you have to create a 2Mb string first. Alternatively, you could hash each and combine the hash codes in some consistent way.
 I was thinking about a hash function that would take several 
 arguments and hash them together. That would let take in 
 account more than one string in the hash while avoiding 
 concatenation.

Thanks Dan
Nov 10 2012
prev sibling next sibling parent reply Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 11/07/2012 07:38 AM, "Raphaël.Jakse"
<raphael.jakse gmail.com>" puremagic.com 
wrote:
 We want to be able to get the hash of s. Therefore, we re-implement the toHash
 method of the Student class :

OK, now I'm curious. Assuming I don't write a custom re-implementation, how would a custom struct or class be hashed? (What about a tuple?) I ask because I'm considering associative arrays where the key is a custom class or tuple as part of a current coding project.
Nov 10 2012
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 11/10/2012 05:37 AM, Joseph Rushton Wakeling wrote:
 On 11/07/2012 07:38 AM, "Raphaël.Jakse"
 <raphael.jakse gmail.com>" puremagic.com wrote:
 We want to be able to get the hash of s. Therefore, we re-implement
 the toHash
 method of the Student class :

OK, now I'm curious. Assuming I don't write a custom re-implementation, how would a custom struct or class be hashed? (What about a tuple?) I ask because I'm considering associative arrays where the key is a custom class or tuple as part of a current coding project.

For classes, because they are reference types, it is the object identity that determines the hash value (probably the pointer of the actual object). As a result, even when the values of the members are the same, two objects have different hash values. For structs, because they are value types, it is the bytes that make up the object determine the hash value. But beware: The associative array members of structs are not hashed by values of their elements. (There was a long discussion recently on the the main newsgroup on this topic.) Ali
Nov 10 2012
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 11/11/2012 01:11 AM, Joseph Rushton Wakeling wrote:

 So where classes are concerned there's a definite need to
 override opHash if you want the _values_ to be the basis of the
 association, rather than the object itself ... this would also have
 potential implications for memory blow-up where a class is used as the
 key type, no?

I am not sure that I understand. The associative array would still contain just class variables, not class objects. Everytime the hash needed to be calculated, the AA would call toHash() on the variable, which in turn would use the values of the members of the object. As another case, a single class object is owned by the runtime but many class variables of it can exist in multiple AAs.
 The more pressing reason for avoiding associative arrays as it happens
 was simply that I was getting unacceptably large memory usage as a
 result: I'd got some data stored in the form of byte[size_t] (really
 this should have been a set of size_t's, but this seemed theoretically
 an acceptable stop gap while there's no set class in Phobos),

I think std.container.RedBlackTree can take that responsibility but if you don't need the elements to be in any particular order, then it may be seen as an overkill as well.
 and for
 some reason that was generating memory consumption twice that of having
 instead a size_t[] regular array. I guess perhaps because although a
 byte should mean just that, in practice each value in the byte[size_t]
 associative array was taking up a whole word?

I don't know the actual implementation of AAs by dmd, but the hash buckets are probably singly-linked lists. Even if your data had no collisions, each byte would have to live in a singly-linked list.
 It's a shame, because functionally it was useful to be able to do things
 of the form if(i in list), but memory-wise it just didn't work for the
 size of data I'm dealing with.

If all you need is 'if(i in list)', then a HashSet may help. I haven't used one myself but apparently there are such data structures in other languages like Java and C#. Ali
Nov 11 2012
parent Manfred Nowak <svv1999 hotmail.com> writes:
=?UTF-8?B?QWxpIMOHZWhyZWxp?= wrote:

 but the hash buckets are probably singly-linked lists

They are unbalanced binary search trees, which indeed turn to singly-linked lists on sorted input. -manfred
Nov 11 2012
prev sibling next sibling parent "Dan" <dbdavidson yahoo.com> writes:
On Saturday, 10 November 2012 at 18:18:07 UTC, Joseph Rushton 
Wakeling wrote:
 On 11/07/2012 07:38 AM, "Raphaël.Jakse" 
 <raphael.jakse gmail.com>" puremagic.com wrote:
 We want to be able to get the hash of s. Therefore, we 
 re-implement the toHash
 method of the Student class :

OK, now I'm curious. Assuming I don't write a custom re-implementation, how would a custom struct or class be hashed? (What about a tuple?) I ask because I'm considering associative arrays where the key is a custom class or tuple as part of a current coding project.

Not sure I understand the question. But here is how I'm doing it. No guarantees, but output looks promising. Code following output. Thanks Dan ----------------------------- true false false true 7F053B2DCFC0 20883845 vs 20883845 ----------------------------- import std.stdio; import std.traits; import std.typecons; import opmix.mix; struct S { mixin(HashSupport); alias Tuple!(int, char, string) X; X x; char[] mutable; } void main() { S s1 = { tuple(3, 'a', "foo".idup), ['a','b'].dup }; S s2 = { tuple(3, 'a', "foo".idup), ['a','b'].dup }; writeln(s1==s2); s1.x[0]++; writeln(s1==s2); writeln(s1<s2); writeln(s2<s1); writeln(s1 in [ s1: 3 ]); s2.x[0]++; writeln(s1.toHash(), " vs ", s2.toHash()); }
Nov 10 2012
prev sibling next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 11/11/2012 02:35 AM, Ali Çehreli wrote:
 For classes, because they are reference types, it is the object identity that
 determines the hash value (probably the pointer of the actual object). As a
 result, even when the values of the members are the same, two objects have
 different hash values.

 For structs, because they are value types, it is the bytes that make up the
 object determine the hash value.

Ahh, clear. So where classes are concerned there's a definite need to override opHash if you want the _values_ to be the basis of the association, rather than the object itself ... this would also have potential implications for memory blow-up where a class is used as the key type, no?
 But beware: The associative array members of structs are not hashed by values
of
 their elements. (There was a long discussion recently on the the main newsgroup
 on this topic.)

I do recall that discussion, and I'll bear that in mind. So far the only practical consideration I've had was for a Tuple!() to be the key, rather than an actual struct or class; as it happens I've avoided that so far, and I think I may continue to do so while there are still issues around hashing. The more pressing reason for avoiding associative arrays as it happens was simply that I was getting unacceptably large memory usage as a result: I'd got some data stored in the form of byte[size_t] (really this should have been a set of size_t's, but this seemed theoretically an acceptable stop gap while there's no set class in Phobos), and for some reason that was generating memory consumption twice that of having instead a size_t[] regular array. I guess perhaps because although a byte should mean just that, in practice each value in the byte[size_t] associative array was taking up a whole word? It's a shame, because functionally it was useful to be able to do things of the form if(i in list), but memory-wise it just didn't work for the size of data I'm dealing with.
Nov 11 2012
prev sibling next sibling parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Jakse wrote:

 It would also be interesting to have ideas for the general
 case 

Yes, ideas might be interesting. :-) A root of "good" hashing is incorporated in algorithm2 of your posting: spread the values produced by the hash function uniformly over the interval size_t.min .. size_t.max. Therefore: Compute the hash value for a given key by multiplying each byte of the key with a factor, which increases from the byte with lowest significance to the byte with highest significance; of course add the results. Remarks: a) Because of the general case: assume that the original key contains much redundance. Therefore do not use the bytes of the original key but compute a ( at least close to) lossless compression of the original key. b) The factors in the factor list should be primes for spreading the hash value uniformly over the intended range c) The quotint of two consecutives primes in the factor list should be greater than 256, because the used key might not contain any reduundancy. -manfred
Nov 11 2012
parent reply =?ISO-8859-1?Q?Rapha=EBl_Jakse?= <raphael.jakse gmail.com> writes:
Le 11/11/2012 12:38, Manfred Nowak a crit :
 Jakse wrote:

 It would also be interesting to have ideas for the general
 case

Yes, ideas might be interesting. :-) A root of "good" hashing is incorporated in algorithm2 of your posting: spread the values produced by the hash function uniformly over the interval size_t.min .. size_t.max. Therefore: Compute the hash value for a given key by multiplying each byte of the key with a factor, which increases from the byte with lowest significance to the byte with highest significance; of course add the results. Remarks: a) Because of the general case: assume that the original key contains much redundance. Therefore do not use the bytes of the original key but compute a ( at least close to) lossless compression of the original key. b) The factors in the factor list should be primes for spreading the hash value uniformly over the intended range c) The quotint of two consecutives primes in the factor list should be greater than 256, because the used key might not contain any reduundancy. -manfred

Thanks for this interesting answer. Is compressing for performance reasons ? is it more interesting to compress and then hash than just hash ?
Nov 17 2012
parent Manfred Nowak <svv1999 hotmail.com> writes:
Raphal Jakse wrote:

 Is compressing for performance reasons?

keys is unknown, no function used for computing the hash value can be guarenteed to indeed spread the hash values uniformly over the hash interval. Compressing would have a negative effect on performance if more time for compressing and decrompessing would be needed than time was lost for resolving conflicting hash values.
 is it more interesting to compress and then hash than just
 hash ?

close to no redundancy in the keys used for hashing. If this special case is already confirmed or it is known that no compression will deminish the computing time: just hash. -manfred
Nov 17 2012
prev sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 11/11/2012 07:40 PM, Ali Çehreli wrote:
 I think std.container.RedBlackTree can take that responsibility but if you
don't
 need the elements to be in any particular order, then it may be seen as an
 overkill as well.

I know, and I probably should give that a go, but as I've got working code right now I'm moving on to something else and will come back to it later.
 If all you need is 'if(i in list)', then a HashSet may help. I haven't used one
 myself but apparently there are such data structures in other languages like
 Java and C#.

Indeed, and I was wondering whether it might be worth writing an implementation for std.containers. As it stands I don't really feel familiar enough with the underlying concepts, but I may revisit that idea once I'm done with a few other things.
Nov 11 2012