Почему делает tr/\n Perl//, становятся медленнее и медленнее, когда длины строки увеличиваются?
В perlfaq5 существует ответ для того, Как проводят меня подсчет количество строк в файле?. Текущий ответ предлагает a sysread и a tr/\n//. Я хотел попробовать несколько других вещей видеть сколько быстрее tr/\n// был бы и также попробовал бы его против файлов с различными средними длинами строки. Я создал сравнительный тест для попытки различных способов сделать это. Я выполняю это на Mac OS X 10.5.8 и Perl 5.10.1 на MacBook Air:
- Выход из оболочки к
wc(самый быстрый за исключением коротких строк) tr/\n//(затем самый быстрый, за исключением долгих средних длин строки)s/\n//g(обычно быстрый)while( <$fh> ) { $count++ }(почти всегда медленное вводит по абсолютному адресу, кроме тех случаев, когдаtr///срывает),1 while( <$fh> ); $.(очень быстро)
Давайте проигнорируем это wc, который даже со всем материалом IPC действительно поворачивается в некоторых привлекательных числах.
На первом румянце это похоже tr/\n// очень хорошо, когда длины строки малы (скажите, 100 символов), но ее производительность понижается, когда они становятся крупными (1 000 символов в строке). Чем дольше строки становятся, тем хуже tr/\n// делает. Есть ли что-то не так с моим сравнительным тестом или там что-то еще продолжающееся во внутренностях, который делает tr/// ухудшиться? Почему не делает s/// ухудшиться так же?
Во-первых, результаты.:
Rate very_long_lines-tr very_long_lines-$count very_long_lines-$. very_long_lines-s very_long_lines-wc
very_long_lines-tr 1.60/s -- -10% -12% -39% -72%
very_long_lines-$count 1.78/s 11% -- -2% -32% -69%
very_long_lines-$. 1.82/s 13% 2% -- -31% -68%
very_long_lines-s 2.64/s 64% 48% 45% -- -54%
very_long_lines-wc 5.67/s 253% 218% 212% 115% --
Rate long_lines-tr long_lines-$count long_lines-$. long_lines-s long_lines-wc
long_lines-tr 9.56/s -- -5% -7% -30% -63%
long_lines-$count 10.0/s 5% -- -2% -27% -61%
long_lines-$. 10.2/s 7% 2% -- -25% -60%
long_lines-s 13.6/s 43% 36% 33% -- -47%
long_lines-wc 25.6/s 168% 156% 150% 88% --
Rate short_lines-$count short_lines-s short_lines-$. short_lines-wc short_lines-tr
short_lines-$count 60.2/s -- -7% -11% -34% -42%
short_lines-s 64.5/s 7% -- -5% -30% -38%
short_lines-$. 67.6/s 12% 5% -- -26% -35%
short_lines-wc 91.7/s 52% 42% 36% -- -12%
short_lines-tr 104/s 73% 61% 54% 14% --
Rate varied_lines-$count varied_lines-s varied_lines-$. varied_lines-tr varied_lines-wc
varied_lines-$count 48.8/s -- -6% -8% -29% -36%
varied_lines-s 51.8/s 6% -- -2% -24% -32%
varied_lines-$. 52.9/s 8% 2% -- -23% -30%
varied_lines-tr 68.5/s 40% 32% 29% -- -10%
varied_lines-wc 75.8/s 55% 46% 43% 11% --
Вот сравнительный тест. Я действительно имею контроль там, но это настолько быстро, я просто не беспокоюсь им. В первый раз, когда Вы выполняете его, сравнительный тест создает тестовые файлы и печатает некоторую статистику об их длинах строки:
use Benchmark qw(cmpthese);
use Statistics::Descriptive;
my @files = create_files();
open my( $outfh ), '>', 'bench-out';
foreach my $file ( @files )
{
cmpthese(
100, {
# "$file-io-control" => sub {
# open my( $fh ), '<', $file;
# print "Control found 99999 lines\n";
# },
"$file-\$count" => sub {
open my( $fh ), '<', $file;
my $count = 0;
while(<$fh>) { $count++ }
print $outfh "\$count found $count lines\n";
},
"$file-\$." => sub {
open my( $fh ), '<', $file;
1 while(<$fh>);
print $outfh "\$. found $. lines\n";
},
"$file-tr" => sub {
open my( $fh ), '<', $file;
my $lines = 0;
my $buffer;
while (sysread $fh, $buffer, 4096) {
$lines += ($buffer =~ tr/\n//);
}
print $outfh "tr found $lines lines \n";
},
"$file-s" => sub {
open my( $fh ), '<', $file;
my $lines = 0;
my $buffer;
while (sysread $fh, $buffer, 4096) {
$lines += ($buffer =~ s/\n//g);
}
print $outfh "s found $lines line\n";
},
"$file-wc" => sub {
my $lines = `wc -l $file`;
chomp( $lines );
print $outfh "wc found $lines line\n";
},
}
);
}
sub create_files
{
my @names;
my @files = (
[ qw( very_long_lines 10000 4000 5000 ) ],
[ qw( long_lines 10000 700 800 ) ],
[ qw( short_lines 10000 60 80 ) ],
[ qw( varied_lines 10000 10 200 ) ],
);
foreach my $tuple ( @files )
{
push @names, $tuple->[0];
next if -e $tuple->[0];
my $stats = create_file( @$tuple );
printf "%10s: %5.2f %5.f \n", $tuple->[0], $stats->mean, sqrt( $stats->variance );
}
return @names;
}
sub create_file
{
my( $name, $lines, $min, $max ) = @_;
my $stats = Statistics::Descriptive::Full->new();
open my( $fh ), '>', $name or die "Could not open $name: $!\n";
foreach ( 1 .. $lines )
{
my $line_length = $min + int rand( $max - $min );
$stats->add_data( $line_length );
print $fh 'a' x $line_length, "\n";
}
return $stats;
}
3 ответа
Мне было интересно, не слишком ли много движущихся частей в используемых тестах: мы обрабатываем файлы данных разного размера, используя разную длину строки и пытаясь измерить скорость tr относительно его конкурентов - с базовым (но непроверенным) предположением, что tr - это метод, производительность которого зависит от длины строки.
Кроме того, как указал Брайан в нескольких комментариях, мы загружаем tr буферы данных, которые всегда имеют одинаковый размер (4096 байт). Если какой-либо из методов должен быть нечувствительным к размеру строки, он должен быть tr .
И тут меня осенило: что, если тр были стабильная точка отсчета и другие методы были те, варьируя размер строки? Когда вы смотрите в окно своего космического корабля, это вы или эта клингонская хищная птица движется?
Итак, я разработал тест, который поддерживал размер файлов данных постоянным: длина строки варьируется, но общее количество байтов остается такой же. Как показывают результаты:
tr- наименее чувствительный подход. к изменению длины строки. поскольку общее количество обработанных байтов N равно постоянная для всех трех длин линий проверено (короткое, среднее, длинное), это означает, чтоtrдостаточно эффективен при редактирование данной строки. Даже хотя файл данных короткой строки требует гораздо больше правок,trподход способен обрабатывать данные файл почти так же быстро, как он обрабатывает файл с длинными строками.- Методы, которые полагаются на
<>скорость вверх по мере того, как линии становятся длиннее, хотя и с уменьшающейся скоростью. Эта имеет смысл: поскольку каждый вызов<>требует некоторой работы, это должно быть медленнее обрабатывать данное N байтов используя более короткие строки (по крайней мере, более испытанный диапазон). - Подход
s ///также чувствителен к длине строки. Подобноtr, это подход работает путем редактирования строки это дано. Опять же, более короткая линия длина означает больше правок. По-видимому, способностьs ///делать такие правки намного менее эффективны, чем результатtr.
Вот результаты на Solaris с Perl 5.8.8:
# ln = $. <>, then check $.
# nn = $n <>, counting lines
# tr = tr/// using sysread
# ss = s/// using sysread
# S = short lines (50)
# M = medium lines (500)
# L = long lines (5000)
Rate nn-S
nn-S 1.66/s --
ln-S 1.81/s 9%
ss-S 2.45/s 48%
nn-M 4.02/s 142%
ln-M 4.07/s 145%
ln-L 4.65/s 180%
nn-L 4.65/s 180%
ss-M 5.85/s 252%
ss-L 7.04/s 324%
tr-S 7.30/s 339% # tr
tr-L 7.63/s 360% # tr
tr-M 7.69/s 363% # tr
Результаты на Perl 5.10.0 Windows ActiveState примерно сопоставимы.
Наконец, код:
use strict;
use warnings;
use Set::CrossProduct;
use Benchmark qw(cmpthese);
# Args: file size (in million bytes)
# N of benchmark iterations
# true/false (whether to regenerate files)
#
# My results were run with 50 10 1
main(@ARGV);
sub main {
my ($file_size, $benchmark_n, $regenerate) = @_;
$file_size *= 1000000;
my @file_names = create_files($file_size, $regenerate);
my %methods = (
ln => \&method_ln, # $.
nn => \&method_nn, # $n
tr => \&method_tr, # tr///
ss => \&method_ss, # s///
);
my $combo_iter = Set::CrossProduct->new([ [keys %methods], \@file_names ]);
open my $log_fh, '>', 'log.txt';
my %benchmark_args = map {
my ($m, $f) = @$_;
"$m-$f" => sub { $methods{$m}->($f, $log_fh) }
} $combo_iter->combinations;
cmpthese($benchmark_n, \%benchmark_args);
close $log_fh;
}
sub create_files {
my ($file_size, $regenerate) = @_;
my %line_lengths = (
S => 50,
M => 500,
L => 5000,
);
for my $f (keys %line_lengths){
next if -f $f and not $regenerate;
create_file($f, $line_lengths{$f}, $file_size);
}
return keys %line_lengths;
}
sub create_file {
my ($file_name, $line_length, $file_size) = @_;
my $n_lines = int($file_size / $line_length);
warn "Generating $file_name with $n_lines lines\n";
my $line = 'a' x ($line_length - 1);
chop $line if $^O eq 'MSWin32';
open(my $fh, '>', $file_name) or die $!;
print $fh $line, "\n" for 1 .. $n_lines;
close $fh;
}
sub method_nn {
my ($data_file, $log_fh) = @_;
open my $data_fh, '<', $data_file;
my $n = 0;
$n ++ while <$data_fh>;
print $log_fh "$data_file \$n $n\n";
close $data_fh;
}
sub method_ln {
my ($data_file, $log_fh) = @_;
open my $data_fh, '<', $data_file;
1 while <$data_fh>;
print $log_fh "$data_file \$. $.\n";
close $data_fh;
}
sub method_tr {
my ($data_file, $log_fh) = @_;
open my $data_fh, '<', $data_file;
my $n = 0;
my $buffer;
while (sysread $data_fh, $buffer, 4096) {
$n += ($buffer =~ tr/\n//);
}
print $log_fh "$data_file tr $n\n";
close $data_fh;
}
sub method_ss {
my ($data_file, $log_fh) = @_;
open my $data_fh, '<', $data_file;
my $n = 0;
my $buffer;
while (sysread $data_fh, $buffer, 4096) {
$n += ($buffer =~ s/\n//g);
}
print $log_fh "$data_file s/ $n\n";
close $data_fh;
}
Обновление в ответ на комментарий Брэда. Я пробовал все три варианта, и они вели себя примерно как s / \ n // g - медленнее для файлов данных с более короткими строками (с дополнительной квалификацией, которая s / (\ n) / $ 1 / был даже медленнее, чем другие). Интересно то, что m / \ n / g было в основном той же скоростью, что и s / \ n // g , предполагая, что медленность подхода регулярного выражения (оба s /// и m // ) не зависят напрямую от редактирования строки.
Я также вижу, что tr/// становится относительно медленнее по мере увеличения длины строки, хотя эффект не так драматичен. Эти результаты взяты из ActivePerl 5.10.1 (32-bit) на Windows 7 x64. Также я получил предупреждения "слишком мало итераций для надежного счета" на 100 и увеличил количество итераций до 500.
VL: 4501.06 288
LO: 749.25 29
SH: 69.38 6
VA: 104.66 55
Rate VL-$count VL-$. VL-tr VL-s VL-wc
VL-$count 2.82/s -- -0% -52% -56% -99%
VL-$. 2.83/s 0% -- -51% -56% -99%
VL-tr 5.83/s 107% 106% -- -10% -99%
VL-s 6.45/s 129% 128% 11% -- -99%
VL-wc 501/s 17655% 17602% 8490% 7656% --
Rate LO-$count LO-$. LO-s LO-tr LO-wc
LO-$count 16.5/s -- -1% -50% -51% -97%
LO-$. 16.8/s 1% -- -50% -51% -97%
LO-s 33.2/s 101% 98% -- -3% -94%
LO-tr 34.1/s 106% 103% 3% -- -94%
LO-wc 583/s 3424% 3374% 1655% 1609% --
Rate SH-$count SH-$. SH-s SH-tr SH-wc
SH-$count 120/s -- -7% -31% -67% -81%
SH-$. 129/s 7% -- -26% -65% -80%
SH-s 174/s 45% 35% -- -52% -73%
SH-tr 364/s 202% 182% 109% -- -43%
SH-wc 642/s 433% 397% 269% 76% --
Rate VA-$count VA-$. VA-s VA-tr VA-wc
VA-$count 92.6/s -- -5% -36% -63% -79%
VA-$. 97.4/s 5% -- -33% -61% -78%
VA-s 146/s 57% 50% -- -42% -67%
VA-tr 252/s 172% 159% 73% -- -43%
VA-wc 439/s 374% 351% 201% 74% --
Edit: Я сделал пересмотренный бенчмарк, чтобы сравнить скорости для разных длин линий. Это наглядно показывает, что tr/// начинается с большим преимуществом для коротких линий, которые быстро исчезают по мере того, как линии становятся длиннее. Что касается -почему, то я могу только предполагать, что tr/// оптимизирован для коротких строк.
Сравнение скорости счета строк http://img69.imageshack.us/img69/6250/linecount.th.png
Длинные линии примерно в 65 раз больше коротких, а ваши цифры показывают, что tr/\n/// работает ровно в 65 раз медленнее. Как и ожидалось.
wc явно лучше масштабируется для длинных линий. На самом деле я не знаю почему, возможно потому, что он настроен только на подсчет новых линий, особенно когда вы используете опцию -l.