FWIW, push seems to be faster than direct indexing on a pre-grown array, as the following table shows.
The only difference between the windex and windex_2 alternatives in the following table is that the former uses push and the latter uses direct indexing on a pre-grown array. The size of the string is 100_000, containing about 3800 matches. (Full code within the readmore tags.)
Rate wregex windex_2 windex
wregex 212/s -- -24% -32%
windex_2 277/s 31% -- -11%
windex 310/s 47% 12% --
| [reply] [Watch: Dir/Any] [d/l] [select] |
In that case, I'd probably code up an XS module that makes two passes over the target string, allocating the result vector once after the first pass, and filling it in on the second.
| [reply] [Watch: Dir/Any] |
The resize and copies have an amortized constant cost per array element added. Put another way, pushing one element at a time averages out to a O(1) operation. | [reply] [Watch: Dir/Any] |
#! perl -slw
use strict;
use Benchmark::Timer;
my $T= new Benchmark::Timer;
for( 1 .. 1000 ) {
my @small = (1) x 100;
my @large = (1 ) x 130900;
$T->start( "small: add 100 by 1" );
push @small, 1 for 1 .. 100;
$T->stop( "small: add 100 by 1" );
$T->start( "large: add 100 by 1" );
push @large, 1 for 1 .. 100;
$T->stop( "large: add 100 by 1" );
$T->start( "small: add 100 by 100" );
push @small, 1 .. 100;
$T->stop( "small: add 100 by 100" );
$T->start( "large: add 100 by 100" );
push @large, 1 .. 100;
$T->stop( "large: add 100 by 100" );
}
$T->report;
__END__
P:\test>461552,pl
1000 trials of small: add 100 by 1 ( 94.947ms total), 94us/trial
1000 trials of large: add 100 by 1 (112.226ms total), 112us/trial
1000 trials of small: add 100 by 100 ( 16.009ms total), 16us/trial
1000 trials of large: add 100 by 100 ( 15.977ms total), 15us/trial
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.
| [reply] [Watch: Dir/Any] [d/l] |
I fail to see how you think this refutes what I said.
When I say "amortized average O(1)" I wasn't saying anything about the size of the constant. Merely that it is a constant.
Certainly I wouldn't expect entering the push op to be free. Entering a for loop isn't free either. Doing both 100 times is more expensive than doing them once. Reallocation is also not free. Amortized constant is not free.
I don't know whether you're reliably measuring the overhead due to reallocating. I guarantee you that the large array has at most one reallocation. (When you reallocate you reserve a buffer that is 1/5 the length of what you need for extra space. 1/5 of 130900 is large enough that we're NOT doing that twice.) From the figures I suspect that you are, and suspect that if you reversed pushing by 1 and pushing by 100 that you'd see an interesting change. (I can't run this since I don't have Benchmark::Timer, and I'm not going to bother installing on a machine that is being booted from Knoppix.)
Also note that when I say "amortized constant" I mean that if you build a large array by pushing one element at a time, the sum of the costs of reallocating come out to (order of magnitude) a constant times the length of the array. However the distribution of reallocation costs is very uneven, you'll see a pattern where as time goes by the odds of a given push having a reallocation go down, but when it happens it costs a lot more. Therefore a test like yours is the wrong way to test my assertion - you want to compare how long it takes to build up arrays of different lengths and see if the times follow a linear pattern.
| [reply] [Watch: Dir/Any] |