Reimplementing, Benchmarking and Optimising Pyttern in Java for Faster Pattern Matching

Details

Supervisors

Mens, Kim

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en informatique, à finalité spécialisée

Abstract

enPyttern is a source-code pattern-matching tool introduced by Liénard, Mens, and Nijssen. Patterns are written in a syntax similar to the target language extended with wildcards. Users can thus describe the code fragments they look for without learning a separate query language or manipulating syntax trees directly. Given a program, Pyttern reports occurrences of such patterns. The current implementation targets Python and is primarily intended for the large-scale analysis of student submissions. The current Python implementation is slow enough to disrupt the user’s workflow, which limits its use in teaching contexts. This thesis improves Pyttern’s performance on two bottlenecks: parsing and patterns whose search space grows combinatorially. Pyttern is first reimplemented in Java, with the original architecture kept unchanged. The matching algorithm is then modified in three ways: a fix removes a transition that produced duplicate matches, a pruning step eliminates redundant wildcards before automaton construction, and a new mechanism shares paths that converge on the same configuration to avoid duplicate work. The Java port alone reduces parsing time by a factor of 2.5 on individual files and by close to 20 on large batches; an interpreted-only configuration shows that this gain comes mostly from HotSpot’s just-in-time compilation rather than from the language change itself. The three matching optimisations further cut the cost of combinatorial patterns by several orders of magnitude on the most extreme cases, bringing them in line with the rest of the benchmark.