Created attachment 4578 [details]
Debug output

Hi,

we have around 13.000 packages on the feed. Installation of one package takes 26 seconds on a not very slow ARM CPU (with debug output).
On a feed with around 6000 packages it's much faster. Only 3 seconds (with debug output). Without debug it's around 22 seconds vs. 1 second.

Debug output is attached. The problem is in opkg_recurse_pkgs_in_order. I have looked into the code. I guess(not tested) that the check whether the package was already visited is quite slow. It iterates over the visited vector and does a strcmp. It will become slower and slower with increasing number of packages.

What about assigning a unique number to every package. Then you can use a simple array "char visited[unique number]" to store a true/false (visited/not visited) for every package and a lookup should be much faster and you also don't need a strcmp.

What I also don't understand is why you build the dependencies for all packages in the feed? opkg_configure_packages calls opkg_recurse_pkgs_in_order for every package. Right? Why don't you do it only for the packages that should be installed? That should be sufficient and much faster as in normal cases only a few packages are installed at once.