Enhanced FF

The new open queue implementation shows a significant speed-up in the Pipesworld domains. Figure 14 shows the difference in CPU time for the two different Pipesworld domains (note the logarithmic time scale). The simplest problems at the left of these charts are solved so quickly that no data bar is drawn. The speedup depends on the problem instance with maximum gains reaching a factor of 10. As a result two more problems were solved in the Pipesworld Tankage Non-Temporal domain and one more problem in the Pipesworld No-Tankage Non-Temporal domain.

The new 64-bit state hashing is especially effective in the PSR and Promela Dining Philosophers domains. Figure 15 shows a speed-up of up to a factor of 2.5. This resulted in 3 more problems solved in PSR, contributing to the success of MACRO-FF in this domain.

The reduced memory requirement is important in Promela Optical Telegraph. Figure 16 shows the memory requirement of the original FF for the initial facts lookup table. As a result of the replacement of the lookup table, 3 more problems were solved in this domain.

Figure 14: Comparison of old and new open queue implementation in Pipesworld Tankage Non-Temporal (left) and Pipesworld No-Tankage Non-Temporal (right). Results are shown for sets of 50 problems in each domain.

Figure 15: Comparison of the two implementations of state hashing in PSR (left) and Promela Dining Philosophers (right). Results are shown for 50 problems in PSR and 48 problems in Promela Dining Philosophers.

Figure 16: Size of the data structures for initial facts in the old implementation (lookup table) and the new implementation (balanced tree) in Promela Optical Telegraph.