[Moscow.pm] Сложить 5000000 чисел

[Ruslan Zakirov]

2010/1/12 Alex Kapranoff <kapranoff на gmail.com>:
> 2010/1/12 Ruslan Zakirov <ruslan.zakirov на gmail.com>
>>
>> 2010/1/12 Alex Kapranoff <kapranoff на gmail.com>:
>> > 2010/1/11 Ruslan Zakirov <ruslan.zakirov на gmail.com>:
>> >> Последний вариант. Отдельное префиксное индексирование чуть быстрее.
>> >
>> > В нём ошибка, из-за которой всё работает на целых 25% быстрее, но
>> > неправильно :)
>> >
>> >> Попробовал splice, но он медленнее
>> >>
>> >> undef $/; @file = split ' ', scalar <>;
>> >>
>> >> $res = '';
>> >> for (1 .. shift(@file)) {
>> >>    $rows = $file[$cur++];
>> >>
>> >>    @s = (0) x ($rows + 1);
>> >>    for (0 .. $rows-1) {
>> >>        $i = 0; $y = 0;
>> >>        $cur += $_;
>> >>
>> >>        for ($cur .. $cur+$_) {
>> >>            $x = $y;
>> >>            $y = $s[$i];
>> >>            $s[$i] = $file[$cur] + ($x > $y? $x : $y);
>> >
>> > Вот тут должно было $file[$_]. Использование $cur реально всё
>> > ускоряет. Это означает, что либо у нас оптимизатор умеет вычислять
>> > неизменяющиеся выражения перед циклом, либо срабатывает эффект
>> > процессорного кэша.
>>
>> Бывает. Я думаю, что есть несколько реальных способов улучшить немного
>> perl.
>>
>> 1) По идее use integer; должен ускорять все это дело. Под действием
>> прагмы используются pp_i_add и соответственно другие макросы получения
>> чисел, но как-то разницы в скорости я не заметил, хотя на 5М должно
>> быть. Похоже на баг или какой-то сторонний эфект, например какая-то
>> операция генерит float/double, а потом обратно.
>
> Я тоже игрался с use integer и удивился, что нет прироста. Было бы интересно
> залезть поглубже и разобраться.
>
>> 2) Я не увидел в splice оптимизации под случаи, когда из массива
>> только вырезаются элементы с края. В таких случаях perl может избежать
>> переноса элементов, а только манипулировать окном. Конечно спорный
>> момент, но можно попробовать как-то поиграться.
>
> Причём эти оптимизации есть для pop/shift. Их надо спортировать на splice.
> Жалко, что у moscow.pm нету перлпортера-резидента ;))

В splice это легко сделать, что-то вроде убрать одну или две строчки
под условие.

Возникает вопрос как правильно исправить push, а точнее av_store,
который использует только правые свободные элементы. Я немного полазил
по функциям и я думаю, что правое и левое свободное пространство
используется не совсем экономично с точки зрения памяти.

Просто исправлять splice не имеет смысла, а более подробный анализ
провести сложнее. Нужны интсрументы, которых сейчас нет.

> --
> Moscow.pm mailing list
> moscow-pm на pm.org | http://moscow.pm.org

-- 
Best regards, Ruslan.