[ Home | Articles | Account | People | Projects | FAQ ] Windows Patches Welcome; Windows Attitude Not
<summary type="xhtml"></summary>Going Faster By Doing Less Work
<summary type="xhtml">Today's Rakudo-building speedup is 27.79%.
(Okay, the other slow part of Rakudo builds 17.59% faster. Still.)
The profile showed that string allocation was a hotspot in the benchmark. In particular, the part of Parrot which allocates memory out of arenas spent a lot of time performing garbage collection. Every time you can avoid either allocating unnecessary memory or running a full garbage collection, you can improve performance.
Parrot r27484 adds one line of code (and one line of comment).
Every time mem_allocate() successfully allocates a new block, it increments a counter. Whenever the garbage collector performs a full run, it resets that counter to zero.
This patch performs a garbage collection run from mem_allocate() only if that counter is non-zero. That is, if the garbage collector has already run, it's already found as much free arena memory as possible. (This is not memory for PMCs or STRING headers; this is buffer memory.) Running the GC again won't find any more free buffer memory. In that case, skipping the GC run and allocating more memory from the OS gives the performance improvement.
I should note that my comments about avoiding memory allocation apply in the general case. Parrot's current GC has some limitations. The biggest is that it stops the world to mark and sweep everything. The new GC Andrew Whitworth will implement as part of the Google Summer of Code will fix that. As well, we have some ideas to improve the implementation such that the GC will become even less expensive now. Then we'll see algorithmic improvements that make even this 27.79% optimization seem small.
Doing Nothing Better in Perl 5
Perl 6 has three code placeholder operators, known affectionately as the "yada, yada, yada" operator (see List Prefix Precedence in Synopsis 3). It's a matter of (very sarcastic) public record how much I love writing, maintaining, and patching parsers, so I've just sent a very preliminary five-line patch to p5p to add support for<nobr> <wbr></nobr>... to Perl 5.
--- perly.y~ 2008-05-09 17:47:35.000000000 -0700
+++ perly.y 2008-05-09 17:47:41.000000000 -0700
@@ -1227,6 +1227,11 @@
}
| WORD
| listop
+ | DOTDOT
+ {
+ $$ = newUNOP(OP_DIE, 0,
+ newSVOP(OP_CONST, 0, newSVpvs("Unimplemented")))
+ }
;
<nobr> <wbr></nobr>/* "my" declarations, with optional attributes */
Apply this to recentish bleadperl sources, run perl regen_perly.pl, rebuild, and now you can run programs such as:
sub foo {<nobr> <wbr></nobr>... }
foo();
And get an "Unimplemented at file line line." error message.
(Now everyone who complains that I don't code enough to match my talk, please punch yourself in the face.)
Perl 6 Design Minutes for 07 May 2008
<summary type="xhtml">The Perl 6 design team met by phone on 07 May 2008. Larry, Allison, Patrick, Will, Jerry, Nicholas, Jesse, and chromatic attended.
Allison:
c:
Allison:
c:
Patrick:
c:
Jesse:
Larry:
nofat rulePatrick:
Jerry:
Patrick:
Jerry:
c:
Nicholas:
state implementation of any languageJesse:
Patrick:
Jesse:
Nicholas:
Jesse:
Will:
Jerry:
Patrick:
Nicholas:
Jerry:
Jesse:
Nicholas:
Allison:
Jesse:
Allison:
Will:
Patrick:
Allison:
Will:
Allison:
Jerry:
Patrick:
Will:
Patrick:
Jerry:
Patrick:
Larry:
Patrick:
Larry:
c:
Will:
Jesse:
Good Error Messages are Important
Parrot r27355 was fun to write.
One of the persistent error messages Parrot emits for compiler writers is
Null PMC access in invoke(). If you've had your hands deep in the
guts of Parrot, you know what that means -- you tried to call a Sub PMC when
you don't have a Sub PMC, you have no PMC. (If you don't know what that means,
this entry is for you.)
Sometimes this means that there's a problem in Parrot. We've fixed almost all of those problems though, so the error usually comes from elsewhere. If you're writing a compiler, or running a compiler built on Parrot, the error usually means "You tried to call a function that doesn't exist."
Parrot's optimizer does something interesting at the end of compilation time. You've probably heard that Parrot's compiler, IMCC, translates PIR into PBC. That is, it turns source code into bytecode, which Parrot can either serialize t to disk or execute immediately. That bytecode is just a chunk of linear data in memory. It's not really a data structure. (Okay, it's a C array, but that doesn't make it a data structure.)
After IMCC has finished building a standalone chunk of bytecode, it performs a constant fixup phase. The notable part of this phase is that it edits the bytecode in place to replace all named invocations of functions known at fixup time with offset invocations.
The previous code looks something like:
invoke known_function
null # padding
null # padding
If IMCC has already seen known_function by this time, the
direct invocation of known_function can continue. There's no
runtime lookup necessary; all functions already compiled and ready are
available in the bytecode.
If IMCC hasn't seen that function, runtime lookup is necessary, and so this function replaces the bytecode earlier with the equivalent of:
<nobr> <wbr></nobr>.local pmc func
func = find_name 'unknown_function'
invoke func
(I've simplified what actually happens slightly, because the concepts are more important than the details. Hopefully you see why the padding is necessary. If not, just imagine trying to splice additional opcodes into what may presumably be a lengthy C array -- like I said, barely a data structure.)
The problem with this second form occurs when find_name returns
a NULL PMC, which it can legitimately do. In that case, the
invoke opcode tries to invoke a NULL PMC and fails, and Parrot
throws an exception saying "There's nothing here to invoke." There's the error
message.
It's clear why that happens, but it's not useful. It would be more
useful to see the name of the function you tried to invoke in the
error message. Unfortunately, by the time Parrot calls the invoke
op, that name is long gone.
My first idea was to rewrite the dynamic lookup form into something resembling:
<nobr> <wbr></nobr>.local pmc func
func = find_name 'unknown_function'
if defined func goto call_it
die "Can't invoke 'unknown_function'"
call_it:
invoke func
Unfortunately, I didn't have the space in the bytecode stream to insert that many ops, and I had no desire to move chunks of memory around in that C array. I could have added more padding after an invocation, but to be fair I'm only mostly sure that it exists there in the first place.
I had room for one op with a destination PMC and a string constant argument.
I added an experimental op called find_sub_not_null which does the
same thing as find_name but throws an exception which includes
the requested name if Parrot can't find a PMC of that name.
This isn't entirely an ideal situation. It's a special case op, and I prefer to remove ops where possible. It's also nearly code duplication, though it's effectively three lines of code in an op, which isn't awful. I still want to be able to perform these kinds of transformations in PBC itself, but we need a different way to generate PBC and perform op-level transformations in PIR before we can do this effectively.
There are always tradeoffs, though. Doing this check in C is slightly faster than doing it in PIR. The standard Perl 5 rule of optimization applies even in Parrot -- the fewer ops, the mostly faster you can go. As well, I was able to improve the warning message today, rather than at some point in the future when we have better PBC optimization possibilities.
After all, I can always remove this op in the future.
What are You Going to Do, SMS at Me?
<summary type="xhtml">For years, I've thought that the only thing sillier than complaining about disaffection and how the world really should work differently in IRC was to sign silly Internet petitions about it. Now I realize that people who feel compelled to register their righteous indignation in 141 characters of chatspeak matter least.
Here's a quarter, kid. Go buy a postcard.
What a GC Bug Looks Like in Parrot
<summary type="xhtml">Every so often someone reports weird behavior in #parrot, and someone says "Hey, that looks like a GC bug!"
Most of them aren't. (Most of them lately seem to be that we're changing the way bytecode works, and we don't have all of the dependencies for all of the generated PBC files correct, so you have to run make realclean and rebuild.)
While adding the vtable override cache the other day, I did create a forehead-slapper of GC bug, but I caught it before I checked in the code. How did I know it was a GC bug? Easy.
The Class PMC itself contains pointers to several other PMCs and GC entities, including the name of the class and its corresponding namespace. I added a pointer to a Hash PMC which maps the names of vtable overrides to Sub PMCs.
I remember thinking at the time "Hey, it's just a cache. I don't have to mark it during the mark phase explicitly. All of the Subs it refers to will stay alive as long as their namespaces live. That's easy."
When I ran the tests, I saw a weird error about not being able to perform a
keyed index PMC lookup on a Key PMC. I set a breakpoint on the
real_exception function (which reports these kinds of errors) in
the debugger, and the backtrace showed that the cause of the call was my cache
lookup function.
"That's weird," I thought. Then I realized what I had done.
My line of thinking was correct in that I don't have to mark all of the PMCs contained in the cache PMC. They're already reachable from the rootset through the namespace. The GC won't collect them.
The problem is that the cache itself -- the Hash PMC -- is only reachable through the Class PMC. Unless it gets marked as live, the GC will reclaim its header and put it on the free list again.
The Class PMC still has a pointer to that header, but the next PMC allocated from the GC which uses that header will overwrite the PMC's information, effectively morphing my lovely cache into something else. In this case, my Hash PMC turned into a Key PMC.
Usually they're not this obvious, but I've gone through all of the PMCs in Parrot to make sure they mark their contained GCable entities appropriately.
Perl 6 Design Minutes for 23 April 2008
The Perl 6 design team met by phone on 23 April 2008. Larry, Allison, Patrick, Jerry, Will, Jesse, Nicholas, and chromatic attended.
Jerry:
Patrick:
Jerry:
Nicholas:
Jesse:
Jerry:
Larry:
Jerry:
Larry:
Allison:
Patrick:
Allison:
Patrick:
Will:
Allison:
Will:
c:
Patrick:
c:
Jesse:
Patrick:
c:
Patrick:
Will:
c:
Patrick:
Will:
Nicholas:
c:
Jesse:
c:
Jesse:
c:
Jerry:
return
Allison:
Will:
return, break, and continue
Allison:
Patrick:
return type exception, it grabs the arguments, does what it has to, and then does a Parrot return
Allison:
Patrick:
handled
Allison:
Patrick:
return in for the April 15 milestone we're behind on
Jerry:
Allison:
c:
Allison:
Refcounting Isn't All Bad
<summary type="xhtml">A lot of people complain about reference counting as a memory management strategy in Perl 5, and they have a point. Unless you're very careful, reference counting spreads its tendrils throughout your system. Unless you're very disciplined, you'll forget to increase a reference count somewhere, and you'll end up collecting things in the wrong places.
The paper A Unified Theory of Garbage Collection discusses the most popular modern GC strategies to demonstrate how reference counting and tracing garbage collection are roughly equivalent, especially as concerns about performance, correctness, and conservativeness increase.
I explain this because I added reference counting to a small part of Parrot today as an optimization -- 11.73% on my Rakudo-building benchmark.
Parrot has an internal data structure called a stack. This represents a particular environment within the call graph. If you think of a normal program flow, where function A calls function B calls function C which returns to B and returns to A, you'll have a sense of a normal call stack. Parrot's stack is similar, except that we use continuation passing style (CPS), where it's not a stack, it's a graph, and control flow doesn't have to be that linear.
There's plenty of literature on CPS (including Luke Palmer's how
to get a free sandwich with continuations, but the important idea is that
function A sets a bookmark inside and passes that bookmark along to function B.
B does the same thing when it calls C. At any point, you can look up any
bookmark you happen to have and magically teleport (okay, it's just a jump
instruction in your processor -- someday I'll explain how very low level
languages have eval and very high level languages have
eval and it's just the poor jerks in the middle who can't do
anything useful without feeding the world's pointiest programming language into
their AbstractFactoryFactoryFactories) to the point of that bookmark.
Ranty story short, our stack is a mostly-acyclic graph represented as a linked list, and stack entries -- or chunks -- are garbage collectable entities.
If you've even sat next to one of my "Let's Make Parrot Go Faster!" entries on a bus somewhere, or heard it playing softly in an elevator, you know that one good way to make Parrot go faster is to use fewer garbage collectable entities. One way to make an O(2n) algorithm faster is to make it an O(log n) algorithm. Another way is to make n smaller, and that's easier for now, especially because all I have to do is watch over Andrew Whitworth who's going to write a nice new garbage collector and keep track of Senaka Fernando, who's going to connect the nice garbage collector from Apache Harmony into Parrot.
One nice feature of reference counting (ah, now you see the connection!) is that you can recycle dead objects as soon as you know they're dead. One sad misfeature of a conservative garbage collector is that dead bodies stack up for a while until you can mulch them. One horrible thing about a stop-the-world full mark-and-sweep garbage collector (and try to guess what Parrot has at the moment) is that if you're out of memory in one of the arenas you care about, you have to mark all of the living GCable entities in your system and sweep all of the pools in all of the arenas to find everything that's alive and to recycle everything that isn't.
If you want to go fast, you want to avoid this until it's absolutely necessary.
Here's the interesting thing about stack chunks: Parrot stores them in one
place in one function (stack_push) and unstores them in one place
in one function (stack_pop). Again, the names are really bad
because it's a graph and not a stack, but you get the point.
I noticed this when I profiled the Rakudo-building benchmark again and saw
that stack_push was one of the most expensive inclusive calls,
apart from the garbage collector. It calls a function which calls a function
which calls a function which asks for a new stack chunk from the GC. When
there are no more free stack chunks, the GC runs again, and that eats up
precious cycles.
After a few minutes of thinking, I realized that the
stack_push/stack_pop pair formed a boundary around a
stack chunk's lifespan. Popping a chunk off of the stack meant that nothing
else needed it. That chunk is immediately identifiably a dead object, suitable
for recycling.
Rather than waiting for a full GC run to find every live object in the system and then run across this dead object and recycle it, I added a couple of lines of code to recycle it automatically then and there.
There was my immediate 11.73% speedup.
There was also a problem in the Continuation PMC tests; I noticed this only after I patted myself on the back for moving the bottleneck in my benchmark elsewhere. I'm sure you'll see it if you think for a moment, especially about how I kept writing that the stack isn't a stack, it's a graph implemented as a linked list.
The problem is that there's not a single linked list. If you take a continuation at various points in the call graph, you can have several linked lists that all share the same tail. If you exhaust one of those call chains, you may pop a stack chunk that's part of another call graph elsewhere. Your reference to it goes away, but it's still live elsewhere, so if you recycle it then and there, you may end up reusing the chunk and storing inappropriate data in it while something else expects it to stay pristine.
If you're very clever, you've figured out the solution.
I added a reference count to the stack chunk structure, incremented it on
stack_push, decremented it on stack_pop, and recycled
the chunk in the latter function only if the refcount is zero.
Is this a long-term solution? Probably not; I posted my initial investigation to the parrot-porters list, and we had a nice discussion on alternate techniques. We'll have to refactor the code more heavily once we find a better approach, but for now, I'll live with this optimization.
(Seneca Cunningham found what appears to be a crash related to this, but I think I've found the culprit and fixed it by adding another reference count pair to the Continuation PMC. See? I told you reference counting made itself pervasive.)
It's Cheaper at Compile Time
I've long used part of the Rakudo-building process as my benchmark for Parrot optimizations. It doesn't exercise all of Parrot by any means, but it pushes the garbage collector, the string system, and the object system pretty hard. It's also the longest part of the build process anywhere, so improving performance there has a dramatic effect on productivity.
I've long known that it appends to and concatenates strings very frequently. The corresponding Parrot functions always show up near the top of the cost list from Callgrind. I've spent a few hours here and there trying to speed them up, but short of rethinking them entirely, I've never found a good solution.
We don't (yet) have a PIR-level profiler like Callgrind (but I'm working on it). Sometimes I can read through the code and see things that might be expensive, knowing what eventually gets called and where. On a whim, I browsed through the generated code for Rakudo to find concatenation. One idiom jumped out at me:
$S0 = concat "PIR", ':"'
This line of code catenates two constant strings into one, and assigns the result to the virtual string register $S0. It's not terribly inefficient; the two constant strings are in the constant table in the bytecode, so they don't get recreated on execution. However, the result is always going to be a constant string.
There's no reason the optimizer couldn't rewrite that line of code into:
$S0 = 'PIR:"'
It didn't. Now it does.
The optimizer already knew how to optimize away constant addition,
subtraction, and other math operations. All I had to do was tell the opcode
generator not to generate the concat_s_sc_sc op (concatenate two
string constants and put the results in a string register -- the destination
register always comes first in the argument list for an opcode), add the
concat operator to the list of rewritable three-register opcodes,
and add a case to the rewriter where the destination register is a string
register.
The result is a modest 5.5% speedup in my benchmark. Part of the gain is avoiding run-time concatenation, but part of it is also using fewer GCable entities. The less garbage you create, the less garbage you have to collect and the less frequently you have to collect it. 5.5% isn't a huge gain, but it's a step in the right direction. Every second we shave off of the hack-compile-test cycle is an improvement, and these optimizations help all Parrot programs as well.
(Are these entries interesting? I seem to get more feedback when I complain about various Technology Distortion Fields.)
FOAF updates: Trust rankings are now exported, making the data available to other users and websites. An external FOAF URI has been added, allowing users to link to an additional FOAF file.
Keep up with the latest Advogato features by reading the Advogato status blog.
If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!