Author: Robert Hyatt
Date: 17:58:05 03/19/99
Go up one level in this thread
On March 19, 1999 at 16:06:10, Inmann Werner wrote:
>Hello.
>
>Today I changed my hashtables from fixed one ta allocated one.
>
>Example
>Old
>
>long hindex[65536]
>signed char hcolor[65536]
>signed short int value[65536]
>.....
>
>New
>
>long *hindex
>signed char *hcolor
>signed short int *value
>....
>
>hindex=malloc(4*65536)
>hcolor=malloc(65536)
>value=malloc(2*65536)
>....
>
>Works fine but:
>
>On my P90, the NPS decreases about 30% !!!!!
>On my Cyrix 233 everything is fine (same speed)
>
>Do I anything extremly wrong or what happens here. Has this something to do
>with Prozessor cache or what?
>
>Any suggestions??
>
>Werner
>
>P.S.: Excuse my C, I come from Cobol....
>I use Watcom C Version 11 Compiler.
here is one useful trick: The PC L2 cache is fetched in blocks of 32 bytes
from memory in a 'burst'. You want to make sure that a hash entry doesn't
'span' two cache lines if you can help it. Here is a way:
TABLE *hash_table
hash_table=malloc(tablesize+15);
hash_table=(hash_table+15)&~15;
what that does (and you will probably have to do some casting to void * to make
the compiler accept some of the above) is do the malloc for the normal size +
15 bytes, then we add 15 to that pointer and then scrub the low order 4 bits to
make the pointer align on 16 byte (and also 32 byte) boundaries. malloc() will
align on the boundary required by the hardware, which generally tops out at 8
bytes. This aligns it better.
Although I am not saying that is your problem...
Your problem is that a single hash table entry is scattered all over memory,
so that if you have draft, value, move, wtm, signature, you need _five_ cache
line fills to get one entry.
Put the whole entry into a structure like this:
struct hash_entry {
long long signature
short value;
short move;
etc.
}
then use htable->signature to get to the signature, htable->value to get to
the value. Now with everything in adjacent bytes, one memory 'burst' will suck
in the whole hash entry and each value can be accessed in cache speed, rather
than memory speed.
it will make a huge difference...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.