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!