Friday, October 12, 2012

Duff's device implementation details

Typically one writes a Duff's device to copy data like it's shown in the Wikipedia, i.e. using *to++ = *from++ for each step.  Most likely a compiler dealing with *to++ = *from++ will emit 4 instructions: a load, a store, and two additions to pointers likely stored in registers.  But, for example, if you have an 8 case device, you can arrange things so that the pointers are incremented with the slack iterations before the switch and then do

  • *(to-8) = *(from-8);
  • *(to-7) = *(from-7);
  • ...
  • *(to-1) = *(from-1);
  • if not done, increment to and from by 8 and go to the top;
With the explicit offsets above, each step requires just a load and store with fixed offsets that a reasonable CPU with instructions such as mov rax, [rsi+offset] calculates on the fly.  The resulting Duff's device is now roughly half the size in assembler instructions.

Wednesday, October 10, 2012

GC improvements continue

I had a bit of time recently to go back to the HPS memory manager and deal with a few loose ends I had previously identified.  I overhauled the large and fixed space implementation because of performance considerations, with the goal of removing bits of inefficiency from the VM's background performance level.  Besides the usual code deletion (about 250 LOC gone so far), scavenges in the presence of numerous fixed space objects became measurably faster.  The same should be true with large space, but of course there are generally fewer large space objects than fixed space objects so your mileage may vary.  Other operations that got a bit faster include mark/sweep GCs and becomes in which at least one of the objects involved is in fixed or large space.

Wednesday, October 03, 2012

Regarding how to teach programming

Here's an awesome talk by Mark Guzdial recorded at the 2012 C5 conference.  Watch how non-CS students can pass programming courses more often than CS students when taught a different way.  The goal of this improved teaching is to allow everyone to take advantage of programming, not just CS oriented people.  In that way, we can all start using the computer for our own stuff as opposed to letting it be a glorified [buy now] button.  We need more people to do the kind of work Mark is doing.

And it doesn't stop there.  Watch what happens when the same techniques are applied to CS students themselves...