search

aig-upf / fs-private

This is the private version of the FS planner repository
GNU General Public License v3.0
5 stars 1 forks source link

Check Match-Tree performance #23

Closed gfrances closed 7 years ago

gfrances commented 7 years ago

I don't have much time to check this now, but we should perhaps have a look at why the match tree successor generation strategy (see #6) is not outperforming the naive one? Is that to be expected?

In some domains, it indeed clearly outperforms it, but in others it is exactly the other way roung. This deserve further examination.

gfrances commented 7 years ago

As a side note, perhaps MatchTreeActionManager can directly subclass NaiveActionManager and spare all the precomputations required in SmartActionManager?

miquelramirez commented 7 years ago

That would help, but I have never been a fan of this Match Tree thing... if our language was restricted to finite domain variables, with small domains, it does make a difference (i.e. like SAS+). In binary domains the results are quite a mixed bag, and when you have variables with dense domains, the approach just doesn't work, requiring some real knowledge compilation techniques to be in-place (e.g. using XDD and ADDs etc.).

miquelramirez commented 7 years ago

Not just the performance, but also we need to check whether it works. My tests indicated so, but now I see it is getting stuck on Thoughtful instances.

gfrances commented 7 years ago

This seems rather advanced with the latest commits, but still the memory footprint seems to be rather high, provoking OOM too often which I suspect happen during match-tree construction time. We need to check this.

gfrances commented 7 years ago

Commit 41723c4aa698704720d58b7a86d04f6d6b3e0bfe solves a memory leak in the match tree component, but I suspect this wont reduce the memory consumption, as memory is only freed at termination time.

miquelramirez commented 7 years ago

Okay, I have done a couple passes on the MatchTree construction code and the only obvious thing I have found is that a pretty big (potentially) index I used to keep track of what actions require in the preconditions a given atom, was not being destroyed after the tree itself was created. This can hold up significant space on the bigger instances.

See Pull Request -- https://github.com/aig-upf/fs-private/pull/32

gfrances commented 7 years ago

@miquelramirez , @nirlipo : I've been looking briefly again at the performance of the Match Tree on large instances. This is what I get on the cluster on CityCar/p4-5-3-0-1 with the latest version:

[INFO][ 1.26669] Successor Generator Strategy: Match Tree [INFO][ 1.26687] Peak mem. usage before match-tree construction: 107836 kB. [INFO][ 1.26703] Current mem. usage before match-tree construction: 61912 kB. [INFO][ 1.26715] [Match Tree] MatchTreeActionManager::MatchTreeActionManager() starts... [INFO][ 1.26722] Current mem. usage: 62008 kB. [INFO][ 1.38734] [Match Tree] Atom -> Action Index built... [INFO][ 1.38754] Current mem. usage: 62864 kB. [INFO][ 5.39533] [Match Tree] Basic Analyzer built... [INFO][ 5.39555] Current mem. usage: 411984 kB. [INFO][ 5.39567] [Match Tree] Calling BaseNode::create_tree() [INFO][ 5.39571] Current mem. usage: 412196 kB. [INFO][ 5.39617] [Match Tree] Size of Variable Selection Heuristic array: 3526 [INFO][ 5.39621] Current mem. usage after match-tree construction: 412204 kB. [INFO][212.18802] Match Tree created [INFO][212.18826] Current mem. usage: 4262908 kB. [INFO][216.02968] Match-tree built with 16439 nodes. [INFO][216.02999] Peak mem. usage after match-tree construction: 4417264 kB. [INFO][216.03010] Current mem. usage after match-tree construction: 4263052 kB.

(Bold is mine). The match tree takes 216sec and after finishing the construction the consumed memory is 4.2 GB. I guess we either find the bug / leak that's evading us, or resort to using the naive successor generation strategy for the paper figures... :-(

gfrances commented 7 years ago

Note, however, that the match-tree is really giving us a performance advantage in difficult problems with 50K+ ground actions, such as Openstacks and Parking, where comparatively it often yelds 100-500% speedup wrt the naive iteration strategy, although the memory overhead is so large that the planner often memories-out much quicker.

gfrances commented 7 years ago

Ok, this was finally tackled in #7ea1b3b3ca28b22e5a81dcae3d2d8aab190f2d2c. Apparently there was no memory leak whatsoever, but a large data structure (which was designed for FSTRIPS encodings and is way too large in some propositional encodings) was being computed innecessarily. This has now been solved, and the mem. footprint greatly reduced.

That said, a match-tree able to deal with multivalued variables would be a nice addition, in that applicable action retrieval could be much more compact. I've opened issue #66 to that effect.