Planet D

Package

2009-11-08T12:38:37+00:00

Yesterday Arthur Loiret announced on the #d.tango channel on Freenode.net that he did some work in packaging ldc and tango. I’ve been working on it for a while, but when i started developing gdc i didn’t maintain that work anymore.

Since Arthur gave me all the needed files to reproduce the packages, i’ve updated the PPA for ldc + tango set. New packages are of revision 1586 of ldc and 5027 of tango.

Detailed instructions in how to install those packages can be found at the Ldc Ubuntu packages page. Let me know if you have troubles with those packages!

DMD frontend 1.051 merged in LDC

2009-11-07T15:08:33+00:00

After 5 or 6 DMD versions with important regressions, LDC has just been updated to DMD's frontend 1.051. This brings a lot of bug fixes to the LDC world (DStress results are looking good! ;).

Lots of thanks to LDC guy for merging the new frontend =)

Patch to make D's GC partially precise

2009-11-06T20:09:27+00:00

David Simcha has announced a couple of weeks ago that he wanted to work on making the D's GC partially precise (only the heap). I was planning to do it myself eventually because it looked like something doable with not much work that could yield a big performance gain, and particularly useful to avoid memory leaks due to false pointers (which can keep huge blocks of data artificially alive). But I didn't had the time and I had other priorities.

Anyway, after some discussion, he finally announced he got the patch, which he added as a bug report. The patch is being analyzed for inclusion, but the main problem now is that it is not integrated with the new operator, so if you want to get precise heap scanning, you have to use a custom function to allocate (that creates a map of the type to allocate at compile-time to pass the information about the location of the pointers to the GC).

I'm glad David could work on this and I hope this can be included in D2, since is a long awaited feature of the GC.

Update

David Schima has been just added to the list of Phobos developers. Maybe he can integrate his work on associative arrays too.

DMD 1.051 and 2.036

2009-11-06T17:41:33+00:00

Walter has pushed new versions of DMD out the door. 1.051 is a bugfix release, while 2.036 gets bugfixes and a ton of new features. Methinks the biggest news in these releases is the OPTLINK fix Walter previously announced. In other news, Tomasz Stachowiak has opened a new wig business. Perhaps a postmortem on how he [...]

OPTLINK and ArcLib and AAs, Oh My!

2009-11-05T13:45:07+00:00

Three news recent news items that will be of interest to some of you in D Land… Walter has let it be known that a long time, and much cursed, bug with OPTLINK has been found and squashed. Specifically, bugzilla #424, which keeps popping up in “why I’m fed up with D” rants. Expect a patched [...]

ArcLib v.03 GUI-Physics-Refactor release

2009-11-03T12:18:57+00:00

Dear D community,

I would like to announce the latest release of ArcLib, Arc v.03 GUI-Physics-Refactor release. See http://www.dsource.org/projects/arclib/report/6 for full list of work done on this release.
The greatest changes were made to the structure of the project. Also includes the joystick support, camera, per pixel collision detection, sprite, and 2d lighting system.

See http://dmedia.dprogramming.com/?n=Tutorials.ArcIntro for getting started with D and ArcLib.
The real purpose of this release is that I finally got everything working and cleaned up in the trunk. I had ported the hybrid GUI, but don’t have time to support it because of the massive amount of code and my lack of familiarity with the system. I will also drop scenegraph unless others want me to keep it.

I will now create the stable branch.
- Clay

Introducing the arc.game Game class

2009-11-03T08:48:54+00:00

Here is the first incarnation of the Game class. The idea behind the class is that the user will overload the this() class for init, process() for game loop, and shutdown() for shutdown code, and the Game class will handle the mundane details, such as input processing and window swapping. After creating their own class to extend the Game class and overloading the correct functions, the main loop simplifies to

// main entry
int main()
{
// initialize game
Game g = new MyGame("Arc
Graphics Primitives", Size.d640x480, false);

// loop game
g.loop();

// shutdown() is called by loop() after loop exits
return 0;
}

Here is an example I’ve modified to make use of the game class: http://svn.dsource.org/projects/arclib/trunk/examples/arc/draw.d

Of course, use of this class is optional. It may gain more features in the future, such as setting up game states and integration with the GUI. For now, its very simple.

Back from the Round-a-bout

2009-11-02T12:51:36+00:00

I’m back from the round-about (South America -> Minnesota -> New Hampshire -> Finding Job)

I’ve been out for a while, but I’ve decided to clean up my project a little. I left it hanging with a broken subversion for too long.

Anyways, I want to get ArcLib fully integrated with eclipse, so I’ve installed the descent plug-in and have an eclipse project file. I plan to use xfbuild when I can get it to work, but right now its complaining about not having the –deps flag, and I can’t get the current hg clone to build. So I’m using reliable old dsss until I figure out how to replace it with xfbuild, and then I’ll figure out how to run xfbuild straight from eclipse.

I find eclipse to be an excellent editor if you have the memory to run it. It has useful features like global project search and replace with the option to use regex, and other neat features.

The news is this: The current trunk now compiles, yay! I haven’t checked to see if it works, but it should for the most part. Also, I’m not going to support hybrid and the scenegraph anymore, for the sheer amount of code they have, and my lack of familiarity with these systems. If I need, I may write a scenegraph or similar features from scratch in the future. Also, arclib should be able to be compilable with xfbuild, once I get that to work.

Speaking of Round-a-bouts, a nearby town decided to install two of them on the roads, with one on the highway. Both round-about's are design fails.

TDPL Excerpt

2009-10-29T13:51:12+00:00

Andrei has posted an excerpt from his forthcoming book, The D Programming Language. In his words: It’s a rough rough draft, but one for the full chapter on arrays, associative arrays, and strings. http://erdani.com/d/thermopylae.pdf Any feedback is welcome. Thanks! If you want to give feedback, a good place to do so would be in the NG thread where the [...]

The D Programming Language

2009-10-29T12:37:40+00:00

The version 2.0 of D will be released in sync with the classic book titled after the language, in this case, The D Programming Language, written by the Andrei Alexandrescu. You can follow the progress of the book looking at his home page, where a words and pages counter and a short term objective are regularly updated.

He posted a little introductory excerpt of the book a while ago and yesterday he published a larger excerpt, the whole chapter 4 about arrays, associative arrays and strings.

If you don't know much about D, it could be a good way to take a peek.

Bartosz Milewski

2009-10-26T20:27:34+00:00

The video of my talk, Haskell and C++ Template Metaprogramming, is now available; and so are the slides. I pretty much covered the material from my last blog post, but many people (including me) find a video presentation easier to follow.

This is also a plug for the Northwest C++ Users Group that meets in Redmond every third Wednesday of the month. If you live in Seattle or on the east side of Lake Washington, check it out. You won’t be disappointed.

Olden "em3d" benchmark in D language

2009-10-25T23:38:20+00:00

All the code shown in this article:
http://www.fantascienza.net/leonardo/js/dolden_em3d.zip

This is a partial port of the Olden benchmarks to the D language. I'll add more Olden benchmarks in future as time allows me to.

Info on the Olden benchmarks and their Java translation (JOlden):
http://www-ali.cs.umass.edu/DaCapo/benchmarks.html
http://www.sable.mcgill.ca/~bdufou1/ashes2/

General comments:

One of my purposes is to test the efficiency of the D1 code compiled with LDC. LDC is usually able to produce efficient binaries when I translate C code to C-like D code. So now I want to see how D is efficient if I start from higher level code, like Java code. It's usually easy to translate such Java code to D, D looks like a super set of C and Java, with some C++ mixed in.

Olden benchmarks are designed to stress first of all the memory allocations. The D Garbage Collector (GC) is quite less efficient than the Java HotSpot GC, so literal translations of the Olden benchmarks from Java to D are usually lower or quite lower performance (up to 4-16 times slower). So I have to work some to regain performance. Usually D allows me to produce final programs that are 2-6 times faster than the original Java versions, but such optimization requires time, experience, and sometimes it's a little bug-prone.

Beside having a more efficient GC, Java performs other optimizations not done by LDC, like inlining of virtual methods, and other things. In future the LLVM back-end of LDC will hopefully perform some of such optimizations (obsoleting some of my manual optimizations).

In all JOlden benchmarks I have packed the Java code of a benchmark in a single source file, that later I have first translated to D, and then optimized for speed and memory usage. Sometimes I have cleaned up some the D code.

Below I explain the various versions I've created.

See the Python2 code near the bottom to see the algorithm used by this "em3d" benchmark. This benchmark models the propagation of electromagnetic waves through objects in 3 dimensions. It is a simple computation on an irregular bipartite graph containing nodes representing electric and magnetic field values.

Update 1.2, Oct 26 2006:

One of the main purposes of this article is to show show and teach how some manual optimizations are done.

Timings of the various versions (i is the number of iterations):

          i=50   i=200  i=2000
Java1:    4.37    7.13
Java2     3.62    6.87
D01:      6.55   11.40
D02:      4.98    9.36
D03:      3.53    8.01
D04:      3.32    6.44
D05:      2.94    5.95
D06:      2.14    5.23
D07:      1.99    4.72
D08:      1.82    4.04
D09:      1.82    4.03
D10:      1.20    3.06
D11:      1.27    2.96   24.62 (TyIndex=ushort)
D11:      1.52    3.60         (TyIndex=uint)
D11b:     1.27    2.97   23.25 (TyIndex=ushort, TyDelta=ubyte)
D11b:     1.31    3.00         (TyIndex=uint, TyDelta=ushort)
D12:      1.61    3.62
Java3:    3.14    6.24
D01b:     6.33   10.60
Python1: 64.3    ---

------------------------------------

Java1

The original JOlden Java code packed in a single source file.

I have fixed a bug present in the Java code of JOlden Em3d but absent in the original C code:
At line 131 of the Em3d1.java the line:
if (otherNode == toNodes[filled]) break;
Has to be fixed as:
if (otherNode == toNodes[k]) break;

Such bug was not found probably because this benchmark suite has no unit-tests that test well each class and each method of each class.

Timings (best of 6, seconds):

...$ time java -server Em3d1 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Propagating field values for 50 iteration(s)...
EM3D build time 2.725
EM3D compute time 1.277
EM3D total time 4.01
Done!
real 0m4.370s
user 0m3.376s
sys 0m0.380s

...$ time java -server Em3d1 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Propagating field values for 200 iteration(s)...
EM3D build time 2.458
EM3D compute time 4.35
EM3D total time 6.812
Done!
real 0m7.128s
user 0m6.568s
sys 0m0.440s

Used:
java version "1.6.0_16"
Java(TM) SE Runtime Environment (build 1.6.0_16-b01)
Java HotSpot(TM) Client VM (build 14.2-b01, mixed mode, sharing)

Code running on Ubuntu, running on VirtualBox, running on Windows Vista, on CPU Celeron 2.13 GHz.

------------------------------------

Java2

It's like the Java1 version, but it use a very simple portable pseudo-random generator. So when I translate this program to D I can see if it gives the same results.

The Random.nextInt is a little different, it accepts a max value (min is 0).

Timings:

...$ time java -server Em3d2 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Propagating field values for 50 iteration(s)...
EM3D build time 2.209
EM3D compute time 1.109
EM3D total time 3.318
Done!
real 0m3.622s
user 0m3.100s
sys 0m0.416s

...$ time java -server Em3d2 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Propagating field values for 200 iteration(s)...
EM3D build time 2.197
EM3D compute time 4.354
EM3D total time 6.551
Done!
real 0m6.875s
user 0m6.292s
sys 0m0.448s

------------------------------------

D01

This is the most direct translation of the Java2 code to D, with the portable pseudo-random generator. I have used printf for maximum portability across different D standard libraries. I have replaced the enumerated with the D opApply.
As you can see D1 allows to program in a style almost equal to Java.

Code compiled with:
...$ ldc -O5 -release -inline em3d01.d

With:
LDC compiler, based on DMD v1.045 and llvm 2.6 (Thu Sep 10 23:50:27 2009)

Timings:

...$ time ./em3d01 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Propagating field values for 50 iteration(s)...
EM3D build time 4.96
EM3D compute time 1.38
EM3D total time 6.34
Done!
real 0m6.547s
user 0m5.856s
sys 0m0.576s

...$ time ./em3d01 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Propagating field values for 200 iteration(s)...
EM3D build time 4.88
EM3D compute time 5.97
EM3D total time 10.86
Done!
real 0m11.398s
user 0m10.801s
sys 0m0.492s

The first D version, despite being compiled with LDC, is slower than the Java version. As you can see the build time is much bigger, more than two times, that's mostly because of the D GC.

To test that no bugs are introduced I have created a small Python script that acts like the "diff" command, but ignored small differences in floating point values. The programs of this benchmark are able to print the results, so I can test them:

...$ java Em3d2 -n 10 -d 4 -i 5 -m -p > outj
...$ ./em3d01 -n 10 -d 4 -i 5 -m -p > outd01

With it I can test that the results are the same:

...$ python approx_diff.py outj2 outd01
3) line=26: ['EM3D', 'build', 'time', '0.0040'] ['EM3D', 'build', 'time', '0.00'] 0.004 0.0
3) line=28: ['EM3D', 'total', 'time', '0.0040'] ['EM3D', 'total', 'time', '0.00'] 0.004 0.0

This is the asm of inner loop of computeNewValue() compiled with LDC:

.LBB11_2:
movl 32(%eax), %esi
movl (%esi,%edx,4), %esi
movl 40(%eax), %edi
movsd (%edi,%edx,8), %xmm1
mulsd 8(%esi), %xmm1
subsd %xmm1, %xmm0
movsd %xmm0, 8(%eax)
incl %edx
cmpl %ecx, %edx
jl .LBB11_2

------------------------------------

D02

Olden benchmarks are quite memory-based, so the first way to optimize them is to reduce the number of memory allocations. Also, in D a good basic optimization for this kind of programs is to convert classes that are instantiated many times, into structs.

A quick scan of the code shows that it contains a single instance of Em3d and BiGraph, and many instances of Node. So this version translated Node into a struct, allocated on the heap and managed by pointer. The code is almost the same. I have also reformatted code to 4 spaces.

Timings:

...$ time ./em3d02 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Propagating field values for 50 iteration(s)...
EM3D build time 3.39
EM3D compute time 1.40
EM3D total time 4.79
Done!
real 0m4.982s
user 0m4.416s
sys 0m0.472s

...$ time ./em3d02 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Propagating field values for 200 iteration(s)...
EM3D build time 3.35
EM3D compute time 5.84
EM3D total time 9.19
Done!
real 0m9.365s
user 0m8.821s
sys 0m0.460s

The code is faster, but there's a lot to do still. The code is not good yet, there are several inefficiencies.

------------------------------------

D03

Timings:

I have converted all the classes (Random, BiGraph and Em3d) to structs with minimal performance changes. So the problem is (as expected) elsewhere.
I have reformatted the Java comments to produce a more compact code that (despite losing being fit for ddoc) allows me to understand the code better.

I have renamed some Node fields to better names, because better names allow to understand code better:
toNodes => outbound
fromNodes => inbound
fromCount => n_inbound

Now the main() is a independent function.

Then I have disabled the GC just before the graph creation, and enabled again after that.

I have also added extra time printings inside the graph creation method, to study better where the running time goes.

Then I have added an exit(0) at the end of the main, it kills the program quickly, saving the time needed to call destructors and to free the GC memory. In general this is not a safe thing to do, because destructors may be necessary, but in this program this is OK.

Timings:

...$ time ./em3d03 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
0.14 0.94 0.48 0.43
Propagating field values for 50 iteration(s)...
EM3D build time 1.99
EM3D compute time 1.36
EM3D total time 3.35
Done!
real 0m3.530s
user 0m2.920s
sys 0m0.524s

...$ time ./em3d03 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
0.15 0.93 0.48 0.43
Propagating field values for 200 iteration(s)...
EM3D build time 1.99
EM3D compute time 5.80
EM3D total time 7.79
Done!
real 0m8.012s
user 0m7.348s
sys 0m0.540s

As expected the compute time is unchanged, but the build time is decreased significantly.
Now the build time is lower than the Java2 code! So the first benchmark (with just 50 loops) is faster than the Java2 version.

This is the asm of inner loop of computeNewValue() compiled with LDC:

.LBB10_2:
movl 24(%eax), %esi
movl (%esi,%edx,4), %esi
movl 32(%eax), %edi
movsd (%edi,%edx,8), %xmm1
mulsd (%esi), %xmm1
subsd %xmm1, %xmm0
movsd %xmm0, (%eax)
incl %edx
cmpl %ecx, %edx
jl .LBB10_2

------------------------------------

D04

I have renamed a method:
BiGraph.compute() => graph.computeStep();

And I have added a test for the sanity of the input numDegree:
if (numDegree > numNodes) {...

The program allocates a linked list of nodes, and then doesn't change that topology any more, just iterates on them. Both allocating many single nodes, and iterating on a linked list, today are slow operations (the original C code was old). So today it's much more efficient to allocated many or all Nodes in an array (this program contains a bipartite graph, so there are two arrays).

So I can also remove the "next" pointer field of Node, that was used for the links of the list.

In this D version the arcs are kept as pointers. Now the opApply isn't needed (this increases speed because I now loop on arrays, but loses some encapsulation).

The fillTable() method becomes the createTable() because it allocates an array of the nodes.

Timings:

...$ time ./em3d04 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
0.13 0.94 0.48 0.40
Propagating field values for 50 iteration(s)...
EM3D build time 1.95
EM3D compute time 1.18
EM3D total time 3.13
Done!
real 0m3.326s
user 0m2.696s
sys 0m0.540s

...$ time ./em3d04 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
0.13 0.92 0.46 0.40
Propagating field values for 200 iteration(s)...
EM3D build time 1.91
EM3D compute time 4.35
EM3D total time 6.26
Done!
real 0m6.443s
user 0m5.908s
sys 0m0.432s

The build time is not changed, I don't know why, probably disabling the GC allows for an efficient enough memory allocation. But now the compute time is decreased, because the program can scan the arrays more efficiently.

If a program like this gets used in practice, the build time is not important, because the number of iterations is probably large, so the compute time has to be as small as possible.

Now both timings are better than the Java2 timings.

This is the asm of inner loop of computeNewValue() compiled with LDC:

.LBB9_2:
movl 12(%eax), %esi
movl (%esi,%edx,4), %esi
movl 20(%eax), %edi
movsd (%edi,%edx,8), %xmm1
mulsd (%esi), %xmm1
subsd %xmm1, %xmm0
movsd %xmm0, (%eax)
incl %edx
cmpl %ecx, %edx
jb .LBB9_2

------------------------------------

D05

The CPU is able to use the pointers among Nodes in a quick way, but the number of nodes is probably limited. The program can increase its speed if there is less data traffic through the CPU cache. So I have replaced the pointers by 16 bit (ushort) indexes. This allows up to 2^16 nodes. If you need more, you can replace:
alias ushort TyIndex;
With:
alias uint TyIndex;
But this may produce code slower than D04.

Timings:

...$ time ./em3d05 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
0.06 0.94 0.38 0.42
Propagating field values for 50 iteration(s)...
EM3D build time 1.80
EM3D compute time 1.00
EM3D total time 2.80
Done!
real 0m2.937s
user 0m2.540s
sys 0m0.324s

...$ time ./em3d05 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
0.07 0.95 0.37 0.39
Propagating field values for 200 iteration(s)...
EM3D build time 1.78
EM3D compute time 4.02
EM3D total time 5.80
Done!
real 0m5.955s
user 0m5.508s
sys 0m0.360s

This is the asm of inner loop of computeNewValue() compiled with LDC:

.LBB9_2:
movl 20(%eax), %edi
movsd (%edi,%esi,8), %xmm1
movl 12(%eax), %edi
movzwl (%edi,%esi,2), %edi
imull $40, %edi, %edi
mulsd (%edx,%edi), %xmm1
subsd %xmm1, %xmm0
movsd %xmm0, (%eax)
incl %esi
cmpl %ecx, %esi
jb .LBB9_2

------------------------------------

D06

Now I look for possible algorithmic improvements.
makeUniqueNeighbors() contains stupid quadratic code to avoid duplicating Neighbors. I have tried to use a D associative array, and then a set implemented as a bit vector (using bt/bts intrinsics), but the most efficient seems a set of booleans implemented with just an array of ubytes.

I have renamed:
coeffs => inCoeffs

Timings:

...$ time ./em3d06 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
0.07 0.11 0.40 0.39
Propagating field values for 50 iteration(s)...
EM3D build time 0.97
EM3D compute time 1.03
EM3D total time 2.00
Done!
real 0m2.145s
user 0m1.748s
sys 0m0.324s

...$ time ./em3d06 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
0.07 0.11 0.37 0.40
Propagating field values for 200 iteration(s)...
EM3D build time 0.95
EM3D compute time 4.11
EM3D total time 5.06
Done!
real 0m5.231s
user 0m4.804s
sys 0m0.352s

The build time for 5000 nodes with 300 arcs is half as before.

This is the asm of inner loop of computeNewValue() compiled with LDC:

.LBB9_2:
movl 20(%eax), %edi
movsd (%edi,%esi,8), %xmm1
movl 12(%eax), %edi
movzwl (%edi,%esi,2), %edi
imull $40, %edi, %edi
mulsd (%edx,%edi), %xmm1
subsd %xmm1, %xmm0
movsd %xmm0, (%eax)
incl %esi
cmpl %ecx, %esi
jb .LBB9_2

------------------------------------

D07

Now the most common optimizations are done, and the code looks good enough. To improve the code some more we have to think more about the CPU cache.

The computations (of "compute time") are done on an array of large structs Node. But only few fields are actually necessary for such computation: value, inbound and inCoeffs (total 6 words), so if I remove the useless data, the iterations on the array will be (hopefully) faster.

I don't know how to remove items from the struct. The simpler way to solve this problem is to define a second Node struct, a Node2, with just the essential fields. Creating the two arrays of Node2 is fast, because all arrays of inbound and inCoeffs are just copied by reference.

So I add the eNodes2 and hNodes2 dynamic arrays of Node2 to BiGraph (now encapsulation looks gone, but in practice I don't think the original design was good. The only data structure that has to know about a collection of Nodes2 has to be BiGraph, and not Node2 itself).

There's some redundancy too here in a Node2: the inbound and inCoeffs arrays have the same length, so the Node2 can use just 5 words. There are few ways to remove this field, but the first field (the value) is a double, and for max performance it must be aligned to 8 bytes. So I have done few experiments, but they are failed, the program was slower, with a small memory usage reduction. So I have kept all the 6 words.

Timings:

...$ time ./em3d07 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Detailed creation timings: 0.08 0.10 0.37 0.39 0.00
Propagating field values for 50 iteration(s)...
EM3D build time 0.94
EM3D compute time 0.92
EM3D total time 1.86
Done!
real 0m1.993s
user 0m1.600s
sys 0m0.316s

...$ time ./em3d07 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Detailed creation timings: 0.07 0.10 0.39 0.40 0.00
Propagating field values for 200 iteration(s)...
EM3D build time 0.96
EM3D compute time 3.62
EM3D total time 4.58
Done!
real 0m4.718s
user 0m4.292s
sys 0m0.360s

The build time of the graph is the same, but the computing time is decreased.
The time needed to build the arrays of Node2 is very small.

This is the asm of inner loop of computeNewValue() compiled with LDC:

.LBB9_2:
movl 20(%eax), %edi
movsd (%edi,%esi,8), %xmm1
movl 12(%eax), %edi
movzwl (%edi,%esi,2), %edi
imull $24, %edi, %edi
mulsd (%edx,%edi), %xmm1
subsd %xmm1, %xmm0
movsd %xmm0, (%eax)
incl %esi
cmpl %ecx, %esi
jb .LBB9_2

-----------------------------------

D08

We can improve the code more taking a look at how hValues are accessed, a sequential access is faster. But I've seen that the inbound[i] are already sorted.

So I have to take a better look at the very small loop that performs one of the two halves of a computation step:

void computeNewValue(Node2[] otherTable) {
  for (int i; i < inbound.length; i++)
    value -= inCoeffs[i] * otherTable[inbound[i]].value;
}

There's not much that can be improved here. I have drawn on paper the simple data structures involved here, and with that I've seen that inbound[i] performs (forward but) large jumps in an array of largish structs (6 words each) to find the "value" fields. This forces the CPU cache to a lot of traffic. If we reduce this traffic the iterations will get faster.

The simple way to do this is to pull the values out of the nodes2 and put them in a uniform array, that's used in parallel to the Node2 array.

// Node2 of D07:
struct Node2 {
    double value;
    Node.TyIndex[] inbound;
    double[] inCoeffs;
}

// Node2 of D08:
struct Node2 {
    Node.TyIndex[] inbound;
    double[] inCoeffs;
    static double[] eValues, hValues;
}

Now the jumps are performed on arrays (eValues and hValues) with just 2 words/item.

To perform a better computation I have had to split computeNewValue() into eValuesStep() and hValuesStep(). I have pulled the outer loop like foreach(j, ref n; hNodes2) inside them, this may help the DMD compiler too, because it doesn't inline functions/methods that have a loop inside.

I also have had to add a "aux_val" auxiliary variable inside the eValuesStep/hValuesStep functions, because it seems LDC/LLVM was not able to pull the access to Node2.hValues[j] out of the loop. I don't know why [see below, the explanation after D01b].

Timings:

...$ time ./em3d08 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Detailed creation timings: 0.07 0.10 0.37 0.40 0.00
Propagating field values for 50 iteration(s)...
EM3D build time 0.94
EM3D compute time 0.74
EM3D total time 1.68
Done!
real 0m1.817s
user 0m1.416s
sys 0m0.332s

...$ time ./em3d08 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Detailed creation timings: 0.07 0.10 0.37 0.39 0.00
Propagating field values for 200 iteration(s)...
EM3D build time 0.93
EM3D compute time 2.96
EM3D total time 3.89
Done!
real 0m4.038s
user 0m3.628s
sys 0m0.336s

The compute time is decreased enough.

This is the asm of inner loop of eValuesStep() compiled with LDC:

.LBB9_4:
movzwl (%esi,%edi,2), %ebp
movsd (%edx,%edi,8), %xmm1
mulsd (%ebx,%ebp,8), %xmm1
subsd %xmm1, %xmm0
incl %edi
cmpl %ecx, %edi
jb .LBB9_4

------------------------------------

D09

There's one last possible optimization of the memory usage that I can see. I can remove again the redundancy from Node2, because now it doesn't contain a double, and now probably I can use 3 32-bit words.

The new Node2 is:

struct Node2 {
  Node.TyIndex* inbound;
  double* inCoeffs;
  int inbound_len;
  static double[] eValues, hValues;
}

Timings:

...$ time ./em3d09 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Detailed creation timings: 0.08 0.10 0.37 0.39 0.00
Propagating field values for 50 iteration(s)...
EM3D build time 0.94
EM3D compute time 0.74
EM3D total time 1.68
Done!
real 0m1.821s
user 0m1.444s
sys 0m0.296s

...$ time ./em3d09 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Detailed creation timings: 0.07 0.11 0.37 0.39 0.00
Propagating field values for 200 iteration(s)...
EM3D build time 0.94
EM3D compute time 2.95
EM3D total time 3.89
Done!
real 0m4.030s
user 0m3.632s
sys 0m0.332s

The computing time is about the same. The memory saving compared to D08 is very small, something like 40 KB.

It may be possible to vectorize the computing loop, but I stop here.

Compared to the Java2 version the speed of this last D09 version is not much higher, because the computing loop is very tight and the JavaVM is able to optimize it very well, quite better than LDC, see the compute time of Java2 compared to the compute time of D01: 4.35 compared to 5.97. A shame for D/LDC/LLVM :-)

Other Olden benchmarks show a bigger gap between the performance of the Java and optimized D code.

This is the asm of inner loop of eValuesStep() compiled with LDC:

.align 16
.LBB9_4:
movzwl (%esi,%edi,2), %ebp
movsd (%edx,%edi,8), %xmm1
mulsd (%ebx,%ebp,8), %xmm1
subsd %xmm1, %xmm0
incl %edi
cmpl %ecx, %edi
jl .LBB9_4

------------------------------------

D10

Update 1.2, Oct 27 2006:

There is another simple performance optimization that can be done. The memory for the Nodes and their arcs can be allocated from the C heap (and in some cases such memory can even be allocated with malloc instead of calloc, but in this programs this has no significant performance difference).

The memory coming from the C heap is usually aligned to 4 bytes, so it's not fit for storing values and coefficients that in this program are doubles, that are used much more efficiently when aligned to 8 bytes. But in this program the actual computations performed on double FP numbers are done on arrays allocated in Node2, that are allocated from the D GC heap that returns memory aligned to 16 bytes. The only problem may come from Node.inCoeffs that's copied as is to Node2 inCoeffs. So this allocation needs a little of extra care (see makeFromNodes()).

I can even allocate all "outbound" arrays at once, because they are all of the same length, but this change will not change performance significantly, because that time is part of the first timing of the "Detailed creation timings:", that's about 0.03-0.04 seconds for 5000 nodes.

I have moved the disable() of the GC below, when the computing loops are done, because there's no point in keeping the GC active during those loops, that produce no garbage.

Timings:

...$ time ./em3d10 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Detailed creation timings: 0.04 0.10 0.14 0.19 0.00
Propagating field values for 50 iteration(s)...
EM3D build time 0.47
EM3D compute time 0.60
EM3D total time 1.07
Done!
real 0m1.203s
user 0m0.968s
sys 0m0.148s

...$ time ./em3d10 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Detailed creation timings: 0.03 0.10 0.16 0.18 0.00
Propagating field values for 200 iteration(s)...
EM3D build time 0.47
EM3D compute time 2.46
EM3D total time 2.93
Done!
real 0m3.061s
user 0m2.844s
sys 0m0.124s

Not just (as expected) the build times are lower, but the compute ones too are lower, I don't know why, maybe the memory from the C heap has more coherence (more contiguous, reducing cache misses. The GC adds some spaces, because it returns memory blocks aligned to 16 bytes).

------------------------------------

D11

Update 1.2, Oct 27 2006:

To reduce the time used by makeFromNodes(), and hopefully to increase the computation loops (with a better cache coherence) we can cut the inbound and inCoeffs arrays of Node (later copied into Node2) from a large memory block allocated all at once (again, doubles are better alighed to 8 bytes) to do this I have created two memory arenas, with the DoubleArena and IndexArena structs.

Timings:

...$ time ./em3d11 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Detailed creation timings: 0.04 0.10 0.00 0.42 0.00
Propagating field values for 50 iteration(s)...
EM3D build time 0.56
EM3D compute time 0.58
EM3D total time 1.14
Done!
real 0m1.271s
user 0m1.028s
sys 0m0.164s

...$ time ./em3d11 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Detailed creation timings: 0.04 0.09 0.00 0.43 0.01
Propagating field values for 200 iteration(s)...
EM3D build time 0.57
EM3D compute time 2.23
EM3D total time 2.80
Done!
real 0m2.961s
user 0m2.652s
sys 0m0.184s

...$ time ./em3d11 -n 5000 -d 300 -i 2000 -m
Initializing em3d random graph...
Detailed creation timings: 0.03 0.11 0.00 0.43 0.00
Propagating field values for 2000 iteration(s)...
EM3D build time 0.57
EM3D compute time 23.39
EM3D total time 23.96
Done!
real 0m24.621s
user 0m23.869s
sys 0m0.144s

Now the build time is a little higher (I don't know why), while the computing loops are faster (I don't know why), so when the number of iterations is 200 the total time is lower.

In the detailed creation timings you can also see that makeFromNodes() is now very fast, while updateFromNodes() is quite slower (I don't know why. Here DMD is twice faster).

This version also needs a little less RAM compared to D10, about 39 MB with -n 5000 -d 300. Java3 needs about 197 MB for the same graph.

Now the D11 program is fast enough, and uses a low enough memory, that the limit of 65000 nodes given by the ushort indexes can be felt. Using an uint as TyIndex the memory used by D11 with -n 5000 -d 300 is 51 MB.

Timings of D11 with TyIndex=uint:

...$ time ./em3d11 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Detailed creation timings: 0.09 0.11 0.00 0.48 0.00
Propagating field values for 50 iteration(s)...
EM3D build time 0.68
EM3D compute time 0.68
EM3D total time 1.36
Done!
real 0m1.525s
user 0m1.220s
sys 0m0.200s

...$ time ./em3d11 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Detailed creation timings: 0.06 0.12 0.00 0.50 0.00
Propagating field values for 200 iteration(s)...
EM3D build time 0.68
EM3D compute time 2.71
EM3D total time 3.39
Done!
real 0m3.597s
user 0m3.252s
sys 0m0.184s

Using such larger indexes the running time is not much higher, but in this case using just pointers is probably faster.

This is the asm of inner loop of eValuesStep() of D11 compiled with LDC, when TyIndex=uint:

.LBB14_4:
movl (%esi,%edi,4), %ebp
movsd (%edx,%edi,8), %xmm1
mulsd (%ebx,%ebp,8), %xmm1
subsd %xmm1, %xmm0
incl %edi
cmpl %ecx, %edi
jl .LBB14_4

------------------------------------

D11b
(lateral branch)

Update 1.2, Oct 27 2006:

When the number of nodes is high, instead of storing ushort indexes, I can store ushort deltas. And because the indexes are ordered such deltas are never negative. If links are well spread, then such deltas are usually small, and they can be used to index far more than 2^16 nodes. If such links are randomly distriuited, you can probably manage millions of nodes in a safe enough way, and it's easy to add a runtime test when they are created to be sure they don't overflow.

I have done a test, using the usual -n 5000 -d 300 arguments with the same seed=783, in such case the maximum delta is 240, so just one ubyte suffices! ubyte indexes reduce traffic through the cache, so they may speed up the program a little more. The D11b uses such TyDelta in Node2 but I have kept usign TyIndex in Node to keep the program simpler.

Timings of D11b with TyIndex=ushort, TyDelta=ubyte:

...$ time ./em3d11b -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Detailed creation timings: 0.04 0.10 0.00 0.42 0.02
Propagating field values for 50 iteration(s)...
EM3D build time 0.59
EM3D compute time 0.56
EM3D total time 1.15
Done!
real 0m1.266s
user 0m1.032s
sys 0m0.156s

...$ time ./em3d11b -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Detailed creation timings: 0.04 0.11 0.00 0.42 0.02
Propagating field values for 200 iteration(s)...
EM3D build time 0.59
EM3D compute time 2.20
EM3D total time 2.79
Done!
real 0m2.968s
user 0m2.676s
sys 0m0.160s

...$ time ./em3d11b -n 5000 -d 300 -i 2000 -m
Initializing em3d random graph...
Detailed creation timings: 0.03 0.12 0.00 0.48 0.02
Propagating field values for 2000 iteration(s)...
EM3D build time 0.65
EM3D compute time 21.98
EM3D total time 22.63
Done!
real 0m23.252s
user 0m22.477s
sys 0m0.204s

The iteration is a bit faster, but the build time of Nodes2 is a little slower (by about 0.02 seconds). So for 200 iterations the running time is about the same, while for 2000 you can see some difference. For TyDelta==ubyte this D11b program is not very useful (unless you have few nodes), but for larger graphs such delta encoding can be useful to keep using ushorts even when there are more than 2^16 nodes.

Timings of D11b with TyIndex=uint, TyDelta=ushort:

...$ time ./em3d11b -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Detailed creation timings: 0.04 0.11 0.00 0.44 0.02
Propagating field values for 50 iteration(s)...
EM3D build time 0.61
EM3D compute time 0.56
EM3D total time 1.17
Done!
real 0m1.309s
user 0m1.032s
sys 0m0.180s

...$ time ./em3d11b -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Detailed creation timings: 0.05 0.10 0.00 0.43 0.02
Propagating field values for 200 iteration(s)...
EM3D build time 0.60
EM3D compute time 2.20
EM3D total time 2.80
Done!
real 0m2.997s
user 0m2.684s
sys 0m0.176s

D11b with TyDelta=ushort is just a little slower than D11b with TyDelta=ubyte, so in most situations it can be enough for a number of nodes >> 2^16 if the arcs are spread in an uniform random way.

This em3d program is just a benchmark, but in a real program you want to add class invariants, unittests, several safeties for the memory, and ways to deallocate memory when not used any more, etc.

------------------------------------

D12
(this ignores the D11b branch)

Update 1.3, Oct 27 2006:

The items of inbound and inCoeffs are accessed in parallel, so it can be useful for them to be close to each other. Ideally the items of inbound and inCoeffs are better kept in the same cache line, that's a block of 64 bytes (and I think it has to be aligned too). But I can't put them into a struct because it wastes a lot of space (such struct has to be 16 bytes long to keep the double it contains aligned to 8 bytes), and wasting space increases cache misses.

If I want to pack pairs of double + ushort in a struct that inside an array is aligned to 8 bytes, I need to pack 4 doubles and 4 ushorts, this needs 8*4 + 2*4 = 32 + 8 = 40 bytes. But this straddles a cache line, and I think this is negative. So to pack as much as possible in a cache line I can use 6 pairs, that need 8*6 + 2*6 = 48 + 12 = 60 bytes, that needs 4 bytes of padding, this wastes 6.25% of space, I think it's acceptable. I can define it like this:

struct PairsPack {
  static if (TyIndex.sizeof == 2)
    const int NPAIRS = 6; // 8*6 + 2*6 + 4 = 48 + 12 + 4 = 64
  else static if (TyIndex.sizeof == 4)
    const int NPAIRS = 5; // 8*5 + 4*5 + 4 = 40 + 20 + 4 = 64
  else
      static assert(0);

  double[NPAIRS] weights;
  TyIndex[NPAIRS] inbounds;
  uint _padding;
}

Just to be sure I'll allocate the array of PairsPack aligned to 64 bytes.

But generally the number of inbound arcs in a node isn't a multiple of 6, so I need to waste some of those pairs, or use part of an already used PairsPack. Both solutions have advantages and disadvantages. I choose the option to not waste memory, this requires a little more complex indexing of the sub-part of a PairsPack, but allows me to allocate the array of PairsPack in a simpler way.

This D12 was the hardest version to create, the code is quite hairy, and hard to maintain and understand. And it's slow (the Range!() that I have used is not necessary. LLVM was able to unroll that loop inside eValuesStep/hValuesStep by itself).

Timings:

...$ time ./em3d12o -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Detailed creation timings: 0.04 0.11 0.00 0.43 0.19
Propagating field values for 50 iteration(s)...
EM3D build time 0.78
EM3D compute time 0.68
EM3D total time 1.46
Done!
real 0m1.614s
user 0m1.240s
sys 0m0.284s

...$ time ./em3d12o -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Detailed creation timings: 0.04 0.11 0.00 0.41 0.20
Propagating field values for 200 iteration(s)...
EM3D build time 0.76
EM3D compute time 2.65
EM3D total time 3.41
Done!
real 0m3.623s
user 0m3.176s
sys 0m0.308s

The asm of inner loop of eValuesStep() of D11 compiled with LDC:

.LBB14_4:
movzwl 50(%eax), %ebp
movsd 8(%eax), %xmm1
mulsd (%esi,%ebp,8), %xmm1
movzwl 48(%eax), %ebp
movsd (%eax), %xmm2
mulsd (%esi,%ebp,8), %xmm2
subsd %xmm2, %xmm0
subsd %xmm1, %xmm0
movzwl 52(%eax), %ebp
movsd 16(%eax), %xmm1
mulsd (%esi,%ebp,8), %xmm1
subsd %xmm1, %xmm0
movzwl 54(%eax), %ebp
movsd 24(%eax), %xmm1
mulsd (%esi,%ebp,8), %xmm1
subsd %xmm1, %xmm0
movzwl 56(%eax), %ebp
movsd 32(%eax), %xmm1
mulsd (%esi,%ebp,8), %xmm1
subsd %xmm1, %xmm0
movzwl 58(%eax), %ebp
movsd 40(%eax), %xmm1
mulsd (%esi,%ebp,8), %xmm1
subsd %xmm1, %xmm0
addl $64, %eax
decl %ebx
jne .LBB14_4

------------------------------------

Java3

Now I can think porting back some of the optimizations I have implemented in D to Java. Java don't uses structs, so several things are not possible.

In this Java3 I have used the uniqueNeighborsSet set, implemented as the D code.

Timings:

...$ time java -server Em3d3 -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Propagating field values for 50 iteration(s)...
EM3D build time 1.681
EM3D compute time 1.14
EM3D total time 2.821
Done!
real 0m3.138s
user 0m2.600s
sys 0m0.416s

...$ time java -server Em3d3 -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Propagating field values for 200 iteration(s)...
EM3D build time 1.649
EM3D compute time 4.29
EM3D total time 5.943
Done!
real 0m6.239s
user 0m5.656s
sys 0m0.452s

More optimizations may be ported from D to Java.

------------------------------------

D01b
(lateral branch)

Looking at the asm of the inner loop of computeNewValue for D01 and D09, I think the D01 can be improved with an auxiliary variable:

void computeNewValue() {
  auto aux = this.value;
  for (int i = 0; i < fromCount; i++)
    aux -= coeffs[i] * fromNodes[i].value;
  this.value = aux;
}

Timings:

...$ time ./em3d01b -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Propagating field values for 50 iteration(s)...
EM3D build time 4.89
EM3D compute time 1.28
EM3D total time 6.17
Done!
real 0m6.335s
user 0m5.804s
sys 0m0.464s

...$ time ./em3d01b -n 5000 -d 300 -i 200 -m
Initializing em3d random graph...
Propagating field values for 200 iteration(s)...
EM3D build time 4.92
EM3D compute time 5.23
EM3D total time 10.15
Done!
real 0m10.601s
user 0m10.105s
sys 0m0.440s

LDC/LLVM must be able to perform that optimization (pulling this.value out of the loop) by itself.

This is the asm of inner loop of computeNewValue() compiled with LDC:

.LBB11_2:
movl (%edx,%edi,4), %ebx
movsd (%esi,%edi,8), %xmm1
mulsd 8(%ebx), %xmm1
subsd %xmm1, %xmm0
incl %edi
cmpl %ecx, %edi
jl .LBB11_2

This asm is very short, but it's quite slower than D09 anyway. I don't know what kind of optimizations are done by the JavaVM on the Java1 code (there is a way to look at the asm produced by the JVM, but it's not handy).

Update 1.1, Oct 26 2006: now I think I know why LDC isn't able to perform that optimization in the computeNewValue() loop: the compiler doesn't know that "value" on the right is always distinct from "value" on the left, because this is a bipartite graph, where no self-loops are allowed. So it can't pull the "value" of the left out of the loop.

To perform the optimization the compiled need more semantics. Future programming languages may allow the programmer to give such semantics to the compiler.

I have done a similar optimization (pulling "value" out of the loop) in the Java3 version, with no change in performance, so probably the JavaVM is somehow able to perform that optimization.

------------------------------------

Python1

I have created a Python version too, that uses Psyco. It's similar to the Java3 version.
I have seen that the faster unique_neighbors_set is using just a Python set.

I have added __slots__ to both Random and Node, this doubles the performance.

Timings:

...$ time python em3d.py -n 5000 -d 300 -i 50 -m
Initializing em3d random graph...
Detailed creation timings: 0.14 3.86 0.16 4.32
Propagating field values for 50 iteration(s)...
EM3D build time 8.48
EM3D compute time 54.70
EM3D total time 63.19
Done!
real 1m4.320s
user 0m59.628s
sys 0m3.876s

I have used:
Python 2.6.2 (release26-maint, Apr 19 2009, 01:56:41)
Psyco 1.6.0 final

------------------------------------

Python2

While improving the D code, and especially when I have created the Python1 version, I have felt the code as too much complex for the simple operations it performs. So I have reduced the Python code, removing useless parts. The Python2 version is almost the shortest Python code that produces the same output (there are ways to shorten it a little more, but I am not doing code golf here, my purposes are different).

The Python2 code is 67 lines long, while the Java3 is 481 lines including the comments.

------------------------------------

Python3

Then I have replaced the random() and sample() with ones from the Python standard library, I have removed the printing code, and I have reorganized the code a little more.

The result is short enough (21 nonempty lines) to be shown here too:

from random import random, sample

class Node:
    def __init__(self, value):
        self.value = value
        self.in_arcs = []

n_nodes, in_degree, n_steps = 15, 5, 5

h_nodes = [Node(random()) for i in xrange(n_nodes)]
e_nodes = [Node(random()) for i in xrange(n_nodes)]

def make_in_arcs(nodes, other_nodes, in_degree):
    for n1 in nodes:
        for n2 in sample(other_nodes, in_degree):
            n2.in_arcs.append((n1, random()))

make_in_arcs(h_nodes, e_nodes, in_degree)
make_in_arcs(e_nodes, h_nodes, in_degree)

def half_step(nodes):
    for n1 in nodes:
        for n2, weight in n1.in_arcs:
            n1.value -= weight * n2.value

for i in xrange(n_steps):
    half_step(e_nodes)
    half_step(h_nodes)

This code shows the essential, and for me it's much simpler to follow and understand. This code may be conveted to C/D again, if necessary. The original C code was harder to understand, and much more complex. Removing the noise and useless parts allows me to understand the algorithm better, this is a simple algorithm. Even if you don't understand this code immediately, the complexity left is necessary, it's not spurious. Generally good programs aren't the clever and complex ones, but ones that look "obvious". This Python code shows that lot of the complexity of the original Java code was spurious.

------------------------------------

Python4

This is similar to the Python3 version, I have just encoded a node in a simpler way, using a single list. The first item is the "value" and all the following ones are pairs of node-weight. This code is just 17 nonempty lines long. For me Python3 version is more readable.

------------------------------------

TDPL Update

2009-10-25T10:22:45+00:00

Andrei has passed the 100,000 word mark on his forthcoming book, The D Programming Language Congrats, Andrei!

LLVM 2.6

2009-10-24T18:30:41+00:00

Just in case you're not that well informed, Chris Lattner has just announced the release of LLVM 2.6. Enjoy!

Bartosz Milewski

2009-10-21T23:02:33+00:00

If you want to understand C++ template metaprogramming (TMP) you have to know functional programming. Seriously. I want you to think of TMP as maximally obfuscated (subset of) Haskell, and I’ll illustrate this point by point. If you don’t know Haskell, don’t worry, I’ll explain the syntax as I go.

The nice thing about single-paradigm languages like Haskell is that they have very simple syntax (think of Lisp that does everything with just a bunch of parentheses). I will start the Haskell-C++TMP mapping with basics, like functions and recursion, but I’ll try to cover a lot more, including higher-order functions, pattern matching, list comprehension (did you know it was expressible in C++?), and more.

Keep in mind that my Haskell examples are runtime functions operating on runtime data whereas their C++ TMP equivalents are compile-time templates operating mostly on types. Operation on types are essential in providing correct and efficient implementations of parametrized classes and functions.

By necessity the examples are simple, but the same mapping may be applied to much more complex templates from the C++ Standard Library and Boost. As a bonus, I’ll also explain the hot new thing, variadic templates.

Functional Approach to Functions

How do you implement useful functions if you don’t have mutable variables, if statements, or loops? To a C++ programmer that might seem like an impossible task. But that’s the reality of C++ compile-time language that forms the basis of TMP. Functional programming to the rescue!

As a warm-up, let’s see how Haskell implements a simple function, the factorial:

fact 0 = 1
fact n = n * fact (n - 1)

The first line states that the factorial of zero is one. The second line defines factorial for a non-zero argument, n (strictly speaking it only works for positive non-zero arguments). It does it using recursion: factorial of n is equal to n times the factorial of n-1. The recursion stops when n is equal to zero, in which case the first definition kicks in. Notice that the definition of the function fact is split into two sub-definitions. So when you call:

fact 4

the first definition is looked up first and, if it doesn’t match the argument (which it doesn’t), the second one comes into play. This is the simplest case of pattern matching: 4 doesn’t match the “pattern” 0, but it matches the pattern n.

Here’s almost exactly the same code expressed in C++ TMP:

template<int n> struct
fact {
    static const int value = n * fact<n - 1>::value;
};

template<> struct
fact<0> { // specialization for n = 0
    static const int value = 1;
};

You might notice how the horrible syntax of C++ TMP obscures the simplicity and elegance of this code. But once you are equipped with the C++/Haskell decoder ring, things become a lot clearer.

Let’s analyze this code. Just like in Haskell, there are two definitions of fact, except that their order is inverted. This is because C++ requires template specialization to follow the template’s general definition (or declaration, as we’ll see later). The pattern matching of arguments in C++ does not follow the order of declarations but rather is based on “best match”. If you instantiate the template with argument zero:

cout << "Factorial of 0 = " << fact<0>::value << endl;

the second pattern, fact<0>, is a better fit. Otherwise the first one, <int n>, is used.

Notice also the weird syntax for “function call”

fact<n>::value

and for the “return statement”

static const int value = n * fact<n - 1>::value;

This all makes sense if you look at templates as definitions of parameterized types, which was their initial purpose in C++. In that interpretation, we are defining a struct called fact, parameterized by an integer n, whose sole member is a static const integer called value. Moreover, this template is specialized for the case of n equal zero.

Now I want you to forget about what I just said and put on the glasses which make the C++ code look like the corresponding Haskell code.

Here’s another example–this time of a predicate (a function returning a Boolean):

is_zero 0 = True
is_zero x = False

Let’s spice it up a little for C++ and define a predicate on types rather than integers. The following compile-time function returns true only when the type T is a pointer:

template<class T> struct
isPtr {
    static const bool value = false;
};

template<class U> struct
isPtr<U*> {
    static const bool value = true;
};

This time the actual argument to isPtr is first matched to the more specialized pattern, U* and, if it fails, the general pattern is used.

We can add yet another specialization, which will pattern-match a const pointer:

template<class U> struct
isPtr<U * const> {
    static const bool value = true;
};

These types of type predicates may be, for instance, used to select more flexible and efficient implementations of parameterized containers. Think of the differences between a vector of values vs. a vector of pointers.

Lists

The basic data structure in functional languages is the list. Haskell’s lists are introduced using square brackets. For instance, a list of three numbers, 1, 2, 3, looks like:

[1, 2, 3]

List processing in functional languages follows the standard pattern: a list is split into head and tail, an operation is performed on the head, and the tail is processed using recursion. The splitting is done by pattern matching: the Haskell pattern being (head:tail) (to be precise, the colon in parentheses represents the cons operation–the creation of a list by prepending an element to an existing list).

Here’s a simple function, count, that calculates the length of a list:

count [] = 0
count (head:tail) = 1 + count tail

The first pattern, [], matches an empty list; the second a non-empty one. Notice that a function call in Haskell doesn’t use parentheses around arguments, so count tail is interpreted as a call to count with the argument tail.

Before C++0x, TMP was severely crippled by the lack of a list primitive. People used separate definitions for a list of zero, one, two, etc., elements, and even used special macros to define them. This is no longer true in C++0x, thanks to variadic templates and template parameter packs. Here’s our Haskel count translated into C++ TMP:

// Just a declaration
template<class... list> struct
count;

template<> struct
count<> {
    static const int value = 0;
};

template<class head, class... tail> struct
count<head, tail...> {
    static const int value = 1 + count<tail...>::value;
};

First we have a declaration (not a definition) of the template count that takes a variable number of type parameters (the keyword class or typename introduces a type parameter). They are packed into a template parameter pack, list.

Once this general declaration is visible, specializations may follow in any order. I arranged them to follow the Haskell example. The first one matches the empty list and returns zero. The second one uses the pattern, <head, tail…>. This pattern will match any non-empty list and split it into the head and the (possibly empty) tail.

To “call” a variadic template, you initiate it with an arbitrary number of arguments and retrieve its member, value, e.g.,

int n = count<int, char, long>::value; // returns 3

A few words about variadic templates: A variadic template introduces a template parameter pack using the notation class… pack (or int… ipack, etc…). The only thing you may do with a pack is to expand it and pass to another variadic template. The expansion is done by following the name of the pack with three dots, as in tail…. You’ll see more examples later.

Variadic templates have many applications such as type-safe printf, tuples (objects that store an arbitrary number of differently typed arguments), variants, and many more.

Higher-Order Functions and Closures

The real power of functional programming comes from treating functions as first class citizens. It means that you may pass functions to other functions and return functions from functions. Functions operating on functions are called higher-order functions. Surprisingly, it seems like compile-time C++ has better support for higher-order functions than run-time C++.

Let’s start with a Haskell example. I want to define a function that takes two predicate functions and returns another predicate function that combines the two using logical OR. Here it is in Haskell:

or_combinator f1 f2 =
    λ x -> (f1 x) || (f2 x)

The or_combinator returns an anonymous function (the famous “lambda”) that takes one argument, x, calls both f1 and f2 with it, and returns the logical OR of the two results. The return value of or_combinator is this freshly constructed function. I can then call this function with an arbitrary argument. For instance, here I’m checking if 2 is either zero or one (guess what, it isn’t!):

(or_combinator is_zero is_one) 2

I put the parentheses around the function and its arguments for readability, although they are not strictly necessary. 2 is the argument to the function returned by or_combinator.

The lambda that’s returned from or_combinator is actually a closure. It “captures” the two arguments, f1 and f2 passed to or_combinator. They may be used long after the call to or_combinator has returned.

It might take some getting used to it before you are comfortable with functions taking functions and returning functions, but it’s much easier to learn this stuff in Haskell than in the obfuscated C++. Indeed, here’s an almost direct translation of this example:

template<template<class> class f1, template<class> class f2> struct
or_combinator {
    template<class T> struct
    lambda {
        static const bool value = f1<T>::value || f2<T>::value;
    };
};

Since in the metalanguage a function is represented by a template, the template or_combinator takes two such templates as arguments. It “calls” these templates using the standard syntax f<T>::value. Actually, the or_combinator doesn’t call these functions. Instead it defines a new template, which I call lambda, that takes the argument T and calls those functions. This template acts like a closure–it captures the two templates that are the arguments to or_combinator.

Here’s how you may use the or_combinator to combine two tests, isPtr and isConst and apply the result to the type const int:

std::cout
   << "or_combinator<isPtr, isConst>::lambda<const int>::value = "
   << or_combinator<isPtr, isConst>::lambda<const int>::value
   << std::endl;

Such logical combinators are essential for predicate composability.

Higher-Order Functions Operating on Lists

Once you combine higher-order functions with lists you have a powerful functional language at your disposal. Higher-order functions operating on lists look very much like algorithms. Let me show you some classic examples. Here’s the function (or algorithm), all, that returns true if and only if all elements of a list satisfy a given predicate.

all pred [] = True
all pred (head:tail) = (pred head) && (all pred tail)

By now you should be familiar with all the techniques I used here, like pattern matching or list recursion.

Here’s the same code obfuscated by the C++ syntax:

template<template<class> class predicate, class... list> struct
all;

template<template<class> class predicate> struct
all<predicate> {
    static const bool value = true;
};

template<
    template<class> class predicate,
    class head,
    class... tail> struct
all<predicate, head, tail...> {
    static const bool value =
        predicate<head>::value
        && all<predicate, tail...>::value;
};

Except for the initial declaration required by C++ there is a one-to-one paradigm match between the two implementations.

Another useful algorithm, a veritable workhorse of functional programming, is “fold right” (together with it’s dual partner, “fold left”). It folds a list while accumulating the results (that’s why in runtime C++ this algorithm is called “accumulate”). Here’s the Haskell implementation:

foldr f init [] = init
foldr f init (head:tail) =
    f head (foldr f init tail)

Function f, which is the first argument to foldr, takes two arguments, the current element of the list and the accumulated value. Its purpose is to process the element and incorporate the result in the accumulator. The new accumulated value is then returned. It is totally up to the client to decide what kind of processing to perform, how it is accumulated, and what kind of value is used. The second argument, init, is the initial value for the accumulator.

Here’s how it works: The result of foldr is generated by acting with f on the head of the list and whatever has been accumulated by processing the tail of the list. The algorithm recurses until the tail is empty, in which case it returns the initial value. At runtime this type of algorithm would make N recursive calls before starting to pop the stack and accumulate the results.

For instance, foldr may be used to sum the elements of a list (so_far is the accumulator, which is initialized to zero):

add_it elem so_far = elem + so_far
sum_it lst = foldr add_it 0 lst

The accumulator function is add_it. If, instead, I wanted to calculate the product of all elements, I’d use a function mult_it and the starting value of one. You get the idea.

Here’s the same algorithm in C++ TMP:

template<template<class, int> class, int, class...> struct
fold_right;

template<template<class, int> class f, int init> struct
fold_right<f, init> {
    static const int value = init;
};

template<template<class, int> class f, int init, class head, class...tail> struct
fold_right<f, init, head, tail...> {
    static const int value = f<head, fold_right<f, init, tail...>::value>::value;
};

Once you understand the Haskell version, this complex code suddenly becomes transparent (if it doesn’t, try squinting ).

Lists of Numbers

Let’s now switch to integers for a moment. Haskell defines a function sum that adds all elements of a list:

sum [] = 0
sum (head:tail) = head + (sum tail)

We can do the same in C++ TMP (in five times as many lines of code):

template<int...> struct
sum;

template<> struct
sum<> {
    static const int value = 0;
};

template<int i, int... tail> struct
sum<i, tail...> {
    static const int value = i + sum<tail...>::value;
};

List Comprehension

Haskell has one more trick up its sleeve for operating on lists without explicit recursion. It’s called list comprehension. It’s a way of defining new lists based on existing lists. The nomenclature and notation are borrowed from Set Theory, where you often encounter definitions such as: S is a set of elements, where… Let’s look at a simple Haskell example:

[x * x | x <- [3, 4, 5]]

This is a set (list) of elements x * x, where x is from the list [3, 4, 5].

Remember our recursive definition of count? Using list comprehension it’s reduced to a one-liner:

count lst = sum [1 | x <- lst]

Here, we create a list of ones, one for each element of the list. Our result is the sum of those ones. To make this definition more amenable to translation into C++, let’s define an auxiliary function one that, for any argument x, returns 1.

one x = 1

Here’s the modified definition of count:

count lst = sum [one x | x <- lst]

Now we are ready to convert this code to C++ TMP:

template<class T> struct
one {
    static const int value = 1;
};

template<class... lst> struct
count {
    static const int value = sum<one<lst>::value...>::value;
};

Here our list is stored in a template parameter pack, lst. If we wanted to expand this pack, we’d use the notation lst…, but that’s not what’s happening here. The ellipsis appears after the pattern containing the pack:

one<lst>::value...

Compare this with the equivalent Haskell:

[one x | x <- lst]

In C++, when the ellipsis follows a pattern that contains a pack, it’s not the pack that’s expanded, but the whole pattern is repeated for each element of the pack. Here, if our list were <int, char, void*>, the pattern would be expanded to:

<one<int>::value, one<char>::value, one<void*>::value>

The subsequent call to sum would be made with those arguments.

Notice that a different positioning of the ellipsis would result in a completely different expansion. This pattern:

one<lst...>::value

would result in the call to one with the list of types, which would be an error.

Here’s another example of pattern expansion: a function that counts the number of pointers in a list of types:

template<class... lst> struct
countPtrs {
    static const int value = sum<isPtr<lst>::value ...>::value;
};

In this case the pattern is:

isPtr<lst>::value ...

and it expands into a list of Booleans. (I’m taking advantage of the fact that false is zero and true is one, when converted to integers.)

You may find a more complex practical example in the Gregor, Järvi, and Powell paper (see bibliography).

Continuations

List comprehension can be used to define some very useful higher-order functions. One of such functions is map, which takes a list and applies a unary function to each element, resulting in a new list. You might be familiar with the runtime implementation of this algorithm in C++ STL under the name of transform. This is what map looks like in Haskell:

map f lst = [f x | x <- lst]

Here, f is the unary function and lst is the input list. You have to admire the terseness and elegance of this notation.

The first impulse would be to translate it into C++ TMP as:

template<template<class> class f, class... lst> struct
map {
    typedef f<lst>... type;
};

This is surprisingly terse too. The problem is that it doesn’t compile. As far as I know there is no way for a template to “return” a variable list of elements. In my opinion, this is a major language design flaw, but that’s just me.

There are several workarounds, none of them too exciting. One is to define a separate entity called a typelist along the lines of:

template struct
typelist<hd, tl...> {
    typedef hd head;
    typedef typelist<tl...> tail;
};

(As a matter of fact I have implemented typelists and related algorithms both in C++ and D.)

Another approach is to use continuations. Template parameter packs cannot be returned, but they can be passed to variadic templates (after expansion). So how about defining an algorithm like map to take one additional function that would consume the list that is the result of mapping? Such a function is often called a continuation, since it continues the calculation where normally one would return the result. First, let’s do it in Haskell:

map_cont cont f lst = cont [f x | x <- lst]

The function map_cont is just like map except that it takes a continuation, cont, and applies it to the result of mapping. We can test it by defining yet another implementation of count:

count_cont lst = map_cont sum one lst

The continuation here is the function sum that will be applied to the list produced by acting with function one on the list lst. Since this is quite a handful, let me rewrite it in a more familiar notation of runtime C++:

int map_cont(int (*cont)(list), int (*f)(int), list lst) {
    list tmp;
    for (auto it = lst.begin(); it != lst.end(); ++it)
        tmp.push_front(f(*it));
    return cont(tmp);
}

Now for the same thing in compile-time C++:

template<template<class...> class cont,
         template<class> class f,
         class... lst> struct
map_cont {
    static const int value =
        cont<typename f<lst>::type ...>::value;
};

It’s a one-to-one mapping of Haskell code–and it has very little in common with the iterative runtime C++ implementation. Also notice how loose the typing is in the TMP version as compared with the runtime version. The continuation is declared as a variadic template taking types, function f is declared as taking a type, and the list is a variadic list of types. Nothing is said about return types, except for the constraints that f returns a type (because cont consumes a list of types) and cont returns an int. Actually, this last constraint can be relaxed if we turn integers into types–a standard trick (hack?) in TMP:

template<int n> struct
Int {
    static const int value = n;
};

Loose typing–or “kinding,” as it is called for types of types–is an essential part of compile-time programming. In fact the popularity of the above trick shows that C++ kinding might be already too strong.

The D Digression

I’m grateful to Andrei Alexandrescu for reviewing this post. Since he objected to the sentence, “I’m disappointed that the D programming language followed the same path as C++ rather than lead the way,” I feel compelled to support my view with at least one example. Consider various implementations of all.

In Haskell, beside the terse and elegant version I showed before:

all pred [] = True
all pred (head:tail) = (pred head) && (all pred tail)

there is also a slightly more verbose one:

all pred list =
    if null list then True
    else pred (head list) && all pred (tail list)

which translates better into D. The D version (taken from its standard library, Phobos) is not as short as Haskell’s, but follows the same functional paradigm:

template allSatisfy(alias F, T...) {
    static if (T.length == 1)
    {
        alias F!(T[0]) allSatisfy;
    }
    else
    {
        enum bool allSatisfy = F!(T[0]) && allSatisfy!(F, T[1 .. $]);
    }
}

It definitely beats C++, there’s no doubt about it. There are some oddities about it though. Notice that the type tuple, T… gets the standard list treatment, but the split into the head and tail follows the array/slice notation. The head is T[0] and the tail is an array slice, T[1..$]. Instead of using value for the return value, D uses the “eponymous hack,” as I call it. The template “returns” the value using its own name. It’s a hack because it breaks down if you want to define the equivalent of “local variable” inside a template. For instance, the following code doesn’t compile:

template allSatisfy(alias F, T...) {
    static if (T.length == 1)
    {
        alias F!(T[0]) allSatisfy;
    }
    else
    {
        private enum bool tailResult = allSatisfy!(F, T[1..$]);
        enum bool allSatisfy = F!(T[0]) && tailResult;
    }
}

This breaks one of the fundamental property of any language: decomposability. You want to be able to decompose your calculation into smaller chunks and then combine them together. Of course, you may still use decomposition if you don’t use the eponymous hack and just call your return value value. But that means modifying all the calling sites.

By the way, this is how decomposition works in Haskell:

all2 pred [] = True;
all2 pred (head:tail) = (pred head) && tailResult
    where tailResult = all2 pred tail

Anyway, the important point is that there is no reason to force functional programming paradigm at compile-time. The following hypothetical syntax would be much easier for programmers who are used to imperative programming:

template allSatisfy(alias Pred, T...) {
    foreach(t; T)
        if (!Pred!(t))
            return false;
    return true;
}

In fact it’s much closer to the parameterized runtime function proposed by Andrei:

bool all(alias pred, Range)(Range r) {
    foreach (e; r)
        if (!pred(e))
            return false;
    return true;
}

This is why I’m disappointed that the D programming language followed the same path as C++ rather than lead the way.

Conclusions

I have argued that some familiarity with Haskell may be really helpful in understanding and designing templates in C++. You might ask why C++ chose such horrible syntax to do compile-time functional programming. Well, it didn’t. The ability to do compile-time calculations in C++ was discovered rather than built into the language. It was a very fruitful discovery, as the subsequent developments, especially the implementation of the Boost MPL, have shown. However, once the functional paradigm and its weird syntax took root in C++ TMP, it stayed there forever. I’m aware of only one effort to rationalize C++ TMP by Daveed Vandevoorde in Reflective Metaprogramming in C++.

I have tested all code in this blog using the Hugs interpreter for Haskell and the GNU C++ compiler v. 4.4.1 with the special switch -std=c++0x. The names I used in the blog might conflict with the standard definitions. For instance, Hugs defines its own map and foldr.

If you want to learn more about template metaprogramming, I recommend two books:

Andrei Alexandrescu, Modern C++ Design
David Abrahams and Aleksey Gurtvoy, C++ Template Metaprogramming

The reference I used for variadic templates was the paper by Douglas Gregor, Jaakko Järvi, and Gary Powell

vincenzoampolo7

2009-10-20T14:47:31+00:00

Today i received a very good mail which stated that what we are doing in developing gdc is appreciated.

The mail is from Tomasz Stachewicz, the developer of RuDy project to enable and ease writing Ruby native extensions in D programming language.

After congratulating for the work we are doing, he stated something new: “Is there a book wishlist or donation account I could use to word my appreciation in a more material way?“

If i’m not wrong (sorry i’m not a native English speaker), he is asking for an account for a donation. I think that maybe he is not the only one which wants to give some founds to the gdc project…

Well… If everybody agrees (well for now me, Michael and David Friedman, the ones which did work for gdc) i can get this moneys with paypal (or with one of the pay-for-feature websites). Moneys will be reserved to develop gdc in a issue/task basis (for porting gdc to lastest gcc you take X, for updating to dmd version Y you take Z and so on)

Of course i don’t think that gdc is so famous to make a lot of people contribute to it, but i think that we should decide about this issue to allow

people to support the gdc project.

This message is on the news.digitalmars.com NG too.

KLEE, automatically generating tests that achieve high coverage

2009-10-20T11:20:51+00:00

This is the abstract of the paper describing KLEE, a new LLVM sub-project announced with the upcoming 2.6 release:

We present a new symbolic execution tool, KLEE, capable of automatically generating tests that achieve high coverage on a diverse set of complex and environmentally-intensive programs. We used KLEE to thoroughly check all 89 stand-alone programs in the GNU COREUTILS utility suite, which form the core user-level environment installed on millions of Unix systems, and arguably are the single most heavily tested set of open-source programs in existence. KLEE-generated tests achieve high line coverage — on average over 90% per tool (median: over 94%) — and significantly beat the coverage of the developers' own hand-written test suites. When we did the same for 75 equivalent tools in the BUSYBOX embedded system suite, results were even better, including 100% coverage on 31 of them. We also used KLEE as a bug finding tool, applying it to 452 applications (over 430K total lines of code), where it found 56 serious bugs, including three in COREUTILS that had been missed for over 15 years. Finally, we used KLEE to cross-check purportedly identical BUSYBOX and COREUTILS utilities, finding functional correctness errors and a myriad of inconsistencies.

I have to try this...

Slow allocation of D objects

2009-10-19T10:10:43+00:00

Allocating objects in D language, usign the good and efficient LDC compiler, may seem slower than doing the same thing in C++, but the situation is a little more complex, so few examples can show what's going on.

This is a syntetic C++ benchmark, it allocates an array of n pointers to Foo object, and then allocates the instances, that contain ten 32 bit integers:

// C++ version 1, 0.46 s
#include "stdio.h"
#include "stdlib.h"

using namespace std;

class Foo {
    public:
        int y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;
        Foo(int, int, int, int, int, int, int, int, int, int);
};

Foo::Foo(int x1, int x2, int x3, int x4, int x5, int x6, int x7, int x8, int x9, int x10):
  y1(x1), y2(x2), y3(x3), y4(x4), y5(x5), y6(x6), y7(x7), y8(x8), y9(x9), y10(x10) {}

int main(int argc, char *argv[]) {
    int n = (argc == 2) ? atoi(argv[1]) : 5;
    Foo* foos[n];

    for (int i = 0; i < n; i++)
        foos[i] = new Foo(i+1, i+2, i+3, i+4, i+5, i+6, i+7, i+8, i+9, i+10);

    printf("%d %d %d\n", foos[n-1]->y1, foos[n-1]->y2, foos[n-1]->y10);
    return 0;
}

This is an almost equivalent D code. I use printf and those imports are so hairy because this code is designed to work with both Phobos or Tango standard libraries, and with D1 and D2 languages:

// D version 1, 0.89 s
version (Tango) {
    import tango.stdc.stdio: printf;
    import Integer = tango.text.convert.Integer;
    alias Integer.parse toInt;
} else {
    import std.c.stdio: printf;
    version (D_Version2) {
        import std.conv: to;
        alias to!(int, char[]) toInt;
    } else
        import std.conv: toInt;
}

class Foo {
    int y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;

    this(int x1, int x2, int x3, int x4, int x5, int x6, int x7, int x8, int x9, int x10) {
        y1 = x1;
        y2 = x2;
        y3 = x3;
        y4 = x4;
        y5 = x5;
        y6 = x6;
        y7 = x7;
        y8 = x8;
        y9 = x9;
        y10 = x10;
    }
}

void main(char[][] args) {
    int n = (args.length == 2) ? toInt(args[1]) : 5;
    Foo[] foos = new Foo[n];

    for (int i = 0; i < n; i++)
        foos[i] = new Foo(i+1, i+2, i+3, i+4, i+5, i+6, i+7, i+8, i+9, i+10);

    printf("%d %d %d\n", foos[$-1].y1, foos[$-1].y2, foos[$-1].y10);
}

Replacing in the C++ the class like this doesn't change the running time of the program:

// piece of the C++ version 2, 0.47 s
class Foo {
    public:
        int y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;
        Foo(int, int, int, int, int, int, int, int, int, int);
};

Foo::Foo(int x1, int x2, int x3, int x4, int x5, int x6, int x7, int x8, int x9, int x10) {
    y1 = x1;
    y2 = x2;
    y3 = x3;
    y4 = x4;
    y5 = x5;
    y6 = x6;
    y7 = x7;
    y8 = x8;
    y9 = x9;
    y10 = x10;
}

The running times on a Ubuntu running on VirtualBox, running on Vista 32 bit, running on a Celeron CPU, using LDC compiler based on DMD v1.045 and llvm 2.6 (Thu Sep 10 23:50:27 2009):

Timings, n = 1_000_000, best of 3, seconds:
  C++ 1: 0.46  |#########                |
  C++ 2: 0.47  |#########                |
  D 1:   0.89  |##################       |
  D 2:   0.82  |################         |
  D 3:   0.87  |#################        |
  D 4:   0.46  |#########                |
  D 5:   0.46  |#########                |
  D 6:   1.22  |#########################|
  D 6b:  0.86  |#################        |
  D 7:   0.63  |############             |
  D 8:   0.71  |##############           |

I have compiled the C++ code with gcc V.4.3.3 with:
g++ -Wall -O3 -s -fomit-frame-pointer -msse3 -march=native objbench1_cpp.cpp -o objbench1_cpp
And the D code with:
ldc -O5 -release -inline objbench1_d.d

As you can see the D version is about twice slower than the C++ code, despite usually the LDC compiler is almost as efficient as GCC (LLVM is not able to perform some optimizations yet, like auto-vectorization, but things are already good and they will improve).

D classes are different from C++ ones, D objects always contain a pointer to the virtual table (even if no virtual methods are present, it's used by the reflection and GC too) and a monitor, so on 32 bit systems they need 8 extra bytes. So we may try to remove such memory (and bookeeping) overhead using a struct (this version can be changed a little, so it works with Phobos of D2 too):

// D version 2, 0.82 s
version (Tango) {
    import tango.stdc.stdio: printf;
    import Integer = tango.text.convert.Integer;
    alias Integer.parse toInt;
} else {
    import std.c.stdio: printf;
    import std.conv: toInt;
}

struct Foo {
    int y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;
}

void main(char[][] args) {
    int n = (args.length == 2) ? toInt(args[1]) : 5;
    
    Foo*[] foos = new Foo*[n];

    for (int i = 0; i < n; i++) {
        foos[i] = new Foo;
        *foos[i] = Foo(i+1, i+2, i+3, i+4, i+5, i+6, i+7, i+8, i+9, i+10);  
    }
    
    printf("%d %d %d\n", foos[$-1].y1, foos[$-1].y2, foos[$-1].y10);
}

But you can see the performance improves only a little, so the problem is elsewhere. I have had to use that two-line initialization because only in D2 language structs are allowed to have an explicit constructor.

We can try allocating the pointer array on the stack but the performance gets a little worse:

// D version 3, 0.87 s
version (Tango) {
    import tango.stdc.stdio: printf;
    import Integer = tango.text.convert.Integer;
    alias Integer.parse toInt;
    import tango.stdc.stdlib: alloca;
} else {
    import std.c.stdio: printf;
    import std.conv: toInt;
    import std.c.stdlib: alloca;
}

struct Foo {
    int y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;
}

void main(char[][] args) {
    int n = (args.length == 2) ? toInt(args[1]) : 5;
    Foo** ptr = cast(Foo**)alloca((Foo*).sizeof * n);
    Foo*[] foos = ptr[0 .. n];
    
    for (int i = 0; i < n; i++) {
        foos[i] = new Foo;
        *foos[i] = Foo(i+1, i+2, i+3, i+4, i+5, i+6, i+7, i+8, i+9, i+10);  
    }

    printf("%d %d %d\n", foos[$-1].y1, foos[$-1].y2, foos[$-1].y10);
}

A next step is to allocate the structs from the C heap, this time the performance is about the same as the C++ code, showing that the cause of the slowdown is the (not efficient yet) D Garbage Collector:

// D version 4, 0.46 s
version (Tango) {
    import tango.stdc.stdio: printf;
    import Integer = tango.text.convert.Integer;
    alias Integer.parse toInt;
    import tango.stdc.stdlib: alloca, malloc;
} else {
    import std.c.stdio: printf;
    import std.conv: toInt;
    import std.c.stdlib: alloca, malloc;
}

struct Foo {
    int y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;
}

void main(char[][] args) {
    int n = (args.length == 2) ? toInt(args[1]) : 5;
    Foo** ptr = cast(Foo**)alloca((Foo*).sizeof * n);
    Foo*[] foos = ptr[0 .. n];
    
    for (int i = 0; i < n; i++) {
        foos[i] = cast(Foo*)malloc(Foo.sizeof);
        *foos[i] = Foo(i+1, i+2, i+3, i+4, i+5, i+6, i+7, i+8, i+9, i+10);  
    }

    printf("%d %d %d\n", foos[$-1].y1, foos[$-1].y2, foos[$-1].y10);
}

So we can restore the original allocation of the dynamic array of pointers, the performance improves a tiny bit (less than 0.01 s):

// D version 5, 0.46 s
version (Tango) {
    import tango.stdc.stdio: printf;
    import Integer = tango.text.convert.Integer;
    alias Integer.parse toInt;
    import tango.stdc.stdlib: malloc;
} else {
    import std.c.stdio: printf;
    import std.conv: toInt;
    import std.c.stdlib: malloc;
}

struct Foo {
    int y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;
}

void main(char[][] args) {
    int n = (args.length == 2) ? toInt(args[1]) : 5;
    Foo*[] foos = new Foo*[n];
    
    for (int i = 0; i < n; i++) {
        foos[i] = cast(Foo*)malloc(Foo.sizeof);
        *foos[i] = Foo(i+1, i+2, i+3, i+4, i+5, i+6, i+7, i+8, i+9, i+10);  
    }

    printf("%d %d %d\n", foos[$-1].y1, foos[$-1].y2, foos[$-1].y10);
}

We may think that the problem is in the double initalization of the structs, it seems that's not the case, as the following code is the slowest, here I use uninitialized memory from the GC heap:

// D version 6, 1.22 s
version (Tango) {
    import tango.stdc.stdio: printf;
    import Integer = tango.text.convert.Integer;
    alias Integer.parse toInt;
    import tango.core.Memory: GC;
    alias GC.malloc gcmalloc;
} else {
    import std.c.stdio: printf;
    import std.conv: toInt;
    import std.gc: gcmalloc = malloc;
}

struct Foo {
    int y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;
}

void main(char[][] args) {
    int n = (args.length == 2) ? toInt(args[1]) : 5;
    Foo*[] foos = new Foo*[n];
    
    for (int i = 0; i < n; i++) {
        foos[i] = cast(Foo*)gcmalloc(Foo.sizeof);
        *foos[i] = Foo(i+1, i+2, i+3, i+4, i+5, i+6, i+7, i+8, i+9, i+10);  
    }

    printf("%d %d %d\n", foos[$-1].y1, foos[$-1].y2, foos[$-1].y10);
}

I don't fully know why the performance of the version 6 is so low (if you have ideas please tell me), part of that lower performance comes from the GC that scans the memory of those structs. You can see it in the version 6b, where I have disabled the scanning of those memory blocks, there's indeed a significant performance improvement:

// D version 6b, 0.86 s
version (Tango) {
    import tango.stdc.stdio: printf;
    import Integer = tango.text.convert.Integer;
    alias Integer.parse toInt;
    import tango.core.Memory: GC;
    alias GC.malloc gcmalloc;
    void hasNoPointers(void* p) {
        GC.setAttr(p, GC.BlkAttr.NO_SCAN);
    }
} else {
    import std.c.stdio: printf;
    import std.conv: toInt;
    import std.gc: gcmalloc = malloc, hasNoPointers;
}

struct Foo {
    int y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;
}

void main(char[][] args) {
    int n = (args.length == 2) ? toInt(args[1]) : 5;
    Foo*[] foos = new Foo*[n];

    for (int i = 0; i < n; i++) {
        foos[i] = cast(Foo*)gcmalloc(Foo.sizeof);
        hasNoPointers(foos[i]);
        *foos[i] = Foo(i+1, i+2, i+3, i+4, i+5, i+6, i+7, i+8, i+9, i+10);
    }

    printf("%d %d %d\n", foos[$-1].y1, foos[$-1].y2, foos[$-1].y10);
}

But even if the GC doesn't scan those memory blocks, it performs several operations anyway, so when you allocate many pieces of memory and you need performance, you may want to disable the GC (and enable it just after the allocation, here I have not added the enable(), but in your code you are supposed to put it), the performance is intermediate:

// D version 7, 0.63 s
version (Tango) {
    import tango.stdc.stdio: printf;
    import Integer = tango.text.convert.Integer;
    alias Integer.parse toInt;
    import tango.core.Memory: GC;
    alias GC.disable disable;
} else {
    import std.c.stdio: printf;
    import std.conv: toInt;
    import std.gc: disable;
}

struct Foo {
    int y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;
}

void main(char[][] args) {
    int n = (args.length == 2) ? toInt(args[1]) : 5;
    disable();
    
    Foo*[] foos = new Foo*[n];

    for (int i = 0; i < n; i++) {
        foos[i] = new Foo;
        *foos[i] = Foo(i+1, i+2, i+3, i+4, i+5, i+6, i+7, i+8, i+9, i+10);  
    }
    
    printf("%d %d %d\n", foos[$-1].y1, foos[$-1].y2, foos[$-1].y10);
}

We can also go back ot the object-based version, with a further little reduction of performance:

// D version 8, 0.71 s
version (Tango) {
    import tango.stdc.stdio: printf;
    import Integer = tango.text.convert.Integer;
    alias Integer.parse toInt;
    import tango.core.Memory: GC;
    alias GC.disable disable;
} else {
    import std.c.stdio: printf;
    import std.conv: toInt;
    import std.gc: disable;
}

class Foo {
    int y1, y2, y3, y4, y5, y6, y7, y8, y9, y10;

    this(int x1, int x2, int x3, int x4, int x5, int x6, int x7, int x8, int x9, int x10) {
        y1 = x1;
        y2 = x2;
        y3 = x3;
        y4 = x4;
        y5 = x5;
        y6 = x6;
        y7 = x7;
        y8 = x8;
        y9 = x9;
        y10 = x10;
    }
}

void main(char[][] args) {
    int n = (args.length == 2) ? toInt(args[1]) : 5;
    disable();
    Foo[] foos = new Foo[n];

    for (int i = 0; i < n; i++)
        foos[i] = new Foo(i+1, i+2, i+3, i+4, i+5, i+6, i+7, i+8, i+9, i+10);

    printf("%d %d %d\n", foos[$-1].y1, foos[$-1].y2, foos[$-1].y10);
}

Having a garbage collector is handy, and sometimes safer too, but it has a price too (in the size of the binary too). D allows you to not use the GC when you need C++-like performance, but then you have to remember to manage and deallocate memory manually as in C, or you need to implement/use other forms or memory management as in C++ (and D allows the scope(exit) idiom too to deallocate memory when a scope ends). If the D language will get widespread, its GC will improve, restoring part of the lost performance.

pybugz, a python and command line interface to Bugzilla

2009-10-16T11:14:48+00:00

Tired of the clumsy Bugzilla web interface? Meet pybugz, a command line interface for Bugzilla.

An example workflow from the README file:

$ bugz search "version bump" --assigned liquidx@gentoo.org

 * Using http://bugs.gentoo.org/ ..
 * Searching for "version bump" ordered by "number"
 101968 liquidx net-im/msnlib version bump
 125468 liquidx version bump for dev-libs/g-wrap-1.9.6
 130608 liquidx app-dicts/stardict version bump: 2.4.7

$ bugz get 101968

 * Using http://bugs.gentoo.org/ ..
 * Getting bug 130608 ..
Title : app-dicts/stardict version bump: 2.4.7
Assignee : liquidx@gentoo.org
Reported : 2006-04-20 07:36 PST
Updated : 2006-05-29 23:18:12 PST
Status : NEW
URL : http://stardict.sf.net
Severity : enhancement
Reporter : dushistov@mail.ru
Priority : P2
Comments : 3
Attachments : 1

[ATTACH] [87844] [stardict 2.4.7 ebuild]

[Comment #1] dushistov@----.ru : 2006-04-20 07:36 PST
...

$ bugz attachment 87844

 * Using http://bugs.gentoo.org/ ..
 * Getting attachment 87844
 * Saving attachment: "stardict-2.4.7.ebuild"

$ bugz modify 130608 --fixed -c "Thanks for the ebuild. Committed to
portage"

D and open development model

2009-10-15T17:09:23+00:00

Warning

Long post ahead =)

I'm very glad that yesterday DMD had the first releases (DMD 1.050 and DMD 2.035) with a decent revision history. It took some time to Walter Bright to understand how the open source development model works, and I think he still has a lot more to learn, but I have some hope now about the future of D.

Not much time ago, neither Phobos, DMD nor Druntime had revision control. Druntime didn't even exist, making D 1 split in two because of the Phobos vs Tango dichotomy. DMD back-end sources were not available either, and Walter Bright was the only person writing stuff (sometimes not because people didn't want to, but because he was too anal retentive to let them ;). It was almost impossible to make patches back then (your only chance was hacking GDC, which is pretty hard).

Now I can say that DMD, Phobos and Druntime have full source availability (DMD back-end is not free/libre though), almost all the parts of DMD have the sources published under a source control system. The core team has been expanded and even when Walter Bright is still in charge, at least 3 developers are now very committed to D: Andrei Alexandrescu (in charge of Phobos), Sean Kelly (in charge of Druntime) and Don Clugston (squashing DMD bugs at full speed, specially in the back-end). Other people are contributing patches in a regular basis. There were about 72 patches submitted to bugzilla before DMD was distributed with full source (72 patches in ~10 years) , since then, 206 patches were submitted (that is, 206 patches in less than 8 months).

But even with this great improvement, there is much left to do yet (and I'm talking only about the development model). This is a small list of what I think it's necessary to keep moving to a more open development model:

Releases

The release process should be improved. Me and other people are suggesting release candidates. This will allow people to test the new releases to find any regressions. As things are now, releases are not much different from a nightly build, except that you don't have one available every night :). People get very frustrated when downloading a new version of the compiler and things stop working, and this holds back front-end updates in other compilers, like LDC (which is frozen at 1.045 because of the regressions found in the next 5 versions).

I think Walter Bright is suffering from premature releasing too. Releases comes from nowhere, when nobody expects them. Nobody knows when a new compiler version will be released. I think that hurts the language reliability.

I think the releases should be more predictable. A release schedule (even when not very accurate, like in many other open source projects) gives you some peace of mind.

Peer review

Even when commits are fairly small now in DMD, I think they are far from ideal. Is very common to see unrelated changes in a commit (the classic example is the compiler version number being bumped in an bug fix). See revision 214 for example: the compiler version is bumped and there are some changes to the new JSON output, totally unrelated to bug 3401, which is supposed to fix; or revision 213, which announces the release of DMD 1.050 and DMD 2.035, introducing a bunch of changes that who knows what are supposed to do (well, they look like the introduction of the new type T[new], but that's not even documented in the release changelog :S). This is bad for several reasons:

Reviewing a patch with unrelated changes is hard.
If you want to fold in a individual patch (let's say, LDC guys want to fold a bug fix), you have a lot of junk to take care of.
If you want to do some sort of bisection to find a regression, you still have to figure out which is the group of related changes that introduced the regression.

I'm sure there are more...

Commit messages lacks a good description of the problem and the solution. Most commit messages in DMD are "bugzilla N". You have to go to the bugzilla bug to know what's all about. For example, Don's patches usually comes with very good and juicy information about the bug causes and why the patch fixes it (see an example). That is a good commit message. You can learn a lot about the code by reading well commented patches, which can lead to more contributions in the future.

Commits in Phobos can be even worse. The commits with a message "bugzilla N" are usually the good ones. There are 56 commits that have "minor" as the commit message. Yes, just "minor". That's pretty useless, it's very hard to review a patch when you don't know what is supposed to do. Commit messages are the base of peer reviewing, and peer reviewing is the base for high quality code.

So I think that D developers should focus a lot more in commit message. I know it can sound silly at first, but I think I would be a huge gain with too little effort.

Besides this, commits should be mailed to a newsgroup or mailing list to easy peer review. Now it's a little hard to make comments about a commit, you have to post the comment in the D newsgroup or make the comment by personal e-mail to the author. The former is not that bad but it's not easy to include context and people reading the comment will probably have to open a browser and search for the commented commit. This clearly make peer reviewing more difficult when the ideal would be to encourage it. The private mail is simply wrong because other people can't see the comments.

Source control and versioning

This one is tightly related to the previous two topics. Using a good DVCS can make help a lot too. Subversion has a lot of problems with branching, which makes releases harder too (as having a branch for each release is very painful). Is bad for commit messages too, because there is no real difference in branches and directories, so know every commit is duplicated (both changes for DMD 1 and 2 are included). It's not easy to cherry-pick single commits either, and you can't fix you commits if you messed up, which leads to a lot of commits of the style "Woops! Fix the typo in the previous commit.".

I'm sure both the release process and peer reviewing can be greatly improved by using a better DVCS.

Easy branching can also lead to a more fast evolving and reliable language. Yes, both are possible with branches. Now there are 2 branches: stable (D1) and experimental (D2). D1 is almost frozen and people is seeing less and less interest on it as it goes old, and D2 is too unstable for real use. Having some intermediate can be really helpful. For example, it has been announced that the concurrency model proposed by Bartosz Milewski will be not part of D2 because there is not enough time to implement it, since D2 should be release fairly soon as Andrei Alexandrescu is writing a book that has a deadline and the language has to be finalized by the time the book is published.

So concurrency (as AST macros) are delayed to D3. D2 is more than 2 years old, so one should expect that D3 will be not available in less than 5 years from now (assuming D2 would take 2.5 years and D3 would take the same). This might be too much time.

I think the language should adopt a model closer to Python, where a minor language version (with backward compatible improvements) is release every 1 ~ 1.5 years. Last mayor version took about 8 years, but considering how many new features Python included in minor versions that's not a big issue. The last mayor version was mostly a clean up of old stuff/nasty stuff, not huge changes to the language.

Licensing

I think the DMD back-end should have a better license. Personal use is simply not enough for a reference implementation of a language that wants to hit mainstream. If you plan to do business with it, not being able to patch the compiler if you need to and distribute it is not an option.

This is for the sake of DMD only, because other compilers (like LDC and GDC) are fully free/libre.

Conclusion

Some of the things I mention are really hard to change, as they modify how people work and imply learning new tools. But other are fairly easy, and can be done progressively (like providing release candidates and improving commits and commit messages).

I hope Walter Bright & Co. keep walking the openness road =)

DMD 1.050 and 2.035

2009-10-15T14:33:11+00:00

Walter has pushed new releases of DMD out the door, 1.050 and 2.035. The purpose was to fix regressions blocking Qtd and Tango. Additionally, both releases now include an option to output some symbol data in JSON format in an effort to assist IDE developers. This feature is likely to evolve as it is used [...]

LLVM developer meeting videos available

2009-10-15T13:35:57+00:00

Chris Lattner announced that the videos for the last LLVM developer meeting are now available. They are usually very interesting, so I'd recommend to watch them if you have some time.

Update

Big WTF and many anti-cool-points for Apple:

On Oct 15, 2009, at 8:29 AM, Anton Korobeynikov wrote:
[...]
> I'm a bit curious: is there any reason why are other slides / videos
> not available (it seems that the ones missing are from Apple folks)?

Unfortunately, we found out at the last minute that Apple has a rule
which prevents its engineers from giving video taped talks or
distributing slides.  We will hold onto the video and slide assets in
case this rule changes in the future.

-Chris

Fragment from a response to the announcement.

Mutt patched with NNTP support for Debian (and friends)

2009-10-14T01:01:05+00:00

Did you ever wanted Mutt with NNTP support packed up for your Debian (or Debian-ish) box, but you are too lazy to do it yourself? Did you even tried to report a bug so the patch can be applied to the official Debian package but the maintainers told you they wont do it?

If so, this is a great day for you, because I did it and I'm giving it away with no charge in this one time only opportunity!!! =P

Seriously, I can understand why the maintainers don't want to support it officially, it a big patch and can be some work to fold it in. So I did it myself, and it turned out it's wasn't that bad.

I adjusted the patch maintained by Vsevolod Volkov to work on top of all the other patches included in the mutt-patched Debian package (the only conflicting patch is the sidebar patch and some files that doesn't exist because the patch should be applied after autotools files are generated and Debian apply the patches before that) and built the package using the latest Debian source (1.5.20-4).

You can find the source package and the binary packages for Debian unstable i386 here. You can find there the modified NNTP patch too.

If you have Ubuntu or other Debian based distribution, you can compile the binary package by downloading the files mutt_1.5.20-4luca1.diff.gz, mutt_1.5.20-4luca1.dsc and mutt_1.5.20.orig.tar.gz, then run:

$ sudo apt-get build-dep mutt
$ dpkg-source -x mutt_1.5.20-4luca1.dsc
$ cd mutt-1.5.20
$ dpkg-buildpackage -rfakeroot
$ cd ..
$ sudo dpkg -i mutt_1.5.20-4luca1_i386.deb \
        mutt-patched_1.5.20-4luca1_i386.deb

Now you can enjoy reading the D newsgroups and your favourite mailing lists via Gmane with Mutt without leaving the beauty of your packaging system. No need to thank me, I'm glad to be helpful ;)

Walter Bright: Geek of the Week

2009-10-12T14:16:55+00:00

Walter is simple-talk.com’s Geek of the Week. In the interview, he talks about some of the rationale for D, some of the problems it solves, and why people should use it, with a few opinions of C and C++ tossed in for good measure. There’s a long list of previous Geeks of the Week, some whose [...]

Rational Lib and Another Demo

2009-10-12T13:57:20+00:00

Two items that may be of interest to some of you. First, dsimcha has released a small library for working with rational numbers. It’s D2 only and can be seen in the Scrapple trunk. From the announcement: It’s templated to work on any integer type that supports the relevant operators. Usually this would be used with [...]

DMD 1.049 and 2.034

2009-10-12T13:45:40+00:00

Two new DMD versions have been rolled out, 1.049 and 2.034. Both feature a number of bug fixes. According to Don Clugston, A small milestone — This release fixes the last remaining compiler segfaults and internal compiler errors from DStress. This will probably be the last “stability release” — there aren’t many ICE bugs left [...]

Link Time Optimization

2009-10-10T15:34:21+00:00

The upcoming LLVM 2.6 will include a plug-in for Gold to implement Link Time Optimization (LTO) using LLVM's LibLTO. There is a similar project for GCC, merged into the main trunk about a week ago. It will be available in GCC 4.5.

This is all fairly new, and will be not enabled by default in LLVM (I don't know what about GCC), but it will add a lot of new optimization oportunities in the future.

So people using LDC and GDC will probably be able to enjoy LTO in a near future =)

Stats for the basic GC

2009-10-08T20:08:03+00:00

Here are some graphs made from my D GC benchmarks using the Tango (0.99.8) basic collector, similar to the naive ones but using histograms for allocations (time and space):

Some comments:

The Wasted space is the Uncommitted space (since the basic GC doesn't track the real size of the stored object).
The Stop-the-world time is the time all the threads are stopped, which is almost the same as the time spent scanning the heap.
The Collect time is the total time spent in a collection. The difference with the Stop-the-world time is almost the same as the time spent in the sweep phase, which is done after the threads have being resumed (except the thread that triggered the collection).

There are a few observations to do about the results:

The stop the world time varies a lot. There are tests where is almost unnoticeable (tree), tests where it's almost equals to the total collection time (rnd_data, rnd_data_2, split) and test where it's in the middle (big_arrays). I can't see a pattern though (like heap occupancy).
There are tests where it seems that collections are triggered for no reason; there is plenty of free space when it's triggered (tree and big_arrays). I haven't investigated this yet, so if you can see a reason, please let me know.

rae_gui_lib_first_demo

2009-10-07T17:29:34+00:00

I thought I’d keep a low profile until my new project was finished, but as it now seems that it is progressing quite slowly, I might as well make it public for others to see.

Rae is going to be a general purpose GUI library. It’s nowhere near finished, and it is not usable for anything but making nice little demos of it. (Well you could make something like a calculator with it. Or possibly a pictureviewer of some sort with some effort. So, it’s not entirely useless…)

The keywords go something like this: D programming language, OpenGL, X11/MIT licence, (GtkD, cairo, pango), Linux, OS X, Windows.

Here’s a link to the video:

Rae GUI first demo

And there’s also a project page at http://www.dsource.org/projects/rae

The source in the repository is up to date, but a bigger example like seen on the video is missing. I might add it there later, when I get the time. But feel free to try and compile it. Shouldn’t be too easy. Lot’s of nasty big dependencies, that I’d want to drop later. The code is a bit hacky, but pragmatic, so if you prefer projects with perfect code, look elsewhere. One of the main features is that it uses 0% CPU when doing nothing. Yes, that’s just how it’s supposed to be, but not any of the OpenGL GUIs that I’ve seen, do that. It’s full of small graphic glithces, unfinished widgets and buggy behaviour and sometimes even bad design. But I’m willing to change all that if anyone wants to start participating in this weird and wonderful project. Progress is slow, as always, but there’s a start. Feel free to donate me time, hardware or anything useful. (I’d put a smiley here, but I’m trying to quit using them.)

DMD 1.048 and 2.033

2009-10-06T12:51:20+00:00

Walter recently announced DMD 1.048 and 2.033. Both versions now sport contract inheritance, which has been missing for a long, long time. Also, both branches can now catch some null dereferences when compiling with the -O switch. So if you build exclusively in debug mode when testing, you may want to start building with -O [...]

GDC resurrection

2009-10-05T11:31:26+00:00

About a month ago, the GDC newsgroup started to get some activity when Michael P. and Vincenzo Ampolo started working on updating GCD. Yesterday they announced that they successfully merged the DMD frontend 1.038 and 2.015, and a new repository for GDC. They will be hanging on #d.gdc if you have any questions or want to help out.

So great news for the D ecosystem! Kudos for this two brave men! =)

DGC page is back

2009-10-02T13:17:58+00:00

I've migrated the wiki pages about DGC from Redmine to Sphinx.

Tree visits in D

2009-09-29T19:28:12+00:00

On the RosettaCode site there's this Programming Task:
http://rosettacode.org/wiki/Tree_traversal

Problem: Implement a binary tree where each node carries an integer, and implement preoder, inorder, postorder and level-order traversal. Use those traversals to output the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

The correct output should look like this:

preorder:    1 2 4 7 5 3 6 8 9
inorder:     7 4 2 5 1 8 6 9 3
postorder:   7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9

The following is my D implementation. I have used the D Version 2 language (to compile the code I am using DMD v2.032, with the Phobos std lib, but it uses only the printing of Phobos, so adapting the code to Tango is easy), but a very similar version can be adapted for D V1.

Disclaimer: The following isn't an example of common (or good) D code. It's very generic and it's a bit tricky. In practice you usually write simpler code, because you don't need such genericity, and to keep the code simpler to write and understand. Simpler code is also simpler to debug. You may need to write code so much generic only in library-like routines, that are usually limited in number and size. So there are surely ways to write simpler/shorter D code, but here I show this version because it can be useful to explain some features of the D language, and because it's more fun.

import std.stdio: write, writeln;

class Node(T) {
T data;
Node left, right;
this(T data, Node left=null, Node right=null) {
this.data = data;
this.left = left;
this.right = right;
}
}

// static templated opCall can't be used in Node
auto node(T)(T data, Node!T left=null, Node!T right=null) {
return new Node!T(data, left, right);
}

void show(T)(T x) {
write(x, " ");
}

enum Visit { pre, inv, post }

// visitor can be any kind of callable or it uses a default visitor.
// TNode can be any kind of Node, with data, left and right fields,
// so this is more generic than a member function of Node.
void backtrackingOrder(Visit v, TNode, TyF=void*)(TNode node, TyF visitor=null) {
static if (is(TyF == void*)) auto truevisitor = &show!(typeof(node.data));
else auto truevisitor = visitor;
if (node !is null) {
static if (v == Visit.pre) truevisitor(node.data);
backtrackingOrder!v(node.left, visitor);
static if (v == Visit.inv) truevisitor(node.data);
backtrackingOrder!v(node.right, visitor);
static if (v == Visit.post) truevisitor(node.data);
}
}

void levelOrder(TNode, TyF=void*)(TNode node, TyF visitor=null, TNode[] more=[]) {
static if (is(TyF == void*)) auto truevisitor = &show!(typeof(node.data));
else auto truevisitor = visitor;
if (node !is null) {
more ~= [node.left, node.right];
truevisitor(node.data);
}
if (more.length)
levelOrder(more[0], truevisitor, more[1..$]);
}

void main() {
auto tree = node(1,
   node(2,
node(4,
   node(7)),
node(5)),
   node(3,
node(6,
   node(8),
   node(9))));
write(" preOrder: ");
backtrackingOrder!(Visit.pre)(tree);
write("\n inOrder: ");
backtrackingOrder!(Visit.inv)(tree);
write("\n postOrder: ");
backtrackingOrder!(Visit.post)(tree);
write("\nlevelorder: ");
levelOrder(tree);
writeln();
}

Output:
  preOrder: 1 2 4 7 5 3 6 8 9
   inOrder: 7 4 2 5 1 8 6 9 3
 postOrder: 7 4 5 2 8 9 6 3 1
levelorder: 1 2 3 4 5 6 7 8 9

A possible design for Java is to create a Node class (using generics to allow for different types of data) that has preOrder, InOrder, etc, methods. This simple design can be used in D too. But it conflates data structure and algorithms, so you can't use the same algorithms (the tree visits) for other kinds of nodes.

So if your language is flexible enough (like C++, D, Haskell, or Python) it's better to follow the strategy used in the C++ STL, and implement generic algorithms, that work with more kinds of binary tree nodes and allow for a more flexible management of the node being visited.

Another design that can be natural in modern versions of Python is to create iterators, that yield the current node. This is very handy, and such strategy can be used in D too (with opApply or with the second iteration protocol of D2) but I have not used it in my D code. In Python (and in some other languages, in D too if you use opApply) this strategy leads to O(n^2) tree visits. (There is a Python PEP that if well implemented may solve this problem).

Th flexibility of D language has allowed me to merge the three backtracking visits (pre, in and post - order) in a single templated function with zero overehead.

In the code I have used a class to represent the node to keep code a little simpler, but a struct too can be used with very small changes. Such structs are smaller 8 bytes less on a 32 bit system) and it's simpler to allocate them with a memory pool that can halve the time needed to create and allocate the tree.

I have added a helper node() templated function, it just allocates a new node and returns it. In D something similar can also be done with a static opCall inside Node, but here it's also templated, and templatd methods can't replace opCall of object (I may be wrong on this, but I don't think so). If you have a different Node class/struct you need a different helper function, or you have to use opCall (if the Node isn't generic) or you have to build the tree in a simpler way.

Node!T is the new compact syntax introduced in D2 to instantiate a template when you have a single argument. The standard older syntax is Node!(T), that equals to C++ Node.

show() is a little function that's used as default visitor of the node. It's templated, so you have to instantiate it before taking its address to use it as function pointer.

backtrackingOrder() merges the three tree visits, its code is a little tricky.

The enum Visit is used to represent one of the three possible visits. To specify it you can first partial specify backtrackingOrder() according to visit type known a compile-time, and then you can fully specify it automatically with the given root node and an optional callable.

The node can be any type that has a left, right and node attributes.

visitor can be any callable, a delegate, function pointer, or callable object. If visitor is unspecified you can omit it, and it uses show() instantiated on the type of the data.

The static ifs are done at compile time, and they don't create a scope, so truevisitor (its type is found automatically) is then visible under the static if. The is() syntax is used to test if types are the same (a better simpler design for the D language is just to allow == between them).

In library code you may add few more static asserts inside backtrackingOrder() to test that visitor is a callable, with a line of code like:
static assert(IsCallable!(typeof(truevisitor)), "...");

Bartosz Milewski

2009-09-22T21:24:27+00:00

Here’s the video from my recent talk to the Northwest C++ Users Group (NWCPP) about how to translate the data-race free type system into a system of user-defined annotations in C++. I start with the definition of a data race and discuss various ways to eliminate them. Then I describe the ownership system and give a few examples of annotated programs.

Here are the slides from the presentation. They include extensive notes.

By the way, we are looking for speakers at the NWCPP, not necessarily related to C++. We are thinking of changing the charter to include all programming languages. If you are near Seattle on Oct 21 09 (or any third Wednesday of the month), and you are ready to give a 60 min presentation, please contact me.

vincenzoampolo7

2009-09-20T10:30:43+00:00

I’ve been working with ldc for a long time. I enjoyed it, i helped the development with tickets and hacking ldc a bit. I even tried to compile Tango as shared library but i got an error, probably caused by the compiler since people reported that in gdc they were able to do it. I then started guessing if llvm is so stable as it seems and if it can substitute the gnu compiler collection. Then i came to these llvm vs gcc benchmarks. Well the result is that llvm is not so fast and reliable as promised. In the same days, a message posted on the D newsgroup got me. I started thinking that resurrection gdc is the only way to make a stable and reliable compiler accepted in the FOSS community for the D programming language. But it should resurrect it should implement the D2 specs: there are no other compilers than dmd which support D2 around. So, me and Michael joined to the challenge to work on gdc

We got the lastest working branch of gdc, the one who relies on gcc 4.3.1. We then copied in our repository in bitbucket and applied some changes, after two days of works, gdc for D2.014 worked under gcc 4.3.4 (there were some problems in the default version when compiling the Phobos library). As a proof that it works look at it

goshawk@earth:/tmp/test/usr/local/gcc-4.3/bin$ ./gdc ~/test.d
goshawk@earth:/tmp/test/usr/local/gcc-4.3/bin$ ./a.out
Hello World, Reloaded
goshawk@earth:/tmp/test/usr/local/gcc-4.3/bin$ ./gdc -v
Using built-in specs.
Target: x86_64-unknown-linux-gnu
Configured with: ../configure –prefix=/usr/local/gcc-4.3 –enable-languages=c,d,c++ –disable-multilib –disable-shared
Thread model: posix
gcc version 4.3.4 (GCC)

Nice, isn’t it?

Now while Michael is focusing in fixing the D1 part, i started merging the lastest dmd D2 compiler in gdc. Making a diff against dmd2.014 and gdc2.014 i’m applying all the necessary patches in gdc for D2 2.032.

We opened a dedicated IRC channel in irc.freenode.net #d.gdc. Feel free to join!

You can find full instructions in how to compile gdc in our wiki page.

Any help, documentation, word on this challenge is appreciated. See you soon

Code performance in D/Java

2009-09-19T15:05:44+00:00

The code discussed in this post:
http://www.fantascienza.net/leonardo/js/life_bench.zip

To try to find "performance bugs" in both the LDC D compiler and the LLVM back-end I am exploring the performance signature of many small programs, often translating them to D. To perform such tests I compare the timings of the D code with the original C or Java code.

Java here is useful because its performance profiles are a little different from the usual C ones. Java HotSpot is able to inline many virtual calls, and its GarbageCollector is quite efficient (both things aren't good in all current D implementations).

I've found a small Life (Horton Conway's game) implementation in Java that shows a higher performance compared to D code (the original Java code isn't mine), so I cleaned up the Java code, I have removed the useless stuff from it (see the zip for the Java code), and I have translated it to as much close as possible D code (able to run both on Tango and Phobos). The result is the first D program (life1_d.d).

I have taken care of setting as final the main class in the D code, to allow inlining.

The Java GC (of Sun) is more efficient than the nonmoving D GC, so first of all I have taken a look at the number of memory allocations, bue they weren't the cause of the performance difference. I've profiled both the D and Java code, and I've seen that the calc_new() method was the one taking most time. I've also seen that the amount of inlining with LDC (using -O5 -release -inline) was not enough, so I've compiled the D code with the following, that forces a more aggressive inlining, that improves performance:

ldc -O5 -release -inline -inline-threshold=2000000001 life1_d.d

I have also seen that for this program Link-Time Optimization plus Interning improve the performance of the code:

ldc -O5 -release -inline -inline-threshold=2000000001 -output-bc life1_d.d

opt -std-compile-opts life1_d.bc > life1_do.bc

llvm-ld -native -ltango-base-ldc -ltango-user-ldc -ldl -lm -lpthread -internalize-public-api-list=_Dmain -o=life1_do life1_do.bc

I have done many more experiments, here you can find the ones that have given good results. I have split the Life class in its methods plus global values, I don't know why this increases performance with the LDC compiler (see the timings), see life2_d.d.

Later I have uses simple pointers as function arguments instead of arrays (see see life3_d.d), again I don't know why this increases the performance with the LDC compiler, also because most of sych functions get inlined anyway.

Now the performance of life3_d.d was bad only for large values (the last values of the use_Sizes array). After several more experiments I have by chance found that the cause was in the inner loop of the calc_new() function, where the whole botRow array is reset to zero. I think here the Java compiler recognizes such loop as a clearing, and replaces it with a call to a function like memset(). This makes the Java code slower than the D one for small botRow arrays, but faster for the longer ones (because it seems an inlined loop is faster than a memset when the length is small, about 50-100 or so if array items are 4 byte long).

So in life4_d.d I have replaced the loop with something a little more complex that takes a look at botRow length:

if (botRow.length > 100)
    botRow[] = 0;
else
    for (int c = 0; c < botRow.length; c++)
        botRow[c] = 0;

The timings of the 4th D version are now good enough, but not the best still, I don't know why. (I am now trying to find a faster array reset that uses an asm routine that contains the movntps SSE instuction).

------------------------

Scores on Windows Vista, using DMD compiler for the D code (bigger is better):

java -server Life
Size    average
Adjusting 6744 to 2811246
5       14288
6       14974
8       14125
10      15697
15      14175
25      15369
50      14595
250     6331
1000    2218
2500    880


life1_d.exe
Size    average
5       9248
6       8938
8       10213
10      10469
15      10974
25      9898
50      7189
250     1694
1000    421
2500    170


life2_d.exe
Size    average
5       9424
6       8270
8       8083
10      7876
15      8389
25      7191
50      5288
250     1331
1000    331
2500    147


life3_d.exe
Size    average
5       10156
6       9172
8       9353
10      9043
15      8802
25      8452
50      5865
250     1357
1000    356
2500    151


life4_d.exe
Size    average
Adjusting 917315 to 0
5       10145
6       9275
8       9631
10      10282
15      10061
25      9083
50      6286
250     4747
1000    1596
2500    743

Home Vista Basic with 2 GB RAM, Celeron 2.13 GHz

Compilers used:

Java version "1.7.0-ea"
Java(TM) SE Runtime Environment (build 1.7.0-ea-b66)
Java HotSpot(TM) Client VM (build 16.0-b06, mixed mode, sharing)

DMD Digital Mars D Compiler v1.042

------------------------

Scores on Ubuntu running on VirtualBox running on Vista, using LDC compiler for the D code (bigger is better):

java -server Life
Size	average
Adjusting 28766 to 951466
Adjusting 951466 to 2616313
5	13740
6	16494
8	14922
10	19481
15	20602
25	21249
50	19979
250	7493
1000	2609
2500	1004


ldc -O5 -release -inline life1_d.d
Size	average
5	17810
6	16661
8	15147
10	15201
15	14818
25	12901
50	4384
250	1893
1000	485
2500	198


ldc -O5 -release -inline -inline-threshold=2000000001 life1_d.d
Size	average
5	16016
6	14690
8	13183
10	11823
15	11100
25	10144
50	5203
250	2305
1000	571
2500	256

ldc -O5 -release -inline -inline-threshold=2000000001 -output-bc life1_d.d
opt -std-compile-opts life1_d.bc > life1_do.bc
llvm-ld -native -ltango-base-ldc -ltango-user-ldc -ldl -lm -lpthread -internalize-public-api-list=_Dmain -o=life1_do life1_do.bc

Size	average
5	22628
6	18773
8	14326
10	18820
15	17558
25	15264
50	10155
250	2329
1000	578
2500	251


ldc -O5 -release -inline -inline-threshold=2000000001 life2_d.d
Size	average
5	16557
6	15205
8	13149
10	12037
15	10870
25	10051
50	6470
250	2327
1000	571
2500	247


ldc -O5 -release -inline -inline-threshold=2000000001 life3_d.d
Size	average
5	18205
6	17032
8	15948
10	17798
15	17907
25	15656
50	10191
250	2310
1000	574
2500	248


ldc -O5 -release -inline -inline-threshold=2000000001 life4_d.d
Size	average
5	18169
6	16576
8	16129
10	17616
15	17937
25	15486
50	9667
250	6714
1000	2006
2500	886

ldc -O5 -release -inline -inline-threshold=2000000001 -output-bc life4_d.d
opt -std-compile-opts life4_d.bc > life4_do.bc
llvm-ld -native -ltango-base-ldc -ltango-user-ldc -ldl -lm -lpthread -internalize-public-api-list=_Dmain -o=life4_do life4_do.bc

Size	average
5	25522
6	22085
8	21079
10	20964
15	21987
25	19300
50	13160
250	6774
1000	1986
2500	900

This version (not included in the zip) is the first D one, but the cleaning of the botRow array in calc_new() is done as in life4_d.d:
ldc -O5 -release -inline -inline-threshold=2000000001 -output-bc life1b_d.d
opt -std-compile-opts life1b_d.bc > life1b_do.bc
llvm-ld -native -ltango-base-ldc -ltango-user-ldc -ldl -lm -lpthread -internalize-public-api-list=_Dmain -o=life1b_do life1b_do.bc

Size	average
5	22957
6	19394
8	16457
10	17208
15	18177
25	15522
50	5089
250	6638
1000	1971
2500	889

Code running on Ubuntu 9.4 running on VirtualBox 3.0.6 r52128.

Compilers used:

LDC based on DMD v1.045 and llvm 2.6 (Thu Sep 10 23:50:27 2009)

Java version "1.6.0_16"
Java(TM) SE Runtime Environment (build 1.6.0_16-b01)
Java HotSpot(TM) Client VM (build 14.2-b01, mixed mode, sharing)

------------------------

Bartosz Milewski

2009-09-08T16:49:52+00:00

“I’ve been doing some template metaprogramming lately,” he said nonchallantly.

Why is it funny? Because template metaprogramming is considered really hard. I mean, über-guru-level hard. I’m lucky to be friends with two such gurus, Andrei Alexandrescu who wrote the seminal “Modern C++ Programming,” and Eric Niebler, who implemented the Xpressive library for Boost; so I know the horrors.

But why is template metaprogramming so hard? Big part of it is that C++ templates are rather ill suited for metaprogramming, to put it mildly. They are fine for simple tasks like parameterized containers and some generic algorithms, but not for operations on types or lists of types. To make things worse, C++ doesn’t provide a lot in terms of reflection, so even such simple tasks like deciding whether a given type is a pointer are hard (see the example later). Granted, C++0x offers some improvements, like template parameter packs; but guru-level creds are still required.

So, I’ve been doing some template metaprogramming lately… in D. The D programming language doesn’t have the baggage of compatibility with previous botched attempts, so it makes many things considerably easier on programmers. But before I get to it, I’d like to talk a little about the connection between generic programming and functional programming, give a short intro to functional programming; and then show some examples in C++ and D that involve pattern matching and type lists.

It’s not your father’s language

The key to understanding metaprogramming is to realize that it’s done in a different language than the rest of your program. Both in C++ and D you use a form of functional language for that purpose. First of all, no mutation! If you pass a list of types to a template, it won’t be able to append another type to it. It will have to create a completely new list using the old list and the new type as raw materials.

Frankly, I don’t know why mutation should be disallowed at compile time (all template calculations are done at compile time). In fact, for templates that are used in D mixins, I proposed not to invent a new language but to use a subset of D that included mutation. It worked just fine and made mixins much easier to use (for an example, see my DrDobbs article).

Once you disallow mutation, you’re pretty much stuck with functional paradigm. For instance, you can’t have loops, which require a mutable loop counter or some other mutable state, so you have to use recursion.

You’d think functional programmers would love template metaprogramming; except that they flip over horrendous syntax of C++ templates. The one thing going for functional programming is that it’s easy to define and implement. You can describe typeless lambda calculus with just a few formulas in operational semantics.

One thing is important though: meta-language can’t be strongly typed, because a strongly typed language requires another language to implement generic algorithms on top of it. So to terminate the succession of meta-meta-meta… languages there’s a need for either a typeless, or at least dynamically-typed, top-level meta-language. My suspicion is that C++0x concepts failed so miserably because they dragged the metalanguage in the direction of strong typing. The nails in the coffin for C++ concepts were concept maps, the moral equivalent of implicit conversions in strongly-typed languages.

Templates are still not totally typeless. They distinguish between type arguments (introduced by typename or class in C++), template template arguments, and typed template arguments. Here’s an example that shows all three kinds:

template<class T, template<class X> class F, int n>

Functional Programming in a Nutshell

“Functions operating on functions”–that’s the gist of functional programming. The rest is syntactic sugar. Some of this sugar is very important. For instance, you want to have built-in integers and lists for data types, and pattern matching for dispatching.

-Functions

Here’s a very simple compile-time function in the C++ template language:

template<class T>
struct IsPtr {
    static const bool apply = false;
}

If it doesn’t look much like a function to you, here it is in more normal ad-hoc notation:

IsPtr(T) {
    return false;
}

You can “execute” or “call” this meta-function by instantiating the template IsPtr with a type argument and accessing its member apply:

IsPtr<int>::apply;

There is nothing magical about “apply”, you can call it anything (“result” or “value” are other popular identifiers). This particular meta-function returns a Boolean, but any compile-time constant may be returned. What’s more important, any type or a template may be returned. But let’s not get ahead of ourselves.

-Pattern matching

You might be wondering what the use is for a function (I’ll be dropping the “meta-” prefix in what follows) that always returns false and is called IsPtr. Enter the next weapon in the arsenal of functional programmers: pattern matching. What we need here is to be able to match function arguments to different patterns and execute different code depending on the match. In particular, we’d like to return a different value, true, for T matching the pattern T*. In the C++ metalanguage this is done by partial template specialization. It’s enough to define another template of the same name that matches a more specialized pattern, T*:

template<class T>
struct IsPtr<T*> {
    static const bool apply = true;
}

When faced with the call,

IsPtr<int*>::apply

the compiler will first look for specializations of the template IsPtr, starting with the most specialized one. In our case, the argument int* matches the pattern T* so the version returning true will be instantiated. Accessing the apply member of this instantiation will result in the Boolean value true, which is exactly what we wanted. Let me rewrite this example using less obfuscated syntax.

IsPtr(T*) {
    return true;
}
IsPtr(T) { // default case
    return false;
}

D template syntax is slightly less complex than that of C++. The above example will read:

template IsPtr(T) {
    static if (is (T dummy: U*, U))
        enum IsPtr = true;
    else
        enum IsPtr = false;
}
// Compile-time tests
static assert( IsPtr!(int*) );
static assert( !IsPtr!(int) );

As you can see, D offers compile-time if statements and more general pattern matching. The syntax of pattern matching is not as clear as it could be (what’s with the dummy?), but it’s more flexible. Compile-time constants are declared as enums.

There is one little trick (a hack?) that makes the syntax of “function call” a little cleaner. If, inside the template, you define a member of the same name as the template itself (I call it the “eponymous” member) than you don’t have to use the “apply” syntax. The “call” looks more like a call, except for the exclamation mark before the argument list (a D tradeoff for not using angle brackets). You’ll see later how the eponymous trick fails for more complex cases.

-Lists

The fundamental data structure in all functional languages is a list. Lists are very easy to operate upon using recursive algorithms and, as it turns out, they can be used to define arbitrarily complex data structures. No wonder C++0x felt obliged to introduce a compile-time type list as a primitive. It’s called a template parameter pack and the new syntax is:

template<class... T>Foo

You can instantiate such a template with zero arguments,

Foo<>

one argument,

Foo<int>

or more arguments,

Foo<int, char*, void*>

How do you iterate over a type list? Well, there is no iteration in the metalanguge so the best you can do is to use recursion. To do that, you have to be able to separate the head of the list from its tail. Then you perform the action on the head and call yourself recursively with the tail. The head/tail separation is done using pattern matching.

Let me demonstrate a simple example from the paper Variadic Templates by Garry Powell et al. It calculates the length of a pack using recursion. First, the basic case–length-zero list:

template<>
struct count <> {
    static const int value = 0;
}

That is the full specialization of a template, so it will be tried first. Here’s the general case:

template<typename Head, typename... Tail>
struct count<Head, Tail...> {
    static const int value = 1 + count<Tail...>::value;
}

Let’s see what it would look like in “normal” notation:

count() {
    return 0;
}
count(head, tail) {
    return 1 + count(tail);
}

And here’s the D version:

template count(T...) {
    static if (T.length == 0)
        enum count = 0;
    else
        enum count = 1 + count!(T[1..$]);
}
// tests
static assert( count!() == 0);
static assert( count!(int, char*, char[]) == 3);

T… denotes a type tuple, which supports array-like access. To get to the tail of the list, D uses array slicing, where T[1..$] denotes the slice of the array starting from index 1 up to the length of the array (denoted by the dollar sign). I’ll explain the important differences between C++ pack and D tuple (including pack expansion) in the next installment.

Conclusion

When looked upon from the functional perspective, template metaprogramming doesn’t look as intimidating as it it seems at first. Knowing this interpretation makes you wonder if there isn’t a better syntax or even a better paradigm for metaprogramming.

I’ll discuss more interesting parts of template metaprogramming in the next installment (this one is getting too big already). In particular, I’ll show examples of higher order meta-functions like Filter or Not and some interesting tricks with type lists.

Life in hell

2009-09-06T18:24:31+00:00

Warning

Long post ahead =)

As I said before, debug is hell in D, at least if you're using a compiler that doesn't write proper debug information and you're writing a garbage collector. But you have to do it when things go wrong. And things usually go wrong.

This is a small chronicle about how I managed to debug a weird problem =)

I had my Naive GC working and getting good stats with some small micro-benchmarks, so I said let's benchmark something real. There is almost no real D applications out there, suitable for an automated GC benchmark at least [1]. Dil looked like a good candidate so I said let's use Dil in the benchmark suite!.

And I did. But Dil didn't work as I expected. Even when running it without arguments, in which case a nice help message like this should be displayed:

dil v1.000
Copyright (c) 2007-2008 by Aziz Köksal. Licensed under the GPL3.

Subcommands:
  help (?)
  compile (c)
  ddoc (d)
  highlight (hl)
  importgraph (igraph)
  python (py)
  settings (set)
  statistics (stats)
  tokenize (tok)
  translate (trans)

Type 'dil help <subcommand>' for more help on a particular subcommand.

Compiled with Digital Mars D v1.041 on Sat Aug 29 18:04:34 2009.

I got this instead:

Generate an XML or HTML document from a D source file.
Usage:
  dil gen file.d [Options]

Options:
  --syntax         : generate tags for the syntax tree
  --xml            : use XML format (default)
  --html           : use HTML format

Example:
  dil gen Parser.d --html --syntax > Parser.html

Which it isn't even a valid Dil command (it looks like a dead string in some data/lang_??.d files).

I ran Valgrind on it and detected a suspicious invalid read of size 4 when reading the last byte of a 13 bytes long class instance. I thought maybe the compiler was assuming the GC allocated block with size multiples of the word size, so I made gc_malloc() allocate multiples of the word size, but nothing happened. Then I thought that maybe the memory blocks should be aligned to a multiple of a word, so I made gc_malloc() align the data portion of the cell to a multiple of a word, but nothing.

Since Valgrind only detected that problem, which was at the static constructor of the module tango.io.Console, I though it might be a Tango bug, so I reported it. But it wasn't Tango's fault. The invalid read looked like a DMD 1.042 bug; DMD 1.041 didn't have that problem, but my collector still failed to run Dil. So I was back to zero.

I tried the Tango stub collector and it worked, so I tried mine disabling the collections, and it worked too. So finally I could narrow the problem to the collection phase (which isn't much, but it's something). The first thing I could think it could be wrong in a collection is that cells still in use are swept as if they were unused, so I then disabled the sweep phase only, and it kept working.

So, everything pointer to prematurely freed cells. But why my collector was freeing cells prematurely being so, so simple? I reviewed the code a couple of times and couldn't find anything evidently wrong. To confirm my theory and with the hope of getting some extra info, I decided to write a weird pattern in the swept cells and then check if that pattern was intact when giving them back to the mutator (the basic GC can do that too if compiled with -debug=MEMSTOMP). That would confirm that the swept memory were still in use. And it did.

The I tried this modified GC with memory stomp with my micro-benchmarks and they worked just fine, so I started to doubt again that it was my GC's problem. But since those benchmarks didn't use much of the GC API, I thought maybe Dil was using some strange features of making some assumptions that were only true for the current implementation, so I asked Aziz Köksal (Dil creator) and he pointed me to some portion of code that allocated memory from the C heap, overriding the operators new and delete for the Token struct. There is a bug in Dil there, because apparently that struct store pointers to the GC heap but it's not registered as a root, so it looks like a good candidate.

So I commented out the overridden new and delete operators, so the regular GC-based operators were used. But I still got nothing, the wrong help message were printed again. Then I saw that Dil was manually freeing memory using delete. So I decided to make my gc_free() implementation a NOP to let the GC take over of all memory management... And finally all [2] worked out fine! =)

So, the problem should be either my gc_free() implementation (which is really simple) or a Dil bug.

In order to get some extra information on where the problem is, I changed the Cell.alloc() implementation to use mmap to allocate whole pages, one for the cell's header, and one or more for the cell data. This way, could easily mprotect the cell data when the cell was swept (and un-mprotecting them when they were give back to the program) in order to make Dil segfault exactly where the freed memory was used.

I ran Dil using strace and this is what happened:

[...]
 (a)  write(1, "Cell.alloc(80)\n", 15)        = 15
 (b)  mmap2(NULL, 8192, PROT_READ|PROT_WRITE, ...) = 0xb7a2e000
[...]
 (c)  mprotect(0xb7911000, 4096, PROT_NONE)   = 0
      mprotect(0xb7913000, 4096, PROT_NONE)   = 0
[...]
      mprotect(0xb7a2b000, 4096, PROT_NONE)   = 0
      mprotect(0xb7a2d000, 4096, PROT_NONE)   = 0
 (d)  mprotect(0xb7a2f000, 4096, PROT_NONE)   = 0
      mprotect(0xb7a43000, 4096, PROT_NONE)   = 0
      mprotect(0xb7a3d000, 4096, PROT_NONE)   = 0
[...]
      mprotect(0xb7a6b000, 4096, PROT_NONE)   = 0
 (e)  mprotect(0xb7a73000, 4096, PROT_NONE)   = 0
 (f)  mprotect(0xb7a73000, 4096, PROT_READ|PROT_WRITE) = 0
      mprotect(0xb7a6b000, 4096, PROT_READ|PROT_WRITE) = 0
[...]
      mprotect(0xb7a3f000, 4096, PROT_READ|PROT_WRITE) = 0
 (g)  mprotect(0xb7a3d000, 4096, PROT_READ|PROT_WRITE) = 0
      --- SIGSEGV (Segmentation fault) @ 0 (0) ---
      +++ killed by SIGSEGV (core dumped) +++

(a) is a debug print, showing the size of the gc_malloc() call that got the address 0xb7a2e000. The mmap (b) is 8192 bytes in size because I allocate a page for the cell header (for internal GC information) and another separated page for the data (so I can only mprotect the data page and keep the header page read/write); that allocation asked for a new fresh couple of pages to the OS (that's why you see a mmap).

From (c) to (e) you can see a sequence of several mprotect, that are cells being swept by a collection (protecting the cells against read/write so if the mutator tries to touch them, a SIGSEGV is on the way).

From (f) to (g) you can see another sequence of mprotect, this time giving the mutator permission to touch that pages, so that's gc_malloc() recycling the recently swept cells.

(d) shows the cell allocated in (a) being swept. Why the address is not the same (this time is 0xb7a2f000 instead of 0xb7a2e000)? Because, as you remember, the first page is used for the cell header, so the data should be at 0xb7a2e000 + 4096, which is exactly 0xb7a2f000, the start of the memory block that the sweep phase (and gc_free() for that matter) was protecting.

Finally we see the program getting his nice SIGSEGV and dumping a nice little core for touching what it shouldn't.

Then I opened the core with GDB and did something like this [3]:

Program terminated with signal 11, Segmentation fault.
(a)  #0  0x08079a96 in getDispatchFunction ()
     (gdb) print $pc
(b)  $1 = (void (*)()) 0x8079a96 <getDispatchFunction+30>
     (gdb) disassemble $pc
     Dump of assembler code for function
     getDispatchFunction:
     0x08079a78 <getDispatchFunction+0>:  push   %ebp
     0x08079a79 <getDispatchFunction+1>:  mov    %esp,%ebp
     0x08079a7b <getDispatchFunction+3>:  sub    $0x8,%esp
     0x08079a7e <getDispatchFunction+6>:  push   %ebx
     0x08079a7f <getDispatchFunction+7>:  push   %esi
     0x08079a80 <getDispatchFunction+8>:  mov    %eax,-0x4(%ebp)
     0x08079a83 <getDispatchFunction+11>: mov    -0x4(%ebp),%eax
     0x08079a86 <getDispatchFunction+14>: call   0x80bccb4 <objectInvariant>
     0x08079a8b <getDispatchFunction+19>: push   $0xb9
     0x08079a90 <getDispatchFunction+24>: mov    0x8(%ebp),%edx
     0x08079a93 <getDispatchFunction+27>: add    $0xa,%edx
(c)  0x08079a96 <getDispatchFunction+30>: movzwl (%edx),%ecx
     [...]
     (gdb) print /x $edx
(d)  $2 = 0xb7a2f000

First, in (a), GDB tells where the program received the SIGSEGV. In (b) I print the program counter register to get a more readable hint on where the program segfaulted. It was at getDispatchFunction+30, so I disassemble that function to see that the SIGSEGV was received when doing movzwl (%edx),%ecx (moving the contents of the ECX register to the memory pointed to by the address in the register EDX) at (c). In (d) I get the value of the EDX register, and it's 0xb7a2f000. Do you remember that value? Is the data address for the cell at 0xb7a2e000, the one that was recently swept (and mprotected). That's not good for business.

This is the offending method (at dil/src/ast/Visitor.d):

Node function(Visitor, Node) getDispatchFunction()(Node n)
{
    return cast(Node function(Visitor, Node))dispatch_vtable[n.kind];
}

Since I can't get any useful information from GDB (I can't even get a proper backtrace [4]) except for the mangled function name (because the wrong debug information produced by DMD), I had to split that function into smaller functions to confirm that the problem was in n.kind (I guess I could figure that out by eating some more assembly, but I'm not that well trained at eating asm yet =). This means that the Node instance n is the one prematurely freed.

This is particularly weird, because it looks like the node is being swept, not prematurely freed using an explicit delete. So it seems like the GC is missing some roots (or there are non-aligned pointers or weird stuff like that). The fact that this works fine with the Tango basic collector is intriguing too. One thing I can come up with to explain why it works in the basic collector is because it makes a lot less collections than the naive GC (the latter is really lame =). So maybe the rootless object becomes really free before the basic collector has a chance to run a collection and because of that the problem is never detected.

I spent over 10 days now investigating this issue (of course this is not near a full-time job for me so I can only dedicate a couple of days a week to this =), and I still can't find a clear cause for this problem, but I'm a little inclined towards a Dil bug, so I reported one =). So we'll see how this evolves; for now I'll just make gc_free() a NOP to continue my testing...

[1]	Please let me know if you have any working, real, Tango-based D application suitable for GC benchmarks (i.e., using the GC and easily scriptable to run it automatically).

[2]	all being running Dil without arguments to get the right help message =)

[3] I have shortened the name of the functions because they were huge, cryptic, mangled names =). The real name of getDispatchFunction is _D3dil3ast7Visitor7Visitor25__T19getDispatchFunctionZ19getDispatchFunctionMFC3dil3ast4Node4NodeZPFC3dil3ast7Visitor7VisitorC3dil3ast4Node4NodeZC3dil3ast4Node4Node (is not much better when demangled: class dil.ast.Node.Node function(class dil.ast.Visitor.Visitor, class dil.ast.Node.Node)* dil.ast.Visitor.Visitor.getDispatchFunction!().getDispatchFunction(class dil.ast.Node.Node) =). The real name of objectInvariant is D9invariant12_d_invariantFC6ObjectZv and has no demagled name that I know of, but I guessed is the Object class invariant.

[4]	Here is what I get from GDB: (gdb) bt #0 0x08079a96 in getDispatchFunction () #1 0xb78d5000 in ?? () #2 0xb789d000 in ?? () Backtrace stopped: previous frame inner to this frame (corrupt stack?) (function name unmangled and shortened for readbility)

DMD 1.047 and 2.032

2009-09-06T03:59:21+00:00

Sorry for being so quiet here. I’ve been largely out of the D loop for a bit, though I do check the newsgroups once every week or so for major announcements. The big news this week is the release of the shiny new DMD 1.047 and 2.032. Both versions include updates to the Compile Time Function [...]

Bartosz Milewski

2009-09-01T21:51:24+00:00

Spawning a thread in non-functional languages is considered a very low-level primitive. Often spawn or CreateThread takes a function pointer and an untyped (void) pointer to “data”. The newly created thread will execute the function, passing it the untyped pointer, and it’s up to the function to cast the data into something more palatable. This is indeed the lowest of the lowest. It’s the stinky gutters of programming.

Isn’t it much nicer to create a Thread or a Runnable object and let the ugly casting be done under the covers? But, as I argued before, the Thread object doesn’t really buy you much in terms of the most important safety issue: the avoidance of data races. So we can have a Thread object instead of a void pointer, and a run method that understands the format of the Thread object (or Runnable, take your pick). But because the Thread /Runnable object has reference semantics, we still end up inadvertently sharing data between threads. Unless the programmer consciously avoids or synchronizes shared access, he or she is left exposed to the most vile concurrency bugs–by default!

As they say, Cooks cover their mistakes with sauces; doctors, with six feet of dirt; language designers, with objects.

Requirements

But enough ranting! I have the opportunity to design the spawn function for D and I don’t want to do any more cover-ups beyond hiding the ugly systems’ APIs. Here are my design requirements:

spawn should take an arbitrary function as the main argument. It should refuse (at compile time) delegates or closures, which would introduce back-door sharing. (This might be relaxed later as we gain experience in controlling the sharing.)
It should take a variable number of arguments of the types compatible with those of the function parameters. It should detect type mismatches at compile time.
It should refuse the types of arguments that are prone to introducing data races. For now, I’ll allow only value types, immutable types, and explicitly shared types (shared is a type modifier in D).

I wish I could use the more precise race-free type system that I’ve been describing in my previous posts, but since I can’t get it into D2, there’s still a little bit of “programmer beware” in this implementation.

These requirement seem like a tall order for any language other than D. I wouldn’t say it’s a piece of cake in D, but it’s well within the reach of a moderately experienced programmer.

Unit Tests

Let me start by writing a little use case for my design (Oh, the joys of extreme programming!):

S s = { 3.14 };
Tid tid = spawn(&thrFun, 2, s, "hello");
tid.join;

Here’s the definition of the function, thrFun:

void thrFun(int i, S s, string str) {
    writeln("thread function called with: ", i, ", ", s.fl, " and ", str);
}

Its parameter types fulfill the restrictions I listed above. The int is a value and so is S (structs are value types in D, unless they contain references):

struct S {
    float fl;
}

Interestingly, the string is okay too, because its reference part is immutable. In D, a string is defined as an array of immutable characters, immutable (char)[].

Besides positive tests, the even more important cases are negative. For instance, I don’t want spawn to accept a function that takes an Object as argument. Objects are reference types and (if not declared shared) can sneak in unprotected sharing.

How do you build unit tests whose compilation should fail? Well, D has a trick for that (ignore the ugly syntax):

void fo(Object o) {}
assert (!__traits(compiles,
    (Object o) { return spawn(&fo, o); }));

This code asserts that the function literal (a lambda),

(Object o){ return spawn(&fo, o); }

does not compile with the thread function fo. Now that’s one useful construct worth remembering!

Implementation

Without further ado, I present you with the implementation of spawn that passes all the above tests (and more):

Tid spawn(T...)(void function(T) fp, T args)
    if (isLocalMsgTypes!(T))
{
    return core.thread.spawn( (){ fp(args); });
}

This attractively terse code uses quite a handful of D features, so let me first read it out loud for kicks:

spawn is a function template returning the Tid (Thread ID) structure. Tid is a reference-counted handle, see my previous blog.
It is parameterized by a type tuple T….
It takes the following parameters:
- a pointer to a function, fp, taking arguments of the types specified by the tuple T…
- a variable number of parameters, args, of types T….
The type tuple T… must obey the predicate isLocalMsgTypes, which is defined elsewhere.
The implementation of spawn calls the (in general, unsafe) function core.thread.spawn (defined in the module core.thread) with the following closure (nested function):
```
    (){ fp(args); }
```
which captures local variables, args.

As you may guess, the newly spawned thread runs the closure, so it has access to captured args from the original thread. In general, that’s a recipe for a data race. What saves the day is the predicate isLocalMsgTypes, which defines what types are safe to pass as inter-thread messages.

Note the important point: there should be no difference between the constraints imposed on the types of parameters passed to spawn and the types of messages that can be sent to a thread. You can think of spawn parameters as initial messages sent to a nascent thread. As I said before, message types include value types, immutable types and shared types (no support for unique types yet).

Useful D features

Let me explain some of D novelties I used in the definition of spawn.

A function with two sets of parenthesized parameters is automatically a template–the first set are template parameters, the second, runtime parameters.

-Tuples

Type tuples, like T…, represent arbitrary lists of types. Similar constructs have also been introduced in C++0x, presumably under pressure from Boost, to replace the unmanageably complex type lists.

What are the things that you can do with a type-tuple in D? You can retrieve its length (T.length), access its elements by index, or slice it; all at compile time. You can also define a variable-argument-list function, like spawn and use one symbol for a whole list of arguments, as in T args:

Tid spawn(T...)(void function(T) fp, T args)

Now let’s go back to my test:

Tid tid = spawn(&f, 2, s, "hello");

I spawn a thread to execute a function of three arguments, void f(int i, S s, string str). The spawn template is instantiated with a type tuple (int, S, string). At compile time, this tuple is successfully tested by the predicate isLocalMsgTypes. The actual arguments to spawn, besides the pointer to function, are (2, s, “hello”), which indeed are of correct types. They appear inside spawn under the collective name, args. They are then used as a collective argument to fp inside the closure, (){ fp(args); }.

-Closures

The closure captures the arguments to spawn. It is then passed to the internal function (not a template anymore),

core.thread.spawn(void delegate() dlg)

When the new thread is created, it calls the closure dlg, which calls fp with the captured arguments. At that point, the value arguments, i and s are copied, along with the shallow part of the string, str. The deep part of the string, the buffer, is not copied–and for a good reason too– it is immutable, so it can safely be read concurrently. At that point, the thread function is free to use those arguments without worrying about races.

-Restricted Templates

The if statement before the body of a template is D’s response to C++0x DOA concepts (yes, after years of design discussions, concepts were finally killed with extreme prejudice).

if (isLocalMsgTypes!(T))

The if is used to create “restricted templates”. It contains a logical compile-time expression that is checked before the template is instantiated. If the expression is false, the template doesn’t match and you get a compile error. Notice that template restrictions not only produce better error messages, but can also impose restrictions that are otherwise impossible or very hard to enforce. Without the restriction, spawn could be called with an unsuitable type, e.g. an Object not declared as shared and the compiler wouldn’t even blink.

(I will talk about template restrictions and templates in general in a future blog.)

–Message Types

Besides values, we may also pass to spawn objects that are declared as immutable or shared (in fact, we may pass them inside values as well). In D, shared objects are supposed to provide their own synchronization–their methods must either be synchronized or lock free. An example of a shared object that you’d want to pass to spawn is a message queue–to be shared between the parent thread and the spawned thread.

You might remember that my race-free type system proposal included unique types, which would be great for message passing, and consequently as arguments to spawn (there is a uniqueness proposal for Scala, and there’s the Kilim message-passing system for Java based on unique types). Unfortunately, unique types won’t be available in D2. Instead some kind of specialized Unique library classes might be defined for that purpose.

Conclusion

The D programming language has two faces. On the one hand, it’s easy to use even for a beginner. On the other hand, it provides enough expressive power to allow for the creation of sophisticated and safe libraries. What I tried to accomplish in this post is to give a peek at D from the perspective of a library writer. In particular I described mechanisms that help make the concurrency library safer to use.

This is still work in progress, so don’t expect to see it in the current releases of D2.

"Silly benchmark" in D/C++

2009-08-30T19:45:46+00:00

All the code discussed here:
http://www.fantascienza.net/leonardo/js/silly_bench.zip

Slava Pestov, author of the programming language Factor, has created a very simple benchmark. Despite being defined "silly" such benchmark has shown me some interesting things.

This the original posts:
"Performance comparison between Factor and Java on a contrived benchmark"
http://factor-language.blogspot.com/2009/08/performance-comparison-between-factor.html

"Struct arrays benchmark revisited: trig function calls are slow in Java, but without them Factor is still 3x faster":
http://factor-language.blogspot.com/2009/08/struct-arrays-benchmark-revisited.html

What the benchmark does:
- It works on points, which are triplets of single-precision floats, (x,y,z)
- First, the benchmark creates a list of 5000000 points for i=0..4999999, where the ith point is (sin(i),cos(i)*3,sin(i)*sin(i)/2).
-Then, each point is normalized; the x, y, and z components are divided by sqrt(x*x+y*y+z*z).
- Finally, the maximum x, y, and z components are found, for all points, and this is printed out.

The purpose of this benchmark is to compare performance of an array of struct in Factor to an array of class references in Java. It also shows how trigonometric functions are managed.

Slava has given Java code, that I have modified a bit, adding more timings inside, pulling out a subclass, making it static. The overall running time of the Java version is improved just a little.

The Java version is slow for the large amount of memory allocations, and also because it doesn't use the CPU native trigonometric instructions (sin, cos or sincos) when the input is arge, because of cross platform issues and because the Intel CPU instructions return quite inaccurate results in some cases, like when the input numers are large.

So I have created a second Java version, that uses an helper class (probably written by Razzi, http://shootout.alioth.debian.org/gp4/benchmark.php?test=partialsums〈=java&id=4 ) to reduce the input range of trig functions. The result is much faster. (2.4 seconds instead of 11.4).

Then I have created three D versions:
- The first version is designed to be very similar to the Java version, the array is filled with class references. It's slower on performing the sqrt() and other code, but even in non-release mode it's overall quite faster than the first Java version. Bothe the Java versions and this D version use lot of RAM on each iteration of the program, the GC doesn't free it efficiently.
- The second D version is more optimized. The rray is now composed of struct values. I also delete the array at the end of each loop, so the memory used by the program is about constant. I have also used free functions instead of Silly class, but this has not much effect. D1 structs don't allow constructors (D2 has struct constructors), so I have had to change code a bit there too. The result is much faster, almost two times faster than the second Java version.
- In the third D version I've tried to manually optimize what possible. The DMD compiler doesn't inline functions with ref arguments and some other things. I have avoided an useless inizialization of the struct array and I have manually inlined its filling. I have used for loops insead of foreach, and allocated memory from the GC heap in a raw way. I have optimized the code using only one call to sin() because the DMD compiler isn't able to see the two calls to sin() have the same results. I have hand-optimized the computation of the max struct, even if takes only a small percentage of the whole runtime. The result is a nice speeup compared to the second D version. In D there's no simple way to allocate an array of uninitialized structs (I have to test something with LDC: it may not initialize the array if the struct data is float x=void,y=void,z=void; To be tested). LDC compiler can probably improve such timings.

Later, to have a baseline timing, I have translated the code to C++, and I have compiled it with G++ and LLVM-GCC. The second compiler uses calls to tle libc even using the -ffast-math compilation argument, so the running time is quite slower. Compiled with G++ the program is quite faster than the D code compiled with DMD.

This code in Haskell (or Python, or D with my dlibs) can be lazy, and reduce a lot memory used and probably running time too.

When possible I'll add timings with the LDC D compiler.

(I have not put the Python+Psyco timings here because I have not enough RAM to test it with n=5 millions. With n=1 million the best Python+Psyco time is about 3700 milliseconds. With the first Java program the best timing with n=1 million is 577 milliseconds, about seven times faster).

--------------------

Timings on Windows:

...>java -Xms512m -Xmx512m -server Silly1
Run #0
0.8944272, 1.0, 0.4472136
10810 422 234 0  Time: 11466

...>java -Xms512m -Xmx512m -server Silly2
Run #0
0.8944272, 1.0, 0.4472136
1966 406 124 0  Time: 2496

...>silly_bench_cpp (g++)
Run #0
0.894427, 1.000000, 0.447214
334 255 36 5  Total=632

...>silly_bench_cpp (llvm-g++)
Run #2
0.894427, 1.000000, 0.447214
1304 374 21 5  Total=1705

...>silly_bench1_d (No -release mode):
Run #0
0.894427, 1.000000, 0.447214
6941 444 80 0  total = 7466

...>silly_bench2_d
Run #1
0.894427, 1.000000, 0.447214
785 446 74 0  total = 1305

...>silly_bench3_d
Run #2
0.894427, 1.000000, 0.447214
488 443 28 0  Total = 960

------------------

Compilation arguments for g++ and llvm-g++:
g++ -Wall -O3 -s -fomit-frame-pointer -msse -msse2 -msse3 -march=native -ffast-math silly_bench_cpp.cpp -o silly_bench_cpp

Compilation arguments for DMD:
dmd -O -release -inline:

Intel CPU Celeron 560 at 2.13 GHz, 1GB RAM, Vista Home Basic.

Compilers used:
DMD v1.042
gcc v. 4.3.3-dw2-tdm-1 (GCC)
LLVM-G++ gcc version 4.2.1 (Based on Apple Inc. build 5636) (LLVM build)
Java HotSpot(TM) Client VM (build 16.0-b06, mixed mode, sharing)

Updates and links

2009-08-27T22:36:39+00:00

Updated two toy raytracers (Sphereflake and Yopyra) in my two software pages.

I have also added a new benchmark, about the Boggle game:
http://www.fantascienza.net/leonardo/js/boggle.zip

---------------------

A nice and probably useful hierarchical allocator for C programs:
http://swapped.cc/halloc/

Why colors are important in scientific visualizations, and the risks of their bad usage:
http://www.research.ibm.com/people/l/lloydt/color/color.HTM

Theo discusses about what's important for young people to learn, the risks of violent video games, the low quality of educational software:
http://theodoregray.com/BrainRot/index.html

Allocations graphs

2009-08-26T21:54:31+00:00

Here are a set of improved statistics graphs, now including allocation statistics. All the data is plotted together and using the same timeline to ease the analysis and comparison.

Again, all graphs (as the graph title says), are taken using the Naive GC (stats code still not public yet :) and you can find the code for it in my D GC benchmark repository.

This time the (big) graphs are in EPS format because I could render them in PNG as big as I wanted and I didn't had the time to fix that =S

The graphs shows the same as in the previous post with the addition of allocation time (how long it took to perform the allocation) and space (how many memory has been requested), which are rendered in the same graph, and an histogram of cell sizes. The histogram differentiates cells with and without the NO_SCAN bit, which might be useful in terms on seeing how bad the effect of false positives could be.

You can easily see how allocation time peeks match allocations that triggered a collection for example, and how bad can it be the effect of false positives, even when almost all the heap (99.99%) has the NO_SCAN bit (see rnd_data_2).

Bartosz Milewski

2009-08-19T19:27:06+00:00

What is there to reference counting that is not obvious? In any language that supports deterministic destruction and the overloading of the copy constructor and the assignment operator it should be trivial. Or so I though until I decided to implement a simple ref-counted thread handle in D. Two problems popped up:

How does reference counting interact with garbage collection?
How to avoid data races in a multithreaded environment?

In purely garbage-collected languages, like Java, you don’t implement reference counting, period. Which is pretty bad, if you ask me. GC is great at managing memory, but not so good at managing other resources. When a program runs out of memory, it forces a collection and reclaims unused memory. When it runs out of, say, system thread handles, it doesn’t reclaim unused handles–it just dies. You can’t use GC to manage system handles. So, as far as system resources go, Java forces the programmer to use the moral equivalent of C’s malloc and free. The programmer must free the resources explicitly.

In C++ you have std::shared_ptr for all your reference-counting needs, but you don’t have garbage collection for memory–at least not yet. (There is also the Microsoft’s C++/CLI which mixes the two systems.)

D offers the best of both worlds: GC and deterministic destruction. So let’s use GC to manage memory and reference counting (or other policies, like uniqueness) to manage other limited resources.

First attempt

The key to reference counting is to have a “value” type, like the shared_ptr in C++, that can be cloned and passed between functions at will. Internally this value type must have access to a shared chunk of memory that contains the reference count. In shared_ptr this chunk is a separately allocated integral type–the counter. The important thing is that all clones of the same resource share the same counter. The counter’s value reflects how many clones there are. Copy constructors and assignment operators take care of keeping the count exact. When the count goes to zero, that is the last copy of the resource goes out of scope, the resource is automatically freed (for instance, by calling CloseHandle).

In my first attempt, I decided that the memory allocated for the counter should be garbage-collected. After all, the important thing is to release the handle–the memory will take care of itself.

struct RcHandle {
   shared Counter _counter; // GC'd shared Counter object
   HANDLE _h;
   ~this() { // destructor
      if (_counter.dec() == 0) // access the counter
         CloseHandle(_h);
   }
   // methods that keep the counter up to date
}

RcHandle is a struct, which is a value type in D. Counter is a class, which is a reference type; so _counter really hides a pointer to shared memory.

A few tests later I got a nasty surprise. My program faulted while trying to access an already deallocated counter. How did that happen? How could garbage collector deallocate my counter if I still had a reference to it?

Here’s what I did in my test: I embedded the ref-counted handle inside another garbage-collected object:

class Embedder { // GC'd class object
   RcHandle _rc;
}

When the time came to collect that object (which happened after the program ran to completion), its finalizer was called. Whenever an object contains fields that have non-trivial destructors, the compiler generates a finalizer that calls the destructors of those embedded objects–_rc in this case. The destructor of the ref-counted handle checks the reference count stored in the counter. Unfortunately the counter didn’t exist anymore. Hours of debugging later I had the answer.

What happened is that the garbage collector had two objects on its list: the embedder and the counter. It just so happened that the collector decided to collect those two objects in reverse order: the counter first, then the embedding object. So, by the time it got to the finalizer of the embedding object, the counter was gone!

What I discovered (with the help of other members of the D team who were involved in the discussion) was that there are some limitations on mixing garbage collection with deterministic destruction. There is a general rule:

An object’s destructor must not access any garbage-collected objects embedded in it.

Since the destructor of the ref-counted handle must have access to the counter, the counter must not be garbage-collectible. That means only one thing: it has to be allocated using malloc and explicitly deallocated using free. Which brings us to the second problem.

Concurrency

What can be simpler than an atomic reference count? On most processors you can atomically increment and decrement a memory location. You can even decrement and test the value in one uninterruptible operation. Problem solved! Or is it?

There is one tiny complication–the location that you are atomically modifying might disappear. I know, this is totally counter-intuitive. After all the management of the counter follows the simple rule: the last to leave the room turns off the light. If the destructor of RcHandle sees the reference count going from one to zero, it knows that no other RcHandle has access it, and it can safely free the counter. Who can argue with cold logic?

Here’s the troubling scenario: RcHandle is embedded in an object that is visible from two threads:

class Embedder {
   RcHandle _rcH;
}
shared Embedder emb;

Thread 1 tries to overwrite the handle:

RcHandle myHandle1;
emb._rcH = myHandle1;

while Thread 2 tries to copy the same handle to a local variable:

RcHandle myHandle2 = emb._rcH;

Consider the following interleaving:

T2: Load the address of the _counter embedded in _rcH.
T1: Swap emb._rcH with myHandle
T1: Decrement the counter that was embedded in _rcH. If it’s zero (and it is, in this example), free the counter.
T2: Increment the _counter. Oops! This memory location has just been freed.

The snag is that there is a window between T2 reading the pointer in (1), and incrementing the location it’s pointing to in (4). Within that window, the reference count does not match the actual number of clients having access to the pointer. If T1 happens to do its ugly deed of freeing the counter within that window, the race may turn out deadly. (This problem has been known for some time and there were various proposals to fix it, for instance using DCAS, as in this paper on Lock-Free Reference Counting.)

Should we worry? After all the C++ shared_ptr also exposes this race and nobody is crying havoc. It turns out that it all boils down to the responsibilities of the shared object (and I’m grateful to Andrei for pointing it out).

A shared object should not willy-nilly expose its implementation to clients

If the clients of Embedder want access to the handle, they should call a synchronized method. Here’s the correct, race-free implementation of the Embedder in the scenario I just described.

class Embedder {
private:
   RcHandle _rcH;
public:
   synchronized RcHandle GetHandle() const { return _rcH; }
   synchronized void SetHandle(RcHandle h) { _rcH = h; }
   ...
}

The method GetHandle copies _rcH and increments its count under the Embedder’s lock. Another thread calling SetHandle has no chance of interleaving with that action, because it is forced to use the same lock. D2 actually enforces this kind of protection for shared objects, so my original example wouldn’t even compile.

You might be thinking right now that all this is baloney because I’m trying to fit a square peg into a round hole. I’m imposing value semantics on a non-atomic object, and you cannot atomically overwrite a non-atomic object. However, using this logic, you could convince yourself that a double cannot have value semantics (on most common architectures doubles are too large to be atomic). And yet you can safely pass doubles between threads and assign them to each other (which is the same as overwriting). It’s only when you embed a double inside a shared object, you have to protect it from concurrent access. And it’s not the double protecting itself–it’s the shared embedder that is responsible for synchronization. It’s exactly the same with RcHandle.

Conclusions

Just when you thought you knew everything about reference counting you discover something you haven’t though about. The take-home message is that mixing garbage collection with deterministic destruction is not a trivial matter, and that a race-free reference-counted object is vulnerable to races when embedded it in another shared object. Something to keep in mind when programming in D or in C++.

Graphs

2009-08-18T00:26:33+00:00

It's been exactly 3 months since the last post. I spent the last months writing my thesis document (in Spanish), working, and being unproductive because of the lack of inspiration =)

But in the last couple of days I decided to go back to the code, and finish the statistics gathering in the Naive GC (the new code is not published yet because it needs some polishing). Here are some nice graphs from my little D GC benchmark:

The graphs shows the space and time costs for each collection in the programs life. The collection time is divided in the time spent in the malloc() that triggered the collection, the time spent in the collection itself, and the time the world has to be stopped (meaning the time all the threads were paused because of the collection). The space is measured before and after the collection, and the total memory consumed by the program is divided in 4 areas: used space, free space, wasted space (space that the user can't use but it's not used by the collector either) and overhead (space used by the collector itself).

As you can see, the naive collector pretty much sucks, specially for periods of lots of allocation (since it just allocated what it's asked in the gc_malloc() call if the collection failed).

The next step is to modify the Tango's Basic collector to gather the same data and see how things are going with it.

Updates and links

2009-08-15T21:25:16+00:00

"Boostbench", a benchmark, in C, Java and D, the zip contains all the code, timings and information:
http://www.fantascienza.net/leonardo/js/boostbench.zip
Original code by Rene Grothmann:
http://mathsrv.ku-eichstaett.de/MGF/homes/grothmann/java/bench/

With the LDC compiler the performance is poor without Link-Time Optimization plus Interning, I don't know why. (If someone is able to tell me I'll be interested to know.)

-------------------

Theo Jansen demonstrates the amazingly lifelike kinetic sculptures he builds from plastic tubes and lemonade bottles, and then lets walk and live on a beach. They have even a brain made of bottles. Windosaurs, etc:
http://www.youtube.com/watch?v=b694exl_oZo

Jarvis March in D

2009-08-14T13:17:35+00:00

Robert C. Martin in his blog has written an implementation of the Jarvis March algorithm in Clojure, and was looking for ways to speed up the code:
http://blog.objectmentor.com/articles/2009/08/11/jarvis-march-in-clojure

See also:
http://www.butunclebob.com/ArticleS.UncleBob.ConvexHullTiming

So I have translated the Java code to D (and later C), and then I have done some timing tests.

The Java results are quite good compared to the D ones.

Number of points in the hull in all tests is just 14.

Timings, n = 2_000_000:

On Windows XP, best of 6, seconds:
  D 1:    1.88 (DMD compiler)
  Java 1: 1.83
  C 2:    1.55 (GCC compiler)
  Java 2: 1.55
  Java 1: 1.47 (-server)
  Java 2: 1.47 (-server -Xms40M)
  C 2:    1.46 (LLVM-GCC compiler)
  Java 2: 1.45 (-server)
  D 2:    1.32 (DMD compiler)

On Pubuntu, best of 6, seconds:
  Java 1: 2.71
  C 2:    2.59 (GCC compiler)
  Java 1: 2.42 (-server)
  Java 2: 2.39
  Java 2: 2.37 (-server)
  D 1:    2.06 (LDC compiler)
  D 1:    2.06 (LDC compiler, LTO+I)
  D 2:    2.02 (LDC compiler, LTO+I)  
  D 2:    2.00 (LDC compiler)

Notes:
- The code of the D 1 version is similar to the Java 1 version. The code of the D 2 version is similar to the Java 2 version and C 2 version.
- On Pubuntu all timings are increased because it has a slower access to memory.
- I have used a (low quality) portable rnd generator to assure equal test cases on all compilers and operating systems. (And because while the D std library Tango has a gaussian generator, the Phobos std lib of Dv.1 doesn't have it).
- Currently the seed of the random generator can't be changed.
- All the programs give the same output, but the results aren't equal up to the last floating point digits anyway because different FP instructions produce sligtly different results. FP numbers are approximations.
- The C code is slower, I don't know why.
- The D 2 code is much faster than D 1 with DMD because DMD has limited inlining capabilities (this is why I have created the D 2 version).
- In the D code the abs function is not taken from Tango because LDC has a performance bug, and otherwise it's not able to inline it.
- For the LTO+I see below.

More info and all the code can be found here:
http://www.fantascienza.net/leonardo/js/jarvism.zip

http://leonardo-m.livejournal.com/86620.html 2009-08-11T18:10:41+00:00 I have improved the code of the Sphereflake raytracer and thanks to Tomas Lindquist Olsen I have fixed my LDC installation, so there I have redone the benchmarks on Pubuntu:

Timings on Pubuntu, w=h=1024, lvl=6, best of 3, seconds:
(66_430 spheres, WITH_SHADOWS=true, FASTER_LDC=true)
  D:    4.33  (claiming 4.6 MB) (first fast version + LTO+I)
  D:    4.51  (claiming 2.5 MB) (second fast version + LTO+I)
  D:    4.55  (claiming 4.6 MB) (basic version + LTO+I)
  D:    4.70  (claiming 2.5 MB) (second fast version)
  D:    4.72  (claiming 4.6 MB) (first fast version)
  D:    4.97  (claiming 4.6 MB) (basic version)
  C++:  5.04  (claiming 4.6 MB) (+4 bytes padding)
  C++:  5.75  (claiming 4.3 MB) (original version)

Timings on Pubuntu, w=h=1024, lvl=7, best of 3, seconds:
(597_871 spheres, WITH_SHADOWS=true, FASTER_LDC=true)
  D:    5.51  (claiming 23 MB) (second fast version + LTO+I)
  D:    5.74  (claiming 41 MB) (first fast version + LTO+I)

Timings on Pubuntu, w=h=1024, lvl=8, best of 3, seconds:
  D:   10.84  (claiming 205 MB) (second fast version + LTO+I)
  D:   11.21  (claiming 205 MB) (second fast version)
  D:   23.34  (claiming 369 MB) (first fast version + LTO+I)
  D:   23.84  (claiming 369 MB) (basic version + LTO+I)
  D:   24.06  (claiming 369 MB) (first fast version)
  D:   24.55  (claiming 369 MB) (basic version)
  C++: 24.61  (claiming 369 MB) (+4 bytes padding)

For more information, and for the updated Sphereflake code:
http://www.fantascienza.net/leonardo/js/index.html#flake

----------------

I have added a new benchmark, a sparse matrix multiplication, this time the performance of D code (with LDC) isn't much good. Info and timings inside the zip:
http://www.fantascienza.net/leonardo/js/index.html#jaspa leonardo maffi http://leonardo-m.livejournal.com/ leonardo</h1> <p>2009-08-11T18:10:41+00:00</p> I have improved the code of the Sphereflake raytracer and thanks to Tomas Lindquist Olsen I have fixed my LDC installation, so there I have redone the benchmarks on Pubuntu:<br /><pre> Timings on Pubuntu, w=h=1024, lvl=6, best of 3, seconds: (66_430 spheres, WITH_SHADOWS=true, FASTER_LDC=true) D: 4.33 (claiming 4.6 MB) (first fast version + LTO+I) D: 4.51 (claiming 2.5 MB) (second fast version + LTO+I) D: 4.55 (claiming 4.6 MB) (basic version + LTO+I) D: 4.70 (claiming 2.5 MB) (second fast version) D: 4.72 (claiming 4.6 MB) (first fast version) D: 4.97 (claiming 4.6 MB) (basic version) C++: 5.04 (claiming 4.6 MB) (+4 bytes padding) C++: 5.75 (claiming 4.3 MB) (original version) Timings on Pubuntu, w=h=1024, lvl=7, best of 3, seconds: (597_871 spheres, WITH_SHADOWS=true, FASTER_LDC=true) D: 5.51 (claiming 23 MB) (second fast version + LTO+I) D: 5.74 (claiming 41 MB) (first fast version + LTO+I) Timings on Pubuntu, w=h=1024, lvl=8, best of 3, seconds: D: 10.84 (claiming 205 MB) (second fast version + LTO+I) D: 11.21 (claiming 205 MB) (second fast version) D: 23.34 (claiming 369 MB) (first fast version + LTO+I) D: 23.84 (claiming 369 MB) (basic version + LTO+I) D: 24.06 (claiming 369 MB) (first fast version) D: 24.55 (claiming 369 MB) (basic version) C++: 24.61 (claiming 369 MB) (+4 bytes padding) </pre><br />For more information, and for the updated Sphereflake code:<br /><a href="http://www.fantascienza.net/leonardo/js/index.html#flake">http://www.fantascienza.net/leonardo/js/index.html#flake</a><br /><br />----------------<br /><br />I have added a new benchmark, a sparse matrix multiplication, this time the performance of D code (with LDC) isn't much good. Info and timings inside the zip:<br /><a href="http://www.fantascienza.net/leonardo/js/index.html#jaspa">http://www.fantascienza.net/leonardo/js/index.html#jaspa</a> </article> <article> <h1>Sphereflake ray-tracing benchmark in C++ and D</h1> <p>2009-08-05T15:33:32+00:00</p> Timings of a small ray-tracing "Spereflake" benchmark (you can find a copy of this Html page in the references directory of the zip too):<br /><a href="http://ompf.org/ray/sphereflake/">http://ompf.org/ray/sphereflake/</a><br /><br /><center></center><br /><br />The D-LDC results of this benchmark are good. I have also created a faster D version where the output is now in P5 pgm format (bytes are represented as single chars, this speeds up the output) and where the trascendental values are precomputed (G++ 4.3.3 is able to pre-compute them, while the current LDC isn't able to).<br /><br />A possible way to further speed up the code: when lvl=8 it creates 5_380_840 visible spheres and node_t, but it needs only 597_871 bounding spheres (the leaves don't need such bounding spheres and most of the nodes of a tree are leaves).<br /><br />So it may be useful to split the array of node_t into two arrays, one much larger that just contains the visible spheres and the skip pointer, and one smaller that contains the bounding spheres (and maybe another skip pointer). In the end the CPU cache has to manage two arrays, so the program may be slower.<br /><br />With that idea with lvl=8 the memory used becomes 205 MB (or 228 MB if doubles are aligned to 8 bytes) instead of the current 369 MB, this lowers the CPU cache traffic.<br /><br />I have 2 GB RAM on my PC, so I can't run it with lvl=9. But removing just visible sphere radiuses it needs less than 2 GB RAM:<br />( 48427561 * (8 + 3 * 8) + 5380840 * (8 + 4 * 8) ) / (1024*1024) = 1683.15<br /><pre> Timings on Windows, w=h=1024, lvl=6, best of 3, seconds: C++: 4.60 (claiming 4.6 MB) (+4 bytes padding) C++: 4.60 (claiming 4.6 MB) C++: 4.63 (claiming 4.6 MB) (+4 bytes padding, LLVM-G++) C++: 4.64 (claiming 4.6 MB) (LLVM-G++) C++: 4.68 (claiming 4.6 MB) (+4 bytes padding, PGO) D: 11.78 (claiming 4.6 MB) (DMD v1.043, with "ref", fast version) D: 17.34 (claiming 4.6 MB) (DMD v1.043, with "ref") D: 17.34 (claiming 4.6 MB) (DMD v1.043, with "ref", no GC) D: 28.24 (claiming 4.6 MB) (DMD v2.031, with no "ref") D: 28.27 (claiming 4.6 MB) (DMD v2.031, with no "ref", gs) D: 29.78 (claiming 4.6 MB) (DMD v1.043, with no "ref") D: 29.79 (claiming 4.6 MB) (DMD v1.046, with no "ref") (Those DMD-Windows timings are not reliable, I have timed it as low ad 12.5 seconds) Timings on Pubuntu, w=h=1024, lvl=6, best of 3, seconds: (66_430 spheres, WITH_SHADOWS=true, FASTER_LDC=true) D: 4.81 (claiming 4.6 MB) (with fast output) C++: 4.86 (claiming 4.6 MB) (+4 bytes padding) D: 4.91 (claiming 4.6 MB) (fast version) D: 4.93 (claiming 4.6 MB) C++: 5.75 (claiming 4.3 MB) Timings on Pubuntu, w=h=1024, lvl=8, best of 3, seconds: (5_380_840 spheres) C++: 25.00 (claiming 369 MB) (+4 bytes padding) D: 25.27 (claiming 369 MB) (fast version) D: 25.62 (claiming 369 MB) (with "ref") </pre><br />Key:<br /> no GC = Garbage collector disabled in the whole running<br /> +4 bytes padding = 4 bytes of padding added to the Node struct<br /> PGO = profile-guided optimization<br /> gs = all global variables are annotated with __gshared<br /><br />Args:<br /> g++ -O3 -s -fomit-frame-pointer -msse3 -march=native -ffast-math<br /> llvm-g++ -O3 -s -fomit-frame-pointer -msse3 -march=native -ffast-math<br /> dmd -O -release -inline<br /> ldc -O5 -release -inline<br /> <br /><br />All the tested code:<br /><a href="http://www.fantascienza.net/leonardo/js/sphereflake.zip">http://www.fantascienza.net/leonardo/js/sphereflake.zip</a> </article> <article> <h1>A small raytracing benchmark</h1> <p>2009-08-05T14:38:44+00:00</p> To test the LDC D compiler, its LLVM backend and to look for more possible optimizations, I have translated to D a small ray tracing benchmark present on Jon Harrop site:<br /><a href="http://www.ffconsultancy.com/languages/ray_tracer/benchmark.html">http://www.ffconsultancy.com/languages/ray_tracer/benchmark.html</a><br /><br />It contains translations in several languages of progressively more optimized versions of a toy ray tracer program. As reference I have used the first C++ implementation, the slowest one hoping it can show me where LDC misses some possible optimizations (if I translate to D1 the faster C++ version I may offer less chances to LDC and G++ compilers to show their optimization capabilities).<br /><br />To translate the code to D I have had to change few things, so to have a more fair comparison I have back-ported those changes to C++.<br /><br />The two main changes I have performed to the first C++ version are:<br />1) vector is used instead of list. This speeds up the code a little. I have done this because D has no built-in list type (there are lists in Phobos2 and Tango that I have not used).<br /><br />2) Inside the Group class "bound" is a Sphere* instead of a Sphere, because in D classes are used by reference only. This has slowed down code. So I have created a "ray1_scoped_cpp" C++ version that keeps "bound" as a value. It shows where D misses a possible optimization. Some people have asked for a 'scope' among class attributes, but the discussion is gone nowhere (I think Walter has never answered). But in some situations LDC is recently able to 'scope' classes by itself, as an optimization. So can LDC perform such optimization anyway, with no change to the language, as a way to optimize? It's not a very quick to do, you have to see if no references to the class "f" in this class escape. It may be doable.<br /><pre>Timings on Windows: ray1_scoped_cpp 6.52 ray1_cpp 6.77 ray1_d 16.01 (DMD v1.043) Timings on Pubuntu: ray1_scoped_cpp 7.99 ray1_d 8.51 (LDC Aug 3 2009) ray1_cpp 8.66 </pre>CPU used: Core2 at 2 GHz.<br /><br />Compilers:<br />LDC LLVM D Compiler based on DMD v1.045 and llvm 2.6svn (Mon Aug 3 22:09:36 2009)<br />On Pubuntu G++ version 4.2.4 (Ubuntu 4.2.4-1ubuntu4)<br />DMD v1.042<br />On Windows gcc version 4.3.3-dw2-tdm-1 (GCC)<br /><br />Compilation arguments:<br />Windows:<br />llvm-g++ -Wall -O3 -s -fomit-frame-pointer -msse3 -march=native ray1d_cpp.cpp -o ray1d_cpp<br /><br />Ubuntu:<br />g++ -Wall -O3 -s -fomit-frame-pointer -msse3 -march=native ray1d_cpp.cpp -o ray1d_cpp<br /><br />All the D and C++ code tested here:<br /><a href="http://www.fantascienza.net/leonardo/js/ray.zip">http://www.fantascienza.net/leonardo/js/ray.zip</a><br /><br />In future I may add a D translation of the 5th (the fastest) C++ version too, as reference point. </article> <article> <h1>Update and links</h1> <p>2009-07-29T11:00:26+00:00</p> A small benchmark, computing digits of Pi, compared D, C++, Java:<br /><a href="http://www.fantascienza.net/leonardo/js/pi_bench.zip">http://www.fantascienza.net/leonardo/js/pi_bench.zip</a><br /><br />------------------------<br /><br />Case study: Improving the performance of matrix multiplication by 296,260x<br /><a href="http://stellar.mit.edu/S/course/6/fa08/6.197/courseMaterial/topics/topic2/lectureNotes/Intro_and_MxM/Intro_and_MxM.pdf">http://stellar.mit.edu/S/course/6/fa08/6.197/courseMaterial/topics/topic2/lectureNotes/Intro_and_MxM/Intro_and_MxM.pdf</a><br /><a href="http://stellar.mit.edu/S/course/6/fa08/6.197/">http://stellar.mit.edu/S/course/6/fa08/6.197/</a><br /><br /><br />What's the fastest programming language? It may be Python, because there are CorePy and PyCuda that allow you to write very fast programs:<br /><a href="http://www.corepy.org/">http://www.corepy.org/</a><br /><a href="http://mathema.tician.de/software/pycuda">http://mathema.tician.de/software/pycuda</a><br /><br /><br />One of the best biology blogs I have found so far:<br /><a href="http://bytesizebio.net/">http://bytesizebio.net/</a><br /><br /><br />Sig.ma - Live views on the Web of Data (a demo video):<br /><a href="http://vimeo.com/5703809">http://vimeo.com/5703809</a><br /><br /><br />Lot of people know Java-style Object Oriented programming, while knowledge of pure mathematics is much less common (even if knowing some group theory, etc, can be quite useful. Such topics are part of courses at the university if you want a degree in computer science). Marc Conrad has shown ways to explain some of those mathematics ideas using the OOP ideas. It may be a good idea:<br /><a href="http://ring.perisic.com/">http://ring.perisic.com/</a> </article> <article> <h1>Linpack benchmark in D</h1> <p>2009-07-20T11:32:55+00:00</p> I have translated a C Linpack benchmark to D, and I have timed it compared to the C and a similar Java version.<br /><br />Some of the D Link-Time optimized (+ interning) versions segfault (binaries produced by DMD here never segfault). The C code compiled with GCC with -msse3 -march=core2 compilation arguments too segfaults (that's why I have used llvm-gcc that has never produced a segfault), I don't know why, it may be a pointer aliasing problem.<br /><br />For bigger matrices Java shows to be about as fast as gcc-C and LDC-D. Both float and real versions are very slow. Static arrays are a bit faster with LDC but not much, I don't know why.<br /><br />See inside the zip for the full timings:<br /><a href="http://www.fantascienza.net/leonardo/js/linpack.zip">http://www.fantascienza.net/leonardo/js/linpack.zip</a> </article> <article> <h1>Review of The Case For D</h1> <p>2009-07-18T10:56:09+00:00</p> Andy Glew attended Andrei’s The Case for D presentation and has posted his reactions on his blog.<div class="feedflare"> <a href="http://feeds.feedburner.com/~ff/TheOneWithD?a=GC6pdUHaYwc:XsRzrK5geUk:yIl2AUoC8zA"></a> <a href="http://feeds.feedburner.com/~ff/TheOneWithD?a=GC6pdUHaYwc:XsRzrK5geUk:F7zBnMyn0Lo"></a> <a href="http://feeds.feedburner.com/~ff/TheOneWithD?a=GC6pdUHaYwc:XsRzrK5geUk:cGdyc7Q-1BI"></a> </div> </article> <article> <h1>Updates</h1> <p>2009-07-17T00:52:16+00:00</p> Updated the rectangle packing code: added a D and ShedSkin version of the first algorithm:<br /><a href="http://www.fantascienza.net/leonardo/so/index.html#rectpack">http://www.fantascienza.net/leonardo/so/index.html#rectpack</a><br /><br /><br />Added a D version (fvd) of the fv tool shown here, the D version compiled with LDC is a bit faster than the C++ version (probably thanks to unlocked_get/set that can also be used in C++):<br /><a href="http://www.fantascienza.net/leonardo/ar/string_repetition_statistics/string_repetition_statistics.html">http://www.fantascienza.net/leonardo/ar/string_repetition_statistics/string_repetition_statistics.html</a> </article> <article> <h1>Bartosz Milewski</h1> <p>2009-07-16T18:28:01+00:00</p> <div class="snap_preview"><br /><p>Is the Actor model just another name for message passing between threads? In other words, can you consider a Java <var>Thread</var> object with a message queue an Actor? Or is there more to the Actor model? Bartosz investigates. </p> <p>I’ll start with listing various properties that define the Actor Model. I will discuss implementation options in several languages.</p> <h2>Concurrency</h2> <p><b>Actors are objects that execute concurrently.</b> Well, sort of. Erlang, for instance, is not an object-oriented language, so we can’t really talk about “objects”. An actor in Erlang is represented by a thing called a Process ID (Pid). But that’s nitpicking. The second part of the statement is more interesting. Strictly speaking, an actor may execute concurrently but at times it will not. For instance, in Scala, actor code may be executed by the calling thread. </p> <p>Caveats aside, it’s convenient to think of actors as objects with a thread inside.</p> <h2>Message Passing</h2> <p><b>Actors communicate through message passing.</b> Actors don’t communicate using shared memory (or at least pretend not to). The only way data may be passed between actors is through messages. </p> <p>Erlang has a primitive send operation denoted by the exclamation mark. To send a message <var>Msg</var> to the process (actor) <var>Pid</var> you write:</p> <pre>Pid ! Msg</pre> <p>The message is copied to the address space of the receiver, so there is no sharing. </p> <p>If you were to imitate this mechanism in Java, you would create a <var>Thread</var> object with a mailbox (a concurrent message queue), with no public methods other than <var>put</var> and <var>get</var> for passing messages. Enforcing copy semantics in Java is impossible so, strictly speaking, mailboxes should only store built-in types. Note that passing a Java <var>String</var>s is okay, since strings are immutable. </p> <h3>-Typed messages</h3> <p>Here’s the first conundrum: in Java, as in any statically typed language, messages have to be typed. If you want to process more than one type of messages, it’s not enough to have just one mailbox per actor. In Erlang, which is dynamically typed, one canonical mailbox per actor suffices. In Java, mailboxes have to be abstracted from actors. So an actor may have one mailbox for accepting strings, another for integers, etc. You build actors from those smaller blocks.</p> <p>But having multiple mailboxes creates another problem: How to block, waiting for messages from more than one mailbox at a time without breaking the encapsulation? And when one of the mailboxes fires, how to retrieve the correct type of a message from the appropriate mailbox? I’ll describe a few approaches.</p> <h3>-Pattern matching</h3> <p>Scala, which is also a statically typed language, uses the power of functional programming to to solve the typed messages problem. The <var>receive</var> statement uses pattern matching, which can match different types. It looks like a switch statements whose <var>case</var> labels are patterns. A pattern may specify the type it expects. You may send a string, or an integer, or a more complex data structure to an actor. A single <var>receive</var> statement inside the actor code may match any of those.</p> <pre>receive { case s: String => println("string: "+ s) case i: Int => println("integer: "+ i) case m => println("unknown: "+ m) }</pre> <p>In Scala the type of a variable is specified after the colon, so <var>s:String</var> declares the variable <var>s</var> of the type <var>String</var>. The last case is a catch-all.</p> <p>This is a very elegant solution to a difficult problem of marrying object-oriented programming to functional programming–a task at which Scala exceeds. </p> <h3>-Casting</h3> <p>Of course, we always have the option of escaping the type system. A mailbox could be just a queue of <var>Object</var>s. When a message is received, the actor could try casting it to each of the expected types in turn or use reflection to find out the type of the message. Here’s what Martin Odersky, the creator of Scala, has to say about it:</p> <blockquote><p>The most direct (some would say: crudest) form of decomposition uses the type-test and type-cast instructions available in Java and many other languages.</p></blockquote> <p>In the paper he co-authored with Emir and Williams (<a href="http://lampwww.epfl.ch/~emir/written/MatchingObjectsWithPatterns-TR.pdf">Matching Objects With Patterns</a>) he gives the following evaluation of this method:</p> <blockquote><p>Evaluation: Type-tests and type-casts require zero overhead for the class hierarchy. The pattern matching itself is very verbose, for both shallow and deep patterns. In particular, every match appears as both a type-test and a subsequent type-cast. The scheme raises also the issue that type-casts are potentially unsafe because they can raise ClassCastExceptions. Type-tests and type-casts completely expose representation. They have mixed characteristics with respect to extensibility. On the one hand, one can add new variants without changing the framework (because there is nothing to be done in the framework itself). On the other hand, one cannot invent new patterns over existing variants that use the same syntax as the type-tests and type-casts. </p></blockquote> <p>The best one could do in C++ or D is to write generic code that hides casting from the client. Such generic code could use <i>continuations</i> to process messages after they’ve been cast. A continuation is a function that you pass to another function to be executed after that function completes (strictly speaking, a real continuation never returns, so I’m using this word loosely). The above example could be rewritten in C++ as:</p> <pre>void onString(std::string const & s) { cout << "string: " << s << std::endl; } void onInt(int i) { cout << "integer: " << i << std::endl; } receive<std::string, int> (&onString, &onInt);</pre> <p>where <var>receive</var> is a variadic template (available in C++0x). It would do the dynamic casting and call the appropriate function to process the result. The syntax is awkward and less flexible than that of Scala, but it works. </p> <p>The use of lambdas might make things a bit clearer. Here’s an example in D using lambdas (function literals), courtesy Sean Kelly and Jason House:</p> <pre>receive( (string s){ writefln("string: %s", s); }, (int i){ writefln("integer: %s", i); } );</pre> <p>Interestingly enough, Scala’s <var>receive</var> is a library function with the pattern matching block playing the role of a continuation. Scala has syntactic sugar to make lambdas look like curly-braced blocks of code. Actually, each case statement is interpreted by Scala as a <i>partial function</i>–a function that is not defined for all values (or types) of arguments. The pattern matching part of <var>case</var> becomes the <var>isDefinedAt</var> method of this partial function object, and the code after that becomes its <var>apply</var> method. Of course, partial functions could also be implemented in C++ or D, but with a lot of superfluous awkwardness–lambda notation doesn’t help when partial functions are involved.</p> <h3>-Isolation</h3> <p>Finally, there is the problem of <b>isolation</b>. A message-passing system must be protected from data sharing. As long as the message is a primitive type and is passed by value (or an immutable type passed by reference), there’s no problem. But when you pass a mutable <var>Object</var> as a message, in reality you are passing a reference (a handle) to it. Suddenly your message is shared and may be accessed by more than one thread at a time. You either need additional synchronization outside of the Actor model or risk data races. Languages that are not strictly functional, including Scala, have to deal with this problem. They usually pass this responsibility, conveniently, to the programmer.</p> <h3>-Kilim</h3> <p>Java is not a good language to implement the Actor model. You can extend Java though, and there is one such extension worth mentioning called <a href="http://www.malhar.net/sriram/kilim/kilim_ecoop08.pdf">Kilim</a> by Sriram Srinivasan and Alan Mycroft from Cambridge, UK. Messages in Kilim are restricted to objects with no internal aliasing, which have move semantics. The pre-processor (weaver) checks the structure of messages and generates appropriate Java code for passing them around. I tried to figure out how Kilim deals with waiting on multiple mailboxes, but there isn’t enough documentation available on the Web. The authors mention using the <var>select</var> statement, but never provide any details or examples.</p> <p><i>Correction: Sriram was kind enough to provide an example of the use of <var>select</var>:</i></p> <pre>int n = Mailbox.select(mb0, mb1, .., timeout);</pre> <p><i>The return value is the index of the mailbox, or -1 for the timeout. Composability is an important feature of the message passing model.</i></p> <h2>Dynamic Networks</h2> <p>Everything I described so far is common to CSP (Communicating Sequential Processes) and the Actor model. Here’s what makes actors more general:</p> <p><b>Connections between actors are dynamic.</b> Unlike processes in CSP, actors may establish communication channels dynamically. They may pass messages containing references to actors (or mailboxes). They can then send messages to those actors. Here’s a Scala example:</p> <pre>receive { case (name: String, actor: Actor) => actor ! lookup(name) }</pre> <p>The original message is a tuple combining a string and an actor object. The receiver sends the result of <var>lookup(name)</var> to the actor it has just learned about. Thus a new communication channel between the receiver and the unknown actor can be established at runtime. (In Kilim the same is possible by passing mailboxes via messages.)</p> <h2>Actors in D</h2> <p>The D programming language with <a href="http://bartoszmilewski.wordpress.com/2009/05/26/race-free-multithreading/">my proposed race-free type system</a> could dramatically improve the safety of message passing. Race-free type system distinguishes between various types of sharing and enforces synchronization when necessary. For instance, since an <var>Actor</var> would be shared between threads, it would have to be declared <var>shared</var>. All objects inside a shared actor, including the mailbox, would automatically inherit the shared property. A shared message queue inside the mailbox could only store value types, <var>unique</var> types with move semantics, or reference types that are either immutable or are monitors (provide their own synchronization). These are exactly the types of messages that may be safely passed between actors. Notice that this is more than is allowed in Erlang (value types only) or Kilim (unique types only), but doesn’t include “dangerous” types that even Scala accepts (not to mention Java or C++). </p> <p>I will discuss message queues in the next installment.</p> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/gocomments/bartoszmilewski.wordpress.com/935/"></a> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/godelicious/bartoszmilewski.wordpress.com/935/"></a> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/gostumble/bartoszmilewski.wordpress.com/935/"></a> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/godigg/bartoszmilewski.wordpress.com/935/"></a> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/goreddit/bartoszmilewski.wordpress.com/935/"></a> </div> </article> <article> <h1>Rectangle packing</h1> <p>2009-07-15T00:01:26+00:00</p> Efficient packing of many rectangles inside a bigger one:<br /><br /><a href="http://www.fantascienza.net/leonardo/so/index.html#rectpack">http://www.fantascienza.net/leonardo/so/index.html#rectpack</a><br /><br />Improved from this C# code:<br /><a href="http://kossovsky.net/index.php/2009/07/cshar-rectangle-packing/">http://kossovsky.net/index.php/2009/07/cshar-rectangle-packing/</a><br /><a href="https://devel.nuclex.org/framework/browser/game/Nuclex.Game/trunk/Source/Packing">https://devel.nuclex.org/framework/browser/game/Nuclex.Game/trunk/Source/Packing</a> </article> <article> <h1>DMD 1.046 & 2.031</h1> <p>2009-07-12T10:43:03+00:00</p> I crawled out from under my rock to discover that Walter has released new versions of the D1 and D2 compilers, 1.046 and 2.031 respectively. Both releases include a laundry list of bug fixes and a patch to the front in from Tomasz Stachowiak that allows DMD to put out a detailed set of dependencies, [...]<div class="feedflare"> <a href="http://feeds.feedburner.com/~ff/TheOneWithD?a=zVAhX0_g6sk:zrlZie3qpLQ:yIl2AUoC8zA"></a> <a href="http://feeds.feedburner.com/~ff/TheOneWithD?a=zVAhX0_g6sk:zrlZie3qpLQ:F7zBnMyn0Lo"></a> <a href="http://feeds.feedburner.com/~ff/TheOneWithD?a=zVAhX0_g6sk:zrlZie3qpLQ:cGdyc7Q-1BI"></a> </div> </article> <article> <h1>Current plans...</h1> <p>2009-07-09T12:37:31+00:00</p> No decent internet connection until the 20th.<br /><br />I've been thinking of hooking ArcLib up to the minid scripting language to provide rapid prototyping of games.<br /><br />Some more extensions I plan on to help provide the rapid development of games as well.<br /><br />arc_actors - keep track of actors in game<br /><br />arc_menu - in game menu capability<br /><br />arc_credits - end credits capability<br /><br />arc_hud - in game hud capability<br /><br />arc_tilemap - bird eye tilemap<br /><br />arc_scrolling- scrolling tilemap<br /><br /><br />Some other tools in consideration...<br /><br />Map Editor<br /><br />Sprite Editor<br /><br />Tools to facilitate rapid game development plans are the current future.<div class="blogger-post-footer"></div> </article> <article> <h1>Bartosz Milewski</h1> <p>2009-07-07T22:37:55+00:00</p> <div class="snap_preview"><br /><p>I started writing a post about implementing actors in D when I realized that there was something wrong with the way thread spawning interacts with data sharing. Currently D’s <var>Thread</var> class closely mimics its Java counterpart, so I started wondering if this may be a more general problem–a problem with mixing object-oriented paradigm with multithreading.</p> <p>In functional languages like Erlang or Concurrent ML, you start a thread by calling a function–<var>spawn</var> or <var>create</var>, respectively. The argument to this function is another function–the one to be executed in a new thread. If you think of a new thread as a semi-separate application, the thread function is its “main”. You may also pass arguments to it–the equivalent of <var>argc</var>, <var>argv</var>, only more general. Those arguments are, of course, passed by value (we’re talking <i>functional</i> programming after all).</p> <p>In non-functional languages it’s possible and often desirable to <i>share</i> data between threads. It’s very important to know which variables are shared and which aren’t, because shared variables require special handling–they need synchronization. You may share global variables with a thread, or you may pass shared variables to it during thread creation. You may also provide access to more shared variables during the thread’s lifetime by attaching and detaching them from the original shared variables–that’s how message queues may be described in this language.</p> <p>In the object-oriented world everything is an object so, predictably, a (capital letter) <var>Thread</var> is an object too. An object combines data with code. There is a piece of data associated with every thread–the thread ID or a handle–and there are things you can do to a thread, like pause it, wait for its termination, etc.</p> <p>But there’s more: A <var>Thread</var> in Java has a thread function. It’s a method called <var>run</var>. The user defines his or her own thread by inheriting from <var>Thread</var> and overriding <var>run</var>. Since <var>run</var> takes no arguments, data has to be passed to the new thread by making it part of the derived thread object. In general a thread object contains two types of data: shared and non-shared. The non-shared data are the value arguments passed by the creator to the thread function, possibly some return values, plus state used internally by the thread function. Thread data may form some logical abstraction or, as it often happens, have the structure of a kitchen sink after a dinner party. </p> <p>Because of the presence of shared state, a <var>Thread</var> object must be considered shared, thus requiring synchronization. As I described in my previous posts, public methods of a shared object must either be synchronized or lock free. But what about the <var>run</var> method? It cannot be synchronized because that would make the whole thread object inaccessible to other threads, including its creator (which may be okay for a daemon thread, but wold be a fatal flaw in general). </p> <p>It makes perfect sense for <var>run</var> to be private, since nobody should call it from the outside (or, for that matter, from the inside). But the reason for private methods not requiring synchronization is that they are only called from public methods, which must be synchronized. This is not true for <var>run</var>–<var>run</var> is not called from under any lock! So essentially <var>run</var> has unfettered access to all (potentially shared) data stored in <var>this</var>. Unless the programmer is <i>very</i> disciplined, the potential for data races is high. And that’s where Java stands right now (the <var>Runnable</var> interface has the same problems).</p> <p>If you’ve been following my blog, you know that I’m working on a <a href="http://bartoszmilewski.wordpress.com/2009/05/26/race-free-multithreading/">type system that eliminates races</a>. If I can convince Walter and Andrei, this system might be implemented in the D programming language. As I mentioned, D’s treatment of threads comes directly from Java and therefore is inherently unsafe. Like in Java, D’s <var>Thread</var> object has a <var>run</var> method. </p> <p>So how could D, with the race-free type system, improve on Java? One possibility is to make the <var>run</var> method <var>lockfree</var>. A <var>lockfree</var> method (public or private) is not synchronized but its access to <var>this</var> is severely restricted. It can only operate on <var>lockfree</var> data members (if any), unless it takes the object’s lock or calls a synchronized method (all public methods of a shared object are, by default, synchronized). Let me give you a small example:</p> <pre>class Counter: Thread { public: // public methods are implicitly synchronized void inc() { ++_cnt; } void dec() { --_cnt; } private: override void run() <span>lockfree</span> { inc(); // ok: calling a synchronized method wait(10000); synchronized(this) { // ok: explicit synchronization on this _cnt = _cnt * _cnt; } // _cnt /= 2; // error: not synchronized! } int _cnt; } // usage: auto cnt = new <span>shared</span> Counter; cnt.start; cnt.inc; cnt.join;</pre> <p>This approach would work and guarantee freedom from races, but I don’t think it fits D. Unlike Java, which is so OO that even <var>main</var> is a method of an object, D is a multi-paradigm language. It doesn’t <i>have to</i> force threads into an OO paradigm. And the thread function, being a thread equivalent of <var>main</var> doesn’t <i>have to</i> be a method of any object. In my opinion, the functional approach to thread creation would serve D much better.</p> <p>Here’s how I see it:</p> <pre>class Counter { public: void inc() { ++_cnt; } void dec() { --_cnt; } int get() const { return _cnt; } void set(int cnt) { _cnt = cnt; } private: int _cnt; } void counterFun(shared Counter cnt) { cnt.inc; Thread.sleep(10000); synchronized(cnt) { int c = cnt.get; cnt.set(c * c); } } // usage: auto cnt = new shared Counter; Thread thr = Thread.spawn(&counterFun, cnt); thr.start; cnt.inc; thr.join;</pre> <p>I find it more logical to have <var>start</var> and <var>join</var> operate on a different object, <var>thr</var>, rather than on the counter, <var>cnt</var>. The static template method <var>spawn</var> accepts a function that takes an arbitrary number of arguments that are either values or shared or unique objects. In particular, you could pass to it your (shared) communication channels or message queues to implement the message-passing paradigm. </p> <p>Such <var>spawn</var> primitive could be used to build more complex classes–including the equivalents of a Java’s <var>Thread</var> or a Scala’s <var>Actor</var>. </p> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/gocomments/bartoszmilewski.wordpress.com/923/"></a> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/godelicious/bartoszmilewski.wordpress.com/923/"></a> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/gostumble/bartoszmilewski.wordpress.com/923/"></a> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/godigg/bartoszmilewski.wordpress.com/923/"></a> <a rel="nofollow" href="http://feeds.wordpress.com/1.0/goreddit/bartoszmilewski.wordpress.com/923/"></a> </div> </article> <article> <h1>Richards benchmark</h1> <p>2009-07-04T21:57:38+00:00</p> This old post of mine is about virtual methods and devirtualizations:<br /><a href="http://leonardo-m.livejournal.com/76547.html">http://leonardo-m.livejournal.com/76547.html</a><br /><br />I have performed more benchmarks about virtual methods and its costs with LDC. I have used a little well known benchmark, the Richards one. I have used the code from here (on the Web Archive because it seems to be not online anymore):<br /><a href="http://web.archive.org/web/20060715074131/lissett.port5.com/ben/bench1.htm">http://web.archive.org/web/20060715074131/lissett.port5.com/ben/bench1.htm</a><br /><a href="http://web.archive.org/web/20060715074131/http://lissett.port5.com/ben/bench3.htm">http://web.archive.org/web/20060715074131/http://lissett.port5.com/ben/bench3.htm</a><br /><br />All the code of the following benchmarks:<br /><a href="http://www.fantascienza.net/leonardo/js/richards.zip">http://www.fantascienza.net/leonardo/js/richards.zip</a><br /><pre> Timing results: Windows, n = 10_000_000: C: 1.26 D ~C: 2.01 Java: 2.04 (final classes, -server) D2 ~C#: 2.36 (final classes) D3 ~C#: 2.36 (final classes, no getters/setters) Java: 2.73 (final classes) D4 ~C#: 3.07 (no getters/setters) C#: 3.98 D1 ~C#: 4.23 Windows, n = 100_000_000: C: 12.16 Java: 18.73 (final classes, -server) D ~C: 18.86 D2 ~C#: 23.11 (final classes) D3 ~C#: 23.12 (final classes, no getters/setters) Java: 25.40 (final classes) D4 ~C#: 30.16 (no getters/setters) C#: 38.39 D1 ~C#: 41.64 Pubuntu, n = 10_000_000: D ~C: 1.35 C: 1.39 D2 ~C#: 1.98 (final classes) D3 ~C#: 2.00 (final classes, no getters/setters) Java: 2.73 (final classes) D4 ~C#: 2.94 (no getters/setters) C#: - D1 ~C#: 4.03 Pubuntu, n = 100_000_000: D ~C: 13.24 C: 13.77 D2 ~C#: 19.64 (final classes) D3 ~C#: 19.92 (final classes, no getters/setters) Java: 25.16 (final classes) D4 ~C#: 29.16 (no getters/setters) C#: - D1 ~C#: 40.17 Key: D ~C# means D code that comes from the C# version. D ~C means D code that comes and looks from the C version. </pre><br />Note that the classes in C# code aren't final. As usual Java shows very good performance.<br /><br /><br />On WindowsXp:<br />DMD Digital Mars D Compiler v1.042<br />gcc version 4.3.3-dw2-tdm-1 (GCC)<br /><br />dmd used with:<br />dmd -O -release -inline<br /><br />ldc used with:<br />ldc -O5 -release -inline<br /><br />gcc used with:<br />gcc -Wall -O3 -s -fomit-frame-pointer -msse3 -march=core2<br /><br /><br />On Pubuntu:<br />gcc version 4.2.4 (Ubuntu 4.2.4-1ubuntu4)<br />ldc based on DMD v1.045 and llvm 2.6svn (Thu Jul 2 23:07:48 2009)<br /><br />ldc used with:<br />ldc -O5 -release -inline<br /><br />gcc used with:<br />gcc -Wall -O3 -s -fomit-frame-pointer -msse3 -march=native </article> </main></body></html>