Performance issues with rdflib.compare

[william-vw]

We're having some performance issues with using rdflib.compare. While the test files contains a lot of blank nodes, they are relatively small (50, 75, 100 lines); even then one can see the performance drop with order(s) of magnitude. (Our actual files have close to 6000 lines).

Checkout the repo here with the test code: https://github.com/william-vw/rdflib_compare_test

On my machine, I get the following times:

file: test1.ttl
isomorphic: 0.06714916229248047
canonical: 0.03405618667602539

file: test2.ttl
isomorphic: 3.1934521198272705
canonical: 1.6439540386199951

file: test3.ttl
isomorphic: 17.75542116165161
canonical: 8.694658994674683

I'm basing myself on this example to perform the compare (for testing purposes I'm comparing a graph with itself).

[aucampia]

Hi @william-vw, sadly the code for compare is quite complex, but any improvements will be welcomed and merged.

[ddeschepper]

@william-vw, @aucampia I've done some research into this issue and made PR #3119 that makes a big difference in the canonicalization (and isomorphization) performance. See the PR for results produced by @william-vw's test script.

[ddeschepper]

If you want to use the performance improvements right now (at your own risk!), here's a monkey patch that applies them that works with v7.1.4:

from rdflib.compare import Color, Stats, _TripleCanonicalizer

def patched_traces(self, coloring: list[Color], stats: Stats | None = None, depth: list[int] = [0]) -> list[Color]:
    if stats is not None and "prunings" not in stats:
        stats["prunings"] = 0
    depth[0] += 1
    candidates = self._get_candidates(coloring)
    best_coloring = None
    best_score = None

    for candidate, color in candidates:
        coloring_copy: list[Color] = []
        color_copy = None
        for c in coloring:
            c_copy = c.copy()
            coloring_copy.append(c_copy)
            if c == color:
                color_copy = c_copy
        new_color = self._individuate(color_copy, candidate)
        coloring_copy.append(new_color)
        refined_coloring = self._refine(coloring_copy, [new_color])
        color_score = tuple(c.key() for c in refined_coloring)

        if best_score is None or best_score < color_score:
            best_coloring = refined_coloring
            best_score = color_score

    if best_coloring is None:
        return coloring

    if not self._discrete(best_coloring):
        return self._traces(best_coloring, stats=stats, depth=depth)

    return best_coloring

_TripleCanonicalizer._traces = patched_traces