pl6anet

Perl 6 RSS Feeds

Steve Mynott (Freenode: stmuk) steve.mynott (at)gmail.com / 2019-01-17T07:11:15


brrt to the future: A short post about types and polymorphism

Published by Bart Wiegmans on 2019-01-14T21:34:00

Hi all. I usually write somewhat long-winded posts, but today I'm going to try and make an exception. Today I want to talk about the expression template language used to map the high-level MoarVM instructions to low-level constructs that the JIT compiler can easily work with:

This 'language' was designed back in 2015 subject to three constraints:
Recently I've been working on adding support for floating point operations, and  this means working on the type system of the expression language. Because floating point instructions operate on a distinct set of registers from integer instructions, a floating point operator is not interchangeable with an integer (or pointer) operator.

This type system is enforced in two ways. First, by the template compiler, which attempts to check if you've used all operands correctly. This operates during development, which is convenient. Second, by instruction selection, as there will simply not be any instructions available that have the wrong combinations of types. Unfortunately, that happens at runtime, and such errors so annoying to debug that it motivated the development of the first type checker.

However, this presents two problems. One of the advantages of the expression IR is that, by virtue of having a small number of operators, it is fairly easy to analyze. Having a distinct set of operators for each type would undo that. But more importantly, there are several MoarVM instructions that are generic, i.e. that operate on integer, floating point, and pointer values. (For example, the set, getlex and bindlex instructions are generic in this way). This makes it impossible to know whether its values will be integers, pointers, or floats.

This is no problem for the interpreter since it can treat values as bags-of-bits (i.e., it can simply copy the union MVMRegister type that holds all values of all supported types). But the expression JIT works differently - it assumes that it can place any value in a register, and that it can reorder and potentially skip storing them to memory. (This saves work when the value would soon be overwritten anyway). So we need to know what register class that is, and we need to have the correct operators to manipulate a value in the right register class.

To summarize, the problem is:
There are two ways around this, and I chose to use both. First, we know as a fact for each local or lexical value in a MoarVM frame (subroutine) what type it should have. So even a generic operator like set can be resolved to a specific type at runtime, at which point we can select the correct operators. Second, we can introduce generic operators of our own. This is possible so long as we can select the correct instruction for an operator based on the types of the operands.

For instance, the store operator takes two operands, an address and a value. Depending on the type of the value (reg or num), we can always select the correct instruction (mov or movsd). It is however not possible to select different instructions for the load operator based on the type required, because instruction selection works from the bottom up. So we need a special load_num operator, but a store_num operator is not necessary. And this is true for a lot more operators than I had initially thought. For instance, aside from the (naturally generic) do and if operators, all arithmetic operators and comparison operators are generic in this way.

I realize that, despite my best efforts, this has become a rather long-winded post anyway.....

Anyway. For the next week, I'll be taking a slight detour, and I aim to generalize the two-operand form conversion that is necessary on x86. I'll try to write a blog about it as well, and maybe it'll be short and to the point. See you later!

Weekly changes in and around Perl 6: 2019.02 Is it Spring?

Published by liztormato on 2019-01-14T15:05:26

For Jonathan Stowe it is already spring. In a spring cleanup, he updated so many modules to CPAN that the numbers are simply staggering. Thanks, Jonathan, for all these goodies: XDG::BaseDirectory, Igo, AccessorFacade, Audio::PortMIDI, App::ModuleSnap, Attribute::Lazy, Acme::Insult::Lala, Audio::Silan, Audio::Convert::Samplerate, Linux::Fuser, Linux::Cpuinfo, Audio::Encode::LameMP3, Audio::Fingerprint::Chromaprint, CheckSocket, Log::Syslog::Native, Crypt::Libcrypt and Util::Bitfield. It’s good to see all of these modules receive the love they deserve!

Grant Extension Request

Jonathan Worthington has requested an extension to his Perl 6 Performance and Reliability Engineering grant. Please feel free to leave your comments with this request, unless you’re already done that, of course.

brrt’s Resolutions

Bart Wiegmans looked back on the past year, and looks forward in his blog post titled “New years post“.

Additional getting things done

Alexey Melezhik added examples of (non-)exported functions and how to make replacements in strings to his Getting Things Done tutorial.

Cheerleading

bobthecimmerian started a discussion on Reddit about Perl 6 cheerleading. I think everybody agrees the potential is there!

A different look

ogniloud proposed a different look for the perl6.org website.

Iterating past the finish

Wenzel P. P. Peppmeyer published a blog post about his attempts to augment the Cool class, and the interesting dragons he encountered on his journey (Reddit comments).

Decompressing Zelda 3 GFX

Sylvain Colinet describes how he used Perl 6 grammars and actions as a decompression algorithm. Definitely one of the more interesting uses of grammars yours truly has seen so far.

Core Developments

Questions about Perl 6

Meanwhile on Twitter

Meanwhile on perl6-users

Perl 6 in comments

Perl 6 modules

New modules:

Updated modules:

Winding down

A relative quiet week, also on account of last week’s Perl 6 Weekly being late, and this one being early. See you next week for your regular dose of Perl 6 news!

gfldex: Iterating past the finish

Published by gfldex on 2019-01-11T09:55:25

A while ago the question was raised how to augment Any. As it turns out the augmenting part is working but the newly added method is not propagated to children of buildin types. One can force the propagation by calling .compose on all type objects. Getting a list of all parents is done with .^mro and the check is done with .

augment class Cool { method HTML { HTML.new(self) } }
if Cool ∈ T.HOW.mro(T) { T.HOW.compose(T); }

I stepped on a Dragon

The tricky part is to get all predefined classes. Mostly because there is a lot of stuff in CORE:: that doesn’t even implement the interfaces to call methods. We can call .DEFINITE because that’s not a method. So we can weed out all predefined objects and are left with type objects and stuff that’s leaking from NQP into Perl 6-land. Those beasties don’t implement .mro so by guarding with try we can bild a list of all Perl 6 type objects. Those type objects contain IterationEnd. Hence we can’t trust for or anything else that is using iterators to loop over a list. There is also Slip in the list. We can help that by using binding everywhere.

my @a = CORE::.values;
my @types;
for 0..^@a.elems -> $i {
my \T := @a[$i];
try @types[$++] := T if not T.DEFINITE;
}

for 0..^@types.elems -> $i {
my \T := @types[$i];
try if Cool ∈ T.HOW.mro(T) {
T.HOW.compose(T);
}
}

And there we have it. All children of Cool have been re-.composed.

It’s no magic!

There are a few things I learned. Firstly much of the magic behind Perl 6 are just type checks. Anything that deals with iteration of lists or similar constructs is checking for Slip or IterationEnd and branching out to deal with their special nature.

And secondly there are a lot of interfaces leaking into spec-land that have no business there. I’m worried that might bite us later because any useful interface will be abused by programmers sooner or later. I would prefer the inner workings of Rakudo to be well hidden.

I found a way to deal with agumenting build in types so it can’t be long before the core devs fix that bug.

brrt to the future: New years post

Published by Bart Wiegmans on 2019-01-06T21:15:00

Hi everybody! I recently read jnthns Perl 6 new years resolutions post, and I realized that this was an excellent example to emulate. So here I will attempt to share what I've been doing in 2018 and what I'll be doing in 2019.

In 2018, aside from the usual refactoring, bugfixing and the like:
So 2019 starts with me trying to complete the goals specified in that grant request. I've already partially completed one goal (as explained in the interim report) - ensuring that register encoding works correctly for SSE registers in DynASM. Next up is actually ensuring support for SSE (and floating point) registers in the JIT, which is surprisingly tricky, because it means introducing a type system where there wasn't really one previously. I will have more to report on that in the near future.

After that, the first thing on my list is the support for irregular register requirements in the register allocator, which should open up the possibility of supporting various instructions.

I guess that's all for now. Speak you later!

Weekly changes in and around Perl 6: 2019.01 Wishes for 2019

Published by liztormato on 2019-01-08T11:56:20

After enjoying the fireworks in his hometown and looking back on his grant work in December, Jonathan Worthington looks forward to 2019 giving an overview of features to appear in Perl 6 and MoarVM. Such as Partial Escape Analysis, decreasing compilation and startup time, and more concurrency safety. As well as getting Cro to 1.0 and getting the community version of the Comma IDE out. Looks like it’s going to be a busy year for Jonathan again (Reddit comments).

Rakudo on Javascript

Paweł Murias has written an update on the Javascript backend. He describes his work that is specific for the Javascript backend, and the stuff he’s done that is more generally useful, such as pre-compiling scripts before execution. Generally, and more specifically when doing a spectest, to shake out the last bugs with regards to precompilation.

Leapt seconds

Brian Duggan explains the support for leap seconds in Perl 6. And the intricacies when working with DateTime and Instant objects, taking leap seconds into account.

Tomtit profiles

Alexey Melezhik introduces Tomtit profiles, sets of predefined tasks that you can have Tomtit run for you. Interesting stuff if you’re really lazy!

Introducing p6env

Shoichi Kaji-san introduces a new tool for managing different versions of Rakudo Perl 6 called p6env. If you know how plenv works, you’re all set!

Squashathon results

Last Saturday saw yet another squashathon, this time focused on open issues that needed testing. And the winner is Ben Davies! (activity log).

Zoffix

Careful Rakudo Perl 6 observers may have noticed that Zoffix‘s Twitter feed has been very quiet since his tweet about awaiting Larry’s ruling with regards to the way the alias “Raku” should be used. His last tweet announced that he will no longer be involved in Perl 6 at all. On the #perl6 IRC channel, Zoffix worded it as “the project’s direction and management style doesn’t match my goals and I’ll be happier elsewhere“.

This is really sad news. Zoffix has meant a lot for the Perl 6 effort: just by looking at the sheer number of commits in the Rakudo repo, should give one an idea on how much he has done in the past 3 years. And that’s without taking into account all of the other things he’s done for Perl 6.

Zoffix, thank you for all of the work you have done! I can only hope that Larry will be able to share his views on the alias question soon and in a way that will make Zoffix come back to Perl 6.

Ticket updates

Aleks-Daniel Jakimenko-Aleksejev has made a nice overview page of current and past updates on the status of Rakudo tickets. In it, you can for instance see that people created 1254 new issues in 2018. By that metric, one can see that there’s still a lot of work to be done. But also that a lot of people are actually using Rakudo Perl 6!

Core Developments

Questions about Perl 6

Meanwhile on Twitter

Meanwhile on Facebook

Meanwhile on perl6-users

Perl 6 in comments

Perl 6 modules

New modules:

Updated modules:

Winding Down

A week with very mixed feelings. Joy in seeing a new year start and the anticipation of good things about to happen in 2019. An example of which are five new Perl 6 modules on CPAN, of which at least one has the potential of becoming a killer application feature of Perl 6.

Mixed feelings because of the sadness of seeing a core team member deciding on not wanting to wait any longer for guidance. Being an optimist at heart, yours truly hopes to be able to report soon that Zoffix has come back to the project that is clearly close to his heart.

So see you next week for more Perl 6 news!

Jo Christian Oterhals: Won’t your Linux laptop charge when the battery’s drained completely? This may fix it

Published by Jo Christian Oterhals on 2019-01-03T21:26:26

I’ve got a dual-boot laptop that lets me switch between Windows 10 and Linux. The Linux distribution varies between Ubuntu 18.04 LTS, 18.10 and Fedora 29, but what I’m about to describe is the same for all of them.

Sometimes — for instance now over the holidays — my laptop can lay unused for days. If I was booted into Linux and did not shutdown the computer before closing, the battery slowly drains. After a few days it’s completely discharged.

When I connect the computer to AC power and boot Linux again, the charge remains at 0 %. It basically doesn’t charge, and the GUI is unable to calculate how much time remains before fully charged. Given that it actually doesn’t charge, that’s not surprising. At first, though, I thought that this maybe only was a reporting error. But running acpi from the command line verified the issue (“will never charge”).

A few Google searches tells me that I’m not alone in having this problem. People have suggested replacing the battery or even the charger itself. But I have never suspected that this is a hardware issue. Because if I boot into Windows the computer manages to recharge. It surprised me that software could have something to do with charging, something I’d always thought of as an hardware thing. But I didn’t bother researching it further; this cumbersome solution worked well enough, it was just a bit annoying.

But this Christmas I managed to delete my Windows partition and suddenly charging-by-Windows was no longer an option. So now I actually had to figure it out. My Google searches didn’t help, so for some reason I opened the BIOS setup (press and hold F2 when booting your computer to access this).

Under Advanced I found a setting called FlexiCharger. Apparently this is a mechanism to prevent the battery from both draining and charging completely. The idea is that this will improve battery longevity, although it somewhat decreases the time you can operate your computer on battery only, as your computer — ideally — will never be fully charged.

What it does isn’t important here; what’s important is that on my computer FlexiCharger was disabled.

I pressed Enter and enabled it. I didn’t know what to enter, so I set stop charge to 100 %. As I understand it I should set it to around 80 %, but battery longevity wasn’t the issue here — getting it to charge was, so I didn’t bother adjusting this at the time (maybe I will now).

My guess is that the values here is not important for solving the charge issue, so enter whatever you like here. In my case the settings looked like this when I had enabled the function:

I saved these settings and rebooted into Linux. And lo and behold! The computer charged again!

Why this helps beats me — I guess the minimum charge settings has something to do with it. Maybe it’s forcing a charge up to 40 % when the hardware discovers it’s below that. I don’t know. I’m just glad that it helped.

Hopefully this may be a solution for you too, should you have the same issue as me.

6guts: My Perl 6 wishes for 2019

Published by jnthnwrthngtn on 2019-01-02T01:35:51

This evening, I enjoyed the New Year’s fireworks display over the beautiful Prague skyline. Well, the bit of it that was between me and the fireworks, anyway. Rather than having its fireworks display at midnight, Prague puts it at 6pm on New Year’s Day. That makes it easy for families to go to, which is rather thoughtful. It’s also, for those of us with plans to dig back into work the following day, a nice end to the festive break.

Prague fireworks over Narodni Divadlo

So, tomorrow I’ll be digging back into work, which of late has involved a lot of Perl 6. Having spent so many years working on Perl 6 compiler and runtime design and implementation, it’s been fun to spend a good amount of 2018 using Perl 6 for commercial projects. I’m hopeful that will continue into 2019. Of course, I’ll be continuing to work on plenty of Perl 6 things that are for the good of all Perl 6 users too. In this post, I’d like to share some of the things I’m hoping to work on or achieve during 2019.

Partial Escape Analysis and related optimizations in MoarVM

The MoarVM specializer learned plenty of new tricks this year, delivering some nice speedups for many Perl 6 programs. Many of my performance improvement hopes for 2019 center around escape analysis and optimizations stemming from it.

The idea is to analyze object allocations, and find pieces of the program where we can fully understand all of the references that exist to the object. The points at which we can cease to do that is where an object escapes. In the best cases, an object never escapes; in other cases, there are a number of reads and writes performed to its attributes up until its escape.

Armed with this, we can perform scalar replacement, which involves placing the attributes of the object into local registers up until the escape point, if any. As well as reducing memory operations, this means we can often prove significantly more program properties, allowing further optimization (such as getting rid of dynamic type checks). In some cases, we might never need to allocate the object at all; this should be a big win for Perl 6, which by its design creates lots of short-lived objects.

There will be various code-generation and static optimizer improvements to be done in Rakudo in support of this work also, which should result in its own set of speedups.

Expect to hear plenty about this in my posts here in the year ahead.

Decreasing startup time and base memory use

The current Rakudo startup time is quite high. I’d really like to see it fall to around half of what it currently is during 2019. I’ve got some concrete ideas on how that can be achieved, including changing the way we store and deserialize NFAs used by the parser, and perhaps also dealing with the way we currently handle method caches to have less startup impact.

Both of these should also decrease the base memory use, which is also a good bit higher than I wish.

Improving compilation times

Some folks – myself included – are developing increasingly large applications in Perl 6. For the current major project I’m working on, runtime performance is not an issue by now, but I certainly feel myself waiting a bit on compiles. Part of it is parse performance, and I’d like to look at that; in doing so, I’d also be able to speed up handling of all Perl 6 grammars.

I suspect there are some good wins to be had elsewhere in the compilation pipeline too, and the startup time improvements described above should also help, especially when we pre-compile deep dependency trees. I’d also like to look into if we can do some speculative parallel compilation.

Research into concurrency safety

In Perl 6.d, we got non-blocking await and react support, which greatly improved the scalability of Perl 6 concurrent and parallel programs. Now many thousands of outstanding tasks can be juggled across just a handful of threads (the exact number chosen according to demand and CPU count).

For Perl 6.e, which is still a good way off, I’d like to having something to offer in terms of making Perl 6 concurrent and parallel programming safer. While we have a number of higher-level constructs that eliminate various ways to make mistakes, it’s still possible to get into trouble and have races when using them.

So, I plan to spend some time this year quietly exploring and prototyping in this space. Obviously, I want something that fits in with the Perl 6 language design, and that catches real and interesting bugs – probably by making things that are liable to occasionally explode in weird ways instead reliably do so in helpful ways, such that they show up reliably in tests.

Get Cro to its 1.0 release

In the 16 months since I revealed it, Cro has become a popular choice for implementing HTTP APIs and web applications in Perl 6. It has also attracted code contributions from a couple of dozen contributors. This year, I aim to see Cro through to its 1.0 release. That will include (to save you following the roadmap link):

Comma Community, and lots of improvements and features

I founded Comma IDE in order to bring Perl 6 a powerful Integrated Development Environment. We’ve come a long way since the Minimum Viable Product we shipped back in June to the first subscribers to the Comma Supporter Program. In recent months, I’ve used Comma almost daily on my various Perl 6 projects, and by this point honestly wouldn’t want to be without it. Like Cro, I built Comma because it’s a product I wanted to use, which I think is a good place to be in when building any product.

In a few months time, we expect to start offering Comma Community and Comma Complete. The former will be free of charge, and the latter a commercial offering under a subscribe-for-updates model (just like how the supporter program has worked so far). My own Comma wishlist is lengthy enough to keep us busy for a lot more than the next year, and that’s before considering things Comma users are asking for. Expect plenty of exciting new features, as well as ongoing tweaks to make each release feel that little bit nicer to use.

Speaking, conferences, workshops, etc.

This year will see me giving my first keynote at a European Perl Conference. I’m looking forward to being in Riga again; it’s a lovely city to wander around, and I remember having some pretty nice food there too. The keynote will focus on the concurrent and parallel aspects of Perl 6; thankfully, I’ve still a good six months to figure out exactly what angle I wish to take on that, having spoken on the topic many times before!

I also plan to submit a talk or two for the German Perl Workshop, and will probably find the Swiss Perl Workshop hard to resist attending once more. And, more locally, I’d like to try and track down other Perl folks here in Prague, and see if I can help some kind of Praha.pm to happen again.

I need to keep my travel down to sensible levels, but might be able to fit in the odd other bit of speaking during the year, if it’s not too far away.

Teaching

While I want to spend most of my time building stuff rather than talking about it, I’m up for the occasional bit of teaching. I’m considering pitching a 1-day Perl 6 concurrency workshop to the Riga organizers. Then we’ll see if there’s enough folks interested in taking it. It’ll cost something, but probably much less than any other way of getting a day of teaching from me. :-)

So, down to work!

Well, a good night’s sleep first. :-) But tomorrow, another year of fun begins. I’m looking forward to it, and to working alongside many wonderful folks in the Perl community.

Weekly changes in and around Perl 6: 2018.53 Goodbye PerlJam

Published by liztormato on 2018-12-30T22:26:51

This week saw the peaceful passing of Jonathan “Scott” Duff (aka perlpilot and PerlJam) at the much too early age of 47. Scott has been heavily involved with Perl 6 since at least the days of Pugs (as far as yours truly has been able to trace back).

Although he would have described his contributions to Perl 6 as small, they have been important in that they helped others to build further at the very early stages of Perl 6. Perhaps more importantly, from at least 2005 until last summer (when he became too ill), Scott has participated almost daily in discussions on the #perl6 IRC channel in the kind and supporting way that people who know him, appreciated him for.

He will be sorely missed. Scott: thanks for all the fish!

Scott on Facebook (Facebook users only) and the go fund me campaign of his family: all donations will be appreciated.

This year’s final Advent posts

Too late for last week’s Perl 6 Weekly:

Getting things done

An interaction about the use of grep and map on the #perl6 IRC channel made Alexey Melezhik realize that it would be handy to have such an example be made more accessible. He even has a little movie to show what that would look like.

Calling subs and typing

Elizabeth Mattijsen had the 9th article about migrating from Perl 5 to Perl 6 published on opensource.com: Calling subs and typing in Perl 6 (Reddit comments).

Squashathon time again

Next Saturday will see yet another Community Squashathon, this time focused on testing. And as usual, “Saturday” will be interpreted as “Saturday anywhere on Earth”, so it will be more like 47 hours worth of fixing, documenting and adding tests. Please join us in making sure we get Perl 6 even better tested than it already is!

Core Developments

Two weeks of core developments this time, as promised last week:

Questions about Perl 6

Meanwhile on Twitter

Meanwhile on Facebook

Meanwhile on perl6-users

Perl 6 in comments

Perl 6 modules

Updated modules:

Winding Down

A week with very mixed feelings. Be careful with any fireworks if you’re celebrating the New Year! Yours truly hopes to see you all and well reading the next Perl 6 Weekly!

Perl 6 Advent Calendar: Day 25 – Calling Numbers Names

Published by uzluisfx on 2018-12-24T23:01:41

This school semester I took my first proof-based class titled “Intro to Mathematical Proof Workshop”. After having taken other math classes (Calculus, Matrix Algebra, etc.), I felt that I didn’t have that much of a mathematical foundation and up to this point, all I had been doing was purely computational mathematics sprinkled with some proofs here and there. Looking back, I found the class quite enjoyable and learning about different theorems and their proofs, mostly from number theory, has given me a new perspective of mathematics.

“How is this related to Perl 6?”, you might be asking. As I mentioned, most of the proofs that were discussed either in class or left for homework were related to number theory. If there’s one thing Perl 6 and number theory have in common is their accessibility. Similar to how the content of the elementary theory of numbers can be tangible and familiar, Perl 6 can be quite approachable to beginners. In fact, beginners are encouraged to write what’s known as “baby Perl”.

Another thing they seem to share is their vastness. For example, in Perl 6 one can find many operators while in number theory one can find a plethora of different types of numbers from even numbers to cute numbers. For most purposes, these numbers are easy to understand and if one has the definition of a number, then it’s quite easy to check if a given integer follows in that category. For example, a prime number is formally defined as follows:

An integer p > 1 is called a prime number, or simply a prime, if its only positive divisors are 1 and p. Otherwise, the integer p is termed composite.

By using this definition, we can quite simply figure out if a certain number is a prime. For example, among the first ten positive integers, 2, 3, 5 and 7 are primes. This is quite trivial for small numbers but doing it by hand with larger numbers would become tedious in no time. This is where Perl 6 comes into the picture. Perl 6 offers many constructs/features that even if they don’t make the job easy, they certainly simplify it. For instance, with the definition of a prime in mind, we could easily implement an algorithm that tests for primality in Perl 6:

sub isPrime( $number ) {
    return $number > 1 if $number ≤ 3;

    loop (my $i = 2; $i² ≤ $number; $i++) {
        return False if $number %% $i;
    }

    return True;
}

Please bear in mind that this is not about writing performant code. If the code turns down that way, then it would be excellent but it is not the goal. My aim is to showcase the easiness with which a beginner can express mathematical constructs in Perl 6. It’s worth mentioning that Perl 6 already includes the subroutine (or method) is-prime that tests for primality. However, although this is true for prime numbers, it might not be the case for another type of number you might come across such as a factorial, a factorion or even a Catalan number. And in cases like this, Perl 6 will be helpful.

After learning about different types of numbers, I set out to look for some peculiar numbers and see how I could implement them using Perl 6. In the process, I found this useful website that lists a bunch of numbers, their definitions and some examples. From all of these, I’ve chosen four types of numbers that aren’t stupidly difficult to implement (I still write baby Perl 😅) while being enough to illustrate some Perl 6 constructs. On the other hand, I’ve avoided those which might be too straightforward.

Let us start with…

Amicable numbers

Amicable numbers are pairs of numbers, also known as friendly numbers, each of whose aliquot parts add to give the other number.

sub aliquot-parts( $number ) {
   (^$number).grep: $number %% *; 
}

sub infix:<amic>( $m, $n ) {
    $m == aliquot-parts($n).sum &&
    $n == aliquot-parts($m).sum;
}

say 12 amic 28;   # False, 12 and 28 aren't amicables.
say 220 amic 284; # True, 220 and 284 are though.

A number’s aliquot parts are its factors excluding the number itself. To find the aliquot parts of a number, I’ve a created the subroutine aliquot-parts which uses 1..^$number to create a list of numbers from 1 up to $numbers (exclusive). This list is subsequently grepped to find out those numbers in the list that evenly divide $number. In this snippet it’s achieved by using the infix operator %% which returns True if a first operand is divisible by a second operand. Otherwise, it returns False. The second operand stands for any number in the list aforementioned so I’ve used *, which in this context is known as the whatever star and creates a closure over the expression $number %% *. Thus the whole expression in the subroutine is equivalent to (^$number).grep: { $number %% $_ };. At the end, the subroutine returns a list of factors of $number excluding $number itself.

To find out if two numbers are amicable, we could have used just a subroutine. However, Perl 6 allows for the creation of new operators, which are just subroutines with funny names themselves, and I’ve done just that. I created the infix operator (meaning between two operands) amic that returns True if two numbers are amicable. Otherwise, False. As you can see, the syntax to create a new operator is straightforward: the keyword sub, followed by the type of the operator (prefix, infix, postfix, etc.), the name of the operator inside quoting constructs, the expected parameters and a code block.

Factorion

A factorion is a natural number that equals the sum of the factorials of its digits in a given base.

subset Whole of Int where * ≥ 0;

sub postfix:<!>( Whole $N --> Whole ) {
    [*] 1..$N;
}

sub is-factorion( Whole $number --> Bool ) {
    $number == $number.comb.map({ Int($_)! }).sum 
}

say is-factorion(25);  # False
say is-factorion(145); # True

Recall that a factorial of a number N, which is usually denoted by N!, is the product 1 x 2 x ... x N. For example, 3! = 1 x 2 x 3 = 6. In the code snippet, I created the postfix operator ! to return the factorial of an integer operand. Thus say 3!; will work just fine in the code snippet and prints 6. How the factorial is calculated is straightforward: The range 1..$N creates a list of numbers from 1 to $N (inclusive) and then I use [...], which is known as the reduction meta-operator, with the operator * to reduce the created list to 1 x 2 x ... $N which effectively gives me the factorial of $N. There are many operators in Perl 6 and the meta-operator [...] can work with many of them.

As for the factorion, I want to know if a number is a factorion so I created a subroutine that takes an integer and returns a Boolean. Perl 6 is gradually typed so it allows to type variables explicitly, specify the return type of a sub, etc. I’ve decided to type the subroutines’ parameters and the subroutine’s return type.

In the section about the amicable numbers, I was quite liberal regarding the subroutines’ arguments. However, here I’ve decided to comply with the definition of a factorial and only allow for whole numbers, hence the definition and use of the Whole type. In Perl 6, the operator subset declares a new type using a base type. However if I hadn’t used the where clause, I’d have ended up with just another name for the Int type which would be redundant. So I used the where clause to constraint the type of any assignment to the desired input. In this case, the assignment to a variable of type Whole.

With the is-factorion sub, I used the method comb to break up $number into its digits and then use map to find their respective factorials and sum them up. The sub returns True if $number is equal to the sum of the factorials of its digits. It returns False otherwise.

Cyclic Numbers

A cyclic number is a number with N digits, which, when multiplied by 1, 2, 3, ..., N produces the same digits in a different order.

sub is-cyclic( Int $n --> Bool ) {
    for 1..$n.chars -> $d {
        return False if $n.comb.Bag != ($n * $d).comb.Bag;
    }
    return True;
}

say is-cyclic(142857); # True
say is-cyclic(95678);  # False

Here I created the subroutine is-cyclic that takes an integer and returns a Boolean value. I use a for loop to iterate over the places of the number’s digits (1st, 2nd, etc.) and use them to multiply the number in each iteration. Afterward I use the previously seen comb method followed by the Bag method. In Perl 6, a Bag is an immutable collection of distinct elements in no particular order where each element is weighted by the number of copies in the collection. This is the kind of structure I need since only the number’s digits and their amounts are important, not their order and a Bag accomplishes exactly this. The subroutine returns False if the bags don’t have the same numbers or have the same numbers but are weighted differently. Otherwise, True is returned indicating the number’s cyclic-ness.

Happy numbers

A happy number is defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits in base-ten, and repeat the process until the number either equals 1 (where it will stay), or it loops endlessly in a cycle that does not include 1.

sub is-happy( $n is copy ) {
    my $seen-numbers = :{};
    while $n > 1 {
        return False if $n ∈ $seen-numbers;
        $seen-numbers{$n} = True;
        $n = $n.comb.map(*²).sum
    }
    return True;
}

say is-happy(7);     # True
say is-happy(2018);  # False

After going through the process described in the definition, a happy number ends being equal to 1. On the other hand, a non-happy number follows a sequence that reaches the cycle 4, 16, 37, 58, 89, 145, 42, 20, 4,… which excludes 1. Armed with this fact, I created the hash $seen-numbers to keep track of such numbers. As illustrated by the while loop, the process is repeated over and over while $n is greater than 1 or until a number has been seen. Here the line that stands out is the one containing the symbol ∈. In set theory, if an element p is a member (or element) of a set A, then it’s denoted by p ∈ A and this exactly what’s being tested here. If the number $n is an element of the hash, then the sub returns False. Otherwise, it returns True which indicates the number’s happiness.

Summary

In this post, I slightly went over gradual typing, how to define a new operator, sub-classing by using the subset keyword and the set and bag data structures. As you may have realized, Perl 6 offers many constructs that facilitate many different tasks. In this instance, it was my desire to express definitions of numbers in a more programmatic way. Yours could be totally different but you can rest assured that Perl 6 is there to make the job easier and immensely more enjoyable.

Well…that’s all folks! Happy Christmas and a wonder-ofun New Year!

Perl 6 Inside Out: 🎄 26/25. Overview of the Perl 6 One-Liner Advent Calendar 2018

Published by andrewshitov on 2018-12-24T20:27:55

The Perl 6 One-Liner Advent Calendar 2018 is over! Let’s make a quick overview of what we have covered so far. There were a few themes covered.

First, some one-liners from the Perl 6 Calendar 2019 were explained in more detail. We looked at how to generate random passwords and random integers, how to print current date, and at how good Perl 6 is doing with Unicode.

Second, a number of problems from Project Euler were solved in Perl 6: #1 grepping dividable numbers, #2 adding up even Fibonacci numbers, #4 testing palindromic numbers, #5 finding the least common divider, #7 printing the given Fibonacci number, #13 computing a sum of big numbers, #19 counting Sundays and counting them differently, #25 finding a Fibonacci number of the given length, and #34 finding a sum of the numbers that are equal to the sum of factorials of their digits.

Third, we looked at some isolated elements of Perl 6 syntax, such as meta-operator X, range and sequence operators, reduction operator, or how rational numbers work in Perl 6 and how to use complex number in geometry. A numerous times, we were using the built-in routines map and grep, and the WhateverCode objects.

Fourth, we explored a few common sequences: Fibonacci numbers and prime numbers, or the Leibnitz series for computing the value of π.

Fifth, we solved a few golf problems: how to print the first Fibonacci numbers, or how to print the first prime numbers. A separate post was dedicated to the ideas of how to make the code more compact.

Sixth, we moved on to command-line tools, covered the basic options that Rakudo supports and created a few one-liners for manipulating files, such as the one for renaming a bunch of files, or reversing a text file, or merging two files horizontally, or computing totals from the table columns, or how to read from multiple input files.

As a bonus, the posts from the One-Liner calendar have been translated to Chines, thanks to Chen Yf (if I decoded the name correctly).

Also, don’t forget about my article in the regular Perl 6 Advent Calendar about how to make the grammar more compact.

Perl 6 Inside Out: 🎄 25/25. Tips and ideas for the Perl 6 Golf code

Published by andrewshitov on 2018-12-24T20:20:20

Welcome to Day 25, the last day of the Perl 6 One-Liner Advent Calendar! Traditional advent calendars have only 24 entries, and our bonus post today will be dedicated to some tips and tricks that you can use in Perl 6 golf contest.

There is a great site, code-golf.io, where you can try solving a number of problems, and move Perl 6 to the top scores. I suspect that many problems can benefit from the techniques that were covered in the previous days of this One-Liner Advent Calendar.

Omitting topic variable

If methods are called on the topic variable $_, then the name of the variable is not really needed for Perl 6 to understand what you are talking about, so, avoid explicitly naming the topic variable:

$_.say for 1..10

Using ranges for making loops

Ranges in Perl are great things to express loop details: in a few characters, you specify both the initial and final state of the loop variable. Postfix forms are usually shorter.

for 1..10 {.say}
.say for 1..10

Think if you can count from 0, in which case, a caret character can be used to get a range starting from 0. The following code prints the numbers 0 to 9:

.say for ^10

Choosing between a range and a sequence

In loops, sequences can work exactly the same as a range would do. The choice may depend on whether the Golf software counts bytes or Unicode characters. In the first case, the two dots of a range are preferable over the three dots of a range. In the second case, use a Unicode character:

.say for 1..10
.say for 1...10
.say for 1…10

When you need to count downwards, sequences are your friends, as they can deduce the direction of changing the loop counter:

.say for 10…1

Using map instead of a loop

In some cases, especially when you have to make more than one action with the loop variable, try using map to iterate over all the values:

(^10).map: *.say

Omitting parentheses

Unlike Perl 5, Perl 6 does not force you to use parentheses in condition checks in the regular form:

if ($x > 0) {say $x;exit}
if $x > 0 {say $x;exit}

Sometimes, you will want to omit parentheses in function calls, too.

Neither you need parentheses when declaring arrays or hashes. With arrays, use the quoting construct on top of that:

my @a = ('alpha', 'beta')
my @b=<alpha beta>

Using chained comparisons

Another interesting feature is using more than one condition in a single expression:

 say $z if $x < 10 < $y

Choosing between methods and functions

In many cases, you can choose between calling a function and using a method. Method calls can be additionally chained after each other, so you can save a lot of parentheses or spaces:

(^10).map({.sin}).grep: *>0 

When there exist both a method and a stand-alone function, method call is often shorter or at least the same length if you omit parentheses.

abs($x)
abs $x
$x.abs

Using Unicode characters

Perl 6 operators often have Unicode equivalents, where you can express a wordy construct with a single character. Compare:

if $x=~=$y
if $x≅$y

Built-in constants are also available in the Unicode space, for example, pi vs π, or Inf vs .

There are many numbers, both small and big, that can be replaced with a single Unicode symbol: 1/3 vs , or 20 vs , or 100 vs .

Using superscripts

Superscripts are great for calculating powers. Compare:

say $x**2
$x².say

Using \ to make sigilless variables

Don’t forget about the the following way of binding containers and creating a kind of a sigilless variable:

my \a=42;say a

Using default parameters

When you are working with functions or class methods, check if there are default values in their signatures. Also check if there is an alternative variant with positional arguments. Compare, for example, three ways of creating a date object.

Date.new(year=>2019,month=>1,day=>1)
Date.new(year=>2019)
Date.new(2019,1,1)

Using && instead of if

Boolean expressions can save a few characters, as Perl will not calculate the second condition if the first gives the result already. For example:

.say if $x>0   
$x>0&&.say

Choosing between put vs say

Finally, sometimes it is better to use put instead of say. In some cases, you will be free from parentheses in the output when printing arrays, for example. In some other cases you will get all values instead of concise output when working with ranges, for example:

> say 1..10
1..10
> put 1..10
1 2 3 4 5 6 7 8 9 10

Till next year!

You can also find many interesting ideas in the last year’s advent post by Aleks-Daniel Jakimenko-Aleksejev.

But this time, this Perl 6 One-Line Advent Calendar is completely over. There will be one more post with an overview of everything published in the last 25 days.

I wish you all the best with your further Perl 6 adventure, would it be one-liners or industrial-scale applications. See you next year in another advent calendar, but don’t forget that perl6.online continues its work, and more posts will be published during the next 2019 year!

Weekly changes in and around Perl 6: 2018.52 Three Years Later

Published by liztormato on 2018-12-24T00:09:34

It was only 3 years ago that the first official release of Perl 6 saw the light of day. Today, we are 36 compiler releases on, with the latest one, the 2018.12 release coming out a few days ago. Again done by Samantha McVey and Aleks-Daniel Jakimenko-Aleksejev, with Claudio Ramirez again taking immediate care of the Linux packages. It all seems so normal. And that’s a good thing! Although some applause is always appreciated!

Prepare Your Presentations!

Both the German Perl Workshop (6-8 March 2019) and the DC-Baltimore Perl Workshop (6 April 2019) have announced their Call For Presentations. The CFP for the German Perl Workshop ends on 20 January, and the CFP for the DC-Baltimore Perl Workshop ends on 31 January. What better time to contemplate your Perl 6 Presentations for 2019 than the Holiday Season? Or even better, prepare them?

Tomtit!

Alexey Melezhik has written two blog posts about his latest product Tomtit: One Tomtit to make it and Automation of Perl 6 development workflow through the Tomtit task runner. A great new alternative to source code management and build automation! (Reddit comments).

Manage PostgreSQL Version (strings)

Luca Ferrari has written a nice blog post about a Perl 6 class to manage PostgreSQL Version strings in a Perl 6 program. A nice example of a small utility class. Too bad it isn’t in the ecosystem or on CPAN yet 😦

A new tool for language compilers

Andrew Shitov has had his presentation using grammars to design and implement a programming language accepted in the Minimalistic Languages track at the next FOSDEM (2/3 february 2019). Congratulations! (/r/perl6, /r/ProgrammingLanguages comments).

Tis the Time of Year

The final set of general Advent Posts:

And the one-line Advent Posts by Andrew Shitov:

If you’re more fluent in Chinese, you can also read all of Andrew Shitov‘s one-liner Advent Posts in Chinese, thanks to 0条评论 (Reddit comments).

Questions about Perl 6

Meanwhile on Twitter

Meanwhile on Facebook

Meanwhile on perl6-users

Perl 6 in comments

Perl 6 Modules

New Modules:

Update modules:

Winding Down

Since not a lot has happened in the past week apart from the work done on getting the 2018.12 Rakudo compiler release out of the door, yours truly will keep the other core developments for the next Perl 6 Weekly, scheduled next Sunday. See you then!

Perl 6 Advent Calendar: Day 24 – Topic Modeling with Perl 6

Published by titsuki on 2018-12-24T00:01:47

Hi, everyone.

Today, let me introduce Algorithm::LDA.
This module is a Latent Dirichlet Allocation (i.e., LDA) implementation for topic modeling.

Introduction

What’s LDA? LDA is one of the popular unsupervised machine learning methods.
It models document generation process and represents each document as a mixture of topics.

So, what does “a mixture of topics” mean? Fig. 1 shows an article in which some of the words are highlighted in three colors: yellow, pink, and blue. Words about genetics are marked in yellow; words about evolutionary biology are marked in pink; words about data analysis are marked in blue. Imagine all of the words in this article are colored, then we can represent this article as a mixture of topics (i.e., colors).

Fig. 1:
Fig. 1
(This image is from “Probabilistic topic models.” (David Blei 2012))

OK, then I’ll demonstrate how to use Algorithm::LDA in the next section.

Modeling Quotations

In this article, we explore Wikiquote. Wikiquote is a cloud-sourced platform providing sourced quotations.
By using Wikiquote API, we get quotations that are used for LDA estimation. After that, we execute LDA and plot the result.
Finally, we create an information retrieval application using the resulting model.

Preliminary

Wikiquote API

Wikiquote has action API that provides means for getting Wikiquote resources.
For example, you can get content of the Main Page as follows:

$ curl "https://en.wikiquote.org/w/api.php?action=query&prop=revisions&titles=Main%20Page&rvprop=content&format=json"

The result of the above command is:

{"batchcomplete":"","warnings":{"main":{"*":"Subscribe to the mediawiki-api-announce mailing list at <https://lists.wikimedia.org/mailman/listinfo/mediawiki-api-announce> for notice of API deprecations and breaking changes. Use [[Special:ApiFeatureUsage]] to see usage of deprecated features by your application."},"revisions":{"*":"Because \"rvslots\" was not specified, a legacy format has been used for the output. This format is deprecated, and in the future the new format will always be used."}},"query":{"pages":{"1":{"pageid":1,"ns":0,"title":"Main Page","revisions":[{"contentformat":"text/x-wiki","contentmodel":"wikitext","*":"
\n
{{Main page header}}
\n
{{Main Page Quote of the day}}
\n</div>\n\n
\n{{Main Page Selected pages}}\n{{Main categories}}\n
\n\n
\n{{New pages}}\n{{Main Page Community}}\n
\n\n
\n==Wikiquote's sister projects==\n{{otherwiki}}\n\n==Wikiquote languages==\n{{Wikiquotelang}}\n
\n__NOTOC__ __NOEDITSECTION__\n{{noexternallanglinks:ang|simple}}\n[[Category:Main page]]"}]}}}}

WWW

WWW by Zoffix Znet is a library which provides easy-to-use API for fetching and parsing json very simply.
For instance, as the README says, you can easily get content by jget(URL)<HASHKEY> style:

say jget('https://httpbin.org/get?foo=42&bar=x')<args><foo>;

To install WWW:

$ zef install WWW

Chart::Gnuplot

Chart::Gnuplot by titsuki is a bindings for gnuplot.

To install Chart::Gnuplot:

$ zef install Chart::Gnuplot

In this article, we use this module; however, if you unfamiliar with gnuplot there are many alternatives: SVG::Plot, Graphics::PLplot, Call matplotlib functions via Inline::Python.

Stopwords from NLTK

NLTK is a toolkit for natural language processing.
Not only APIs, it also provides corpus.
You can get stopwords for English via “70. Stopwords Corpus”: http://www.nltk.org/nltk_data/

Exercise 1: Get Quotations and Create Cleaned Documents

At the beginning, we have to get quotations from Wikiquote and create clean documents.

The main goal of this section is to create documents according to the following format:

<docid> <personid> <word> <word> <word> ...
<docid> <personid> <word> <word> <word> ...
<docid> <personid> <word> <word> <word> ...

The whole source code is:

use v6.c;
use WWW;
use URI::Escape;

sub get-members-from-category(Str $category --> List) {
    my $member-url = "https://en.wikiquote.org/w/api.php?action=query&list=categorymembers&cmtitle={$category}&cmlimit=100&format=json";
    @(jget($member-url)<query><categorymembers>.map(*<title>));
}

sub get-pages(Str @members, Int $batch = 50 --> List) {
    my Int $start = 0;
    my @pages;
    while $start < @members {
        my $list = @members[$start..^List($start + $batch, +@members).min].map({ uri_escape($_) }).join('%7C');
        my $url = "https://en.wikiquote.org/w/api.php?action=query&prop=revisions&rvprop=content&format=json&formatversion=2&titles={$list}";
        @pages.push($_) for jget($url)<query><pages>.map({ %(body => .<revisions>[0]<content>, title => .<title>) });
        $start += $batch;
    }
    @pages;
}

sub create-documents-from-pages(@pages, @members --> List) {
    my @documents;
    for @pages -> $page {
        my @quotations = $page<body>.split("\n")\
        .map(*.subst(/\[\[$<text>=(<-[\[\]|]>+?)\|$<link>=(<-[\[\]|]>+?)\]\]/, { $<text> }, :g))\
        .map(*.subst(/\[\[$<text>=(<-[\[\]|]>+?)\]\]/, { $<text> }, :g))\
        .map(*.subst("[", "[", :g))\
        .map(*.subst("]", "]", :g))\
        .map(*.subst("&amp;", "&", :g))\
        .map(*.subst("&nbsp;", "", :g))\
        .map(*.subst(/:i [ \<\/?\s?br\> | \<br\s?\/?\> ]/, " ", :g))\
        .grep(/^\*<-[*]>/)\
        .map(*.subst(/^\*\s+/, ""));

        # Note: The order of array wikiquote API returned is agnostic.
        my Int $index = @members.pairs.grep({ .value eq $page<title> }).map(*.key).head;
        @documents.push(%(body => $_, personid => $index)) for @quotations;
    }
    @documents.sort({ $^a<personid> <=> $^b<personid> }).pairs.map({ %(docid => .key, personid => .value<personid>, body => .value<body>) }).list
}

my Str @members = get-members-from-category("Category:1954_births");
my @pages = get-pages(@members);
my @documents = create-documents-from-pages(@pages, @members);

my $docfh = open "documents.txt", :w;
$docfh.say((.<docid>, .<personid>, .<body>).join(" ")) for @documents;
$docfh.close;

my $memfh = open "members.txt", :w;
$memfh.say($_) for @members;
$memfh.close;

First, we get the members listed in the “Category:1954_births” page. I choosed the year that the Perl 6 designer was born in:

my Str @members = get-members-from-category("Category:1954_births");

where get-members-from-category gets members via Wikiquote API:

sub get-members-from-category(Str $category --> List) {
    my $member-url = "https://en.wikiquote.org/w/api.php?action=query&list=categorymembers&cmtitle={$category}&cmlimit=100&format=json";
    @(jget($member-url)<query><categorymembers>.map(*<title>));
}

Next, call get-pages:

my @pages = get-pages(@members);

get-pages is a subroutine that gets pages of the given titles (i.e., members):

sub get-pages(Str @members, Int $batch = 50 --> List) {
    my Int $start = 0;
    my @pages;
    while $start < @members {
        my $list = @members[$start..^List($start + $batch, +@members).min].map({ uri_escape($_) }).join('%7C');
        my $url = "https://en.wikiquote.org/w/api.php?action=query&prop=revisions&rvprop=content&format=json&formatversion=2&titles={$list}";
        @pages.push($_) for jget($url)<query><pages>.map({ %(body => .<revisions>[0]<content>, title => .<title>) });
        $start += $batch;
    }
    @pages;
}

where @members[$start..^List($start + $batch, +@members).min] is a slice of length $batch, and the elements of the slice are percent encoded by uri_escase and joint by %7C (i.e., percent encoded pipe symbol).
In this case, one of the resulting $list is:

Mumia%20Abu-Jamal%7CRene%20Balcer%7CIain%20Banks%7CGerard%20Batten%7CChristie%20Brinkley%7CJames%20Cameron%20%28director%29%7CEugene%20Chadbourne%7CJackie%20Chan%7CChang%20Yu-hern%7CLee%20Child%7CHugo%20Ch%C3%A1vez%7CDon%20Coscarelli%7CElvis%20Costello%7CDaayiee%20Abdullah%7CThomas%20H.%20Davenport%7CGerardine%20DeSanctis%7CAl%20Di%20Meola%7CKevin%20Dockery%20%28author%29%7CJohn%20Doe%20%28musician%29%7CF.%20J.%20Duarte%7CIain%20Duncan%20Smith%7CHerm%20Edwards%7CAbdel%20Fattah%20el-Sisi%7CRob%20Enderle%7CRecep%20Tayyip%20Erdo%C4%9Fan%7CAlejandro%20Pe%C3%B1a%20Esclusa%7CHarvey%20Fierstein%7CCarly%20Fiorina%7CGary%20L.%20Francione%7CAshrita%20Furman%7CMary%20Gaitskill%7CGeorge%20Galloway%7C%C5%BDeljko%20Glasnovi%C4%87%7CGary%20Hamel%7CFran%C3%A7ois%20Hollande%7CKazuo%20Ishiguro%7CJean-Claude%20Juncker%7CAnish%20Kapoor%7CGuy%20Kawasaki%7CRobert%20Francis%20Kennedy%2C%20Jr.%7CLawrence%20M.%20Krauss%7CAnatoly%20Kudryavitsky%7CAnne%20Lamott%7CJoep%20Lange%7CAng%20Lee%7CLi%20Bin%7CRay%20Liotta%7CPeter%20Lipton%7CJames%20D.%20Macdonald%7CKen%20MacLeod

Note that get-pages subroutine uses hash contextualizer %() for creating a sequence of hash:

@pages.push($_) for jget($url)<query><pages>.map({ %(body => .<revisions>[0]<content>, title => .<title>) });

After that, we call create-documents-from-pages:

my @documents = create-documents-from-pages(@pages, @members);

create-documents-from-pages creates documents from each page:

sub create-documents-from-pages(@pages, @members --> List) {
    my @documents;
    for @pages -> $page {
        my @quotations = $page<body>.split("\n")\
        .map(*.subst(/\[\[$<text>=(<-[\[\]|]>+?)\|$<link>=(<-[\[\]|]>+?)\]\]/, { $<text> }, :g))\
        .map(*.subst(/\[\[$<text>=(<-[\[\]|]>+?)\]\]/, { $<text> }, :g))\
        .map(*.subst("[", "[", :g))\
        .map(*.subst("]", "]", :g))\
        .map(*.subst("&amp;", "&", :g))\
        .map(*.subst("&nbsp;", "", :g))\
        .map(*.subst(/:i [ \<\/?\s?br\> | \<br\s?\/?\> ]/, " ", :g))\
        .grep(/^\*<-[*]>/)\
        .map(*.subst(/^\*\s+/, ""));

        # Note: The order of array wikiquote API returned is agnostic.
        my Int $index = @members.pairs.grep({ .value eq $page<title> }).map(*.key).head;
        @documents.push(%(body => $_, personid => $index)) for @quotations;
    }
    @documents.sort({ $^a<personid> <=> $^b<personid> }).pairs.map({ %(docid => .key, personid => .value<personid>, body => .value<body>) }).list
}

where .map(*.subst(/\[\[$<text>=(<-[\[\]|]>+?)\|$<link>=(<-[\[\]|]>+?)\]\]/, { $<text> }, :g)) and .map(*.subst(/\[\[$<text>=(<-[\[\]|]>+?)\]\]/, { $<text> }, :g)) are coverting commands that extract texts for displaying and delete texts for internal linking from anchor texts. For example, [[Perl]] is reduced into Perl. For more syntax info, see: https://docs.perl6.org/language/regexes#Named_captures or https://docs.perl6.org/routine/subst

After some cleaning operations (.e.g., .map(*.subst("[", "[", :g))), we extract quotation lines.
.grep(/^\*<-[*]>/) finds lines starting with single asterisk because most of the quotations appear in such kind of lines.

Next, .map(*.subst(/^\*\s+/, "")) deletes each asterisk since asterisk itself isn’t a constituent of each quotation.

Finally, we save the documents and members (i.e., titles):

my $docfh = open "documents.txt", :w;
$docfh.say((.<docid>, .<personid>, .<body>).join(" ")) for @documents;
$docfh.close;

my $memfh = open "members.txt", :w;
$memfh.say($_) for @members;
$memfh.close;

Exercise 2: Execute LDA and Visualize the Result

In the previous section, we saved the cleaned documents.
In this section, we use the documents for LDA estimation and visualize the result.
The goal of this section is to plot a document-topic distribution and write a topic-word table.

The whole source code is:

use v6.c;
use Algorithm::LDA;
use Algorithm::LDA::Formatter;
use Algorithm::LDA::LDAModel;
use Chart::Gnuplot;
use Chart::Gnuplot::Subset;

sub create-model(@documents --> Algorithm::LDA::LDAModel) {
    my $stopwords = "stopwords/english".IO.lines.Set;
    my &tokenizer = -> $line { $line.words.map(*.lc).grep(-> $w { ($stopwords !(cont) $w) and $w !~~ /^[ <:S> | <:P> ]+$/ }) };
    my ($documents, $vocabs) = Algorithm::LDA::Formatter.from-plain(@documents.map({ my ($, $, *@body) = .words; @body.join(" ") }), &tokenizer);
    my Algorithm::LDA $lda .= new(:$documents, :$vocabs);
    my Algorithm::LDA::LDAModel $model = $lda.fit(:num-topics(10), :num-iterations(500), :seed(2018));
    $model
}

sub plot-topic-distribution($model, @members, @documents, $search-regex = rx/Larry/) {
    my $target-personid = @members.pairs.grep({ .value ~~ $search-regex }).map(*.key).head;
    my $docid = @documents.map({ my ($docid, $personid, *@body) = .words; %(docid => $docid, personid => $personid, body => @body.join(" ")) })\
    .grep({ .<personid> == $target-personid and .<body> ~~ /:i << perl >>/}).map(*<docid>).head;

    note("@documents[$docid] is selected");
    my ($row-size, $col-size) = $model.document-topic-matrix.shape;
    my @doc-topic = gather for ($docid X ^$col-size) -> ($i, $j) { take $model.document-topic-matrix[$i;$j]; }
    my Chart::Gnuplot $gnu .= new(:terminal("png"), :filename("topics.png"));
    $gnu.command("set boxwidth 0.5 relative");
    my AnyTicsTic @tics = @doc-topic.pairs.map({ %(:label(.key), :pos(.key)) });
    $gnu.legend(:off);
    $gnu.xlabel(:label("Topic"));
    $gnu.ylabel(:label("P(z|theta,d)"));
    $gnu.xtics(:tics(@tics));
    $gnu.plot(:vertices(@doc-topic.pairs.map({ @(.key, .value.exp) })), :style("boxes"), :fill("solid"));
    $gnu.dispose;
}

sub write-nbest($model) {
  my $topics := $model.nbest-words-per-topic(10);
  for ^(10/5) -> $part-i {
    say "|" ~ (^5).map(-> $t { "topic { $part-i * 5 + $t }" }).join("|") ~ "|";
    say "|" ~ (^5).map({ "----" }).join("|") ~ "|";
    for ^10 -> $rank {
        say "|" ~ gather for ($part-i * 5)..^($part-i * 5 + 5) -> $topic {
            take @($topics)[$topic;$rank].key;
        }.join("|") ~ "|";
    }
    "".say;
  }
}

sub save-model($model) {
  my @document-topic-matrix := $model.document-topic-matrix;
  my ($document-size, $topic-size) = @document-topic-matrix.shape;
  my $doctopicfh = open "document-topic.txt", :w;

  $doctopicfh.say: ($document-size, $topic-size).join(" ");
  for ^$document-size -> $doc-i {
    $doctopicfh.say: gather for ^$topic-size -> $topic { take @document-topic-matrix[$doc-i;$topic] }.join(" ");
  }
  $doctopicfh.close;

  my @topic-word-matrix := $model.topic-word-matrix;
  my ($, $word-size) = @topic-word-matrix.shape;
  my $topicwordfh = open "topic-word.txt", :w;

  $topicwordfh.say: ($topic-size, $word-size).join(" ");
  for ^$topic-size -> $topic-i {
    $topicwordfh.say: gather for ^$word-size -> $word { take @topic-word-matrix[$topic-i;$word] }.join(" ");
  }
  $topicwordfh.close;

  my @vocabulary := $model.vocabulary;
  my $vocabfh = open "vocabulary.txt", :w;

  $vocabfh.say($_) for @vocabulary;
  $vocabfh.close;
}

my @documents = "documents.txt".IO.lines;
my $model = create-model(@documents);
my @members = "members.txt".IO.lines;
plot-topic-distribution($model, @members, @documents);
write-nbest($model);
save-model($model);

First, we load the cleaned documents and call create-model:

my @documents = "documents.txt".IO.lines;
my $model = create-model(@documents);

create-model creates a LDA model by loading given documents:

sub create-model(@documents --> Algorithm::LDA::LDAModel) {
    my $stopwords = "stopwords/english".IO.lines.Set;
    my &tokenizer = -> $line { $line.words.map(*.lc).grep(-> $w { ($stopwords !(cont) $w) and $w !~~ /^[ <:S> | <:P> ]+$/ }) };
    my ($documents, $vocabs) = Algorithm::LDA::Formatter.from-plain(@documents.map({ my ($, $, *@body) = .words; @body.join(" ") }), &tokenizer);
    my Algorithm::LDA $lda .= new(:$documents, :$vocabs);
    my Algorithm::LDA::LDAModel $model = $lda.fit(:num-topics(10), :num-iterations(500), :seed(2018));
    $model
}

where $stopwords is a set of English stopwords from NLTK (I mentioned preliminary section), and &tokenizer is a custom tokenizer for Algorithm::LDA::Formatter.from-plain. The tokenizer converts given sentence as follows:

Algorithm::LDA::Formatter.from-plain creates numerical native documents (i.e., each word in a document is mapped to its corresponding vocabulary id, and this id is represented by C int32) and vocabulary from a list of texts.

After creating an Algorithm::LDA instance using the above numerical documents, we can start LDA estimation by Algorithm::LDA.fit. In this example, we set the number of topics to 10, and the number of iterations to 100, and the seed for srand to 2018.

Next, we plot a document-topic distribution. Before this plotting, we load the saved members:

my @members = "members.txt".IO.lines;
plot-topic-distribution($model, @members, @documents);

plot-topic-distribution plots topic distribution with Chart::Gnuplot:

sub plot-topic-distribution($model, @members, @documents, $search-regex = rx/Larry/) {
    my $target-personid = @members.pairs.grep({ .value ~~ $search-regex }).map(*.key).head;
    my $docid = @documents.map({ my ($docid, $personid, *@body) = .words; %(docid => $docid, personid => $personid, body => @body.join(" ")) })\
    .grep({ .<personid> == $target-personid and .<body> ~~ /:i << perl >>/}).map(*<docid>).head;

    note("@documents[$docid] is selected");
    my ($row-size, $col-size) = $model.document-topic-matrix.shape;
    my @doc-topic = gather for ($docid X ^$col-size) -> ($i, $j) { take $model.document-topic-matrix[$i;$j]; }
    my Chart::Gnuplot $gnu .= new(:terminal("png"), :filename("topics.png"));
    $gnu.command("set boxwidth 0.5 relative");
    my AnyTicsTic @tics = @doc-topic.pairs.map({ %(:label(.key), :pos(.key)) });
    $gnu.legend(:off);
    $gnu.xlabel(:label("Topic"));
    $gnu.ylabel(:label("P(z|theta,d)"));
    $gnu.xtics(:tics(@tics));
    $gnu.plot(:vertices(@doc-topic.pairs.map({ @(.key, .value.exp) })), :style("boxes"), :fill("solid"));
    $gnu.dispose;
}

In this example, we plot topic distribution of a Larry Wall’s quotation (“Although the Perl Slogan is There’s More Than One Way to Do It, I hesitate to make 10 ways to do something.”):
"Although the Perl Slogan is There's More Than One Way to Do It, I hesitate to make 10 ways to do something."

After the plotting, we call write-nbest:

write-nbest($model);

In LDA, what topic XXX represents is expressed as a list of words. write-nbest writes a markdown style topic-word distribution table:

sub write-nbest($model) {
  my $topics := $model.nbest-words-per-topic(10);
  for ^(10/5) -> $part-i {
    say "|" ~ (^5).map(-> $t { "topic { $part-i * 5 + $t }" }).join("|") ~ "|";
    say "|" ~ (^5).map({ "----" }).join("|") ~ "|";
    for ^10 -> $rank {
        say "|" ~ gather for ($part-i * 5)..^($part-i * 5 + 5) -> $topic {
            take @($topics)[$topic;$rank].key;
        }.join("|") ~ "|";
    }
    "".say;
  }
}

The result is:

topic 0 topic 1 topic 2 topic 3 topic 4
would scotland black could one
it’s country mr. first work
believe one lot law new
one political play college human
took world official basic process
much need new speak business
don’t must reacher language becomes
ever national five every good
far many car matter world
fighting us road right knowledge
topic 5 topic 6 topic 7 topic 8 topic 9
apple united people like */
likely war would one die
company states i’m something und
jobs years know think quantum
even would think way play
steve american want things noble
life president get perl home
like human going long dog
end must say always student
small us go really ist

As you can see, the quotation of “Although the Perl Slogan is There’s More Than One Way to Do It, I hesitate to make 10 ways to do something.” contains “one”, “way” and “perl”. This is the reason why this quotation is mainly composed of topic 8.

For the next section, we save the model by save-model subroutine:

sub save-model($model) {
  my @document-topic-matrix := $model.document-topic-matrix;
  my ($document-size, $topic-size) = @document-topic-matrix.shape;
  my $doctopicfh = open "document-topic.txt", :w;

  $doctopicfh.say: ($document-size, $topic-size).join(" ");
  for ^$document-size -> $doc-i {
    $doctopicfh.say: gather for ^$topic-size -> $topic { take @document-topic-matrix[$doc-i;$topic] }.join(" ");
  }
  $doctopicfh.close;

  my @topic-word-matrix := $model.topic-word-matrix;
  my ($, $word-size) = @topic-word-matrix.shape;
  my $topicwordfh = open "topic-word.txt", :w;

  $topicwordfh.say: ($topic-size, $word-size).join(" ");
  for ^$topic-size -> $topic-i {
    $topicwordfh.say: gather for ^$word-size -> $word { take @topic-word-matrix[$topic-i;$word] }.join(" ");
  }
  $topicwordfh.close;

  my @vocabulary := $model.vocabulary;
  my $vocabfh = open "vocabulary.txt", :w;

  $vocabfh.say($_) for @vocabulary;
  $vocabfh.close;
}

Exercise 3: Create Quotation Search Engine

In this section, we create a quotation search engine which uses the model created in the previous section.
More specifically, we create LDA-based document model (Xing Wei and W. Bruce Croft 2006) and make a CLI tool that can search quotations. (Note that the words “token” and “word” are interchangable in this section)

The whole source code is:

use v6.c;

sub MAIN(Str :$query!) {
    my \doc-topic-iter = "document-topic.txt".IO.lines.iterator;
    my \topic-word-iter = "topic-word.txt".IO.lines.iterator;
    my ($document-size, $topic-size) = doc-topic-iter.pull-one.words;
    my ($, $word-size) = topic-word-iter.pull-one.words;

    my Num @document-topic[$document-size;$topic-size];
    my Num @topic-word[$topic-size;$word-size];

    for ^$document-size -> $doc-i {
        my \maybe-line := doc-topic-iter.pull-one;
        die "Error: Something went wrong" if maybe-line =:= IterationEnd;
        my Num @line = @(maybe-line).words>>.Num;
        for ^@line {
            @document-topic[$doc-i;$_] = @line[$_];
        }
    }

    for ^$topic-size -> $topic-i {
        my \maybe-line := topic-word-iter.pull-one;
        die "Error: Something went wrong" if maybe-line =:= IterationEnd;
        my Num @line = @(maybe-line).words>>.Num;
        for ^@line {
            @topic-word[$topic-i;$_] = @line[$_];
        }
    }

    my %vocabulary = "vocabulary.txt".IO.lines.pairs>>.antipair.hash;
    my @members = "members.txt".IO.lines;
    my @documents = "documents.txt".IO.lines;
    my @docbodies = @documents.map({ my ($, $, *@body) = .words; @body.join(" ") });
    my %doc-to-person = @documents.map({ my ($docid, $personid, $) = .words; %($docid => $personid) }).hash;
    my @query = $query.words.map(*.lc);

    my @sorted-list = gather for ^$document-size -> $doc-i {
        my Num $log-prob = gather for @query -> $token {
            my Num $log-ml-prob = Pml(@docbodies, $doc-i, $token);
            my Num $log-lda-prob = Plda($token, $topic-size, $doc-i, %vocabulary, @document-topic, @topic-word);
            take log-sum(log(0.2) + $log-ml-prob, log(0.8) + $log-lda-prob);
        }.sum;
        take %(doc-i => $doc-i, log-prob => $log-prob);
    }.sort({ $^b<log-prob> <=> $^a<log-prob> });

    for ^10 {
        my $docid = @sorted-list[$_]<doc-i>;
        sprintf("\"%s\" by %s %f", @docbodies[$docid], @members[%doc-to-person{$docid}], @sorted-list[$_]<log-prob>).say;
    }

}

sub Pml(@docbodies, $doc-i, $token --> Num) {
    my Int $num-tokens = @docbodies[$doc-i].words.grep({ /:i^ $token $/ }).elems;
    my Int $total-tokens = @docbodies[$doc-i].words.elems;
    return -100e0 if $total-tokens == 0 or $num-tokens == 0;
    log($num-tokens) - log($total-tokens);
}

sub Plda($token, $topic-size, $doc-i, %vocabulary is raw, @document-topic is raw, @topic-word is raw --> Num) {
    gather for ^$topic-size -> $topic {
        if %vocabulary{$token}:exists {
            take @document-topic[$doc-i;$topic] + @topic-word[$topic;%vocabulary{$token}];
        } else {
            take -100e0;
        }
    }.reduce(&log-sum);
}

sub log-sum(Num $log-a, Num $log-b --> Num) {
    if $log-a < $log-b {
        return $log-b + log(1 + exp($log-a - $log-b))
    } else {
        return $log-a + log(1 + exp($log-b - $log-a))
    }
}

At the beginning, we load the saved model and prepare @document-topic, @topic-word, %vocabulary, @documents, @docbodies, %doc-to-person and @members:

    my \doc-topic-iter = "document-topic.txt".IO.lines.iterator;
    my \topic-word-iter = "topic-word.txt".IO.lines.iterator;
    my ($document-size, $topic-size) = doc-topic-iter.pull-one.words;
    my ($, $word-size) = topic-word-iter.pull-one.words;

    my Num @document-topic[$document-size;$topic-size];
    my Num @topic-word[$topic-size;$word-size];

    for ^$document-size -> $doc-i {
        my \maybe-line = doc-topic-iter.pull-one;
        die "Error: Something went wrong" if maybe-line =:= IterationEnd;
        my Num @line = @(maybe-line).words>>.Num;
        for ^@line {
            @document-topic[$doc-i;$_] = @line[$_];
        }
    }

    for ^$topic-size -> $topic-i {
        my \maybe-line = topic-word-iter.pull-one;
        die "Error: Something went wrong" if maybe-line =:= IterationEnd;
        my Num @line = @(maybe-line).words>>.Num;
        for ^@line {
            @topic-word[$topic-i;$_] = @line[$_];
        }
    }

    my %vocabulary = "vocabulary.txt".IO.lines.pairs>>.antipair.hash;
    my @members = "members.txt".IO.lines;
    my @documents = "documents.txt".IO.lines;
    my @docbodies = @documents.map({ my ($, $, *@body) = .words; @body.join(" ") });
    my %doc-to-person = @documents.map({ my ($docid, $personid, $) = .words; %($docid => $personid) }).hash;

Next, we set @query using option :$query:

my @query = $query.words.map(*.lc);

After that, we compute the probability of P(query|document) based on Eq. 9 of the aforementioned paper (Note that we use logarithm to avoid undeflow and set the parameter mu to zero) and sort them.

    my @sorted-list = gather for ^$document-size -> $doc-i {
        my Num $log-prob = gather for @query -> $token {
            my Num $log-ml-prob = Pml(@docbodies, $doc-i, $token);
            my Num $log-lda-prob = Plda($token, $topic-size, $doc-i, %vocabulary, @document-topic, @topic-word);
            take log-sum(log(0.2) + $log-ml-prob, log(0.8) + $log-lda-prob);
        }.sum;
        take %(doc-i => $doc-i, log-prob => $log-prob);
    }.sort({ $^b<log-prob> <=> $^a<log-prob> });

Plda adds logarithmic topic given document probability (i.e., lnP(topic|theta,document)) and word given topic probability (i.e., lnP(word|phi,topic)) for each topic, and sums them by .reduce(&log-sum);:

sub Plda($token, $topic-size, $doc-i, %vocabulary is raw, @document-topic is raw, @topic-word is raw --> Num) {
    gather for ^$topic-size -> $topic {
        if %vocabulary{$token}:exists {
            take @document-topic[$doc-i;$topic] + @topic-word[$topic;%vocabulary{$token}];
        } else {
            take -100e0;
        }
    }.reduce(&log-sum);
}

and Pml (ml means Maximum Likelihood) counts $token and normalizes it by the number of the total tokens in the document (Note that this computation is also conducted in log space):

sub Pml(@docbodies, $doc-i, $token --> Num) {
    my Int $num-tokens = @docbodies[$doc-i].words.grep({ /:i^ $token $/ }).elems;
    my Int $total-tokens = @docbodies[$doc-i].words.elems;
    return -100e0 if $total-tokens == 0 or $num-tokens == 0;
    log($num-tokens) - log($total-tokens);
}

OK, then let’s execute!

query “perl”:

$ perl6 search-quotation.p6 --query="perl"
"Perl will always provide the null." by Larry Wall -3.301156
"Perl programming is an *empirical* science!" by Larry Wall -3.345189
"The whole intent of Perl 5's module system was to encourage the growth of Perl culture rather than the Perl core." by Larry Wall -3.490238
"I dunno, I dream in Perl sometimes..." by Larry Wall -3.491790
"At many levels, Perl is a 'diagonal' language." by Larry Wall -3.575779
"Almost nothing in Perl serves a single purpose." by Larry Wall -3.589218
"Perl has a long tradition of working around compilers." by Larry Wall -3.674111
"As for whether Perl 6 will replace Perl 5, yeah, probably, in about 40 years or so." by Larry Wall -3.684454
"Well, I think Perl should run faster than C." by Larry Wall -3.771155
"It's certainly easy to calculate the average attendance for Perl conferences." by Larry Wall -3.864075

query “apple”:

$ perl6 search-quotation.p6 --query="apple"
"Steve Jobs is the"With phones moving to technologies such as Apple Pay, an unwillingness to assure security could create a Target-like exposure that wipes Apple out of the market." by Rob Enderle -3.841538
"*:From Joint Apple / HP press release dated 1 January 2004 available [http://www.apple.com/pr/library/2004/jan/08hp.html here]." by Carly Fiorina -3.904489
"Samsung did to Apple what Apple did to Microsoft, skewering its devoted users and reputation, only better. ... There is a way for Apple to fight back, but the company no longer has that skill, and apparently doesn't know where to get it, either." by Rob Enderle -3.940359
"[W]hen it came to the iWatch, also a name that Apple didn't own, Apple walked away from it and instead launched the Apple Watch. Certainly, no risk of litigation, but the product's sales are a fraction of what they otherwise might have been with the proper name and branding." by Rob Enderle -4.152145
"[W]hen Apple wanted the name "iPhone" and it was owned by Cisco, Steve Jobs just took it, and his legal team executed so he could keep it. It turned out that doing this was surprisingly inexpensive. And, as the Apple Watch showcased, the Apple Phone likely would not have sold anywhere near as well as the iPhone." by Rob Enderle -4.187223
"The cause of [Apple v. Qualcomm] appears to be an effort by Apple to pressure Qualcomm into providing a unique discount, largely because Apple has run into an innovation wall, is under increased competition from firms like Samsung, and has moved to a massive cost reduction strategy. (I've never known this to end well, as it causes suppliers to create unreliable components and outright fail.)" by Rob Enderle -4.318575
"Apple tends to aggressively work to not discover problems with products that are shipped and certainly not talk about them." by Rob Enderle -4.380863
"Apple no longer owns the tablet market, and will likely lose dominance this year or next. ... this level of sustained dominance doesn't appear to recur with the same vendor even if it launched the category." by Rob Enderle -4.397954
"Apple is becoming more and more like a typical tech firm — that is, long on technology and short on magic. ... Apple is drifting closer and closer to where it was back in the 1990s. It offers advancements that largely follow those made by others years earlier, product proliferation, a preference for more over simple elegance, and waning excitement." by Rob Enderle -4.448473
"[T]he litigation between Qualcomm and Apple/Intel ... is weird. What makes it weird is that Intel appears to think that by helping Apple drive down Qualcomm prices, it will gain an advantage, but since its only value is as a lower cost, lower performing, alternative to Qualcomm's modems, the result would be more aggressively priced better alternatives to Intel's offerings from Qualcomm/Broadcom, wiping Intel out of the market. On paper, this is a lose/lose for Intel and even for Apple. The lower prices would flow to Apple competitors as well, lowering the price of competing phones. So, Apple would not get a lasting benefit either." by Rob Enderle -4.469852 Ronald McDonald of Apple, he is the face." by Rob Enderle -3.822949
"With phones moving to technologies such as Apple Pay, an unwillingness to assure security could create a Target-like exposure that wipes Apple out of the market." by Rob Enderle -3.849055
"*:From Joint Apple / HP press release dated 1 January 2004 available [http://www.apple.com/pr/library/2004/jan/08hp.html here]." by Carly Fiorina -3.895163
"Samsung did to Apple what Apple did to Microsoft, skewering its devoted users and reputation, only better. ... There is a way for Apple to fight back, but the company no longer has that skill, and apparently doesn't know where to get it, either." by Rob Enderle -4.052616
"*** The previous line contains the naughty word '$&'.\n if /(ibm|apple|awk)/; # :-)" by Larry Wall -4.088445
"The cause of [Apple v. Qualcomm] appears to be an effort by Apple to pressure Qualcomm into providing a unique discount, largely because Apple has run into an innovation wall, is under increased competition from firms like Samsung, and has moved to a massive cost reduction strategy. (I've never known this to end well, as it causes suppliers to create unreliable components and outright fail.)" by Rob Enderle -4.169533
"[T]he litigation between Qualcomm and Apple/Intel ... is weird. What makes it weird is that Intel appears to think that by helping Apple drive down Qualcomm prices, it will gain an advantage, but since its only value is as a lower cost, lower performing, alternative to Qualcomm's modems, the result would be more aggressively priced better alternatives to Intel's offerings from Qualcomm/Broadcom, wiping Intel out of the market. On paper, this is a lose/lose for Intel and even for Apple. The lower prices would flow to Apple competitors as well, lowering the price of competing phones. So, Apple would not get a lasting benefit either." by Rob Enderle -4.197869
"Apple tends to aggressively work to not discover problems with products that are shipped and certainly not talk about them." by Rob Enderle -4.204618
"Today's tech companies aren't built to last, as Apple's recent earnings report shows all too well." by Rob Enderle -4.209901
"[W]hen it came to the iWatch, also a name that Apple didn't own, Apple walked away from it and instead launched the Apple Watch. Certainly, no risk of litigation, but the product's sales are a fraction of what they otherwise might have been with the proper name and branding." by Rob Enderle -4.238582

Conclusions

In this article, we explored Wikiquote and created a LDA model using Algoritm::LDA.
After that we built an information retrieval application.

Thanks for reading my article! See you next time!

Citations

License

Perl 6 Inside Out: 🎄 24/25. Reading files with $*ARGFILES in Perl 6

Published by andrewshitov on 2018-12-23T23:01:38

Welcome to Day 24 of the Perl 6 One-Liner Advent Calendar!

In the previous days, we were reading text files, so it would be logical to talk about $*ARGFILES, a built-in dynamic variable that may be handy when working with multiple input files.

How do you read two or more files passed in the command-line?

$ perl6 work.pl a.txt b.txt

If you need to process all the files together as if they would be a single data source, you could ask our today’s variable to do the job in a one-liner:

.say for $*ARGFILES.lines

Inside the program, you don’t have to think about looping over the files; $*ARGFILES will automatically do that for you.

If there are no files in the command line, the variable will be attached to STDIN:

$ cat a.txt b.txt | perl6 work.pl 

Handy indeed, isn’t it?

6.d and MAIN

I also have to warn you if you will want to use it in bigger programs. Consider the following program:

sub MAIN(*@files) {
.say for $*ARGFILES.lines;
}

In Perl 6.d, $*ARGFILES works differently inside the MAIN subroutine and outside of it.

This program will perfectly work with Perl 6.c, but not under Perl 6.d. In other words, in Rakudo Star up to and including version 2018.10, $*ARGFILES handles filenames in the command line, but starting with Rakudo Star 2018.12, it will be always connected to $*IN if it is used inside MAIN.

And that’s the end of today’s advent post and almost the end of the whole calendar of this year. Nevertheless, come again tomorrow!

Perl 6 Advent Calendar: Day 23 – Blin, it’s Christmas soon!

Published by AlexDaniel on 2018-12-23T00:00:15

I’ve already mentioned Bisectable in one of the advent posts two years ago, but since then a lot has changed, so I think it’s time to give a brief history of the bisectable bot and its friends.

First of all, let’s define the problem that is being solved. Sometimes it happens that a commit introduces an unintended change in behavior (a bug). Usually we call that a regression, and in some cases the easiest way to figure out what went wrong and fix it is to first find which commit introduced the regression.

There are exactly 9000 commits between Rakudo 2015.12 and 2018.12, and even though it’s not over 9000, that’s still a lot.


Luckily, we don’t need to test all of the revisions. Assuming that the behavior wasn’t changing back and forth all the time, we can use binary search.

git bisect and binary search

Basically, given any commit range, we take a commit in the “middle” of the range and test it. If it’s “bad” or if it shows the “new” (now incorrect) behavior, then we can throw away the second half of our range (because we know that the change must have happened before that commit or exactly on that commit). Similarly we throw away the other half if it is “good” (or “old”). So instead of testing all 9000 commits we can just check about log n revisions (≈13).

Git comes with git bisect command which implements the binary search logic for you. All you have to do is give it some starting points and then for every commit it jumps to, tell if it is good/bad. If you do that enough times, it’ll tell you which commit is at fault.

That’s all good, but there are two problems with it.

Problem ❶: Skipping

Let’s imagine a situation where 2 + 2 used to return 4 (correct!), but now returns 42 (… also right, but not quite).

So you kick off the bisection process, git jumps between revisions, you test them. If it’s 4 then it’s good (or old), if it’s 42 then it is bad (or new). But then you stumble upon this behavior:

> 2 + 2

Merry Christmas!

… Now what? Clearly that specific revision is somewhat special. We can’t tell if our bug is present or not, we simply can’t know. Yes, it doesn’t print 4, but we are looking for a very specific bug, so it doesn’t classify as “new” behavior either. Of course, we can toss a coin and mark it randomly as old or new, and hope for a Christmas miracle… but that has a 50% probability (if we see only one of these) to divert the binary search into the wrong direction.

For these cases git provides a special skip command.

If you are testing manually, then it is somewhat straightforward to handle these revisions (as long as you remember that you should skip them). However, because of problem ❷, a lot of people are tempted to use git bisect run which automates the process with a script. It is possible to skip revisions using a script too (use exit code 125), but it is not that obvious how to figure out which revisions should be skipped.

Problem ❷: Build times

Let’s take the optimistic figure of 13 to estimate the amount of revisions that we are going to test. Remember that it doesn’t include commits that we will have to skip, and possibly other extra builds that we might want to test.

The amount of time it takes to build rakudo varies depending on the hardware, but let’s optimistically say that it takes us 2 minutes to build rakudo on a particular commit and test it.

13 × 2 = 26 (minutes)

That’s not very convenient, right? And if something goes wrong during the process… you start over, and then you wait.

Bisectable

In 2016, after seeing the pain of those who have to run git bisect manually (actually, mostly myself), I wondered:

<AlexDaniel> has anybody thought about building rakudo for every single commit, so that you can quickly run git bisect?

The cost-benefit analysis of the idea was promptly questioned:

<perlpilot> AlexDaniel: do you believe that bisects will be common in the future?

To which I provided a very detailed justification:

<AlexDaniel> perlpilot: yes

Three days later, the bot joined the channel. The reactions were quite interesting to see:

<moritz> woah
<tadzik> wow
<RabidGravy> OoOOOoooh
<llfourn> Cooooool

Little did we know back then. Even I had no idea how useful it will turn out. Fast forward 2 years:

<lizmat> with regards to size of commits: I try to keep them as small and contained as possible, to allow for easier bisecting
<lizmat> in that sense, bisectable6 has changed the way I code
<lizmat> also: bisectable6 has made me worry less about changes I commit
<lizmat> because it usually limits the places to look for fixing an issue so much, that they can be fixed within minutes rather than hours
<lizmat> or at least show the cause very quickly (so the short-time fix may mean a revert)
<AlexDaniel> \o/

But it wasn’t always perfect. About one hour after the introduction of the bot, it was used for its purpose:

<moritz> bisect: try { NaN.Rat == NaN; exit 0 }; exit 1
<bisectable> moritz: (2016-05-02) https://github.com/rakudo/rakudo/commit/949a7c7

However, because of an off-by-one, it returned the wrong commit. The actual commit was e2f1fa7, and 949a7c7 is its parent.

Honestly, the bot was very bad back then. For example, it fully relied on the exit code, so you couldn’t just throw 2 + 2 into it and expect it to check the output. Eventually, different modes were implemented, and nowadays the bot first checks the behavior on the starting points (e.g. 2015.12 and HEAD), and determines the best strategy to perform the bisection. For example, if the signal is different (e.g. a SEGV), then it bisects based on the signal. If the signal is same, but the exit code is different, then it uses the exit code. If all else can’t be used, it bisects using the output.

Keep in mind that bisectable checks for you if perl6 binary can’t be built. This means that in most cases you don’t need to add your own logic for skipping. Not only it brought the bisection time from tens of minutes to a few seconds, it also gives results that are more reliable/correct.

Storage

Some time later the commit range was expanded to 2014.01HEAD, meaning all commits starting from the first ever Rakudo on Moar release. Currently it has over 17000 builds. It may sound like a lot, but with every rakudo installation taking just ≈28 MB, that’s not too much. Having a few TB of storage should get you going for a few years to come.

That being said, I don’t have that luxury on my server. It has a RAID of 120 GB SSDs, so the whole thing not only has to fit into that little amount of space, but it should also leave enough space for the rest of the system.

There was a lot of experimentation (one, two) involved in figuring out the best strategy to save space, but long story short, we can go as low as about half a megabyte per build! Of course, it is always a tradeoff between the compression ratio and decompression speed, but using modern compression algorithms (zstd, lrzip) everything is relatively easy.

More bots, more better

Shortly after Bisectable was released, people saw an opportunity for other tools. Want to run some code on a specific commit? Sure, here’s a bot for that. Want to download a prebuilt rakudo archive instead of wasting your own cpu time? Yes, there’s another bot. Want to graph some info about rakudo? Of course there’s a bot for that!

And it continued until we reached the total of 17 bots! Some argue that these bots should stop multiplying like that, and perhaps people are right. But I guess the point is that now it is extremely easy to build upon Whateverable to create more tools for developers, which is of course great.

OK, now what?

So bisectable can bisect across thousands of commits in no time. It consumes very little storage space, and it doesn’t require full understanding of the bisection process from the user. Now that the bisection is free and easy, can we do more?

Yes, Blin!

You may have heard about Toaster. Toaster is a tool that attempts to install every module in the ecosystem on two or more revisions. For example, let’s say that the last release was 2018.12 and the release manager is about to cut a rakudo release from master HEAD. You can then run toaster on 2018.12 and master, and it will show which modules used to install cleanly but no longer do.

That gives us the information that something is likely wrong in Rakudo, but doesn’t tell what exactly. Given that this post was mostly about Bisectable, you can probably guess where this is going.

Project Blin – Toasting Reinvented

Blin is a quality assurance tool for Rakudo releases. It is used to find regressions in rakudo, but unlike Toaster, not only it tells which modules are no longer installable, it also bisects rakudo to find out which commit caused the issue. Of course, it is built around Whateverable, so that extra functionality doesn’t cost much (and doesn’t even require a lot of code). As a bonus, it generates nice graphs to visualize how the issue propagates from module dependencies (though that is not very common).

One important feature of Blin is that it tries to install every module just once. So if module B depends on module A, A will be tested and installed once, and then reused for the testing of B. Because this process is parallelized, you may wonder how it was implemented. Basically, it uses the underrated react/whenever feature:

# slightly simplified
react {
    for @modules -> $module {
        whenever Promise.allof($module.depends.keys».done) {
            start { process-module $module, … }
        }
    }
}

For every module (we have more than 1200 now) it creates its own whenever block which fires when its dependencies are satisfied. In my opinion, that’s the whole implementation of the main logic in Blin, everything else is just glue to get Whateverable and Zef working together to achieve what we need, + some output generation.

In some way, Blin didn’t change much in the way we do quality assurance for Rakudo. Toaster was already able to give us some basic info (albeit slower) so that we could start the investigation, and in the past I was known for shoving weird things (e.g. full modules with dependencies) into bisectable. It’s just that now it is much easier, and when The Day comes, I won’t be punished for robot abuse.

Future

Whateverable and Blin together have 243 open issues. Both projects work great and are very useful, but as we say, they are Less Than Awesome. Most issues are relatively easy and fun to work with, but they require time. If there’s anything you can help with or if you want to maintain these projects, please feel free to do so. And if you want to build your own tools based on Whateverable (which we probably need a lot!), see this hello world gist.

🎅🎄, 🥞

Perl 6 Inside Out: 🎄 23/25. Calculating totals with Perl 6

Published by andrewshitov on 2018-12-22T23:01:54

Welcome to Day 23 of the Perl 6 One-Liner Advent Calendar! End of the year is the time when people evaluate there year results, and Perl 6 can help with that, too.

Today, we’ll see a one-liner that calculates totals for the columns of a table.

Here’s some sample data in a file:

100.20  303.50 150.25
130.44 1505.12 36.41
200.12 305.60 78.12

And here’s the code that prints three numbers—totals for each column:

put [Z+] lines.map: *.words

The program prints the numbers that we need:

430.76 2114.22 264.78

From the update of yesterday’s post, we know that bare lines is the same as $*IN.lines, so lines.map iterates over all the lines in the input stream. Each line is then split into words—substrings separated by whitespaces.

The part of the job that parses input data is complete. We have got a number of sequences corresponding to the lines of input data. For our sample file, these are the following:

(("100.20", "303.50", "150.25").Seq, ("130.44", "1505.12", "36.41").Seq, ("200.12", "305.60", "78.12").Seq).Seq

Now, add up every first element, every second element, etc. The combination of the reduction operator and the zip meta-operators does all the work with only four characters of code: [Z+].

At this point, we have a reduced sequence:

(430.76, 2114.22, 264.78).Seq

The last trivial step is to print the values using the put routine. If you did the homework yesterday, you would know that say uses the gist method (which adds parentheses around a sequence) to visualise the result, while put simply prints the values using the Str method.

An addition

Let us add a few more characters to the script to demonstrate how you can skip the first column that, for example, contains month names:

Jan 100.20  303.50 150.25
Feb 130.44 1505.12 36.41
Mar 200.12 305.60 78.12

All you need is to make a slice and select all columns except the first one:

put 'Total ', [Z+] lines.map: *.words[1..*]

As you see, we even don’t need to count columns ourselves. The 1..* range can make that job.

And that’s the end of today’s advent post, so come again tomorrow!

Perl 6 Advent Calendar: Day 22 – Testing Cro HTTP APIs

Published by jnthnwrthngtn on 2018-12-22T00:00:06

A good amount of my work time this year has been spent on building a couple of Perl 6 applications. After a decade of contributing to Perl 6 compiler and runtime development, it feels great to finally be using it to deliver production solutions solving real-world problems. I’m still not sure whether writing code in an IDE I founded, using a HTTP library I designed, compiled by a compiler I implemented large parts of, and running on a VM that I play architect for, makes me one of the world’s worst cases of “Not Invented Here”, or just really Full Stack.

Whatever I’m working on, I highly value automated testing. Each passing test is something I know works – and something that I won’t break as I evolve the software in question. Even with automated tests, bugs happen, but adding a test to cover the bug at least means I’ll make different bugs in the future, which is perhaps a bit more forgivable.

Most of the code, and complexity, in the system I’m currently working on is in its domain objects. Those are reached through a HTTP API, implemented using Cro – and like the rest of the system, this HTTP API has automated tests. They use one old module of mine – Test::Mock – along with a new module released this year, Cro::HTTP::Test. In today’s advent post, I’ll discuss how I’ve been using them together, with results that I find quite pleasing.

A sample problem

It’s the advent calendar, so of course I need a sufficiently festive example problem. For me, one of the highlights of Christmas time in Central Europe is the Christmas markets, many set on beautiful historic city squares. And what, aside from sausage and mulled wine, do we need on that square? A tall, handsome Christmas tree, of course! But how to find the best tree? Well, we get the internet to help, by building a system where they can submit suggestions of trees they’ve seen that might be suitable. What could possibly go wrong?

One can PUT to a route /trees/{latitude}/{longitude} to submit a candidate tree at that location. The expected payload is a JSON blob with a tree height, and a text description of 10-200 characters explaining why the tree is so awesome. If a tree in the same location has already been submitted, a 409 Conflict response should be returned. If the tree is accepted, then a simple 200 OK response will be produced, with a JSON body describing the tree.

A GET of the same URI will return a description of the tree in question, while a GET to /trees will return the submitted trees, tallest first.

Testability

Back in highschool, science classes were certainly among my favorite. Now and then, we got to do experiments. Of course, each experiment needed writing up – both the planning before, the results, and an analysis of them. One of the most important parts of the planning was about how to ensure a “fair test”: how would we try control all of the things we weren’t trying to test, so that we could trust in our observations and draw conclusions from them?

Testing in software involves much the same thought process: how do we exercise the component(s) we’re interested in, while controlling the context they operate in? Sometimes, we get lucky, and we’re testing pure logic: it doesn’t depend on anything other than the things we give it to work with. In fact, we can create our own luck in this regard, spotting parts of our system that can be pure functions or immutable objects. To take examples from the current system I’m working on:

So, the first thing to do for testability is to find the bits of the system that can be like this and build them that way. Alas, not all things are so simple. HTTP APIs are often a gateway to mutable state, database operations, and so forth. Further, a good HTTP API will map error conditions from the domain level into appropriate HTTP status codes. We’d like to be able to create such situations in our tests, so as to cover them. This is where a tool like Test::Mock comes in – but to use it, we need to factor our Cro service in a way that is test-friendly.

Stubbing a service

For those new to Cro, let’s take a look at the bare minimum we can write to get a HTTP service up and running, serving some fake data about trees.

use Cro::HTTP::Router;
use Cro::HTTP::Server;

my $application = route {
    get -> 'trees' {
        content 'application/json', [
            {
                longitude => 50.4311548,
                latitude => 14.586079,
                height => 4.2,
                description => 'Nice color, very bushy'
            },
            {
                longitude => 50.5466504,
                latitude => 14.8438714,
                height => 7.8,
                description => 'Really tall and wide'
            },
        ]
    }
}

my $server = Cro::HTTP::Server.new(:port(10000), :$application);
$server.start;
react whenever signal(SIGINT) {
    $server.stop;
    exit;
}

This isn’t a great setup for being able to test our routes, however. Better would be to put the routes into a subroutine in a module lib/BestTree.pm6:

unit module BestTree;
use Cro::HTTP::Router;

sub routes() is export {
    route {
        get -> 'trees' {
            content 'application/json', [
                {
                    longitude => 50.4311548,
                    latitude => 14.586079,
                    height => 4.2,
                    description => 'Nice color, very bushy'
                },
                {
                    longitude => 50.5466504,
                    latitude => 14.8438714,
                    height => 7.8,
                    description => 'Really tall and wide'
                },
            ]
        }
    }
}

And use it from the script:

use BestTree;
use Cro::HTTP::Server;

my $application = routes();
my $server = Cro::HTTP::Server.new(:port(10000), :$application);
$server.start;
react whenever signal(SIGINT) {
    $server.stop;
    exit;
}

Now, if we had something that could be used to test that route blocks do the right thing, we could use this module, and get on with our testing.

Stores, models, etc.

There’s another problem, however. Our Christmas tree service will be stashing the tree information away in some database, as well as enforcing the various rules. Where should this logic go?

There’s many ways we might choose to arrange this code, but the key thing is that this logic does not belong in our Cro route handlers. Their job is to map between the domain objects and the world of HTTP, for example turning domain exceptions into appropriate HTTP error responses. That mapping is what we’ll want to test.

So, before we continue, let’s define how some of those things look. We’ll have a BestTree::Tree class that represents a tree:

class BestTree::Tree {
    has Rat $.latitude;
    has Rat $.longitude;
    has Rat $.height;
    has Str $.description;
}

And we’ll work with a BestTree::Store object. We won’t actually implement this as part of this post; it will be what we fake in our tests.

class BestTree::Store {
    method all-trees() { ... }
    method suggest-tree(BestTree::Tree $tree --> Nil) { ... }
    method find-tree(Rat $latitude, Rat $longitude --> BestTree::Tree) { ... }
}

But how can we arrange things so we can take control of the store that is used by the routes, for testing purposes? One easy way is to make it a parameter to our routes subroutine, meaning it will be available in the route block:

sub routes(BestTree::Store $store) is export {
    ...
}

This is a functional factoring. Some folks may prefer to use some kind of OO-based Dependency Injection, using some kind of container. That can work fine with Cro too: just have a method that returns the route block. (If building something non-tiny with Cro, check out the documentation on structuring services for some further advice on this front.)

Getting a list of trees

Now we’re ready to start writing tests! Let’s stub the test file:

use BestTree;
use BestTree::Store;
use Cro::HTTP::Test;
use Test::Mock;
use Test;

# Tests will go here

done-testing;

We use BestTree, which contains the routes we want to test, along with:

Next, we’ll make a couple of tree objects to use in our tests:

my $fake-tree-a = BestTree::Tree.new:
        latitude => 50.4311548,
        longitude => 14.586079,
        height => 4.2,
        description => 'Nice color, very bushy';
my $fake-tree-b = BestTree::Tree.new:
        latitude => 50.5466504,
        longitude => 14.8438714,
        height => 7.8,
        description => 'Really tall and wide';

And here comes the first test:

subtest 'Get all trees' => {
    my $fake-store = mocked BestTree::Store, returning => {
        all-trees => [$fake-tree-a, $fake-tree-b]
    };
    test-service routes($fake-store), {
        test get('/trees'),
                status => 200,
                json => [
                    {
                        latitude => 50.4311548,
                        longitude => 14.586079,
                        height => 4.2,
                        description => 'Nice color, very bushy'
                    },
                    {
                        latitude => 50.5466504,
                        longitude => 14.8438714,
                        height => 7.8,
                        description => 'Really tall and wide'
                    }
                ];
        check-mock $fake-store,
                *.called('all-trees', times => 1, with => \());
    }
}

First, we make a fake of BestTree::Store that, whenever all-trees is called, will return the fake data we specify. We then use test-service, passing in the route block created with the fake store. All test calls within the block that follows will be executed against that route block.

Notice that we don’t need to worry about running a HTTP server here to host the routes we want to test. In fact, due to the pipeline architecture of Cro, it’s easily possible for us to take the Cro HTTP client, wire its TCP message output to put the data it would send into a Perl 6 Channel, and then have that data pushed into the server pipeline’s TCP message input pipeline, and vice versa. This means that we test things all the way down to the bytes that are sent and received, but without actually having to hit even the local network stack. (Aside: you can also use Cro::HTTP::Test with a URI, which means if you really wanted to spin up a test server, or even wanted to write tests against some other service running in a different process, you could do it.)

The test routine specifies a test case. Its first argument describes the request that we wish to perform – in this case, a get to /trees. The named arguments then specify how the response should look. The status check ensures we get the expected HTTP status code back. The json check is really two in one:

If that’s all we did, and we ran our tests, we’d find they mysteriously pass, even though we didn’t yet edit our route block’s get handler to actually use the store! Why? Because it turns out I was lazy and used the data from my earlier little server example as my test data here. No worries, though: to make the test stronger, we can add a call to check-mock, and then assert that our fake store really did have the all-trees method called once, and with no arguments passed.

That just leaves us to make the test pass, by implementing the handler properly:

get -> 'trees' {
    content 'application/json', [
        $store.all-trees.map: -> $tree {
            {
                latitude => $tree.latitude,
                longitude => $tree.longitude,
                height => $tree.height,
                description => $tree.description
            }
        }
    ]
}

Getting a tree

Time for the next test: getting a tree. There are two cases to consider here: the one where the tree is found, and the one where the tree is not found. Here’s a test for the case where a tree is found:

subtest 'Get a tree that exists' => {
    my $fake-store = mocked BestTree::Store, returning => {
        find-tree => $fake-tree-b
    };
    test-service routes($fake-store), {
        test get('/trees/50.5466504/14.8438714'),
                status => 200,
                json => {
                    latitude => 50.5466504,
                    longitude => 14.8438714,
                    height => 7.8,
                    description => 'Really tall and wide'
                };
        check-mock $fake-store,
                *.called('find-tree', times => 1, with => \(50.5466504, 14.8438714));
    }
}

Running this now fails. In fact, the status code check fails first, because we didn’t implement the route yet, and so get 404 back, not the expected 200. So, here’s an implementation to make it pass:

        get -> 'trees', Rat() $latitude, Rat() $longitude {
            given $store.find-tree($latitude, $longitude) -> $tree {
                content 'application/json', {
                    latitude => $tree.latitude,
                    longitude => $tree.longitude,
                    height => $tree.height,
                    description => $tree.description
                }
            }
        }

Part of this looks somewhat familiar from the other route, no? So, with two passing tests, let’s go forth and refactor:

get -> 'trees' {
    content 'application/json',
            [$store.all-trees.map(&tree-for-json)];
}

get -> 'trees', Rat() $latitude, Rat() $longitude {
    given $store.find-tree($latitude, $longitude) -> $tree {
        content 'application/json', tree-for-json($tree);
    }
}

sub tree-for-json(BestTree::Tree $tree --> Hash) {
    return {
        latitude => $tree.latitude,
        longitude => $tree.longitude,
        height => $tree.height,
        description => $tree.description
    }
}

And the tests pass, and we know our refactor is good. But wait, what about if there is no tree there? In that case, the store will return Nil. We’d like to map that into a 404. Here’s another test:

subtest 'Get a tree that does not exist' => {
    my $fake-store = mocked BestTree::Store, returning => {
        find-tree => Nil
    };
    test-service routes($fake-store), {
        test get('/trees/50.5466504/14.8438714'),
                status => 404;
        check-mock $fake-store,
                *.called('find-tree', times => 1, with => \(50.5466504, 14.8438714));
    }
}

Which fails, in fact, with a 500 error, since we didn’t consider that case in our route block. Happily, this one is easy to deal with: turn out given into a with, which checks we got a defined object, and then add an else and produce the 404 Not Found response.

get -> 'trees', Rat() $latitude, Rat() $longitude {
    with $store.find-tree($latitude, $longitude) -> $tree {
        content 'application/json', tree-for-json($tree);
    }
    else {
        not-found;
    }
}

Submitting a tree

Last but not least, let’s test the route for suggesting a new tree. Here’s the successful case:

subtest 'Suggest a tree successfully' => {
    my $fake-store = mocked BestTree::Store;
    test-service routes($fake-store), {
        my %body = description => 'Awesome tree', height => 4.25;
        test put('/trees/50.5466504/14.8438714', json => %body),
                status => 200,
                json => {
                    latitude => 50.5466504,
                    longitude => 14.8438714,
                    height => 4.25,
                    description => 'Awesome tree'
                };
        check-mock $fake-store,
                *.called('suggest-tree', times => 1, with => :(
                    BestTree::Tree $tree where {
                        .latitude == 50.5466504 &&
                        .longitude == 14.8438714 &&
                        .height == 4.25 &&
                        .description eq 'Awesome tree'
                    }
                ));
    }
}

This is mostly familiar, except the check-mock call looks a little different this time. Test::Mock lets us test the arguments in two different ways: with a Capture (as we’ve done so far) or with a Signature. The Capture case is great for all of the simple cases, where we’re just dealing with boring values. However, once we get in to reference types, or if we don’t actually care about exact values and just want to assert the things we care about, a signature gives us the flexibility to do that. Here, we use a where clause to check that the tree object that the route handler has constructed contains the expected data.

Here’s the route handler that does just that:

put -> 'trees', Rat() $latitude, Rat() $longitude {
    request-body -> (Rat(Real) :$height!, Str :$description!) {
        my $tree = BestTree::Tree.new: :$latitude, :$longitude,
                :$height, :$description;
        $store.suggest-tree($tree);
        content 'application/json', tree-for-json($tree);
    }
}

Notice how Cro lets us use Perl 6 signatures to destructure the request body. In one line, we’ve said:

Should any of those fail, Cro will automatically produce a 400 bad request for us. In fact, we can write tests to cover that – along with a new test to make sure a conflict will result in a 409.

subtest 'Problems suggesting a tree' => {
    my $fake-store = mocked BestTree::Store, computing => {
        suggest-tree => {
            die X::BestTree::Store::AlreadySuggested.new;
        }
    }
    test-service routes($fake-store), {
        # Missing or bad data.
        test put('/trees/50.5466504/14.8438714', json => {}),
                status => 400;
        my %bad-body = description => 'ok';
        test put('/trees/50.5466504/14.8438714', json => %bad-body),
                status => 400;
        %bad-body<height> = 'grinch';
        test put('/trees/50.5466504/14.8438714', json => %bad-body),
                status => 400;

        # Conflict.
        my %body = description => 'Awesome tree', height => 4.25;
        test put('/trees/50.5466504/14.8438714', json => %body),
                status => 409;
    }
}

The main new thing here is that we’re using computing instead of returning with mocked. In this case, we pass a block, and it will be executed. (The block does not get the method arguments, however. If we want to get those, there is a third option, overriding, where we get to take the arguments and write a fake method body.)

And how to handle this? By making our route handler catch and map the typed exception:

put -> 'trees', Rat() $latitude, Rat() $longitude {
    request-body -> (Rat(Real) :$height!, Str :$description!) {
        my $tree = BestTree::Tree.new: :$latitude, :$longitude,
                :$height, :$description;
        $store.suggest-tree($tree);
        content 'application/json', tree-for-json($tree);
        CATCH {
            when X::BestTree::Store::AlreadySuggested {
                conflict;
            }
        }
    }
}

Closing thoughts

With Cro::HTTP::Test, there’s now a nice way to write HTTP tests in Perl 6. Put together with a testable design, and perhaps a module like Test::Mock, we can also isolate our Cro route handlers from everything else, easing their testing.

The logic in our route handlers here is relatively straightforward; small sample problems usually are. Even here, however, I find there’s value in the journey, rather than only in the destination. The act of writing tests for a HTTP API puts me in the frame of mind of whoever will be calling the API, which can be a useful perspective to have. Experience also tells that tests “too simple to fail” do end up catching mistakes: the kinds of mistakes I might assume I’m too smart to make. Discipline goes a long way. On which note, I’ll now be disciplined about taking a break from the keyboard now and then, and go enjoy a Christmas market. -Ofun!

Perl 6 Inside Out: 🎄 22/25. Reversing a file with Perl 6

Published by andrewshitov on 2018-12-21T23:01:45

Welcome to Day 22 of the Perl 6 One-Liner Advent Calendar! Today, we will continue working with files, and the goal for today is to create a one-liner to print the lines of a text file in reversed order (as tail -r does it).

The first one-liner does the job with the STDIN stream:

.say for $*IN.lines.reverse

Run the program as:

$ perl6 reverse.pl < text.txt

Update. Thanks to the reader comment, we can gain from the fact that $*IN can be omitted in this case, which makes the one-liner even shorter:

.say for lines.reverse

If you want to read the files directly from Perl 6, modify the program a bit to create a file handle out of the command-line argument:

.say for @*ARGS[0].IO.open.lines.reverse

Now you run it as follows:

$ perl6 reverse.pl text.txt

It is important to remember that the default behaviour of the lines method is to exclude the newline characters from the final sequence of lines (the method returns a Seq object, not an array or a list). It may be opposite to what you are used to when working with Perl 5. Using chomp is quite a common practice there.

In Perl 6, the lines method splits the lines based on the value stored in the .nl-in attribute of the IO::Handle object.

You can look at the current value of the line separators with the following tiny script:

dd $_ for @*ARGS[0].IO.open.nl-in

This is what you find there by default:

$["\n", "\r\n"]

The interesting thing is that you can control the behaviour of lines and tell Perl not to exclude the newline characters:

@*ARGS[0].IO.open(chomp => False).lines.reverse.put

The chomp attribute is set to True by default. You can also change the default separator:

@*ARGS[0].IO.open(
  nl-in => "\r", chomp => False
).lines.reverse.put

Notice that without chomping, you do not need an explicit for loop over the lines: in the last two one-liners, the .put method is called directly on the sequence object. In the earlier versions, the strings did not contain the newline characters, and thus they would be printed as a single long line.

I will leave you today with some small homework: Tell the difference between put and say.

Till tomorrow!

Perl 6 Advent Calendar: Day 21 – A Red Secret Santa

Published by SmokeMachine on 2018-12-20T23:01:49

The year is ending and we have a lot to celebrate! What is a better way to celebrate the end of the year than with our family and friends? To help achieve that, here at my home, we decided to run a Secret Santa Game! So, my goal is to write a Secret Santa Program! That’s something where I can use this wonderful project called Red.

Red is an ORM (Object Relational Model) for perl6 still under development and not published as a module yet. But it’s growing and it is close to a release.

So let’s create our first table: a table that will store the people participating in our Secret Santa. To the code:

Red maps relational databases to OOP. Each table is mapped to a Red class (model), each of whose objects represents a row.

The way we a create a model is by using the model special word. A model is just a normal class that extends Red::Model and has a MetamodelX::Red::Model‘s object as its metaclassRed does not add any methods you didn’t explicitly create to its models. So to interact with the database you should use the metaclass.

But let’s continue.

The code creates a new model called Person. The name of the table this model represents will be the same name as the model: “Person”. If necessary, you can change the name of the table with the is table<...> trait (for example: model Person is table<another_name> {...}).

This model has 3 attributes:

Red uses not null columns by default, so if you want to create a nullable columns you should use is column{ :nullable }.

So all attributes on Person are columns. The is serial (I mean the :id part) means that it’s the table’s primary key.

After that it’s setting a dynamic variable ($*RED-DB) for the result of database "SQLite". The database sub receives the driver‘s name and the parameters it expects.

In this case it uses the SQLite driver and if you don’t pass any argument, it will use it as an in memory database. If you want to use a file named secret-santa.db as the database file, you can do database "SQLite", :database<secret-santa.db>. Or, if you want to use a local Postgres, just use  database "Pg"Red uses the variable $*RED-DB to know what database to use.

OK, now lets create the table! As I said before, Red did not add any methods you didn’t explicitly ask for. So, to create the table a metaclassmethod is used. Person.^create-table is how you create the table.

This will run:

Now we should insert some data. We do that with another meta method (.^create). The .^create meta method expects the same arguments .new expects. Each named argument will set an attribute with the same name. .^create will create a new Person object, save it in the database (with .^save: :insert), and return it.

It runs:

Every model has a ResultSeq. That is a sequence that represents every row on the table. We can get its ResultSeq with .^all (or .^rs). ResultSeq has some methods to help you to get information from the table, for example: .grep will filter the rows (as it does in a normal Seq) but it doesn’t do that in memory, it returns a new ResultSeq with that filter set. When its iterator is retrieved, it runs a SQL query using everything set on the ResultSeq.

In our example, Person.^all.grep(*.email.defined).map: *.name will run a query like:

And it’ll print:

Fernando
Aline

Okay, we have a code that can save who is entered in our Secret Santa game. But each one on it want different gifts. How can we know the wishes of each one?

Let’s modify the code to make it save the wishlist for everyone participating in the secret santa:

That prints:

Fernando
    Comma => https://commaide.com
    perl6 books => https://perl6book.com
    mac book pro => https://www.apple.com/shop/buy-mac/macbook-pro/15-inch-space-gray-2.6ghz-6-core-512gb#

Aline
    a new closet => https://i.pinimg.com/474x/02/05/93/020593b34c205792a6a7fd7191333fc6--wardrobe-behind-bed-false-wall-wardrobe.jpg

Fernanda
    mimikyu plush => https://www.pokemoncenter.com/mimikyu-poké-plush-%28standard-size%29---10-701-02831
    camelia plush => https://farm9.static.flickr.com/8432/28947786492_80056225f3_b.jpg

Sophia
    baby alive => https://www.target.com/p/baby-alive-face-paint-fairy-brunette/-/A-51304817

Now we have a new model Wishlist that refers to a table named wishlist. It has $!id as id$!name and $!link are columns, and there are some things new! has UInt $!wisher-id is referencing{ Person.id }; is the same as has UInt $!wisher-id is column{ :references{ Person.id } }; that means it’s a column that’s a foreign key that references the id Person‘s column. It also has a has Person $.wisher is relationship{ .wisher-id }; it’s not a column, it’s a “virtual” field. the $ sigil means that there is only 1 wisher for a wish. And is relationship expects a Callable that will receive a model. If it’s Scalar it will receive the current model as the only argument. So, in this case, it will be Wishlist. The return of the relationsip’s Callable must be a column that references some other column.

Lets see how this table is created:

As you can see, no wisher column is created.

The Person model has changed too! Now it has a @.wishes relationship (has Wishlist @.wishes is relationship{ .wisher-id }). It uses a @ sigil so each Person can have more than one wish. The Callable passed will receive the type of the Positional attribute (Wishlist on this case) and must return a column that references some other column.

The table created is the same as before.

We created a new Person as we did before: my \fernando = Person.^create: :name<Fernando>, :email<fco@aco.com>; and now we can use the relationship (wishes) to create a new wish (fernando.wishes.create: :name<Comma>, :link<https://commaide.com&gt;). That creates a new wish for Fernando running the following SQL:

Had you seen? wisher_id is 1… 1 is Fernando’s id. Once you have created the wish from Fernando’s .wishes(), it already knows that it belongs to Fernando.

And then we define wishes for every person we create.

Then we loop over every Person in the database (Person.^all) and print its name and loop over that person’s wishes and print its name and link.

Okey, we can save who is participating… get what they want… but the draw? Who should I give a gift to? To do that we change our program again:

Now Person has two new attributes ($!pair-id and $.pair) and a new method (draw). $!pair-id is a foreign key that references the field id on the same table (Person) so we have to use an alias (.^alias). The other one is the relationship ($.pair) that uses that foreign key.

The new method (draw) is where the magic happens. It uses the method .pick: * that on a normal Positional would shuffle the list. And it does the same here, with the query:

Once we have the shuffled list, we use .rotor to get two items and go one back, so we save what is the pair of each person giving to the next person, and the last person in the list will give to the first person.

And this is the output of our final code:

Fernando -> Sophia
Wishlist: baby alive
Aline -> Fernanda
Wishlist: mimikyu plush, camelia plush
Fernanda -> Fernando
Wishlist: COMMA, perl6 books, mac book pro
Sophia -> Aline
Wishlist: a new closet

As a bonus, let’s check out the track Red is going to follow. This is a current working code:

And this is the SQL it runs:

And prints:

Fernando => fco@aco.com
Aline => aja@aco.com
Fernanda
Sophia

Weekly changes in and around Perl 6: 2018.51 Principally Designed

Published by liztormato on 2018-12-17T16:44:45

Ralph Mellor started an interesting discussion about the principles people have adopted for the design of their programming language. Recommended reading. And he initiated an at least equally interesting discussion on /r/ProgrammingLanguages about Jonathan Worthington‘s article titled: Racing to writeness to wrongness leads. As if there wasn’t already good stuff to read in this time of year!

Tis the Time of Year

Another batch of regular Advent posts:

And another batch of one-liner Advent posts by Andrew Shitov:

Improve Perl 6 Networking Support

Ben Davies has submitted a request for a grant to improve the networking support of Perl 6. Comments welcome!

last / LAST on whenever

A feature sometimes felt sorely missed: Timo Paulssen implemented the last statement (and the LAST phaser) on whenever blocks. This now gives a more idiomatic way to get out of the implicit loop in a whenever block.

Byte-oriented read/write methods

Using the nqp:: functions that Stefan Seifert has implemented using Jonathan Worthington’s design from a few months ago, Elizabeth Mattijsen has implemented the associated functions in Perl 6:
blob8.read-int8/16/32/64/128 for reading signed integers, blob8.read-uint8/16/32/64/128 for reading unsigned integers and blob8.read-num32/64 for reading IEEE floating point values (full documentation).

And of course there are also counterparts for writing: buf8.write-int8/16/32/64/128 for writing signed integers, buf8.write-uint8/16/32/64/128 for writing unsigned integers, and buf8.write-num32/64 for writing IEEE floating point values (full documentation).

All of these methods take a byte offset as the first parameter, and an optional endianness parameter for the last parameter. To indicate endianness, the Endian enum has been created: it has three possible values: NativeEndian (the endianness of the system Perl 6 is running on), LittleEndian and BigEndian. The default for the last parameter is NativeEndian. The write-... methods take a second parameter as the value to set.

Finally, the Kernel class now has a endian class method that indicates the endianness of the system on which Perl 6 is executing.

Other Core Developments

Questions about Perl 6

Meanwhile on Twitter

Meanwhile on Facebook

Perl 6 in comments

Perl 6 Modules

New Modules:

Updated Modules:

Winding Down

With lots of nice stuff to read, yours truly hopes you will have time enough to prepare for the holiday season.

In the coming weeks, the Perl 6 Weekly will most likely already be published on Sunday night (CET) rather than on Monday: publishing in the evening of the 24th and the 31st of December is not only in conflict with the schedule of yours truly, but probably also with most of the readers of the Perl 6 Weekly.

Jo Christian Oterhals: Perl 6 small stuff #14: Regexes and guesses (name extraction)

Published by Jo Christian Oterhals on 2018-12-07T19:13:42

In my last post I explained what I do for a living, and gave an example of the ad hoc stuff I use Perl 6 for at work. Here’s another example.

The script shown here utilizes the following concepts from earlier articles:

“I love nynorsk”. Wikimedia Commons.

But first, some background info. Norway is a small country where most people speak the same language (there are difference in dialects of course, but the language is the same). But as crazy as it may sound… this single spoken language has two written languages. Yes, you read that right: You speak Norwegian but you write either Bokmål or Nynorsk — loosely translated to “Book language” and “New Norwegian”. I won’t go into the historical reasons for this — if you’re interested I recommend the Wikipedia article about it. Suffice it to say that these two versions of written Norwegian are very similar, but different enough for it to be noticeable.

Some news outlets use Nynorsk, while the majority use Bokmål. A consequence of this is that there is significantly more content for Bokmål readers than there is for Nynorsk readers. That’s the reason why my workplace is trying to get software to translate Bokmål to Nynorsk.

The translator works well enough, but now and then there are mishaps. Many of them are caused by the translator misinterpreting names. We’ve got dictionaries with names so they should be easy to identify. But they’re not easy to identify if the name’s among the lesser used ones. When the dictionary fails us, we can try using rules/regexes to identify them. But even then we’re not always able to decide whether a word’s a regular word or a name.

Let’s take a look at the name Fuglesang (i.e. the astronaut). Fuglesang is a name, but it’s also a noun meaning bird’s song or chirp. As stated above, it’s no problem identifying Fuglesang as a name, using a regex or by using a dictionary of names, if it occurs mid-sentence. The regex looks for words starting with a capital letter, and can — potentially — signal to the translator that the word’s probably a name. But if the word occurs at the start of a sentence — where all words are capitalized — Fuglesang becomes ambiguous again, even if that name occurs in the dictionary of names. The removal of this ambiguity is important, because if not, the name could be translated as if it was any other word. In my case, with ambiquity, Fuglesang could potentially be translated into “fuglesong”, which would be correct if it is a noun but wrong if it is a proper noun.

So the questing is: What is Fuglesang? A name or bird song?

Obviously, this is a case where the translation software needs help. I thought about it a while, and decided that maybe we could develop a simple algorithm to help us along. I wrote a script that do one simple thing: It parses a text and finds every capitalized word that occurs mid-sentence. Then it extracts the first word of any sentence and checks whether that word occurs in the list of mid-sentence words. If it does, then we assume that — within the particular context of that single text — the word can be considered a name.

In addition there was one more thing I had to take care of. Possessives. In English, possessives are relatively easy to spot. The possessives are added to the noun with an apostrophe and an s. When comparing two sentences, “Peter owns a car” and “This is Peter’s car”, a simple Str.subst("'s", "") will remove the possessive in the latter sentence. Now Peter, as in Peter’s, can be compared for equality with the Peter in the first sentence.

But in Norway possessives are simply trailing s-es without the apostrophe — “Peter eier en bil” vs “Peters bil” — so the solution isn’t quite as simple. But all in all, this too was a fairly simple task to solve using Perl 6.

The resulting script may be short and simple, but it sure is useful. In any case, I though I’d share the script here anyway. It showcases quite a few of the concepts I’ve been discussing earlier in this series of articles. I’ll delve further into the details further down, but first — the code.

#!/usr/bin/env perl6
my $text = prep-text(slurp);
my regex sentence-begin {
^^ | \– <space> + | \n <space> *
}
my regex probably-name {
<upper> <alnum> +
}
my regex sentence-delimiter {
<[ \n \. \: \? \! \– \- ]> ' ' *
}
my regex strip-characters {
<[ \» \« ]>
}
my @in-sentence = ( $text ~~   m:g/
<<
( <!after <sentence-begin> > )
( <probably-name> )
>>
/
).map( *.Str ).unique.sort;
my @begin-sentence = ( $text ~~ m:g/
<<
( <after <sentence-begin> > )
( <probably-name> )
>>
/
).map( *.Str ).unique.sort;
my @probably-names = @in-sentence.grep( -> $a { 
@begin-sentence.grep( -> $b { is-equal($a, $b) } )
} );
say @probably-names.unique.join("\n");
sub is-equal($a is copy, $b is copy) {
$a ~~ s/s$//; # Possessives
$b ~~ s/s$//;
return $a eq $b;
}
sub prep-text($t is copy) {
$t ~~ s:g/ <strip-characters> //;
return $t.split( / <sentence-delimiter> /).join(".\n");
}

The code starts with a slurp . Slurp gobbles up an entire file instead of line by line. It works on any file handle or implicitly on stdin. In this case I receive the file trough stdin. The slurped text is passed on to the prep-text subroutine. That routine strips away a few characters that’s just noise in this context. I might add more characters to this in the future, that’s why I’ve put them into a named regex. Additionally, the routine removes a custom group of punctuation characters and replace them with “. “ (dot + space). Perl 6 has the character class <punct> built-in, but that includes characters I want to preserve. That’s I’ve created my own named regex, <sentence-delimiter> that defines a custom group of punctuations.

The second thing prep-text does is to reformat the text so that every sentence is placed on a line by itself. Doing this makes the rest of the parsing easier.

After the text prep, I declare a few more named regexes as well. I could have written all this stuff into the regexes I use further down, but then I’d repeat the same regex. Instead I split the repeated parts of the regexes into named regexe. Not only does that prevent repetition, it improves readability as well.

The @in-sentence array is a list of capitalized words that is not the first word of a sentence. The assumption on my part is that most words in this list are names (Norwegian doesn’t use capitalization much, usually only for proper nouns, so the assumption is likely to be correct most of the time). The regex returns a list of Match objects. Since I’ll have to compare strings later on, I use the map method to convert the Match objects into strings. Finally I run unique.sort on the list. Unique makes sure we only get one representation of each capitalized word. As for the sort, I could have made do without it. But I like my output to be alphabetized. It’s just a preference thing.

The @begin-sentence array is also a list of capitalized words, but in this case only capitalized words that appears as the first word of a sentence. All words in the start of a sentence, whether they’re names or not (they probably aren’t), are capitalized. So here we can’t be sure of anything.

That’s where the third array comes into play. Here I make us of grep and anonymous functions to keep all names in the @in-sentence array that also appear in the @begin-sentence array. What I’m left with is a list of words that are capitalized both within and in the start of sentences. In these cases, there’s a good chance that those words are names.

That’s does almost everything I set out to achieve. But I do one more thing. The innermost anonymous function calls a subroutine named is-equal . I could have done a simple $a eq $b insted to find equality. But since names can have possessives (“Peter’s car” which in Norwegian is written “Peters bil”), I have to take an extra step before checking for equality.

So when word A and word B is sent to is-equal I use a simple regex to remove the last s in the words, if one or both of them has one. Then I compare the two stripped words and check equality of those two instead.

What we end up with is a list of words that occurs in start of sentences, that likely are names. A job well done if I may say so myself.

Last but not least the parameters of the sub routines use the is copy function. Normally parameters are immutable and not possible to change or manipulate within the sub. But sometimes you want to do that anyway. One way to this is to declare new variables within the sub sand assign them with the value of the parameters. I.e. my $inner-a = $a; . Instead I use is copy, that makes the parameters mutable. Some may think this is bad form, but to me it’s just shorthand. Probably I’m just “lazy”.

So… the chance is that this is a scenario you’ll never stumble upon, so why should you care about this code?

Well, I think it’s a showcase of how different Perl 6 regexes are compared to good old perlre. They’re not different for difference’s sake, but are really readable. In addition they have a few functions that perlre don’t. Named regexes are central to this. They make the main regexes short and easy to read.

In addition I like the double grep I use to create the @probably-names array. The use of anonymous functions helped me avoid nested for loops. It’s not that I have anything against them, it’s just that this way is shorter and more succinct. I also have a small hope that using Perl 6 built-ins are faster as well, although speed’s not really an issue in this case.

As for anonymous functions, I’m happy that I found a use for them. I mentioned them in the very first article I wrote about Perl 6. At the time I wasn’t sure whether they were useful or just something to impress your friends with. The folk singer Woody Guthrie once said that “anyone who uses more than two chords are just showing off”. I thought anonymous functions maybe were the Perl 6 equivalent of Woody’s 3+ chords. I’m happy to report that they’re not. They are useful in and of themselves.

And that’s it. Not only have I learned a little more about Perl 6 in the months I’ve been writing these articles, programming Perl 6 is getting more fun to. Hopefully you experience the same as me.

Jo Christian Oterhals: Perl 6 small stuff #13: Did you mean X?

Published by Jo Christian Oterhals on 2018-11-13T20:41:19

Given that I a while back wrote an article suggesting that Perl 6 should change its name to Century, you’d probably expect me to have an opinion about the Raku debacle. Well, I don’t. For me, I think the time has come to share something else than interesting peculiarities of Perl 6, namely real code I use in my work.

Too soon?

I work as a kind of Jack-of-all-trades at a Norwegian media company, mostly wrangling numbers. Now and then I need to program a few ad hoc scripts to help extract interesting data from various databases, web pages, etc. Some of these end up in production, deployed in the cloud. But a surprising amount of what I do is to write ad hoc code solving a one-time specific problem. Code that is neither particularly optimised nor especially robust, given that it will be used once and never leave my MacBook.

What follows is one example of the latter.

One day I noticed that quite a few of the searches our clients made in one of our databases returned zero results. It was easy to see that many of them were caused by incorrect spelling [1]. Wanting to investigate this a little further, I pulled six months worth of queries from our log database. Since this was not meant as anything but an experiment, I reduced the amount of that by removing multi-word queries, and keeping only one-word queries that contained alphabetic characters. I also normalized the words, i.e. I dropped accented versions of characters. That reduced the dataset to a manageable size. I stored the resulting dataset in a simple CSV file.

File: st2.csv (containing 726,609 queries; a subset shown here)
Gaza,94279,editorial
Kaulitz,1667,editorial
senkvald,0,editorial
senkveld,1608,editorial
plenklipper,0,editorial

The first column is the word that was searched for, the second column contained the number of results (the third is irrelevant for the discussion here).

Looking at this data I started wondering whether I could make qualified guesses as to what words the misspellers actually thought they wrote. In short: Could I create data that could form the basis of a Google-like “Did you mean X” feature?

I knew that I could use the Levenshtein-Damerau algorithm (among others) to compare one word to another and figure out how similar they were. But it seemed like overkill to compare each word to all the words in, say, a dictionary. A program doing that would take forever to run.

But: If you look at the example CSV above you see that the word “senkvald” has zero results while “senkveld” has 1608 results. That made me realize that for each mis-spelled query there’d likely be a correctly spelled query that returned results. I could limit the comparisons to queries with results.

What I needed was a program that created a list of mis-spelled zero-hit words and a list of words with hits; just that optimisation alone would speed things up. In addition I thought that the speed would increase even further if I utilized Perl 6 parallelisation stuff.

Now, bring out your torches and pitchforks, because I’m sure you’ll see lots of stuff to improve and optimize here. But in this case it’s a little beside the point, because some of the stuff I’ve done here is done because it’s simple to do and easy to read, and not because it’s the fastest way to do these things [2].

#!/usr/bin/env perl6
use v6.c;
use Text::Levenshtein::Damerau;
my %term;
my %alphabet-hits;
my %alphabet-zero-hits;
my @results;
my @promises;
my @zero-hit;
my @non-zero-hit;
my $PARALLELS = 4;
my $MAX-DISTANCE = 0.3;
my $MIN-COMP-LENGTH = 4;
my $MAX-COMPARISONS = 1_000_000;
constant @ALPHABET = (("a".."z"), (<æ ø å>)).flat;
$*ERR.out-buffer = 0;
$*OUT.out-buffer = 0;
read-words;
similarity;
sort-and-spurt;
sub read-words {
my $file = open "st2.csv";
for $file.lines -> $line {
my @elms = $line.split(",");
%term{lc(@elms[0])} += @elms[1];
}
$file.close;
note "Read search queries.";
for (%term.keys) -> $t {
@zero-hit.push($t) if %term{$t} == 0;
@non-zero-hit.push($t) if %term{$t} > 0;
}
@zero-hit = @zero-hit.grep(
{ $_.chars >= $MIN-COMP-LENGTH } ).sort;
@non-zero-hit = @non-zero-hit.grep(
{ $_.chars >= $MIN-COMP-LENGTH } ).sort;
note "Processed " ~ %term.keys.elems ~ " terms.";
for (@ALPHABET) -> $char {
%alphabet-hits{$char} =
(@non-zero-hit.grep( { $_.starts-with($char) } ));
%alphabet-zero-hits{$char} =
(@zero-hit.grep( { $_.starts-with($char) } ));
$max-no-comparisons +=
%alphabet-hits{$char}.elems *
%alphabet-zero-hits{$char}.elems;
}
note "Split dictionaries into alphabetized chunks.";
}
sub sort-and-spurt {
for (@results.sort) -> $o {
my ($a, $b) = $o.split(',');
my $near-equal =
($a.split('').unique.sort cmp $b.split('').unique.sort
== Same ?? '*' !! '');
say "$o,$near-equal";
}
note "Sorted and output finished.";
}
sub similarity {
my $processed-comparisons = 0;
my $zero-chunk-size = (@ALPHABET.elems / $PARALLELS).Int;
my @alphabet-copy = @ALPHABET;
for 1..$PARALLELS -> $t {
$zero-chunk-size++ if
($t == $PARALLELS && $zero-chunk-size < @alphabet-copy.elems);
my @alpha-chunk = @alphabet-copy.splice(0, $zero-chunk-size);
push @promises, start compare(@alpha-chunk, $t);
}
note "Finished waiting: " ~ await Promise.allof(@promises);
  sub compare(@alphabet-subset, $parallel-no) {
note "Parallel $parallel-no: " ~ @alphabet-subset.elems;
for (@alphabet-subset) -> $start-char {
for ((%alphabet-zero-hits{$start-char}).flat) -> $z {
for ((%alphabet-hits{$start-char}).flat) -> $nz {
my $distance = dld($z, $nz);
my $fraction = $z.chars > $nz.chars ??
$distance / $z.chars !! $distance / $nz.chars;
if $fraction < $MAX-DISTANCE {
@results.push: $z ~ "," ~ $nz ~ "," ~ $fraction;
}
note "Compared $processed-comparisons of " ~
"$max-no-comparisons."
if $processed-comparisons %% 10_000;
return False if ++$processed-comparisons > $MAX-COMPARISONS;
}
}
}
}
}

This script did the job! I got a list of around 17.000 suggestions that could be useful for implementing a “Did you mean X” type of routine. But what was unexpectedly more useful, and more immediately useful at that, is that we could use it internally to improve how we tagged our content. Instead of improving things automatically, it first and foremost improves manual work.

Anyway, back to the interesting stuff (at least to me) this uncovered about Perl 6:

  1. I used the keyword note a lot; note is like say, only that it outputs to STDERR. A little like warn in Perl 5. I could direct the output of the program to a file, while still being able to see the debug/error info.
  2. Output is often buffered. Most of the time I want it not to be. I want to see the results immediately, so I used this: $*OUT.out-buffer = 0; — This is equivalent to Perl 5’s $|++, except that the Perl 6 version is unexpectedly verbose but at the same time self-explanatory.
  3. constant @ALPHABET = ((“a”..”z”), (<æ ø å>)).flat; —as I had normalized all of the keywords and only kept keywords with Norwegian alphabetic characters, I had to generate a list of norwegian characters. I couldn’t use a range, i.e. “a”..”å”, as that would contain all kinds of characters. So I combined two lists, the range “a”..”z” and the list <æ ø å>, into one by using the .flat method.
  4. my @alpha-chunk = @alphabet-copy.splice(0, $zero-chunk-size); — I must have used this in other variants before, but splice felt like a new discovery. Splice is kind of like a super pop. It removes and returns not only a single element, but an entire chunk of an array. In other words, the original array is shortened accordingly, while you can assign the removed elements to a new array. This was useful for splitting the array into pieces I could use when parallelising the comparison task.
  5. And parallelisation is dead simple! All I needed was the start keyword. I did this: push @promises, start compare(@alpha-chunk, $t); — the subroutine compare is parallelised by the start keyword. You don’t need the push, but you should: The @promises array contains all the, well, promises. The note “Finished waiting: “ ~ await Promise.allof(@promises); ensures that all the parallels had finished running before moving on. That was all there was to it! The $PARALLELS variable manages how many parallels you want to run. I chose 4 as that’s the number of cores in my MacBook’s processor.
  6. A sub within a sub: Since the compare sub was a subroutine that was only to be used by the similarity sub, I used Perl 6’s ability to have a sub within a sub. So the compare sub is only visible from within compare. I probably did this only to impress myself.
  7. The similarity calculation my $distance = dld($z, $nz); my $fraction = $z.chars > $nz.chars ?? $distance / $z.chars !! $distance / $nz.chars; is a combination of Levenshtein-Damerau and my own stuff. The L-D algorithm — simplified — compares two string and tries to calculate how many substitutions you need in word 2 for it to be similar to word 1 (think of how many keyboard presses you’d need). You’ll get an integer with the number of substitutions as result. But two substitutions in a short word is more significant than in a long word. So I try to create a factor based on the number of substitutions divided by the length of the longest of the two words. This factor will be a floating point number between 0 and 1. The lower the number, the more similar the words are.
  8. In the line my $near-equal =
    ($a.split(‘’).unique.sort cmp $b.split(‘’).unique.sort
    == Same ?? ‘*’ !! ‘’); I reduce each word to a sorted array of the unique characters in each words. I.e. ABBA is reduced to the array <A B>, but so is BABA. My assumption was that similar words containing the identical characters are more similar than the other matches, even though the difference may be larger. I.e. ABBA and BABA is more similar than ABBA and ABDA — <A B> and <A B D>. But I discovered that if you compare two arrays for similarity, i.e. whether their elements contain the same values in the same order, the comparison return Same. In Perl 5 you get 0 as a result. In Perl 6 you can choose to check for 0 as well as Same and both will work. But I have to say Same is more self explanatory.

So it’s safe to say that I learned a lot by programming this. It was equally nice that the results were useful!

NOTES
[1]
Of course quite a few of the zero-hit searches was caused by the fact that we didn’t have matching content, but those were beyond my scope.

[2] But I probably should have been more concerned with speed. Even though I’ve said earlier that speed depends on your point of view, slow is slow. Even with the parallelisation, this script used almost five hours before it was finished. It may be faster in the latest version of Rakudo; for this I used Rakudo Start 2018.06.

POSTSCRIPT
I had to do it, didn’t I? Since I’m flirting with two ladies at the moment, both Camelia and Julia, I couldn’t resist implementing the same thing in Julia version 1.0.0.

One thing I didn’t expect: Although Julia supports parallelisation, arguably just as easy if not easier to implement than with Perl 6, Julia parallelisation was unusable for this. If I understood the documentation correctly, Julia is good at parallelising code that deals with IO; but if you try to parallelise non-IO code, it’s queued up and run in a single thread.

A win for Perl 6 there, in other words.

However, the Julia code was 2/3 the size of the Perl 6 version. And execution speed? Well, this being a Perl 6 blog I’m almost shameful to admit that the non-parallelised Julia version finished the comparisons in 12 minutes, approximately 20 times faster than Perl 6.

When it comes to the size of the code, much of the difference is probably caused by the fact that having already written this once, I knew where I could make things easier. But the thinking behind the Julia version is the same, and how I filter and flip and flop the data, is the same. That’s why I don’t have a good explanation of the speed difference (just to double check I also made a Perl 5 version as well, single threaded like the Julia version; that version more or less used the same amount of time as my original Perl 6 version). One of these days I have to run the profiler on the Perl 6 version. I guess that much of the time is spent calculating Levenshtein-Damerau distance, but I believe the for loops in themselves are taking time as well.

When we’re talking about Levenshtein, it’s worth noting that Julia’s Levensthein implementation automatically calculates a distance factor. I made my own in the Perl 6 version. The sharp-eyed reader will see that in my code the lower the factor is, the larger the similarity. The Julia version is exactly the opposite.

All the optimisation stuff is a story for another day, if ever. Meanwhile, here’s the Julia version. Thanks for bothering to read all the way to the end!

#!/usr/bin/env julia
using Base.Unicode
using StringDistances
alphabet = vcat('a':'z', ['æ','ø','å'])
dictionary = Dict{String,Int}()
zero_words = []
hit_words = []
similarity_count = 0
total_similarities = 0
function read_words()
open("st2.csv") do file
for ln in eachline(file)
c, d = split(ln, ",")
e = parse(Int, d)
try
dictionary[lowercase(c)] += e
catch
dictionary[lowercase(c)] = e
end
end
end
for (k, v) in enumerate(dictionary)
(word, value) = v
if value == 0
push!(zero_words, word)
else
push!(hit_words, word)
end
end
sort!(zero_words)
sort!(hit_words)
for c in alphabet
hw = size(filter(p->startswith(p, c), hit_words))[1]
zw = size(filter(p->startswith(p, c), zero_words))[1]
global total_similarities += (hw * zw)
end
end
function similarity()
for k1 in zero_words
for k2 in filter(p->startswith(p, string(first(k1))), hit_words)
x = compare(DamerauLevenshtein(), k1, k2)
if x > 0.7
println("$k1\t$k2\t$x")
end
global similarity_count += 1
if similarity_count % 10000 == 0
perc = (similarity_count / total_similarities) * 100
println(stderr, "Progress... $perc % [ $similarity_count of $total_similarities]")
flush(stdout)
end
end
end
end
read_words()
similarity()

rakudo.org: Rakudo Star Release 2018.10

Published on 2018-11-11T00:00:00

Perlgeek.de: Perl 6 Coding Contest 2019: Seeking Task Makers

Published by Moritz Lenz on 2018-11-10T23:00:01

I want to revive Carl Mäsak's Coding Contest as a crowd-sourced contest.

The contest will be in four phases:

For the first phase, development of tasks, I am looking for volunteers who come up with coding tasks collaboratively. Sadly, these volunteers, including myself, will be excluded from participating in the second phase.

I am looking for tasks that ...

This is non-trivial, so I'd like to have others to discuss things with, and to come up with some more tasks.

If you want to help with task creation, please send an email to moritz.lenz@gmail.com, stating your intentions to help, and your freenode IRC handle (optional).

There are other ways to help too:

In these cases you can use the same email address to contact me, or use IRC (moritz on freenode) or twitter.

my Timotimo \this: Rakudo Perl 6 performance analysis tooling: Progress Report

Published by Timo Paulssen on 2018-11-10T00:22:45

Rakudo Perl 6 performance analysis tooling: Progress Report

I have started properly working on the grant later than I had hoped, and have not been able to invest as much time per week as I had initially planned. However, recently more and more parts of the tool have come together to form a useful product.

Recently, core developer Stefan 'nine' Seifert has been able to make good use of the tool to assist in analyzing and optimizing the performance of a re-write of MoarVM's bytecode compiler in NQP code. Here are quotes from Stefan on IRC, along with links to the public IRC logs:

https://colabti.org/irclogger/irclogger_log/perl6-dev?date=2018-10-09#l56

I now managed to get a profile of the MAST stage using a patched --profile-stage, but the profile is too large even for the QT frontend :/
timotimo++ # moarperf works beautifully with this huge profile :)

https://colabti.org/irclogger/irclogger_log/perl6-dev?date=2018-10-23#l66

timotimo++ # the profiler is indespensable in getting nqp-mbc merge worthy.

Below you can find a copy of the "Deliverables and Inchstones" section of the original grant proposal with explanations of the current status/progress and any additional features I've been able to implement, along with a couple of screenshots to illustrate what I mean.

The "web frontend for heap snapshot analyzer" and "bunch of examples" sections have had their sub-headings removed, because work on that area has not yet started.

Deliverables and Inchstones

A blog with progress reports.

There have been 6 reports, mostly due to a long starting delay and some additional intervention from Life Itself:

A web frontend for the heap snapshot analyzer

I have pushed this off to the future, opting to prioritize the instrumented profiler frontend instead.

A new web frontend for the instrumented profiler

Rakudo Perl 6 performance analysis tooling: Progress Report

Rakudo Perl 6 performance analysis tooling: Progress Report

Rakudo Perl 6 performance analysis tooling: Progress Report

Rakudo Perl 6 performance analysis tooling: Progress Report

Rakudo Perl 6 performance analysis tooling: Progress Report

Rakudo Perl 6 performance analysis tooling: Progress Report

Rakudo Perl 6 performance analysis tooling: Progress Report

User-facing documentation on using the profiling facilities and interpreting the data

This has not yet happened, except for the blog post for the release that explains how to run the profiler, and the README.

Build a bunch of examples that show different performance issues and describe how to figure them out

There are currently big changes going on in MoarVM's optimizer relating to removing unnecessary boxing of intermediate values in calculations and such, which may make any examples moot real soon. I've delayed this part of the work a bit for that reason.

In Summary ...

I was positively surprised when I last opened the original tasks list and saw what was already done, and what could be finished with just a little bit of work!

I hope you'll give moarperf a try some time soon and let me know what you think! Here's a link to the project on github: MoarPerf project on github

Thanks for staying around and reading my blog posts :)
  - Timo

my Timotimo \this: Where did I leave my AT-KEYs?

Published by Timo Paulssen on 2018-11-09T21:17:24

Where did I leave my AT-KEYs?

Even though it's only been a week and a half since my last report, there's already enough new stuff to report on! Let's dig right in.

Where did I leave my AT-KEYs?
Photo by NeONBRAND / Unsplash

Overview Page

Where did I leave my AT-KEYs?

Is there terribly much to say about this? It now shows the same data that was already available in the old profiler's overview page. It's the go-to page when you've changed your code in the hopes of making it faster, or changed your version of rakudo in hopes of not having to change your code in order to make it faster.

Here's a screenshot from the other profiler for comparison:

Where did I leave my AT-KEYs?

The main addition over the previous version is the "start times of threads" piece at the top left. In multi-threaded programs it shows you when more threads were added, for example if you use start blocks on the default ThreadPoolScheduler.

The GC Performance section gives you not only the average time spent doing minor and major collections, but also the minimum and maximum time.

The rest is pretty much the same, except the new version puts separators in numbers with more than three digits, which I find much easier on the eyes than eight-digit numbers without any hints to guide the eye.

GC Run List

Where did I leave my AT-KEYs?

The graphs at the top of the GC tab has changed a bit! There's now the option to show only major, only minor, or all collections in the graph, and there are three different display modes for the "Amounts of data" graphs.

The one shown by default gives bars split into three colors to signify how much of the nursery's content has been freed (green), kept around for another round (orange), or promoted to the old generation (red). That's the mode you can see in the screenshot above.

Where did I leave my AT-KEYs?

The second mode is "Combined Chart", which just stacks the amounts in kilobytes on top of each other. That means when more threads get added, the bars grow. In this example screenshot, you can barely even see orange or red in the bars, but this program is very light on long-lived allocations.

Where did I leave my AT-KEYs?

The third mode is "Split Charts", which has one chart for each "color". Since they all have their own scales, you can more easily see differences from run to run, even if some of the charts appear tiny in the "combined" or "combined relative" charts.

Routines List

The routines overview – and actually all lists of routines in the program – have a new little clickable icon now. Here it is:

Where did I leave my AT-KEYs?

The icon I'm talking about is the little up-right-arrow in a little box after a routine's name. When you click on it, the row turns blue. Huh, that doesn't sound so useful? That's because the button brings you to the routines list and scrolls to and highlights the routine you've clicked on. If you're already right there, you will not notice a lot of change, of course.

However, it gets more interesting in the callers or callees lists:

Where did I leave my AT-KEYs?

Even better, since it actually uses links to actual URLs, the browser's back/forward buttons work with this.

Other useful places you can find this navigation feature are the allocations list and the call graph explorer:

Where did I leave my AT-KEYs?

Where did I leave my AT-KEYs?

Where are my AT-KEYs at?

If you have a very big profile, a routine you're interested in may be called in many, many places. Here's a profile of "zef list". Loading up the call graph for this routine may just explode my computer:

Where did I leave my AT-KEYs?

Note the number of Sites: 27 thousand. Not good.

But what if you're already in the call graph explorer anyway, and you just want to find your way towards functions that call your routine?

Enter the search box:

Where did I leave my AT-KEYs?

As you can see, when you input something in the search bar, hand icons will point you towards your destination in the call graph.

I'm looking to add many more different kinds of searches, for example I can imagine it would be interesting to see at a glance "which branches will ever reach non-core code". Searching for files ought to also be interesting.

Another idea I've had is that when you've entered a search term, it should be possible to exclude specific results, for example if there are many routines with the same name, but some of them are not the ones you mean. For example, "identity" is in pretty much every profile, since that's what many "return"s will turn into (when there's neither a decont nor a type check needed). However, Distributions (which is what zef deals in) also have an "identity" attribute, which is about name, version, author, etc.

At a much later point, perhaps even after the grant has finished, there could also be search queries that depend on the call tree's shape, for example "all instances where &postcircumfix:{ } is called by &postcircumfix:{ }".

That's it?

Don't worry! I've already got an extra blog post in the works which will be a full report on overall completion of the grant. There'll be a copy of the original list (well, tree) of the "deliverables and inchstones" along with screenshots and short explanations.

I hope you're looking forward to it! I still need to replace the section that says "search functionality is currently missing" with a short and sweet description of what you read in the previous section :)

With that I wish you a good day and a pleasant weekend
  - Timo

Zoffix Znet: Perl 6 Advent Calendar 2018 Call for Authors

Published on 2018-10-31T00:00:00

Write a blog post about Perl 6

my Timotimo \this: Full Screen Ahead!

Published by Timo Paulssen on 2018-10-28T18:50:54

Full Screen Ahead!

Whew, it's been a long time since the last report already! Let's see what's new.

Full Screen Ahead!
Photo by Jack Anstey / Unsplash

Improvements to the Routine Overview

The first tab you'll usually go to is the routine overview. It gives you a list of every routine that was encountered in the program. In a bunch of columns it shows you the name of the routine, along with the file it comes from and the line it's defined on. It tells you how often the routine was entered and how many of these entries were into or inside of jitted code.

The last column shows how much time the routine accounted for. The last part is split up twice. Once into inclusive vs exclusive time, which tells you how much total time was spent from entry to exit vs how much time was spent only inside the routine itself, rather than any routines called by it. The second split is into total time vs time divided by number of entries. That lets you more easily figure out which routines are slow by themselves vs which routines take a lot of time because they are called very, very often.

Usually it's best to start with the routines that take the most time in total, but routines that take longer per call may have more obvious optimization opportunities in them in my experience.

It is for that reason that being able to sort by different columns is extra important, and that wasn't available in the new tool for a whole while. That changed just yesterday, though! It still looks quite odd, because it's just a bunch of buttons that don't even react to which sorting mode is currently active, but that will change soon enough.

Full Screen Ahead!

The routines overview of course lets you expand the individual routines to get at more details. The details that were already in the previous blog post, were Callees, Paths, and Allocations. All three of them have changed a bit, and one more has been added recently.

All that happened in the Callees tab is that it is now also sortable.

The Paths tab has got a little toggle button called "Minimal" that reduces every cell in the tree to a little square. On top of that, the cells are now colored by the routine's filename - in the normal view the lower border of the cells shows the color, in the minimal view the cells themselves are colored in.

Here's two screenshots comparing regular and minimal view:

Full Screen Ahead!

Full Screen Ahead!

The Allocations tab now shows the total amount of memory allocated by the given routine for the given type. Of course this doesn't directly correspond to memory usage, since the profiler can't tell you how long the given objects survive.

Full Screen Ahead!

The new tab that was recently added is a very useful one. It's the Callers tab. It lets you see which routines have called the given routine, how often they called it, and to what percentage the routine got inlined into the callers. Here's a screenshot:

Full Screen Ahead!

Allocations Tab

There's a whole new top-level tab, too. It's titled "Allocations" and does very much what you would expect.

The tab contains a big table of all types the profiler saw in the program. Every row shows the Type name along with potentially a link to the docs website, the size of each object and how much memory in total was allocated for it, and how often that type of object was allocated in total.

On the left there is a button that lets you expand the type's column to get extra details:

Full Screen Ahead!

None of these things are very surprising, but they are useful.

Overview Tab

The overview tab used to just have a placeholder text. However, it now displays at least a little bit of information. Have a look!

Full Screen Ahead!

It's still very fresh and I expect it to look completely different in a week or two.

What's with the "Full Screen" pun?

This post starts with a silly little pun on "Full Steam Ahead". What does it mean for the profiler tool?

The answer is very simple, it lets you use the whole width of your browser window. Bootstrap – which is the library of CSS styles and primitives I use so that I don't have to spend three fourths of the entire development time fiddling with CSS rules so that things look okay or even work at all – is convinced that the outermost Container element of the site shouldn't be wider than a specific width, probably because things can look kind of "lost" on a page that's not filled side-to-side with stuff. If you have big tables full of data or wide graphs with tiny bars, it sure is good to be able to expand the page sideways.

Here's a little animation I made a few weeks ago that shows the fullscreen button in action for one example.

You're my favourite customer!

Stefan 'nine' Seifert has recently been working on replacing the "mast" stage in the Perl 6 compiler.

In the simplest terms, it used to take the abstract syntax tree to rewrite it into a very flat tree consisting of lists of moar instructions. Those were then fed into MoarVM as objects, which were then translated into actual moar bytecode, literally as bytes.

The main drawback of the earlier approach was memory use. On top of all the QAST node objects that were the input to the mast stage, a huge batch of new objects were created before it was all passed to moar's bytecode compiler as one set. The more alive objects there are, the higher the maximum memory usage gets, and the longer it takes the GC to go through everything to decide what's garbage and what needs to stick around.

The new approach starts with the QAST nodes again, but immediately starts writing out bytes into buffers. That has a whole bunch of implications immediately: Every Object consists of at least a header that's a couple of bytes big. Buffers (and native arrays) are just a single object with a big consecutive blob of memory they "own". No matter how big the blob grows, the garbage collector only has to look at the object header and can ignore the blob itself! Not only does it save memory by not having as many individual objects, it also saves the garbage collector time!

Stefan told me on IRC that the new profiler tool already helped him a lot in making the new implementation faster.

I now managed to get a profile of the MAST stage using a patched --profile-stage, but the profile is too large even for the QT frontend :/
timotimo++ # moarperf works beautifully with this huge profile :)

https://colabti.org/irclogger/irclogger_log/perl6-dev?date=2018-10-09#l56

timotimo++ # the profiler is indespensable in getting nqp-mbc merge worthy.

https://colabti.org/irclogger/irclogger_log/perl6-dev?date=2018-10-23#l66

This obviously makes yours truly very happy :)

There's still lots of "paper cuts" to be ironed out from a User Experience standpoint, but I'm very glad that the tool is already making work possible that used to be impossible.

That's all the improvements I have to report for now, but I'll be continuing work on the UI and backend and write up another report (hopefully) soon!

BTW, a big conference on React.js (the tech I use to make the frontend tick) just happened and the react core dev team unveiled a few new APIs and tricks that I expect will let me make the existing code a lot simpler and write new code faster than before!

Also, during the conference Chris Trevino presented a new charting library based around the "Grammar of Graphics" philosophy(?) that is also the basis of vega and vega-lite which as I understand it is The Big Cheese among data visualization experts. I've been having some gripes with recharts, so I'll be checking this out soon!

Hope to see y'all in the next one!
  - Timo

Jo Christian Oterhals: Perl 6 small stuff #12: Cobol precision, revisited (or… even more fun with FatRats)

Published by Jo Christian Oterhals on 2018-10-22T12:00:58

Let me start by saying that this will be the last article exploring peculiarities of Perl 6’s maths functions. I promise. At least for a while. With that said, let’s dive back into rational numbers vs floating point one last time.

Binary representation of the floating point number 0.15625. CC © Wikimedia Commons.

Back in number 4 of this series, I tried to figure out the precision of Perl 6‘s ’rational numbers compared to Cobol’s fixed precision types. That may sound like a strange thing to do, but I had just read an article about why Cobol still was preferred by financial institutions (read it if you haven’t already — this article will be easier to understand if you do, especially why the particular algorithm below is used to check precision). It had to do with how Cobol could control floating point precision to avoid rounding errors that accumulated over time could cost banks, stock exchanges, the IRS, etc., millions of dollars. The author proved that by comparing a little Python snippet to Cobol, a script that broke Python in all the expected ways.

Since Perl 6 use the Rat (rational) data type under the hood for lots of things, even without explicit typing on the programmer’s part, my hypothesis was that Perl 6 wouldn’t have these kinds of errors at all. So I made a Perl 6 implementation of the error provoking algorithm outlined in the Cobol article. And wouldn’t you know it: Perl 6 didn’t have the errors mentioned in the Cobol article. I proudly spread that conclusion in my Having fun with Rats post.

As it turns out I was a little too trigger happy. In my article I just tested the algorithm to 20 iterations since that was what the Cobol article did. When tinkering with the code afterwards I found that my Perl 6 code broke at around 28 iterations. So although it fared better than Python, and went beyond the Cobol example, even Perl 6 wasn’t foolproof.

That made me think: What if I implemented it using explicit typing, this time forcing the use of FatRats? So I did:

#!/usr/bin/env perl6
sub rec(FatRat $y, FatRat $z) {
return 108 — (815–1500/$z)/$y;
}
sub default-behavior(Int:D $N) {
my @x = FatRat.new(4), FatRat.new(17, 4);
for (2..$N+1) -> $i {
my $n = rec(@x[$i-1], @x[$i-2]);
@x.append($n);
}
return @x;
}
my @y = default-behavior(2000);
for @y.kv -> $i, $p {
say $i.fmt(“%02d”) ~ “ | “ ~ @y[$i].fmt(“%3.20f”);
say join “ / “, @y[$i].nude;
}

As you can see I ran the code up to 2000 iterations. And Perl 6 didn’t break once. I figure I could continue much longer, but that wouldn’t prove my point any more than it already had: FatRats seemingly handle everything.

At around 2000 iterations, the floating point representation was an even 5. The FatRat had increased to something beyond readable:

2001 | 5.00000000000000000000
10887262270271520844470244368473590369823879678381735770804366536872861066757834267230923438499734851331955108971818900795255377964985420406353488530653796076376888302887871648059636404237386779810073204677465433988288796371463779266725835301768375910295365966893549342070113935097170738554786589822697649361389182715711445880206813457196212233603705832810491425136584469585820510373307587755977621707298634317089590138855983741462833338843271340817765566670690233393031687431055903364260747271559744687940769179892188275670612186517021074968728089773868903232112413409395441640658761326225416663244033887317133246740410946847989349983326675880888985445567168787598735624717364724914686476958266124806775762813974242476406932409145206237566267025023985919713838560053160634848162125063714368558880445253361406701423828947352575925454715484530130867655804116616415778049891344295072286232982121196487495343247308360407488300676499377578310332816377975448193225536813649463486171661227928324492008794414474774496406886870868799498753785243478428165856592662574587026062708505894963955557204003803392615937919983143327086591424359681275817919140507987737463394218763462404759849484338109892177212883565977961986616331952406228280515381736751779687947623033277314097434771424807829329022829618524311375471611964574251871376643107540529697952215346315210658268262117062285956468458853775876425932095612817 / 2177452454054304168894048873694718073964775935676347154160873307374572213351566853446184687699946970266391021794363780159051075592997084081270697706130759215275377660577574329611927280847477355962014640935493086797657759274292755853345167060353675182059073193378709868414022787019434147710957317964539529872277836543142289176041362691439242446720741166562098285027316893917164102074661517551195524341459726863417918027771196748292566667768654269212275864367729012474591108985007522990289641915425059624720960922390197391499416012195286133802412263320144198333588435944700149853436940773893604588831895901210854703334389818287374956988979446767663405991767869404053875825243861633344428650812796466524645611445569036116412001976972688038699652154919003410804565289198476051171009210210514432258823939333189758824739429056132928366378633982114880626729252784764043010629666202312909247751673764726461337254048195958324091876383541819502316785741383639145866071856825051549231447161710399611381911575660385601546360041084280896676911889810584537683240864405819307049463732925606631546639518426651121208176285007436520251461854127484076350233519219480398658641001242539048046529742114192549782403287806556840860371337966097173350218236381329518702831401361914811597448759832549227759610938548970537888455950617834972888158093407922606309451101643311842471881838667105291086022959240750179576618885386564

I can’t say that I’m anything but impressed. So go on. Reimplement your bank systems in Perl 6 🤪.

Since these articles are nothing without a comparison to something else, I figured I’d do it again. Since I had so much success using Perl 5 with the use bignum pragma in my last article (Numberphile calculator test), I decided, just for fun, to implement this in Perl 5 as well.

#!/usr/bin/env perl
use 5.18.0;
use bignum;
use strict;
my $cnt = 0;
sub rec {
my ($y, $z) = (shift, shift);
return 108 - (815-1500/$z)/$y;
}
sub default_behavior {
my $N = shift;
my @x = ( 4, 4.25 );
for my $i (2..$N+1) {
my $n = rec($x[$i-1], $x[$i-2]);
push(@x, $n);
}
return @x;
}
my @y = default_behavior(30);
for my $i (0..30) {
say $i . " | " . $y[$i];
}

This time Perl 5 is not as impressive. This code croaks around iteration 26. Remove the use bignum pragma and it croaks around 13.[1]

Still: For most us this is just theoretical stuff, so in reality you’ll make do with both Perls I guess. At least I know I will.

NOTE
[1]
Julia, that was a part of the comparison mix in my last article, was good until iteration 52 using the BigFloat type. To have a fair comparison with Perl 6 I also tried Julia with Julia’s rational type, specified to the highest precision — Rational{UInt128}. Julia gave up at around the same iteration using that as well. So Julia fared better than Perl 5 but nowhere near Perl 6. But as I noted above about the two Perls, the difference is theoretical. For all practical purposes even Julia will do.

Jo Christian Oterhals: Not bad! My only issue with it is that depending on your point of view the Pearly Gate is either…

Published by Jo Christian Oterhals on 2018-10-11T11:22:24

Not bad! My only issue with it is that depending on your point of view the Pearly Gate is either the beginning of something or the end. How do we avoid the latter?

Zoffix Znet: A Request to Larry Wall to Create a Language Name Alias for Perl 6

Published on 2018-10-07T00:00:00

The culmination of the naming discussion

6guts: Speeding up object creation

Published by jnthnwrthngtn on 2018-10-06T22:59:11

Recently, a Perl 6 object creation benchmark result did the rounds on social media. This Perl 6 code:

class Point {
    has $.x;
    has $.y;
}
my $total = 0;
for ^1_000_000 {
    my $p = Point.new(x => 2, y => 3);
    $total = $total + $p.x + $p.y;
}
say $total;

Now (on HEAD builds of Rakudo and MoarVM) runs faster than this roughly equivalent Perl 5 code:

use v5.10;

package Point;

sub new {
    my ($class, %args) = @_;
    bless \%args, $class;
}

sub x {
    my $self = shift;
    $self->{x}
}

sub y {
    my $self = shift;
    $self->{y}
}

package main;

my $total = 0;
for (1..1_000_000) {
    my $p = Point->new(x => 2, y => 3);
    $total = $total + $p->x + $p->y;
}
say $total;

(Aside: yes, I know there’s no shortage of libraries in Perl 5 that make OO nicer than this, though those I tried also made it slower.)

This is a fairly encouraging result: object creation, method calls, and attribute access are the operational bread and butter of OO programming, so it’s a pleasing sign that Perl 6 on Rakudo/MoarVM is getting increasingly speedy at them. In fact, it’s probably a bit better at them than this benchmark’s raw numbers show, since:

While dealing with Int values got faster recently, it’s still really making two Int objects every time around that loop and having to GC them later. An upcoming new set of analyses and optimizations will let us get rid of that cost too. And yes, startup will get faster with time also. In summary, while Rakudo/MoarVM is now winning that benchmark against Perl 5, there’s still lots more to be had. Which is a good job, since the equivalent Python and Ruby versions of that benchmark still run faster than the Perl 6 one.

In this post, I’ll look at the changes that allowed this benchmark to end up faster. None of the new work was particularly ground-breaking; in fact, it was mostly a case of doing small things to make better use of optimizations we already had.

What happens during construction?

Theoretically, the default new method in turn calls bless, passing the named arguments along. The bless method then creates an object instance, followed by calling BUILDALL. The BUILDALL method goes through the set of steps needed for constructing the object. In the case of a simple object like ours, that involves checking if an x and y named argument were passed, and if so assigning those values into the Scalar containers of the object attributes.

For those keeping count, that’s at least 3 method calls (newbless, and BUILDALL).

However, there’s a cheat. If bless wasn’t overridden (which would be an odd thing to do anyway), then the default new could just call BUILDALL directly anyway. Therefore, new looks like this:

multi method new(*%attrinit) {
    nqp::if(
      nqp::eqaddr(
        (my $bless := nqp::findmethod(self,'bless')),
        nqp::findmethod(Mu,'bless')
      ),
      nqp::create(self).BUILDALL(Empty, %attrinit),
      $bless(|%attrinit)
    )
}

The BUILDALL method was originally a little “interpreter” that went through a per-object build plan stating what needs to be done. However, for quite some time now we’ve instead compiled a per-class BUILDPLAN method.

Slurpy sadness

To figure out how to speed this up, I took a look at how the specializer was handling the code. The answer: not so well. There were certainly some positive moments in there. Of note:

However, the new method was getting only a “certain” specialization, which is usually only done for very heavily polymorphic code. That wasn’t the case here; this program clearly constructs overwhelmingly one type of object. So what was going on?

In order to produce an “observed type” specialization – the more powerful kind – it needs to have data on the types of all of the passed arguments. And for the named arguments, that was missing. But why?

Logging of passed argument types is done on the callee side, since:

The argument logging was done as the interpreter executed each parameter processing instruction. However, when there’s a slurpy, then it would just swallow up all the remaining arguments without logging type information. Thus the information about the argument types was missing and we ended up with a less powerful form of specialization.

Teaching the slurpy handling code about argument logging felt a bit involved, but then I realized there was a far simpler solution: log all of the things in the argument buffer at the point an unspecialized frame is being invoked. We’re already logging the entry to the call frame at that point anyway. This meant that all of the parameter handling instructions got a bit simpler too, since they no longer had logging to do.

Conditional elimination

Having new being specialized in a more significant way was an immediate win. Of note, this part:

      nqp::eqaddr(
        (my $bless := nqp::findmethod(self,'bless')),
        nqp::findmethod(Mu,'bless')
      ),

Was quite interesting. Since we were now specializing on the type of self, then the findmethod could be resolved into a constant. The resolution of a method on the constant Mu was also a constant. Therefore, the result of the eqaddr (same memory address) comparison of two constants should also have been turned into a constant…except that wasn’t happening! This time, it was simple: we just hadn’t implemented folding of that yet. So, that was an easy win, and once done meant the optimizer could see that the if would always go a certain way and thus optimize the whole thing into the chosen branch. Thus the new method was specialized into something like:

multi method new(*%attrinit) {
    nqp::create(self).BUILDALL(Empty, %attrinit),
}

Further, the create could be optimized into a “fast create” op, and the relatively small BUILDALL method could be inlined into new. Not bad.

Generating simpler code

At this point, things were much better, but still not quite there. I took a look at the BUILDALL method compilation, and realized that it could emit faster code.

The %attrinit is a Perl 6 Hash object, which is for the most part a wrapper around the lower-level VM hash object, which is the actual hash storage. We were, curiously, already pulling this lower-level hash out of the Hash object and using the nqp::existskey primitive to check if there was a value, but were not doing that for actually accessing the value. Instead, an .AT-KEY('x') method call was being done. While that was being handled fairly well – inlined and so forth – it also does its own bit of existence checking. I realized we could just use the nqp::atkey primitive here instead.

Later on, I also realized that we could do away with nqp::existskey and just use nqp::atkey. Since a VM-level null is something that never exists in Perl 6, we can safely use it as a sentinel to mean that there is no value. That got us down to a single hash lookup.

By this point, we were just about winning the benchmark, but only by a few percent. Were there any more easy pickings?

An off-by-one

My next surprise was that the new method didn’t get inlined. It was within the size limit. There was nothing preventing it. What was going on?

Looking closer, it was even worse than that. Normally, when something is too big to be inlined, but we can work out what specialization will be called on the target, we do “specialization linking”, indicating which specialization of the code to call. That wasn’t happening. But why?

Some debugging later, I sheepishly fixed an off-by-one in the code that looks through a multi-dispatch cache to see if a particular candidate matches the set of argument types we have during optimization of a call instruction. This probably increased the performance of quite a few calls involving passing named arguments to multi-methods – and meant new was also inlined, putting us a good bit ahead on this benchmark.

What next?

The next round of performance improvements – both to this code and plenty more besides – will come from escape analysis, scalar replacement, and related optimizations. I’ve already started on that work, though expect it will keep me busy for quite a while. I will, however, be able to deliver it in stages, and am optimistic I’ll have the first stage of it ready to talk about – and maybe even merge – in a week or so.

brrt to the future: A future for fork(2)

Published by Bart Wiegmans on 2018-10-04T05:18:00

Hi hackers. Today I want to write about a new functionality that I've been developing for MoarVM that has very little to do with the JIT compiler. But it is still about VM internals so I guess it will fit.

Many months ago, jnthn wrote a blog post on the relation between perl 5 and perl 6. And as a longtime and enthusiastic perl 5 user - most of the JIT's compile time support software is written in perl 5 for a reason - I wholeheartedly agree with the 'sister language' narrative. There is plenty of room for all sorts of perls yet, I hope. Yet one thing kept itching me:
Moreover, it’s very much the case that Perl 5 and Perl 6 make different trade-offs. To pick one concrete example, Perl 6 makes it easy to run code across multiple threads, and even uses multiple threads internally (for example, performing optimization and JIT compilation on a background thread). Which is great…except the only winning move in a game involving both threads and fork() is not to play. Sometimes one just can’t have their cake and eat it, and if you’re wanting a language that more directly gives you your POSIX, that’s probably always going to be a strength of Perl 5 over Perl 6.
(Emphasis mine). You see, I had never realized that MoarVM couldn't implement fork(), but it's true. In POSIX systems, a fork()'d child process inherits the full memory space, as-is, from its parent process. But it inherits only the forking thread. This means that any operations performed by any other thread, including operations that might need to be protected by a mutex (e.g. malloc()), will be interrupted and unfinished (in the child process). This can be a problem. Or, in the words of the linux manual page on the subject:

       *  The child process is created with a single thread—the one that
called fork(). The entire virtual address space of the parent is
replicated in the child, including the states of mutexes,
condition variables, and other pthreads objects; the use of
pthread_atfork(3) may be helpful for dealing with problems that
this can cause.

* After a fork() in a multithreaded program, the child can safely
call only async-signal-safe functions (see signal-safety(7)) until
such time as it calls execve(2).

Note that the set of signal-safe functions is not that large, and excludes all memory management functions. As noted by jnthn, MoarVM is inherently multithreaded from startup, and will happily spawn as many threads as needed by the program. It also uses malloc() and friends rather a lot. So it would seem that perl 6 cannot implement POSIX fork() (in which both parent and child program continue from the same position in the program) as well as perl 5 can.

I was disappointed. As a longtime (and enthusiastic) perl 5 user, fork() is one of my favorite concurrency tools. Its best feature is that parent and child processes are isolated by the operating system, so each can modify its own internal state without concern for concurrency,. This can make it practical to introduce concurrency after development, rather than designing it in from the start. Either process can crash while the other continues. It is also possible (and common) to run a child process with reduced privileges relative to the parent process, which isn't possible with threads. And it is possible to prepare arbitrarily complex state for the child process, unlike spawn() and similar calls.

Fortunately all hope isn't necessarily lost. The restrictions listed above only apply if there are multiple threads active at the moment that fork() is executed. That means that if we can stop all threads (except for the one planning to fork) before actually calling fork(), then the child process can continue safely. That is well within the realm of possibility, at least as far as system threads are concerned.

The process itself isn't very exciting to talk about, actually - it involves sending stop signals to system threads, waiting for these threads to join, verifying that the forking thread is the really only active thread, and restarting threads after fork(). Because of locking, it is a bit subtle (tbere may be another user thread that is also trying to fork), but not actually very hard. When I finally merged the code, it turned out that an ancient (and forgotten) thread list modification function was corrupting the list by not being aware of generational garbage collection... oops. But that was simple enough to fix (thanks to timotimo++ for the hint).

And now the following oneliner should work on platforms that support fork():(using development versions of MoarVM and Rakudo):

perl6 -e 'use nqp; my $i = nqp::fork(); say $i;'

The main limitation of this work is that it won't work if there are any user threads active. (If there are any, nqp::fork() will throw an exception). The reason why is simple: while it is possible to adapt the system threads so that I can stop them on demand, user threads may be doing arbitrary work, hold arbitrary locks and may be blocked (possibly indefinitely) on a system call. So jnthn's comment at the start of this post still applies - threads and fork() don't work together.

In fact, many programs may be better off with threads. But I think that languages in the perl family should let the user make that decision, rather than the VM. So I hope that this will find some use somewhere. If not, it was certainly fun to figure out. Happy hacking!


PS: For the curious, I think there may in fact be a way to make fork() work under a multithreaded program, and it relies on the fact that MoarVM has a multithreaded garbage collector. Basically, stopping all threads before calling fork() is not so different from stopping the world during the final phase of garbage collection. And so - in theory - it would be possible to hijack the synchronization mechanism of the garbage collector to pause all threads. During interpretation, and in JIT compiled code, each thread periodically checks if garbage collection has started. If it has, it will synchronize with the thread that started GC in order to share the work. Threads that are currently blocked (on a system call, or on acquiring a lock) mark themselves as such, and when they are resumed always check the GC status. So it is in fact possible to force MoarVM into a single active thread even with multiple user threads active. However, that still leaves cleanup to deal with, after returning from fork() in the child process. Also, this will not work if a thread is blocked on NativeCall. Altogether I think abusing the GC in order to enable a fork() may be a bit over the edge of insanity :-)

6guts: Eliminating unrequired guards

Published by jnthnwrthngtn on 2018-09-29T19:59:28

MoarVM’s optimizer can perform speculative optimization. It does this by gathering statistics as the program is interpreted, and then analyzing them to find out what types and callees typically show up at given points in the program. If it spots there is at least a 99% chance of a particular type showing up at a particular program point, then it will optimize the code ahead of that point as if that type would always show up.

Of course, statistics aren’t proofs. What about the 1% case? To handle this, a guard instruction is inserted. This cheaply checks if the type is the expected one, and if it isn’t, falls back to the interpreter. This process is known as deoptimization.

Just how cheap are guards?

I just stated that a guard cheaply checks if the type is the expected one, but just how cheap is it really? There’s both direct and indirect costs.

The direct cost is that of the check. Here’s a (slightly simplified) version of the JIT compiler code that produces the machine code for a type guard.

/* Load object that we should guard */
| mov TMP1, WORK[obj];
/* Get type table we expect and compare it with the object's one */
MVMint16 spesh_idx = guard->ins->operands[2].lit_i16;
| get_spesh_slot TMP2, spesh_idx;
| cmp TMP2, OBJECT:TMP1->st;
| jne >1;
/* We're good, no need to deopt */
| jmp >2;
|1:
/* Call deoptimization handler */
| mov ARG1, TC;
| mov ARG2, guard->deopt_offset;
| mov ARG3, guard->deopt_target;
| callp &MVM_spesh_deopt_one_direct;
/* Jump out to the interpreter */
| jmp ->exit;
|2:

Where get_spesh_slot is a macro like this:

|.macro get_spesh_slot, reg, idx;
| mov reg, TC->cur_frame;
| mov reg, FRAME:reg->effective_spesh_slots;
| mov reg, OBJECTPTR:reg[idx];
|.endmacro

So, in the case that the guard matches, it’s 7 machine instructions (note: it’s actually a couple more because of something I omitted for simplicity). Thus there’s the cost of the time to execute them, plus the space they take in memory and, especially, the instruction cache. Further, one is a conditional jump. We’d expect it to be false most of the time, and so the CPU’s branch predictor should get a good hit rate – but branch predictor usage isn’t entirely free of charge either. Effectively, it’s not that bad, but it’s nice to save the cost if we can.

The indirect costs are much harder to quantify. In order to deoptimize, we need to have enough state to recreate the world as the interpreter expects it to be. I wrote on this topic not so long ago, for those who want to dive into the detail, but the essence of the problem is that we may have to retain some instructions and/or forgo some optimizations so that we are able to successfully deoptimize if needed. Thus, the presence of a guard constrains what optimizations we can perform in the code around it.

Representation problems

A guard instruction in MoarVM originally looked like:

sp_guard r(obj) sslot uint32

Where r(obj) is an object register to read containing the object to guard, the sslot is a spesh slot (an entry in a per-block constant table) containing the type we expect to see, and the uint32 indicates the target address after we deoptimize. Guards are inserted after instructions for which we had gathered statistics and determined there was a stable type. Things guarded include return values after a call, reads of object attributes, and reads of lexical variables.

This design has carried us a long way, however it has a major shortcoming. The program is represented in SSA form. Thus, an invoke followed by a guard might look something like:

invoke r6(5), r4(2)
sp_guard r6(5), sslot(42), litui32(64)

Where r6(5) has the return value written into it (and thus is a new SSA version of r6). We hold facts about a value (if it has a known type, if it has a known value, etc.) per SSA version. So the facts about r6(5) would be that it has a known type – the one that is asserted by the guard.

The invoke itself, however, might be optimized by performing inlining of the callee. In some cases, we might then know the type of result that the inlinee produces – either because there was a guard inside of the inlined code, or because we can actually prove the return type! However, since the facts about r6(5) were those produced by the guard, there was no way to talk about what we know of r6(5) before the guard and after the guard.

More awkwardly, while in the early days of the specializer we only ever put guards immediately after the instructions that read values, more recent additions might insert them at a distance (for example, in speculative call optimizations and around spesh plugins). In this case, we could not safely set facts on the guarded register, because those might lead to wrong optimizations being done prior to the guard.

Changing of the guards

Now a guard instruction looks like this:

sp_guard w(obj) r(obj) sslot uint32

Or, concretely:

invoke r6(5), r4(2)
sp_guard r6(6), r6(5), sslot(42), litui32(64)

That is to say, it introduces a new SSA version. This means that we get a way to talk about the value both before and after the guard instruction. Thus, if we perform an inlining and we know exactly what type it will return, then that type information will flow into the input – in our example, r6(5) – of the guard instruction. We can then notice that the property the guard wants to assert is already upheld, and replace the guard with a simple set (which may itself be eliminated by later optimizations).

This also solves the problem with guards inserted away from the original write of the value: we get a new SSA version beyond the guard point. This in turn leads to more opportunities to avoid repeated guards beyond that point.

Quite a lot of return value guards on common operations simply go away thanks to these changes. For example, in $a + $b, where $a and $b are Int, we will be able to inline the + operator, and we can statically see from its code that it will produce an Int. Thus, the guard on the return type in the caller of the operator can be eliminated. This saves the instructions associated with the guard, and potentially allows for further optimizations to take place since we know we’ll never deoptimize at that point.

In summary

MoarVM does lots of speculative optimization. This enables us to optimize in cases where we can’t prove a property of the program, but statistics tell us that it mostly behaves in a certain way. We make this safe by adding guards, and falling back to the general version of the code in cases where they fail.

However, guards have a cost. By changing our representation of them, so that we model the data coming into the guard and after the guard as two different SSA versions, we are able to eliminate many guard instructions. This not only reduces duplicate guards, but also allows for elimination of guards when the broader view afforded by inlining lets us prove properties that we weren’t previously able to.

In fact, upcoming work on escape analysis and scalar replacement will allow us to start seeing into currently opaque structures, such as Scalar containers. When we are able to do that, then we’ll be able to prove further program properties, leading to the elimination of yet more guards. Thus, this work is not only immediately useful, but also will help us better exploit upcoming optimizations.

6guts: Faster box/unbox and Int operations

Published by jnthnwrthngtn on 2018-09-28T22:43:55

My work on Perl 6 performance continues, thanks to a renewal of my grant from The Perl Foundation. I’m especially focusing on making common basic operations faster, the idea being that if those go faster than programs composed out of them also should. This appears to be working out well: I’ve not been directly trying to make the Text::CSV benchmark run faster, but that’s resulted from my work.

I’ll be writing a few posts in on various of the changes I’ve done. This one will take a look at some related optimizations around boxing, unboxing, and common mathematical operations on Int.

Boxing and unboxing

Boxing is taking a natively typed value and wrapping it into an object. Unboxing is the opposite: taking an object that wraps a native value and getting the native value out of it.

In Perl 6, these are extremely common. Num and Str are boxes around num and str respectively. Thus, unless dealing with natives explicitly, working with floating point numbers and strings will involve lots of box and unbox operations.

There’s nothing particularly special about Num and Str. They are normal objects with the P6opaque representation, meaning they can be mixed into. The only thing that makes them slightly special is that they have attributes marked as being a box target. This indicates the attribute out as being the one to write to or read from in a box or unbox operation.

Thus, a box operations is something like:

While unbox is:

Specialization of box and unbox

box is actually two operations: an allocation and a store. We know how to fast-path allocations and JIT them relatively compactly, however that wasn’t being done for box. So, step one was to decompose this higher-level op into the allocation and the write into the allocated object. The first step could then be optimized in the usual way allocations are.

In the unspecialized path, we first find out where to write the native value to, and then write it. However, when we’re producing a specialized version, we almost always know the type we’re boxing into. Therefore, the object offset to write to can be calculated once, and a very simple instruction to do a write at an offset into the object produced. This JITs extremely well.

There are a couple of other tricks. Binds into a P6opaque generally have to check that the object wasn’t mixed in to, however since we just allocated it then we know that can’t be the case and can skip that check. Also, a string is a garbage-collectable object, and when assigning one GC-able object into another one, we need to perform a write barrier for the sake of generational GC. However, since the object was just allocated, we know very well that it is in the nursery, and so the write barrier will never trigger. Thus, we can omit it.

Unboxing is easier to specialize: just calculate the offset, and emit a simpler instruction to load the value from there.

I’ve also started some early work (quite a long way from merge) on escape analysis, which will allow us to eliminate many box object allocations entirely. It’s a great deal easier to implement this if allocations, reads, and writes to an object have a uniform representation. By lowering box and unbox operations into these lower level operations, this eases the path to implementing escape analysis for them.

What about Int?

Some readers might have wondered why I talked about Num and Str as examples of boxed types, but not Int. It is one too – but there’s a twist. Actually, there’s two twists.

The first is that Int isn’t actually a wrapper around an int, but rather an arbitrary precision integer. When we first implemented Int, we had it always use a big integer library. Of course, this is slow, so later on we made it so any number fitting into a 32-bit range would be stored directly, and only allocate a big integer structure if it’s outside of this range.

Thus, boxing to a big integer means range-checking the value to box. If it fits into the 32-bit range, then we can write it directly, and set the flag indicating that it’s a small Int. Machine code to perform these steps is now spat out directly by the JIT, and we only fall back to a function call in the case where we need a big integer. Once again, the allocation itself is emitted in a more specialized way too, and the offset to write to is determined once at specialization time.

Unboxing is similar. Provided we’re specializing on the type of the object to unbox, then we calculate the offset at specialization time. Then, the JIT produces code to check if the small Int flag is set, and if so just reads and sign extends the value into a 64-bit register. Otherwise, it falls back to the function call to handle the real big integer case.

For boxing, however, there was a second twist: we have a boxed integer cache, so for small integers we don’t have to repeatedly allocate objects boxing them. So boxing an integer is actually:

  1. Check if it’s in the range of the box cache
  2. If so, return it from the cache
  3. Otherwise, do the normal boxing operation

When I first did these changes, I omitted the use of the box cache. It turns out, however, to have quite an impact in some programs: one benchmark I was looking at suffered quite a bit from the missing box cache, since it now had to do a lot more garbage collection runs.

So, I reinstated use of the cache, but this time with the JIT doing the range checks in the produced machine code and reading directly out of the cache in the case of a hit. Thus, in the cache hit case, we now don’t even make a single function call for the box operation.

Faster Int operations

One might wonder why we picked 32-bit integers as the limit for the small case of a big integer, and not 64-bit integers. There’s two reasons. The most immediate is that we can then use the 32 bits that would be the lower 32 of a 64-bit pointer to the big integer structure as our “this is a small integer” flag. This works reliably as pointers are always aligned to at least a 4-byte boundary, so a real pointer to a big integer structure would never have the lowest bits set. (And yes, on big-endian platforms, we swap the order of the flag and the value to account for that!)

The second reason is that there’s no portable way in C to detect if a calculation overflowed. However, out of the basic math operations, if we have two inputs that fit into a 32-bit integer, and we do them at 64-bit width, we know that the result can never overflow the 64-bit integer. Thus we can then range check the result and decide whether to store it back into the result object as 32-bit, or to store it as a big integer.

Since Int is immutable, all operations result in a newly allocated object. This allocation – you’ll spot a pattern by now – is open to being specialized. Once again, finding the boxed value to operate on can also be specialized, by calculating its offset into the input objects and result object. So far, so familiar.

However, there’s a further opportunity for improvement if we are JIT-compiling the operations to machine code: the CPU has flags for if the last operation overflowed, and we can get at them. Thus, for two small Int inputs, we can simply:

  1. Grab the values
  2. Do the calculation at 32-bit width
  3. Check the flags, and store it into the result object if no overflow
  4. If it overflowed, fall back to doing it wider and storing it as a real big integer

I’ve done this for addition, subtraction, and multiplication. Those looking for a MoarVM specializer/JIT task might like to consider doing it for some of the other operations. :-)

In summary

Boxing, unboxing, and math on Int all came with various indirections for the sake of generality (coping with mixins, subclassing, and things like IntStr). However, when we are producing type-specialized code, we can get rid of most of the indirections, resulting in being able to perform them faster. Further, when we JIT-compile the optimized result into machine code, we can take some further opportunities, reducing function calls into C code as well as taking advantage of access to the overflow flags.

samcv: Adding and Improving File Encoding Support in MoarVM

Published on 2018-09-26T07:00:00

Encodings. They may seem to some as horribly boring and bland. Nobody really wants to have to worry about the details. Encodings are how we communicate, transmit data. Their purpose is to be understood by others. When they work, nobody should even know they are there. When they don’t — and everyone can probably remember a time when they have tried to open a poorly encoded or corrupted file and been disappointed — they cannot be ignored.

Here I talk about the work I have done in the past and work still in progress to improve the support of current encodings, add new encodings, and add new features and new options to allow Perl 6 and MoarVM to support more encodings and in a way which better achieves the goals encodings were designed to solve.

Table of Contents

Which Encodings Should We Add?

I started looking at the most common encodings on the Web. We supported the two most common, UTF-8 and ISO-8859-1 but we did not support windows-1251 (Cyrillic) or ShiftJIS. This seemed like the makings of a new project so I got to work.

I decided to start with windows-1251 since it was an 8 bit encoding while Shift-JIS was a variable length one or two byte encoding (the shift in the name comes from the second byte 'shift'). While the encoding itself was simpler than Shift-JIS, I was soon realizing some issues with both windows-1251 and our already supported windows-1252 encoding.

One of the first major issues I found in windows-1252, you could create files which could not be decoded by other programs. An example of this is codepoint 0x81 (129) which does not have a mapping in the windows-1252 specification. This would cause many programs to not detect the file as windows-1252, or to fail saying the file was corrupted and could not be decoded.

While our non-8bit encodings would throw an error if asked to encode text which did not exist in that codemapping, our 8 bit encodings would happily pass through invalid codepoints, as long as they fit in 8 bits.

As I said at the start, encodings are a way for us to communicate, to exchange data and to be understood. This to me indicated a major failing. While the solution could be to never attempt to write codepoints that don’t exist in the target encoding, that was not an elegant solution and would just be a workaround.

To remedy this I had to add new ops, such as decodeconf to replace decode op, and encodeconf to replace encode (plus many others). This would allow us to specify a configuration for our encodings and allow Perl 6 to tell MoarVM if it wanted to encode strictly according to the standard or to be more lenient.

I added a new :strict option to open, encode and a few others to allow you to specify if it should be encoding strict or not strict. In the needs of backwards compatibility it still defaults to leniently encoding and decoding. Strict is planned to become the default for Perl 6 specification 6.e.

Replacements

Some of our other encodings had support for 'replacements'. If you tried to encode something that would not fit in the target encoding, this allowed you to supply a string that could be one or more characters which would but substituted instead of causing MoarVM to throw an exception.

Once I had the strictness nailed down I was able to add support for replacements so one could have the ability to write data in a strict mode while still ensuring all compatible characters would get written properly, and you did not have to choose between unstrict and writing incompatible files and strict and having the encoding or file write failing when you really needed it not to.

Shift-JIS

Encodings are not without difficulty. As with the previous encodings I talked about, Shift-JIS would not be without decisions that had to be made. With Shift-JIS, the question became, "which Shift-JIS?".

You see, there are dozens of different extensions to Shift-JIS, in addition to original Shift-JIS encoding. As a variable length encoding, most of the one byte codepoints had been taken while there were many hundreds of open and unallocated codepoints in the two byte range. This saw the wide proliferation of manufacturer specific extensions which other manufacturers may adopt while adding their own extensions to the format.

Which of the dozens of different Shift-JIS encodings should we support? I eventually decided on windows-932 because that is the standard that is used by browsers when they encounter Shift-JIS text and encompasses a great many symbols. It is the most widely used Shift-JIS format. This would allow us to support the majority of Shift-JIS encoded documents out there, and the one which web browsers use on the web. Most but not all the characters in it are compatible with the other extensions, so it seemed like it was the sensible choice.

The only notable exception to this is that windows-932 is not totally compatible with the original Shift-JIS encoding. While the original windows-932 encoding (and some extensions to it) map the ASCII’s backslash to the yen symbol ¥, windows-932 keeps it to the backslash. This was to retain better compatibility with ASCII and other formats.

UTF-16

While MoarVM had a UTF-16 encoder and decoder, it was not fully featured.

  • You could encode a string into a utf16 buffer:

    • "hello".encode('utf16') #> utf16:0x<68 65 6c 6c 6f>

  • You could decode a utf16 buffer into a string:

    • utf16.new(0x68, 0x65, 0x6C, 0x6C, 0x6F).decode('utf16') #> hello

That was about it. You couldn’t open a filehandle as UTF-16 and write to it. You couldn’t even do $fh.write: "hello".encode('utf16') as the write function did not know how to deal with writing a 16 bit buffer (it expected an 8-bit buffer).

In addition there was no streaming UTF-16 decoder, so there was no way to read a UTF-16 file. So I set out to work, first allowing us to write 16-bit buffers to a file and then being able to .print a filehandle and write text to it.

At this point I knew that I would have to confront the BOM in the room, but decided to first implement the streaming decoder and ensure all of our file handle operations worked.

The BOM in the Room

You may be noticing a theme here. You do not just implement an encoding. It does not exist in a vacuum. While there may be standards, there may be multiple standards. And those standards may or may not be followed in practice or it may not be totally straightforward.

Endianess defines which order the bytes are in a number. Big endian machines will store a 16-bit number with the larger section first, similar to how we write numbers, while little endian machines will put the smallest section first. This only matters for encoding numbers that are more than one byte. UTF-16 can be either big endian or little endian. Meaning big and little endian files will contain the same bytes, but the order is different.

Since swapping the two bytes of a 16-bit integer causes a different integer instead of an invalid one, the creators of UTF-16 knew it was not possible to determine with certainty the endianess of a 16 bit number. And so the byte order mark was created, a codepoint that would be added at the start of a file to signify which endianess the file was. Since they didn’t want to break already existing software, they used a "Zero width no-break space" (ZWNBSP) and designated that a ZWNBSP with bytes reversed would be invalid in UTF-16, a "non-character".

If the BOM was not removed, it would not be visible since it is zero width. If your program opens a file and sees a byte order mark it knew it was in the correct endianess. If it’s the "non-character" then it knew it had to swap the bytes when it read the file.

The standard states that utf16 should always use a BOM and that when reading a file as utf16 the BOM should be used to detect the endianess. It states the BOM is not passed through as it is assumed to not be part of the actual data. If it doesn’t exist then the system is supposed to decode as the endianess that the context suggests. So you get a format where you may lose the first codepoint of your file if that codepoint happens to be a zero width non-break space.

For utf16be (big endian) and utf16le (little endian) the standard states the byte order mark should not exist, and that any zero width no-break space at the start of a file is just that, and should be passed through.

Standards and practice are not identical and in practice many programs will remove a leading zero width non-break space even if set explicitly to utf16be or utf16le. I was unsure which route I should take. I looked at how Perl 5 handled it and after thinking for a long time I decided that we would follow the spec. Even though other software will get rid of any detected byte order mark, I think it’s important that if a user specifies utf16be or utf16le, they will always get back the same codepoints that they write to a file.

Current Work

I am currently working on adding support so that when you write a file in 'utf16' it will add a byte order mark, as utf16 is supposed to always have one. Until this is added you can write a file with Perl 6 on one computer using the 'utf16' encoding which will not decode correctly using the same 'utf16' setting if the two computers are of different endianess.

Since there was no functionality for writing utf-16 to a file previously, there should be no backwards compatibility issues to worry about there and we can set it to add a byte order mark if the utf16 encoder is used.

Release 2018.09

In the last release utf16, utf16le and utf16be should work, aside from utf16 not adding a byte order mark on file write. Anyone who uses utf16 and finds any issues or comments are free to email me or make an issue on the MoarVM or Rakudo issue trackers.

brrt to the future: Template Compiler Update

Published by Bart Wiegmans on 2018-09-04T17:30:00

Hi everybody. After samcv++ released MoarVM again, it was finally time to introduce some updates to the expression template compiler.

As you may or may not know, the expression JIT backend maps MoarVM opcodes to its internal representation via expression templates. At runtime (during the JIT compilation phase), these templates are combined to form an expression tree. The expression template language remains somewhat underdocumented, but quite a few brave developers have still ventured to add templates. With the new template compiler, a few things will change:

(macro: ^foo (,bar)
(let (($obj ...))
(add $obj ,bar)))
(template: foobar
(let (($obj ...))
(^foo $obj))

Prior to these patches, this would expand to something like:

(template: foobar
(let (($obj ...))
(let (($obj ...)) # name conflict is here
(add $obj $obj))) # which $obj?

Although this code would previously fail during compilation, having to deal with such conflicts in remote code segments is annoying. But now named declarations are resolved prior to expanding the inner macro, and this means that the $obj for macro ^foo is resolved to the let: within that macro, and the outer $obj in the template refers to the outer declaration, as if you'd written:

(template: foobar
(let (($obj1 ...))
(let (($obj2 ...))
(add $obj2 $obj1)))

I believe that this makes writing templates safer and simpler, catching more errors at compile time and fewer at runtime. Happy hacking!

my Timotimo \this: Faster FASTA, please

Published by Timo Paulssen on 2018-08-31T16:52:11

Faster FASTA, please

The other day on Stack Overflow: User Beuss asked "What is the best way for dealing with very big files?". The question features the task of parsing a FASTA file, which is a common file format in Bioinformatics. The format is extremely simple. It's based on lines, where a line starting with a > gives an identifier which is then followed by any number of lines containing protein sequences or nucleic acid sequences. The simplest you'll see will contain the letters A, C, G, and T, though there are far more letters that have meaning, and extra symbols. The "parsing" part of the question was limited to efficiently splitting the file up in its individual sequences and storing each sequence in a hash keyed on its identifier.

The end of the question asks, specifically, "Did I reach the maximum performances for the current version of Perl6 ?". This immediately caught my eye, of course.

In this post I'd like to take you through my process of figuring out the performance characteristics and potential gains for a program like this.

Let's start with the original code suggested by Beuss and make a few tiny modifications: The original Stack Overflow code was lacking the class seq, but as far as I could tell it needed nothing but two attributes. There was a line that would output every id it came across, but I/O like that is really slow, so I just removed it. I also added very simple timing code around the three stages: Slurping, splitting, and parsing. Here's the result:

my class seq {
  has $.id;
  has $.seq;
}
my class fasta {
  has Str $.file is required;
  has %!seq;

  submethod TWEAK() {
    my $id;
    my $s;
    my $now = now;

    say "Slurping ...";
    my $f = $!file.IO.slurp;
    say "slurped in { now - $now }";
    $now = now;

    say "Splitting file ...";
    my @lines = $f.split(/\n/);
    say "split in { now - $now }";
    $now = now;

    say "Parsing lines ...";
    for @lines -> $line {
      if $line !~~ /^\>/ {
          $s ~= $line;
      }
      else {
        if $id.defined {
          %!seq{$id} = seq.new(id => $id, seq => $s);
        }
        $id = $line;
        $id ~~ s:g/^\>//;
        $s = "";
      }
    }
    %!seq{$id} = seq.new(id => $id, seq => $s);
    say "parsed in { now - $now }";
  }
}

sub MAIN()
{
    my $f = fasta.new(file => "genome.fa");
}

And let's generate an example genome.fa file to test it out with. This one-liner will give you a genome.fa file that's 150_000_200 characters long, has 2_025_704 lines in total, 192_893 of which are lines with identifiers, and the remaining 1_832_811 lines are sequence lines with 80 characters each.

perl6 -e 'srand(2); my $f = "genome.fa".IO.open(:w); while $f.tell < 150_000_000 { $f.put(">" ~ flat("A".."Z", "a".."z", "0".."9", "_", "-").roll((5..7).pick).join); $f.put(<A C G T>.roll(80).join()) for ^(3..16).pick }'

This script has not been optimized for performance at all ;)

Okay, we're just about ready to go with this. Let's have a look at how long only the first two stages take by just hitting Ctrl-C after it outputs "Parsing lines ...":

Slurping ...
slurped in 1.4252846
Splitting file ...
split in 30.75685953
Parsing lines ...

Huh. That's pretty darn slow, isn't it? 67k lines split per second? We should really be able to do better than that. Let's zoom in on the slurping and splitting:

say "Slurping ...";
my $f = $!file.IO.slurp;

say "Splitting file ...";
my @lines = $f.split(/\n/);

My experience with Rakudo has taught me many times that currently our regexes are much more expensive than they have to be. Even though this regex is extremely simple, the regex engine is currently an all-or-nothing deal.

Let's use the built-in method lines on Str instead and see how that fares:

Slurping ...
slurped in 1.4593975
Splitting file ...
split in 2.9614959
Parsing lines ...
parsed in 32.9007177

Cool, that's already a 10x as much performance for just the splitting! If I had let the program run to completion before, the whole program's run time would have been 50% slurping and splitting and 50% parsing. But if you look at the parsing part, there's two more regexes in there, too:

for @lines -> $line {
  if $line !~~ /^\>/ {
      # ...
  }
  else {
    # ...
    $id ~~ s:g/^\>//;
    $s = "";
  }
}

Can we do the same thing without regex here, too? Sure! $line !~~ /^\>/ is equivalent to the much, much faster not $line.starts-with(">"), and since we already know in that branch of the if statement that the line starts with > we can replace $id ~~ s:g/^\>// with just $id .= substr(1). Let's see what happens to the performance now:

Slurping ...
slurped in 1.463816
Splitting file ...
split in 2.9924887
Parsing lines ...
parsed in 3.8784822

Cool. It's about 8.5x as much speed. In total, it used to take about 1m10s, now it takes 8.6s.

Second implementation

Let's switch gears for a bit. Before I came into the discussion, Stack Overflow user Christoph already came up with a good answer. They also immediately had the instinct to cut out the regex/grammar engine to get a speed-up. The first suggested piece of code looks like this:

my %seqs = slurp('genome.fa', :enc<latin1>).split('>')[1..*].map: {
    .[0] => .[1..*].join given .split("\n");
}

It works like this: It splits the whole file by the > character. Now every chunk after the split is a string consisting of the ID line and all FASTA sequence lines that come after it and before the next ID line - except of course if there's a > in the middle of some line. [1]

Since the file itself starts with a > character [2] we have to skip the very first entry, as it would just be an empty string. The code does that with array slice syntax [1..*]. Then in the block it splits the individual strings that each start with the ID line followed by the sequence data into lines.

I like this answer a lot. It's short and sweet, but it's not golfed to the point of being unreadable. Let's see how it performs!

time perl6 christoph-fasta.p6 
38.29user 0.53system 0:38.85elapsed 99%CPU (0avgtext+0avgdata 1040836maxresident)k

Whoops, that's very slow compared to our optimized code from above! Since this program is mostly methods from built-in classes, we'll most likely have to find more efficient versions of what we've got in the code right now.

The slurp and split invocations in the beginning are probably as fast as we can get, but what about using [1..*] to skip the first element?

split returns a Seq object, which is the Perl 6 user's way to work with iterators. One important feature of Seq is that it throws away values after they have been consumed. However, if you use array accesses like [1], [4, 5, 2, 1] it can't do that. The code doesn't know if you're going to have lower indices later in the list, so writing that last example would lead to an error. So it caches the values - literally by calling the cache method on the Seq.

Surely there's a way to skip a single element without having to memoize the resulting list? Turns out that there is: The skip method is one of the few methods on the Seq class itself! Let's go ahead and replace the first [1..*] with a call to skip. Another thing we can do is replace .[0] with .head and the other .[1..*] with a .skip(1) as well. For these to work we'll have to add our own .cache call on the .split, though. Here's the code we end up with:

my %seqs = slurp('genome.fa', :enc<latin-1>).split('>').skip(1).map: {
    .head => .skip(1).join given .split("\n").cache;
}

And here's the run time:

time perl6 christoph-fasta-no-circumfix.p6 
12.18user 0.57system 0:12.79elapsed 99%CPU (0avgtext+0avgdata 1034176maxresident)k

That's already better, but no-where near where I'd like it to be. However, I couldn't yet come up with a way to make this variant any faster.

Third Implementation

Stack Overflow user Christoph also had a second implementation in their answer. It's based on finding the next interesting character with the .index method on strings. Let's see how it compares! Here's the code in full:

my %seqs;
my $data = slurp('genome.fa', :enc<latin1>);
my $pos = 0;
loop {
    $pos = $data.index('>', $pos) // last;

    my $ks = $pos + 1;
    my $ke = $data.index("\n", $ks);

    my $ss = $ke + 1;
    my $se = $data.index('>', $ss) // $data.chars;

    my @lines;

    $pos = $ss;
    while $pos < $se {
        my $end = $data.index("\n", $pos);
        @lines.push($data.substr($pos..^$end));
        $pos = $end + 1
    }

    %seqs{$data.substr($ks..^$ke)} = @lines.join;
}

And a first timing run:

time perl6 christoph-two.p6 
15.65user 0.44system 0:16.05elapsed 100%CPU (0avgtext+0avgdata 1011608maxresident)k

Now that doesn't look too bad. It's already faster than the previous implementation's first version, but a bit slower than the final version I presented just above.

Let's grab a profile with the profiler and see what we can find!

Opening up the routines tab and sorting by exclusive time, we immediately see something rather suspicious:

Faster FASTA, please

Here we can see that the Range construction operator ..^ is responsible for a big chunk of time – almost a third – and the substr method is responsible for almost a quarter. The new method just below that isn't actually interesting, as it's just always called by the ..^ operator, and as such has its time captured in the operator's inclusive time.

So what are we using ..^ for? The code uses the form of substr that passes a Range instead of a start and length argument. If you have a start and an end position like in this case, it's a whole lot nicer to look at. Unfortunately, it seems to suffer from a large amount of overhead.

Let's rewrite the code to use the .substr($start, $amount) form instead. The transformation is very simple:

@lines.push($data.substr($pos..^$end));
# becomes
@lines.push($data.substr($pos, $end - $pos));
# and
%seqs{$data.substr($ks..^$ke)} = @lines.join;
# becomes
%seqs{$data.substr($ks, $ke - $ks)} = @lines.join;

And now we can time the result:

time perl6 christoph-two-no-range.p6 
8.34user 0.44system 0:08.72elapsed 100%CPU (0avgtext+0avgdata 1010172maxresident)k

Great result! We've shaved off around 45% of the run time with just our first find!

What else can we do? Let's see if sprinkling some native types would help gain performance for this script. Let's make all the integer variables be typed int, which is a native 64bit integer instead of the potentially infinitely big Int. We can also turn the @lines array into a native string array, saving us one layer of indirection for every entry we have. Here's the full code:

my %seqs;
my $data = slurp('genome.fa', :enc<latin1>);
my int $pos = 0;
loop {
    $pos = $data.index('>', $pos) // last;

    my int $ks = $pos + 1;
    my int $ke = $data.index("\n", $ks);

    my int $ss = $ke + 1;
    my int $se = $data.index('>', $ss) // $data.chars;

    my str @lines;

    $pos = $ss;
    while $pos < $se {
        my int $end = $data.index("\n", $pos);
        @lines.push($data.substr($pos, $end - $pos));
        $pos = $end + 1
    }

    %seqs{$data.substr($ks, $ke - $ks)} = @lines.join;
}

And here's the timing:

time perl6 christoph-two-no-range-native-int.p6 
6.29user 0.36system 0:06.60elapsed 100%CPU (0avgtext+0avgdata 1017040maxresident)k

Oh, huh. That's not quite an amazing improvement, but let's see if we can push it further by turning $data into a native string! Surely that'll give us a little speed-up?

time perl6 christoph-two-no-range-native-int-str.p6 
7.16user 0.36system 0:07.45elapsed 100%CPU (0avgtext+0avgdata 1017076maxresident)k

Isn't that interesting? Turns out that in order to call a method on a native string, rakudo has to create a temporary Str object to "box" the value into something that can have methods and such. That means that every method call on $data will create one shiny Str object for us. That's not quite what we want ☺

Conveniently, there are also sub forms of index and substr. We can either rewrite the method calls to sub calls and move the invocant (this is how we refer to the thing the method is called on) to be the first argument, or we can use the convenient "use sub but with method syntax" feature Perl 6 has. It looks like $data.&substr($ks, $ke - $ks) and all it does is put the invocant as the first argument of the sub and the rest of the arguments follow.

Unfortunately, there aren't actually candidates for these subs that will take native strings and ints, and so we'll end up with the same problem!

Eliminating boxed objects, Str, Int, Num, and similar things, is actually on the agenda for MoarVM. Recent improvements to the dynamic specializer "spesh" by jnthn have been laying the foundation on top of which improving this situation should be doable.

Illegal Performance Gains

So is this the most we can get? Not quite. That was actually a pun, because there's a thing called NQP, which stands for "Not Quite Perl". It's both a separate language with much stricter rules that rakudo itself is written in, and the namespace under which most of the low-level operations that the VM knows are available. These ops are not part of the Perl 6 Language Specification, and the rakudo developers do not guarantee that any code you write using NQP ops will continue working on newer versions of rakudo.

What it does allow us to do is find out where the performance ceiling is, roughly. I'll first write the code to use NQP ops, and then I'll explain what I mean by that.

use nqp;

my Mu $seqs := nqp::hash();
my str $data = slurp('genome.fa', :enc<latin1>);
my int $pos = 0;

my str @lines;

loop {
    $pos = nqp::index($data, '>', $pos);

    last if $pos < 0;

    my int $ks = $pos + 1;
    my int $ke = nqp::index($data, "\n", $ks);

    my int $ss = $ke + 1;
    my int $se = nqp::index($data ,'>', $ss);

    if $se < 0 {
        $se = nqp::chars($data);
    }

    $pos = $ss;
    my int $end;

    while $pos < $se {
        $end = nqp::index($data, "\n", $pos);
        nqp::push_s(@lines, nqp::substr($data, $pos, $end - $pos));
        $pos = $end + 1
    }

    nqp::bindkey($seqs, nqp::substr($data, $ks, $ke - $ks), nqp::join("", @lines));
    nqp::setelems(@lines, 0);
}

Let's go through it piece by piece. The first line is new, it's use nqp;. It's a synonym for use MONKEY-GUTS; which is a bold declaration meaning in essence "I know what I'm doing, and I deserve whatever I've got coming to me".

We'll use a low-level hash object taken from the nqp world by binding to a scalar variable. We use the type constraint Mu here, because nqp types aren't part of the Perl 6 type hierarchy, and thus will not go through a type check for Any, which is the default type constraint for scalar variables. Also, it does not do the Associative role, which is why we can't bind it to a variable with a % sigil.

Next, we'll pull out the @lines array, so that we don't have to allocate a new one for every round through the loop. We don't have to use nqp::list_s() here like with the hash, because the native string array you get from my str @foo has barely any overhead if we use nqp ops on it rather than methods.

I've removed usage of the // operator, though I am not actually sure how much overhead it has.

The signature of nqp::index is the same as the three-argument sub version of index, and the same is true for the nqp::substr op. There's also an nqp::join op that will only accept a native (or literal) string as first argument and a native string array as the second argument.

You'll also notice that the $end variable is now outside of the inner loop. That has a relatively simple reason: A block that introduces lexical variables cannot be inlined into the outer block. That means that the inner block has to be invoked as a closure, so that it has access to all of the relevant variables. This adds the combined overhead of invoking a code object and of taking a closure. The Garbage Collector has to sweep all of those closures up for us. It'll be best not to generate them in the first place.

We use the nqp op nqp::push_s to add to the @lines array because the regular nqp::push op works with "objects", rather than native strings.

Then there's something that has no corresponding piece of code in the previous version: nqp::setelems(@lines, 0). Since we keep the @lines array around instead of building a new one every time, we have to empty it out. That's what nqp::setelems does, and it's very cheap.

A profile of this code tells us that all that's left being allocated is Str objects, exactly 192_899 of them. This comes from the fact that the hash wants to store objects, not native strings.

Let's see what the run time is!

time perl6 christoph-two-no-range-native-nqp.p6 
2.04user 0.33system 0:02.27elapsed 104%CPU (0avgtext+0avgdata 1004752maxresident)k

Whew! Our fastest implementation so far took 6.6s, now we're down to 2.3s, which is close to a third of the time the second-fastest version takes.

What's a "performance ceiling"?

Everything our code does will at some point end up using nqp:: ops to actually do work. Have a look at the substr method of Str, the index method of Str, the push method of strarray, and the ASSIGN-KEY method of Hash, that sits behind postcircumfix:<[ ]>. In between our code and these ops there are often multiple layers of methods that make things more comfortable to work with, or check values for validity.

Rakudo's static optimizer already works towards simpler code consisting of fewer calls. For example it would replace a call to infix:<+> with a low-level nqp::add_i op if it knows only native ints are involved. MoarVM's dynamic specializer has a lot more knowledge to work with, as it watches the code during execution, and can speculatively inline sub and method calls. After inlining, more optimizations are available, such as removing boxing that was necessary for passing arguments into, and returning the result out of the routine – this is currently being worked on!

If the MoarVM specializer were flawless, it ought to be able to generate the equivalent of what I coded up by hand. It will not do something as bold as keeping that one array around between rounds and just clearing it at the right moment, as it is currently not able to prove that the array doesn't get stashed away somewhere. But all in all, most of what I did should be achievable with more intelligence in the specializer.

The word "performance ceiling" is still not quite accurate, though. There's still a lot of optimization potential in the JIT compiler, for example. Bart Wiegmans just blogged about a benchmark where recent improvements to MoarVM got us to the point where the code was only 30% slower than an equivalent implementation in C. That was mostly due to the focus of the code being floating point operations, which likely take so long individually that imperfect code-gen is less of a problem.

But this is about the most we can get from the current version of rakudo, unless we find a better algorithm to do what we want.

The Elephant in the RAM

One thing that you've surely noticed is that this program uses about one gigabyte of memory at its highest point (that's what "maxresident" means). Sadly, this is a property of MoarVM's string implementation. In order for grapheme-level access to be fast ("linear time"), we upgrade strings to 32 bits per grapheme if needed, rather than storing strings as utf8 internally. Our strings also support 8 bits per character storage, which I had expected to be used here, but something in the machinery upgrades the string data from 8 bits to 32 bits, even though all character values ought to fit.

In the medium to far future, we'll also get strings that sacrifice linear time access for storage efficiency, but we're not at that point just yet.

Is there something else we could do to get around this? Sure! Instead of saving the string we cut out of the source file with substr and concatenated with join, we could save the start and end value of every piece of string in a native int array. We could implement a Hash subclass or compose in a role that grabs the data from the source file whenever the user asks for it. Native int arrays are much faster to GC than string arrays, and if you instead hold an index into a single giant int array in the hash, you can reduce the pressure on the GC even further!

That's a task for another post, though, as this one rapidly approaches 4k words.

Yet another task would be to write the same program in perl 5, python, and/or ruby. It should be interesting to compare performance characteristics among those. Surely our fastest code is still slower than at least one of these, but having a target in sight could help figure out which parts exactly are slower than they should be.

I personally don't code any ruby or perl 5, so I'd be happy if someone would contribute those implementations!

Parting QWORDS

Thanks for sticking with me for the duration of this huge post, and thanks to raiph for requesting this article. It may have been a bit more work than I had anticipated, but it was fun, and hopefully it is interesting for you readers!

And here's the QWORDS I promised: 0x7fffffffd950, 0x7ffff3a17c88, and 0x7ffff62dd700.

Have a good time, and see you in the next one!
  - Timo


  1. This ought to be a relatively simple fix. Split by \n> instead of >, and handle the very first blob differently, because it now starts with a > still left in it. ↩︎

  2. We're ignoring the possibility of adding comments to the beginning of the file, or anywhere in the file, really. ↩︎

brrt to the future: A Curious Benchmark

Published by Bart Wiegmans on 2018-08-25T15:57:00

Hi hackers! I recently saw a curious benchmark passed round on the #moarvm channel. (I understand that this originates from Ovid during his Future of Perl 5 and 6 presentation, but I haven't seen it myself, so if I'm wrong, don't hesitate to correct me). It's curious because it runs on perl5 and perl6, and because the difference is… significant:

# reciprocal.pl
my $x = 0;
$x += 1/$_ for 1..50_000_000;
print "$x\n";

Perl 5 (5.24.1), on my laptop (Intel i7-4700HQ CPU @ 2.40GHz, 16GB ram), takes approximately 2.7s to print the value 18.3047492382933. Perl 6, on the same script, takes just shy of 2m18s, or nearly 140s. This is 51 times as much. Perl 5 is not known as a particularly fast language, but in this case perl 6 is really very slow indeed.

Let's try and do a little better. As pointed out by timotimo, the benchmark above is a pessimal case for rationals numbers, which perl 6 uses by default. Perl 5 uses floating point throughout. So we can do better by explicitly using floating point calculations in perl6:

# reciprocal.pl6
my $x = 0e0;
$x += 1e0/$_.Num for 1..50_000_000;
say $x;

This takes approximately 30s on my machine, approximately 5 times faster, but still over 11 times slower than perl5. (NB: for all these numbers I'm posting here, I didn't run exhaustive tests and calculate the statistics, but I feel like this is reliable).

We can typically avoid some overhead in Perl 6 if we avoid using scalar containers by means of binding. We can avoid the dynamic lookup of $_ by replacing the for with a while loop. And we can skip the cast from Int to Num by using a Num iterator value. That gives us the following code:

# reciprocal-while.pl6
my $x := 0e0;
my $i := 0e0;
while (($i := $i + 1e0) < 5e7) {
$x := $x + 1e0/$i;
}
say $x;

This reduces the run time to approximately 26.5s. So instead of well over 11 times slower than perl 5, perl 6 is now a little less than 10 times slower.
I tried using native types, but that increased the run time to up to 36s. Native type performance (except for native typed arrays) has so far not met expectations for perl 6. (I understand that this is due to excessive boxing and unboxing, unfortunately). So it seems that I failed to make a perl6 program that performs comparably to perl 5.

And yet…

With all due respect to the perl 5 (and perl 6) developers, I think MoarVM ought to be able to do better. MoarVM has support for native-typed values and operators, the perl interpreter does not. It has a dynamic specializer and JIT compiles to native code, the perl interpreter does not. I should expect MoarVM to do better on this benchmark. (Otherwise, what have I been doing with my life, the last few years?)

Let's try the secret weapon: NQP. NQP stands for Not Quite Perl and it is the language the rakudo compiler is built in. It acts like a 'bootstrap' language and compatibility layer between the various backends of rakudo perl 6, such as MoarVM, Java and Javascript, and in the near future Truffle. I like to think that it relates to MoarVM in the same way that C relates to contemporary CPUs - it is a sort of low level, high level language. Although NQP fully support perl6 classes, regular expressions and grammars, it has no support for ranges or C-style for loops, so it does tend to look a bit primitive:

# reciprocal-boxed.nqp
my $x := 0e0;
my $i := 1e0;
while ($i < 5e7) {
$x := $x + 1e0/$i;
$i := $i + 1e0;
}
nqp::say("$x");

This version uses boxed objects and takes (on my machine) approximately 12.5s. If you recall, perl 5 took 2.7s, so this is just a bit less than 5 times slower than perl 5. Still not very satisfying though.

Let's improve this version a little bit and add native types here. The only difference between this code and the code above it, is that we have explicitly opted to use num values for $x and $i.

# reciprocal-native.nqp
my num $x := 0e0;
my num $i := 1e0;
while ($i < 5e7) {
$x := $x + 1e0/$i;
$i := $i + 1e0;
}
nqp::say("$x");

This code, with JIT enabled, consistently runs in approximately 0.28s on my machine. That is not a typing error. It prints the correct result. I emphatically want you to try this at home: simply save it as reciprocal.nqp and run time nqp reciprocal.nqp. (With JIT disabled, it runs in 2.4s, which is (finally) a bit faster than perl 5 in the interpreter).

Just out of curiosity, I tried comparing this result with the following C code:
 
#include <stdio.h>

int main(int argc, char **argv) {
double x = 0.0;
double i;
for (i = 1.0; i < 5e7; i += 1.0)
x += 1.0/i;
printf("%f", x);
}

On my machine, this takes approximately 0.22s per run, which means that NQP on MoarVM, using native types, is a little more than 1.3x slower than compiled C, excluding the compilation time of the C program. The NQP program does include JIT compilation.

For the record, the C compiled code is much simpler and faster than that generated by the MoarVM JIT - 75 bytes for C 'main' vs 1139 bytes for the NQP 'mainline' (149 bytes for the hot loop). So there is much to improve left, for sure. (EDIT: I originally wrote this in a rather confusing way, but the C code was always the shorter version).

So what does that tell us? Is perl6 50 times slower than perl5, or is NQP just 30% slower than C? There is actually much more to learn from the relative performance of these programs:
After I wrote this (but before publishing), I reran the benchmarks with the new branch postrelease-opts. The results were rather different and encouraging (units in seconds):

testmasterpostrelease-opts
reciprocal.pl14051
reciprocal.pl6316.6
reciprocal-while.pl6264.6
reciprocal-boxed.nqp123.6
reciprocal-native.nqp0.270.25

Congratulations to jnthn++ and timotimo++ for this fantastic result. As I understand it, we expect to merge this branch after the release of MoarVM 2018.08.

As always, benchmarks should be taken with a grain of salt - results do not always generalize cleanly to production code. But I hope this has given some insights into the performance characteristics of perl 6, and I think it highlights some areas of interest.

PS. The postrelease-opts has taken the place of the masterbranch as the mainline for development, as we aim to get master fit for a release. Personally, I'd rather have master open for development and a release branch for cutting a stable release. I expect most users get MoarVM from a specific revision via MOAR_REVISION anyway, so having master be the 'development' branch should cause little harm.

my Timotimo \this: The first public release!

Published by Timo Paulssen on 2018-08-15T14:52:11

Hello esteemed readers, and thank you for checking in on my progress. Not a full month ago I showed off the GC tab in the previous post, titled "Wow check out this garbage". Near the end of that post I wrote this:

I had already started the Routine Overview tab, but it's not quite ready to be shown off. I hope it'll be pretty by the time my next report comes out.

Well, turns out I got a whole lot of work done since then. Not only is the Routine tab pretty, but there's also a Call Graph explorer beside it. This post has the details, and at the end I'll give you the link to the github repository where you can get the code and try it out for yourself!

Routine Tab

Routine Overview

Now, the simplest part of the Routine tab is its overview function. Every routine that has been called while the profiler was recording shows up here. Here's a screenshot so you can understand what I'm referring to:

Selection_036

For comparison, here's the old profiler's Routine Tab

Selection_037

There's actually a lot of differences. Going from the old to the new, the Interp / Spesh / Jit column has disappeared, and with it the OSR badges. Also, the table headers are no longer clickable (to change the sorting order) and there is no filter search field. Both of these features will make a come-back in the new profiler's UI as well, though!

There are also additions, though: There's now a column labelled "Sites", some of the filename + line texts are clickable (they take you directly to github, though opening the files locally in an editor is a feature on my wish-list), and there's a column of mysterious buttons. On top of that, you can now see not only the exclusive / inclusive times for each routine, but also how much time that is when divided by the number of entries.

I wonder what happens when I click one of these!

Expanding

Selection_038

Neat, clicking the button expands an extra section below the routine. It has three tabs: Callees, Paths, and Allocations. Let's go through them one by one.

Callees

Listed here are all routines that got called by the parent routine (in this case ACCEPTS from the Regex source file). They are ordered by inclusive time, as opposed to the outer list which is ordered by exclusive time. [1]

Since there is now a parent/child relationship between the routines, there's also the number of entries per entry in the entries column. That's simply the entries of the child divided by the entries of the parent. This number can tell you how often another routine is mentioned, or what the probability for the child being called by the parent is.

Paths, and what's this about "Sites"?

Selection_039

The next tab you can open in the expanded view is called "Paths". Here you can see a vaguely tree-shaped table with four rows. These rows actually correspond to the Sites column that I have not explained yet. That's because the number of Sites corresponds directly to the number of rows in this table, or the number of leafs in the tree it displays.

The same Routine can behave in different ways depending on where it was called from. Normally, a difference in arguments passed is the main cause of different behaviour, but it's very likely that each unique location in the program will call the Routine the same way every time. Such a "location" is sometimes called a "Call Site", i.e. the site where a call resides. A Site in the profiler's nomenclature refers to one specific path from the outermost routine of the profile to the given Routine. In the screenshot above, all paths to ACCEPTS go through to-json either once, twice, or three times. And every path goes through str-escape.

The names in the table/tree (trable?) are all clickable. I can tell you right now, that they bring you right over to the Call Graph. More on that later, though.

Allocations

Selection_040

This is a small one, at least for ACCEPTS. It has one row per type, and splits the number of objects created for each type into before spesh and after spesh/jit. Coincidentally, the ACCEPTS method is already a good example for having the split: BOOTHash is just a lower-level hash class used in some internals. Notably, BOOTHash is used to pass named arguments to methods. Of course, many method invocations don't actually pass named arguments at all, and many methods don't care about named arguments either. Thankfully, spesh is competent at spotting this situation and removes all traces of the hash ever existing. The Scalar on the other hand seems to be used, so it stays even after spesh optimized the code.

There's also a Sites column here. This lets you spot cases where one or two sites differ strikingly from the others.

Call Graph Tab

Selection_041

Here's the new Call Graph tab. It's similar to the old one with one major omission. The new version of the call graph explorer currently lacks a flame graph (or icicle graph in this case). It will return later, of course.

Until then, there's a few improvements to be enjoyed. One of them is that the breadcrumbs navigation now works reliably, whereas in the previous profiler it tended to lose elements near the beginning or in the middle sometimes. On top of that, your browser's back and forward buttons will work between nodes in the call graph as well as the different tabs!

Something that's completely new is the Allocations section at the bottom of the page, shown in the screenshot below:

Selection_042

Here you can see that the Routine in question (it's the body of this for loop allocates Str and Scalar objects. The Str objects seem to be optimized by spesh again.

There's still two unexplained buttons here, though. The one at the bottom is labelled "Load inclusive allocations". Clicking on it reveals a second table of allocations, which is quite a lot bigger:

Selection_043

This view is about everything allocated by anything in the call graph from the current node downwards (towards the leaves, not towards the root. You know, because trees hang from the ceiling, right?). For something so close to the root in a rather deep call graph, you'll get quite a big list, and it's not very helpful in finding where exactly individual types are being allocated.

That's where the second button comes in. It says "Show allocations for all children" on it, and clicking it expands every row in the table of routines:

Selection_044

This way you can drill down from the root towards nodes that interest you.

What's missing?

Here's a little overview of what I'd like to include in the near and medium future:

Where can I get it?

I just uploaded all the code to my github. You can find it here. To use it, you will have to run npm install in the source folder to get all the javascript dependencies, and npm run build to compile all the javascript bundles. It will run a watcher process that will update as soon as any sources change, but if you're not working on the moarperf source code, you can just kill it after it has done its thing once.

Next, you'll have to install the dependencies of the Perl 6 program that acts as the back-end. You can do that with zef --depsonly install in the same folder as the META6.json. Please note that I haven't prepared the app for actually being installed, so don't do that yet :)

You can then start the backend with perl6 -Ilib service.p6 /path/to/profile.sql, where profile.sql is a profile generated with a commandline like perl6 --profile --profile-filename=profile.sql my_script.p6. Passing the filename to service.p6 on the commandline is optional, you can also enter it in the web frontend. By default, it is reachable on http port 20000 on localhost, but you can set MOARPERF_HOST and MOARPERF_PORT in the environment using the env or export commands of your shell.

A word of warning, though: It still has a bunch of rough edges. In some parts, loading data isn't implemented cleanly yet, which can lead to big red blocks with frowny faces. A refresh and/or doing things more slowly can help in that case. There's places where "there is no data" looks a lot like "something broke". Little usability problems all around.

I would appreciate a bit of feedback either on the github issue tracker, on #perl6 on the freenode IRC server, on reddit if someone's posted this article in /r/perl6, or via mail to the perl6-users mailing list or to timo at this website's domain name.

Thanks again to The Perl Foundation for funding my grant, and to you for reading my little report.

Have fun with the program!
  - Timo


  1. The reasoning behind the different default sorting modes is that in the first step you are likely more interested in routines that are expensive by themselves. Sorting by inclusive time just puts the entry frame first, and then gives you the outermost frames that quite often hardly do any work themselves. When you've found a routine that has a lot of exclusive time, the next step is - at least for me - to look at what routines below that take up the most time in total. That's why I prefer the inner routines list to be sorted by inclusive time. Once the user can change sorting in the UI i'll also offer a way to set the selected sorting as the default, i think. ↩︎

  2. The difference between managed and unmanaged bytes is that the managed bytes are what lands in the actual nursery, whereas unmanaged bytes refers to all kinds of extra data allocated for an Object. For example, an Array, Hash, or String would have a memory buffer somewhere in memory, and a header object pointing to that buffer in the nursery or gen2 memory pools. The managed size doesn't change for objects of the same type, which is why it's fine to put them in the allocations tabs. ↩︎

Zoffix Znet: The 100 Day Plan: The Update on Perl 6.d Preparations

Published on 2018-08-09T00:00:00

Info on how 6.d release prep is going

rakudo.org: Rakudo Star Release 2018.06

Published on 2018-08-06T00:00:00

Zoffix Znet: Introducing: Perl 6 Marketing Assets Web App

Published on 2018-08-05T00:00:00

Get your Perl 6 flyers and brochures

Zoffix Znet: Introducing: Newcomer Guide to Contributing to Core Perl 6

Published on 2018-08-02T00:00:00

Info on the new guide for newcomers

6guts: Redesigning Rakudo’s Scalar

Published by jnthnwrthngtn on 2018-07-26T23:54:45

What’s the most common type your Perl 6 code uses? I’ll bet you that in most programs you write, it’ll be Scalar. That might come as a surprise, because you pretty much never write Scalar in your code. But in:

my $a = 41;
my $b = $a + 1;

Then both $a and $b point to Scalar containers. These in turn hold the Int objects. Contrast it with:

my $a := 42;
my $b := $a + 1;

Where there are no Scalar containers. Assignment in Perl 6 is an operation on a container. Exactly what it does depending on the type of the container. With an Array, for example, it iterates the data source being assigned, and stores each value into the target Array. Assignment is therefore a copying operation, unlike binding which is a referencing operation. Making assignment the shorter thing to type makes it more attractive, and having the more attractive thing decrease the risk of action at a distance is generally a good thing.

Having Scalar be first-class is used in a number of features:

And probably some more that I forgot. It’s powerful. It’s also torture for those of us building Perl 6 implementations and trying to make them run fast. The frustration isn’t so much the immediate cost of the allocating all of those Scalar objects – that of course costs something, but modern GC algorithms can throw away short-lived objects pretty quickly – but also because of the difficulties it introduces for program analysis.

Despite all the nice SSA-based analysis we do, tracking the contents of Scalar containers is currently beyond that. Rather than any kind of reasoning to prove properties about what a Scalar holds, we instead handle it through statistics, guards, and deoptimization at the point that we fetch a value from a Scalar. This still lets us do quite a lot, but it’s certainly not ideal. Guards are cheap, but not free.

Looking ahead

Over the course of my current grant from The Perl Foundation, I’ve been working out a roadmap for doing better with optimization in the presence of Scalar containers. Their presence is one of the major differences between full Perl 6 and the restricted NQP (Not Quite Perl), and plays a notable part in the performance difference between the two.

I’ve taken the first big step towards improving this situation by significantly re-working the way Scalar containers are handled. I’ll talk about that in this post, but first I’d like to provide an idea of the overall direction.

In the early days of MoarVM, when we didn’t have specialization or compilation to machine code, it made sense to do various bits of special-casing of Scalar. As part of that, we wrote code handling common container operations in C. We’ve by now reached a point where the C code that used to be a nice win is preventing us from performing the analyses we need in order to do better optimizations. At the end of the day, a Scalar container is just a normal object with an attribute $!value that holds its value. Making all operations dealing with Scalar container really be nothing more than some attribute lookups and binds would allow us to solve the problem in terms of more general analyses, which stand to benefit many other cases where programs use short-lived objects.

The significant new piece of analysis we’ll want to do is escape analysis, which tells us which objects have a lifetime bounded to the current routine. We understand “current routine” to incorporate those that we have inlined.

If we know that an object’s usage lies entirely within the current routine, we can then perform an optimization known as scalar replacement, which funnily enough has nothing much to do with Scalar in the Perl 6 sense, even if it solves the problems we’re aiming to solve with Scalar! The idea is that we allocate a local variable inside of the current frame for each attribute of the object. This means that we can then analyze them like we analyze other local variables, subject them to SSA, and so forth. This for one gets rid of the allocation of the object, but also lets us replace attribute lookups and binds with a level of indirection less. It will also let us reason about the contents of the once-attributes, so that we can eliminate guards that we previously inserted because we only had statistics, not proofs.

So, that’s the direction of travel, but first, Scalar and various operations around it needed to change.

Data structure redesign

Prior to my recent work, a Scalar looked something like:

class Scalar {
    has $!value;        # The value in the Scalar
    has $!descriptor;   # rw-ness, type constraint, name
    has $!whence;       # Auto-vivification closure
}

The $!descriptor held the static information about the Scalar container, so we didn’t have to hold it in every Scalar (we usually have many instances of the same “variable” over a programs lifetime).

The $!whence was used when we wanted to do some kind of auto-vivification. The closure attached to it was invoked when the Scalar was assigned to, and then cleared afterwards. In an array, for example, the callback would bind the Scalar into the array storage, so that element – if assigned to – would start to exist in the array. There are various other forms of auto-vivification, but they all work in roughly the same way.

This works, but closures aren’t so easy for the optimizer to deal with (in short, a closure has to have an outer frame to point to, and so we can’t inline a frame that takes a closure). Probably some day we’ll find a clever solution to that, but since auto-vivification is an internal mechanism, we may as well make it one that we can see a path to making efficient in the near term future.

So, I set about considering alternatives. I realized that I wanted to replace the $!whence closure with some kind of object. Different types of object would do different kinds of vivification. This would work very well with the new spesh plugin mechanism, where we can build up a set of guards on objects. It also will work very well when we get escape analysis in place, since we can then potentially remove those guards after performing scalar replacement. Thus after inlining, we might be able to remove the “what kind of vivification does this assignment cause” checking too.

So this seemed workable, but then I also realized that it would be possible to make Scalar smaller by:

This not only makes Scalar smaller, but it means that we can use a single guard check to indicate the course of action we should take with the container: a normal assignment, or a vivification.

The net result: vivification closures go away giving more possibility to inline, assignment gets easier to specialize, and we get a memory saving on every Scalar container. Nice!

C you later

For this to be really worth it from an optimization perspective, I needed to eliminate various bits of C special-case code around Scalar and replace it with standard MoarVM ops. This implicated:

The first 3 became calls to code registered to perform the operations, using the 6model container API. The second two cases were handled by replacing the calls to C extops with desugars, which is a mechanism that takes something that is used as an nqp::op and rewrites it, as it is compiled, into a more interesting AST, which is then in turn compiled. Happily, this meant I could make all of the changes I needed to without having to go and do a refactor across the CORE.setting. That was nice.

So, now those operations were compiled into bytecode operations instead of ops that were really just calls to C code. Everything was far more explicit. Good! Alas, the downside is that the code we generate gets larger in size.

Optimization with spesh plugins

talked about specializer plugins in a recent post, where I used them to greatly speed up various forms of method dispatch. However, they are also applicable to optimizing operations on Scalar containers.

The change to decontainerizing return values was especially bad at making the code larger, since it had to do quite a few checks. However, with a spesh plugin, we could just emit a use of the plugin, followed by calling whatever the plugin produces.

Here’s a slightly simplified version of the the plugin I wrote, annotated with some comments about what it is doing. The key thing to remember about a spesh plugin is that it is not doing an operation, but rather it’s setting up a set of conditions under which a particular implementation of the operation applies, and then returning that implementation.

nqp::speshreg('perl6', 'decontrv', sub ($rv) {
    # Guard against the type being returned; if it's a Scalar then that
    # is what we guard against here (nqp::what would normally look at
    # the type inside such a container; nqp::what_nd does not do that).
    nqp::speshguardtype($rv, nqp::what_nd($rv));

    # Check if it's an instance of a container.
    if nqp::isconcrete_nd($rv) && nqp::iscont($rv) {
        # Guard that it's concrete, so this plugin result only applies
        # for container instances, not the Scalar type object.
        nqp::speshguardconcrete($rv);

        # If it's a Scalar container then we can optimize further.
        if nqp::eqaddr(nqp::what_nd($rv), Scalar) {
            # Grab the descriptor.
            my $desc := nqp::speshguardgetattr($rv, Scalar, '$!descriptor');
            if nqp::isconcrete($desc) {
                # Has a descriptor, so `rw`. Guard on type of value. If it's
                # Iterable, re-containerize. If not, just decont.
                nqp::speshguardconcrete($desc);
                my $value := nqp::speshguardgetattr($rv, Scalar, '$!value');
                nqp::speshguardtype($value, nqp::what_nd($value));
                return nqp::istype($value, $Iterable) ?? &recont !! &decont;
            }
            else {
                # No descriptor, so it's already readonly. Return as is.
                nqp::speshguardtypeobj($desc);
                return &identity;
            }
        }

        # Otherwise, full slow-path decont.
        return &decontrv;
    }
    else {
        # No decontainerization to do, so just produce identity.
        return &identity;
    }
});

Where &identity is the identity function, &decont removes the value from its container, &recont wraps the value in a new container (so an Iterable in a Scalar stays as a single item), and &decontrv is the slow-path for cases that we do not know how to optimize.

The same principle is also used for assignment, however there are more cases to analyze there. They include:

Vivifying hash assignments are not yet optimized by the spesh plugin, but will be in the near future.

The code selected by the plugin is then executed to perform the operation. In most cases, there will only be a single specialization selected. In that case, the optimizer will inline that specialization result, meaning that the code after optimization is just doing the required set of steps needed to do the work.

Next steps

Most immediately, a change to such a foundational part of the the Rakudo Perl 6 implementation has had some fallout. I’m most of the way through dealing with the feedback from toaster (which runs all the ecosystem module tests), being left with a single issue directly related to this work to get to the bottom of. Beyond that, I need to spend some time re-tuning array and hash access to better work with these changes.

Then will come the step that this change was largely in aid of: implementing escape analysis and scalar replacement, which for much Perl 6 code will hopefully give a quite notable performance improvement.

This brings me to the end of my current 200 hours on my Perl 6 Performance and Reliability Grant. Soon I will submit a report to The Perl Foundation, along with an application to continue this work. So, all being well, there will be more to share soon. In the meantime, I’m off to enjoy a week’s much needed vacation.

samcv: Secure Hashing for MoarVM to Prevent DOS Attacks

Published on 2018-05-16T07:00:00

Hashes are very useful data structures and underlie many internal representations in Perl 6 as well as being used as themselves. These data structures are very nice since they offer O(1) insertion time and O(1) lookup time on average. Hashes have long been considered an essential feature for Perl, much loved by users. Though when exploited, hashes can cause servers to grind to a halt. New in Rakudo Perl 6 2018.5 will be a feature called hash randomization which does much to help protect against this attack. In this article I explain some hashing basics as well as how the attack against non-randomized hashing can work.

Table of Contents

Hashing Basics

Some hashing basics: when we use a hash, we take a string and come up with a unique integer to represent the string. Similar to how md5 or sha1 sums take an arbitrary amount of data and condense it into a shorter number which can identify it, we do a similar thing for strings.

my %hash; %hash<foo> = 10

In this code, MoarVM takes the string foo and performs a hashing function on it using a series of bitwise operations. The goal is to create a shorter number which allows us to put the foo key into one of the 8 buckets that MoarVM initializes when a hash is created.

8 Hash buckets

Our hashing code sets up a predefined number of buckets . When a bucket fills up to have 10 items it doubles the number of buckets. In normal operation the hashes will be randomly distributed, so it would take ≈47 keys added (≈47 is the average number of items to result in one bucket being filled to 10 items) before we have to expand the buckets the first time.

When the buckets are expanded, we will now have 16 buckets. In normal operation our previous ≈47 items should be evenly distributed into those 16 buckets.

The Attack

Without a random hash seed it is easy for an attacker to generate strings which will result in the same hash. This devolves to O(n️2) time for the hash lookup. This O(n2) is actually O(string_length * num_collisions). When we have hash collisions, that means that no matter how many times we double the number of buckets we have, the strings which have hash collisions will always remain in the same bucket as each other. To locate the correct string, MoarVM must go down the chain and compare each hash value with the one we’re looking for. Since they are all the same, we must fall back to also checking each string itself manually until we find the correct string in that bucket.

Hash collision

This attack is done by creating a function that essentially is our hashing function backward (for those curious see here for an example of code which does forward and backward hashing for Chrome V8 engine’s former hashing function). We hash our target string, t. We then use random 3 character sequences (in our case graphemes) and plug them into our backward hashing function along with the hash for our target t. The backward hash and the random character sequence are stored in the dictionary and the process is repeated until we have a very large number of backward hash’s and random 3 grapheme prefixes.

We can then use this dictionary to construct successively longer strings (or short if we so desire) which are the same hash as our target string t. This is a simplification of how the Meet-In-The-Middle attack works.

This has been fixed in most programming languages (Python, Ruby, Perl), and several CVE’s have been issued over the years for this exploit (See CVE’s for PHP, OCaml, Perl, Ruby and Python).

Assuming everything is fine for the next release I will also merge changes which introduce a stronger hashing function called SipHash. SipHash is meant to protect against an attacker discovering a hash secret remotely. While randomizing the seed makes this attack much harder, a determined attacker could discover the hash and if that is done they can easily perform a meet in the middle attack. SipHash was designed to solve the vulnerability of the hash function itself to meet-in-the-middle attacks. Both the randomization of the hash secret in addition with a non-vulnerable hashing function work work together to avert hash collision denial of service attacks.

While the hash secret randomization will be out in Rakudo 2018.05, SipHash is planned to be introduced in Rakudo 2018.06.

Randomness Source

On Linux and Unix we prefer function calls rather than reading from /dev/urandom. There are some very important reasons for this.

Relying on an external file existing is potentially problematic. If we are in a chroot and /dev is not mounted we will not have access to /dev/urandom. /dev/urandom is not special, it can be deleted by accident (or on purpose) or a sparse data file mounted in its place undetectable by programs. Trusting it simply because of its path is not ideal. Also, if we exhaust the maximum number of open file descriptors we will be unable to open /dev/urandom as well.

System Functions

On Windows we use the pCryptGenRandom which is provided by advapi32.dll since Windows XP.

Linux, FreeBSD, OpenBSD and MacOS all use system provided random calls (if available) to get the data rather than having to open /dev/urandom. All these OS’s guarantee these calls to be non-blocking, though MacOS’s documentation does not comment on it. This is mostly important in very early userspace, which bit Python when a developer accidentally changed the randomness source causing systems which relied on very early Python scripts to stop booting due to waiting for randomness source to initialize.

If the function doesn’t exist we fall back to using /dev/urandom. If opening or reading it fails, on BSD’s we will use the arc4random() function. In many BSD’s this is seeded from the system’s random entropy pool, providing us with a back up in case /dev/urandom doesn’t exist.

On Linux we use the getrandom() system call which was added to kernel 3.17 instead of using the glibc wrapper since the glibc wrapper was added much later than to the kernel.

On MacOS, Solaris and FreeBSD we use getrandom() while on OpenBSD we use getentropy().

User Facing Changes

From Rakudo Perl 6 2018.05, the order that keys are returned will be random between each perl6 instance.

perl6 -e 'my %hash = <a 1 b 1 c 1 d 1 e 1 f 1>; say %hash.keys'
(d f c a b e)
perl6 -e 'my %hash = <a 1 b 1 c 1 d 1 e 1 f 1>; say %hash.keys'
(e f a d c b)

This will also effect iterating a hash without sorting: for %hash { }

What Do I Have To Do?

Users and module developers should make sure that they explicitly sort hashes and not rely on a specific order being constant. If you have a module, take a look at the code and see where you are iterating on a hash’s keys and whether or not the order of processing the hash’s keys affects the output of the program.

# This should be okay since we are putting the hash into another hash, order
# does not matter.
for %hash.keys -> $key {
    %stuff{$key} = $i++;
}
# This can potentially cause issues, depending on where `@stuff` is used.
for %hash.keys -> $key {
    @stuff.push: $key;
}
# This should be OK since we are using is-deeply and comparing a hash with another
# hash
is-deeply my-cool-hash-returning-function($input), %( foo => 'text', bar => 'text', baz => 'text');
# Probably best to avoid using `is`. The `is` test function converts the input to a string before
# checking for equality, but works since we stringify it in sorted order.
is %hash,  %( foo => 'text', bar => 'text', baz => 'text');
# NO. Keys are not guaranteed to be in the same order on each invocation
is %hash.keys, <a b c d>;

Module Developers

Module developers should check out the git master of Rakudo, or if 2018.05 has been released, use that to run the tests of your module. Make sure to run the tests multiple times, ideally at least 10 times or use a loop:

while prove -e 'perl6 -Ilib'; do true; done

This loop will run again and again until it encounters a test failure, in which case it will stop.

You must run your tests many times because the hash order will be different on each run. For hashes will a small number of items, it may not fail on every run. Make sure that you also look at the source to identify items that need fixing; don’t just rely on the test’s to tell you if you must make changes to your module.

Further Reading

Hardening Perl’s Hash Function, article by Booking.com about changes Perl 5 has made to harden hashing.

gfldex: Deconstructing Simple Grammars

Published by gfldex on 2018-05-10T14:51:34

Last year I wrote an egg timer that was parsing command line arguments similar to GNU sleep. I was happy with the stringent form of the parser as follows.

my Seconds $to-wait = @timicles»\
    .split(/<number>/, :v)\
    .map(-> [$,Rat(Any) $count, Str(Any) $unit] --> Seconds { %unit-multipliers{$unit} * $count })\
    .sum;

It does a few simple things and does them one after another. A grammar with an action class would be overkill. I wasn’t happy with using splits ability to return the needle with the parts. It certainly does not improve readability.

After quite a few iterations (and stepping on a bug), I came up with a way to use Str.match instead. If I convert each Match-object into a Hash I can use deconstruction in a signature of a pointy block.

my Seconds $to-wait = @timicles»\
    .match(/<number> <suffix>+/)».hash\ # the +-quatifier is a workaround
    .map(-> % ( Rat(Any) :$number, Str(Any) :$suffix ) { %unit-multipliers{$suffix} * $number })\
    .sum;

Instead of using positionals I can use named arguments that correspond to the named regexes inside the match arguments.

Even in such a small pice of code things fall into place. Hyper-method-calls get rid of simple loops. The well crafted buildin types allow signature deconstruction to actually work without loads of temporary variables. It’s almost as certain language designers where aiming to make a most elegant language.

rakudo.org: Rakudo Star Release 2018.04

Published on 2018-05-07T00:00:00

rakudo.org: Rakudo Star Release 2018.01

Published on 2018-01-29T00:00:00

gfldex: Expensive Egg-Timers

Published by gfldex on 2017-12-31T13:28:01

If you use a CLI you might have done something along the line.

sleep 1m 30s; do-the-next-thing

I have a script called OK that will display a short text in a hopeful green and morse code O-K via the PC speaker. By doing so I turn my computer into an expensive egg-timer.

As of late I found myself waiting for longer periods of time and was missing a count-down so I could estimate how much more time I can waste playing computer games. The result is a program called count-down.

Since I wanted to mimic the behaviour of sleep as closely as possible I had a peek into its source-code. That made me realise how lucky I am to be allowed to use Perl 6. If I strip all the extra bits a count-down needs I’m at 33 lines of code compared to 154 lines of GNU sleep. The boilerplate I have is mostly for readability. Like defining a subset called Seconds and a Rexex called number.

Errors in the arguments to the script will be cought by the where clause in MAINs signature. Since there are no further multi candidates for MAIN that might interfere, the usage message will be displayed automatically if arguments are not recognized. Pretty much all lines in the C implementation deal with argument handling and the fact that they can’t trust their arguments until the last bit of handling is done. With a proper signature a Perl 6 Routine can fully trust its arguments and no further error handling is needed. Compared to the C version (that does a lot less) the code can be read linear from top to bottom and is much more expressive. After changing a few identifiers I didn’t feel the need for comments anymore. Even some unclear code like the splitting on numbers and keeping the values, becomes clear in the next lines where I sum up a list of seconds.

Now I can comfortably count down the rest of a year that was made much better by a made better Perl 6. I wish you all a happy 2018.