Memory Consumption Optimisations for the dbm_fc_solver On the Repository Tip
- View SourceHi all,
this message aims to detail some of the recent optimisations done to reduce
memory consumption in regards to the dbm_fc_solver in the repository tip here:
1. The first thing that was done (and it was done quite some time ago) was
switching the balanced binary tree to "avl.c" from libavl, which doesn't use
parent pointers for its tree nodes. This saved an extra pointer - or 8 bytes
per states (because on 64-bit machines, pointers take 8 bytes).
2. Afterwards the queue used by the dbm_fc_solver was converted to an
offloading-to-hard-disk queue. Such a queue splits the data into constant-sized
frames, each assigned a serial index, and offloads the middle frames (i.e:
those not at the head or tail of the queue) to the hard-disk. It was prototyped
in Perl and later on translated to C, and works pretty well. You can find it
This saves us from having to store the queue's items in RAM, while we can use
the hard-disk instead, and also since frames are vectors, they waste less space
than a linked list which has a pointer for each item.
3. After that, I decided to store the raw items of the AVL tree directly in the
tree's nodes, instead of allocate them dynamically and store them as pointers
(which was somewhat wasteful). This required extensively patching libavl/avl.c,
but worked pretty well.
3. Then I took a closer look at the way the items were stored in
the binary tree. It looked something like that:
signed char avl_balance;
Since fcs_encoded_state_buffer_t take 24 bytes, it is more wasteful than an
8-byte pointer. I don't need parent_and_move - just its pointer (which by
virtue of the tree implementation remains constant throughout the program's
run). So I converted it to a pointer, and placed the move in one of the bytes
of "key", which is 24 bytes for alignment, and never reached more than 18
occupied bytes and so has some bytes to spare.
Similarly, I've also moved avl_balance inside key, so it won't waste
avl_balance's 8 bytes in total for alignment.
4. Afterwards, I realised I can reduce the size of the queue's frames by
keeping only pointers instead of the keys, for similar reasons. This does not
save a lot of RAM, but it does cuts the hard-disk space consumption to a third
of its original value. As a result, it was implemented too.
All these memory consumption optimisations appear to have made the RAM
consumption of the dbm_fc_solver better, but like I said, I'd like to look into
the Partial IDA* scan to improve matters even more.
Shlomi Fish http://www.shlomifish.org/
Escape from GNU Autohell - http://www.shlomifish.org/open-source/anti/autohell/
I hope that if it had not been clear before, it isn’t less clear now.
— One of Shlomi Fish’s Technion Lecturers
Please reply to list if it's a mailing list post - http://shlom.in/reply .