[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] seq: speed up the common case by 25x
From: |
Jim Meyering |
Subject: |
Re: [PATCH] seq: speed up the common case by 25x |
Date: |
Fri, 01 Apr 2011 11:29:07 +0200 |
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