Home > Raku > Manual hypering

## Manual hypering

Nemokosch was unhappy with the performance of a literal translation from Python. So he asked for advice in #raku-beginner. (The logger is missing messages. Authorities have been informed.) This lead to many suggestions, none of which helped much. As such, I was forced to play our Get out of Jail Free (card).

``````use v6.*;

sub is-pentagon(\$c is raw) { (1+sqrt(1+24*\$c))%%6 }

sub P(\$n is raw) { \$n*(3*\$n-1) div 2 }
my atomicint \$bail = 0;
(^∞).hyper(:batch(64)).map( -> \b {
last if \$bail;
for (1..^b) -> \s {
my \bp = P(b);
my \sp = P(s);
if is-pentagon(bp + sp) && is-pentagon(bp - sp) {
say [b, s];
\$bail⚛++;
say now - BEGIN now;
last;
}
}
});``````

This is a rather strange use for `.hyper` as we don’t collect the resulting list. Also, `last` doesn’t quite work on a `HyperSeq`. Jnthn is confident this is a fixable problem. Sadly, I don’t have the patience to wait.

``````my \integers = Channel.new;

start for (^∞).batch(46) { try integers.send(\$_); }

my @promises;
for ^(\$*KERNEL.cpu-cores - 1) {
my atomicint \$bail = 0;
with integers {
@promises.push: start {
loop { integers.receive.map( -> \b {
last if \$bail;
for (1..^b) -> \s {
my \integers = Channel.new;

start {
for (^5000).batch(46) { try integers.send(\$_); }
integers.close;
}

my @promises;
for ^(\$*KERNEL.cpu-cores - 1) {
my atomicint \$bail = 0;
with integers {
@promises.push: start {
my \$result = Empty;
loop {
integers.receive.map( -> \b {
for (1..^b) -> \s {
last if \$bail;
my \bp = P(b);
my \sp = P(s);
if is-pentagon(bp + sp) && is-pentagon(bp - sp) {
\$bail⚛++;
\$result = |(b, s);
integers.close;
}
}
});
CATCH { when X::Channel::ReceiveOnClosed { last } }
}

\$result;
};
}
}

say @promises».result;``````

The idea is simple. I pipe the list in chunks into a `Channel` and start a bunch of threads. Those threads look for the needle and signal each other via an `atomicint` that it’s time to go home. By defaulting to `Empty` in the result value of the `start`-block, I eliminate all return values of threads that didn’t find the value of interest.

Let’s generalise this a little.

``````use MONKEY;
augment class HyperSeq {
multi method find(&needle, :\$first!, :\$take-result!) {
my \chan = Channel.new;

my @promises;
for ^(self.configuration.degree - 1) {
my \$p = Promise.new;
start {
my \$result = Empty;
BAIL: loop {
for chan.receive {
\$result = .&needle;
unless \$result =:= Nil {
chan.close;
\$p.keep(\$result);
last BAIL;
}
}

CATCH { when X::Channel::ReceiveOnClosed { say 'bail'; last } }
}

for @promises {
.keep(Empty) unless .status ~~ Kept;
}
};
@promises.push: \$p;
}

await start {
for self.batch(self.configuration.degree) { chan.send(\$_); }
chan.close;
CATCH { when X::Channel::SendOnClosed { } }
}

@promises».result.head;
}
}

sub needle(\b) {
for (1..^b) -> \s {
my \bp = P(b);
my \sp = P(s);
if is-pentagon(bp + sp) && is-pentagon(bp - sp) {
return |(b, s);
}
}
}

say (^∞).hyper(:46batch).find(&needle, :first, :take-result);``````

By using the `Channel` to indicate that one of the threads is done, I don’t need the `atomicint` any more and the `&needle` is using `Nil` for something useful. This is now faster then the original Python implementation — with 16 cores on full steam. And that is very promising. Once we got single thread performance under control, we won’t even see the competition in the rear mirror.

I do have the feeling that our hyper/race-facilities do lack some algorithms. If you know other languages that have them, please plunder and pillage away. YARRRR!

Categories: Raku
1. No comments yet.
1. January 17, 2022 at 13:55