Hash speed and memory usage

[Evert]

I think you're going about this the wrong way. Using static arrays for things like the hash table is a bad idea. Doesn't matter if it's faster in one particular test on one particular system right now. You're making things more complicated and potentially limit yourself in the future. At best this is a case of premature optimisation.

Let's phrase this another way: hash table access is not the bottleneck in your program - and if you find that it is, that probably means there is something wrong.

[cdani]

Yes, I understand the point. Anyway I learned a lot , and may be someone else reading all this stuff.
Now I will devote to improve the bad moves the engine is doing in the tournaments that Graham is running
Thanks.

[jdart]

Global memory access can be a bottleneck in multithreaded programs, especially in systems with multiple physical CPUs. There are several reasons for this.

There is less of an issue with single-threaded programs but you may need to be wary of unaligned memory access.

Have you considered storing the static eval in the main hashtable? Quite a few programs do this.

--Jon

[cdani]

Global memory access can be a bottleneck in multithreaded programs, especially in systems with multiple physical CPUs. There are several reasons for this.

There is less of an issue with single-threaded programs but you may need to be wary of unaligned memory access.

Have you considered storing the static eval in the main hashtable? Quite a few programs do this.

--Jon

Thanks! I will try.

[Gerd Isenberg]

I have found more or less a solution! I suppose it's related on how the cpu handles the memory.
It was enough to manually setting the hash memory to 0 with a for loop after doing the same with memset, and now it goes quite faster. Following the example I put before, now requires 35250 milliseconds. It's slower than with a static array, but a lot better.
I tried in different ways, and the faster was this dirty one, at least on my system:

Code: Select all

memset(thishash, 0, numofbytes);

char *j;
int i;
j=(char*)uintptr_t(thishash);
for (i=0;i<numofbytes;i++)
	  *j=1;
for (i=0;i<numofbytes;i++)
	  *j=0;

If I do with only the second for loop, it's slower. And if I add a third for loop, also it's slower.
With static array this trick it's not necessary, so clearly the system handles different the two types of memory.

But all those things sure will be different from system to system, so I suppose the best approach is to use static arrays for hash that will be little in size, and malloc hash for the bigger ones.

At last, may be this will be useful to someone, at least to avoid crashing his head

And now we return to one of the starting questions, about the size of static memory usage that you consider fair.

Thanks for your patience!

Todays super pipelined processors along with memory/caches with all their heuristics sometimes behave a bit chaotic. A lot happens simultaneously even within one thread, which memory pages stay in the caches, etc.. Tiny code or data changes sometimes have distinguishable impact, f.i. re-arranging some global or local data and struct/class members.

You may use static arrays for const tables or once initialized lookup tables i.e. for magic attacks, piece imbalance tables and such stuff with a fixed size, may be up to a few MByte. For hashtables it is preferable to allocate them from the heap at initialization time with variable and configurable sizes dependent on the system and physical memory size. Some force power of two sizes to use the "and" size-1 trick instead of more expensive modulo size for the index calculation. Also, with multiple threads, you may want to try a shared versus local eval hash, i.e. passed by a pointer to the thread constructor.

Otoh, for the huge trans-table due to latency and TLB misses, there is the question whether to use them in quiescene or not, and a smaller eval-cache might be a good alternative for qsearch. See Dieter Buerssner's dblat memory latency experiment, which made some of us aware of TLB issues:
http://www.stmintz.com/ccc/index.php?id=306858

[cdani]

It's very interesting!
Thanks.