Message5843

Author jendrik
Recipients andrew.coles, erez, florian, jendrik, malte, silvia
Date 2016-11-30.19:10:59
Content
Malte and I analyzed the memory profiles of A* + blind search for pegsol-opt11-strips:p03.pddl today and noted 
where we use how much memory in a 32-bit, 64-bit and ideal version. Here are the numbers:


A* + blind search                                  32-bit          64-bit           ideal

---------------------------------------------------------------------------------------------------------------

PerStateInformation<SearchNodeInfo>              16 Bytes        24 Bytes         8 Bytes (parent state + g)
(parent state, creating operator, g, real g)

PerStateInformation<HEntry>                       4 Bytes         4 Bytes         0 Bytes (for blind search)
(h-cache)

State registry - state data                     4*B Bytes       4*B Bytes       4*B Bytes (B = #buckets)
(h-cache)

State registry - hash table                     ~17 Bytes       ~34 Bytes        ~5 Bytes (4 Bytes + overhead)
(h-cache)

Open list                                         4 Bytes         4 Bytes         4 Bytes (per open-list entry)

---------------------------------------------------------------------------------------------------------------

Total                                           ~45 Bytes       ~70 Bytes       ~21 Bytes (in example with B=1)


We have already started to reduce the size of SearchNodeInfo by storing operator IDs (ints) instead of 
GlobalOperator pointers. Next, we will be looking into more memory-efficient hash table implementations, probably 
using open addressing instead of separate chaining like std::unordered_set.
History
Date User Action Args
2016-11-30 19:10:59jendriksetmessageid: <1480529459.59.0.225427932395.issue213@unibas.ch>
2016-11-30 19:10:59jendriksetrecipients: + jendrik, malte, erez, andrew.coles, silvia, florian
2016-11-30 19:10:59jendriklinkissue213 messages
2016-11-30 19:10:59jendrikcreate