From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.90_1) id 1nmd2O-0006k2-Bw for mharc-grub-devel@gnu.org; Thu, 05 May 2022 11:05:09 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:44430) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nmd1u-0006iA-06 for grub-devel@gnu.org; Thu, 05 May 2022 11:04:34 -0400 Received: from us-smtp-delivery-74.mimecast.com ([170.10.129.74]:41582) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nmd1q-00059B-NM for grub-devel@gnu.org; Thu, 05 May 2022 11:04:32 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1651763067; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=YAQBLlDaAFJUPS2c61+1BYgY+pPmn2zzhm6fXCalLdI=; b=HXUt0cXFQgMB/LI0Ap+58JV8KJKHxqYJnSkpAw/ciuK3wP/54XjntjOibfqvMCUvh+XqOS DsDirfw8jRE+JN8/pq539Wj85aKyv65UEp+pu/2Fn9KeLUL/DO7SK+EHQ7bkiL85jfQeJr XJTeU4lp1/uGxn76eMIyCpsgad/GHMk= Received: from mail-qk1-f198.google.com (mail-qk1-f198.google.com [209.85.222.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-67-1jwDQggaPPKnO_1TAl9whA-1; Thu, 05 May 2022 11:04:26 -0400 X-MC-Unique: 1jwDQggaPPKnO_1TAl9whA-1 Received: by mail-qk1-f198.google.com with SMTP id u7-20020ae9d807000000b00680a8111ef6so3000369qkf.17 for ; Thu, 05 May 2022 08:04:26 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:in-reply-to:references:date :message-id:mime-version; bh=YAQBLlDaAFJUPS2c61+1BYgY+pPmn2zzhm6fXCalLdI=; b=GF6GHgS/DTcjR+KW6V9yAml3A7LqRccR9ulRIIlrcw2siCUHpk/Fmcs2nDVpBf2fxS D8SyAk1mUEd1/IIOiKDjGMz3eCG2Ys9VudeI3JKaVJ3HKuYOXlfFItXDXjbgRMyvoEbV mV0qUgkfK+spxqwii9eFsA5Pcl6RMGKV110GhO514a1QAMzt3p/WmGSLaiqRFXxXHTg/ syvGEEyDFfO2mErRn7SfiX+FXkgj5d1dujkCgTQa4hj29qXMcRp/ZllZiAR48Y1fODrP V/tTD6UnllMyfxAzvjxKVvXgwJRf5YR0Fc6hQw8+DuM/qfaur0+Tl3vH/ppiPUh4NJ/L EwxA== X-Gm-Message-State: AOAM530IQUA0YNqUnNbu9UBR8wFHrQhXBApC5wgCuIcvyz95BSlI3hdx 2tgRLVOrKR38E4hFPt2xO5Uz5akY+pSbG7oPKw3VirxXWHeWu6qIfoEU5uPXFClfI+R18FWWQA7 QWsWgqtJp8DQ= X-Received: by 2002:a05:622a:1793:b0:2e1:ba41:ed2 with SMTP id s19-20020a05622a179300b002e1ba410ed2mr23793524qtk.238.1651763065578; Thu, 05 May 2022 08:04:25 -0700 (PDT) X-Google-Smtp-Source: ABdhPJxCaeEukyMEJXBzo2aq3joS6unN7Alo00YxKtLFUx4Fj1hqX0SBHAwKBZJ2m53xf5dJFEHHig== X-Received: by 2002:a05:622a:1793:b0:2e1:ba41:ed2 with SMTP id s19-20020a05622a179300b002e1ba410ed2mr23793467qtk.238.1651763065064; Thu, 05 May 2022 08:04:25 -0700 (PDT) Received: from localhost (c-73-227-130-153.hsd1.ma.comcast.net. [73.227.130.153]) by smtp.gmail.com with ESMTPSA id bm27-20020a05620a199b00b0069fc13ce253sm917478qkb.132.2022.05.05.08.04.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 05 May 2022 08:04:23 -0700 (PDT) From: Robbie Harwood To: Mathieu Desnoyers , Daniel Kiper , Vladimir phcoder Serbinenko , grub-devel , Paul Menzel Cc: Mathieu Desnoyers Subject: Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items In-Reply-To: <20220505142456.58107-1-mathieu.desnoyers@efficios.com> References: <20220505142456.58107-1-mathieu.desnoyers@efficios.com> Date: Thu, 05 May 2022 11:04:17 -0400 Message-ID: MIME-Version: 1.0 Content-Type: multipart/signed; boundary="=-=-="; micalg=pgp-sha512; protocol="application/pgp-signature" Received-SPF: pass client-ip=170.10.129.74; envelope-from=rharwood@redhat.com; helo=us-smtp-delivery-74.mimecast.com X-Spam_score_int: -28 X-Spam_score: -2.9 X-Spam_bar: -- X-Spam_report: (-2.9 / 5.0 requ) BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.082, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: grub-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: The development of GNU GRUB List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 05 May 2022 15:04:53 -0000 --=-=-= Content-Type: text/plain Mathieu Desnoyers 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` > 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 Reviewed-by: Robbie Harwood Be well, --Robbie --=-=-= Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQJIBAEBCgAyFiEEA5qc6hnelQjDaHWqJTL5F2qVpEIFAmJz53EUHHJoYXJ3b29k QHJlZGhhdC5jb20ACgkQJTL5F2qVpEI07hAAvATS6JnSOFWeL4tseuy24ClAITeX AWvpQiYetOXoaRz2XYEektyTzghHmz2Ew2gau/VhiL5qUvhzGGn3zJJoGhgbDF0y iMkeQiEqmY4epPj0mujgzA7K4JeQeT9IGZTb4wXK664GlrMS02CoTD/S2KVj7mcT Rf7OiBqexqJCNi1HOzJwM4vh86okW41sGc8+gucfFKrad7L/72LeKStdjzmXwSfO qggIM1bTunjUZHiA/eXjJew0puW9Pm0bidxh5aYGLMmGf+Fgd+nVH1Y+e9JER89a LmxdgHn9l/LA2FqkDaBnbF9TazsTBFnB6zosuHwHcypVxJ0hMpPGS9GtAHN9LF2Q 00JYiRt5s7bcsHhBAjBcYnubIF/11lcKRxkpl7e7gnenAqrQCe/jLEE7cI3g5Xcb CKErqqt5En4wnlSNlGEwEaV9SeUzIMOQoanMPE1VICZ2N2n66az7DJ2FQwcZwESL wp7P+HyVbcaxxWnsI/736SoI/v8KxuV1XMNVbKo4e1CfKyQBbxhbOeS+w07WFfk4 fRcMKie2grFdgK6m/lIr4WGywXTT3mbgckKH63B+fF81dC8nboYr8c0kRlRp9HpV YN6QfSG0c5BZ7ZluUJsB3Olneo/Hls76w2MyQOuZ5Dc4xa8q4cAdbJRLf4/cDeW4 OX2gtf1JxkId7Kg= =GQfv -----END PGP SIGNATURE----- --=-=-=--