|
From: | Paul Menzel |
Subject: | Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items |
Date: | Tue, 3 May 2022 16:47:17 +0200 |
User-agent: | Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.8.1 |
Dear Mathieu, Am 03.05.22 um 16:42 schrieb Mathieu Desnoyers:
----- On May 3, 2022, at 4:47 AM, Paul Menzel pmenzel@molgen.mpg.de wrote:
Am 02.05.22 um 16:14 schrieb Mathieu Desnoyers:The current implementation of the 10_linux script implements its menu items sorting in bash with a quadratic algorithm, calling "sed", "sort", head, and grep to compare versions between individual lines, which is annoyingly slow for kernel developers who can easily end up with 50-100 kernels in /boot. As an example, on a Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, running: /usr/sbin/grub-mkconfig > /dev/null With 44 kernels in /boot, this command takes 10-15 seconds to complete. After this fix, the same command runs in 5 seconds. With 116 kernels in /boot, this command takes 40 seconds to complete. After this fix, the same command runs in 8 seconds. For reference, the quadratic algorithm here is: while [ "x$list" != "x" ] ; do <--- outer loop linux=`version_find_latest $list` version_find_latest() for i in "$@" ; do <--- inner loop version_test_gt() fork+exec sed version_test_numeric() version_sort fork+exec sort fork+exec head -n 1 fork+exec grep list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '` tr fgrep tr So all commands executed under version_test_gt() are executed O(n^2) times where n is the number of kernel images in /boot. I notice that the same quadratic sorting is done for other supported OSes, so I suspect similar gains can be obtained there, but I limit the scope of this patch to Linux because this is the platform on which I can test.Wow, thank you very much. Can you add a paragraph describing the new algorithm, and what runtime it has O(n)?How does the following paragraph sound ? ^^^^^^^^ Here is the improved algorithm proposed: - Prepare a list with all the relevant information for ordering by a single sort(1) execution. This is done by renaming ".old" suffixes by " 1" and by suffixing all other files with " 2", thus making sure the ".old" entries will follow the non-old entries in reverse-sorted-order. - Call version_reverse_sort on the list (sort -r -V): A single execution of sort(1) will reverse-sort the list in O(n*log(n)) with a merge sort. - Replace the " 1" suffixes by ".old", and remove the " 2" suffixes. - Iterate on the reverse-sorted list to output each menu entry item. Therefore, the algorithm proposed has O(n*log(n)) complexity compared to the prior O(n^2) complexity. Moreover, the constant time required for each list entry is much less because sorting is done within a single execution of sort(1) rather than requiring O(n^2) executions of sed(1), sort(1), head(1), and grep(1) in sub-shells. ^^^^^^^^^
Sounds perfect. Thank you.
Please let me know if you want me to re-send an updated patch or if you want to add the text to the current patch's commit message as it is committed.
As the maintainers are pretty busy, I guess it’s better you send a v2. […] Kind regards, Paul
[Prev in Thread] | Current Thread | [Next in Thread] |