sutton036

Our previous post caused some controversy by questioning the validity of some commonly-held beliefs. Specifically, the beliefs that reference counting (RC) always requires less memory than tracing garbage collection (GC) and that tracing GCs require 3-4x more memory in order to perform adequately. We presented a benchmark written in Swift and OCaml and noted that the RC'd Swift implementation ran over 5x slower and required over 3x more memory than the tracing GC'd OCaml implementation. This observation disproves these beliefs in their strong form and even brings into question whether there is even any validity in the weak forms of those beliefs. After all, we have never seen any empirical evidence to support these beliefs in any form. We received a lot of criticism for that post. The vast majority of the criticism was not constructive but two valid points did arise. Firstly, although our result was anomalous it would be more compelling to see the benchmark repeated across a w...

People often assert that scope-based reference counting such as shared_ptr in C++ collects garbage “promptly” and some people define this as “collects at the earliest possible point”. For example, at the time of writing the Wikipedia page about garbage collection says: “ Compared to tracing garbage collection, reference counting guarantees that objects are destroyed as soon as they become unreachable … ”  – Wikipedia Similar claims can even be seen in published research such as the paper “ Down for the Count? Getting Reference Counting Back in the Ring ”: “Of the two fundamental algorithms on which the garbage collection literature is built, reference counting has lived in the shadow of tracing. It has a niche among language developers for whom either performance or completeness is not essential, and is unused by mature high performance systems, despite a number of intrinsic advantages such as promptness of recovery and dependence on local rather than global state.” – Blackburn...

Time taken to insert ten million int→T bindings for T as each of int , float , complex and string using F# on .NET 4.5, OCaml 3.12 and GHC 7.4.2: On a 3.4GHz Intel Core i7-3770 running Windows 7. Value types and reified generics facilitate .NET's very efficient Dictionary implementation when handling value types like int , float and complex (unmatched by any other language/VM including C, C++ and Java). F# is 50% faster than OCaml and Haskell using the reference type string perhaps because the .NET write barrier is significantly more efficient. Note: we use "int" to refer to ordinary 32-bit ints in F# and Haskell but 31-bit ints in OCaml. Using 32-bit ints in OCaml would be much slower because they are boxed (i.e. heap allocated).

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...

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 25 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...

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 ...

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...

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:

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 langu...

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 implementati...

Here's Markus Mottl's OCaml translation of Okasaki's purely functional leftist heap: module LeftistHeap (Element : ORDERED) : (HEAP with module Elem = Element) = struct module Elem = Element type heap = E | T of int * Elem.t...

For around 30 years, the ML family of languages have been characterised by several unusual features including a novel and powerful higher-order module system. This language feature was pioneered by Dave MacQueen in the early 1980s and found its way into the Standard ML and OCaml languages. Higher-order modules allow one module to be parameterized over another module in the form of functors that map modules to modules. Higher-order modules turn out to be especially useful for parameterizing concrete data structures over more primitive data structures. Perhaps the most compelling application of higher-order modules comes from graph theory, where they allow algorithms over graphs to be abstracted over the concrete data structures used to represent the graphs. This application was discussed in our most recent OCaml Journal article " The A* algorithm " that describes a generalization of Dijkstra's shortest path algorithm that is widely used for route finding in game AI. Th...

We just finished a week of hell after trying and failing to upgrade from Debian Lenny to Debian Squeeze. None of the Debian Linux kernels working correctly on our stock Dell PowerEdge T605 hardware was the first major headache and KDE 4 was the second. In our 10 years of using Linux its user unfriendliness seems to be as poor as ever. With the latest KDE 4, it seems that KDE itself has also gone from bad to worse. We migrated from Gnome to KDE many years ago because we found Gnome to be buggy and user unfriendly only to discover that KDE was only superficially stable. KDE 4 takes this to a new level and our log files are filled with records of segfaults. KMail was once riddled with serious bugs but these were ironed out in KDE 3 and it became a usably-stable e-mail client a few years ago and served us well. Not so with KMail from KDE 4, which regularly segfaults, losing and/or corrupting data and has consistently failed even to move significant numbers of e-mails around within its own ...

Miguel de Icaza of the Mono project made two surprise announcements in a recent blog post : "We are working to improve our support for F# and together with various groups at Microsoft we are working to improve Mono's compatibility with the CLR to run IronPython, IronRuby and F# flawlessly in Mono. Supporting F# will require some upgrades to the way that Mono works to effectively support tail call optimizations." "we continue to work on integrating LLVM [better use LLVM to produce better code, use it in more places where the old JIT was still required and expand its use to be used for AOT code]" We have been pushing for these developments (F# support and an LLVM backend) for over a year now and it is very exciting to hear that the Mono team are taking this seriously. F# is the future of .NET and building upon LLVM offers huge potential not only for improving upon the performance of Mono's code generator but also in improving LLVM itself, which is now the ...

For a bit of fun, we recently ran programs to determine the current sizes of our company's OCaml and F# code bases. This includes the code we use in-house for everything from web analytics to accountancy as well as the code behind our commercial products . We found 345kLOC of OCaml code and 171kLOC of F# code. In comparison, Jane St. Capital now have around a million lines of production OCaml code and Citrix have 130kLOC of production OCaml code .

Our new book F# for Technical Computing has been published and is now available for order! This is currently the only published book to cover the latest version of the F# programming language and also covers the following exciting topics: Windows Presentation Foundation for interactive 2D and 3D graphics. The Task Parallel Library for shared-memory parallel programming on multicores and MPI for distributed parallelism on clusters. LINQ for the dissection of XML data. Sequence expressions. Asynchronous workflows for concurrent programming. Functional design patterns (tail calls, untying the recursive knot and continuation passing style). Purely functional data structures (balanced trees, tries, lazy streams and queues). Named and optional arguments. .NET interfaces including IEnumerable, IComparable and IDisposable. Performance in the context of caches and multicores. Reflection. Every graph in the book was created with our own F# for Visualization library and the complete source ...

While asking on the OCaml mailing list about the relative merits of our HLVM project, David McClain described a computation that he had been required to perform in the context of scientific computing in the past: "I remember dealing with stacks of images taken from an infrared imaging sensor -- perhaps 256 images, each of which is, say 512 x 512 pixels. I needed to obtain median pixel values from the stack and produce one median image..." This problem is easily solved in both OCaml and F# using idiomatic functional programming. For example, the following is a one-line solution written in OCaml: Array.map (Array.map (fun gs -> Array.sort compare gs; gs.(m/2))) images This simply sorts each pixel's sequence into non-descending order and extracts the middle (median) pixel, mapped across the columns and then the rows of the image. This tiny implementation solves David's example with 2 26 pixels in 32 seconds, which is fast enough for many applications. However, the ...

The Burrows-Wheeler Transform (BWT) is a block-sorting data compression algorithm that acts as a preconditioner to dramatically improve the compression ratios of subsequent compression phases in many cases. This algorithm is the core of the bzip2 data compression utility that is ubiquitous on Unix and, in particular, is often much more effective than zip and gzip. The core of the BWT algorithm is easily written in F# : let cmp (str: _ array) i j = let rec cmp i j = if i=str.Length then 1 else if j=str.Length then -1 else let c = compare str.[i] str.[j] in if c 0 then c else cmp (i+1) (j+1) cmp i j let bwt (str: byte array) = let n = str.Length let a = Array.init n (fun i -> i) Array.sortInPlaceWith (cmp str) a Array.init n (fun i -> str.[(a.[i] + n - 1) % n]) However, this implementation is very slow and, in particular, is many times slower than the extremely heavily optimized C implementation found in the bzip2 program. The main ca...

Recent articles in the OCaml and F#.NET Journals derived high-level implementations of QR decomposition via Householder reductions. This numerical method has many applications, most notably in the computation of best fit parameters of linear sums. Imperfections in OCaml The OCaml programming language allows this algorithm to be expressed very elegantly in only 15 lines of code: # let qr a = let m, n = Matrix.dim a in let rec qr_aux k q r qa = if k = n then q, Ma...