Bug 15006 - Improve performance of the pkg_hash_fetch_best_installation_candidate function.
Summary: Improve performance of the pkg_hash_fetch_best_installation_candidate function.
Status: ACCEPTED
Alias: None
Product: opkg
Classification: Yocto Project Subprojects
Component: opkg (show other bugs)
Version: 0.6.1
Hardware: x86 Multiple
: Undecided enhancement
Target Milestone: next-patch
Assignee: Alex Stewart
QA Contact:
URL:
Whiteboard:
Depends on:
Blocks:
 
Reported: 2023-01-13 08:04 UTC by Alex Stewart
Modified: 2023-01-13 08:04 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
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Alex Stewart 2023-01-13 08:04:11 UTC 
This enhancement request was moved from the project's `:TODO` file, and was originally authored by Graham Gower.

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.

https://git.yoctoproject.org/opkg/tree/libopkg/pkg_hash.c?id=cee294e72d257417b5e55ef7a76a0fd15313e46b#n335