JonathanWorthington's Friends' Journals

Todays Vienna.pm TechSocial

leo — 2007-12-03T22:59:45+00:00

We had another TechSocial Meeting in Vienna - taking place on 1st monday of every month. First Willy showed using Perl for emulating heavy (really tons of) hardware - very impressive. Second talk by domm was an intro to Perl 5.10.

The pub (remember TechScocial) did e.g. provide 'Perlhuhnbrust' on the menue, but we didn't ask if it were of the 5.10 persuasion.

The smart match operator lead to immediate discussion, whether there exists a 'not-smart-operator' or rather a 'smart-not-operator' or their combination:

$foo !~~ /bar/; # not smart aka dumb match

Would this maybe match every chicken or rather not?

$foo ~!~ /bar/; # smart no match $foo !~!~ /bar/; # no dumb match

... which immediately lead to a discussion of the orthogonality of the not operator, which generally was considered as very important. E.g. is this valid syntax, and what does it mean:

not my $var;

Semantically it's a promise not to use this variable in that scope. But perl has a different POV

$ perl -Mstrict -Mwarnings -le'not my $var' Useless use of not in void context at -e line 1.

OTOH ...

$ perl -Mstrict -Mwarnings -le'print not my $beer' 1 $ perl -Mstrict -Mwarnings -le'print ! my $beer' 1

... there are some 'true' items, which aren't your beer. But ...

$ perl -Mstrict -Mwarnings -le'print $_->ignore for not our @beer' Can't call method "ignore" without a package or object reference at -e line 1.

... you can't actually ignore all of them.

P3 - Parrot Presentation Program

leo — 2006-09-10T19:57:30+00:00

As outlined in the previous journal entry, I'm writing a new presentation tool using Parrot. It now has hit the parrot svn repository.

A basic presentation (written in html) about P3 itself can be found here (sorry - the svn server is delivering this as text/plain).

Parrot can do AJAX too!

leo — 2006-09-05T22:41:06+00:00

Above subject is shamelessy stolen from Jonathan, who has used it on IRC. Anyway, I got bored by doing my presentations with

$ ./parrot slpod.imc yapc.pod

... or some such. I wrote the predecessor of that at YAPC::EU::2003 during lunch break and the slides at dinner (no, that isn't a joke) and it caused a lot of fun at these days.

But in recent times all has to be AJAX, hasn't it? Alas, I started hacking examples/io/httpd.pir to support a CGI GET request, which is invoking Parrot subroutines, and put together 60 lines of JavaScript dealing mainly with keyboard requests to navigate between slide pieces and to send XMLHttpRequests. The XML thingy is totally optional, don't be afraid, plain text messages or html snippets are working fine too - and that's what the next slide presentation program will use.

Given that your GET request delivers a valid HTML snippet, and you got e.g. <div id="answer"></div> on your html page, then all you need to fill this with contents is mainly this JavaScript two-liner:

var x = document.getElementById('answer'); x.innerHTML = req.responseText;

That's almost it. I'll put together a working example in the parrot repo during the next days.

YAPC::EU::2006 Parrot BOF

leo — 2006-09-04T15:50:36+00:00

About 10 (more or less) parrots flocked together in the lobby of Jury's Inn Hotel at Wednesday. The topics were:

Parrot on VMS (VAX). The Vaxman and Martin, who has already sent a patch to p6i, are hopefully continuing this story.
JIT for the x86_64 architecture
Perl5 continuations. I discussed parrot's implemenation and some implications mainly with Nick.
Parrot interfaces. Allison and me went through a more flexible concept extending the current static vtable layout.

Parrot: if vs. unless

leo — 2006-02-18T21:12:58+00:00

Parrot provides two opcodes to branch on the truthness of a register: if and unless. It looks like that it's just a matter of taste, which one to use. Is it really?

Not with modern CPUs with branch prediction rules and with JIT code inside tight inner loops. Below are two versions of the ackermann function, one written with if and one using unless. (If you are missing the loop in the code, well, that's coming from tailcall optimization, turned on with -Oc.)

$ cat ack-if.pir .sub ack .param int x .param int y if x goto a1 inc y .return (y) a1: if y goto a2 dec x .return ack(x, 1) a2: dec y y = ack(x, y) dec x .return ack(x, y) .end

$ cat ack-unless.pir .sub ack .param int x .param int y unless x goto a1 unless y goto a2 dec y y = ack(x, y) dec x .return ack(x, y) a1: inc y .return (y) a2: dec x .return ack(x, 1) .end

And here are the timings of both with ./parrot -Oc -Cj ack-xx.pir 12 on an AMD X2@2000:

ack-if 2.9 s ack-unless 2.4 s

Branches with positive branch offsets (downwards) are considered to be likely not taken, that is the fall-through case is the default one. As there are a lot more positive numbers than the one zero, the unless is the better choice here (for some CPUs, YMMV). Well, that's at least my conclusion for now. But there is another issue: branch alignment. I've not yet experimented with different label alignments, but I know that alignment can cause timing differences like above too.

Parrot -Ofun

leo — 2006-02-08T16:56:09+00:00

Heureka - from the -Ofun department

Or - running the ackermann function (and possibly other recursive functions) really fast.

$ time ./parrot -Oc -C ack.pir 11 Ack(3, 11) = 16381 real 0m0.567s user 0m0.559s sys 0m0.008s

$ time ./ack 11 Ack(3,11): 16381 real 0m0.980s user 0m0.978s sys 0m0.002s

The latter is optimized C code. Parrot is recompiling (or will do when that's finished) statically known and simple PIR code to native machine code via it's JIT system.

See also a recent post on perl6-internals.

Parrot 0.4.1 "Foghorn Leghorn" Released!

leo — 2006-01-08T16:11:26+00:00

Numerous folks contributing more than 640 revisions were helping to create a more powerful bird err parrot.

Thanks all!

Parrot 0.4.0 "Luthor" Released!

leo — 2005-12-04T16:53:28+00:00

Numerous people have contributed to another major release of Parrot: 0.4.0 'Luthor' is out - thanks to all.

The release name is of course not related to this article, but comes from our brand new lexical stuff.

"The Continuation Bug" is gone

leo — 2005-11-07T23:24:35+00:00

Today I've checked in the final fix for one of the longest outstanding bugs inside Parrot.

A short recap:

Having first-class continuation objects is one of the design goals of Parrot. A lot of HLLs support continuations with some special syntax and with continuations in the core a lot of HLL control structures and features like exceptions can be implemented easily.

But there was a problem with continuations. Continuations can change the CFG (control flow graph) of a program in such a way that there are suddenly loops, where the register allocation code isn't (and can't be) aware of it.

The following code piece from a test provided by Piers revealed the whole problem:

arr1 = "[1, 3, 5]" arr2 = "[1, 5, 9]" x = choose(arr1) y = choose(arr2) if (x * y != 15) fail = find_lex "fail" fail()

To the register allocator this looks like a linear control flow, which is just executed once (there is no loop outside of that code snippet). But actually the choose closures are capturing their continuations and are backtracking through the call to the fail function. We suddenly have a loop going from fail() to one of the choose() function call returns. The code that the register allocator should have been considering would be something like this:

arr1 = "[1, 3, 5]" arr2 = "[1, 5, 9]" choose_again_1: # label actually in front of function return x = choose(arr1) choose_again_2: y = choose(arr2) if (x * y != 15) fail = find_lex "fail" fail() goto choose_again_1 or _2

This implies that the registers of the variables x, y, arr2 can't be reused for example to assign a register to the fail variable. But exactly this has happened and the code really "fail"ed.

There were some (IMHO) impractical proposals to fix this, like refetching all variables from lexicals all the time (and don't use native integers and numbers because these aren't lexicals) but the real fix for this is now in: that is - just don't reallocate the registers used by lexicals and non-volatile variables to other variables like temporaries.

That's the reason for variable-sized register frames and, well, some lack of visible progress of Parrot development for some time.

Parrot 0.3.1 "Wart" Released!

leo — 2005-11-06T13:54:32+00:00

After more than 400 revisions within one month the next release of Parrot has arrived on CPAN.

Thanks to all providing patches and help us with developing Parrot.

Parrot 0.3.0 "Alex" Released!

leo — 2005-10-01T15:48:48+00:00

With a lot of help (Robrt, clkao, svk - many thanks) the branch got merged back to trunk and is now released as Parrot 0.3.0. The official announce should make it to the front page soon.

Calling conventions - a comparison

leo — 2005-08-16T14:13:57+00:00

I've now compared old calling conventions with the new one by checking bytecode size, executed amount of opcodes, and the timings of one of the benchmarks.

I've used the suduku solver and the oo5 benchmark. The latter does 1 million attribute accesses via a method call, comprising a typical example of OO code.

The numbers were achieved by running$ ./parrot -o sudoku.pbc examples/assembly/sudoku.pir $ ./pdump sudoku.pbc | grep size $ ./parrot -p sudoku.pbc and by $ ./parrot -p examples/benchmarks/oo5.imc or -C .

Here are the results:

old new Sudoku codesize 5764 3442 Sudoku ops -p 911973 793967 oo5 ops -p 22501832 10503606 oo5 time -C 7.5s 4.9s

The new calling code reduces code size and executed opocdes significantly, which goes up to a factor of two for the benchmark. There is also a non-trivial speedup albeit no attempts were done yet to optimze the new code for speed.

Slow progress

leo — 2005-07-13T21:27:04+00:00

Two GC bugs (one in my branch, one in both trunk and the branch) slowed down further progress in finishing the calling convention changes. But these bugs are fixed now, and Coke can finish hunting his own in partcl ;-)

In return for endless debug sessions, I compared oo5.imc and oo6.imc from examples/benchmarks - these (premature) results are promising: around half of the opcodes saved and more then 20% speedup. These two benchmarks test attribute accessor functions, where the call overhead is considerable.

Continuations and return context

leo — 2005-07-10T21:17:06+00:00

A correction foremost

A remark WRT the paragraph mentioning type checking in my first ewaa journal. It was caused by me misinterpreting the type conversion specs in pdd03. We are now doing full type conversion, which makes argument passing strictly positional. That's very likely the expectation of our users anyway. In the old scheme calling a subroutine:

foo(pmc b, str a) # pseudosyntax to denote argument types

just worked, despite the sub was defined as:

.sub foo .param str a .param pmc b

Looks weird, but was really used, probably more by accident then for some good reason. Now you get the first argument converted to a string and the second as a new string PMC.

Continuations and return context

As Dan describes in his blog, there is not much difference between a subroutine call and the invocation of a continuation. Both can return results to the caller. A nice example provided by Piers from Parrot's tests (yeah, number 13) contains something like:

x = choose([1, 3, 5]) y = choose([1, 5, 9]) if (x * y != 15) fail()

Above is vastly simplified, because the choose function calls capture their continuations and call a try closure that either backtracks via the saved fail hook or delivers the next item from the passed in choices array. Anyway the interesting thing (for a proper implementation of continuations) is, that there are mupltiple continuations that like to return either the next x or y, when invoked indirectly via the fail function. These continuations are not only returning to different program locations they are also returning different results.

In the source we got this line:

our_cc($P3) # $P3 being one of the next choices

where eventually the next result for choose is to be returned to the main program. It looks like a plain subroutine call, but invokes the passed in continuation and ends up, where one of the choose calls had left off.

This means that creating a full continuation still needs to copy the context structure (which contains also the current return results location). A return continuation can just contain a pointer to the refered context.

After having implemented this all now, the rather complicated tests (p6rules, streams), which are using continuations as well as coroutines are passing within my branch (I didn't look at other failing tests yet, but just converting explicit register usage for call setup to new conventions should fix almost all). These tests are of course passing in Parrot svn trunk true, but now (for the most common case of invoking a return continuation) no context is copied at all, it's just a matter of putting the pointer of the captured context into the interpreter.

The official way to do call/cc is still unchanged, it's:

.include "interpinfo.pasm" cc = interpinfo .INTERPINFO_CURRENT_CONT

This usually means that you need a helper subroutine, where you capture the continuation (and pass it along somewhere for later usage), it's OTOH a well defined usage of continuations in e.g. scheme. When things are settling, I'm sure that we can provide some shortcuts for capturing continuations inside the same sub (or context) too.

And implementing want or similar is of course simple now, as the get_results opcode is emitted before the subroutine invocation, and is therefore available for plain function returns as well as for continuations that return a result. Both can return what the caller wants, because the information is present in the context.

360 KByte and done

leo — 2005-07-06T21:40:12+00:00

Well, the svn diff got bigger a bit and operation is now that far consolidated that I've committed it to a new branch branches/leo-ctx5, so that @all can investigate it and start helping to get it finished soon.

160 KBytes and still counting

leo — 2005-07-05T19:35:51+00:00

Well, 160 Kbytes are my diffs now against Parrot svn HEAD. And still no chance to check it in, without blocking $others, because too much still is failing.

Done:

r = foo(a, b) translates now to new call scheme opcodes, as well as .param and .returns() stuff. Just tossed 460 lines in imcc/pcc.c and added 20 new. Works fine.
Converted the NCI generation code to the new scheme too.
Running Parrot Subs from C code now also uses new conventions

Overall it looks like that calling PASM/PASM is by far simpler now, but PASM/C (NCI) and C/PASM (runops_fromc_*) interfaces use slightly more code lines. OTOH we get now strict type checking and conversions to and from PMCs, which wasn't in the old scheme. I can very well imagine that we don't want to call C code w/o argument verification anyway.

Context patch is getting ready

leo — 2005-07-04T20:11:05+00:00

Wrote a second context allocation strategy today. Just malloc/free backed by a free list. Works fine, except that it seems to reveal a very likely unrelated GC bug, which I'm still chasing.

Yesterday was "Somehow Olympia" (German text) here in Herrnbaumgarten. We had a lot of fun for example watching "towel throwing for politicians".

Parrot Calling Conventions

leo — 2005-07-03T11:46:19+00:00

WWCPD: Calling Conventions

The original design was not only rather heavyweight, it was also incomplete and a bit blurry. It was lacking support for MMD argument signatures, return value context, typechecking, and so on.

I'll try do describe some reasons, why we changed calling conventions to use a new abstract scheme. The major change is that all the argument passing is now done by dedicated opcodes, which allows any later implementation and adaption under the hood without changing the ABI of the Parrot VM.

MMD Signatures

A function call:

foo(Px, Iy)

was translated to these argument-related opcodes (function lookup and call opcodes omitted for brevity):

set I0, 1 # prototyped call set I1, 1 # 1 INT argument set I2, 0 # 0 STR arguments set I3, 1 # 1 PMC argument set I4, 0 # 0 NUM arguments set P5, Px # get PMC argument set I5, Iy # get INT argument set S0, "foo" # function name

A lot of opcodes to dispatch, but takes almost no time with the JIT runtime. Fine so far. Another function call:

foo(Ix, Py)

produced exactly the same call register setup - these two function calls can not be discerned when, it comes to multi method dispatch.

Now the first argument setup just translates to:

set_args "(0b10,0)", Px, Iy

and the second is:

set_args "(0,0b10)", Ix, Py

Thus we not only saved 7 opcode dispatches per function call, we got a clear type information of the caller's arguments including the argument order. You don't have to set these type bits yourself, the assembler does it according to the passed arguments, so just writing:

set_args "(0,0)", Ix, Py

works fine.

Type checking

In the old scheme you could happily call a function with:

foo(Px, Iy)

which was defined as:

.sub foo .param float n .param string s

The .param was just translated to:

foo: set Nx, N5 # get 1st NUM param into n set Sy, I5 # get 1st STR param into s

Due to the register usage of argument passing the function would have picked up whatever happens to be in registers N5 and S5 and would run - probably not long though. A possible "solution" would have been to force all compilers and Parrot hackers to emit code to first verify the passed arguments. That's of course another bunch of opcodes, bulky and error-prone. Now the function defines precisely what it awaits:

.sub foo get_params "(0b11,0b1)", Nx, Sy

Again the type bits are filled in by the assembler. But during the call sequence, the argument passing code can verify the types (and counts) of arguments and parameters. Conversions to and from PMC parameters are specified and done automatically. Mismatches are reported by an exception.

Implicit register usage

The central mechanism of a function call in the old scheme was just the plain argumentless opcode:

invoke

It would pick up whatever happens to be in P1 and uses it as the continuation of the call. P2 was defined to be the invocant, if it's a method call. And so on - and it call's whatever is in P0. That's per se fine, if all code writers and compilers strictly use this convention and don't forget to NULLify registers that shouldn't be used for the call, but it's a major PITA for the assembler, which ought to track the control flow for proper register allocation: is the invoke a function call, a yield, a return from a function? Well it's not defined, it could be everything. Not a few lines inside imcc are trying to track down the usage of invoke opcodes to do the right thing. You can imagine that this does not contribute to clear code.

Method invocant

The old call scheme demanded that the invocant is passed out-of-band in P2. It's also only available in functions declared as methods by a special interpinfo call. This doesn't really match our major target languages, where the invocant just happens to be the first param of a method.

Calling a function as a method or vice versa would have needed to shift PMC arguments down or up to get everything into the registers that the callee expects.

Return value context

The old scheme had no provision for specifying, what and how many return results the caller expects. Now the get_results opcode is emitted before the actual function call, so that a function return has a chance to return what the caller wants.

Future and optimizationIn the old scheme the lower 16 registers of each kind were volatile (each function return could set these registers). This implies that you usually have to move registers from the preserved area into the lower half, during the call sequence registers are moved into the callee's lower half, from where another round through all parameters would have placed everything in the preserved area. This are three passes over all arguments - hardly to avoid in the general case.

The old call scheme reserved 4*16 registers just for function calls and returns. This accounts for 320 bytes (on a 32-bit machine) that have to be allocated per call to pass e.g. just one word argument to an one-liner function or an attribute accessor method.

Ok, we are not doing optimzation now - that's fine. But the old calling scheme would have prevented all future optimizations that will be needed. You can't do any optimizations later when the call scheme is carved in stone and just reserves half of the register resources for itself.

---
WWCPD ... why we change(d) parrot's design