* [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items @ 2022-05-02 14:14 Mathieu Desnoyers 2022-05-03 8:47 ` Paul Menzel 0 siblings, 1 reply; 8+ messages in thread From: Mathieu Desnoyers @ 2022-05-02 14:14 UTC (permalink / raw) To: grub-devel, Daniel Kiper, Vladimir 'phcoder' Serbinenko Cc: 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. Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> --- 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..f1a09f4c9 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_reverse_sort_sort_has_v in + yes) + LC_ALL=C sort -r -V;; + no) + LC_ALL=C sort -r -n;; + *) + if sort -r -V </dev/null > /dev/null 2>&1; then + version_reverse_sort_sort_has_v=yes + LC_ALL=C sort -r -V + else + version_reverse_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..23d4bb741 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/$/ 2/' | sed -e 's/.old 2/ 1/' | version_reverse_sort | sed 's/ 1$/.old/' | sed '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 # If at least one kernel was found, then we need to -- 2.30.2 ^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items 2022-05-02 14:14 [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers @ 2022-05-03 8:47 ` Paul Menzel 2022-05-03 14:42 ` Mathieu Desnoyers 0 siblings, 1 reply; 8+ messages in thread From: Paul Menzel @ 2022-05-03 8:47 UTC (permalink / raw) To: Mathieu Desnoyers Cc: Daniel Kiper, Vladimir 'phcoder' Serbinenko, grub-devel Dear Mathieu, 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)? Kind regards, Paul > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> > --- > 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..f1a09f4c9 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_reverse_sort_sort_has_v in > + yes) > + LC_ALL=C sort -r -V;; > + no) > + LC_ALL=C sort -r -n;; > + *) > + if sort -r -V </dev/null > /dev/null 2>&1; then > + version_reverse_sort_sort_has_v=yes > + LC_ALL=C sort -r -V > + else > + version_reverse_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..23d4bb741 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/$/ 2/' | sed -e 's/.old 2/ 1/' | version_reverse_sort | sed 's/ 1$/.old/' | sed '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 > > # If at least one kernel was found, then we need to ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items 2022-05-03 8:47 ` Paul Menzel @ 2022-05-03 14:42 ` Mathieu Desnoyers 2022-05-03 14:47 ` Paul Menzel 2022-05-03 17:15 ` Mihai Moldovan 0 siblings, 2 replies; 8+ messages in thread From: Mathieu Desnoyers @ 2022-05-03 14:42 UTC (permalink / raw) To: Paul Menzel Cc: Daniel Kiper, Vladimir 'phcoder' Serbinenko, grub-devel ----- On May 3, 2022, at 4:47 AM, Paul Menzel pmenzel@molgen.mpg.de wrote: > Dear Mathieu, > > > 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. ^^^^^^^^^ 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. Thanks, Mathieu > > > Kind regards, > > Paul > > >> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> >> --- >> 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..f1a09f4c9 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_reverse_sort_sort_has_v in >> + yes) >> + LC_ALL=C sort -r -V;; >> + no) >> + LC_ALL=C sort -r -n;; >> + *) >> + if sort -r -V </dev/null > /dev/null 2>&1; then >> + version_reverse_sort_sort_has_v=yes >> + LC_ALL=C sort -r -V >> + else >> + version_reverse_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..23d4bb741 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/$/ 2/' | sed -e >> 's/.old 2/ 1/' | version_reverse_sort | sed 's/ 1$/.old/' | sed '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 >> > > # If at least one kernel was found, then we need to -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items 2022-05-03 14:42 ` Mathieu Desnoyers @ 2022-05-03 14:47 ` Paul Menzel 2022-05-03 17:15 ` Mihai Moldovan 1 sibling, 0 replies; 8+ messages in thread From: Paul Menzel @ 2022-05-03 14:47 UTC (permalink / raw) To: Mathieu Desnoyers Cc: Daniel Kiper, Vladimir 'phcoder' Serbinenko, grub-devel 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items 2022-05-03 14:42 ` Mathieu Desnoyers 2022-05-03 14:47 ` Paul Menzel @ 2022-05-03 17:15 ` Mihai Moldovan 2022-05-04 0:54 ` Oskari Pirhonen 2022-05-19 20:21 ` Mathieu Desnoyers 1 sibling, 2 replies; 8+ messages in thread From: Mihai Moldovan @ 2022-05-03 17:15 UTC (permalink / raw) To: The development of GNU GRUB, Mathieu Desnoyers [-- Attachment #1.1: Type: text/plain, Size: 1374 bytes --] Just a nit, feel free to ignore it... * On 5/3/22 4:42 PM, Mathieu Desnoyers wrote: > 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. This is correct for GNU coreutils's sort, but nothing (I'm mostly thinking of SUS/POSIX here) mandates that the sort utility must either use merge sort or have O(n*log(n)) time complexity. Given that you're using version sort, which is a GNU extension, it probably can't be anything than GNU sort anyway, though, so the point still holds by implicity. However, this also means that you're adding a hidden dependency upon GNU coreutils sort here, which will hit systems traditionally not using the GNU userland by default, most prominently BSDs (which, I might add, seem not to use GRUB by default and generally either discourage it or have thrown it out of their package management systems). Mihai [-- Attachment #2: OpenPGP digital signature --] [-- Type: application/pgp-signature, Size: 840 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items 2022-05-03 17:15 ` Mihai Moldovan @ 2022-05-04 0:54 ` Oskari Pirhonen 2022-05-04 3:54 ` Mihai Moldovan 2022-05-19 20:21 ` Mathieu Desnoyers 1 sibling, 1 reply; 8+ messages in thread From: Oskari Pirhonen @ 2022-05-04 0:54 UTC (permalink / raw) To: grub-devel [-- Attachment #1: Type: text/plain, Size: 2124 bytes --] On Tue, May 03, 2022 at 07:15:47PM +0200, Mihai Moldovan wrote: > Just a nit, feel free to ignore it... > > > * On 5/3/22 4:42 PM, Mathieu Desnoyers wrote: > > 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. > > This is correct for GNU coreutils's sort, but nothing (I'm mostly thinking of > SUS/POSIX here) mandates that the sort utility must either use merge sort or > have O(n*log(n)) time complexity. > > Given that you're using version sort, which is a GNU extension, it probably > can't be anything than GNU sort anyway, though, so the point still holds by > implicity. > > However, this also means that you're adding a hidden dependency upon GNU > coreutils sort here, which will hit systems traditionally not using the GNU > userland by default, most prominently BSDs (which, I might add, seem not to use > GRUB by default and generally either discourage it or have thrown it out of > their package management systems). The existing `version_sort()` function in grub-mkconfig_lib.in uses the same logic for detecting the existence of `sort -V` with a fallback to `sort -n`. I don't think it adds any new hidden dependencies. version_sort () { case $version_sort_sort_has_v in yes) LC_ALL=C sort -V;; no) LC_ALL=C sort -n;; *) if sort -V </dev/null > /dev/null 2>&1; then version_sort_sort_has_v=yes LC_ALL=C sort -V else version_sort_sort_has_v=no LC_ALL=C sort -n fi;; esac } - Oskari [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 228 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items 2022-05-04 0:54 ` Oskari Pirhonen @ 2022-05-04 3:54 ` Mihai Moldovan 0 siblings, 0 replies; 8+ messages in thread From: Mihai Moldovan @ 2022-05-04 3:54 UTC (permalink / raw) To: grub-devel [-- Attachment #1.1: Type: text/plain, Size: 424 bytes --] * On 5/4/22 2:54 AM, Oskari Pirhonen wrote: > The existing `version_sort()` function in grub-mkconfig_lib.in uses the > same logic for detecting the existence of `sort -V` with a fallback to > `sort -n`. I don't think it adds any new hidden dependencies. Right, there are fallbacks in both places for sort versions not supporting the version sort extension, so that's probably fine then. Nevermind. Mihai [-- Attachment #2: OpenPGP digital signature --] [-- Type: application/pgp-signature, Size: 840 bytes --] ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items 2022-05-03 17:15 ` Mihai Moldovan 2022-05-04 0:54 ` Oskari Pirhonen @ 2022-05-19 20:21 ` Mathieu Desnoyers 1 sibling, 0 replies; 8+ messages in thread From: Mathieu Desnoyers @ 2022-05-19 20:21 UTC (permalink / raw) To: The development of GNU GRUB ----- On May 3, 2022, at 1:15 PM, Mihai Moldovan ionic@ionic.de wrote: > Just a nit, feel free to ignore it... > > > * On 5/3/22 4:42 PM, Mathieu Desnoyers wrote: >> 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. > > This is correct for GNU coreutils's sort, but nothing (I'm mostly thinking of > SUS/POSIX here) mandates that the sort utility must either use merge sort or > have O(n*log(n)) time complexity. > > Given that you're using version sort, which is a GNU extension, it probably > can't be anything than GNU sort anyway, though, so the point still holds by > implicity. I'm using the same sort already used in version_sort(). It uses sort -V if available, but there is a fallback to sort if -V is not available. Therefore, nothing implies a version sort, so nothing implies a GNU extension. So your point about other sort not necessarily being O(nlog(n)) merge sort is valid. I will remove this statement from the next patch version commit message. Thanks, Mathieu -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2022-05-19 20:22 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-05-02 14:14 [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers 2022-05-03 8:47 ` Paul Menzel 2022-05-03 14:42 ` Mathieu Desnoyers 2022-05-03 14:47 ` Paul Menzel 2022-05-03 17:15 ` Mihai Moldovan 2022-05-04 0:54 ` Oskari Pirhonen 2022-05-04 3:54 ` Mihai Moldovan 2022-05-19 20:21 ` Mathieu Desnoyers
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.