sutton036

Some objective quantitative measurements I once posted on Usenet: Jon Harrop wrote: > Andreas Rossberg wrote: >> That is a wild claim, and I doubt that you have any serious statistics >> to back it up. > > Here are some statistics on the proportion of lines of code devoted to > type annotations from 175kLOC of production OCaml and 5kLOC of production > Haskell: > > OCaml: > Hevea 9.0% > ADVI 8.6% > FFTW3 5.2% > Unison 3.5% > MLDonkey 2.5% > LEdit 1.4% > MTASC 0.0% > HLVM 0.0% > > Haskell: > XMonad 19% > Darcs 12% For further comparison, here are some statistics for compilers written in OCaml and Standard ML: OCaml: 6.3% of 217kLOC MosML: 13% of 69kLOC

Eight years ago I answered a question on Stack Overflow about the suitability of OCaml and Haskell for soft real-time work like visualization: " for real-time applications you will also want low pause times from the garbage collector. OCaml has a nice incremental collector that results in few pauses above 30ms but, IIRC, GHC has a stop-the-world collector that incurs arbitrarily-long pauses " My personal experience has always been that RAII in C++ incurs long pauses when using non-trivial data (i.e. nested, structured, collections of collections of collections, trees, graphs and so on), non-deferred reference counting has the same problem for the same reason, tracing garbage collectors like OCaml work beautifully but there are many notoriously bad tools like Java that have given tracing garbage collection a bad name. Now that I am revisiting this issue I am surprised to find many individuals and organisations repeating exactly the same experimental tests that I did and coming...

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

The way software developers cling to folklore and avoid proper experimental testing of hypotheses really bothers me. I think perhaps the worst branch of computer science still riddled with myths and legends is memory management. Despite over half a century of research on garbage collection showing that reference counting is inferior to tracing garbage collections algorithms (even when almost all GC research restricts consideration to Java when much better algorithms have been known for years) there are still many people who claim otherwise. C++ developers obviously still believe that reference counted smart pointers are superior to tracing garbage collection but now other people are doing it too. People who should know better. This situation recently reared its ugly head again when Apple released a promising new programming language called Swift that shuns tracing garbage collection in favor of reference counting. Now, there are logical reasons for Apple to have chosen reference count...

Xavier Leroy’s standard lecture on threads post from the caml-list in 2002 seems to have disappeared from the INRIA archives so I am reproducing it here for anyone who is interested. This post is of historical interest because it explains why OCaml has no support for multicore parallelism to this day (twelve years after the release of the first consumer-level multicore CPUs). Date: 2002-11-25 (10:01) From: Xavier Leroy <xavier.leroy@i...> Subject: Re: [Caml-list] Why systhreads? It seems that the annual discussion on threads started again.  Allow me to deliver again my standard lecture on this topic. Threads have at least three different purposes: 1- Parallelism on shared-memory multiprocessors. 2- Overlapping I/O and computation (while a thread is blocked on a network    read, other threads may proceed). 3- Supporting the "coroutine" programming style    (e.g. if a program has a GUI but performs long computations,     using threads is a nicer wa...

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

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

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

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

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

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

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

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

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 .

We recently completed a translation of our famous ray tracer language comparison to HLVM . The translation is equivalent to the most highly optimized implementations written in other languages and this allows us to compare HLVM with a variety of competing languages for the first time. The results are astonishing. Running the benchmark with the default settings (level=9, n=5 to render 87,381 spheres at 512×512) on 32-bit x86 gives the following times for different languages: These results show that HLVM already provides competitive performance for a non-trivial benchmark. HLVM took 6.7s whereas C++ (compiled with g++ 4.3.3) took only 4.3s and Haskell (compiled with GHC 6.12) took 13.9s. However, cranking up the level parameter to 12 in order to increase the complexity of the scene, rendering a whopping 5,592,405 spheres, we find that HLVM blows away the other garbage collected languages and is even able to keep up with C++: This remarkable result is a consequence of HLVM's space-ef...

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