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
From 2bb3d23c747f144888fcd877bbb7fcba59f7c2cd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?P=C3=A1draig=20Brady?= <pbr...@fb.com> 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) != (x)) #endif +/* 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" @@ -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)); } /* 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 = STREQ (b, "inf"); @@ -498,10 +502,15 @@ seq_fast (char const *a, char const *b) bufp = mempcpy (bufp, p, p_len); /* Append separator then number. */ - while (inf || cmp (p, p_len, q, q_len) < 0) + while (true) { + for (uintmax_t n_incr = step; n_incr; n_incr--) + incr (&p, &p_len); + + if (! inf && 0 < cmp (p, p_len, q, q_len)) + break; + *bufp++ = *separator; - incr (&p, &p_len); /* Double up the buffers when needed for the inf case. */ if (p_len == 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 == 1 or not specified [FIXME: relax this, eventually] - then use the much more efficient integer-only code. */ + - integer increment <= SEQ_FAST_STEP_LIMIT + then use the much more efficient integer-only code, + operating on arbitrarily large numbers. */ + bool fast_step_ok = false; + if (n_args != 3 + || (all_digits_p (argv[optind + 1]) + && xstrtold (argv[optind + 1], NULL, &step.value, cl_strtold) + && 0 < step.value && step.value <= SEQ_FAST_STEP_LIMIT)) + fast_step_ok = true; + if (all_digits_p (argv[optind]) && (n_args == 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) == 1) { char const *s1 = n_args == 1 ? "1" : argv[optind]; char const *s2 = argv[optind + (n_args - 1)]; - if (seq_fast (s1, s2)) + if (seq_fast (s1, s2, step.value)) return EXIT_SUCCESS; /* Upon any failure, let the more general code deal with it. */ @@ -678,9 +695,9 @@ main (int argc, char **argv) } } - if ((isfinite (first.value) && first.precision == 0) - && step.precision == 0 && last.precision == 0 - && 0 <= first.value && step.value == 1 && 0 <= last.value + if (first.precision == 0 && step.precision == 0 && last.precision == 0 + && isfinite (first.value) && 0 <= first.value && 0 <= last.value + && 0 < step.value && step.value <= SEQ_FAST_STEP_LIMIT && !equal_width && !format_str && strlen (separator) == 1) { char *s1; @@ -692,7 +709,7 @@ main (int argc, char **argv) else if (asprintf (&s2, "%0.Lf", last.value) < 0) xalloc_die (); - if (*s1 != '-' && *s2 != '-' && seq_fast (s1, s2)) + if (*s1 != '-' && *s2 != '-' && 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 = ['fast-1', qw(4), {OUT => [qw(1 2 3 4)]}], ['fast-2', qw(1 4), {OUT => [qw(1 2 3 4)]}], ['fast-3', qw(1 1 4), {OUT => [qw(1 2 3 4)]}], + ['fast-4', qw(1 2 4), {OUT => [qw(1 3)]}], + ['fast-5', qw(1 4 4), {OUT => [qw(1)]}], + ['fast-6', qw(1 1e0 4), {OUT => [qw(1 2 3 4)]}], # Ensure an INCREMENT of Zero is rejected. ['inc-zero-1', qw(1 0 10), {EXIT => 1}, {ERR => $err_inc_zero}], -- 2.9.3
