templates/linux: Fix quadratic algorithm for sorting menu items

templates/linux: Fix quadratic algorithm for sorting menu items

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). For instance, GNU coreutils' sort 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 with GNU
coreutils' sort 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.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Reviewed-by: Robbie Harwood <rharwood@redhat.com>
Reviewed-by: Daniel Kiper <daniel.kiper@oracle.com>