sutton036

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

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

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

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

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