Bug 8347 - Review performance of algorithms using pkg_vec (old issue #120)
Summary: Review performance of algorithms using pkg_vec (old issue #120)
Status: RESOLVED WONTFIX
Alias: None
Product: opkg
Classification: Yocto Project Subprojects
Component: opkg (show other bugs)
Version: unspecified
Hardware: x86 Multiple
: Undecided enhancement
Target Milestone: 1.0
Assignee: Alex Stewart
QA Contact:
URL:
Whiteboard:
Depends on:
Blocks:
 
Reported: 2015-09-20 23:00 UTC by Alejandro del Castillo
Modified: 2021-07-08 15:20 UTC (History)
0 users

See Also:
OS type for building Yocto: ---
Type of Regression: ---
Verified:
Documentation change: No (bug/feature does not impact docs)


Attachments

Note You need to log in before you can comment on or make changes to this bug.
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.