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

Question

Это проблема36 из проекта Эйлера. Суммируйте все числа ниже миллиона, которые представляют собой палиндроми c в базе 2 и в базе 10.

Я первоначально пытался решить ее в более функциональном стиле.

Это работает всего за до 6 секунд.

[1..1_000_000]
    .grep( * !%% 2 )
    .grep( -> $x { $x == $x.flip } )
    .grep( -> $y { $y.base(2) == $y.base(2).flip } )
    .sum.say

Удивительно, но это заняло 12 секунд, хотя я генерирую только нечетные числа и поэтому пропускаю тест на четность.

(1,3 ... 1_000_000)
    .grep( -> $x { $x == $x.flip } )
    .grep( -> $y { $y.base(2) == $y.base(2).flip } )
    .sum.say

Это выполняется примерно за 3 секунды .

my @pals;
for (1,3 ... 1_000_000) -> $x {
    next unless $x == $x.flip;
    next unless $x.base(2) == $x.base(2).flip;
    @pals.push($x);
}

say [+] @pals;

Я также отметил, что существует значительная разница между использованием

for (1,3 ... 1_000_000) -> $x { ...

и

for [1,3 ... 1_000_000] -> $x { ...

Кто-нибудь знает, почему потоковые версии намного медленнее чем итеративный? И почему эти два цикла for будут такими разными по производительности?

Answer 1

Конструкция [...] представляет собой массив composer. Он с энтузиазмом выполняет итерацию найденного в нем и сохраняет каждое значение в массиве. Только тогда мы приступаем к выполнению итерации. Это приводит к гораздо большему выделению памяти и менее благоприятно для кэша. Напротив, круглые скобки ничего не делают (кроме группировки, но они не добавляют никакой семантики кроме этого). Таким образом:

[1..1_000_000]
    .grep( * !%% 2 )
    .grep( -> $x { $x == $x.flip } )
    .grep( -> $y { $y.base(2) == $y.base(2).flip } )
    .sum.say

выделит и настроит массив из миллиона элементов и выполнит его итерацию, в то время как:

(1..1_000_000)
    .grep( * !%% 2 )
    .grep( -> $x { $x == $x.flip } )
    .grep( -> $y { $y.base(2) == $y.base(2).flip } )
    .sum.say

Работает довольно быстро, потому что это не нужно.

Кроме того, оператор ... в настоящее время намного медленнее, чем оператор ... Это не обречено на вечность, просто до сих пор уделялось гораздо меньше внимания. Поскольку .grep также был прилично хорошо оптимизирован, оказывается, быстрее отфильтровать элементы, созданные диапазоном - пока что, во всяком случае.

Наконец, используя == для сравнения (строка) результаты base и flip не так эффективны, так как он анализирует их обратно в целые числа, когда мы можем использовать eq и сравнивать строки:

(1 .. 1_000_000)
    .grep(* !%% 2)
    .grep( -> $x { $x eq $x.flip } )
    .grep( -> $y { $y.base(2) eq $y.base(2).flip } )
    .sum.say

Answer 2

Если вам нужно что-то более быстрое, вы можете написать собственный генератор последовательности.

gather {
  loop (my int $i = 1; $i < 1_000_000; $i += 2) {
    take $i
  }
}
.grep( -> $x { $x eq $x.flip } )
.grep( -> $y { $y.base(2) eq $y.base(2).flip } )
.sum.say

Это занимает около 4 секунд.

---

Или go еще быстрее , вы можете создать объект Iterator самостоятельно.

class Odd does Iterator {
    has uint $!count = 1;

    method pull-one () {
        if ($!count += 2) < 1_000_000 {
            $!count
        } else {
            IterationEnd
        }
    }
}

Seq.new(Odd.new)
.grep( -> $x { $x == $x.flip } )
.grep( -> $y { $y.base(2) == $y.base(2).flip } )
.sum.say

Это занимает всего около 2 секунд.

---

Конечно, если вы хотите go как можно быстрее, избавьтесь итерации последовательности полностью.

Также используйте нативный int s.

Также кэшируйте строку из 10 строк. (my $s = ~$x)

my int $acc = 0;
loop ( my int $x = 1; $x < 1_000_000; $x += 2) {
  next unless (my $s = ~$x) eq $s.flip;
  next unless $x.base(2) eq $x.base(2).flip;
  $acc += $x
}
say $acc;

Что снижает его до примерно 0.45 секунд.

(Кэширование .base(2), похоже, ничего не делает.)

Это, вероятно, близко к минимуму, не прибегая к непосредственному использованию nqp ops.

---

Я попытался написать собственный битный флиппер int, но он замедлился. 0.5 секунд.
(Я не придумал этот алгоритм, я только адаптировал его к Raku. Я также добавил +> $in.msb, чтобы решить эту проблему.)

Я бы предположил, что spe sh уходит в операции, которые не должны быть там.
Или, может быть, это не JIT очень хорошо.

Это может быть больше производительности для значений, больших 1_000_000.
(.base(2).flip равно O(log n), тогда как O(1).)

sub flip-bits ( int $in --> int ) {
  my int $n =
       ((($in +& (my int $ = 0xaaaaaaaa)) +> 1) +| (($in +& (my int $ = 0x55555555)) +< 1));
  $n = ((($n  +& (my int $ = 0xcccccccc)) +> 2) +| (($n  +& (my int $ = 0x33333333)) +< 2));
  $n = ((($n  +& (my int $ = 0xf0f0f0f0)) +> 4) +| (($n  +& (my int $ = 0x0f0f0f0f)) +< 4));
  $n = ((($n  +& (my int $ = 0xff00ff00)) +> 8) +| (($n  +& (my int $ = 0x00ff00ff)) +< 8));
  ((($n +> 16) +| ($n+< 16)) +> (32 - 1 - $in.msb)) +& (my int $ = 0xffffffff);
}

…

  # next unless (my $s = ~$x) eq $s.flip;
  next unless $x == flip-bits($x);

---

Можно даже попробовать использовать несколько потоков.

Обратите внимание, что эта рабочая нагрузка слишком мала для того, чтобы она была эффективной.
Затраты на использование потоков сводят на нет любую выгоду.

my atomicint $total = 0;

sub process ( int $s, int $e ) {
  # these are so the block lambda works properly
  # (works around what I think is a bug)
  my int $ = $s;
  my int $ = $e;

  start {
    my int $acc = 0;
    loop ( my int $x = $s; $x < $e; $x += 2) {
      next unless (my $s = ~$x) eq $s.flip;
      next unless $x.base(2) eq $x.base(2).flip;
      $acc += $x;
    }
    $total ⚛+= $acc;
  }
}


my int $cores = (Kernel.cpu-cores * 2.2).Int;

my int $per = 1_000_000 div $cores;
++$per if $per * $cores < 1_000_000;

my @promises;

my int $start = 1;
for ^$cores {
  my int $end = $start + $per - 2;
  $end = 1_000_000 if $end > 1_000_000;

  push @promises, process $start, $end;

#say $start, "\t", $end;

  $start = $end + 2;
}

await @promises;
say $total;

, которая выполняется примерно за 0.63 секунд .
(Я запутался со значением 2.2, чтобы найти почти минимальное время на моем компьютере.)