Bug 8347

Summary: Review performance of algorithms using pkg_vec (old issue #120)
Product: [Yocto Project Subprojects] opkg Reporter: Alejandro del Castillo <alejandro.delcastillo>
Component: opkgAssignee: Alex Stewart <alex.stewart>
Status: RESOLVED WONTFIX QA Contact:
Severity: enhancement    
Priority: Undecided    
Version: unspecified   
Target Milestone: 1.0   
Hardware: x86   
OS: Multiple   
Whiteboard:
OS type for building Yocto: --- Type of Regression: ---
Verified: Documentation change: No (bug/feature does not impact docs)

Description Alejandro del Castillo 2015-09-20 23:00:20 UTC
From TODO list in opkg source tree:

pkg_hash_fetch_best_installation_candidate() is linear search O(P*PN)
   and is slow (frequently called).
      P provider
      PN pkgs in a provider
   It can be O(P) if a hash table is used.

This is part of a bigger class of questions about performance. At some point we need to review the algorithms which use a pkg_vec and see if we can improve them without greatly increasing the memory usage.

This is a long-term consideration and not something we need to do immediately.

Originally reported by paul.betafive, Feb 1, 2014
-----------------------------------------------------------------------------
Comment 1 Alex Stewart 2021-07-08 15:20:43 UTC
Closing this bug, because it is an old issue and isn't specific to any particular performance issue or codepath. We have other bugs on the backlog which target performance issues that are actually impacting users.

But this bug's closure shouldn't dissuade anyone from filing a performance bug about a particular workflow or codepath.