The Flying Frog Blog

The "C++ renaissance"

2012-01-15T02:58:00.000-08:00

According to Herb Sutter, C++ (and C and Fortran) are unmatched for performance per dollar and, therefore, he believes C++ will once again top the programming language charts as mobile devices make power consumption (which he equates with performance) a high priority again:

Herb said this in his recent lecture Why C++? and other Microsoft employees from the Visual C++ team have called this prophecy the "C++ Renaissance".

Similar statements about the superior performance of C++ were commonplace over 15 years ago when Java was new and unproven but we now know they were almost entirely wrong. The world migrated from native to managed languages over 10 years ago and never looked back because their performance is more than adequate. Furthermore, the implementations of managed languages have improved substantially since then and even toy benchmarks now show them competing with or even beating native code. Furthermore, the difficulty of optimizing large code bases means that many real-world applications are substantially faster when written using modern tools. For example, we recently helped a client translate 10,000 lines of numerical C++ code into F# and were easily able to make it 10× faster than the original C++. This is typical because C++ is much more difficult to optimize, particularly in the context of multicore parallelism, and developers in the real-world rarely have the time to do it if they are still using C++.

So why would anyone be promoting C++ now when it has so many disadvantages. Several reasons, we believe. Firstly, C++0x was finally released as C++11 last year and Microsoft's Visual C++ team hope to ride a wave of hype following this. Secondly, Microsoft want to draw people back into C++ as a route to vendor lock-in. We have seen several big code bases written in "C++" using Microsoft's tools and none of them were remotely portable due to the extensive use of proprietary features. Ironically, Herb tries to play to portability in his preachings and even goes so far as to assert that C++ has the advantage of offering a single string type that is compatible with the operating systems. In addition, C++ is particularly bad for metaprogramming and, consequently, it is unusually difficult to translate code mechanically from C++ to other languages. Thirdly, what else do Microsoft's Visual C++ team have left to hype?

Fortunately, this recent hype from Microsoft seems to have been largely ignored...

Here is the current trend in the UK job market for C++ developers:

Is it about to change?

EDIT

Herb Sutter responded to some of my tweets about this. His responses are remarkable.

Firstly, he states that "no way should you need barriers to get sequential consistency". This is an amazing statement because all mainstream languages (Java, .NET, C++) and all dominant CPU architectures (ARM, Intel, AMD, PowerPC) require barriers to achieve sequential consistency. This property is ubiquitous because it is required for latency hiding to work effectively. The paper "Realization And Performance Comparison Of Sequential And Weak Memory Consistency Models In Network-on-Chip Based Multi-Core Systems" found that performance is around 40% worse if sequential consistency is imposed. ARM's Principal Software Engineer even went so far as to call sequentially consistent memory models a "nostalgic fantasy".

In reality, ARM and PowerPC have weak memory models that allow many memory operations to be reordered and x86 has a stronger memory model that prohibits most reordering but still allows reads to be moved before independent writes and, consequently, is also not sequentially consistent. Note that Herb's dream of sequential consistency is at odds with the desire for more latency hiding that he expressed in his latest article.

Then he predicts that CPU vendors will adopt stronger memory models within 2 years. Perhaps Herb has inside knowledge of Microsoft leaning on ARM to adopt the x86 memory model to ease Microsoft's Windows 8 port. Only time will tell if Herb's prediction is accurate but two interesting observations can be made. Firstly, Apple have sold 10,000,000s of iPad 2's that are running the 500,000 apps on their AppStore without anyone having complained about bugs caused by the weak memory model of the multicore ARMs inside them. Secondly, Intel weakened the x86 memory model when they added SSE and, consequently, also added the LFENCE, SFENCE and MFENCE instructions. So Herb is predicting that Intel will do a U-turn and ARM will throw away one of their largest performance advantages.

Finally, Herb asserts that "x86 is the canonical example of a strong hardware memory model". Although many people can be seen asserting that the x86 has a strong memory model, many experts describe it as a weak memory model because it does reorder and does not provide sequential consistency. For example, computer science researchers in this field from the University of Cambridge describe x86 as having a weak memory model in their paper "x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors". And computer science researchers from the University of Oxford describe it as a weak memory model in their paper "Soundness of Data Flow Analyses for Weak Memory Models".

What is your garbage collector collecting?

2011-11-16T09:51:00.001-08:00

As a garbage collector runs it recycles unreachable values. A well known result in GC theory is that values tend to die in "clumps" rather than individually. This post visualizes these clumps.

We instrumented a C++ program equipped with our own mark-region collector (using 64kB regions) that is equivalent to the following F# implementation of a list-based n-queens solver in order to gather information about the structures being collected:

let safe x1 y1 x2 y2 =
  x1 <> x2 && y1 <> y2 &&
    x2 - x1 <> y2 - y1 && x1 - y2 <> x2 - y1

let ps n =
  [ for i in 1 .. n do
      for j in 1 .. n do
        yield i, j ]

let rec filter x0 y0 = function
  | [] -> []
  | (x1, y1 as q)::xys as list ->
      let xys' = filter x0 y0 xys
      if safe x0 y0 x1 y1 then
        if System.Object.ReferenceEquals(xys', xys) then list else
          q::xys'
      else
        xys'

let rec search n nqs qs ps a =
  match ps with
  | [] -> if nqs=n then a+1 else a
  | (x, y as q)::ps ->
      search n nqs qs ps a
      |> search n (nqs+1) (q::qs) (filter x y ps)

let solve n =
  search n 0 [] (ps n) 0

Stopping this program on its 1,000th GC cycle when it is solving the 11-queens problem, extracting references between allocated but unmarked cons cells, filtering out connected components with 3 or more vertices and visualizing the result using Mathematica's GraphPlot function gives the following:

In this case, we find that just 6% of the cons cells die alone (i.e. singleton lists) and 84% die in a clump of two cons cells, 6.5% die in a clump of 3 cons cells and 3.4% die in clumps containing four or more cons cells. Only a handful of clumps had interesting structures.

Although these results suggest that it might be easy to obtain a speedup by adding a special case to the list type for lists containing two elements we have found that this is not the case because the required changes also add expensive operations elsewhere, e.g. destructuring the special two-element list now incurs an allocation. Therefore, the next best solution would be to optimize the garbage collector for this case but it would be prudent to analyze the clusters collected during the running of other programs first. Analyzing the garbage generated by a program using red-black trees would be interesting...

The LMAX disruptor and Baker's Treadmill

2011-11-14T08:16:00.000-08:00

A new retail financial trading platform called LMAX recently published their work on new software technology for low-latency servers that they call the "disruptor":

We have noticed a striking similiarity between their disruptor and an old garbage collection algorithm from 1992 called Baker's Treadmill:

The LMAX disruptor and the story behind it are very interesting in their own right and well worth reading up on. In their system, binary messages come from the "receiver" and are distributed to the "journaller", "replicator" and "unmarshaller" in parallel and the "unmarshaller" then passes on the deserialized messages to the "consumer". The core of their idea is to accomplish all of this message passing using a single shared data structure, the disruptor, rather than using several separate concurrent queues.

Baker's Treadmill is a low-latency garbage collection algorithm. Allocated blocks in the heap are linked together to form a cyclic doubly-linked list that is divided into four segments using four iterators that chase each other around the ring as heap blocks are allocated, traced and freed. In addition to making all of the necessary operations incremental, this algorithm is interesting because it migrates heap blocks between its "to", "from", "new" and "free" spaces without physically copying them as so-called copying GC algorithms do (e.g. Cheney semi-space or the nursery in a generational GC). Although this kind of logical migration is very valuable it is surprisingly uncommon in GC research literature. The VCGC algorithm is another example of a GC algorithm that logically migrates heap blocks between "young", "old" and "dead" spaces or "epochs" as the authors call them.

Beyond the striking resemblance of the disruptor to the Treadmill, there are some important differences:

The disruptor is a thread-safe concurrent data structure whereas the Treadmill was designed for single-threaded use.
The disruptor was designed to flow data from producers to consumers whereas the Treadmill also requires the ability to move an element from one segment of the ring to another.

Despite these differences, we think it is interesting to observe the similarities between these two different data structures and to note that they were both designed for low latency. Given that Baker's Treadmill is now quite dated in terms of low latency GC algorithms, perhaps future work on low-latency data structures can borrow from more recent GC theory?

Real garbage collector characteristics

2011-11-12T12:55:00.001-08:00

The trade-offs between tracing and reference counting garbage collectors are nicely demonstrated by systems like F# and Mathematica. F# inherits garbage collection from .NET which uses a conventional generational tracing garbage collector with three generations and a Large Object Heap (LOH). Mathematica uses reference counting with language semantics that make it impossible to create cycles in the heap.

The following Mathematica program creates a balanced binary tree 25 levels deep that contains 2²⁵ branches stores it in a variable and then mutates the variable back to the empty list:

Because Mathematica uses reference counting, the act of resetting the variable back to the empty list decrements the reference count for the root of our tree back to zero, causing an avalanche of reference counts in the branches down to the leaves also being decremented back to zero, reclaiming all of the space that was consumed by the tree that is now unreachable. Moreover, Mathematica is serial so all of this work is done on the main thread, blocking everything. Consequently, resetting the variable to the empty list takes a whopping 2.213s.

Surprisingly, although Mathematica has clearly done a lot of work that is presumably involved in releasing the space consumed by the tree it does not actually return any memory to the OS and continues to consume almost half of the entire 32-bit address space on this machine!

This program may be written as follows in F#:

type t = Leaf | Branch of t * t  let rec deepTree = function   | 0 -> Leaf   | n -> Branch(deepTree(n-1), deepTree(n-1))  let mutable t = deepTree 25  t <- Leaf  System.GC.Collect()

In this case, creating the tree takes 10.2s, resetting the tree takes a fraction of a millisecond and explicitly invoking the garbage collector (which actually returns all of the memory back to the OS) takes 0.44s.

This highlights some of the trade-offs involved both in using systems that provide garbage collection as a user and in creating such systems as a developer.

Classifying garbage collection algorithms

2011-11-11T15:07:00.001-08:00

Richard Jones' excellent new book about garbage collection has rekindled my fascination with this important subject. The Wikipedia page about GC is disappointingly poor quality so it is productive to review the main points here.

GC algorithms are categorized into four main families with production garbage collectors often combining algorithms from different families. The families are copying, mark-sweep, mark-compact and reference counting. The first three are all tracing collectors that work by tracing all reachable values by starting from the global roots (global variables and locals held on the stack).

Copying collectors allocate into one space and then "evacuate" the reachable heap blocks (called "survivors") into another space before clearing the space they came from. The Cheney semi-space algorithm is the simplest copying collector: it uses two spaces and copies from one to the other and back again. The advantage of copying collection is that many heap-allocated blocks are deallocated simultaneously simply by resetting a pointer. This is ideal when only a small proportion of the allocated values survive a collection. As most values die young, the copying collection algorithm is commonly used for the nursery generation in a generational collector.

Mark sweep is the oldest garbage collection algorithm (McCarthy 1959) and works by tracing all reachable values and then deallocating all of the remaining unreachable values. This algorithm offers relatively high throughput and can be made incremental (low latency) using Dijkstra's tricolor marking scheme but is (arguably) prone to fragmentation. Consequently, the mark-sweep algorithm is commonly used for the old generation of generational collectors.

Mark compact traces reachable values and then slides them together. This avoids the problem of fragmentation that can (allegedly) afflict mark-sweep collectors but the throughput of mark-compact collectors is apparently so poor that they are practically unheard of.

Reference counting works by having each value count the number of references to it. This requires the program to register locally held references by incrementing the reference count of the value referred to and then decrementing it again when the reference is no longer held. This is typically done by decrementing the reference count when the local reference falls out of scope in the source code although liveness analysis can be exploited to find a tighter bound on when a reference is no longer needed. When a reference count is decremented to zero there are no longer any references to the value so it is unreachable and can be deallocated. Interestingly, reference counting is the opposite of tracing because it works by pursuing dropped references rather than by following live references. The advantages of reference counting are its simplicity, determinism in the context of single-threaded programs (multithreaded programs race to decrement and, therefore, deallocate non-deterministically) and that it can easily be made incremental by maintaining a queue of reference counts that have yet to be decremented. The disadvantages are that it leaks cycles and has very poor throughput. However, cycles can be collected either by a backup tracing collector or by using a specific cycle collector such as the trial deletion algorithm, and throughput can be improved by deferring decrements (although this recovers the disadvantage of unpredictability).

Latency is a big issue in the context of garbage collection so algorithms are also classified according to their latency characteristics. Stop-the-world algorithms are relatively simple but high latency, incurring arbitrarily-long pause times during which the mutator threads (those running the actual program) make no progress at all. The .NET 4 server GC is an example of a stop-the-world GC in production. GHC also uses a stop-the-world GC. The advantages of stop-the-world garbage collection algorithms are simplicity and high throughput. These GCs often incur pauses of the order of one second, which is totally unacceptable for many soft real-time applications such as visualization, games and (ironically!) servers.

Incremental GCs break up the work of a full GC and interleave the resulting bits of work in with the execution of the program. For example, OCaml's GC performs a "slice" of the work required to collect the old generation every time the young generation is collected. The advantages of incremental GCs are low latency compared to stop-the-world (e.g. ~10ms pauses with OCaml) and simplicity compared to concurrent GCs.

Today, the term "parallel GC" is used to describe a GC that uses multiple threads to speedup the collection of garbage. The .NET 4 server GC is an example of a parallel GC because it uses one thread per core to mark the heap in parallel. Concurrent GC means the GC runs at the same time as the mutators. For example, the .NET workstation GC is an example of a concurrent GC in production. Concurrent garbage collectors are further refined into on-the-fly and mostly-concurrent algorithms. An on-the-fly GC is defined by Jones et al. as one that never suspends more than one mutator at a time (i.e. there is no stop-the-world phase) although I suspect he meant that mutators are suspended independently of each other. Finally, a mostly-concurrent GC is one that does suspend all mutator threads simultaneously but only for a short period of time and not for an arbitrarily-long GC phase. For example, the .NET workstation GC pauses all mutator threads while the global roots are examined but runs concurrently with them during the marking and sweeping of the whole heap so it is a mostly concurrent garbage collector.

These classifications by family of algorithm and by latency characteristics are the most important ones.

Applying optimization algorithms to profits

2011-11-03T10:50:00.000-07:00

As a technology company, we like to apply technical solutions to problems at all levels. Our board of directors even apply technical solutions to the problem of company direction.

Business can be thought of as an optimization algorithm: tweaking stuff and things in order to maximize company profits. Interestingly, we use a number of different kinds of optimization algorithm when dictating the direction of the company.

We begin new product lines based on experience but continue to optimize our products based on customer feedback, trying to solve the problems that are most important to our customers. For example, our F# for Numerics library started life as our second attempt at selling libraries to F# users (our first attempt was F# for Visualization) and we provided the features we thought would be most useful. Customers inevitably requested more features including both technical features like parallel matrix inversion with arbitrary-precision rational arithmetic but also non-technical features such as licences allowing them to bundle our library in their own commercial products. This approach of incrementally improving products is a kind of local optimization algorithm, like gradient descent. This is a low-risk approach that yields small improvements in profits.

Over the years, we have been commissioned to write many books and reports and have published many books ourselves. We often use content from one successful book as the inspiration for the next. For example, our 2004 book OCaml for Scientists was surprisingly successful and became the inspiration for our 2006 book F# for Scientists and more recently Visual F# 2010 for Technical Computing. This is a kind of evolutionary algorithm because the next generation of books are derived from the previous generation and share some of their "DNA" with them. This is a riskier approach with variable results. We take a lot of risks and expect a significant proportion of our new products to fail but every now and then we come up with a new product that ends up earning as much revenue as all of the others combined.

At this level of abstraction, computational algorithms can be used for all sorts of weird and wonderful applications. Doubtless we all use them without even realising it!

New book on garbage collection

2011-09-07T01:53:00.001-07:00

After 15 years, Richard Jones has written a new monograph about garbage collection called The Garbage Collection Handbook. This supercedes his previous seminal book on the subject Garbage Collection: algorithms for automatic dynamic memory management.

In particular, this new book covers state-of-the-art techniques including parallel, incremental, concurrent and real-time garbage collection algorithms.

I'll post a review as soon as I've read my copy!

Pros and cons of OCaml

2011-03-27T02:27:00.000-07:00

The advantages and disadvantages of the OCaml programming language.

Pros:

More powerful type inference than any other language: OCaml even infers union and class types!
Powerful module system lets you parameterize modules over other modules easily and safely with full compile-time checking and minimal run-time overhead.
Structural typing of modules, polymorphic variants and classes improves brevity, closing the gap with dynamic languages, but can obfuscate error messages.
Powerful integrated macro system lets you alter the language's syntax on-the-fly and write parsers quickly and easily.
Good serial performance from the x64 code gen.
Easy-to-use REPL.
Lots of high-quality tools and libraries.

Cons:

No overloading can make numerical code over many different types (e.g. complex numbers, vectors and matrices) tedious.
Poor multicore support means poor performance on today's computers.
Some basic functionality missing (e.g. no 32-bit floats, no try..finally construct).
Some basic functionality is very inefficient (e.g. 32-bit ints).
Poor floating point performance from the x86 code gen.
16MB limit on strings and arrays on 32-bit systems.
No way to override equality, comparison and hashing for new types and no way to catch errors created by this when the default structural versions are not applicable. Type classes are a solution to the former problem and equality types are a solution to the latter.
No value types means more memory use and worse performance in some important situations (e.g. filling a hash table with float keys and values in OCaml is 17× slower than F#).

Alternatives to Numerical Recipes

2011-03-13T10:31:00.000-07:00

The Jet Propulsion Laboratory at Nasa once hosted an interesting web page listing better alternatives to the infamous book Numerical Recipes. Here is a copy courtesy of The Wayback Machine:

There is no single alternative to Numerical Recipes. The authors of Numerical Recipes provide a superficial overview of a large amount of material in a small volume. In order to do so, they made many unfortunate compromises.

It is naïve to hope that every computational problem can be solved by a simple procedure that can be described in a few pages of chatty prose, and using a page or two of Fortran or C code. Today's ambitions for correctness, accuracy, precision, stability, "robustness", efficiency, etc. demand sophisticated codes developed by experts with deep understanding of their disciplines. We have long ago outgrown the capabilities of the simplistic approaches of 30 years ago.

Steve Sullivan has constructed a FAQ (Frequently Asked Questions) list on numerical analysis. The size of the list will give you some idea of the scope of the field. Some books are reviewed in section q165.

It would be unproductive to try to list all the excellent textbooks on numerical analysis. A few of them are (in alphabetical order of primary author):

Kendall Atkinson, Numerical Analysis.
Ward Cheney and David Kincaid, Numerical Mathematics and Computing, Brooks-Cole (Third edition, 1994). Aharon Naiman has prepared slides for a series of lectures he teaches at Jerusalem College of Technology using this text.
George Forsythe, Michael Malcolm and Cleve Moler, Computer Methods for Mathematical Computations, Prentice-Hall (1977). This book is probably out of print. It is a predecessor to the book by Kahaner et. al., and written in a similar style. It is less comprehensive than the newer work.
Francis B. Hildebrand, Introduction to Numerical Analysis, McGraw-Hill (1956, 1974), Dover (1987 0-486-65363-3). This is one of the best books ever written on numerical analysis. It's out-of-date in some areas, most notably in Least Squares computation. Hildebrand has an engaging and transparent style of exposition, similar to Press et. al. This book is, however, a mathematically sound reference to material of the same era as presented in much of Numerical Recipes.
David Kahaner, Cleve Moler and John Nash, Numerical Methods and Software, Prentice-Hall (1989). ISBN 0-13-627258-4. This book is probably closest in style to Numerical Recipes, but was written by practitioners in the field, rather then by experts in a different field.
Diskette included.
John H. Mathews, Numerical Methods: for Mathematics, Science & Engineering, 2nd Ed., ISBN 0-13-624990-6 and 0-13-625047-5, Prentice Hall Inc. (1992). With purchase of this book free software is available from the following links:
John H. Mathews and Russell W. Howell,
COMPLEX ANALYSIS: for Mathematics and Engineering, Third Edition, 1997, ISBN 0-7637-0270-6.
With purchase of this book, free software is available.
Zdzislaw Meglicki has posted the text for a course on advanced scientific computing at Indiana University.
G. W. "Pete" Stewart posted the following in
na-net:
"I have recently published a book entitled `Afternotes on Numerical Analysis'... It is a series of 22 lectures on elementary numerical analysis. The notes themselves were prepared after the lectures were given and are an accurate snapshot of what went on in class. Although they are no substitute for a full-blown numerical analysis textbook, many people have found them a useful supplement to a first course. The book is published by SIAM. For further information contact service@siam.org." and on 2 Jan 1997:
I have just completed a new set of afternotes and have posted them on the web. The original afternotes were based on an advanced undergraduate course taught at the University of Maryland. The present notes are based on the follow-up graduate course. The topics treated are approximation\,---\,discrete and continuous\,---\,linear and quadratic splines, eigensystems, and Krylov sequence methods. The notes conclude with two little lectures on classical iterative methods and nonlinear equations
The notes may be obtained by anonymous ftp at thales.cs.umd.edu in /pub/afternotes or by browsing my homepage
http://www.cs.umd.edu/~stewart/.
I will be grateful for any comments, corrections, or suggestions.

There are excellent texts and reference works that focus on narrow portions of
the discipline of numerical analysis. Consider, for example:

Gene H. Golub and Charles F. Van Loan, Matrix Computations, Johns Hopkins (first edition 1983, second edition 1989, third edition 1996). ISBN 0-8018-5413-X (0-8018-5414-8 paper).
Ernst Hairer, Syvert Paul Nørsett, Gerhard Wanner, Solving Ordinary Differential Equations I: Nonstiff Problems, Springer-Verlag (1987 3-540-17145-2 0-387-17145-2). A second edition has appeared but the ISBN's here are for the first.
Ernst Hairer, Gerhard Wanner, Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, Springer-Verlag (1991: 3-540-53775-9 and 0-387-53775-9; 1996: 3-540-60452-9). This book and the previous one are highly regarded.
Charles L. Lawson and Richard J. Hanson, Solving Least Squares Problems, Prentice-Hall (first edition 1974), SIAM Press (second edition 1995) ISBN 0-89871-356-0.
Philip J. Davis and Philip Rabinowitz, Methods of Numerical Integration, Academic Press (second edition 1984) ISBN 0-12-206360-0.
Ingrid Daubechies, Ten Lectures on Wavelets, SIAM Press.
Jorge J. Moré and Stephen J. Wright, Optimization Software Guide, Frontiers in Applied Mathematics 14, Society for Industrial and Applied Mathematics (1993). About evenly divided between algorithms and software, both public-domain and commercial. (This book actually covers a fair amount of the content of Numerical Recipes, especially those parts that the authors of NR deemed too complex to do well.)
Spaeth, Mathematical Algorithms for Linear Regression (1987).

If you have been using Numerical Recipes for software, we recommend that
you contact the computing professionals in your organization. For JPL users, you can contact the Computational Mathematics Subgroup, or obtain the Math77 and mathc90 libraries of mathematical software directly. There is also a substantial amount of software and information about software on-line.

For one-of-a-kind computations, we recommend MATLAB (The MathWorks, Inc.).

Scala's premature release

2011-02-23T14:11:00.000-08:00

Back in August 2010, Martin Odersky raised eyebrows by stating that "Scala is foremost an industrial language". We commented on this triumph of hope over reality at the time, citing Scala's poor IDE support as a major headache for industrial users that had deterred us from adopting this academically-interesting programming language.

This rookie mistake of marketing a product months before it is ready is all too common. Several of our young client companies made the same mistake. One had even been paying an entire sales division not only salaries but bonuses for over a year before their first product was released!

The problem is not just the wasted marketing effort but that potential customers are deterred by their bad experiences with the immature product. This is reflected in Jonathan Edwards' recent article "Switching to Plan J", where he writes:

"My experiment with Scala is not working out. It’s just not ready for prime time..." - Jonathan Edwards

and others echo the sentiment:

"I’ve found exactly the same thing..." - Nat

"I agree with every point you made in this article... Tools are awful, even though years have been spent developing them." - Mark

"...plagued by continuous problems..." - Roy Batty

Martin Odersky now says that he is "painfully aware of the Eclipse issues" and Scala Solutions are working to produce reliable IDE support for Scala but he also admits that Emacs has been his IDE of choice for Scala development.

Hopefully the potential users who have been disappointed by today's Scala will try the language again once a first attempt has been made to address core issues like the reliability of the IDE support.

Size of industrial F# code bases

2011-02-09T10:16:00.000-08:00

Almost exactly a year ago, we published a blog post stating that we had 345kLOC of production OCaml code and 171kLOC of production F# code. Today, we have 261kLOC of production F# code!

Sweeping 700× faster

2011-01-09T04:29:00.000-08:00

Our initial experiments using the new garbage collector design indicate that it dramatically improves the performance of the slowest GC phase (sweeping) as expected, to the extent that it brings the overall performance of our C++ prototype within 10% of OCaml without introducing any of the overheads of generational garbage collection:

Moreover the algorithm is very simple and, in particular, parallel and concurrent variants should be much easier to design with this style of collector than with generational collectors because regions are a suitable granularity.

The sweep phase of the GC accounted for around a third of the total running time of the entire program using the traditional algorithm with allocated and free lists, with each sweep taking around 70µs. Using the new bitwise algorithm, the sweep phase takes just 100ns and accounts for just 0.7% of the total running time of the program.

Our prototype mark region collector using a fake marking phase is now between 2 and 10% slower than OCaml without having sacrificed either its better performance on other benchmarks or its multicore capability. However, our new design has increased the cost of both allocation and marking. Although they accounted for a tiny proportion of the total running time, it remains to be seen whether or not this new GC algorithm will be faster than a traditional generational collector in this best-case scenario for generational collection when it is implemented in a real VM. In particular, the overheads of HLVM's current shadow stack may well make it slower.

Our collection strategy also captures the benefits of Appel's semi-generational collection algorithm. Appel's algorithm compacted nursery survivors to one end of the nursery and used the remaining space as a smaller nursery repeatedly until the entire nursery was full of reachable values that were then promoted to the old generation. Our region-based collector can allow each thread to sweep its own region locally, independently of all other regions and cores. This also leads to the same non-linearity that makes Appel's algorithm so effective but without the overheads of copying. Using regions containing 62 blocks each 64 bytes long, local sweeping increased the number of allocations performed before a new region was required from 62 to a whopping 3,000 allocations. Obtaining a new region requires synchronization, so this simple improvement has reduced the rate of synchronizations by around a factor of 50. With 8-byte regions, the 11-queens problem can be solved with a single region and, therefore, without any contention at all between threads.

Therefore, we believe our new GC design will allow us to make HLVM competitively performant on functional benchmarks like this without losing its substantial advantages on imperative code, where it is often several times faster than OCaml.

The importance of locality and sparsity in memory management

2011-01-08T06:12:00.000-08:00

Our previous articles describing the disadvantages of generational garbage collection and our prototype mark-region memory management system designed for HLVM originally showed that region-based allocation and deallocation has the potential to be only 4-20% slower than OCaml's generational collector. However, our more recent work that was designed to be more realistic by deferring deallocations to bulk GC cycles was significantly slower, around twice as slow as OCaml.

There are several differences between the stack-based deallocation scheme used in the first benchmark and the GC-like deallocation scheme used in the second benchmark that have the potential to account for this performance degradation:

The mock GC introduced mark bytes into the allocated values and marked them as unreachable when they fell out of scope in the mutator.
The mock GC allocated by popping a reference of the top of a region's free list.
The mock GC deallocated by pushing a reference onto the free list of the reference's region.
The mock GC added an "allocated list" that is used to record everything that has been allocated.
Upon deallocation, the mock GC removed a reference from the allocated list by overwriting it with the last element and reducing the length of the allocated list by one.

The overhead of the new "mark phase" that marks values as unreachable when they fall out of scope is minimal. The mark phase in HLVM's real GC accounts for less than 2% of the total running time of this benchmark and it does significantly more work (traversing the shadow stack) than the mark phase in this benchmark.

Using the free list as a stack would cause subsequent allocations to be contiguous in memory if and only if the free list happens to be ordered, i.e. allocations and deallocations are in LIFO order. This was the case in the first benchmark but not the second.

Upon collection, the allocated list was traversed sequentially. However, the way in which references were removed from the allocated list may well have been the critical design flaw. Specifically, moving an the element from the back of the allocated list into the middle, to overwrite a removed element changes the order of the list slightly. We suspected that the disorder would accumulate over time, destroying the locality of the references in the allocated list. Consequently, a sequential traversal of the allocated list is likely to have been of little benefit because the subsequent elements of the allocated list would have referenced random locations. Moreover, that disorder would have been passed on to the free lists, which would have seen values freed in random order rather than sequentially.

We had speculated that sparsity was largely responsible for the remaining performance gap between OCaml and all of the strategies based upon per-value deallocation because OCaml's generational GC is able to sweep runs of contiguously-allocated values from the nursery generation in constant time. On the basis of this, we predicted that a derivative of mark-region capable of deallocating contiguous runs of values from a region might get significantly closer to OCaml's performance on this benchmark. In particular, the performance profile of our prototype indicates that 18% of the total time is spent allocating and 17% is spent collecting. Furthermore, the L2 cache is around 50% slower than the L1 cache on this machine so the performance of the mutator might be 50% worse due to poor locality of reference in the second benchmark. These figures suggest that improving locality might double performance and, therefore, make our solution as fast as OCaml.

To answer some of our questions, we wrote a simulation of the prototype (!) in the F# programming language and used it to gather relevant statistics. This proved to be extremely successful and led to several major insights.

Firstly, values die over time so longer gaps between GC cycles means a higher proportion of unreachable values. The following graph illustrates the relationship between the number of allocations performed between collections and the proportion of values that remain reachable:

If GC cycles are separated by at least 300 allocations then more than half of the allocated values become unreachable and are swept. Therefore, we can optimize the allocated list operations under the assumption that most of the elements of the list will not survive a GC cycle.

Secondly, we found that the algorithm used to remove an element from the allocated list does indeed dominate the locality and, therefore, the performance of the entire program. The following graph illustrates the probability density of deallocations as a function of the length of the run of contiguously-allocated values that a value is in:

These results show that the original algorithm for removing references from the allocated list led to 45% of values being deallocated alone and significantly fewer being deallocated in contiguous runs. Therefore, it is clear that the original algorithm was indeed destroying locality when it reordered the references in the allocated lists.

In contrast, removing values from the allocated list using the order-preserving sliding compaction retained locality. In that case, only 0.02% of values were deallocated alone. In fact, the new algorithm is so good at preserving locality that values are more likely to be deallocated with a few neighbors than alone. Specifically, values are 4× more likely to be deallocated as part of a run of 23 contiguously-allocated values than they are to be deallocated alone.

These new results lend credence to our conjecture that exploiting sparsity by deallocating contiguous runs of values rather than individual values is the key to achieving performance comparable to that of a generational GC. However, we also now know that this will only be possible if the allocation-collection cycle preserves locality as much as possible.

The simplest way to preserve the order of allocations and exploit sparse deallocations is to side step the problem by changing the data structures involved:

Replace the free list with a bitvector.
Replace the mark bits in each value with a per-region mark bitvector.
Replace the allocated list with queues of full and non-full regions.

With 512 bits in a cache line, we can reserve the first cache line of each region to use as a bitvector for the entire region because we previously found that regions containing around this many values give near-optimal performance. Allocating from a region is then a matter of finding the first (un)set bit in the bitvector and the associated location, flipping the bit and returning the location. A contiguous sequence of values can be deallocated from a region by computing and applying a bitmask to the bitvector.

With regions conveying where allocated values are, there is no longer any need for an explicit allocated list. Therefore, the allocated list may be replaced with a global queue of regions. When a local region is filled it is enqueued on the global queue of full-regions and a region is dequeued from the global queue of non-full regions or freshly allocated if there are no non-full regions in the global queue. When a GC cycle occurs, the global regions are dequeued, swept and enqueued again on the appropriate queue, i.e. if a full region becomes non-full then it changes queues.

Incredibly, sweeping a region is now as simple as applying bitwise operations to the allocated- and marked-bitvectors in order to remove unmarked locations from the allocated bitvector.

With this new design, the operations that limited the performance of the old design will now be substantially faster and the locality of reference for the mutator threads will be greatly improved.

We are currently prototyping this new design. As we shall see in a future post, this new GC algorithm not only naturally lends itself to both parallelism and concurrency but is also almost a drop-in replacement for HLVM's current memory management subsystem.

Paul Graham's accumulator generator

2011-01-05T04:38:00.000-08:00

Paul Graham once published an article about what he called "accumulator generators". This problem requires the existence of an unspecified numeric tower. Lisp happens to have one and it happens to be adequate for Paul Graham's examples.

You can implement a numeric tower in F# either using a union type (like type number = Int of int | Float of float) or by boxing everything. The following solution uses the latter approach:

let add (x: obj) (y: obj) =
match x, y with
| (:? int as m), (:? int as n) -> box(m+n)
| (:? int as n), (:? float as x)
| (:? float as x), (:? int as n) -> box(x + float n)
| (:? float as x), (:? float as y) -> box(x + y)
| _ -> failwith "Run-time type error"

let acc x =
let x = ref x
fun (y: obj) ->
 x := add !x y
 !x

let x : obj -> _ = acc(box 1)
do x(box 5)
do acc(box 3)
do printfn "%A" (x(box 2.3))

However, numeric towers are of little use in general purpose programming and usually do more harm than good. Trying to learn from these kinds of challenges can do more harm than good. The real question is: why we do not want a numeric tower, do not want to box and do not want run-time type promotion?

In other words, why didn't we just write:

let x = 1
let x = x + 5
ignore(3)
let x = float x + 2.3

We know the type of x at every step. Every number is stored unboxed. And we know that this code cannot produce a run-time type error.

IO throughput: Haskell vs F#

2011-01-04T05:15:00.000-08:00

Many applications require the ability to churn through gigabytes of data. In such cases, high IO throughput is valuable. This article examines high-throughput IO in the Haskell and F# programming languages. The Haskell solutions use the ByteString library and the F# solutions use ordinary .NET 4 IO.

An eager Haskell solution that loads the entire file into memory may be written as follows:

import System
import Bits
import Data.List
import Data.ByteString as B

main =
    getArgs
    >>= B.readFile . Data.List.head
    >>= print . B.foldl xor 0

A lazy alternative that loads parts of the file on-demand may be written as follows:

import System
import Bits
import Data.List
import Data.ByteString.Lazy as B

main =
    getArgs
    >>= B.readFile . Data.List.head
    >>= print . B.foldl xor 0

An eager F# version can simply call the ReadAllBytes function to load the entire file:

System.IO.File.ReadAllBytes file
|> Array.fold (^^^) 0uy

An on-demand alternative simply opens the file and calls ReadByte on a buffered stream in a loop until the end of the file is reached:

use stream = new System.IO.FileStream(file, System.IO.FileMode.Open)
use stream = new System.IO.BufferedStream(stream)
let rec loop n =
  let b = stream.ReadByte()
  if b >= 0 then loop (n ^^^ b) else n
loop 0

Compiling the Haskell with GHC 6.12.3 using --make -O2 flags and running the F# interactively in Visual Studio 2010 on a Dell Precision T5400 running 32-bit Windows Vista with 4Gb of RAM gave the following results for the on-demand versions:

The eager F# failed due to lack of memory on all three files. The eager Haskell obtained the correct answer on the smallest file, crashed on the middle file and produced corrupted output on the largest file. These problems appear to stem from a signed 32-bit integer overflowing inside the ByteString library, causing it to either crash when apparently-negative ByteString lengths are encountered or to read only part of a file.

Several points of interest:

The variations between the speed of the Haskell and F# solutions is less than 5% in each case.
Wrapping the IO in an IEnumerable (seq in F#) severely degrades performance.
On 64-bit machines, memory mapping have different trade-offs.
Haskell's ByteString library includes some special functions (e.g. count) that use optimized kernels written in C and assembler to manipulate large quantities of data more efficiently than is currently possible from Haskell or F#.

For more information on high-performance F#, read Visual F# 2010 for Technical Computing.

The benefits of purely functional data structures

2011-01-01T16:14:00.000-08:00

Purely functional data structures have the following advantages:

Persistence: old versions can be reused safe in the knowledge that they cannot have been changed.
Sharing: many versions of a data structure can be kept simultaneously with relatively modest memory requirements.
Thread safety: any mutation is hidden inside lazy thunks (if any) and, therefore, thread safety is handled by the language implementation.
Simplicity: not having to keep track of state changes often makes purely functional data structures simpler to use, particularly in the context of concurrency.
Incrementality: purely functional data structures are composed of many tiny parts, making them ideal for incremental garbage collection, leading to lower latencies.

Purely functional data structures also have the potential to be beneficial in the context of parallel programming for multicores. However, efficient multicore parallelism requires predictable locality in order to leverage caches and avoid getting bottlenecked on access to shared caches and main memory and purely functional data structures have, at best, unknown characteristics in this regard. Consequently, many programs that use purely functional data structures do not scale well when parallelized on a multicore because they spend all of their time in cache misses, contending for shared memory pathways.

Boost's shared_ptr up to 10× slower than OCaml's garbage collection

2011-01-01T08:03:00.000-08:00

Our recent post about the merits of accurate garbage collection over reference counting prompted Tezka to ask for measurements demonstrating the performance differences between an accurate GC and the reference counted shared_ptr smart pointers provided by the Boost C++ library.

The benchmarks we have been using to prototype allocators for our HLVM project provide the perfect setting for such an experiment. We already have C++ code that solves the n-queens problem using logic programming with a variety of different allocation strategies. Adding another version of our benchmark using Boost's shared_ptr gave the following remarkable results:

These new results highlight just how slow reference counting can be. The C++ code using Boost's reference counted smart pointers is running up to 10× slower than OCaml!

Note also the new "stack" section that is the first C++ to beat OCaml, albeit cheating by exploiting the fact that this implementation of this benchmark always happens to allocate and free in FIFO order. So this approach is problem-specific and cannot be used as a general-purpose allocator. However, it is worth noting that the only allocation strategy to beat C++ also (like OCaml's nursery) exploits the ability to collect many freed values in constant time by resetting the stack pointer rather than using repeated pops. Therefore, the only allocation strategies likely to approach OCaml's performance on these kinds of problems are those that exploit sparsity. For example, by manipulating free lists in run-length encoded form.

We have yet to find a general-purpose allocation strategy that can match the performance of OCaml's generational garbage collector for these kinds of applications but we can make two interesting observations from these new results:

Reference counting is the only difference between the "free" results (using malloc and free in FIFO order) and these new "shared_ptr" results, so around 80% of the time is spent handling reference counts, far more than is spent in actual allocation and deallocation!
HLVM currently performs poorly on this benchmark because around 70% of its time is spent maintaining the shadow stack, a comparable overhead to the use of reference counting (but one that handles the collection of cycles correctly).

Finally, we should note that our "region 12" results are also new and note that they are significantly worse than the previous "region" results. The difference is that the previous results allocated and deallocated in FIFO order explicitly in the inner loops of the benchmark whereas these new results are a more accurate reflection of the allocation and deallocate patterns that the current version of HLVM generates, specifically the inner loops only maintain the mark bits and deallocation is now performed by sweeps triggered by sufficient allocation. Sweeping results in much worse performance (from 20% slower than OCaml to 2× slower than OCaml). We have invented two ways to attack this problem. Firstly, the thread-local current region could be swept locally, either using a remembered set or just back to the previous write barrier. Secondly, runs of consecutively-allocated unreachable values are likely to appear near the end of the allocated list, so sparse free lists will hopefully accelerate the collection of contiguous sequences of unreachable values.

Extensibility in functional programming languages

2010-12-29T15:44:00.000-08:00

Most software developers are now familiar with inheritance and virtual methods as common techniques for extensibility from the object oriented paradigm. When faced with functional programming for the first time, these developers often ask how to write extensible code in this alien paradigm.

The functional paradigm actually only provides a single form of extensibility: higher-order functions. These allow you to factor out "inner" functions. For example, code that often appears with the same first and last code blocks:

let f x =
 first x
 stuff1 x
 last x
let g x =
 first x
 stuff2 x
 last x

can be factored into a general higher order function that is reused from the specific cases:

let hof stuff x =
 first x
 stuff x
 last x
let f = hof stuff1 x
let g = hof stuff2 x

Applying this aggressively leads to design patterns such as parser combinators and is a very powerful and lightweight technique for making code extensible. However, it does not make data types extensible.

Consequently, functional programming languages almost always include language features to help with extensibility:

Common Lisp has the Common Lisp Object System (CLOS) and a macro system.
Standard ML has parametric polymorphism and a higher-order module system.
OCaml added polymorphic variants, objects, optional arguments and the Camlp4 macro system.
Haskell has parametric polymorphism and type classes, and Template Haskell adds macros.
Scala has Java-style OOP with some added features.

Read Chris Okasaki's excellent monograph Purely functional data structures for some great examples using higher-order modules in Standard ML and type classes in Haskell. Read Code reuse through polymorphic variants by Jacques Garrigue for a description of how that language feature can be used to attack the expression problem. However, these solutions are quite rare in the wild and, in particular, you can get a long way without them (e.g. in F#).

Historically, this diversity appeared because most functional programming languages were research projects and, consequently, they existed to add novel features. Therefore, we now have a wide variety of disparate forms of extensibility in today's functional programming languages.

F# is a different beast compared to its predecessors like OCaml and Haskell because its design requirements were seamless interoperability with the rest of .NET (which imposes .NET-style OOP) and pragmatism. Consequently, F# keeps the ML core with parametric polymorphism and adds .NET's object system. So you can benefit from the easy extensibility offered by generic higher-order functions and conventional OOP but not from any of the more esoteric features like higher-order modules, type classes and macros.

The only form of extensibility F# has pioneered is active patterns. These allow you to separate code that destructures via pattern matching from the concrete data representation. This is an important way to decouple code from data and, therefore, make it more reusable.

Distinctive traits of functional programming languages

2010-12-29T15:10:00.000-08:00

The landscape of functional programming languages is remarkably diverse, with most of the major families having quite distinctive traits and dialects that bring their own quirks. Here are some of the major categorizations:

Evaluation strategy: non-strict (Miranda, Haskell) vs strict evaluation.
Type system: static (Standard ML, OCaml, F#, Haskell, Scala, C# 3) vs dynamic (Scheme, Lisp, Clojure, Erlang) typing and untyped (Mathematica).
Kind of static typing: structural (OCaml) vs nominal (F#, Haskell, Scala, C# 3) static typing.
Type inference: Damas-Milner (Standard ML, OCaml, F#, Haskell) vs "local" inference (Scala, C# 3).
Destructuring: pattern matching (Standard ML, OCaml, F#, Haskell, Erlang, Mathematica) vs manual deconstruction (Scheme, Lisp, C#).
Extensibility of algebraic types: always closed (Standard ML, Haskell) vs optionally closed (OCaml).
Pattern matching: linear (Standard ML, OCaml, Haskell) vs unbounded (F#, Mathematica).
Run-time code generation: meta-circular evaluator (Scheme, Lisp, Clojure) vs heterogeneous code generation (F# → CIL) vs nothing (Standard ML, OCaml, Haskell).
Macros: unhygenic macros (Common Lisp, OCaml, Template Haskell, Mathematica) vs hygenic macros (Scheme) vs no macros (Standard ML, F#).
Standardization: standardized (Standard ML, Haskell 98, Common Lisp, Scheme) vs proprietary (OCaml, F#, GHC Haskell, Erlang, Mathematica).

Why GC when you have reference counted smart pointers?

2010-12-29T14:07:00.001-08:00

Reference counted smart pointers are a simple form of garbage collection usable from the C++ programming language. A recent question on Stack Exchange asks why anyone would want anything more when reference counted smart pointers are already available.

Other forms of garbage collection (most notably tracing GCs) have several advantages over reference counting:

Accuracy: Reference counting alone leaks cycles so reference counted smart pointers will leak memory in general unless other techniques are added to catch cycles. Once those techniques are added, reference counting's benefit of simplicity has vanished.
Throughput: Smart pointers are one of the least efficient forms of garbage collection, particularly in the context of multi-threaded applications when reference counts are bumped atomically. There are advanced reference counting techniques designed to alleviate this but tracing GCs are still the algorithm of choice in production environments.
Latency: Typical smart pointer implementations allow destructors to avalanche, resulting in unbounded pause times. Other forms of garbage collection are much more incremental and can even be real time, e.g. Baker's treadmill.

Many of the answers given perpetuate myths about garbage collection. There is a myth that scope-based reference counting guarantees that values are collected as soon as possible. In fact, tracing collectors can and do collect values before the end of their lexical scope if the value becomes unreachable sooner and a GC occurs. Another myth is that garbage collected languages cannot release resources deterministically. In fact, this is done in exactly the same way as in unmanaged languages. Finally, there is a myth that manual memory management minimizes latency. In fact, manual memory management often has poorer worst-case latency characteristics than garbage collection (this problem originally drove us from C++ to OCaml!) and optimizing latency in an unmanaged language is seriously hard work.

Towards a mark-region GC for HLVM

2010-12-28T08:10:00.000-08:00

Our previous article highlighted the advantages of the recent mark-region GC design and hinted at HLVM adopting this design. We just completed some preliminary tests using a prototype written in C++ to measure the performance of different allocation strategies. Our results are as follows with times normalized by the time an equivalent OCaml program takes (so 1.0 means as fast as OCaml):

The four columns in each section give the times relative to OCaml for solving the 8-, 9-, 10- and 11-queens problems.

The "Boehm" section refers to the conservative Boehm GC which is 40-70% slower than OCaml on this benchmark. The "malloc" section refers to allocating using the malloc function from glibc without ever freeing and is 2.2-3.1× slower than OCaml. The "free" section refers to allocating with malloc and freeing (manually) and is 1.9-2.3× slower than OCaml. The "bump" section refers to a naive bump allocator that never recycles memory and is 1.4-1.7× slower than OCaml. Finally, the "region" section refers to our prototype region-based algorithm, which is just 4-20% slower than OCaml on this benchmark!

This benchmark is a classic logic programming problem that allocates large numbers of short-lived values. This is a best-case benchmark for OCaml and a worst-case benchmark for the current HLVM. OCaml's generational garbage collector with its fast bump allocator and constant-time recycling of dead values from the nursery generation does extremely well on this benchmark: we have been unable to beat its performance from C/C++.

The Boehm garbage collector is another interesting point of comparison because it has been the subject of intense optimization for many years.

These new results are very enlightening. Recycling memory by calling free is significantly faster than leaking memory by only ever calling malloc. Specifically, leaking is around 3× slower than OCaml and proper manual memory management using malloc and free is around 2× slower than OCaml. Moreover, the performance of the Boehm GC is very similar to manual memory management but still 2× slower than OCaml.

Bump allocating from a huge preallocated pool without ever freeing is surprisingly slow: around 1.5× slower than OCaml. This early result was disappointing but it turned out that our new region allocator is very fast indeed. This is extremely encouraging because it means that a non-moving mark-region collector for HLVM might be able to offer the best of both worlds: the speed of C/C++/Fortran for imperative code using mutable data structures and the speed of OCaml/Haskell for functional code using immutable data structures.

Our prototype region allocator allocates aligned regions using the glibc memalign function. This allows a pointer to the start of the region to be obtained from any pointer inside the region using bitwise operations. Each region begins with a C++ vector that holds the free list, the list of pointers inside the region that are not currently allocated. The remainder of the region is a pool of fixed-size blocks that can be allocated and deallocated. To allocate, the last element is popped off the free list. To free, the free list associated with the pointer is obtained using bitwise operations and the pointer is pushed onto the back of the free list. In the prototype, if the allocator finds the current region to be full then it stores it in a global collection of regions and allocates a new local region. In a production version, the allocator would recycle one of the non-full regions from the global collection of regions rather than allocating a new region each time.

How big should a region be? The results shown above were obtained using 1MB regions, large enough that they were never filled and a new region was never needed. However, reducing the region size to 1kB causes the prototype to create 8,295 regions on the 11-queens problem but the program is only 5% slower and total memory consumption is around 99% lower than simply leaking, so memory is being recycled effectively.

Measuring the absolute performance of the 10-queens solver as a function of the region size gives the following results:

The smallest possible region size of 16 bytes allows a single allocation per region and makes the whole program run 7.6× slower. Increasing the region size improves the efficiency of the region allocator (except for an anomaly between 128 and 256 byte regions that is probably due to benchmark-specific allocation patterns). With 1,024-byte regions, performance is within a few percent of optimal for this benchmark. One might have expected to see significant performance gains from larger regions up to the size of the 6Mb L2 cache on this machine but the tiny working set required by this benchmark eliminated any performance difference beyond 1kB regions.

The following graph shows the number of regions allocated for different region sizes on the 10-queens benchmark:

Smaller regions means a larger number of regions are required, up to around ten million for 16-byte regions. The relationship here reflects the previous region size vs performance relationship because the most of the time is spent administering regions when they are small. The initial sharp drop-off occurs because allowing regions to contain just a few more values significantly increases their ability to recycle space. With 1kB regions, only 874 regions are created to solve this problem.

The product of the region size and number of regions used quantifies the total space allocated for regions using glibc. Doubling the region size from 64 bytes to 128 bytes reduces the total memory allocated by 33% and doubling the region size from 2kB to 4kB reduces the total memory allocated by 99%. Perhaps the accelerated efficiency is due to the generational hypothesis that predicts inverse hyper-exponential decay of the probability of death as a function of age.

In HLVM, a thread-safe allocator will try to use the thread-local region and resort to synchronization only when obtaining the current region is full whereupon an existing non-full region will be reused or a new empty region will be created. The deallocator must potentially access any region but, with HLVM's current design, it is only invoked from a single thread during the stop-the-world phase so it can be thread unsafe. This has two benefits over the current technique:

Single-threaded allocation and deallocation should be almost twice as fast as they are today.
Multi-threaded allocation should scale linearly with the number of cores whereas HLVM currently sees performance degradation from concurrent allocations.

However, our previous results indicated that HLVM's currently-dismal performance on this benchmark is actually due to the shadow stack and not to allocation. We anticipate that efficient concurrent allocation will be the next bottleneck after the performance of the shadow stack is addressed so this is still valuable work.

Two pieces of related work remain to be done:

Mimic the effects of HLVM's current GC more accurately by deallocating in chunks.
Extend the prototype to reuse existing non-full regions before allocating a new empty region.

When generational GC goes bad

2010-12-23T17:05:00.000-08:00

For many years, generational collection was the defacto-standard GC architecture. Based upon the observation that the distribution of value lifetimes is heavily skewed towards short lifetimes (most values die young), generational garbage collectors allocate into a nursery generation and survivors are copied out into an old generation.

Many practical language implementations use generational garbage collection including OCaml, GHC and .NET. Generational collection works well when the generational hypothesis holds but struggles when values survive the nursery only to become unreachable soon afterwards. This corresponds to common allocation patterns such as cycling values through mutable queues or caches and filling hash tables.

Imagine repeatedly enqueuing and dequeuing values on a queue. The lifetimes of the values are proportional to the length of the queue. Thus, this provides a simple way to quantify the performance overhead of generational garbage collection. If boxed values are enqueued and dequeued on OCaml's built-in mutable Queue data structure then the time taken per element jumps by around a factor of 2-3.5 when the elements reachable from the queue exceed the size of the nursery and, thus, most survive to the old generation rather than being collected efficiently in the young generation. Specifically, the time taken to enqueue and dequeue 32-bit ints on this 2.1GHz 2352 Opteron jumps from 0.33μs to 0.68-1.13μs. Where is this time being wasted?

When a boxed value (such as a 32-bit integer) is allocated in OCaml, it is augmented with a 1-word header and another for the forwarding pointer and that whole block is bump allocated from the nursery. When that value is written into the Queue in the old generation, a write barrier is incurred which stores a copy of the reference in the remembered set. When the nursery is filled, a minor collection is performed that traces from the global roots and remembered set throughout the reachable values in the nursery. These values are then copied into the old generation, their forwarding pointers are set and all locally-held references to them are updated via the forwarding pointers to point into their copies in the old generation. The nursery is then swept by resetting the bump allocator to the start of the nursery.

Suffice to say, this is a lot of overhead when the values allocated into the nursery do not die quickly enough. In that case, all of this effort is a complete waste of time and we would have been better off allocating directly into the old generation in the first place. What can be done to address this problem?

Fortunately, McKinley et al. made a breakthrough in GC design in recent years with their invention of a new class of GC algorithms known as mark-region GCs. It all began with their invention of the Beltway GC in 2002, a generalization of several existing GC designs, and culminated in their Immix GC in 2007. In effect, this GC design allows a nursery full of reachable values to be migrated to the old heap implicitly without any copying and a new nursery is allocated to replace it. The old generation is then effectively a collection of surviving nurseries. The precise placement policy is more complicated because it is possible to reuse old nurseries in order to avoid gross fragmentation but the basic concept is simple enough.

A Google Summer of Code project had an Immix variant implemented for the Glasgow Haskell Compiler. They found the results to be underwhelming but that is not so surprising given that this GC design should be most effective when filling mutable data structures such as queues, caches, hash sets and hash tables. We believe that a simple mark-region variant should be able to dramatically improve HLVM's performance on parallel functional code without degrading the performance of imperative code as generational garbage collectors like OCaml's do.

Getting paid to remove features

2010-12-15T10:56:00.000-08:00

Although the Industrial Haskell Group has yet to garner its first industrial member since its inception almost two years ago, they have managed the impressive feat of getting paid to remove a feature from Haskell. Specifically, to make it easier to build programs written in Haskell that do not rely upon the GNU Multiprecision library for arbitrary-precision arithmetic (bignums).

We made this interesting observation when considering adding bignums using GMP as a primitive type for HLVM. Apparently, having bignums in the language is not very useful beyond irrelevant microbenchmarks like computing the digits of π.

The slides here also criticize the CAML Consortium (which has garnered 11 members) for charging too little and states that the IHG aimed to garner five members each paying £12k per annum. Why has this target not yet been reached? Our guess is insufficient sales and marketing directed at decision makers in industry who could benefit from using Haskell. As an aside, we believe this same mistake is why the founders of Stack Overflow found it so difficult to monetize despite having millions of non-paying users. In contrast, Rich Hickey managed to garner funding from a whopping 427 people and several companies for his own language, Clojure.

Regardless, the fact that they are trying to build a business around the development of Haskell itself is admirable and should at least prompt more professionals to take a look at what is on offer.

Texas Multicore Technologies on Haskell

2010-12-05T07:46:00.000-08:00

US-based startup Texas Multicore Technologies have published some of the results they obtained using Haskell for parallel programming. Their results mirror our own:

Thanks to Manuel Chakravarty of the University of New South Wales for drawing this to our attention.

Mono 2.8: a step closer to a reliable foundation

2010-11-06T16:15:00.000-07:00

We previously complained about the use of Boehm's conservative garbage collector in earlier versions of Mono because it is fundamentally flawed and prone to causing unpredictable memory leaks that result in applications dying with out-of-memory errors when there is plenty of garbage left to be reclaimed. Specifically, we gave a simple 9-line example program that fills and forgets ten hash tables that ran out of memory when run on Mono 2.4. What happens when this program is run on Mono 2.8 using the new SGen garbage collector?

Running the test with Mono 2.8 using the default Boehm GC often reproduces the same leak that we saw before, as expected. Repeating our previous test using the new SGen garbage collector we find that the program does not die after four iterations with an out-of-memory error but gets as far as eight of the intended ten iterations before dying with a segmentation fault:

$ mono-sgen TailCall.exe
m[42] = 42
Took 3.40511s

m[42] = 42
Took 3.41273s

m[42] = 42
Took 3.20464s

m[42] = 42
Took 3.96534s

m[42] = 42
Took 3.14944s

m[42] = 42
Took 3.10114s

m[42] = 42
Took 3.14187s

m[42] = 42
Took 3.27123s

Stacktrace:

  at (wrapper managed-to-native) object.__icall_wrapper_mono_gc_alloc_vector (intptr,intptr,intptr) <0x00003>
  at (wrapper managed-to-native) object.__icall_wrapper_mono_gc_alloc_vector (intptr,intptr,intptr) <0x00003>
  at (wrapper alloc) object.AllocVector (intptr,intptr) <0x000ac>
  at System.Collections.Generic.Dictionary`2<double, double>.Resize () <0x001bc>
  at System.Collections.Generic.Dictionary`2<double, double>.set_Item (double,double) <0x0014f>
  at <StartupCode$TailCall>.$Program.main@ () <0x0007c>
  at (wrapper runtime-invoke) object.runtime_invoke_void (object,intptr,intptr,intptr) <0x0007d>

Native stacktrace:

        mono-sgen [0x80dec34]
        mono-sgen [0x812b2cb]
        [0xb76f3410]
        mono-sgen [0x8174e17]
        mono-sgen [0x8175428]
        [0xb72ecb0b]
        [0xb72e97d5]
        [0xb72ec695]
        [0xb72ec2a8]
        [0xb72e8d9d]
        [0xb72e8fd6]
        mono-sgen [0x8065318]
        mono-sgen(mono_runtime_invoke+0x40) [0x81a9aa0]
        mono-sgen(mono_runtime_exec_main+0xd6) [0x81ad1f6]
        mono-sgen(mono_main+0x1a41) [0x80bb501]
        mono-sgen [0x805b388]
        /lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xe6) [0xb7451b56]
        mono-sgen [0x805b131]

Debug info from gdb:

[Thread debugging using libthread_db enabled]
[New Thread 0xb7103b70 (LWP 8401)]
0xb76f3430 in __kernel_vsyscall ()
  2 Thread 0xb7103b70 (LWP 8401)  0xb76f3430 in __kernel_vsyscall ()
* 1 Thread 0xb7439720 (LWP 8400)  0xb76f3430 in __kernel_vsyscall ()

Thread 2 (Thread 0xb7103b70 (LWP 8401)):
#0  0xb76f3430 in __kernel_vsyscall ()
#1  0xb75a9f75 in sem_wait@@GLIBC_2.1 ()
    at ../nptl/sysdeps/unix/sysv/linux/i386/i686/../i486/sem_wait.S:80
#2  0x0822c778 in mono_sem_wait (sem=0x89ce64c, alertable=0)
    at mono-semaphore.c:102
#3  0x081560c7 in finalizer_thread (unused=0x0) at gc.c:1048
#4  0x08183065 in start_wrapper (data=0xa37c760) at threads.c:747
#5  0x0821a7df in thread_start_routine (args=0xa36762c) at wthreads.c:285
#6  0x0816da8b in gc_start_thread (arg=0xa37c808) at sgen-gc.c:5350
#7  0xb75a380e in start_thread (arg=0xb7103b70) at pthread_create.c:300
#8  0xb75078de in clone () at ../sysdeps/unix/sysv/linux/i386/clone.S:130

Thread 1 (Thread 0xb7439720 (LWP 8400)):
#0  0xb76f3430 in __kernel_vsyscall ()
#1  0xb75aac8b in read () from /lib/tls/i686/cmov/libpthread.so.0
#2  0x080dedfc in read (signal=11, ctx=0xb72fcd0c)
    at /usr/include/bits/unistd.h:45
#3  mono_handle_native_sigsegv (signal=11, ctx=0xb72fcd0c)
    at mini-exceptions.c:1935
#4  0x0812b2cb in mono_arch_handle_altstack_exception (sigctx=0xb72fcd0c,
    fault_addr=0x8, stack_ovf=0) at exceptions-x86.c:1163
#5  <signal handler called>
#6  alloc_large_inner (vtable=<value optimised out>,
    size=<value optimised out>) at sgen-los.c:368
#7  0x08174e17 in mono_gc_alloc_obj_nolock (vtable=0xa3af948, size=0)
    at sgen-gc.c:3219
#8  0x08175428 in mono_gc_alloc_vector (vtable=0xa3af948, size=147681864,
    max_length=18460231) at sgen-gc.c:3437
#9  0xb72ecb0b in ?? ()
#10 0xb72e97d5 in ?? ()
#11 0xb72ec695 in ?? ()
#12 0xb72ec2a8 in ?? ()
#13 0xb72e8d9d in ?? ()
#14 0xb72e8fd6 in ?? ()
#15 0x08065318 in mono_jit_runtime_invoke (method=0xa330bdc, obj=0x0,
    params=0xbfd1aafc, exc=0x0) at mini.c:5392
#16 0x081a9aa0 in mono_runtime_invoke (method=0xa330bdc, obj=0x0,
    params=0xbfd1aafc, exc=0x0) at object.c:2709
#17 0x081ad1f6 in mono_runtime_exec_main (method=0xa330bdc, args=0xb6c00638,
    exc=0x0) at object.c:3838
#18 0x080bb501 in main_thread_handler (argc=2, argv=0xbfd1ace4) at driver.c:999
#19 mono_main (argc=2, argv=0xbfd1ace4) at driver.c:1836
#20 0x0805b388 in mono_main_with_options (argc=2, argv=0xbfd1ace4) at main.c:66
#21 main (argc=2, argv=0xbfd1ace4) at main.c:97

=================================================================
Got a SIGSEGV while executing native code. This usually indicates
a fatal error in the mono runtime or one of the native libraries
used by your application.
=================================================================

Aborted

Seven years after the Mono team described their use of the Boehm garbage collector as "an interim measure", the SGen collector is still experimental. Hopefully these issues will be resolved and the Mono platform will benefit from a reliable garbage collector in the not too-distant future. However, we cannot help but wonder why the Mono team have not chosen to release a simple but reliable garbage collector that people could use while they wait for SGen to be stabilized. After all, multicore-friendly garbage collection can be easy.

"The F# Asynchronous Programming Model" by Don Syme et al.

2010-10-27T09:24:00.000-07:00

The creator of the F# programming language at Microsoft Research in Cambridge, Don Syme, recently had a paper accepted for the Practical Aspects of Declarative Languages conference. This paper provides a great introduction to asynchronous workflows and the MailboxProcessor in F#.

In fact, the use of monads to sequence asynchronous operations has a long history. For example, this approach has been used in the OCaml programming language, from which F# is descended, for at least 8 years. Specifically, Jérôme Vouillon's LWT library for OCaml made asynchronous programming easy. For example, the first F# sample given in this paper:

async { let! html = getWebPage "http://www.google.com"
        return html.Length }

Could have been written in OCaml as follows in 2002:

getWebPage "http://www.google.com" >>=
String.length

In 2005, Jacques Carette et al.'s pa_monad syntax extension even added the same kind of syntactic sugar that F# provides for its asynchronous workflows, allowing the sample to be written in OCaml as:

perform
  html <-- getWebPage "http://www.google.com"
  return String.length html

For more information on asynchronous programming in F#, read Visual F# 2010 for Technical Computing.

What is the difference between parallel and concurrent programming?

2010-10-20T15:18:00.000-07:00

Concurrent programming regards operations that appear to overlap and is primarily concerned with the complexity that arises due to non-deterministic control flow. The quantitative costs associated with concurrent programs are typically both throughput and latency. Concurrent programs are often IO bound but not always, e.g. concurrent garbage collectors are entirely on-CPU. The pedagogical example of a concurrent program is a web crawler. This program initiates requests for web pages and accepts the responses concurrently as the results of the downloads become available, accumulating a set of pages that have already been visited. Control flow is non-deterministic because the responses are not necessarily received in the same order each time the program is run. This characteristic can make it very hard to debug concurrent programs. Some applications are fundamentally concurrent, e.g. web servers must handle client connections concurrently. Erlang is a language designed specifically for distributed concurrent programming with fault tolerance but many other languages provide features for concurrent programming, such as asynchronous workflows in the F# programming language.

Parallel programming concerns operations that are overlapped for the specific goal of improving throughput. The difficulties of concurrent programming are evaded by making control flow deterministic. Typically, programs spawn sets of child tasks that run in parallel and the parent task only continues once every subtask has finished. This makes parallel programs much easier to debug. The hard part of parallel programming is performance optimization with respect to issues such as granularity and communication. The latter is still an issue in the context of multicores because there is a considerable cost associated with transferring data from one cache to another. Dense matrix-matrix multiply is a pedagogical example of parallel programming and it can be solved efficiently by using Strassen's divide-and-conquer algorithm and attacking the sub-problems in parallel. Cilk is pioneered the most promising techniques for high-performance parallel programming on shared-memory computers (including multicores) and its technology is now offered by Intel in their Threaded Building Blocks (TBB) and Microsoft in .NET 4. So this is also easily accessible from the F# programming language.

Don Syme on "Functional approaches to parallelism and concurrency"

2010-10-20T10:41:00.001-07:00

Don Syme, creator of the F# programming language, recently gave a superb lecture on parallel and concurrent programming using F# at QCon 2010. Video and slides hosted by InfoQ here.

Parallel programming continues to be a hot topic in the face of multicore computing but, as Don points out, the world is also moving steadily towards more concurrent programming.

Work continues on our forthcoming "Multicore .NET" book that studies parallel programming using C# and F# in detail...

Can you repro this 64-bit .NET GC bug?

2010-10-19T02:22:00.001-07:00

Update: Maoni Stephens of Microsoft, the author of this new "Background" garbage collector in .NET 4, has now reproduced the bug and acknowledged that we really are seeing GC pauses lasting several minutes.

Whilst developing low latency software on .NET, we have discovered a serious bug in the .NET 4 concurrent workstation garbage collector that can cause applications to hang for up to several minutes at a time.

On three of our machines the following simple C# program causes the GC to leak memory until none remains and a single mammoth GC cycle kicks in, stalling the program for several minutes (!) while 11Gb of heap is recycled:

static void Main(string[] args) {

  var q = new System.Collections.Generic.Queue();

  while (true) {

    q.Enqueue(0);

    if (q.Count > 1000000)

      q.Dequeue();

You need to compile for x64 on a 64-bit Windows OS with .NET 4 and run with the default (concurrent workstation) GC using the default (interactive) latency setting.

Here's what the Task Manager looks like when running this program on this machine:

Note that 11Gb of heap have been leaked here when this program requires no more than 100Mb of memory.

We have now accumulated around a dozen repros of this bug, written in F# as well as C#, and it appears to be related to a bug in the GC write barrier when most of gen0 survives. However, Microsoft have not yet been able to reproduce it. Can you?

ARM-based iPads choke Intel-based netbook sales

2010-10-16T13:22:00.000-07:00

The recent news that Apple are selling around 18 million of their ARM-based iPads per year reminded us of our article Will Intel lose the computer market to ARM in 2012? from January. Following their success, there are now a growing number of competitors itching to release ARM-based tablet PCs of their own, like Marvell's $99 Moby tablet.

Compare just those iPad sales to the 35 million netbooks of all brands sold in 2009 and the predicted 36 million netbooks to be sold in 2010 and it looks as though Intel may at least lose the mobile market to ARM in 2012.

Towards concurrent garbage collection for GHC

2010-10-10T14:00:00.000-07:00

Simon Marlow of Microsoft Research recently published a blog post entitled First results from GHC's new garbage collector. As his beautiful graphs show so clearly, this is a first step towards concurrent garbage collection. The blog post describes this advancement entirely from the perspective of throughput because the ability to collect per-thread nursery generations independently removes some of the blocking that was wasting mutator time in the previous version.

However, we believe that concurrent programming may become a killer application domain for Haskell and, in that context, latency can be critical. If GHC's garbage collector is made more concurrent, by allowing the old generation to be collected independently as well, then pause times could be greatly reduced and Haskell would have a considerable advantage over competing technologies like .NET.

We have found that even the best-behaved .NET programs that allocate still suffer GC pauses of around 20ms, over an order of magnitude longer than the 600µs pause times indicated on the graphs for this new version of GHC. Real .NET applications that were not designed from the ground up to attain low latency suffer stalls lasting several seconds!

Lessons learned from HLVM

2010-09-26T04:50:00.001-07:00

Although our HLVM project is intended to bring modern VM techniques to modern programming languages without requiring any new research, we have ended up producing several enlightening new results. This article takes a look at some of the weird and wonderful techniques we used in HLVM.

GC as a metaprogram (good!)

Whereas most VMs use a garbage collector written in C or C++, the GC in HLVM is written in its own intermediate representation. This unusual design has a variety of benefits:

The GC acts as a test for the compiler.
The GC benefits from improvements we make to the compiler.
The GC is simplified by being able to use features like tail call elimination and higher-order functions.

Overall, implementing the GC in HLVM's own IR proved to be hugely beneficial: the GC was very easy to write and is easy to maintain.

Fat references (bad!)

Most VMs store header data in each heap-allocated block that describes the size and type of a value in order to allow the garbage collector to traverse it. In HLVM, we moved this header data into the reference itself. This allows C data structures to be used directly without having to be copied in order add the header, simplifying and improving the efficiency of the foreign function interface (FFI).

This adds a 4-word space overhead for duplicated references. Fortunately, duplicate references are rare and no significant space overhead has ever been observed in practice.

However, there are two disadvantages. Firstly, we have observed significant performance degradation as fat references are pushed onto the stadow stack, requiring 4× more bandwidth than 1-word references would. Secondly, our fat references cannot be updated atomically so our VM is not memory safe.

Lack of memory safety is a major concern and the best solution we have come up with to date is to resort to 1-word references as pointers to heap-allocated header information. Note that HLVM currently calls malloc twice for each allocation (once to allocate a mark bit and again to allocate the actual data) so moving the header information back into the heap need not require more allocations. The obvious solution of placing the header alongside the mark bit would incur false sharing when the GC thread writes to the mark bit and a mutator reads the header information. If that proves to be a problem then a better solution might be to store an index that can be used to look up the mark bit and header data from two separate arrays.

Shadow stacks (adequate!)

Xavier Leroy dismissed our proposed shadow stack, saying "probably the worst approach performance-wise; even a conservative GC should work better". Our motivation for using shadow stacks was always simplicity rather than performance. Shadow stacks are simply because LLVM's GC support is highly experimental (to date, only two people claim to have managed to get it to work) and shadow stacks facilitate accurate GC in an uncooperative environment). In fact, our results have already proven that Xavier's statement is not true in general and, in fact, we believe it may even be wrong in general.

Specifically, of the six benchmarks from our benchmark suite than handle references in the inner loop (thus incurring manipulation of the shadow stack), HLVM is significantly faster than OCaml on four of them. So our shadow stack cannot be degrading performance that much! Moreover, OCaml is 9× faster than HLVM on our n-queens benchmark only because its generational collector allows short-lived values to be recycled very efficiently and that has nothing to do with the shadow stack.

So we believe shadow stacks are an adequate solution.

The effectiveness of Boehm's GC

2010-09-25T04:41:00.000-07:00

Many people still seem to be trying to use Boehm's garbage collector. This is surprising because that GC is conservative, meaning it is incapable of accurately distinguishing between integers and pointers and, consequently, it is prone to memory leaks due to false positives where integers are assumed to be pointers into an allocated heap block, preventing the block from being reclaimed. Consequently, Boehm's GC is a notorious source of memory leaks.

Moreover, 32-bit machines with 4Gb of RAM and programs that use a significant proportion of that RAM are still very common and the proportion of the address space in use is, therefore, high so the probability of false positives is very high.

Imagine a 32-bit program using 40Mb of heap contains a random integer. The probability of that random integer coincidentally pointing into an allocated heap block is approximately 1% because 1% of the 4Gb address space is covered by heap blocks. Now imagine a 32-bit program containing n random ints and using a proportion p of the address space. The probability that one or more of those ints point into allocated heap blocks is 1-(1-p)ⁿ. In our previous example, if there were 100 random ints then the probability of a false positive is a whopping 63%!

This is why 32-bit programs that use Boehm's GC are so prone to memory leaks. Hash tables are particularly susceptible to this problem because hashes are effectively random ints and the spines of hash tables are large heap blocks. Indeed, this appears to explain the memory leak we observed when using hash tables on Mono back in July.

Are multicore-capable garbage collectors hard to write?

2010-09-19T13:25:00.000-07:00

In this era of multicore computing, garbage collectors need to allow user threads (aka mutators) to run in parallel on separate cores simultaneously in order to facilitate efficient shared memory parallel programming.

There are two relevant phrases from garbage collection terminology here:

Parallel GC means the garbage collector itself has been parallelised in order to speed up garbage collections. For example, a stop-the-world collector might traverse the heap in parallel when marking in an attempt to reduce pause times.
Concurrent GC means the garbage collector runs at the same time as the user threads (aka mutators). For example, Dijkstra's algorithm and derivatives like Doligez-Leroy use fine-grained synchronization to keep a concurrently-running collector apprised of the constantly-changing heap topology.

However, we are talking about neither parallel GC nor concurrent GC but, rather, the simpler challenge of just allowing mutators to run in parallel. In the absence of any established terminology, we call any GC that allows mutator threads to run in parallel with each other a multicore-friendly garbage collector.

Frustratingly, many people are perpetuating the myth that it is difficult to write parallel or concurrent or even just multicore-friendly garbage collectors. In particular, this is happening around the OCaml language as a result of Xavier Leroy's (in)famous "standard lecture on threads" from 2002 where he explained that they were not creating a multicore-friendly garbage collector for OCaml because multicores would never become popular and he described Intel's hyperthreading as "the last convulsive movement of SMP's corpse". Xavier is a great guy and had done a lot of great work but, of course, he was completely wrong about this. Not only are multicores ubiquitous and hyperthreading is very common but shared memory parallelism is here to stay: even if distributed parallelism becomes essential in the future when cache coherence breaks down we will be doing distributed parallel programming between multicores because shared memory parallelism is so much more efficient than distributed parallelism most of the time.

The JVM and .NET CLR obviously provide multicore-friendly garbage collectors so people sometimes assert that creating such a garbage collector requires huge resources and is beyond a small group such as the OCaml team at INRIA. This is simply not true. The simplest multicore-friendly garbage collector design is a stop-the-world collector that pauses all user threads while the entire heap is marked and swept safe in the knowledge that the heap topology is static. Our own HLVM project currently uses exactly this design and it took just a few days to write and is under 100 lines of code! And we are not alone. Simon Marlow has written several far more sophisticated multicore-friendly garbage collectors for the Glasgow Haskell Compiler by himself. The PolyML project developed a multicore-friendly garbage collector without benefit of funding from a multinational corporation. Same for Manticore.

Even some of the more sophisticated mostly-concurrent garbage collector designs are remarkably simple. For example, the Very Concurrent Garbage Collector (VCGC) uses a breathtakingly-elegant approach based around three epochs (instead of the usual tricolor marking scheme) that completely avoids the error-prone and inefficient fine-grained synchronization originally proposed by Dijkstra and followed by almost everyone else. The entire algorithm for this mostly concurrent garbage collector can be expressed in a single page of code!

So please do not let these myths put you off trying to write your own multicore-friendly garbage collector: this is an interesting, rewarding and entirely tractable challenge!

Burton Smith vs Erik Meijer

2010-09-12T02:38:00.000-07:00

We were recently led to a fascinating Channel 9 interview where the insideous Erik Meijer walks in on parallelism-expert Burton Smith, culminating in a fight the likes of which have not been seen since Chris Curry vs Sir Clive Sinclair in the Baron of Beef here in Cambridge.

A pragmatic Burton points out that lazy evaluation renders performance unpredictable and that, in turn, makes it impossible to tune the granularity of parallel programs to ensure that more effort is spent doing actual work than is wasted administering parallel tasks. The puritanical Erik points out that strictness is essentially another form of side effect because it affects issues such as non-termination. The conclusion is irreconcilable differences between what parallel programming requires and what purely functional programming can provide.

Erik and Burton were joined by an elephant in the room though: caches. They are the main difference between supercomputers and multicores and are a game changer, yet people do not discuss the effect caches have on programming and that effect will only grow as the memory gap continues to widen. Today, effective utilization of caches offers an order of magnitude in performance yet their effective use from purely functional languages like Haskell is essentially impossible precisely because memory has been successfully abstracted away. Indeed, as we have explained before, this not only remains a show-stopping unsolved problem for parallel Haskell but is not even being addressed by researchers. Today's state-of-the-art advice for multicore programmers is still to use mutable data structures in order to ensure caches are used effectively based upon the quantification of asymptotic cache complexity in the context of a simple theoretical model of CPU caches.

New Scala consultancy company

2010-08-10T06:43:00.000-07:00

We have uncovered an interesting development since publishing our previous article about Martin Odersky's claim that Scala is "foremost an industrial language". Apparently, Martin Odersky stated at Scala Days 2010 that he intends to create a startup offering commercial Scala support. He also mentioned it in a comment here. Needless to say, this would be a huge step forwards for Scala!

As an interesting aside, the Scala in the Enterprise web page lists some industrial users of Scala including Électricité de France Trading, Twitter, Xebia, Xerox, FourSquare, Sony, Siemans, GridGain, AppJet, Reaktor, Nature, Managed Gaming Solutions, Tiental, Sygneca, AD Holdings, SAIC, Mimesis Republic and WattzOn.

"I think F# is very cool" - Rich Hickey

2010-08-09T13:34:00.000-07:00

Very interesting video interview here with Rich Hickey of Clojure and Joe Pamer of F# side-by-side. When the interviewer asks Rich Hickey what he thinks of F#, he says "I think F# is very cool" and then explains why.

Rich Hickey is, of course, a visionary among programming language developers having single-handedly built a self-sustaining business around his own Clojure language. Remarkably, there are already more Clojure jobs than OCaml jobs according to IT Jobs Watch and there are now twice as many Google searches for Clojure as there are for OCaml:

"Scala is foremost an industrial language"

2010-08-07T02:15:00.000-07:00

In a recent interview about Scala and Clojure, Martin Odersky of Scala gave some interesting answers including the following:

Q: Rich Hickey is as well-read in the academic papers as anyone, but it’s Scala that has gained the perception as an “academic language”. Why do you think that has happened?
A: I think it’s mostly people who want to put Scala down making that comment. They take my EPFL affiliation and the papers we publish as an excuse to attach that label to the language. What’s funny is that often senior industrial Scala programmers get also accused as being academic. All this is rather ironical because Scala is foremost an industrial language with many well known companies using it. By contrast it’s much less taught at universities than Haskell or Lisp, let alone Java!

This raises the obvious question: in what sense is Scala "foremost an industrial language"?

As we understand it, Scala is developed by an academic team led by professor Odersky at an academic institution with academic funding for the sole purpose of academic research and this has culminated in a new academic paper every 7½ months on average over the past decade. That is not true of any industrial programming languages. Indeed, from our experiences with Scala this is reflected as a growth in esoteric language features when basic IDE support is neglected. Some people are trying to use Scala in industry, but that is true of many academic languages. Some funding has come from industry, including a surprising grant from Microsoft to update the .NET port of Scala, but that is presumably a tiny fraction of the total funding that has been spent on Scala. So this seems like rather an odd claim.

More OCaml trends

2010-08-06T15:40:00.000-07:00

Paolo from Italy pointed out that the number of blog posts on OCaml has continued to increase in recent years (6,420, 10,500 and 12,100 in 2007/8/9 according to Google blog search) and referred to the success of this year's OCaml meeting with 80 delegates in France. These are certainly encouraging results but it may be worth bringing more data to the table.

Firstly, Google Trends can be used to graph the proportion of Google searches for different search terms over time. The following graph shows the trends for the keywords OCaml and F# since 2004:

As you can see, the proportion of searches for OCaml (blue) is in steady decline whereas the proportion of searches for F# (red) is on the increase and the two crossed over in 2007. In fact, we have found that Google Trends correlates very strongly with our revenue.

Secondly, we can examine statistics about the job market. The following bar chart illustrates the change in UK jobs from 2008 to 2010 for four functional programming languages (source IT Jobs Watch):
As you can see, every language saw tremendous growth in this boom period for functional programming except OCaml which actually saw a decline in the number of jobs on offer.

The deal breaker for us was, of course, revenue. The proportion of our revenue coming from OCaml has fallen steadily from 80% in 2007 to just 10% today.

Pure F# now only 2× slower than OCaml

2010-08-05T17:08:00.000-07:00

One of the concerns expressed by some of the remaining OCaml users, such as Yaron Minsky of Jane St Capital, is the relative performance of F# in the context of purely functional data structures. Specifically, language implementations like OCaml are heavily optimized for this use case due to their legacy and on-going use for applications such as theorem proving, which benefit greatly from the efficient handling of purely functional data structures. Historically, most users of imperative languages such as Java and C# have not required this kind of performance and, consequently, their implementations have not been optimized for this style of programming. However, the recently released .NET 4 includes a new garbage collector and we have found that it provides substantial performance improvements in the context of purely functional data structures which is of particular benefit to F# developers.

We recently examined the performance of four different purely functional heap implementations across five different benchmarks written in both OCaml and F# (see Data structures: heaps). Where our previous findings in similar benchmarks showed F# to be 5× slower than OCaml, our new results indicate that F# on .NET 4 is now only 2× slower than OCaml on average. In one case, a leftist min heap with elements inserted in descending order, F# even ran 20% faster than OCaml.

This is a surprising and encouraging result not only because it makes F# competitive for an even wider variety of tasks but because it also implies that Microsoft are taking F# so seriously that they are optimizing the .NET garbage collector for it!

Parallel generic quicksort in Haskell

2010-08-01T08:47:00.001-07:00

Haskell has a history of making easy problems difficult. Perhaps the most infamous example was the Sieve of Eratosthenes, which is easily implemented in any imperative language but was so difficult to write in Haskell that almost all of the solutions that had been taught in universities and used in research for the preceding 18 years had been wrong until Melissa O'Neill published a seminal paper The Genuine Sieve of Eratosthenes that gave a beautiful description of what they had been doing wrong and how it should be corrected. Melissa's solution was to use a priority queue to implement a rolling wheel of numbers. The correct solution turned out to be 10× longer than a much simpler F# solution and a whopping 100× longer than the original bastardized algorithm in Haskell.

Today, quicksort is the new Sieve of Eratosthenes. Again, the academics have addressed Haskell's failure by bastardizing the algorithm, trading orders of magnitude in performance for something that Haskell can express easily:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

This completely fails to capture the essence of the real quicksort algorithm (see Tony Hoare's original 1962 quicksort paper) that makes it so efficient. Specifically, the in-place partitioning using swaps.

Faced with the challenge of writing a parallel generic quicksort in Haskell, Jim Apple (who is doing a PhD on Haskell at UC Davis) kicked of proceedings with the following code:

import Data.HashTable as H
import Data.Array.IO
import Control.Parallel.Strategies
import Control.Monad
import System

exch a i r =
    do tmpi <- readArray a i
       tmpr <- readArray a r
       writeArray a i tmpr
       writeArray a i tmpi

bool a b c = if c then a else b

quicksort arr l r =
  if r <= l then return () else do
    i <- loop (l-1) r =<< readArray arr r
    exch arr i r
    withStrategy rpar $ quicksort arr l (i-1)
    quicksort arr (i+1) r
  where
    loop i j v = do
      (i', j') <- liftM2 (,) (find (>=v) (+1) (i+1)) (find (<=v) (subtract 1) (j-1))
      if (i' < j') then exch arr i' j' >> loop i' j' v
                   else return i'
    find p f i = if i == l then return i
                 else bool (return i) (find p f (f i)) . p =<< readArray arr i

main = 
    do [testSize] <- fmap (fmap read) getArgs
       arr <- testPar testSize
       ans <- readArray arr  (testSize `div` 2)
       print ans

testPar testSize =
    do x <- testArray testSize
       quicksort x 0 (testSize - 1)
       return x

testArray :: Int -> IO (IOArray Int Double)
testArray testSize = 
    do ans <- newListArray (0,testSize-1) [fromIntegral $ H.hashString $ show i | i <- [1..testSize]]
       return ans

This solution uses Haskell's parallel "strategies". This concept was introduced to give Haskell programmers more control over parallelization but the only available implementation was found to leak memory and nobody was able to get it to work in this case: Jim's solution contains a concurrency bug that causes it to return incorrect results almost every time it is called.

Peaker then posted his own Haskell solution:

import Data.Array.IO
import Control.Monad
import Control.Concurrent

bool t _f True = t
bool _t f False = f

swap arr i j = do
  (iv, jv) <- liftM2 (,) (readArray arr i) (readArray arr j)
  writeArray arr i jv
  writeArray arr j iv

parallel fg bg = do
  m <- newEmptyMVar
  forkIO (bg >> putMVar m ())
  fg >> takeMVar m

sort arr left right = when (left < right) $ do
  pivot <- read right
  loop pivot left (right - 1) (left - 1) right
  where
    read = readArray arr
    sw = swap arr
    find n pred i = bool (find n pred (n i)) (return i) . pred i =<< read i
    move op d i pivot = bool (return op)
                        (sw (d op) i >> return (d op)) =<<
                        liftM (/=pivot) (read i)
    loop pivot oi oj op oq = do
      i <- find (+1) (const (<pivot)) oi
      j <- find (subtract 1) (\idx cell -> cell>pivot && idx/=left) oj
      if i < j
        then do
          sw i j
          p <- move op (+1) i pivot
          q <- move oq (subtract 1) j pivot
          loop pivot (i + 1) (j - 1) p q
        else do
          sw i right
          forM_ (zip [left..op-1] [i-1,i-2..]) $ uncurry sw
          forM_ (zip [right-1,right-2..oq+1] [i+1..]) $ uncurry sw
          let ni = if left >= op then i + 1 else right + i - oq
              nj = if right-1 <= oq then i - 1 else left + i - op
          let thresh = 1024
              strat = if nj - left < thresh || right - ni < thresh
                      then (>>)
                      else parallel
          sort arr left nj `strat` sort arr ni right

main = do
  arr <- newListArray (0, 5) [3,1,7,2,4,8]
  getElems arr >>= print
  sort (arr :: IOArray Int Int) 0 5
  getElems arr >>= print

This solution also turned out to be buggy. Firstly, it contains a more subtle concurrency bug causes it to return incorrect results only occassionally. Peaker corrected this bug to give the following code:

import System.Time
import System.Random
import Data.Array.IO
import Control.Monad
import Control.Concurrent
import Control.Exception
import qualified Data.List as L

bool t _ True = t
bool _ f False = f

swap arr i j = do
  (iv, jv) <- liftM2 (,) (readArray arr i) (readArray arr j)
  writeArray arr i jv
  writeArray arr j iv

background task = do
  m <- newEmptyMVar
  forkIO (task >>= putMVar m)
  return $ takeMVar m

parallel fg bg = do
  wait <- background bg
  fg >> wait

sort arr left right = when (left < right) $ do
  pivot <- read right
  loop pivot left (right - 1) (left - 1) right
  where
    read = readArray arr
    sw = swap arr
    find n pred i = bool (find n pred (n i)) (return i) . pred i =<< read i
    move op d i pivot = bool (return op)
                        (sw (d op) i >> return (d op)) =<<
                        liftM (/=pivot) (read i)
    swapRange px x nx y ny = if px x then sw x y >> swapRange px (nx x) nx (ny y) ny else return y
    loop pivot oi oj op oq = do
      i <- find (+1) (const (<pivot)) oi
      j <- find (subtract 1) (\idx cell -> cell>pivot && idx/=left) oj
      if i < j
        then do
          sw i j
          p <- move op (+1) i pivot
          q <- move oq (subtract 1) j pivot
          loop pivot (i + 1) (j - 1) p q
        else do
          sw i right
          nj <- swapRange (<op) left (+1) (i-1) (subtract 1)
          ni <- swapRange (>oq) (right-1) (subtract 1) (i+1) (+1)
          let thresh = 1024000
              strat = if nj - left < thresh || right - ni < thresh
                      then (>>)
                      else parallel
          sort arr left nj `strat` sort arr ni right

timed act = do
  TOD beforeSec beforeUSec <- getClockTime
  x <- act
  TOD afterSec afterUSec <- getClockTime
  return (fromIntegral (afterSec - beforeSec) +
          fromIntegral (afterUSec - beforeUSec) / 1000000000000, x)

main = do
  let n = 1000000
  putStrLn "Making rands"
  arr <- newListArray (0, n-1) =<< replicateM n (randomRIO (0, 1000000) >>= evaluate)
  elems <- getElems arr
  putStrLn "Now starting sort"
  (timing, _) <- timed $ sort (arr :: IOArray Int Int) 0 (n-1)
  print . (L.sort elems ==) =<< getElems arr
  putStrLn $ "Sort took " ++ show timing ++ " seconds"

This solution does run correctly on small inputs but increasing the problem size to 1,000,000 elements results in a stack overflow. Two attempts were made to diagnose this bug, here and here, but both turned out to be wrong. The bug is actually in the getElems function of the Haskell standard library which stack overflows on long arrays.

Surprisingly, more bug fixing seems to have culminated in the world's first parallel generic quicksort written in Haskell. Furthermore, the resulting Haskell solution is only around 55% slower than the equivalent F# solution. Note that this requires the latest GHC that was only released in recent weeks.

The rise and fall of OCaml

2010-08-01T05:39:00.000-07:00

After over 3 years, The OCaml Journal is finally closing down. New subscriptions offer access to the 75 existing articles and only a few more articles will be published, to honour outstanding subscriptions.

This marks Flying Frog Consultancy Ltd. officially pulling out of the OCaml market as our remaining OCaml products (such as the OCaml for Scientists book) require no on-going maintenance.

This change has, of course, come about due to a dramatic fall in our revenue from OCaml products since 2007. This is partly because we decided in 2007 to jump ship to Microsoft's new F# programming language. However, the same trend can be seen in the rate of posts to the OCaml mailing lists, which has fallen 60% since 2007 and has now reached its lowest level for a decade:

We blame the inability of OCaml's garbage collector to allow threads to run in parallel as the primary reason for this mass exodus. OCaml was an awesome tool in the late 1990s and, by 2004, many people were finding the OCaml language from benchmark results that showed it to be one of the fastest languages available. Ironically, that was largely due to the superior performance of OCaml's garbage collector but that same garbage collector is now a serious impediment to parallel programming on today's multicore machines. Coupled with advancements like monomorphization on .NET and LLVM-based backends with vastly better code generation like GHC, OCaml has been left in the dust. Consequently, the majority of OCaml programmers who had chosen it for performance reasons (many of whom were research scientists) are leaving.

OCaml also suffers from several other problems including the cumbersome FFI that requires separate C stubs and the lack of a native-code REPL. However, all of these problems could be addressed by developing a new VM. Indeed, at only 2kLOC our own HLVM project has demonstrated just how easy LLVM makes it to build a new high-performance multicore-capable VM for OCaml-like languages. We believe a complete replacement could be developed in just a few months but, sadly, nobody has done any work on this beyond our own tentative attempts with HLVM.

On the other hand, there was never any onus on an academic institution to create such a useful tool in the first place so it is important to remember that OCaml was only valuable thanks to the hard work and dedication of its academic creators. Thanks INRIA!

Mathematica 7 review: buggy but fun!

2010-07-31T12:25:00.001-07:00

At only £195+VAT, the Mathematica 7 Home Edition is just too tempting as an executive toy but it still seems to be far too buggy to be taken seriously. After just a few hours of playing around, a variety of bugs have become apparent. Every Mathematica user fears the dreaded error box that marks the loss of all unsaved data:

Fortunately, a really serious bug in the FFT routines of Mathematica 7.0.0 was fixed for the 7.0.1 release. This was a showstopper for customers of our time-frequency analysis add-on. The severity and ubiquity of this bug really highlights just how little quality assurance goes into Wolfram's software which, in turn, goes to show how a unimportant correctness is in the creation of commercially-successful software products, even if they are used in aerospace engineering!

The first bug is in the new support for parallelism in Mathematica. Although it is only supposed to handle 4 cores, it produces pages of errors when run on a machine with more cores such as our 8 core system:

Half of the spawned kernels die and the errors are about miscommunications. Looks like it was not tested on anything beyond a quadcore.

Another bug appears when trying to load the example matrices as described in Mathematica's own documentation:

And there seems to be a nasty bug in the MinCut function that is supposed to find partitions that break the fewest edges because this function causes an access violation (aka segmentation fault) every time we try to use it:

A question on Stack Overflow highlighted another bug, this time in Mathematica's regular expression engine which crashes on non-trivial inputs, again losing all unsaved data:

So, although we do not hesitate to recommend Mathematica as an executive toy or even fun educational software for children, we still cannot recommend Mathematica for serious use due to the pervasiveness of serious bugs in this software. On the other hand, Mathematica's commercial success really demonstrates just how unimportant quality is in the software world.

As an aside, it is interesting to note that Mathematica is one of the languages with a bleak future in the face of multicore computing due to fundamental design issues. Specifically, the Mathematica system is largely built around the Mathematica language which is a term rewrite language evaluated by repeated substitution using symbolic replacement rules. The rules are, by definition, read and written via one giant global rule table and, consequently, direct concurrent use from multiple threads would introduce massive contention for the global table. The only viable solution is to duplicate the entire system separately on each core and communicate via message passing. This foregos the benefits of shared memory offered in a highly-efficient hardware-accelerated form on all multicore computers and, consequently, parallelism in Mathematica is orders of magnitude slower than in other languages. For example, even ignoring the distribution of definitions required to use parallelism in Mathematica, its ParallelTable construct is over 250× slower than the equivalent Array.Parallel.init in F#.

Still, Mathematica's accompanying literature alone justifies the price of just £195!

F#unctional Londoners meetup lecture (28th July 2010)

2010-07-27T15:44:00.000-07:00

Zach Bray of Trayport and Jon Harrop of Flying Frog Consultancy Ltd. will be presenting lectures at Skills Matter eXchange London (UK) at 6:30pm on Wednesday 28th July 2010.

Many thanks to Carolyn Miller and Phil Trelford for organizing F#unctional Londoners Meetup Group, an excellent series of events!

Haskell's hash tables revisited: part 2

2010-07-22T14:53:00.000-07:00

Our previous blog post contained several benchmark results comparing the new GHC 6.12.3 with F#. We have since discovered some other points of interest regarding this benchmark.

Firstly, the results for Haskell rely on the use of a garbage collector that prevents parallelism. If the more modern multicore-friendly GC is used (by compiling with -threaded and running with +RTS -N8) then the time taken increases from 4.5s to 10.6s. This is over 2× slower than before and now over 13× slower than F#. Naturally, the F# was already using the multicore-capable .NET garbage collector so this was an unfair bias in favor of Haskell.

Secondly, the Haskell code exploits an algorithmic optimization on the assumption that the keys are unique. This is often not the case in practice and, again, the F# code did not exploit such an assumption so this was another unfair bias in favor of Haskell. A fairer comparison may be obtained by changing from the insert function to the update function in the Haskell code. Again, this incurs a substantial performance penalty and increases the time taken to 20.6.

With these alterations, Haskell becomes 26× slower than F# on this benchmark even with the latest GHC. Although these latest improvements are a step in the right direction, it seems that Haskell still has a long way to go before attaining competitive performance with mutable data structures.

Haskell's hash tables revisited

2010-07-18T16:24:00.000-07:00

Update: We have since discovered that these results were biased towards Haskell.

Mikhail Glushenkov recently announced the Haskell Platform 2010.2 RC for Windows. In particular, this is the first release to include a version of the Glasgow Haskell Compiler (6.12.3) that has the new garbage collector fix to address the performance problems Haskell programmers have been experiencing with mutable arrays of boxed values over the past 5 years, such as the spines of hash tables.

Naturally, we couldn't resist benchmarking the new release to see if it lives up to the promise of decent hash table performance. Even though this installer for the Haskell Platform is just a release candidate, we found that it installed smoothly and ran correctly first time.

First up, a repeat of our previous benchmark which inserted 10,000,000 bindings with int keys mapping to int values into an initially-empty hash table:

GHC 6.12.1: 19.2s
GHC 6.12.3: 4.48s
F# .NET 4: 0.8s

The new version of GHC is clearly a substantial improvement over previous versions in this context, completing this benchmark over 4× faster than its predecessor. The fastest Haskell is still 5.6× slower than F# but that is a more reasonable performance difference than before.

Altering the benchmark to build five hash tables containing 5,000,000 bindings each with float keys and values and using the floor or truncate functions as the hash function changes the relative performance considerably:

GHC 6.12.1: 131s
GHC 6.12.3: 30.2s
F# .NET 4: 2.98s

Here, the old GHC is a whopping 44× slower than F# and the latest GHC is still 10× slower.

Surprisingly, this turns out to be a 3 year old performance bug, this time in the implementation of basic numeric functions. Fortunately, this can be fixed simply by annotating the type of the truncate function. This gives the following performance:

GHC 6.12.1: 43.8s
GHC 6.12.3: 17.1s
F# .NET 4: 2.98s

The latest Haskell is now back to being only 5.7× slower than F#.

Here's the new F# code:

let cmp =
  { new System.Object()
      interface System.Collections.Generic.IEqualityComparer with
        member this.Equals(x, y) = x=y
        member this.GetHashCode x = int x }
for _ in 1..5 do
  let m = System.Collections.Generic.Dictionary(cmp)
  for i=5000000 downto 1 do
    m.[float i] <- float i
  printfn "m[42] = %A" m.[42.0]

And here's the new Haskell code:

import qualified Data.HashTable as H
import GHC.Float

act 0 = return ()
act n = do
  ht <- H.new (==) (fromIntegral . (truncate :: Double -> Int)) :: IO (H.HashTable Double Double)
  let loop 0 = return ()
      loop i = do
          H.insert ht (fromIntegral i) (fromIntegral $ i+n)
          loop (i-1)
  loop (5*(10^6))
  ans <- H.lookup ht 42.0
  print ans
  act (n-1)

main :: IO ()
main = act 5

Mono 2.4 still leaking like a sieve

2010-07-12T17:04:00.000-07:00

How fast are hash tables in Mono 2.4 compared to .NET 4? An excellent question but one which led us to another trivial program that leaks memory on Mono but not on .NET (we previously gave a simple stack implementation written in F# that leaked memory on Mono 2.2).

We tried to use the following benchmark program to measure Mono's performance when filling a hash table from empty with float keys and values:

for i in 1..10 do
  let t = System.Diagnostics.Stopwatch.StartNew()
  let m = System.Collections.Generic.Dictionary()
  let mutable x = 0.0
  for i=1 to 10000000 do
    m.[x] <- x
    x <- x + 1.0
  printfn "m[42] = %g" m.[42.0]
  printfn "Took %gs\n" t.Elapsed.TotalSeconds

Here's the output of that program on Mono 2.4:

$ mono HashTableBenchmark.exe
m[42] = 42
Took 3.45099s
m[42] = 42
Took 3.2431s
m[42] = 42
Took 3.39288s
m[42] = 42
Took 27.2352s

Unhandled Exception: System.OutOfMemoryException: Out of memory
  at (wrapper managed-to-native) object:__icall_wrapper_mono_array_new_specific (intptr,int)
  at System.Collections.Generic.Dictionary`2[System.Double,System.Double].Resize () [0x00000]
  at System.Collections.Generic.Dictionary`2[System.Double,System.Double].set_Item (Double key, Double value) [0x00000]
  at <StartupCode$HashTableBenchmark>.$Program.main@ () [0x00000]

Even more surprisingly, this program still dies with out of memory even if we explicitly Clear the hash table after every iteration!

Animated Mathematica functions

2010-07-12T15:33:00.001-07:00

Here's a fun web page from Wolfram Research that has animations for a bunch of Mathematica's built-in functions.

Book review: Mathematica Cookbook by Sal Mangano

2010-07-12T05:49:00.000-07:00

O'Reilly just published a new book, the Mathematica Cookbook, about Wolfram Research's flagship product. This book contains many interesting examples from various different disciplines. Most of these are derived from freely available examples written by other people (primarily from Wolfram Research's original Mathematica Book and also the excellent Wolfram Demonstrations Project) but the author has simplified some of the programs to make them more accessible.

However, the density of the information in this book is incredibly low. Most pages are filled with superfluous Mathematica output that is often not even described in the text:

Dozens of triples on page 15.
Page 58 lists hundreds of numbers but the text does not even describe their significance.
Page 205 lists all of the words with a subset of the letters "thanksgiv".
Page 226 is raw XML data.
Pages 264-265 are solid code that renders a snowman with circles and some dots for snow (all in black and white).
Pages 303-304 are two more pages of code to plot a snowman in 3D.
Page 321 lists all of the properties in Mathematica's polyhedron database and page 322 draws 20 polyhedra before page 324 enumerates exactly the same polyhedron properties again.
Pages 334-335 enumerate image data numerically (three times).
Page 359 displays quadrant swapping with 25x more matrix elements than necessary.
Page 360 is the Fourier transform of an image and page 361 is an apparently identical one.
Page 507 lists every chemical element and page 571 lists every property of them.
Page 553 lists every property available for financial data and page 554 lists them all over again.
Page 572 contains an empty graph.
and so on...

Many pages are devoted to TreeForm plots of trees that convey no useful information, e.g. the trees drawn on page 129 in the section about red-black trees:

Would have been nice to see red and black colored nodes or even learn how to do that using Mathematica (assuming it is possible). In particular, half of page 115 is a TreeForm view so badly laid out by Mathematica that it is unreadable.

There are also some problems with the technical content itself. For example, the section on red-black trees is a simple translation from Okasaki's excellent book "Purely functional data structures". The only new functionality Sal Mangano added is a remove function but his implementation is completely wrong.

The book is chocked full of advice about optimization. This is both good and bad. Good because Mathematica users need all the help they can get with performance because Mathematica is so slow. Bad because the best advice for a Mathematica user when performance is even vaguely relevant is to ditch Mathematica in favor of a more modern tool with better performance. For example, section 14.10 "Compiling an Implementation of Explicit Trinomial for Fast Pricing of American Options" states that "You need a very fast pricer for American options" but the fastest Mathematica code given can be a whopping 960× slower than a comparably-simple F# solution. Furthermore, it turns out that this was not written by Sal Mangano (the author of the book) but by Andreas Lauschke (a Mathematica and Java consultant) and it is a translation of MATLAB code written by Ansgar Jüngel (an academic).

There are several multi-page program listings written as plain Mathematica code with embedded comments that are difficult to read (they are not even spaced out, let alone typeset properly!) instead of prose. Page 265 is a block of code, for example:

Although the book does contain a frustrating amount of blatant filler, it is very cheap (O'Reilly) and does contain several thought-provoking examples. Whether you use Mathematica or not, you'll probably learn something useful about the state-of-the-art in the Mathematica world by skimming this book. On a higher level, you will probably learn a lot more about business if you consider what this book and the army of Mathematica devotees behind it represent. After all, there is a lot of money in starting a religion!

FWIW, here are the interesting references from the book to original sources:

Interval Computations.
Sequential and parallel sorting algorithms.
Interactive data structure visualizations.
How to write a spelling corrector by Peter Norvig (of Google).
Data structures and efficient algorithms in Mathematica by Daniel Lichtblau.
Packrat parsing.
Twisted architecture by Chris Carlson.
Histogram equalization.
The Yale face database.
A tutorial on Principal Components Analysis by Lindsay I Smith.
Generatingfunctionology by Hilbert S Wilf.
Predator-Prey dynamics with type-2 functional response by Wilfried Gabriel.
Theory of Finite Element Analysis.
Finance-related Mathematica resources from Weber & Partner.

Purely functional games

2010-07-05T01:48:00.001-07:00

A recent blog post entitled "Follow up to functional programming doesn't work" recently caused a bit of a stir, encouraging Haskell programmers to dredge up the nearest things Haskell has to real computer games. A Super Mario clone, Frag (a reimplementation of part of Quake), a Gradius clone, 4Blocks and a game that blows all of the others away called Bloxors:

This beautiful little OpenGL-based puzzle game weighs in at just 613 lines of purely functional code (many of the other games use unsafe* functions to introduce uncontrolled side effects). This is also one of the few programs that cabal install actually works on.

Check it out here!

Debunking the 100× GPU vs. CPU myth

2010-07-02T13:47:00.000-07:00

Intel recently published a paper with no less than 12 authors called Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU where they criticize the huge performance discrepancies cited by researchers publishing about General-Purpose GPU (GPGPU) programming in the context of what they call "throughput computing".

We have also noticed bad science in this domain before. We tried to reproduce the incredible results of one paper, with a view to entering this market ourselves, only to discover they had used the reference implementation of LAPACK instead of the vendor tuned implementation for their CPU that was 10× faster. Like Intel, we found that the performance advantage of a GPU was relatively modest (2.5×) given the enormous costs and liabilities of using a GPU for number crunching. However, we are fortunate to be able to simply dismiss fantastical results as irrelevant propaganda but Intel are presumably feeling the pinch as misinformed customers flock to buy nVidia's GPUs to attack problems for which a better Intel CPU would have been more appropriate.

On the other hand, the failure of manycore GPUs to attain competitive performance for all but a handful of tasks raises the question of how much general software stands to gain from the multicore revolution? Is this the end of the line for performance as we know it?

Intel's careful use of the phrase "throughput computing" is significant. Their point is that memory hierarchies are the shared headache. Applications that perform local computations in registers without need of external data can easily be made to scale extremely well. Computing Mandelbrot fractals is one example of this. For example, GPUs should excel at rendering the complex Mandelbulb fractal that was discovered in recent years:

Awesome stuff, but what is it useful for?