Performance Optimization Enhancement for Verification

[goneall]

One way to speed up the verification algorithm is to cache the results of each element being verified. It will take up more memory, but save having to re-parse and traverse the graph for elements if they are referenced more than once (e.g. within a relationship).

[goneall]

I did a some experimentation and found the issue is really #40 when using tag/value

If I comment out the check for removing in-use SPDX ID's, the time it take to verify keycloak-13.0.1.zip-too-big goes from 1:42 down to less than 6 seconds on my machine - a 16X improvement in performance.

[goneall]

@puerco - Can you point me to one of the output files for Kubernetes referenced in your tweet? - I'll verify it is the same issue.

I suspect the issue is related to the tag/value format - it may not occur in JSON format, but I'm not certain.

[puerco]

Yes glad to! Here is a copy of one of them:
kubernetes-source.spdx.gz

This file is almost the same as the Kubernetes v.1.22.0-beta.2 SBOM we will generate tomorrow.

[puerco]

BTW, I think I found an interesting fact that perhaps will be useful:

When I run the verification with tools-java-1.0.1-jar-with-dependencies.jar it takes 12m12.034s to complete.

On another computer, I had a copy of the deprecated spdx-tools-2.2.5-jar-with-dependencies.jar version. This one runs much much faster. It takes 2m19.739s to process the file.

I hope that helps and let me know if I can help with anything else!

[goneall]

Thanks @puerco - This is almost certainly related to the delete performance issue referenced above. I'll do some analysis and see if I can come up with a fix.

[goneall]

I just finished running some experiments with 3 scenarios:

• Baseline: Current version of the SPDX tools
• No in use: Remove in use check on delete (hack to work around the delete performance problem)
• No in use + no related element: In addition to working around the in use check performance problem, don't verify the related SPDX element (works around the performance issue this issue covers)

Here's the results:

• Baseline: 1,163 seconds
• No in use: 174 seconds
• No use no related element: 162

From the above results, it looks like there is a very significant issue with the deserialization of tag/value due to the delete performance issue.

This problem should not occur if other serialization formats are used (e.g. JSON).

I have a few ideas on how to fix this which I'll research over the next couple of days.

[goneall]

I just created #56 which resolves the delete performance issue.

The kubernetes-source.spdx now validates in 109 seconds, more than a 10X improvement.

[goneall]

Moving this issue to the Spdx Java Library

[puerco]

Thanks a lot @goneall I'll give it a go when you cut a new release!

[goneall]

@puerco I'll be cutting a new release within the next few days - quite a few people have run into this performance issue, so it would be nice to get out a fix especially for the online tools.

[goneall]

Resolved with PR #56

[goneall]

@puerco I just released version 1.0.2 of the SPDX Tools Java which includes a fix for this issue. Let me know if this resolves the performance issue for you. If it does resolve the issue, would you mind updating the twitter message with the improved results?