GNU bug report logs - #37241
large performance gap when start+inc specified with 'seq'

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 37241 in the body.
You can then email your comments to 37241 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: L A Walsh <coreutils <at> tlinx.org>
To: Coreutils <bug-coreutils <at> gnu.org>
Subject: large performance gap when start+inc specified with 'seq'
Date: Fri, 30 Aug 2019 16:29:52 -0700

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?

Message #8 received at 37241 <at> debbugs.gnu.org (full text, mbox):

From: Pádraig Brady <P <at> draigBrady.com>
To: L A Walsh <coreutils <at> tlinx.org>, 37241 <at> debbugs.gnu.org
Subject: Re: bug#37241: large performance gap when start+inc specified with
 'seq'
Date: Wed, 4 Sep 2019 02:51:16 +0100

[Message part 1 (text/plain, inline)]

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

[seq-fast-step.patch (text/x-patch, attachment)]

Message #11 received at 37241 <at> debbugs.gnu.org (full text, mbox):

From: L A Walsh <coreutils <at> tlinx.org>
To: Pádraig Brady <P <at> draigBrady.com>
Cc: 37241 <at> debbugs.gnu.org
Subject: Re: bug#37241: large performance gap when start+inc specified with
 'seq'
Date: Wed, 04 Sep 2019 13:42:56 -0700

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

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.  
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 
determined to be simple integers in the range 1<=X<=1e8 
with integer start and step sizes and where the limit was
'<=' 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 <REG>' (native inc on a register),
but needing to do an add-immediate 'ADD <REG>,CONS' the algorithms would
be the same.

So, logically, I'd think for all items within the native add/sub 
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 
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: 
"Some version" of the 'factor-parallel.sh' test
in the coreutils 'tests/misc' dir, which I thought might actually
do something like that...
:-)

Message #16 received at 37241-done <at> debbugs.gnu.org (full text, mbox):

From: Pádraig Brady <P <at> draigBrady.com>
To: L A Walsh <coreutils <at> tlinx.org>
Cc: 37241-done <at> debbugs.gnu.org
Subject: Re: bug#37241: large performance gap when start+inc specified with
 'seq'
Date: Thu, 5 Sep 2019 11:40:57 +0100

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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.