Насколько быстры строковые операции в Perl? В частности, конкатенация и назначение

Question

Как быстро происходит конкатенация строк в Perl?Это линейно по длине второго операнда?Если да, какие условия должны быть выполнены, чтобы эта операция была линейной?Каковы примеры нелинейного времени конкатенации?

А как насчет назначения строк?Когда и где происходит фактическая копия буфера?

А как насчет других операций, таких как подстрока или простые регулярные выражения?

Answer 1

Это действительно сложный вопрос, и ответ на него зависит от многих факторов (архитектура, базовая ОС, HW, флаги компиляции Perl и т. Д.)

Чтобы понять, вы можете взглянуть на внутренние структуры perl, используемые для представления ваших переменных. Хороший источник - иллюстрированные пергуты .

Если вы имеете в виду конкретную реализацию, попробуйте сравнить ваш код:

use Benchmark qw(:all);

my $a = "Some string";
my @b = map { "Some string to append " x $_ } (1..10);

cmpthese(-1, {
    ( map {+ "concat_$_" => sub { my $c = $a . $b[$_] } } (1..10) )
});

Приведенная выше вещь сравнивает операцию my $c = $a . $b для различной длины второго аргумента. Из результата видно, что для этих диапазонов длины операция выполняется примерно за линейное время.

Answer 2

Я проверял это сам.Конкатенация линейна по длине второго аргумента, но присваивание всегда линейно по длине строки.

Похоже, что Perl не считает ссылки для строк, но связывает буфер с каждой переменной (ссылкой).

Вот некоторые результаты теста:

Конкатенация кажется постоянной, а весь тест - линейным:

 248ms   my $x; $x .= "a" for 1..2_000_000
 501ms   my $x; $x .= "a" for 1..4_000_000
 967ms   my $x; $x .= "a" for 1..8_000_000

$x = $x . $y кажется оптимизированным и использует буфер $xв этом случае:

 295ms   my $x; $x = $x . "a" for 1..2_000_000
 592ms   my $x; $x = $x . "a" for 1..4_000_000
1170ms   my $x; $x = $x . "a" for 1..8_000_000

Предыдущая оптимизация выполняется статически, поэтому конкатенация в следующем тесте является линейной по отношению к полученной длине строки, а весь тест является квадратичным:

 233ms   my $x; ${\$x} = ${\$x} . "a" for 1..40_000
 951ms   my $x; ${\$x} = ${\$x} . "a" for 1..80_000
3811ms   my $x; ${\$x} = ${\$x} . "a" for 1..160_000

Копирование является линейным:

 186ms   my $x; for (1..50_000) { $x .= "a"; my $y = $x }
 764ms   my $x; for (1..100_000) { $x .= "a"; my $y = $x }
3029ms   my $x; for (1..200_000) { $x .= "a"; my $y = $x }

Каждая копия является линейной, подсчет ссылок для строк не используется:

 545ms   my $x; for (1..50_000) { $x .= "a"; my $y = $x; my $y2 = $x; my $y3 = $x }
2264ms   my $x; for (1..100_000) { $x .= "a"; my $y = $x; my $y2 = $x; my $y3 = $x }
8951ms   my $x; for (1..200_000) { $x .= "a"; my $y = $x; my $y2 = $x; my $y3 = $x }