From unknown Fri Jun 20 07:21:11 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#37241 <37241@debbugs.gnu.org> To: bug#37241 <37241@debbugs.gnu.org> Subject: Status: large performance gap when start+inc specified with 'seq' Reply-To: bug#37241 <37241@debbugs.gnu.org> Date: Fri, 20 Jun 2025 14:21:11 +0000 retitle 37241 large performance gap when start+inc specified with 'seq' reassign 37241 coreutils submitter 37241 L A Walsh severity 37241 normal thanks From debbugs-submit-bounces@debbugs.gnu.org Fri Aug 30 19:30:07 2019 Received: (at submit) by debbugs.gnu.org; 30 Aug 2019 23:30:07 +0000 Received: from localhost ([127.0.0.1]:54889 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1i3qLG-00036k-Q1 for submit@debbugs.gnu.org; Fri, 30 Aug 2019 19:30:06 -0400 Received: from lists.gnu.org ([209.51.188.17]:53951) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1i3qLE-00036b-94 for submit@debbugs.gnu.org; Fri, 30 Aug 2019 19:30:04 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:43758) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1i3qLC-00010F-9Z for bug-coreutils@gnu.org; Fri, 30 Aug 2019 19:30:03 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1i3qL9-0007Hs-Bq for bug-coreutils@gnu.org; Fri, 30 Aug 2019 19:30:02 -0400 Received: from ishtar.tlinx.org ([173.164.175.65]:54046 helo=Ishtar.sc.tlinx.org) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1i3qL9-00076v-2r for bug-coreutils@gnu.org; Fri, 30 Aug 2019 19:29:59 -0400 Received: from [192.168.3.12] (Athenae [192.168.3.12]) by Ishtar.sc.tlinx.org (8.14.7/8.14.4/SuSE Linux 0.8) with ESMTP id x7UNTqrS078214 for ; Fri, 30 Aug 2019 16:29:55 -0700 Message-ID: <5D69B170.40504@tlinx.org> Date: Fri, 30 Aug 2019 16:29:52 -0700 From: L A Walsh User-Agent: Thunderbird MIME-Version: 1.0 To: Coreutils Subject: large performance gap when start+inc specified with 'seq' Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x (no timestamps) [generic] X-Received-From: 173.164.175.65 X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) Was looking at some large sequences and the time they took and found that while end-point only was fast: declare -x TIMEFORMAT="%2Rsec %2Uusr %2Ssys (%P%% cpu)" > time seq 1e8 >/dev/null 0.75sec 0.74usr 0.01sys (99.77% cpu) Trying just to generate only odd numbers: > time seq 1 2 1e8 >/dev/null 24.70sec 24.64usr 0.01sys (99.82% cpu) took way longer. Shouldn't the 2nd case take about half as long as the first? They are both adding integers though in 2nd case, its skipping the "even"s on output. If it was some floating point calculation needed, I might not have blinked, but both an integer sequence with the 2nd being half as long? Should half the numbers take almost 33x longer? From debbugs-submit-bounces@debbugs.gnu.org Tue Sep 03 21:51:24 2019 Received: (at 37241) by debbugs.gnu.org; 4 Sep 2019 01:51:24 +0000 Received: from localhost ([127.0.0.1]:60721 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1i5KSB-0001At-Qk for submit@debbugs.gnu.org; Tue, 03 Sep 2019 21:51:24 -0400 Received: from mail.magicbluesmoke.com ([82.195.144.49]:50752) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1i5KS6-0001Aa-QH for 37241@debbugs.gnu.org; Tue, 03 Sep 2019 21:51:21 -0400 Received: from localhost.localdomain (86-40-129-28-dynamic.agg2.lod.rsl-rtd.eircom.net [86.40.129.28]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.magicbluesmoke.com (Postfix) with ESMTPSA id 3CFDF9F7A; Wed, 4 Sep 2019 02:51:17 +0100 (IST) Subject: Re: bug#37241: large performance gap when start+inc specified with 'seq' To: L A Walsh , 37241@debbugs.gnu.org References: <5D69B170.40504@tlinx.org> From: =?UTF-8?Q?P=c3=a1draig_Brady?= Message-ID: Date: Wed, 4 Sep 2019 02:51:16 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.8.0 MIME-Version: 1.0 In-Reply-To: <5D69B170.40504@tlinx.org> Content-Type: multipart/mixed; boundary="------------887B73C2A8F22455E74ECF1E" X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 37241 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) This is a multi-part message in MIME format. --------------887B73C2A8F22455E74ECF1E Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit On 31/08/19 00:29, L A Walsh wrote: > Was looking at some large sequences and the time they took > and found that while end-point only was fast: > > declare -x TIMEFORMAT="%2Rsec %2Uusr %2Ssys (%P%% cpu)" > >> time seq 1e8 >/dev/null > 0.75sec 0.74usr 0.01sys (99.77% cpu) > > Trying just to generate only odd numbers: >> time seq 1 2 1e8 >/dev/null > 24.70sec 24.64usr 0.01sys (99.82% cpu) > > took way longer. > > Shouldn't the 2nd case take about half as long as > the first? They are both adding integers though in > 2nd case, its skipping the "even"s on output. > > If it was some floating point calculation needed, I might not > have blinked, but both an integer sequence with the 2nd > being half as long? Should half the numbers take almost 33x > longer? Yes we could be better here. Attached is a fairly simple improvement: $ time seq.new 1 1 1e8 >/dev/null real 0m1.516s $ time seq.new 1 2 1e8 >/dev/null real 0m0.834s $ time seq.orig 1 2 1e8 >/dev/null real 0m40.435s It might be improved further with BCD addition of the step string, but this should be good for now. cheers, Pádraig --------------887B73C2A8F22455E74ECF1E Content-Type: text/x-patch; name="seq-fast-step.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="seq-fast-step.patch" =46rom 2bb3d23c747f144888fcd877bbb7fcba59f7c2cd Mon Sep 17 00:00:00 2001 From: =3D?UTF-8?q?P=3DC3=3DA1draig=3D20Brady?=3D Date: Tue, 3 Sep 2019 10:14:48 +0100 Subject: [PATCH] seq: use faster processing for all integer steps from 1 = to 200 * src/seq.c: (seq_fast): Accept STEP as a parameter and use that to skip the output of generated numbers. (main): Relax to using seq_fast for integer steps between 1 and 200. For larger steps the throughput was faster using the standard incrementing procedure. (cmp): Use the equivalent but faster memcmp for equal len strings. * tests/misc/seq.pl: Update fast path cases. Addresses https://bugs.gnu.org/37241 --- src/seq.c | 41 +++++++++++++++++++++++++++++------------ tests/misc/seq.pl | 3 +++ 2 files changed, 32 insertions(+), 12 deletions(-) diff --git a/src/seq.c b/src/seq.c index 8efe929..1443695 100644 --- a/src/seq.c +++ b/src/seq.c @@ -37,6 +37,10 @@ # define isnan(x) ((x) !=3D (x)) #endif =20 +/* Limit below which seq_fast has more throughput. + Determined with: seq 0 200 inf | pv > /dev/null */ +#define SEQ_FAST_STEP_LIMIT 200 + /* The official name of this program (e.g., no 'g' prefix). */ #define PROGRAM_NAME "seq" =20 @@ -431,7 +435,7 @@ cmp (char const *a, size_t a_len, char const *b, size= _t b_len) return -1; if (b_len < a_len) return 1; - return (strcmp (a, b)); + return (memcmp (a, b, a_len)); } =20 /* Trim leading 0's from S, but if S is all 0's, leave one. @@ -453,7 +457,7 @@ trim_leading_zeros (char const *s) followed by a newline. If B < A, return false and print nothing. Otherwise, return true. */ static bool -seq_fast (char const *a, char const *b) +seq_fast (char const *a, char const *b, uintmax_t step) { bool inf =3D STREQ (b, "inf"); =20 @@ -498,10 +502,15 @@ seq_fast (char const *a, char const *b) bufp =3D mempcpy (bufp, p, p_len); =20 /* Append separator then number. */ - while (inf || cmp (p, p_len, q, q_len) < 0) + while (true) { + for (uintmax_t n_incr =3D step; n_incr; n_incr--) + incr (&p, &p_len); + + if (! inf && 0 < cmp (p, p_len, q, q_len)) + break; + *bufp++ =3D *separator; - incr (&p, &p_len); =20 /* Double up the buffers when needed for the inf case. */ if (p_len =3D=3D inc_size) @@ -641,17 +650,25 @@ main (int argc, char **argv) - no format string, [FIXME: relax this, eventually] - integer start (or no start) - integer end - - increment =3D=3D 1 or not specified [FIXME: relax this, eventuall= y] - then use the much more efficient integer-only code. */ + - integer increment <=3D SEQ_FAST_STEP_LIMIT + then use the much more efficient integer-only code, + operating on arbitrarily large numbers. */ + bool fast_step_ok =3D false; + if (n_args !=3D 3 + || (all_digits_p (argv[optind + 1]) + && xstrtold (argv[optind + 1], NULL, &step.value, cl_strtold) + && 0 < step.value && step.value <=3D SEQ_FAST_STEP_LIMIT)) + fast_step_ok =3D true; + if (all_digits_p (argv[optind]) && (n_args =3D=3D 1 || all_digits_p (argv[optind + 1])) - && (n_args < 3 || (STREQ ("1", argv[optind + 1]) + && (n_args < 3 || (fast_step_ok && all_digits_p (argv[optind + 2]))) && !equal_width && !format_str && strlen (separator) =3D=3D 1) { char const *s1 =3D n_args =3D=3D 1 ? "1" : argv[optind]; char const *s2 =3D argv[optind + (n_args - 1)]; - if (seq_fast (s1, s2)) + if (seq_fast (s1, s2, step.value)) return EXIT_SUCCESS; =20 /* Upon any failure, let the more general code deal with it. */ @@ -678,9 +695,9 @@ main (int argc, char **argv) } } =20 - if ((isfinite (first.value) && first.precision =3D=3D 0) - && step.precision =3D=3D 0 && last.precision =3D=3D 0 - && 0 <=3D first.value && step.value =3D=3D 1 && 0 <=3D last.value + if (first.precision =3D=3D 0 && step.precision =3D=3D 0 && last.precis= ion =3D=3D 0 + && isfinite (first.value) && 0 <=3D first.value && 0 <=3D last.val= ue + && 0 < step.value && step.value <=3D SEQ_FAST_STEP_LIMIT && !equal_width && !format_str && strlen (separator) =3D=3D 1) { char *s1; @@ -692,7 +709,7 @@ main (int argc, char **argv) else if (asprintf (&s2, "%0.Lf", last.value) < 0) xalloc_die (); =20 - if (*s1 !=3D '-' && *s2 !=3D '-' && seq_fast (s1, s2)) + if (*s1 !=3D '-' && *s2 !=3D '-' && seq_fast (s1, s2, step.value))= { IF_LINT (free (s1)); IF_LINT (free (s2)); diff --git a/tests/misc/seq.pl b/tests/misc/seq.pl index f143f6a..b20e43f 100755 --- a/tests/misc/seq.pl +++ b/tests/misc/seq.pl @@ -153,6 +153,9 @@ my @Tests =3D ['fast-1', qw(4), {OUT =3D> [qw(1 2 3 4)]}], ['fast-2', qw(1 4), {OUT =3D> [qw(1 2 3 4)]}], ['fast-3', qw(1 1 4), {OUT =3D> [qw(1 2 3 4)]}], + ['fast-4', qw(1 2 4), {OUT =3D> [qw(1 3)]}], + ['fast-5', qw(1 4 4), {OUT =3D> [qw(1)]}], + ['fast-6', qw(1 1e0 4), {OUT =3D> [qw(1 2 3 4)]}], =20 # Ensure an INCREMENT of Zero is rejected. ['inc-zero-1', qw(1 0 10), {EXIT =3D> 1}, {ERR =3D> $err_inc_zero}], --=20 2.9.3 --------------887B73C2A8F22455E74ECF1E-- From debbugs-submit-bounces@debbugs.gnu.org Wed Sep 04 16:43:03 2019 Received: (at 37241) by debbugs.gnu.org; 4 Sep 2019 20:43:04 +0000 Received: from localhost ([127.0.0.1]:34376 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1i5c7L-0005Mk-0Q for submit@debbugs.gnu.org; Wed, 04 Sep 2019 16:43:03 -0400 Received: from ishtar.tlinx.org ([173.164.175.65]:44758 helo=Ishtar.sc.tlinx.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1i5c7J-0005MI-BR for 37241@debbugs.gnu.org; Wed, 04 Sep 2019 16:43:01 -0400 Received: from [192.168.3.12] (Athenae [192.168.3.12]) by Ishtar.sc.tlinx.org (8.14.7/8.14.4/SuSE Linux 0.8) with ESMTP id x84KguMn007931; Wed, 4 Sep 2019 13:42:59 -0700 Message-ID: <5D7021D0.7040707@tlinx.org> Date: Wed, 04 Sep 2019 13:42:56 -0700 From: L A Walsh User-Agent: Thunderbird MIME-Version: 1.0 To: =?UTF-8?B?UMOhZHJhaWcgQnJhZHk=?= Subject: Re: bug#37241: large performance gap when start+inc specified with 'seq' References: <5D69B170.40504@tlinx.org> In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 37241 Cc: 37241@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) On 2019/09/03 18:51, P=C3=A1draig Brady wrote: > Yes we could be better here. > Attached is a fairly simple improvement: >=20 > $ time seq.new 1 1 1e8 >/dev/null > real 0m1.516s >=20 > $ time seq.new 1 2 1e8 >/dev/null > real 0m0.834s >=20 > $ time seq.orig 1 2 1e8 >/dev/null > real 0m40.435s >=20 > It might be improved further with BCD addition of the step string, > but this should be good for now. --- Thanks, um, do you know what the time would have been on your machine of the original, non-explicit case, i.e.: time seq.new 1e8 >/dev/null I'm wondering if it is about the same, now, as the "1 1 1e8" case, as the original question I had was why the case doing half as many iterations with "1 2 1e8" took almost 33x as long as the "1e8" case (or, perhaps logically equivalent) why "1 1 1e8" wouldn't be the same as "1e8" by itself. I had a bit of a problem following the logic of the original source and as to how it determined to use the simpler algorithm over the more general. Logically, I thought "1 1 1e8" and "1e8" should have take about the same amount of time as the first fit the defaults of the 2nd (1e8) case. =20 If that was the same, then the case of "1 2 1e8", logically, should take half as long (because it was half as many iterations). In cases, where all values could be=20 determined to be simple integers in the range 1<=3DX<=3D1e8=20 with integer start and step sizes and where the limit was '<=3D' than the native int size of the machine could be done with a native, non-complex library call. Other than not being able to use 'INC ' (native inc on a register), but needing to do an add-immediate 'ADD ,CONS' the algorithms would be the same. So, logically, I'd think for all items within the native add/sub=20 word size, the timing would be close to the same, wouldn't it? I'll admit to the work being of questionable use, but not so much less useful than using/needed 'seq' in the first place. I.e. if=20 coreutils was going to include a special binary to produce sequences in the first place, it should probably be very efficient so a user would never feel a need for a specialized version for native integers. The reason for that would be so if the work done in making the sequence was significant enough, it could be split by 'N' physical cores in a machine, one could see about a {90..100}*N Speed-boost over the original. Example of such:=20 "Some version" of the 'factor-parallel.sh' test in the coreutils 'tests/misc' dir, which I thought might actually do something like that... :-) From debbugs-submit-bounces@debbugs.gnu.org Thu Sep 05 06:41:01 2019 Received: (at 37241-done) by debbugs.gnu.org; 5 Sep 2019 10:41:01 +0000 Received: from localhost ([127.0.0.1]:34854 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1i5pCH-0004J8-8g for submit@debbugs.gnu.org; Thu, 05 Sep 2019 06:41:01 -0400 Received: from mail.magicbluesmoke.com ([82.195.144.49]:59708) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1i5pCE-0004Iz-TZ for 37241-done@debbugs.gnu.org; Thu, 05 Sep 2019 06:40:59 -0400 Received: from localhost.localdomain (86-40-129-28-dynamic.agg2.lod.rsl-rtd.eircom.net [86.40.129.28]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.magicbluesmoke.com (Postfix) with ESMTPSA id 7B90FCE56; Thu, 5 Sep 2019 11:40:57 +0100 (IST) Subject: Re: bug#37241: large performance gap when start+inc specified with 'seq' To: L A Walsh References: <5D69B170.40504@tlinx.org> <5D7021D0.7040707@tlinx.org> From: =?UTF-8?Q?P=c3=a1draig_Brady?= Message-ID: <3da217d9-deda-8103-14d0-2256d9c01db2@draigBrady.com> Date: Thu, 5 Sep 2019 11:40:57 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.8.0 MIME-Version: 1.0 In-Reply-To: <5D7021D0.7040707@tlinx.org> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 37241-done Cc: 37241-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) On 04/09/19 21:42, L A Walsh wrote: > > > On 2019/09/03 18:51, Pádraig Brady wrote: >> Yes we could be better here. >> Attached is a fairly simple improvement: >> >> $ time seq.new 1 1 1e8 >/dev/null >> real 0m1.516s >> >> $ time seq.new 1 2 1e8 >/dev/null >> real 0m0.834s >> >> $ time seq.orig 1 2 1e8 >/dev/null >> real 0m40.435s >> >> It might be improved further with BCD addition of the step string, >> but this should be good for now. > --- > Thanks, um, do you know what the time would have been > on your machine of the original, non-explicit case, i.e.: > > time seq.new 1e8 >/dev/null `seq 1e8` is treated the same as `seq 1 1 1e8` on both old and new code. I.E. a step of 1 was treated specially, even if specified. I'll push this later. Marking as done. cheers, Pádraig From unknown Fri Jun 20 07:21:11 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Thu, 03 Oct 2019 11:24:05 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator