Re: [PATCH] seq: speed up the common case by 25x

[Jim Meyering]

Jim Meyering wrote:

> Pádraig Brady wrote:
>> commit 775cc028323de225018b9a43141fe9a93a5b9162
>> Author: Pádraig Brady <address@hidden>
>> Date:   Mon Mar 28 08:41:31 2011 +0100
>>
>>     seq: speed up the common case by 560%
>>
>>     * seq.c (print_range): Print a range of numbers
>>     without using if statements for speed.
>>     (print_long_range): Print a range of numbers
>>     using the unix paradigm of using other utils
>>     that do it better.
>
> Great idea.
>
> This must be an old patch.
> First, it doesn't apply, and second, it has a bug
> that makes it so your cool new code is never run.
>
> Moving the code that sets format_str into the "else" clause
> where it's actually used by print_numbers, I get this:
>
>   $ env time ./seq 10000000 > /dev/null
>   0.50user 0.06system 0:00.20elapsed 273%CPU (0avgtext+0avgdata 
> 4800maxresident)k
>   ...
>
> Compare with the old version's time:
>
>   5.06user 0.00system 0:05.08elapsed 99%CPU (0avgtext+0avgdata 
> 2608maxresident)k
>
> So here I benefit from parallelism, and end up with not just 560% (5.6x)
> but a 25x(!) speed-up (on an i7-970).
>
>> diff --git a/src/seq.c b/src/seq.c
>> index 751d665..643c50c 100644
>> --- a/src/seq.c
>> +++ b/src/seq.c
>> @@ -233,6 +233,36 @@ long_double_format (char const *fmt, struct layout 
>> *layout)
>>        }
>>  }
>>
>
> Oops.
> You need a type on printN:
>
> static int
>
> Your patch was corrupted, somehow.
> I applied the changes manually and compared our diffs:
>
>     -@@ -233,6 +233,36 @@ ...
>     +@@ -233,6 +233,35 @@ ...
>
>     -@@ -437,7 +467,17 @@ ...
>     +@@ -437,7 +466,17 @@ ...
>
>
> Here's the adjusted patch:

Here's one that actually passes the tests ;-)
(the other failed "seq -1" due to blown stack
and ignored a specified --format string)

>From 242689f0442c6df671562425b299337e9a9c7b57 Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Fri, 1 Apr 2011 11:24:57 +0200
Subject: [PATCH] padraig's change

---
 src/seq.c |   50 ++++++++++++++++++++++++++++++++++++++++++++++----
 1 files changed, 46 insertions(+), 4 deletions(-)

diff --git a/src/seq.c b/src/seq.c
index 751d665..212772e 100644
--- a/src/seq.c
+++ b/src/seq.c
@@ -233,6 +233,36 @@ long_double_format (char const *fmt, struct layout *layout)
       }
 }

+static int
+printN (int n)
+{
+  printf ("%d\n", n);
+  return 1;
+}
+
+static int
+print_range (int low, int high)
+{
+  return (((low + 1 == high)
+          && (printN (low)))
+          || (   print_range (low, (low+high)/2)
+              && print_range ((low+high)/2, high)));
+}
+
+static int
+print_long_range (int first, int last)
+{
+  (void) first;
+  int ret;
+  char *cmd;
+  ret = asprintf (&cmd, "yes | head -n%d | cat -n | tr -cd '[0-9\\n]'", last);
+  if (ret != -1)
+    ret = system (cmd);
+  free (cmd);
+  return ret;
+}
+
+
 /* Actually print the sequence of numbers in the specified range, with the
    given or default stepping and format.  */

@@ -434,10 +464,22 @@ format string may not be specified when printing equal 
width strings"));
       usage (EXIT_FAILURE);
     }

-  if (format_str == NULL)
-    format_str = get_default_format (first, step, last);
-
-  print_numbers (format_str, layout, first.value, step.value, last.value);
+  if (first.precision == 0 && step.precision == 0 && last.precision ==0
+      && first.value == 1 && step.value == 1 && !equal_width && !format_str
+      && 1 < last.value
+      && STREQ (separator, "\n"))
+    {
+      if (last.value < 1000)
+        print_range (first.value, last.value + 1);
+      else
+        print_long_range (first.value, last.value);
+    }
+  else
+    {
+      if (format_str == NULL)
+        format_str = get_default_format (first, step, last);
+      print_numbers (format_str, layout, first.value, step.value, last.value);
+    }

   exit (EXIT_SUCCESS);
 }
--
1.7.4.2.662.gcbd0