FreePascal and HashTables' size problem/anomaly

[JuLieN]

(Note to the reader : forgive me in advance, but this will be quite a technical reading for you ... )

I've been working recently on diminishing Prédateur's memory footprint and was quite successful :

- the latest public Prédateur (Pred 2.0) uses about 450 MB of RAM, including 128 MB of hashtables,
- whereas my latest beta, Pred 2.1 now uses around 223 MB of RAM, including 128 MB of hashtables.

To do that, I changed lots of data structures, especially my previously HUGE HistoryKillers array, that was around 150 MB big and is now 0.9 MB big.

Problem is :

223 - 128 = 95 MB
I also have a 8 MB pawnhash, so :
95-8 = 87 MB of non-hash memory use

BUT... When I sum up all my other arrays, they're about 3 MB big in total. So where does the rest of the memory use come from ?

As I saw no other way to reduce any more my memory use, I made some experiments and found something strange :

Prédateur with a 128 MB Hashtable : 97 MB of non-hash memory use
Prédateur with a 64 MB Hashtable : 63 MB of non-hash memory use
Prédateur with a 8 MB Hashtable : 32 MB of non-hash memory use

Clearly, the "non-hahs" memory use actually increases when the hash's size does. So there must be something wrong with the way I compute my hashtable's size. Problem is, I double-checked everything and can't find what's wrong. Here are the details of my implementation :


Here's a hash "slot" (my hash tables is a dynamical array made of such records) :

Code: Select all

Hash = record
ZobristKey : Int64;                   //8  bytes
Depth : SmallInt;                     //2  bytes
Flag    : ShortInt;                     //1  bytes
Score : SmallInt;                     //2  bytes
Move  : array[1..3] of ShortInt; //3  bytes
end;                                       //Total : 16 bytes 

As you can see, the total size of a slot is of 16 bytes. Here is what the FreePascal's wiki says about data types' sizes :

From the FPC manual
integer types
Type Range Bytes
Byte 0 .. 255 1
Shortint -128 .. 127 1
Smallint -32768 .. 32767 2
Word 0 .. 65535 2
Integer smallint or longint 2 or 4
Cardinal longword 4
Longint -2147483648 .. 2147483647 4
Longword 0..4294967295 4
Int64 -9223372036854775808 .. 9223372036854775807 8
QWord 0 .. 18446744073709551615 8

(Source, for a better layout : http://wiki.freepascal.org/Variables_and_Data_Types )

Then, when I set the hashtable's size to 128 MB (for instance) I compute the number of slots that way :

NbOfSlots := (128 * 1024 * 1024) div 16;

And I set it to this length doing a SetLength :

SetLength(HashTable, NbOfSlots);


So, what is wrong? Are the datatypes of a different size than advertised on the FreePascal's wiki, or is there some additional memory used to handle dynamical arrays of records ?

I'm stuck!

[Joost Buijs]

Is it possible that your problem will be solved if you use packed records instead of normal (unpacked) records?
The compiler probably is aligning each record field on a 64 bit boundary.

[JuLieN]

Is it possible that your problem will be solved if you use packed records instead of normal (unpacked) records?
The compiler probably is aligning each record field on a 64 bit boundary.

Joost, you're a GENIUS! I tried your suggestion and it works!!! Pred with a 128 MB hash now uses around 150 MB of memory, instead of 223 MB!

Thanks a lot!!!

EDIT: the strange thing is... shouldn't a 16-bytes (= 128 bits = 2x64 bits) be 64-bits aligned anyway?

[Joost Buijs]

Each field is aligned on 64 bits even the byte values, this will speed up things a little bit, but in practice you wont notice any difference.

I also have a problem with free Pascal, I wont let me allocate more than 4 gig. memory. I tried everything, even linking a module with C++ memory allocation modules but this didn't solve it either. Probably the heap is still in a 32 bit segment or something like that.

[JuLieN]

Each field is aligned on 64 bits even the byte values, this will speed up things a little bit, but in practice you wont notice any difference.

Ok, I see... that was very ineffective, considering I had at least four fields that were a byte big...

I also have a problem with free Pascal, I wont let me allocate more than 4 gig. memory. I tried everything, even linking a module with C++ memory allocation modules but this didn't solve it either. Probably the heap is still in a 32 bit segment or something like that.

This might be OS-related. For what OS are you trying to use such big data structures?

[Joost Buijs]

I use the 2.5.1 compiler with Lazarus on Windows 7 Ultimate 64 bit.
When I have some time I will try it on Linux to see what happens.

[JuLieN]

This thread might interest you :
http://free-pascal-general.1045716.n5.n ... 22981.html

I just tried to compile this small example of a 5GB big array on my 64bits MacOS X :

Code: Select all

program test;

var
  BigArray : array[1..5000000000] of byte;
begin
  writeln('Small program, big needs!');
  Readln;
end.

and got a "project1.lpr(4,33) Error: The range of the array is too large
" error message... But I don't remember if my fpc is 32 or 64 bits...

As for me, I now converted all my records to packed records and Prédateur now uses 142 MB of memory. Which means that it uses 142 - 128 (hashtable) - 8 (pawnhash) = 6MB of non-hash memory. It could probably still be tweaked a bit but it's much more reasonable than the 450 - 128 - 16 = 306 MB of non-hash memory used by Pred 2.0

[JuLieN]

Another thread of interest :

http://62.166.198.202/bug_view_page.php ... &history=1

Especially :

(0020800) Marco van de Voort (manager) 2008-07-18 23:13

Note that more than 2GB memory, and more than 2GB consecutive memory might not be the same.

Also, 64-bit windows binaries should have {$setpeflags $20} in the header ?

(0020805) Yury Sidorov (manager) 2008-07-18 23:45

Try to allocate memory for the array in runtime.

(0020818) Florian Klämpfl (administrator) 2008-07-19 19:35

The internal linker probably needs some consistence checks for section sizes.

(0020859) IanC (reporter) 2008-07-22 10:58

Setting {$setpeflags $20} makes no difference.
Allocating the array at runtime instead makes no difference.

If I do the same thing in MS Visual C++ (Visual Studio 2005) I am able to create arrays of many gigabytes.

(0020861) Marco van de Voort (manager) 2008-07-22 11:50

Florian:
Note that when I tried it a few months back(using smaller blocks) it also didn't work.

So there is most certainly a 2GB limit with smaller datastructures. It is not *just* a one big array problem

(0020867) Yury Sidorov (manager) 2008-07-22 13:59

Dynamic allocation should work in rev. 11433 of FPC trunk. Please test.

Static data is limited by 2GB due to internal linker bugs, which will be fixed later.

(0020875) Marc Weustink (administrator) 2008-07-22 23:50

I can confirm that dynamic allocating upto 9GB works here on XP64 (4GB physical + 8GB swap)

(0020990) Yury Sidorov (manager) 2008-07-28 23:59

Static data is limited by 4GB image size on win64 now. It is PE32+ limitation.

The last sentence is very interesting : "Static data is limited by 4GB image size on win64 now. It is PE32+ limitation.".

So, with this 2008-old thread I can say three things :
1- if there was a problem, it is fixed, now;
2- you might have to add a {$setpeflags $20} in your header;
3- you might want to make your array dynamical if it was static.

[Joost Buijs]

Hi Julien,

Thanks for sending me these links!

I need this big amount of memory for the transposition table and the indices of the table bases.
Loading all 6 piece Nalimov TB's takes about 2.5 gig. so there is not much room left for the TT.

[bob]

(Note to the reader : forgive me in advance, but this will be quite a technical reading for you ... )

I've been working recently on diminishing Prédateur's memory footprint and was quite successful :

- the latest public Prédateur (Pred 2.0) uses about 450 MB of RAM, including 128 MB of hashtables,
- whereas my latest beta, Pred 2.1 now uses around 223 MB of RAM, including 128 MB of hashtables.

To do that, I changed lots of data structures, especially my previously HUGE HistoryKillers array, that was around 150 MB big and is now 0.9 MB big.

Problem is :

223 - 128 = 95 MB
I also have a 8 MB pawnhash, so :
95-8 = 87 MB of non-hash memory use

BUT... When I sum up all my other arrays, they're about 3 MB big in total. So where does the rest of the memory use come from ?

As I saw no other way to reduce any more my memory use, I made some experiments and found something strange :

Prédateur with a 128 MB Hashtable : 97 MB of non-hash memory use
Prédateur with a 64 MB Hashtable : 63 MB of non-hash memory use
Prédateur with a 8 MB Hashtable : 32 MB of non-hash memory use

Clearly, the "non-hahs" memory use actually increases when the hash's size does. So there must be something wrong with the way I compute my hashtable's size. Problem is, I double-checked everything and can't find what's wrong. Here are the details of my implementation :


Here's a hash "slot" (my hash tables is a dynamical array made of such records) :

Code: Select all

Hash = record
ZobristKey : Int64;                   //8  bytes
Depth : SmallInt;                     //2  bytes
Flag    : ShortInt;                     //1  bytes
Score : SmallInt;                     //2  bytes
Move  : array[1..3] of ShortInt; //3  bytes
end;                                       //Total : 16 bytes 

As you can see, the total size of a slot is of 16 bytes. Here is what the FreePascal's wiki says about data types' sizes :

From the FPC manual
integer types
Type Range Bytes
Byte 0 .. 255 1
Shortint -128 .. 127 1
Smallint -32768 .. 32767 2
Word 0 .. 65535 2
Integer smallint or longint 2 or 4
Cardinal longword 4
Longint -2147483648 .. 2147483647 4
Longword 0..4294967295 4
Int64 -9223372036854775808 .. 9223372036854775807 8
QWord 0 .. 18446744073709551615 8

(Source, for a better layout : http://wiki.freepascal.org/Variables_and_Data_Types )

Then, when I set the hashtable's size to 128 MB (for instance) I compute the number of slots that way :

NbOfSlots := (128 * 1024 * 1024) div 16;

And I set it to this length doing a SetLength :

SetLength(HashTable, NbOfSlots);


So, what is wrong? Are the datatypes of a different size than advertised on the FreePascal's wiki, or is there some additional memory used to handle dynamical arrays of records ?

I'm stuck!

What, exactly, are you measuring and how? There are library buffers, a large program stack, lots of instructions, lots of linked in library modules, etc. Without knowing exactly what you are measuring and how you are measuring it, it is impossible to guess.