Finally, my first workshop paper got published, which was a little odyssey with some misunderstandings, but anyway, now it is out. It is just a position paper, thus, do not expect to many insights. However, what it describes is my big plan, and hopefully the story of my PhD. Am working on it…

Abstract

The upcoming many-core architectures require software developers to exploit concurrency to utilize available computational power. Today’s high-level language virtual machines (VMs), which are a cornerstone of software development, do not provide sufficient abstraction for concurrency concepts. We analyze concrete and abstract concurrency models and identify the challenges they impose for VMs. To provide sufficient concurrency support in VMs, we propose to integrate concurrency operations into VM instruction sets.

Since there will always be VMs optimized for special purposes, our goal is to develop a methodology to design instruction sets with concurrency support. Therefore, we also propose a list of trade-offs that have to be investigated to advise the design of such instruction sets.

As a first experiment, we implemented one instruction set extension for shared memory and one for non-shared memory concurrency. From our experimental results, we derived a list of requirements for a full-grown experimental environment for further research.

• Paper: PDF
• EPTCS: Proceedings Second International Workshop on Programming Language Approaches to Concurrency and Communication-cEntric Software
• BibTex: BibSonomy

Slides of the Talk at PLACES09

Spending the time on coming up with a nice poster eventually paid off.
And here is the winner of this year’s MoVES poster award:

 

Thanks to anyone at the event, and for the interest in my research

 

The third and last part of the summer school started with Ondrej Lhotak talking about pointer analysis. David Bacon presented a basic introduction to garbage collection and detailed description of the real-time Metronome GC. The last lecturer for this summer school was Patrick Cousot, who gave a very basic and thus understandable introduction to abstract interpretation.

Pointer Analysis

Ondrej’s lectures were focused on pointer analysis for C and Java-like languages. He introduced it as a static analysis for several problems like for instance optimization, call-graph construction, dependency analysis and optimization, cast elimination, side effect, and escape analysis. The major problem seems to be that it is a very broad subject with many different applications, and thus, many different techniques to do the analysis.

So, before applying pointer analysis the right abstraction for a specific problem has to be chosen. Usually, this kind of analysis will result in an over approximation of the actual problem. Under approximations are unsound and the exact points-to sets are not computable. Thus, a suitable over approximation has to be found which is exact enough for a specific question to be answered.

Just to recapitulate two examples, he introduced abstractions based on type filtering, i.e, points-to sets are calculated on the bases of types of the potential object during a program execution. Furthermore, he explained field sensitive abstractions. Here the main property of interest is the field to which an object is assigned and this information is used to calculate the points-to sets. More examples and more advance techniques like refinement demand-driven analysis are shown in the slide set which will hopefully appear on the summer school webpage.

Garbage Collection and the Metronome GC

David started his lectures by showing off a bit He showed a nice demo of what the Metronome system is able to achieve in terms of real-time constraints. Definitely very interesting and it fortifies my belief that a Java-like language will be the next system programming language succeeding C/C++.

Afterwards, he gave a short introduction to mark/sweep and semi-space collectors. Useful was his explanation about the actual semantics of StopTheWorld, parallel, concurrent, and incremental GCs supported with an illustration (should remember that one). BTW: The world needs a better book on garbage collection. I don’t like the one of Jones and Lins. It does not solve my problems

Eventually, he started explaining the Metronome-2 systems. The paging approach let me wonder whether there is anything an operating system is actually doing for a modern VM. Well there is, but is it enough to justify the additional trouble? Dreaming of Singularity… The second lesson was basically dedicated to synchronization issues and parallel/concurrent data structures like lock-free stacks and which strategies are out there to implement them. This was a nice addition to what we discussed during Yannis’ lectures and gave me some basic inspiration to implement a lock-free ring buffer for multiple writers and a single reader.

His explanation of all the details of the metronome algorithm and how the different phases interact was quite difficult, and well, not to easy to follow especially since I lost the overall picture from time to time. But well, it is a hard problem and a lot of engineering without a simple solution as it seems.

Abstract Interpretation

The last topic at the summer school was abstract interpretation and the lectures were given by Mr. Abstract Interpretation Patrick Cousot himself. Even so it is a theoretical topic, I liked his introduction. Probably for some of the people it was to basic, but since I never had looked at it before, for me it was the right level of detail and complexity to get an idea what abstract interpretation is actually about.

Unfortunately, my own notes are very spares, and I was not able to retrieve the slide set up to now. However, abstract interpretation tries to provide a sound approximation of the semantics of a computer program, to enable various kinds of static analysis. The main problem here is, similar to pointer analysis, to choose the right abstraction for a given problem.

The examples I recall could have fit into Summit’s presentation about bound computation of loops as well. He introduced ideas like step-wise approximation and other techniques. But, well, unfortunately my memory is too blurry to write something down here with certainty. Beside the introduction of the formal techniques, he also spent some time on how to implement them with Ocaml examples. He also made quite some advertisement for his product ASTRÉE, which originally was developed to analyze code for avionic systems. Well, if I can get my hands on his slides, I might add some more information about the content, but for the moment that’s it.

Where to go next Year?

Need less to say, that I really enjoyed the summer school. The lectures had different levels and quality, but the overall experience was great. Hope, that there will be a VM summer school next year, somewhere on this nice planet. I would love to attend it, too.

Along the way to measure the performance of a Smalltalk implementation for commodity multi-core systems, I tried to use Pharo as a more convenient development platform. Well, and I failed in the first attempt…

To remind myself and document some of the necessary steps in this environment, I wrote up the following tutorial.

Command-line Scripts with a Headless Pharo

For some tasks like benchmarking and automated testing, an integration with other tools comes in handy. For such use cases, Pharo can be used headless, i.e., without its graphical user interface.

This brief tutorial will demonstrate how to use the Debian Language Shootout benchmarks with a fresh Pharo image.

Step 1: Setup Pharo and a Fresh Image

• download a Pharo image, the sources file, and a VM from the download page
• extract all archives in the same folder
• start Pharo, from the commandline, on a MacOSX it should look like this: "Squeak 4.2.1beta1U.app/Contents/MacOS/Squeak VM Opt" \ pharo1.0-10418-BETAdev09.08.3.image

Step 2: Load OSProcess

For output on the shell, we need an extra package from the SqueakSource repository.

It can be loaded by simply executing the following code in a workspace window:

ScriptLoader loadLatestPackage: 'OSProcess' from:
'http://www.squeaksource.com/OSProcess'

To execute this code snippet, select it and press cmd+d or use the “do it” item in the context menu.

Step 3: Load Common Benchmark Code

Now we can load the common parts of all shootout benchmarks into our image.

• On way to do this is to grab the code shown here
and save it to a file called common.st.
• Open the file browser from the Menu -> Tools -> File Browser.
• Select common.st and press filein to load the code.

Now you can close all windows in your image and save and quit it.

Step 4: Run a Benchmark

• Grab the code of a benchmark like Fannkuch
• Save it to a file named like fannkuch.st
• Add a run script to the end of the code in fannkuch.st, like this:
  

      Tests fannkuch.
      SmalltalkImage current snapshot: false andQuit: true.
  

• Run it with a headless Pharo:
  

      "Squeak 4.2.1beta1U.app/Contents/MacOS/Squeak VM Opt" \
          -headless pharo1.0-10418-BETAdev09.08.3.image \
          $PWD/fannkuch.st 6
  

  
  important is here the absolute path to the script, clearly inconvenient and uncommon on the command-line.

PHP 5.3 is already released for a while and starts to settle in.

Now it seems to be a good time to philosophize about the future language development of PHP again. To promote this discussion, I backported my Traits-patch to PHP 5.3, fixed some bugs, and used GitHub to publish it. Lets hope that this will allow a painless maintenance of the patch.

For the moment, there is no uptodate standalone patch file anymore, but only the GitHub repository.

• PHP 6: http://github.com/gron/php-src/tree/PHP_6-traits
• PHP 5.3: http://github.com/gron/php-src/tree/PHP_5_3-traits

For a basic introduction please refer to the RFC (http://wiki.php.net/rfc/horizontalreuse) and the test cases available in the source folder Zend/tests/traits.