[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting
Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
Thu, 05 May 2022 11:04:17 -0400
Mathieu Desnoyers <firstname.lastname@example.org> writes:
> 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`
> for i in "$@" ; do <--- inner loop
> fork+exec sed
> fork+exec sort
> fork+exec head -n 1
> fork+exec grep
> list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
> So all commands executed under version_test_gt() are executed
> O(n^2) times where n is the number of kernel images in /boot.
> 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.
> 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
> Signed-off-by: Mathieu Desnoyers <email@example.com>
Reviewed-by: Robbie Harwood <firstname.lastname@example.org>
Description: PGP signature