Skip to content

[#2143] Strip references pass and collect them in checking

Motivation and Context

Problem

References pass takes too many cycles for the checker contract (around 618.54M cycles). We can collect them during the type checking since the typer looks for original binders with original locations.

Solution

Strip the references pass, introduce a references hashtable in the typer, fill it on each value/type/label/module resolution request.

Flame Graph Comparison

Before Stripping References Pass

Call graph 'ligo info get-scope --format dev --with-types --defs-only src/main.mligo':
--------------------------------------------------------------------------------------
[   11.23G cycles in     1 calls ]     - 72.42% : Scopes.run
[    8.45G cycles in     1 calls ]     |   - 75.21% : Types_pass.Typing_env.type_program
[  618.54M cycles in     1 calls ]     |   -  5.51% : References.declarations (src/main/scopes/references)
[  618.54M cycles in     1 calls ]     |   |   - 100.00% : References.declarations (src/main/scopes/references)
[  310.68M cycles in  8752 calls ]     |   |   |   - 50.23% : References.resolve_module_alias_and_update_mvar_references
[  211.58M cycles in  8752 calls ]     |   |   |   |   - 68.10% : References.resolve_mpath
[   42.88M cycles in  8752 calls ]     |   |   |   |   - 13.80% : References.References.add_module_usages
[   39.07M cycles in  8756 calls ]     |   |   |   |   |   - 91.12% : References.References.map_ref
[  452.92K cycles in  8756 calls ]     |   |   |   |   |   -  1.06% : References.References.add_def_usage
[   41.99M cycles in  8404 calls ]     |   |   |   |   - 13.52% : References.References.add_def_opt_usage
[   38.53M cycles in  8404 calls ]     |   |   |   |   |   - 91.76% : References.References.map_ref
[    8.69M cycles in  8404 calls ]     |   |   |   |   -  2.80% : References.References.add_maccess
[    2.49M cycles in  6214 calls ]     |   |   |   |   |   - 28.68% : References.References.add_tvar
[    2.00M cycles in  2190 calls ]     |   |   |   |   |   - 23.08% : References.References.add_vvar
[  173.44M cycles in 38957 calls ]     |   |   |   - 28.04% : References.References.add_def_opt_usage
[  160.36M cycles in 38350 calls ]     |   |   |   |   - 92.46% : References.References.map_ref
[    2.52M cycles in 38350 calls ]     |   |   |   |   -  1.45% : References.References.add_def_usage
[   46.92M cycles in  7904 calls ]     |   |   |   -  7.59% : References.References.add_ctor
[   21.25M cycles in  5581 calls ]     |   |   |   |   - 45.29% : References.References.map_ref
[   14.31M cycles in 24212 calls ]     |   |   |   -  2.31% : References.References.add_tvar
[   11.06M cycles in 14745 calls ]     |   |   |   -  1.79% : References.References.add_vvar

Note: Nodes accounting for less than 1.00% of their parent have been ignored.

Aggregated table:
----------------
                                                      Name;                          Filename;    Calls;     Time
                                                      ROOT;                   src/landmark.ml;        0;   15.51G
                                                Scopes.run;      src/main/scopes/scopes.ml:70;        1;   11.23G
                        Types_pass.Typing_env.type_program; src/main/scopes/types_pass.ml:774;        1;    8.45G
                                   References.declarations; src/main/scopes/references.ml:732;        1;  618.54M
                                   References.declarations; src/main/scopes/references.ml:721;        1;  618.54M
References.resolve_module_alias_and_update_mvar_references; src/main/scopes/references.ml:308;     8752;  310.68M
                             References.References.map_ref;  src/main/scopes/references.ml:64;    61091;  259.21M
                   References.References.add_def_opt_usage; src/main/scopes/references.ml:115;    47361;  215.43M
                                  References.resolve_mpath; src/main/scopes/references.ml:286;     8752;  211.58M
                                          References.patch; src/main/scopes/references.ml:786;        1;   66.25M
                                          Types_pass.patch; src/main/scopes/types_pass.ml:899;        2;   64.39M
                            References.References.add_ctor; src/main/scopes/references.ml:141;     7904;   46.92M
                   References.References.add_module_usages; src/main/scopes/references.ml:179;     8752;   42.88M
                            References.References.add_tvar; src/main/scopes/references.ml:132;    30426;   16.80M
                            References.References.add_vvar; src/main/scopes/references.ml:124;    16935;   13.07M
                         References.References.add_maccess; src/main/scopes/references.ml:216;     8404;    8.69M
                       References.References.add_def_usage;  src/main/scopes/references.ml:80;    61091;    3.68M
                               References.patch_references; src/main/scopes/references.ml:747;        1;  853.82K

After Stripping References Pass

Call graph 'ligo info get-scope --format dev --with-types --defs-only src/main.mligo':
--------------------------------------------------------------------------------------
[   10.44G cycles in 1 calls ]     - 71.12% : Scopes.run
[    8.36G cycles in 1 calls ]     |   - 80.10% : Types_pass.Typing_env.type_program_with_refs

Note: Nodes accounting for less than 1.00% of their parent have been ignored.

Aggregated table:
----------------
                                        Name;                          Filename;    Calls;     Time
                                        ROOT;                   src/landmark.ml;        0;   14.67G
                                  Scopes.run;      src/main/scopes/scopes.ml:70;        1;   10.44G
Types_pass.Typing_env.type_program_with_refs; src/main/scopes/types_pass.ml:781;        1;    8.36G
                            Types_pass.patch; src/main/scopes/types_pass.ml:910;        2;   79.34M

Related issues

Resolves a part of #2143 .

Checklist for the LIGO Language Server

  • I checked whether I need to update the README.md file for the plugin and did so if necessary:
    • If I implemented a new LSP request, I added it to the list of supported features that may be disabled
    • If I implemented a new LSP method, I added it to the list of supported functionality
  • I checked that my changes work in Emacs, Vim, and Visual Studio Code
  • (Before merging) The commit history is squashed and prettified, and follows the Serokell commit policy, or the MR is set to squash the commits

Description

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

Improved performance for LSP.

The LSP should now take less time between keystrokes.

This is done by stripping the references pass and moving their collection to the type checker.

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).

Merge request reports