www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - storing the hash multiplier instead of the hash value

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Currently, each entry in a D hashtable stores the hash of the key for 
efficiency purposes.

There is a bit of redundancy: as soon as you entered a hash bucket you 
know that the hashkey % tablesize is a specific number, call it k. But k 
is not enough information to restore the hash, so the actual hash gets 
stored for each entry.

I'm thinking of exploiting that redundancy by storing the hash 
multiplier, not the hash value. Instead of storing h in each slot, store 
m = h / tablesize. Then you can restore the actual h by writing:

restored_h = m * tablesize + k;

k is known for each given bucket (it's the index of the bucket) and m is 
what gets stored per entry.

What's the advantage of this approach? Well the advantage is that m is a 
small number. Any hash function will try to disperse the hash value as 
much as possible between the 32 available bits. But m will be a smaller 
number, and therefore will be more grouped and will engender fewer false 
pointers.

Would this help?


Andrei
Mar 22 2010
next sibling parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
How about just *fixing* the hashtable so it doesn't generate false
pointers in the first place?  Maybe I'm just strange, but that seems
like a more direct, efficacious solution...

As for the redundancy, I was under the impression that the hash was
cached so make resizing more efficient: if the number of buckets
changes, you have to re-insert all the nodes.  If you don't store the
hash, you have to recompute it (which is expensive for anything other
than ints (wherein D laughably 'hashes' by returning the ints value)).

Given that I already think this is a silly way to go about solving the
false pointer issue, I don't see any benefit to doing this other than to
give the CPU something to do while it waits for memory reads.

Sadly, I lack the background to make any sort of objective judgement of
the hash function *itself*, so I'll just reiterate what I've heard
repeated to me over and over again by numerous people: D's builtin hash
function sucks like a black holes.
Mar 22 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/22/2010 02:50 PM, Daniel Keep wrote:
 How about just *fixing* the hashtable so it doesn't generate false
 pointers in the first place?  Maybe I'm just strange, but that seems
 like a more direct, efficacious solution...

This was of course the first thing Walter and I discussed. It turns out that that would necessitate precise GC, which we don't have yet.
 As for the redundancy, I was under the impression that the hash was
 cached so make resizing more efficient: if the number of buckets
 changes, you have to re-insert all the nodes.  If you don't store the
 hash, you have to recompute it (which is expensive for anything other
 than ints (wherein D laughably 'hashes' by returning the ints value)).

What would be a better hashing scheme for ints?
 Given that I already think this is a silly way to go about solving the
 false pointer issue, I don't see any benefit to doing this other than to
 give the CPU something to do while it waits for memory reads.

 Sadly, I lack the background to make any sort of objective judgement of
 the hash function *itself*, so I'll just reiterate what I've heard
 repeated to me over and over again by numerous people: D's builtin hash
 function sucks like a black holes.

Then you might be glad to hear that Walter has recently improved the default hashtable implementation significantly (at least for heavy-duty applications). We're using Paul Hsieh's hash function for strings and general memory, which is no slouch. http://www.dsource.org/projects/druntime/browser/trunk/src/rt/util/hash.d Better suggestions are always welcome. For integrals I'm unclear on what we could use to make things better. (Clearly we could and should get rid of the extraneous field.) Andrei
Mar 22 2010
next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 Better suggestions are always welcome. For integrals I'm unclear on what 
 we could use to make things better. (Clearly we could and should get rid 
 of the extraneous field.)

Unfortunately, it won't be much of a win. Memory allocation is done in buckets of size 16, 32, 64, etc. Reducing the node size for a uint[uint] from 16 to 12 saves no memory at all.
Mar 22 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/22/2010 03:36 PM, Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Better suggestions are always welcome. For integrals I'm unclear on
 what we could use to make things better. (Clearly we could and should
 get rid of the extraneous field.)

Unfortunately, it won't be much of a win. Memory allocation is done in buckets of size 16, 32, 64, etc. Reducing the node size for a uint[uint] from 16 to 12 saves no memory at all.

As we discussed, if nodes are allocated in bunches, you could store 5 nodes in a 64-byte block instead of 4. That's more than a 25% increase in effectiveness because the per-block bookkeeping is also slashed by 5. Andrei
Mar 22 2010
next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 As we discussed, if nodes are allocated in bunches, you could store 5 
 nodes in a 64-byte block instead of 4. That's more than a 25% increase 
 in effectiveness because the per-block bookkeeping is also slashed by 5.

Right, but the downside is that the nodes will not be collected unless all its neighbors are also not used.
Mar 22 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/22/2010 04:03 PM, Andrei Alexandrescu wrote:
 On 03/22/2010 03:36 PM, Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Better suggestions are always welcome. For integrals I'm unclear on
 what we could use to make things better. (Clearly we could and should
 get rid of the extraneous field.)

Unfortunately, it won't be much of a win. Memory allocation is done in buckets of size 16, 32, 64, etc. Reducing the node size for a uint[uint] from 16 to 12 saves no memory at all.

As we discussed, if nodes are allocated in bunches, you could store 5 nodes in a 64-byte block instead of 4. That's more than a 25% increase in effectiveness because the per-block bookkeeping is also slashed by 5. Andrei

One more idea before I forget: the bunches approach requires using a freelist for nodes that are available but not used. (Freelists are a good idea whether or not bunches are used.) One good possibility is to store the head of the freelist in a static variable, such that e.g. all int[string] instances use the same freelist. And there's no thread contention issue because each thread has its own freelist. Andrei
Mar 22 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/22/2010 04:59 PM, Andrei Alexandrescu wrote:
 On 03/22/2010 04:03 PM, Andrei Alexandrescu wrote:
 On 03/22/2010 03:36 PM, Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Better suggestions are always welcome. For integrals I'm unclear on
 what we could use to make things better. (Clearly we could and should
 get rid of the extraneous field.)

Unfortunately, it won't be much of a win. Memory allocation is done in buckets of size 16, 32, 64, etc. Reducing the node size for a uint[uint] from 16 to 12 saves no memory at all.

As we discussed, if nodes are allocated in bunches, you could store 5 nodes in a 64-byte block instead of 4. That's more than a 25% increase in effectiveness because the per-block bookkeeping is also slashed by 5. Andrei

One more idea before I forget: the bunches approach requires using a freelist for nodes that are available but not used. (Freelists are a good idea whether or not bunches are used.) One good possibility is to store the head of the freelist in a static variable, such that e.g. all int[string] instances use the same freelist. And there's no thread contention issue because each thread has its own freelist.

And the last idea before I forget (just talked to Walter about it) is that the GC could and should offer functions: GC.preCollect(void delegate()); GC.postCollect(void delegate()); That way we can effectively implement weak pointers. Andrei
Mar 22 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/22/2010 08:32 PM, Robert Jacques wrote:
 On Mon, 22 Mar 2010 19:00:57 -0300, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 [snip]
 And the last idea before I forget (just talked to Walter about it) is
 that the GC could and should offer functions:

 GC.preCollect(void delegate());
 GC.postCollect(void delegate());

 That way we can effectively implement weak pointers.

Pre and post collect should be an array of delegates. Otherwise only one person's weak pointer library would work.

Those are functions that you can call several times. The gc will keep indeed a container of delegates. Andrei
Mar 22 2010
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/23/2010 08:11 AM, Michael Rynn wrote:
 On Mon, 22 Mar 2010 16:59:36 -0500, Andrei Alexandrescu wrote:

 On 03/22/2010 04:03 PM, Andrei Alexandrescu wrote:
 On 03/22/2010 03:36 PM, Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Better suggestions are always welcome. For integrals I'm unclear on
 what we could use to make things better. (Clearly we could and should
 get rid of the extraneous field.)

Unfortunately, it won't be much of a win. Memory allocation is done in buckets of size 16, 32, 64, etc. Reducing the node size for a uint[uint] from 16 to 12 saves no memory at all.

As we discussed, if nodes are allocated in bunches, you could store 5 nodes in a 64-byte block instead of 4. That's more than a 25% increase in effectiveness because the per-block bookkeeping is also slashed by 5. Andrei

One more idea before I forget: the bunches approach requires using a freelist for nodes that are available but not used. (Freelists are a good idea whether or not bunches are used.) One good possibility is to store the head of the freelist in a static variable, such that e.g. all int[string] instances use the same freelist. And there's no thread contention issue because each thread has its own freelist. Andrei

I just committed a aaA.d version that uses some heap node memory management, although its on a per class instance basis. Also it dispences with a separate hash storage for keys<= size_t. Sharing would mean some working out of which classes share the same sized node blocks. Much easier to implement class sharing using templates. See the code here : http://www.dsource.org/projects/aa/browser/trunk/ druntime/aaA.d See the benchmarks and comments here : http://www.dsource.org/projects/aa/ wiki/DrunTimeAA. The result squeezes some extra performance for integer or less sized keys (about 20% faster for lookups). For the druntime, the generic C interface constrains the kinds of specialized AA versions that can be instantiated using run-time TypeInfo and var-arged calls. Maybe a class / interface direct calls would work better. Just imagine at runtime looking at the TypeInfo_AssociatedArray and trying to work out exactly which template is going to be instantiated. And having a low code size, one or few versions fit all approach, that performance sacrifice is unavoidable in a basic runtime libary. But in template land , options and combinations and gains abound.

Absolutely! This is solid work. It would be interesting to assess how your implementation and the old built-in hashes compare with Walter's new implementation, which uses a singly-linked list instead of a tree. Do you have what it takes to check out and build druntime and phobos? Andrei
Mar 23 2010
prev sibling next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 Then you might be glad to hear that Walter has recently improved the 
 default hashtable implementation significantly (at least for heavy-duty 
 applications).

All I did was switch from a tree used to resolve a bucket collision with a singly linked list. The improvement comes from reduced memory consumption, which for uint[uint] changes a node from 20 bytes to 16, thus halving the memory used. If the hash node still uses over 16 bytes, I doubt there will be any improvement at all. Note that the linked list implementation is equivalent to g++'s hash_map implementation.
Mar 22 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/22/2010 03:54 PM, Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Then you might be glad to hear that Walter has recently improved the
 default hashtable implementation significantly (at least for
 heavy-duty applications).

All I did was switch from a tree used to resolve a bucket collision with a singly linked list. The improvement comes from reduced memory consumption, which for uint[uint] changes a node from 20 bytes to 16, thus halving the memory used. If the hash node still uses over 16 bytes, I doubt there will be any improvement at all. Note that the linked list implementation is equivalent to g++'s hash_map implementation.

In at least one application, the new hash performed on a par with or better than g++'s hash_map. Andrei
Mar 22 2010
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/23/2010 12:08 PM, Fawzi Mohamed wrote:
 On 22-mar-10, at 21:04, Andrei Alexandrescu wrote:
 Better suggestions are always welcome. For integrals I'm unclear on
 what we could use to make things better. (Clearly we could and should
 get rid of the extraneous field.)

I like murmurhash, that I what I put into tango, see http://www.dsource.org/projects/tango/browser/trunk/tango/core/rt/compiler/util/hash.d all that file is based on freely available code and written by me, and I give my code with whatever license would be needed.

Thanks, Fawzi, that's great. I'm trying to collect evidence of MurmurHash's effectiveness versus Hsieh's SuperFastHash. I seemed to find some: http://tanjent.livejournal.com/756623.htmlhttp://tanjent.livejournal.com/756623.html I also found what seems to be a thorough benchmark: http://www.strchr.com/hash_functions Looks pretty solid to me. The benchmarks look only at strings, not at typical workloads on void* (e.g. arbitrary objects containing integers and pointers and whatnot). Hsieh's hash is smack in the middle, whereas Murmur2 is fourth, faster by 10%.
 I think that the public interface should be exposed (or re-exposed)
 somewhere to the outside so that one can easily create efficient hashes
 for user defined types.
 For example it is nice to be able to chain hash functions (something
 that the default one does not allow).

What I'm pushing for as of now is to move the associative array definition from opacity into templated goodies in object_.d. Andrei
Mar 23 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/23/2010 02:34 PM, Fawzi Mohamed wrote:
 On 23-mar-10, at 19:04, Andrei Alexandrescu wrote:

 What I'm pushing for as of now is to move the associative array
 definition from opacity into templated goodies in object_.d.

that would be nice, that is one the main reasons Steven implementation is faster. It would be nice if this would be done by the compiler as rewriting the calls as call to "normal" templates, i.e. to a specially named templated struct (AArray for example) so that (syntactic sugar for the name aside) that would be the same as a library implementation. This would have two advantages: - easy to replace the library implementation, as it would be even less special - easy to replace the usage in one piece of code with another implementation (well truth to be told that is rather easy also now)

I have much loftier goals, which scare Walter sometimes :o). In the long term, my plan is to allow object.d to decide on a number of fundamental program-wide choices, such as the use of mark-sweep GC versus reference counting GC. In wake of my experience with D in heavyset programs, I reckon that there is a necessity to have deterministic memory management for a subset of applications. Walter is afraid that that's going to mean the balkanization of D - everyone will define their own object.d. That may be a risk, but I strongly believe it's a risk worth taking. Andrei
Mar 23 2010
parent Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 Walter is afraid that that's going to mean the balkanization of D - 
 everyone will define their own object.d. That may be a risk, but I 
 strongly believe it's a risk worth taking.

It would mean the end of precompiled libraries.
Mar 23 2010
prev sibling next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Fawzi Mohamed wrote:
 
 On 23-mar-10, at 19:04, Andrei Alexandrescu wrote:
 
 What I'm pushing for as of now is to move the associative array 
 definition from opacity into templated goodies in object_.d.

that would be nice, that is one the main reasons Steven implementation is faster. It would be nice if this would be done by the compiler as rewriting the calls as call to "normal" templates, i.e. to a specially named templated struct (AArray for example) so that (syntactic sugar for the name aside) that would be the same as a library implementation. This would have two advantages: - easy to replace the library implementation, as it would be even less special - easy to replace the usage in one piece of code with another implementation (well truth to be told that is rather easy also now)

D2 already allows this.
Mar 23 2010
prev sibling parent Fawzi Mohamed <fawzi gmx.ch> writes:
On 23-mar-10, at 23:07, Walter Bright wrote:

 Fawzi Mohamed wrote:
 On 23-mar-10, at 19:04, Andrei Alexandrescu wrote:
 What I'm pushing for as of now is to move the associative array  
 definition from opacity into templated goodies in object_.d.

implementation is faster. It would be nice if this would be done by the compiler as rewriting the calls as call to "normal" templates, i.e. to a specially named templated struct (AArray for example) so that (syntactic sugar for the name aside) that would be the same as a library implementation. This would have two advantages: - easy to replace the library implementation, as it would be even less special - easy to replace the usage in one piece of code with another implementation (well truth to be told that is rather easy also now)

D2 already allows this.

ok I did not know that was possible.
Mar 23 2010
prev sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Fawzi Mohamed wrote:
 I think that the public interface should be exposed (or re-exposed) 
 somewhere to the outside so that one can easily create efficient hashes 
 for user defined types.
 For example it is nice to be able to chain hash functions (something 
 that the default one does not allow).

Just overload the toHash() function for your user-defined type to be whatever you want it to be.
Mar 23 2010
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 22 Mar 2010 19:00:57 -0300, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:
[snip]
 And the last idea before I forget (just talked to Walter about it) is  
 that the GC could and should offer functions:

 GC.preCollect(void delegate());
 GC.postCollect(void delegate());

 That way we can effectively implement weak pointers.

Pre and post collect should be an array of delegates. Otherwise only one person's weak pointer library would work.
Mar 22 2010
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 22 Mar 2010 17:04:56 -0300, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 03/22/2010 02:50 PM, Daniel Keep wrote:
 How about just *fixing* the hashtable so it doesn't generate false
 pointers in the first place?  Maybe I'm just strange, but that seems
 like a more direct, efficacious solution...

This was of course the first thing Walter and I discussed. It turns out that that would necessitate precise GC, which we don't have yet.

What about the precise GC patch? http://d.puremagic.com/issues/show_bug.cgi?id=3463
Mar 22 2010
prev sibling next sibling parent Michael Rynn <michaelrynn optusnet.com.au> writes:
On Mon, 22 Mar 2010 16:59:36 -0500, Andrei Alexandrescu wrote:

 On 03/22/2010 04:03 PM, Andrei Alexandrescu wrote:
 On 03/22/2010 03:36 PM, Walter Bright wrote:
 Andrei Alexandrescu wrote:
 Better suggestions are always welcome. For integrals I'm unclear on
 what we could use to make things better. (Clearly we could and should
 get rid of the extraneous field.)

Unfortunately, it won't be much of a win. Memory allocation is done in buckets of size 16, 32, 64, etc. Reducing the node size for a uint[uint] from 16 to 12 saves no memory at all.

As we discussed, if nodes are allocated in bunches, you could store 5 nodes in a 64-byte block instead of 4. That's more than a 25% increase in effectiveness because the per-block bookkeeping is also slashed by 5. Andrei

One more idea before I forget: the bunches approach requires using a freelist for nodes that are available but not used. (Freelists are a good idea whether or not bunches are used.) One good possibility is to store the head of the freelist in a static variable, such that e.g. all int[string] instances use the same freelist. And there's no thread contention issue because each thread has its own freelist. Andrei

I just committed a aaA.d version that uses some heap node memory management, although its on a per class instance basis. Also it dispences with a separate hash storage for keys <= size_t. Sharing would mean some working out of which classes share the same sized node blocks. Much easier to implement class sharing using templates. See the code here : http://www.dsource.org/projects/aa/browser/trunk/ druntime/aaA.d See the benchmarks and comments here : http://www.dsource.org/projects/aa/ wiki/DrunTimeAA. The result squeezes some extra performance for integer or less sized keys (about 20% faster for lookups). For the druntime, the generic C interface constrains the kinds of specialized AA versions that can be instantiated using run-time TypeInfo and var-arged calls. Maybe a class / interface direct calls would work better. Just imagine at runtime looking at the TypeInfo_AssociatedArray and trying to work out exactly which template is going to be instantiated. And having a low code size, one or few versions fit all approach, that performance sacrifice is unavoidable in a basic runtime libary. But in template land , options and combinations and gains abound. --- Michael Rynn
Mar 23 2010
prev sibling parent reply Fawzi Mohamed <fawzi gmx.ch> writes:
On 22-mar-10, at 21:04, Andrei Alexandrescu wrote:

 On 03/22/2010 02:50 PM, Daniel Keep wrote:
 Sadly, I lack the background to make any sort of objective  
 judgement of
 the hash function *itself*, so I'll just reiterate what I've heard
 repeated to me over and over again by numerous people: D's builtin  
 hash
 function sucks like a black holes.

Then you might be glad to hear that Walter has recently improved the default hashtable implementation significantly (at least for heavy- duty applications). We're using Paul Hsieh's hash function for strings and general memory, which is no slouch. http://www.dsource.org/projects/druntime/browser/trunk/src/rt/util/hash.d Better suggestions are always welcome. For integrals I'm unclear on what we could use to make things better. (Clearly we could and should get rid of the extraneous field.)

I like murmurhash, that I what I put into tango, see http://www.dsource.org/projects/tango/browser/trunk/tango/core/rt/compiler/util/hash.d all that file is based on freely available code and written by me, and I give my code with whatever license would be needed. I think that the public interface should be exposed (or re-exposed) somewhere to the outside so that one can easily create efficient hashes for user defined types. For example it is nice to be able to chain hash functions (something that the default one does not allow). Fawzi
Mar 23 2010
next sibling parent Sea Kelly <sean invisibleduck.org> writes:
I like murmurhash as well, and I'd even had it in druntime briefly, but
it uses a proprietary license and I couldn't get permision from the
author to use it. It's also an order of magnitude slower on sparc than
x86. 
Fawzi Mohamed <fawzi gmx.ch> wrote:
 
 On 22-mar-10, at 21:04, Andrei Alexandrescu wrote:
 
 On 03/22/2010 02:50 PM, Daniel Keep wrote:
 Sadly, I lack the background to make any sort of objective  >>
 judgement of
 the hash function *itself*, so I'll just reiterate what I've heard
 repeated to me over and over again by numerous people: D's builtin 
 hash



Then you might be glad to hear that Walter has recently improved the > default hashtable implementation significantly (at least for heavy- > duty applications). We're using Paul Hsieh's hash function for strings and general > memory, which is no slouch. http://www.dsource.org/projects/druntime/browser/trunk/src/rt/util/hash.d Better suggestions are always welcome. For integrals I'm unclear on
 what we could use to make things better. (Clearly we could and  >
 should get rid of the extraneous field.)


I like murmurhash, that I what I put into tango, see http://www.dsource.org/projects/tango/browser/trunk/tango/core/rt/compiler/util/hash.d all that file is based on freely available code and written by me, and I give my code with whatever license would be needed. I think that the public interface should be exposed (or re-exposed) somewhere to the outside so that one can easily create efficient hashes for user defined types. For example it is nice to be able to chain hash functions (something that the default one does not allow). Fawzi

Mar 30 2010
prev sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Tue, 30 Mar 2010 16:17:20 -0300, Sea Kelly <sean invisibleduck.org>  
wrote:

 I like murmurhash as well, and I'd even had it in druntime briefly, but
 it uses a proprietary license and I couldn't get permision from the
 author to use it. It's also an order of magnitude slower on sparc than
 x86.

That seems weird. The website it lists it as: "All code is released to the public domain. For business purposes, Murmurhash is under the MIT license."
Mar 30 2010
parent Sean Kelly <sean invisibleduck.org> writes:
"Robert Jacques" <sandford jhu.edu> wrote:
 On Tue, 30 Mar 2010 16:17:20 -0300, Sea Kelly <sean invisibleduck.org>
  wrote:
 
 I like murmurhash as well, and I'd even had it in druntime briefly,
 but
 it uses a proprietary license and I couldn't get permision from the
 author to use it. It's also an order of magnitude slower on sparc
 than
 x86.

That seems weird. The website it lists it as: "All code is released to the public domain. For business purposes, Murmurhash is under the MIT license."

That must be new, I couldn't find any license at all at the time. I emailed the author about it and he never replied, jough he'd been helpful with other issues. Or perhaps I jus missed it.
Apr 11 2010
prev sibling next sibling parent Lionello Lunesu <lio lunesu.remove.com> writes:
On 23-3-2010 1:51, Andrei Alexandrescu wrote:
 Currently, each entry in a D hashtable stores the hash of the key for
 efficiency purposes.
 
 There is a bit of redundancy: as soon as you entered a hash bucket you
 know that the hashkey % tablesize is a specific number, call it k. But k
 is not enough information to restore the hash, so the actual hash gets
 stored for each entry.
 
 I'm thinking of exploiting that redundancy by storing the hash
 multiplier, not the hash value. Instead of storing h in each slot, store
 m = h / tablesize. Then you can restore the actual h by writing:
 
 restored_h = m * tablesize + k;
 
 k is known for each given bucket (it's the index of the bucket) and m is
 what gets stored per entry.
 
 What's the advantage of this approach? Well the advantage is that m is a
 small number. Any hash function will try to disperse the hash value as
 much as possible between the 32 available bits. But m will be a smaller
 number, and therefore will be more grouped and will engender fewer false
 pointers.
 
 Would this help?

Probably not. hash is an 'int' and this 'm' will still use up the same space as an int, I reckon. Even if it ends up being 16-bit and can be put in a short, alignment will probably cause it to consume 32-bits anyway. What's more the 16-bit access (not to mention the multiplier) will slow the AA down. I say, leave it be. L.
Mar 22 2010
prev sibling next sibling parent Leandro Lucarella <llucax gmail.com> writes:
Andrei Alexandrescu, el 22 de marzo a las 15:04 me escribiste:
 On 03/22/2010 02:50 PM, Daniel Keep wrote:
How about just *fixing* the hashtable so it doesn't generate false
pointers in the first place?  Maybe I'm just strange, but that seems
like a more direct, efficacious solution...

This was of course the first thing Walter and I discussed. It turns out that that would necessitate precise GC, which we don't have yet.

Well... there is an implementation hanging in bugzilla... -- Leandro Lucarella (AKA luca) http://llucax.com.ar/ ---------------------------------------------------------------------- GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) ----------------------------------------------------------------------
Mar 23 2010
prev sibling next sibling parent Fawzi Mohamed <fawzi gmx.ch> writes:
On 23-mar-10, at 19:04, Andrei Alexandrescu wrote:

 What I'm pushing for as of now is to move the associative array  
 definition from opacity into templated goodies in object_.d.

that would be nice, that is one the main reasons Steven implementation is faster. It would be nice if this would be done by the compiler as rewriting the calls as call to "normal" templates, i.e. to a specially named templated struct (AArray for example) so that (syntactic sugar for the name aside) that would be the same as a library implementation. This would have two advantages: - easy to replace the library implementation, as it would be even less special - easy to replace the usage in one piece of code with another implementation (well truth to be told that is rather easy also now) Fawzi
Mar 23 2010
prev sibling parent Fawzi Mohamed <fawzi gmx.ch> writes:
On 23-mar-10, at 23:02, Walter Bright wrote:

 Fawzi Mohamed wrote:
 I think that the public interface should be exposed (or re-exposed)  
 somewhere to the outside so that one can easily create efficient  
 hashes for user defined types.
 For example it is nice to be able to chain hash functions  
 (something that the default one does not allow).

Just overload the toHash() function for your user-defined type to be whatever you want it to be.

I know, maybe I have not expressed myself clearly, but this overridden function has to be written. For objects combining various pieces, one has to create a unique hash from various pieces. The functions I have defined in hash.d help in doing that is such a way that changing a bit anywhere most likely changes the whole hash.
Mar 23 2010