Performance problem of PDDL parser

[arbimo]

It seems that the PDDL parser has some important performance problems when parsing non trivial problems. Below is the runtime in seconds to parse some HDDL problems. Runtimes are often above one second and even go up to 23 seconds (!) for instance [23]. This instance in particular has a fairly big (though not completely unusual) initial state expression.

=== [0]  2020-po-Monroe-Partially-Observable === 1.3065104484558105
=== [1]  2020-to-Blocksworld-HPDDL === 0.1640629768371582
=== [2]  2020-to-Transport === 0.143265962600708
=== [3]  2020-to-Robot === 0.1581273078918457
=== [4]  2020-po-Monroe-Fully-Observable === 1.7055234909057617
=== [5]  2020-to-Towers === 0.12245368957519531
=== [6]  2020-to-Blocksworld-GTOHP === 0.20174217224121094
=== [7]  2020-to-Logistics-Learned-ECAI-16 === 0.7226729393005371
=== [8]  2020-po-Satellite === 0.23903155326843262
=== [9]  2020-to-Monroe-Fully-Observable === 2.0467567443847656
=== [10] 2020-to-Childsnack === 0.3639533519744873
=== [11] 2020-to-Depots === 0.27066755294799805
=== [12] 2020-to-AssemblyHierarchical === 0.5382301807403564
=== [13] 2020-to-Minecraft-Regular === 1.166816234588623
=== [14] 2020-to-Entertainment === 1.3003723621368408
=== [15] 2020-to-Multiarm-Blocksworld === 0.23566651344299316
=== [16] 2020-po-PCP === 0.31250834465026855
=== [17] 2020-to-Factories-simple === 0.28209948539733887
=== [18] 2020-to-Hiking === 0.5998499393463135
=== [19] 2020-to-Elevator-Learned-ECAI-16 === 0.4780910015106201
=== [20] 2020-po-Transport === 0.1967909336090088
=== [21] 2020-to-Snake === 0.3077516555786133
=== [22] 2020-to-Woodworking === 2.1901118755340576
=== [23] 2020-to-Minecraft-Player === 23.85342025756836
=== [24] 2020-to-Monroe-Partially-Observable === 3.194375514984131
=== [25] 2020-po-Rover === 0.7088096141815186
=== [26] 2020-to-Rover-GTOHP === 0.865910530090332
=== [27] 2020-to-Satellite-GTOHP === 0.3189351558685303

A (very limited) analysis show that the immense majority of the time is spent in the initial parsing (inside pyparsing itself). Below the cProfile for parsing a single domain, sorted by cumulative time.

ncalls    tottime    percall    cumtime    percall    filename:lineno(function)        
1    0    0    2.465    2.465    {built-in    method    builtins.exec}
1    0    0    2.464    2.464    <string>:1(<module>)        
1    0.006    0.006    2.437    2.437    pddl_reader.py:722(parse_problem)        
3    0    0    2.23    0.743    core.py:1078(parse_string)        
2    0    0    2.23    1.115    core.py:1889(parse_file)        
414154/3    0.804    0    2.208    0.736    core.py:778(_parseNoCache)        
6020/12    0.045    0    2.205    0.184    core.py:4779(parseImpl)        
1359/26    0.002    0    2.176    0.084    core.py:4889(parseImpl)        
5083/651    0.011    0    1.988    0.003    core.py:5200(parseImpl)        
1012/833    0.001    0    1.087    0.001    core.py:4956(parseImpl)        
21448    0.016    0    0.827    0    core.py:4748(parseImpl)        
21448    0.02    0    0.811    0    core.py:888(can_parse_next)        
21448    0.022    0    0.792    0    core.py:880(try_parse)        
46573    0.109    0    0.62    0    core.py:746(_skipIgnorables)        
127851/10    0.195    0    2.208    0.221    core.py:3861(parseImpl)        
94344    0.148    0    0.193    0    results.py:136(__new__)        
51898    0.065    0    0.125    0    core.py:2986(parseImpl)        
810    0.014    0    0.123    0    pddl_reader.py:323(_parse_exp)        
55136    0.064    0    0.101    0    core.py:2347(parseImpl)        
2742    0.019    0    0.08    0    core.py:5417(postParse)        
107182    0.068    0    0.068    0    exceptions.py:24(__init__)        
2134    0.01    0    0.051    0    expression.py:139(create_node)        
21448    0.032    0    0.047    0    core.py:3306(parseImpl)        
502    0.002    0    0.045    0    expression.py:321(FluentExp)        

I did not see an obvious fix for this: the expression parsing is actually the one defined by pyparsing (nestedExpr). I tried the apparently common trick of enablePackrat that actually increase parse time to 2 minutes for problem [23].

To reproduce, you can replace the test_hddl_parsing method by this one. The commented lines would in addition give you a profiling of these.

    def test_hddl_parsing(self):
        """Tests that all HDDL benchmarks are successfully parsed."""
        hddl_dir = os.path.join(FILE_PATH, "hddl")
        subfolders = [f.path for f in os.scandir(hddl_dir) if f.is_dir()]
        for id, domain in enumerate(subfolders[:]):
            import time
            start = time.time()

            domain_filename = os.path.join(domain, "domain.hddl")
            problem_filename = os.path.join(domain, "instance.1.pb.hddl")
            reader = PDDLReader()
            # import cProfile
            # cProfile.run(f'from unified_planning.io import PDDLWriter, PDDLReader\n'
            #              f'PDDLReader().parse_problem("{domain_filename}", "{problem_filename}")')
            problem = reader.parse_problem(domain_filename, problem_filename)
            print(f"=== [{id}] {domain} ===", time.time() - start)
            # print(problem)

            assert isinstance(problem, up.model.htn.HierarchicalProblem)

[mikand]

I played a bit with the PDDLReader and I managed to get the time to ~1.3s on my machine (from ~6s) with the attached patch. I think there is still some opportunity for optimization of the grammar, but for very large files pyparsing performance is not on par with other parsers...

pyparsing_nested_expr.txt

[mikand]

@arbimo Do you think we can close this or the performance is still not good enough?

[arbimo]

After the PR, the runtimes are now mostly acceptable for the problems we have in tests. Those remain small compared to what can be found in many IPC benchmarks (not even speaking about the so called "hard-to-ground" instances).

So I suspect that it will show up again, rather sooner than later if people start exploiting the UP and at that time, it is better if we already have an open issue. We could also close this one and create a more targeted one with some pointers on how to improve the parser.