Skip to content
Snippets Groups Projects

Perf: Implement a new algorithm for pattern matching compilation to reduce code size

Merged Perf: Implement a new algorithm for pattern matching compilation to reduce code size
melwyn95@compile_pattern_matching_to_decision_tree into dev
Merged Melwyn Saldanha requested to merge melwyn95@compile_pattern_matching_to_decision_tree into dev

Motivation and Context

Closes #1924 (closed)

This MR implements the algorithm from the paper "Compiling Pattern Matching to Good Decision Trees" for pattern matching compiler.

This algorithm performs better than the previous one in the cases when there are nested pattens in a match expression coupled with wildcards in between.

In some cases we can see more than 80% reduction in code size (compared to the old algorthim).

This algorithm simpler to implement and this also removes the pattern simplification pass (pattern_simpl.ml) which was needed by the old algorithm for compressing the matches. The new algorithm generates smaller automaton/match so there is not need for simplification/compression.

Description

examples 0.67.1 (bytes) new algo (bytes) diff (%)
edge_case_T.mligo 3920 468 -88.06
bug_report.mligo 2801 468 -83.29
permit-cameligo 4967 4955 -0.24
dao-cameligo 6481 6479 -0.03
permit-jsligo 5010 5010 0
randomness-cameligo 12542 12542 0
randomness-jsligo 23695 23695 0
fa2 (single-asset) 1550 1550 0
fa2 (multi-asset) 2054 2054 0
fa2 (nft) 2447 2447 0
dao-jsligo 6323 6323 0
predictive-market-jsligo 7769 7769 0
predictive-market-cameligo 7804 7804 0
advisor-jsligo 308 308 0
advisor-cameligo 308 308 0
multisig-jsligo 1302 1302 0
multisig-cameligo 1274 1274 0
shifumi-jsligo 9090 9090 0
shifumi-cameligo 5353 5353 0
NFT-factory-jsligo 3491 3491 0
NFT-factory-cameligo 3497 3497 0
checker-ligo 18467 18467 0
tzsafe 6854 6854 0
batcher 23135 23149 +0.06

Component

  • compiler
  • website
  • webide
  • vscode-plugin
  • debugger

Types of changes

  • Bug fix (non-breaking change which fixes an issue)
  • New feature (non-breaking change which adds functionality)
  • Breaking change (fix or feature that would cause existing functionality to not work as expected)
  • Performance improvement (non-breaking change that improves performance)
  • None (change with no changelog)

Changelog

We implement a new algorithm for the pattern-matching compiler which reduces the size of generated code in some cases.

In some cases we observed upto 80% reduction in generated code.

Example

type t = A | B

type p = (t * t * t * t)

let main (p : p) (_ : int) : operation list * int = 
  [], (match p with
    A,A,A,A -> 1
  | B,B,B,B -> 1
  | _,A,A,A -> 2
  | _,B,B,B -> 2
  | _,_,A,A -> 3
  | _,_,B,B -> 3
  | _,_,_,A -> 4
  | _,_,_,B -> 4)

Before

$ ligo.67 info measure-contract x.mligo 
3920 bytes

After

$ ligo info measure-contract x.mligo 
468 bytes

Checklist:

  • Changes follow the existing coding style (use dune @fmt to check).
  • Tests for the changes have been added (for bug fixes / feature).
  • Documentation has been updated.
  • Changelog description has been added (if appropriate).
  • Start titles under ## Changelog section with #### (if appropriate).
  • There is no image or uploaded file in changelog
  • Examples in changed behaviour have been added to the changelog (for breaking change / feature).
Edited by Melwyn Saldanha

Merge request reports

Loading
Loading

Activity

Filter activity
  • Approvals
  • Assignees & reviewers
  • Comments (from bots)
  • Comments (from users)
  • Commits & branches
  • Edits
  • Labels
  • Lock status
  • Mentions
  • Merge request status
  • Tracking
Please register or sign in to reply