[Rpm-maint] [PATCH] Performance improvement of rpmfcSaveArgs

Giulio Eulisse Giulio.Eulisse at cern.ch
Thu Jan 13 13:51:03 UTC 2011


the current implementation of rpmfcSaveArgs (now argvAddUniq) is quite suboptimal since it does a sort for each insertion in order to preserve ordering in the argv.

Find in attachment a more efficient implementation which finds the insertion point (using a linear search, could be improved by using a std::lower_bound like search), makes some space and inserts a new entry directly in the correct spot so that the resulting vector is already sorted. 

If my math does not fool me, my implementation is roughly O(N) (due to the linear search) while the current one is O((1+N)*log(N)) (due to the search and the sort).

More pragmatically, in my tests, the (rpm)build time of an extremely large (~ one thousand dynamic libraries and several thousands files) package we have, went from three hours to two.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: rpm-4.8.0-improve-file-deps-speed.patch
Type: application/octet-stream
Size: 2435 bytes
Desc: not available
URL: <http://lists.rpm.org/pipermail/rpm-maint/attachments/20110113/5477fd16/attachment.obj>

More information about the Rpm-maint mailing list