Skip to content

Improve performance of dependency analysis phase #794

Open
@konsoletyper

Description

@konsoletyper

Currently, it's the most memory and time consuming phase of compilation, especially for large code bases. There are some thoughts how this could be improved:

  1. Instead of storing full set of reached typed for each node, a new "overflow" mechanism can be used: when the number of types of a node reaches some limit, "merge" this node with special "all reachable types" node. This also makes unnecessary special kind of "fast dependency analysis": the same effect can be achieved by controlling type number threshold (e.g. by setting it to 1).
  2. Sometimes type propagation should be stopped and graph optimization could be performed: all loops merged into one node, nodes sorted topologically, etc.
  3. Sort nodes topologically so that propagation could be done from the first node to the last one instead of current queue-based approach
  4. Sometimes all nodes of graph should be fully re-created in topological order to achieve better space locality and to reduce CPU cache misses.

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions