Archive for

October 2009

Finally found the ghci bug on Snow Leopard

After much digging through otool output and tracing Haskell code with dtrace, log messages, and gdb, I finally found the cause of the SIGBUS errors with ghci on Snow Leopard. At the end, only a tiny change was required[1]: the homegrown dynamic linker of ghci had simply ignored a relocation type that ld on Snow Leopard chose to use.

What this really shows again is that re-implementing parts of basic infrastructure in an ad hoc manner always comes back to bite you. Such infrastructure is usually full of low-level, platform-dependent details, which you are bound to get wrong once in a while and then it can be rather involved to find the problem. In this case, the relocation of the memory access of a bit of C code in GMP, reading a global variable, went wrong. As a result, the wrong memory location was accessed, which happened to contain a NULL pointer. Upon dereferencing the NULL, the program crashed.

All of this was further obscured by the fact that the homegrown linker approach of ghci implies that we have two copies of the basic libraries in memory and in use at the same time. One copy has been statically linked with the ghc executable and the second copy is dynamically loaded by ghci. The relocation in the statically linked copy was perfectly fine, but the relocation in the dynamically loaded one was broken.

[1] http://www.haskell.org/pipermail/cvs-ghc/2009-October/050863.html

Filed under  //  ghc   haskell   snow leopard  
Posted

Data-oriented programming and the vectorisation transformation

I just realised that the data layout and the resulting code organisation in data-oriented programming, as proposed for games design, in many aspects resembles the data layout and code organisation favoured by the vectorisation transformation that is at the core of Data Parallel Haskell.  This should not be surprising as both have similar goals, namely to maximise data throughput, to minimise stalls by utilising the memory hierarchy, and to maximise parallelism.

However, the parallels are interesting given the very different origins of both approaches.  The big difference is of course that data-oriented programming is a design methodology for programmers, whereas the vectorisation transformation is a program transformation automatically applied by a compiler.  Nevertheless, we may regard the vectorisation transformation as a program transformation that turns purely functional code into code that is structured in a data-oriented manner, where the layout of bulk data shapes the organisation of the code.

This raises the question of how useful nested data parallel programming and the vectorisation transformation may be to games programming.

Filed under  //  data-orientation   dph   vectorisation  
Posted

Fun with higher-order functions in C and Objective-C

The latest release of Mac OS X (Snow Leopard) came with an upgrade to the C and Objective-C languages, adding lambda abstractions — which they call blocks. Matt Gallagher has a nice blog post that describes some of the trickier aspects of blocks: http://cocoawithlove.com/2009/10/ugly-side-of-blocks-explicit.html

Interesting is the function 'newDoubleToIntComparison' (in Section "Declaring a block that returns a block"), which is a curried[1] version of 'compareDoubleToInt'. Together with the explicit memory management for returned blocks and the need for involved type annotations and casts, it becomes clear why functional languages like Haskell make curried functions the default as well as support garbage collection and type inference out of the box.

[1] http://en.wikipedia.org/wiki/Currying

Filed under  //  blocks   objective-c  
Posted

Multicore Haskell Now!

Don Stewart summarised the state of play of parallel programming in Haskell at "ACM Reflections | Projections 2009". He covers strategies, Concurrent Haskell, STM, and Data Parallel Haskell: http://donsbot.wordpress.com/2009/10/17/multicore-haskell-now-acm-reflections...

Filed under  //  dph   haskell   multicore   parallelism   stm  
Posted

Don Stewart's talk on Domain Specific Languages and Haskell

Don argues in favour of domain-specific languages for high-performance computing. Not surprisingly, he suggests that Haskell is well suited as a host for realising such domain-specific languages as embedded languages: http://donsbot.wordpress.com/2009/10/16/lacss-2009-domain-specific-languages-...

Filed under  //  edsl   haskell   parallelism  
Posted

The Status of the P Versus NP Problem

The current issue of CACM (Communications of the ACM) has a very nice summary of the long-standing question of whether nondeterministic polynomial-time problems (NP) can also be solved in polynomial-time (P). In particular, it discusses the implications of this question on computing and other scientific disciplines in some detail: http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-prob...

Filed under  //  complexity theory  
Posted

Parallelism /= Concurrency

Simon Marlow posted an instructive blog article disentangling the widespread confusion about the relationship between parallelism and concurrency: http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/

Filed under  //  concurrency   parallelism   purity  
Posted

The insanity of software patents

There is plenty of coverage on how illicit copying of software harms the software industry, but little is told about how Patent Pirates turn to a modern form of extortion: http://arstechnica.com/tech-policy/news/2009/10/company-that-won-585m-from-mi...

Filed under  //  badpatents  
Posted