Stack overflow in Models.matchModels

[ArkanEmre]

Hi everyone,

I wanted to compare two RDF Datasets with Models.isomorphic function. They both have around 50000 Statements, unfortunately this triggers a stack overflow due to a recursive call in the Models class. Here is the link to the line where the recursive call happens.

It is also commented by the developer that it should be fixed. Do you know of any solutions?

Best regards,
Emre

[abrokenjester]

I haven't looked in detail but generally speaking the solution would be to rewrite as an iterative algorithm. A common way to do that is to introduce an explicit stack (instead of relying on the programming stack).

[hmottestad]

I've had huge issues with Models.isomorphic in RDF4J. In my previous project we used RDF4J everywhere except for isomorphic. Here we converted our model to a JSON-LD string and parsed it into Jena and ran isomorphic there. This was considerably faster.

[abrokenjester]

I don't think a performance refactor would be particularly difficult. I'll try and take a stab at it over the weekend.

[abrokenjester]

I'll try and take a stab at it over the weekend.

Ok so that didn't happen. If anyone else wants to have a go be my guest :)

[hmottestad]

I've created some benchmarks for us for reference: #1476

All based on files I made or found in other places. The spin-full-forwardchained.ttl file actually triggers the stack overflow, so that's good.

[hmottestad]

I found another case of stack overflow. A lot of properties seems to be the trigger. So now we have two stack overflow cases and a bunch of other benchmarks. Here are the results on my ageing macbook pro.

# Run complete. Total time: 00:05:02

Benchmark                                 Mode  Cnt    Score    Error  Units
IsomorphicBenchmark.blankNodes            avgt   10    0.614 ±  0.007  ms/op
IsomorphicBenchmark.bsbm                  avgt   10  810.974 ± 60.225  ms/op
IsomorphicBenchmark.empty                 avgt   10    0.132 ±  0.002  ms/op
IsomorphicBenchmark.internallyIsomorphic  avgt   10   43.071 ±  0.833  ms/op
IsomorphicBenchmark.list                  avgt   10    8.167 ±  0.096  ms/op
IsomorphicBenchmark.longChain             avgt   10    3.097 ±  0.066  ms/op
IsomorphicBenchmark.manyProperties2       avgt   10  248.785 ± 59.606  ms/op
IsomorphicBenchmark.shacl                 avgt   10    7.022 ±  0.141  ms/op
IsomorphicBenchmark.sparqlTestCase        avgt   10    0.915 ±  0.026  ms/op

[hmottestad]

@ArkanEmre this is now fixed and will be released as part of either the next minor or major release (whichever comes first). You can likely try it tomorrow by using 3.0-SNAPSHOT as your version.

[ArkanEmre]

@hmottestad Thank you!