Slow for SBOMs with a large number of files + relationships

This check iterates over the list existing_relationships up to 2 times:

tools-python/src/spdx_tools/spdx/parser/jsonlikedict/relationship_parser.py

Lines 162 to 172 in 8050fd9

    
           def check_if_relationship_exists( 
        
               self, relationship: Relationship, existing_relationships: List[Relationship] 
        
           ) -> bool: 
        
               # assume existing relationships are stripped of comments 
        
               if relationship in existing_relationships: 
        
                   return True 
        
               relationship_inverted: Relationship = self.invert_relationship(relationship) 
        
               if relationship_inverted in existing_relationships: 
        
                   return True 
        
               return False

And it's called for every file:

tools-python/src/spdx_tools/spdx/parser/jsonlikedict/relationship_parser.py

Lines 144 to 157 in 8050fd9

    
           for file_spdx_id in contained_files: 
        
               try: 
        
                   contains_relationship = Relationship( 
        
                       spdx_element_id=package_spdx_id, 
        
                       relationship_type=RelationshipType.CONTAINS, 
        
                       related_spdx_element_id=file_spdx_id, 
        
                   ) 
        
               except ConstructorTypeErrors as err: 
        
                   logger.append(err.get_messages()) 
        
                   continue 
        
               if not self.check_if_relationship_exists( 
        
                   relationship=contains_relationship, existing_relationships=existing_relationships 
        
               ): 
        
                   contains_relationships.append(contains_relationship)

So if F is the number of files and R is the number of relationships, we are doing O(F * R) comparisons of relationships (which seem not cheap individually).

And given that this seems to expect to find a relationship for every file, we know that R is >= F, so this is at least O(F^2).

Looks quadratic to me.

With the caveat that I'm not a python expert, this being a list seems to be the issue:

tools-python/src/spdx_tools/spdx/parser/jsonlikedict/relationship_parser.py

Lines 55 to 57 in 8050fd9

    
           existing_relationships_without_comments: List[Relationship] = self.get_all_relationships_without_comments( 
        
               relationships 
        
           )

Is it possible to turn that into a set so these membership tests are O(1) instead of O(N)?

As an example:

$ curl -L https://packages.wolfi.dev/os/aarch64/renovate-37.151.0-r0.apk | tar -Oxz var/lib/db/sbom/renovate-37.151.0-r0.spdx.json > sbom.spdx.json

$ wc -c sbom.spdx.json
 36350622 sbom.spdx.json

$ cat sbom.spdx.json | jq '.files[]' -c | wc -l
   30193

$ cat sbom.spdx.json | jq '.relationships[]' -c | wc -l
   30193

# 30193 * 30193 = 911617249, which is a pretty big number for python

$ time ntia-checker -v --file sbom.spdx.json

Is this SBOM NTIA minimum element conformant? True

Individual elements                            | Status
-------------------------------------------------------
All component names provided?                  | True
All component versions provided?               | True
All component identifiers provided?            | True
All component suppliers provided?              | True
SBOM author name provided?                     | True
SBOM creation timestamp provided?              | True
Dependency relationships provided?             | True

No components with missing information.

real	8m57.222s
user	8m57.118s
sys	0m0.085s

Navigation Menu

Repository navigation

Slow for SBOMs with a large number of files + relationships #790

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	def check_if_relationship_exists(
	self, relationship: Relationship, existing_relationships: List[Relationship]
	) -> bool:
	# assume existing relationships are stripped of comments
	if relationship in existing_relationships:
	return True
	relationship_inverted: Relationship = self.invert_relationship(relationship)
	if relationship_inverted in existing_relationships:
	return True

	return False

	for file_spdx_id in contained_files:
	try:
	contains_relationship = Relationship(
	spdx_element_id=package_spdx_id,
	relationship_type=RelationshipType.CONTAINS,
	related_spdx_element_id=file_spdx_id,
	)
	except ConstructorTypeErrors as err:
	logger.append(err.get_messages())
	continue
	if not self.check_if_relationship_exists(
	relationship=contains_relationship, existing_relationships=existing_relationships
	):
	contains_relationships.append(contains_relationship)

	existing_relationships_without_comments: List[Relationship] = self.get_all_relationships_without_comments(
	relationships
	)

Slow for SBOMs with a large number of files + relationships #790

Description

Activity

jonjohnsonjr commented on Jan 25, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions