On Thu, May 05, 2022 at 10:24:56AM -0400, Mathieu Desnoyers wrote: > 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. > > 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 > test. > > Signed-off-by: Mathieu Desnoyers <mathieu.desnoy...@efficios.com> > --- > Changes since v1: > - Escape the dot from .old in the sed match pattern, thus ensuring it > matches ".old" rather than "[any character]old". > - Use "sed" rather than "sed -e" everywhere for consistency. > - Document the new algorithm in the commit message. > > Changes since v2: > - Rename version_reverse_sort_sort_has_v to version_sort_sort_has_v, > - Combine multiple sed executions into a single sed -e ... -e ... > --- > util/grub-mkconfig_lib.in | 18 ++++++++++++++++++ > util/grub.d/10_linux.in | 12 ++++++++---- > 2 files changed, 26 insertions(+), 4 deletions(-) > > diff --git a/util/grub-mkconfig_lib.in b/util/grub-mkconfig_lib.in > index 301d1ac22..201b8b7c8 100644 > --- a/util/grub-mkconfig_lib.in > +++ b/util/grub-mkconfig_lib.in > @@ -218,6 +218,24 @@ version_sort () > esac > } > > +version_reverse_sort () > +{ > + case $version_sort_sort_has_v in > + yes) > + LC_ALL=C sort -r -V;; > + no) > + LC_ALL=C sort -r -n;; > + *) > + if sort -V </dev/null > /dev/null 2>&1; then > + version_sort_sort_has_v=yes > + LC_ALL=C sort -r -V > + else > + version_sort_sort_has_v=no > + LC_ALL=C sort -r -n > + fi;; > + esac > +} > + > version_test_numeric () > { > version_test_numeric_a="$1" > diff --git a/util/grub.d/10_linux.in b/util/grub.d/10_linux.in > index ca068038e..8178318f5 100644 > --- a/util/grub.d/10_linux.in > +++ b/util/grub.d/10_linux.in > @@ -195,9 +195,15 @@ title_correction_code= > # yet, so it's empty. In a submenu it will be equal to '\t' (one tab). > submenu_indentation="" > > +# Perform a reverse version sort on the entire list. > +# Temporarily replace the '.old' suffix by ' 1' and append ' 2' for all > +# other files to order the '.old' files after their non-old counterpart > +# in reverse-sorted order. > + > +reverse_sorted_list=$(echo $list | tr ' ' '\n' | sed -e 's/\.old$/ 1/' -e '/ > 1$/! s/$/ 2/' | version_reverse_sort | sed -e 's/ 1$/.old/' -e 's/ 2$//') > + > is_top_level=true > -while [ "x$list" != "x" ] ; do > - linux=`version_find_latest $list` > +for linux in $reverse_sorted_list; do > gettext_printf "Found linux image: %s\n" "$linux" >&2 > basename=`basename $linux` > dirname=`dirname $linux` > @@ -293,8 +299,6 @@ while [ "x$list" != "x" ] ; do > linux_entry "${OS}" "${version}" recovery \ > "${GRUB_CMDLINE_LINUX_RECOVERY} ${GRUB_CMDLINE_LINUX}" > fi > - > - list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '` > done
Could you do the same in util/grub.d/20_linux_xen.in? Both should be kept in sync. And you are not first one who updates 10_linux.in only. If you could make a patch which adds something like "Keep logic in sync with..." to the util/grub.d/10_linux.in and util/grub.d/20_linux_xen.in that would be perfect. Did you consider Oskari's comment sent in the other email? Daniel _______________________________________________ Grub-devel mailing list Grub-devel@gnu.org https://lists.gnu.org/mailman/listinfo/grub-devel