Почему Perl tr/\n//становится медленнее и медленнее по мере увеличения длины строк?

В perlfaq5, есть ответ для Как сделать Я подсчитываю количество строк в файле?. Текущий ответ предполагает 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 символов), но ее производительность падает, когда они становятся большими (1000 символов в строке). Чем длиннее линии, тем хуже 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;
    }

Ответы

Ответ 1

Я задавался вопросом, есть ли в тестах, которые мы использовали, слишком много движущихся частей: мы хрустаем файлы данных разных размеров, используя разные длины линий и пытаясь оценить скорость tr относительно своих конкурентов - с базовые (но непроверенные) предположения, что tr - это метод, производительность которого изменяется с длиной строки.

Кроме того, как заметил Брайан в нескольких комментариях, мы загружаем буферы tr данных, которые всегда имеют одинаковый размер (4096 байт). Если какой-либо из методов должен быть нечувствительным к размеру строки, он должен быть tr.

И потом это меня поразило: что, если 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

Результаты на Windows ActiveState Perl 5.10.0 были примерно сопоставимы.

Наконец, код:

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;
}

Обновление в ответ на комментарий Brad. Я пробовал все три варианта, и они вели себя примерно как s/\n//g - медленнее для файлов данных с более короткими линиями (с дополнительной квалификацией, которая s/(\n)/$1/ был еще медленнее, чем другие). Интересная часть заключалась в том, что m/\n/g была в основном той же скоростью, что и s/\n//g, предполагая, что медленность подхода регулярного выражения (как s///, так и m//) не зависит от вопроса редактирования строки.

Ответ 2

Я также вижу, что tr/// становится относительно медленнее по мере увеличения длины строк, хотя эффект не так драматичен. Эти результаты взяты из ActivePerl 5.10.1 (32-разрядная версия) в 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%        --

Изменить: Я сделал пересмотренный тест, чтобы сравнить ставки для разных длин линий. Это ясно показывает, что tr/// начинается с большого преимущества для коротких линий, которые быстро исчезают, когда линии растут дольше. Что касается этого, я могу только предположить, что tr/// оптимизирован для коротких строк.

Сравнение скорости подсчета строк http://img69.imageshack.us/img69/6250/linecount.th.png

Ответ 3

Длинные строки примерно в 65 раз больше коротких строк, а ваши номера указывают, что tr/\n//выполняется ровно в 65 раз медленнее. Это как ожидалось.

wc, очевидно, лучше масштабируется для длинных линий. Я действительно не знаю, почему; возможно, потому, что он настроен только на пересчет строк, особенно если вы используете опцию -l.