Sorting perception graphs and patterns for matching speed take about ~5% of processing time

[gabbard]

When matching patterns, we first sort the perception and pattern graphs so nodes appear in a controlled order which is tuned to optimize matching speed. Profiling indicates this consumes ~5% of total runtime for our verb subset learner tests (one of our most time-consuming test suites).

Here is the relevant code::

# Controlling the iteration order of the graphs
        # controls the order in which nodes are matched.
        # This has a significant, benchmark-confirmed impact on performance.
        sorted_graph_to_match_against = digraph_with_nodes_sorted_by(
            graph_to_match_against._graph,  # pylint: disable=W0212
            _graph_node_order
            if not self.matching_pattern_against_pattern
            else _pattern_matching_node_order,
        )
        sorted_pattern = digraph_with_nodes_sorted_by(
            pattern._graph, _pattern_matching_node_order  # pylint: disable=W0212
        )

Fixing this for patterns is fairly easy: we should sort patterns on creation, via a converter in the constructor. Since the same patterns are matched over and over and over, this is a win.

It's less obvious to me that enforcing sorting on create for PerceptionGraphs will be a net win, but it's worth experimenting with. Part of the problem is that it conflicts somewhat with out goal of minimizing copies. A possible option is:

• add a field is_sorted to PerceptionGraph
• sort PerceptionGraphs for final versions of scenes (after all translation is done)
• making our request to sort a perception graph only trigger if it isn't already sorted, or maybe having it through an exception if it isn't sorted?

[spigo900]

@gabbard I think it would make sense to implement this for patterns first and re-profile before implementing it for perception graphs. Is that right?

[lichtefeld]

This may be useful for considerations in #1030’s patterns creation.