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

[Giulio Eulisse]

Ciao,

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.

Ciao,
Giulio
-------------- 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>