Loading ...
Sorry, an error occurred while loading the content.

Memory Consumption Optimisations for the dbm_fc_solver On the Repository Tip

Expand Messages
  • Shlomi Fish
    Hi 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
    Message 1 of 1 , May 23, 2012
    • 0 Attachment
      Hi 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:

      fcs_encoded_state_buffer_t key;
      fcs_encoded_state_buffer_t parent_and_move;
      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

      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 .
    Your message has been successfully submitted and would be delivered to recipients shortly.