Functional hypering

In my last post I used a one-shot-operator to improve neatness. Sadly, by defining custom operators we also improve Rakudo’s slowness. After staring at the code form quite some time, I realised that hyper- and meta-operators are code generators. They produce a new operator in-place, which is then used with two operands. In functional programming we do the same thing by returning a sub from a sub.

multi sub hyperize(&code, '«') {
    sub (@little, @large) {
       ((@little xx *).flat Z @large).flat.map(&code)
    }
}

my &hyper-assume = hyperize({&^a.assuming($^b)}, '«');

sub sc($_) {
    .words».&{ hyper-assume((&lc, &uc), .comb)».().join }
}

Hyper-operators have a “direction” indicated by using » or «. Whereby the pointy bit points at the operand that doesn’t stop iteration. In hyperize I’m doing the same with a string literal.

However, this is terribadly slow. The culprit is .assuming, which has been reported to the authorities and will likely be fixed with RakuAST. In my case I don’t really need the fancy things .assuming does.

sub simple-assume(&routine, |tail) {
    sub (|c) {
        my \real-args = \(|tail, |c);
        routine(|real-args)
    }
}

multi sub hyperize(&code, '«') {
    sub (@little, @large) {
       ((@little xx *).flat Z @large).flat.map(&code)
    }
}

my &hyper-assume = hyperize({simple-assume(&^a, $^b)}, '«');

sub sc($_) {
    .words».&{ hyper-assume((&lc, &uc), .comb)».().join }
}

A speed up of factor 608 seems to be quite acceptable. No kidding, as soon as .assuming is involved Rakudo refuses to inline and as a consequence of that to JIT.

I will try to provide a sub assuming (right now we only have the method-form), provided I find a reasonable way to implement the advanced stuff, like skipping arguments with a Whatever.

Iterative golfing

Lured by the Weekly, I went on twitter and lost an hour because lizmat could not resist.

sub sc($str) {
  $str.words.map({
    .comb(2).map({
      .chars == 1 ?? .lc !! .lc.flip.tc.flip
    } ).join
  }).join(" ")
}
say sc "sarcasmcase FOR YOU";
# sArCaSmCaSe fOr yOu

That’s nice and short but in my eyes, showing off on twitter should involve more Raku features. My first shot as follows.

sub sc($_) {
    .words».&{ 
        my @c = &uc, &lc;
        .comb».map({ @c = @c[1..*,0].flat; @c[0]($_);  }).join
    }.flat;
}

I’m trying to use a functional approach by building a list of functions and then rotating that list while I apply the first element in that list. Thus, &lc and &uc are called alternating. That works but looks a bit line noisy.

sub sc($_) {
    my \c = (|(&lc, &uc) xx *).cache;
    .words».&{ (.comb Z c.clone).map( -> ($c, &c) { c($c) }).join }.flat;
}

By building an infinite list of functions, I don’t need to mutate that list. Just using Z will create the right amount of iterators in the background to alternate &lc and &uc. I’m still not happy with the map-part.

sub sc($_) {
    .words».&{ (.comb »,» (&lc, &uc)).flat.map({ &^b($^a) }).join }.flat
}

That’s much shorter and I don’t need to build the infinite list of functions by hand any more. Of cause, that list still exists. It is just hidden within the hyper operator. I’m still not happy with the .map. I’m building a pair of a value and a function-object. If I could .assume, I would not need the .map at all.

multi sub infix:<⊙>(&c, +@a) {
    &c.assuming(|@a)
}
sub sc($_) {
    .words».&{ ((&lc, &uc) «⊙« .comb)».().join }
}

By turning .assuming into an infix, I can use it straight in the hyper-operator. The resulting list of .assumed function can then be called via »..

Infix operators allow us to play functional tricks with very few keystrokes. We already got ∘ to combine functions. It may make sense to include ⊙ into CORE too. I’m not sure about its Texas-variant thought. Any suggestions?

Fooled by complexity

And that fool would be me. After realising that HyperSeq is lazy, I managed to simplify the code in my last post.

sub needle(int \b) {
    sub is-pentagon($c is raw) { (1+sqrt(1+24*$c))%%6 }
    sub P($n is raw) { $n*(3*$n-1) div 2 }

    loop (my int $s = 1; $s < b; $s++) {
        my \bp = P(b);
        my \sp = P($s);
        if is-pentagon(bp + sp) && is-pentagon(bp - sp) {
            return |(b, $s);
        }
    }
}

sub infix:<notnilor>(\maybenil, \alternative) {
    maybenil =:= Nil ?? alternative !! maybenil
}

say (^∞).hyper(:batch(8), :degree(16)).map({.&needle notnilor Empty }).head;

The sub needle transforms its argument or returns Nil. By turning Nil into Empty, any call to .head will skip all values that where not a hit. At least for strongly CPU-bound tasks, which allow for small batch sizes, .hyper doesn’t overshoot much.

my atomicint $steps;
say (^∞).hyper(:batch(8), :degree(16)).map({$steps⚛++; .&needle notnilor Empty }).head;
say $steps;

# OUTPUT: (2167 1020)
          2246

Right now, almost all task are CPU-bound. Once Rakudo has learned to produce better bytecode being able to stop sibling threads will become desirable.

UPDATE

lizmat suggested to simplify the code further by replacing .&needle notnilor Empty with $_ with .&needle. This works because when with doesn’t fire, it returns Empty. That I did not know. It is specced and also applies to if. I filed the ENODOC under #4017. As it seems, we need to be careful not to run out of space on the interwebs by completing Raku’s docs.

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!