From 2bb3d23c747f144888fcd877bbb7fcba59f7c2cd Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?P=C3=A1draig=20Brady?= <address@hidden>
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