Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Performance issue with CResourceHandler::makePackageResourceID #326

Open
shahchintan14 opened this issue Nov 4, 2023 · 2 comments
Open

Comments

@shahchintan14
Copy link

The use of std::max_element in CResourceHandler::makePackageResourceID makes the time complexity of this method O(n) which results in making IDs for all resources in a package O(n2) i.e. quadratic.
This is a performance regression over older versions of lib3mf.

If there is a need to get the biggest ID, then it is better to make m_resourceIDs an (ordered) std::map instead of std::unoredered_map.
That way m_resourceIDs.rbegin()->first will give the biggest ID in constant time.

This will reduce the time complexity of CResourceHandler::makePackageResourceID to O(log(n)). There are other std::map look ups in that method, but log(n) is much better. Overall ID creation in entire package will be O(n * log(n)).

There will be a side effect of this change on 2 other methods of CResourceHandler - findResourceIDByUniqueID and removePackageResourceID. Their time complexities will increase from constant to O(log(n)). But overall performance of lib3mf should still be better.

This above fix could be implemented with minimal changes - replace unordered_map with map and max_element with rbegin()->first.
However, if the side effects are not acceptable, then it is best to maintain biggestID separately rather than finding it in linear fashion every time we make a new resource ID.

@martinweismann Any thoughts on this?

@shahchintan14
Copy link
Author

Link to problem code:
https://github.com/3MFConsortium/lib3mf/blame/master/Source/Model/Classes/NMR_PackageResourceID.cpp#:~:text=UniqueIDPackageIdMap%3A%3Aconst_iterator%20biggestId,%7D)%3B

Instead of m_resourceIDs.rbegin() suggested above, we could use m_resourceIDs.crbegin().
m_resourceIDs.rend() can be used to check for empty map.

@shahchintan14
Copy link
Author

shahchintan14 commented Nov 4, 2023

@feliperoos Tagging you as I see your commit in this area of code.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant