Planet Fp-Syd

In my day job I do Linux embedded work and as people in the embedded world know, Linux is a pretty commonly used embedded OS. Today I was evaluating a new board and found it had an Intel graphics chip that was not properly detected by Ubuntu 9.10. The ever trusty lspci said this:

  00:02.0 VGA compatible controller: Intel Corporation System Controller Hub
        	(SCH Poulsbo) Graphics Controller (rev 07)

We all know that Intel employs a bunch of well known Xorg developers, so this shouldn't be a problem, right?

Unfortunately, it is a problem. Intel's offering for this chipset is the Intel® Embedded Graphics Drivers web page where they offer a 124 megabyte download (registration required). After registration you get to choose which driver pack you want and which OS you are downloading it for. Ubuntu was not on the list and neither was Debian. I chose Fedora 10 (released in 2008) as that was the most recent one.

Now, you can image my surprise when the driver download for Fedora Linux contained just four files:

  Archive:  /tmp/IEGD_10_3_GOLD.zip
      testing: UsersGuide_10_3_1525.pdf   OK
      testing: IEGD_10_3_GOLD_1525.exe    OK
      testing: IEGD_SU_10_3_GOLD.pdf      OK
      testing: RELNOTES_10_3_1525.txt     OK
  No errors detected in compressed data of /tmp/IEGD_10_3_GOLD.zip.

Yep, thats right, the driver download for Fedora Linux contains two PDF files, a text file and an executable installer for Windows.

Being the curious (and paranoid) type I decided to explore this further, by running the installer under WINE in a chroot. After the installer you get left with several metric craploads of Java Jar files, and another windows executable iegd-ced.exe that supposedly configures this nightmare. I ran it (again, under WINE in a chroot) but it didn't seem to do anything sensible or worthwhile so I looked around amongst the other installed files and found IEGD_10_3_Linux.tgz.

Inside that tarball there are a bunch of Xorg library binaries (for several different versions of Xorg), a large chunk of source code that gets compiled into the Linux kernel and even better yet, a couple of Microsoft Visual Studio project files. WTF?

Unbe-fscking-lievable. Needless to say, I will avoid any hardware which uses this chipset and any other hardware that requires binary only kernel blobs packaged this badly. Doing so makes my life easier.

The people at Intel who thought this was a good idea must have their own personal mother-lode of stupid.

Goanna version 1.2 has been released. Download it now.

The major change is More Checks, in fact 40% more than were previously available in v1.1. Over the next few months we will continue to add new checks with each release. You can expect to see up to 100 additional high quality checks within the coming 6 months, which as usual will be free for all existing customers. Additionally, should you require a 30 day Trial Extension for your version 1.2 update please complete this trial extension request form.

We are also very pleased to announce the Beta release of Goanna for Command Line. This new command line version enables more flexibility and freedom for those wishing to integrate our powerful C/C++ static analyzer into their own development process. The Beta is currently available for Linux users and a version for Windows users is scheduled to be available in May. Linux users can now access a fully gcc-compatible solution integrated with over 60 classes of flow-sensitive quality checks to detect critical bugs as early as possible in the development cycle.

Inter-procedural analysis is also well under way, so stay tuned for a public Beta release soon!

We’re proud to have been selected for simultaneous shipment of our Goanna static analysis extension with Microsoft Visual Studio 2010. Here is a short introductory video demonstrating our Visual Studio 2010 integration, and we’re on schedule for April release:

We have some further news regarding recent developments (more high quality checks being one) and we’ll be posting more information next week.

The Australian Federal Minister for Communications, Stephen Conroy, may not actually be corrupt; I certainly have no evidence that he is, but a number of recent incidents sure look like corruption to me. For instance:

• Conroy's recommendation of a former ALP Staffer for a highly paid senior position (government relations) with the National Broadband Network an organisation operating in the area of Conroy's ministry.
• Conroy playing golf with billionaire media mogul James Packer on the same day the government announced a $250 million licence fee rebate for free-to-air television stations (one of which is owned by Packer).
• Conroy skiing with media mogul Kerry Stokes in Colorado a month before the $250 million licence fee rebate was announced. James Packer and Kerry Stokes are the owners of 2 of the 3 main non-government free-to-air television stations.

The real irony is that under Conroy's proposed scheme to filter the internet in Australia comments like this blog entry may end up being censored. The problem with Conroy's filter is not that it filters porn, but rather that the list of what is being filtered is secret and hence could easily include web sites which contain comments which the government or the Minister for Communications want silenced.

I recently wrote about profiling sparse-matrix vector multiplication implemented with Data Parallel Haskell.  Let's take this a step further and look at a program parallelised with package parallel, instead of Data Parallel Haskell.  Specifically, we look at the dense matrix-matrix multiplication benchmark of the parallel section of the nofib benchmark suite.  This benchmark uses a linewise version of the torus-based Gentleman algorithm implemented with vanilla Haskell lists.  As we see in the following profile, the algorithm parallelises very well on two cores.  It also has a low allocation rate; hence, there is little garbage collection.

In the above profile and that of the sparse-matrix vector multiplication that I showed in my previous post, the width of the time slices of the mutator threads and of garbage collection are determined by the wall clock time of the run-thread/stop-thread and gc-start/gc-end events, respectively.  These events are generated by the Haskell thread scheduler and do not —they cannot— take the OS scheduling of the Haskell Execution Contexts (HECs) running Haskell threads into account.  In other words, a Haskell thread may be scheduled on a HEC for a long time, but if the HEC itself (i.e., the operating thread on which it executes) is descheduled by the operating system, then the Haskell thread still won't make any progress.  To visualise this effect, the custom instruments used here also support graphing the virtual time that expired in a time slice.  The following profile is a slightly magnified version of the initial portion of the previous profile, where the height of a mutator time slice indicates its virtual extent.  The screenshot also shows the configuration pane for one mutator track.  The virtual extent of time slices in the garbage collection pane can also be displayed in this alternative form, although that is not shown here.

The custom instruments for GHC provide addition information that is by default not displayed in the track pane, including the wall clock percentage during which the runtime performs garbage collection and the percentage of utilisation of the mutators threads.  However, all information is accessible via Instrument's tabular detail view.  In particular, the library function GHC.Exts.traceEvent can be used to inject user-defined messages into the event stream.  In the DPH benchmarking framework, we use this for example to delimit the start and end of the benchmark payload, as opposed to benchmark set up, data generation, and tear down code.  The following snapshot shows part of the detail view for the sparse-matrix vector multiplication benchmark, where the event indicating the start of benchmarking is highlighted.

By clicking on the user message events in the detail view, we can easily mark the relevant section of the profile — it is the section highlighted in blue.  Below, we see that the sequential part of the profile is only part of the set up, but not of the benchmarked code.

If you like to try for yourself, download the trace template GHC HEC 2-core and use it in Instruments.

A current caveat: Instruments supports zooming the track views horizontally (on the time axis) with a slider.  Unfortunately, in version 2.0.1 of Instruments, the maximum resolution is not sufficient to see the exact relative timing of mutator and garbage collection time slices if garbage collection is very frequent.  Moreover, when using the Block Graph style, blocks that are very closely spaced may be coloured very lightly or appear transparent — if you are suspicious of a section that seems to show no activity in a profile, use the Peak Graph style to double check.  Instruments collects all the data to provide a better resolution; it's just a matter of supporting a wider range in the zoom slider.  (If anybody knows a work around for that, please post it in the comments.)

Permalink | Leave a comment  »

Permalink | Leave a comment  »

Is it ok to use chat to communicate with my wife?
If she is sitting at the next desk?
If there is a sleeping baby in between?

Is any of this relevant if she laughs?

Almost two decades ago, when I was at university I played bass guitar in a couple of rock bands; Golden Section and Fishtank. Both bands playing an all original set although Golden Section did cover a song by Fishtank and Fishtank had a song without lyrics but found by accident that the lyrics to the Beatles' "Lucy in the Sky with Diamonds" worked, despite our melody being different.

Recently one of my bands mates in Golden Section posted a video of Golden Section playing live at the Palais Hotel in Newcastle (Australia) in 1993. The first real glimpse of me playing bass is at 1:10.

Playing in Golden Section was just so much fun! Working up to the 1991 Newcastle University Band Competition (which we won) we were rehearsing twice a week and as a result reached a state where the band synced like clockwork. We could play light and reasonably heavy (Fishtank was heavier) and we were even a bit funky on certain songs.

I absolutely loved playing in this band. Good times, good memories.

Permalink | Leave a comment  »

I'm shopping for a laptop to run Linux on and I'm finding it a really frustrating process. I would like a high end, small form factor machine like the Dell Studio XPS 13. I've seen one of these machines in the real life and held it in my hands. It seems to be excellent quality and have the right features at a reasonable price. Unfortunately, on the Dell Australia web site, there is no option to purchase this machine with Linux pre-installed.

My current laptop is a Dell Latitude X1, and my wife has a Dell too. At work I have a Dell Precision workstation. All of these machine run Linux 100% of the time and for every single one of these machines I had to pay for a Microsoft Windows license that was never used. As most people know, Microsoft uses a small portion of its revenue to fund attacks on Linux and Free/Open Source Software like the SCO debacle and the ramming of OOXML through the ISO standards process.

Considering Microsoft's malignant presence in the computer industry and the fact that I don't use their products makes me reluctant to buy a machine with Windows pre-installed. I want to buy a laptop where I get my operating system of choice and just as importantly, I know Microsoft doesn't get any part of the money I pay.

Looking around for laptops with Linux pre-installed in Australia I found VG Computing who have a range of laptops which can be shipped with Linux. Unfortunately, their order page says that they get the machines with Windows which they remove to install Linux. I do realise that as a small vendor, there is not much that VG can do about this, but as far as I am concerned, thats a fail.

Another company thats been around for ages is Pioneer Computers but their machines always seemed a bit old, a bit under powered and a bit over priced. Looking at that site just recently I found their DreamBook Light M73 which was close to what I was looking for. Ordering machines from Pioneer with Windows XP costs $89 more than the same machine with Ubuntu. Purchased with Linux, this is genuinely a Microsoft free machine.

Taking a trip out to Pioneer in Alexandria I was able to see one up close and I must say I was disappointed. Compared to the Dell XPS 13, the DreamBook felt flimsy and poorly constructed. On top of that the DreamBook had a smaller keyboard (much like the Compaq M300 I had years ago) than than the Dell and SiS graphics whereas I was really hoping for Nvidia. Another machine crossed off the list.

In the US, there are a number vendors that sell laptops with Linux. In late November 2009 I contacted two of them, System 76 and ZaReason Inc. System 76 wasn't willing to ship to Australia for warranty reasons. ZaReason will ship to Australia, but to take advantage of any warranty work, I'd have to ship the machine to and from the US which would be rather inconvenient.

Despite the concerns over warranty, by early December 2009 I had come to the decision to purchase a ZaReason Alto 3550 with a bunch of extras like faster CPU, more RAM and a bigger disk. Unfortunately, while trying to purchase it online I ran afoul of their payment system and by the time we'd figured that out they had run out of stock.

I contacted them and asked about the ETA for new stock. They said, Dec 19th, which came and went with no new stock on the website. I contacted them again and was told another week. A week passed with no new stock so I contacted them again when I was informed that their distributor doesn't have any more of the Alto 3550 available. I would go for the Alto 2550 but that has an Intel graphics chip whereas I was hoping for an Nvidia like in the Alto 3550.

So now I have to decide, do I go with the ZaReason Alto 2550 with the Intel chip and then worry about warranty issues or do I buy the Dell locally, where I know that the support and service will be excellent and then try to get a refund for the Windows license I don't need or want.

Recently I've been hacking on Conrad Parker's sound editing, audio mangling and DJing tool Sweep. As part of my bug fixing and clean up work I ran Sweep under the Linux world's favourite memory debugging tool Valgrind. Even after running valgrind with the officially sanctioned environment variables and gtk suppressions file, the resulting 500k gzipped output file was a little shocking.

Now I'm pretty sure a number of those leaks are in Sweep, but a significant number of them seem to be in GTK+ and Glib. Since trying to differentiate the leaks in Sweep from the leaks in GTK+ was proving to be a very difficult and frustrating task I decided to look at the behaviour of a simple GTK+ program under Valgrind. The program I chose was the helloworld example from the GTK+ tutorial.

Compiling that on Ubuntu 9.10 and running it under valgrind using the following commands:

  export G_SLICE=always-malloc
  export G_DEBUG=gc-friendly
  valgrind --tool=memcheck --leak-check=full --leak-resolution=high \
    --num-callers=50 --show-reachable=yes --suppressions=gtk.suppression \
    helloworld > helloworld-vg.txt 2>&1

resulted in a memcheck summary of:

  ==22566== LEAK SUMMARY:
  ==22566==    definitely lost: 1,449 bytes in 8 blocks
  ==22566==    indirectly lost: 3,716 bytes in 189 blocks
  ==22566==      possibly lost: 4,428 bytes in 107 blocks
  ==22566==    still reachable: 380,505 bytes in 7,898 blocks
  ==22566==         suppressed: 35,873 bytes in 182 blocks

The full memcheck report is available here.

The simplest GTK+ hello world program is 100 lines of code and results in a leak report of over 8000 leaked blocks even when using the recommended valgrind suppressions file and GTK+ debugging environment variables. If someone modifies that code and adds another leak, trying to find that leak needle in the GTK+ leak haystack is going to be a needlessly difficult task.

Researching this some more I find that GTK+ is known to do a large number of allocations that are done once per program run and are never released. Furthermore the GTK+ developers seem to think this is ok and from the point of view of a user running a GTK+ program this is true. However for developers coding against GTK+ and hoping to use Valgrind to find leaks in their own code, this is a royal PITA. Leaks in the developer's code can easily be swamped and hidden by GTK+ leaks. My guess is that most people don't even bother checking unless their program's memory footprint grows over time for no good reason.

Obviously, I'm not the first to realise how hard it is too debug memory leaks in a program when the library it links against throws up so many warnings. In fact, back in 2001 a bug was raised in the GTK+ bug tracker requesting the addition of a call to be used only during debugging that would release all memory so that client programs are easier to debug. That bug has remained open and without action for over 8 years.

As far as I am concerned, this is completely unacceptable. If this was my code, I would be too ashamed to put my name on it. Edit: Being able to valgrind GTK+ client code is worth the effort and cost of changing the otherwise perfectly reasonable behaviour of not accounting for lifetime-of-the-app data structures (thanks Andrew).

Note: Anyone who wishes to comment on this can do so on reddit.

I finally got around to committing my instrumentation of the GHC runtime system with DTrace probes (commit message).  The current set of probes tracks all the events of the eventlog framework used by ThreadScope.  A detailed description of the probes is on the new Using DTrace with GHC page of the GHC developer wiki.

Permalink | Leave a comment  »

Two weeks ago, on November 19th we held the 21st meeting of FP-Syd, the Sydney Functional Programming group. The meeting was held at Google's Sydney offices and we had 22 people show up to hear our two presenters.

First up we had repeat offender Mark Wotton give us a presentation titled "Hubris : A Trojan Horse for Haskell" on his project called Hubris, a bridge between Ruby (ie Rails) and Haskell. The specific use case Mark has in mind for this bridge is call fast compiled Haskell code from Ruby web code. The code this is is available at:

  git clone git://github.com/mwotton/HaskellHubris.git
   

but requires the 6.12 release candidate of the GHC Haskell compiler.

Our second presenter for the evening was Tony Sloane who gave us an introduction to "Embedding a Rewriting DSL in Scala". Tony's DSL of interest is the Stratego Language which he is embedding in Scala using the Kiama library. Tony's particular interest seems to be in program transformation; desugaring of high level languages, evaluation by reduction rules, optimisation and source to target translation.

A big thanks to both our speakers and to Dan, Mark and Google for providing the meeting venue and the light refreshments.

FP-Syd will be having brief hiatus over the Xmas/New Year period and our next meeting will be in February.

Goanna for Visual Studio 1.1 has been released. Download  it now. Changes include:

Fixed a constructor initialization false positive.

Fixed several unused variable false positives related to complex types in C++.

Include paths can now end in a backslash.

Accelerator keys: Alt+F1 (run Goanna on the Solution) and Alt+F2 (Run Goanna on the active project).

Several new checks, including:

Comparison never holds

Comparison always holds

Switch case is unreachable

Expanded the interval analysis.

Checks are now organized by category in the settings dialog.

Underlining (”Squiggles”) of warning-relevant code in the Visual Studio text editor.

Statistics page for monitoring Goanna’s progress.

Analysis of assert() statements for variable bounds.

Improved traces.

Much more internal work has been done, laying the groundwork for inter-procedural analysis and user-defined checks. Visual Studio 2010 support is well underway.

Four years ago the Haskell' Committee was assembled, charged with the task to produce a new revision of the Haskell language standard (aka Haskell 98). There was a lot of enthusiasm and many wild ideas in the beginning, but it turned out that it was hard to agree on the scope of changes and that it was very hard to find a person willing to shoulder the rather large editorial burden that a major revision of Haskell entails.

The Committee finally decided that our only realistic chance of making progress was to break the mammoth task into smaller chunks. More concretely, we decided to evolve the language in small increments with a release every year, while rotating the committee on an annual basis to avoid burn out.[1] Whether this fine-grained evolutionary approach to language design will be successful in the long run remains to be seen. Nevertheless, the new approach helped us to make progress and to agree on a revision for this year: behold Haskell 2010!

[1] Details about The Haskell Prime Process

Permalink | Leave a comment  »

Computer scientist Donald Knuth came up with something he called the Man or Boy Test as a way of evaluating implementations of the ALGOL60 language (standardized in 1963) to distinguish compilers that correctly implemented "recursion and non-local references" from those that did not. Knuth said:

"I have written the following simple routine, which may separate the 'man-compilers' from the 'boy-compilers'."

My first attempt at solving this problem in Disciple resulted in me raising bug #148 in the DDC bug tracker with the following code:

  -- Compiler needs a little help inferring the types.
  a :: Int -> a -> a -> a -> a -> a -> Int
  a k x1 x2 x3 x4 x5
   = do    b () = do { k := k - 1 ; a k b x1 x2 x3 x4 }
           if k = 0 then x4 () + x5 () else b ()

  fn n = \() -> n

  main ()  -- Function 'a' should return -67
   = do    out = a 10 (fn 1) (fn -1) (fn -1) (fn 1) (fn 0)
           if out /= -67
               then println $ "Output was " % show out % ". Should have been -67."
               else println "Passed!"

Fiddling around with the problem a bit, I suddenly realised that the Disciple language has call-by-reference semantics by default (by way of contrast, the C programming language has default call-by-value semantics with optional call-by-reference semantics using pointers).

While chatting with Ben on IRC he suggested using a copy to create a local copy of the function parameter that gets mutated so that mutation doesn't change the value outside call frame.

Here are two correct solutions to the Man or Boy problem:

  a0 :: Int -> a -> a -> a -> a -> a -> Int
  a0 k x1 x2 x3 x4 x5
   = do   b () = do { k := k - 1 ; a0 (copy k) b x1 x2 x3 x4 }
          if k = 0 then x4 () + x5 () else b ()


  a1 :: Int -> a -> a -> a -> a -> a -> Int
  a1 k x1 x2 x3 x4 x5
   = do   m = copy k
          b () = do { m := m - 1 ; a1 m b x1 x2 x3 x4 }
          if k = 0 then x4 () + x5 () else b ()

  fn n = \() -> n

  main ()
   = do   out0 = a0 10 (fn 1) (fn -1) (fn -1) (fn 1) (fn 0)
          out1 = a1 10 (fn 1) (fn -1) (fn -1) (fn 1) (fn 0)

          println "All outputs below should be equal to -67."
          println $ "Output 0 : " % show out0
          println $ "Output 1 : " % show out1

Both of these Disciple solutions are significantly less complex than the equivalent Haskell solution.

While I have no problem with function parameters being passed by reference, I don't think its a good idea to have those parameters being mutable by default (ie with the values also changing in the calling function).

I need to play with this some more.

Over the last couple of months I've been doing a bit of hacking on an experimental compiler called DDC. This has been some of the most interesting, gratifying and challenging hacking I have done in years. Having this much fun should probably be illegal!!

I was introduced to DDC at the April 2008 meeting of FP-Syd when Ben Lippmeier, its author, gave a presentation titled "The Disciplined Disciple Compiler". The two main reasons this compiler is interesting are:

• Its written in Haskell an advanced purely functional programming language.
• The language it compiles (Disciple) has some interesting solutions to the problems of side effects and mutability.

The Disciple language is very Haskell-like but has some extra features in the type system which allows the compiler to track mutability and side effects in the type system. The important differences between the Disciple language and the Haskell language are listed on the DDC web page as:

• Strict Evaluation Order is the default, laziness is introduced explicitly.
• Type directed Field Projections complement type classing.
• All data objects support Destructive Update.
• The Effect System tracks what computational effects are being used in a program, without the need for state monads.
• The Class System ensures that effects and destructive update play nicely with laziness.
• Closure Typing is used to track data sharing, and to preserve soundness in the presence of Polymorphic Update.

Obviously a compiler that is doing all this really clever stuff has to be pretty complicated, but it still only weighs in at about 50k lines of code.

The main challenge in working on this is that i am not a very experienced Haskell programmer. There are also large chunks of the compiler doing some very complicated stuff that I don't even have a hope of understanding without reading and understanding Ben's PhD thesis.

Despite that, Ben was willing to give me commit access to the Darcs repo and I have been able to significantly reduce the number of bugs in the DDC bugtracker. Since I was already pretty familiar with the concepts of lexing and parsing as well as being familiar with Parsec (probably the most widely used parsing tool in the Haskell community) I started off fixing some simple lexer and parser bugs like:

• #91 : Require module imports (and exports) to be at the start of the module.
• #95 : Parse error with lists.
• #96 : ellipsis in list generator expressions not comprehensive enough.
• #97 : Error in parsing end of {- -} comments.
• #103 : Not able to parse 'a, b, c :: Type' style type signatures.

I then managed to hack in support for Int64 and Float64 (#106) followed by some significant re-factoring of the Parsec parser which reduced the usage of the Parsec.try construct allowing Parsec to produce much better error messages.

Once I'd done all that, I ran into a very busy time at work and didn't mess with DDC for a couple of months. When I finally got back to looking at DDC, I realised that nearly all of the remaining bugs were much deeper than the bugs I had tackled so far. Tackling these deeper bugs required a new strategy as follows:

1. Scan the bug list for reports that either had test cases already or give enough information for me to proceed.
2. Create a new darcs branch for each bug. This allowed me to work on multiple different bugs at once so that if I got stuck on any one specific bug, I could just leave it and move on to another.
3. Create a reproducible test case if one didn't exist already.
4. Create a shell script in the root directory of each branch which did make and then ran the specific test case for this specific bug.
5. Use Haskell's Debug.Trace module in conjunction with Haskell's very wonderful Show Type Class to add debug statements to the code.
6. Use the Wolf Fencing debugging technique to narrow down the problem to specific area of the code.

Once the problem had been narrowed down to a piece of code, all that remained was to develop a fix. In many cases this resulted in me asking Ben how he'd like it fixed, either in email or on IRC. I also often came up with an ugly fix at first which was refined and cleaned up before being applied and pushed upstream.

With the above methodology I was able to fix a number of deeper and more complex bugs like the following:

• #33 : Check for conflicting projection functions.
• #39 : Emit an error if modules are recursive.
• #42 : Support unboxed CAFs
• #45 : Better error message for runtime pattern match failure.
• #53 : Check for name shadowing in forall quantifiers.
• #58 : Panic in type inferencer.
• #71 : Better error message for unimplemented class functions.
• #77 : crushProjClassT panics when there are type errors.
• #78 : Renamer problems in data type defs.
• #144 : Need better error message when source file does not exist.

I'm now getting a pretty good idea of how the compiler is put together and I'm stretching my hacking into feature enhancements.

My enthusiasm for DDC was recently validated by functional programming guru Oleg Kiselyov's comment on the haskell-cafe mailing list:

"One may view ML and Haskell as occupying two ends of the extreme. ML assumes any computation to be effectful and every function to have side effects. Therefore, an ML compiler cannot do optimizations like reordering (even apply commutative laws where exists), unless it can examine the source code and prove that computations to reorder are effect-free. .....

Haskell, on the other hand, assumes every expression pure. Lots algebraic properties become available and can be exploited, by compilers and people. ....

Hopefully a system like DDC will find the middle ground."

Anyway, back to hacking ....

To celebrate I've expanded Hikari's photo page, its here.

Born at 1:47 pm on the 11th November 2009 at the Royal Hospital for Women in Randwick. 2.72kg healthy boy.

Photos here

If you are interested in Haskell generally or the Glasgow Haskell Compiler (GHC) in particular, you may want to have a look at the latest issue of the biannual GHC status updates.  It includes a summary of our recent progress in the Data Parallel Haskell project.

Permalink | Leave a comment  »

Download now or preview on posterous

delayed-regular-arrays-Sep09.pdf (417 KB)

Permalink | Leave a comment  »

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.

Permalink | Leave a comment  »

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.

Permalink | Leave a comment  »

On October 22th we held the 20th meeting of FP-Syd, the Sydney Functional Programming group. The meeting was held at Google's Sydney offices and we had about 28 people show up to hear our two presenters.

First up we had Roman Leshchinskiy and his presentation "Loop Fusion in Haskell", work that is part of GHC's Data Parallel Haskell library. Loop fusion depends on the ability to convert operations on arrays into operations on streams. Then, when applying multiple stream operations, adjacent conversions to and from streams can be dropped, allowing further inlining. The real beauty of this approach is that stream operations and data parallelism can be written as a library outside of the GHC compiler and then depend on the compiler to do most of the heavy lifting. Romain then moved on to explain that this work was just as applicable to general parallel computation on multicore systems as it was to clusters and GPUs.

Our second presenter for the evening was Barry Jay who gave us an introduction to "Pattern Calculus". Barry's work on Pattern Calculus was inspired by the fact that while lambda calculus is able to adequately explain computation, it does not explain operations on data well. In particular, lambda calculus does not distinguish between variables and data constructors while in the pattern calculus constructors are treated as a separate class; matchable symbols. The ideas behind Pattern Calculus are explained more fully in Barry's book:

A big thanks to both our speakers and to Shane Stephens and Google for providing the meeting venue and the light refreshments.

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

Permalink | Leave a comment  »

I suppose Watergate is the archetypal example of the consequences of the cover up being worse than the original offence, but you see it all the time.

The example I have in mind has less geopolitical significance, but will probably be more interesting for most readers.

A company named PopCap Games publish a nice little game called ‘Plants vs. Zombies’. I played the demo for the allotted 60 minutes when it was originally released, and then forgot about it when my trial expired.

About a week ago they released a free Flash version, which uses a subset of the plants and zombies from the full game, and playing that got me interested in buying the full version again.

The game sells for USD20 or AUD30, which at current exchange rates is a bit rich — the Australian dollar is buying 92 US cents at the moment. Just yesterday I bought another game, Machinarium — which also sells for USD20 — for AUD22.32.

So I sent a tweet to PopCap enquiring about their pricing:

@popcap_games why is PvZ AUD30, when USD20 is only AUD22?

To their credit, they replied quickly, but I didn’t find their answer convincing:

@tgdavies USD price displayed is pre-tax which is added in the cart. International prices include sales tax.

To get 22 to 30 you need more than 30% tax — Australia’s GST is only 10%, and I think paying that is my responsibility as the person ‘importing’ the game.

Of course, the real reason is that as recently as March the Aussie dollar was only buying 65 US cents — which gives you about AUD30 for USD20. PopCap simply haven’t adjusted their prices.

I wish they could have said that, or just “I don’t know”, instead of invoking some mythical tax!

PopCap aren’t the only company whose Australian prices are out of whack — the cheapest 15″ MacBook Pro is AUD600 more expensive than a simple exchange rate + tax calculation would suggest.

Early in 2008 I drafted a blog post about something on Mac OS X called Universal binaries. Now the same stupid idea is available for Linux, and planned for other ELF systems. Its called Fat Elf.

The original post follows.

As the main author and maintainer of libsndfile I've recently been involved in a number of email exchanges along the lines of this:

  OS X User : Is it possible to build a Universal Binary of libsndfile?
  Me        : No, please see the FAQ.
  OS X User : Autoconf sucks!
  Me        : Even if you use Xcode, the problem of testing remains.
  OS X User : Other projects can build Universal Binaries, why can't yours?

to which I should probably respond "Have you stopped beating your wife/ girlfriend yet?".

For those lucky enough to be blissfully unaware of the issue, Universal Binaries are Apple's solution to the marketing problem that arose from their decision to ditch the PowerPC processors it had been using in its machines in favour of CPUs from Intel. Obviously, this change of CPU would have an impact on users and Apple chose a two pronged approach to ease the migration of its users from one CPU to another; Rosetta a PowerPC emulator which allows PowerPC code to run on Intel based Macs, and the idea of the Universal Binary (UB), a way of packaging binary code for PowerPC and Intel into a single monolithic file so that the OSX operating system can run which ever is appropriate for the CPU it is being run on.

Building Universal Binaries on Mac OS X using Apple's own development toolset Xcode is apparently quite trivial. Under the hood, Xcode uses a version of the GNU GCC compiler which Apple hacked to allow it to take in a single input source code file, pass it through both an Intel and a PowerPC back-end and then generate a single binary containing both Intel and PowerPC executable code.

Apple has obviously gone to a lot of trouble to make the process easy. So easy, that the average OSX developer expects it to just work, without realising exactly what it is they are doing and even more importantly, without realising that the process itself contains one very large flaw (which I'll get to shortly).

Building Universal Binaries of FLOSS (Free/Libre/Open Source ...) software is a whole different matter. A large majority of FLOSS software uses things like scons or autoconf and its related tools to detect characteristics of the target platform so that the source code can be compiled correctly for the target.

The problem is, that people who know that the Xcode version of GCC can generate a universal binary from one pass over a source code file expect to take a project like libsndfile, set the CFLAGS environment variable, run configure and build a working universal binary. Anyone who knows autoconf can guess that this is simply not going to work. The main output of the configure script generated by autoconf is a header file containing definitions to handle the detected features of the CPU and operating system. The problem is that the configure script is only run once and the characteristics detected on that run are then used to compile both the Intel and the PowerPC version of the executable code.

The result of the above is that people developing FLOSS like myself get emails from OSX users complaining that their UB version of libsndfile doesn't work. Since I first heard of Apple's Universal Binaries back in early 2006 I have personally spent over 50-100 hours trying to come up with a solution to an issue that only affects an operating system that I personally am not very interested in. Thats a bunch of hours that I could have spent in much more enjoyable pursuits.

Now, consider how many other FLOSS project would have been hit by similar problems. So lets say 10 hours per project across a thousand projects. Thats one hell of a lot of developer time that could have been spent doing more useful things. Why didn't Apple foresee this? Why didn't Apple spend some of its resources trying to mitigate the effect of UB on FLOSS projects. Why didn't Apple devote say 500 man hours of its developer's time to help ease the transition of FLOSS projects to UB; 500 man hours of work on autoconf and automake would likely have gone a long way.

The difficulty of generating UB for code using the autotools is not even the biggest problem with UB. What I see as the biggest problem is the huge green elephant standing in the corner that no one wants to talk about; testing (maybe that should have a blink tag).

For nearly a decade, testing, especially reliable, repeatable, automated testing has been considered an important part of the process of creating reliable software. Now Apple is encouraging the building of Universal Binaries, but I for one am very curious as to how these are being tested. I can think of the following possibilities:

• Ad-hoc and manual testing. Obviously this is a poor substitute for automated testing.
• Automated testing relying on copying test binaries to another machine and running the tests for the other architecture there. This requires easy access to the other machine and considerable effort to make the tests work.
• Automated testing relying on Rosetta. Like the previous option this requires considerable effort to make the tests work.

Given that all these options are difficult it is highly likely that testing falls by the wayside. In short Apple is effectively encouraging the release of untested binaries to users. When these untested binaries go wrong, who do users blame? The authors of that software even when those FLOSS authors are not Mac users and have little or no interest in Apple and its operating system.

Furthermore, Apple is about to add another spanner to the works; quad binaries. Quad binaries are like Universal Binaries that contain code for both 32 bit and 64 bit versions of PowerPC and Intel. Quad binaries will be even more difficult to test, more difficult to get right and still more pain for FLOSS developers.

On September 17th we held the 19th meeting of FP-Syd, the Sydney Functional Programming group. The meeting was held at Google's Sydney offices and we had about 18 people show up to hear our two presenters.

First up we had Raphael Speyer and his presentation "Rhino, ES5 & GSoC". Raphael explained how he was accepted into the Google Summer of Code project to work on bring the Rhino, a Javascript engine that runs on the Java Virtual machine, into line with the upcoming EcmaScript 5 standard.

For the second presentation we had Shane Stephens one of the Google people working on Google Wave giving us an overview of Google's Operational Transform algorithm which is at the core Google Wave. He then walked us through a reimplementation of the algorithm in Haskell.

A big thanks to Shane Stephens and Google for providing the meeting venue and the light refreshments.

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-projections-2009/

Permalink | Leave a comment  »

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-and-haskell/

Permalink | Leave a comment  »

Another new Goanna feature is operational feedback. While Goanna is analyzing your source files, you can check to see exactly what is being done. Just select the new Goanna Statistics button from the Tool menu:

Way back on August 23rd we held the 18th meeting of FP-Syd, the Sydney Functional Programming group. As usual, the meeting was held at Google's Sydney offices and we had about 24 people attend to hear our two presenters.

First up we had Mark Wotton and his presentation "Testing By Convention and Flow". TBC ( on Hackage) is a harness for running tests written with HUnit or Quickcheck. The main idea is that if your tests are written to follow a set of conventions, a lot of the boiler can be skipped used TBC.

The second presentation was by Ben Lippmeier on his work on getting Haskell's GHC compiler working on SUN's OpenSparc T2 processor. The OpenSparc T2 is interesting because it has 8 cores per processor and 8 hardware threads per core and hence is an interesting target for GHC's parallel evaluation model.

A big thanks to Shane Stephens and Google for providing the meeting venue and some light refreshments.

The next release of Goanna determines facts about your program from assertions. We can use this information to determine the bounds of variables and the nullity of pointers.

Goanna’s interval analysis can now catch this division by zero:

#include <assert.h>

int bad_div_of_8(int x)
{
  assert(x == 4);
  x -= 3;
  x--;
  return 8 / x;
}

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-problem/

Permalink | Leave a comment  »

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/

Permalink | Leave a comment  »

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-microsoft-sues-apple-google.ars

Permalink | Leave a comment  »

Yesterday, NVIDIA presented its next-generation GPU architecture, called "Fermi": http://insidehpc.com/2009/09/30/nvidia-next-generation-gpu-fermi-targets-hpc-supercomputing/

Permalink | Leave a comment  »

I feel like there’s been four stages to my life. The first stage was being a youngling at primary school: I don’t remember much from there except that I fantasised about handball being an olympic sport. The second stage was the PC demoscene, where I grew interested in many things that I love today about computing: art, music, and my first experience with a community and culture that you could love and immerse yourself in. The third stage was my twenties: an introduction to university, Linux, coding, the Mac, Haskell, research conferences, industry conferences, the working life, and balancing it all with healthy doses of relaxation, food and the beautiful world that Sydney had to offer. The fourth stage was tearing myself away from that fairly sheltered life and my emotional base, and moving to San Francisco.

I’ve been here for six months. It’s felt like two years. It has been a truly wonderful experience: making new friends, learning a new culture that’s both significantly but subtly different, and doing it all without my family nearby, who’ve been my anchor and support for the past three decades. Part of the motivation was proving to myself that I could make it on my own: prove myself worthy in the eyes of my peers, be social enough to make genuine friends here who I cared about and who cared about me, living on my own and simply paying the rent. Part of the motivation was to shake things up from a cruisy life in Sydney and experience new things. I’m glad to report that the experiment’s going pretty well so far.

San Francisco is a city of immense contrast. For every stupid hipster who thinks that owning a Prius absolves them of their environmental debt to society, there are remarkable individuals who understand and challenge the daunting realism of politics, lobbying, energy, transformity and limits to growth. For every poser upstart get-rich-quick guy chasing after VC funding for Facebook apps, there are the quiet anonymous developers at Apple, Google, and startups you’ve never heard of who work on all the amazing technologies that the entire world takes for granted today. The Tenderloin, so unpleasant to walk through, has some of the very best restaurants and bars that the city has to offer. The nouveau shiny high-rises of South Beach contrast with the destitute run-down feel of western SoMa, only a few blocks away.

It’s a make-or-break city: rents are insanely high despite the rent control laws, and there’s no lower-middle class population here because either you’re flying high, or you’re not flying at all. It’s natural selection in action: either you keep up with the pack and continue being successful, or you fall and become left behind. And so, in contrast to the relaxed lifestyle of Sydney, San Francisco is full of ambition. While it lacks the non-stop pace of New York or the late-night industry of Detroit and Chicago, the people here want to change the world, and they have the innovation, the smarts and the determination to do so.

The tech industry here is simply amazing. Despite being here for half a year, I’m still floored when I go to a party and every person I meet there ends up being a Web designer, or a coder, or a sysadmin, or a DBA, or a network engineer, or a manager of a bunch of coders, or a VC funding a tech company, or a lawyer or accountant or marketing or PR person working for a tech company, or a level designer or artist working for a games company. Even the girls. It boggles me. It’s like the entire Bay Area simply exists to build software and iPhones and tech solutions. I was truly daunted in the first few months to find out that everyone around me was, well, just like me. A few months ago, I was at my favourite little tea shop in San Francisco decompressing and minding my own business, when three people sat down next to me and started talking about VGA BIOS exploits. (Turns out that they work for VMware.) I mean, seriously?

I wouldn’t say that I’m totally acclimated to the Bay Area yet, and perhaps I never will be. Visiting Australia just a month ago reminded me just how different the two cities are in their lifestyles. People are always doing something in San Francisco: there’s so many interesting people there that you feel like need to divide your time between groups, let alone having time to yourself. Even the serious introverts there are out on most schoolnights. The people here are always switched on; even at a party, there’s an air of networking going on and the feeling of opportunities to be seized. You almost always end up talking shop at any event, because people here are defined by what they do: one of the very first questions you’re usually asked is “Where do you work?” or “What do you do for a living?”. In Sydney, asking that question so soon would just be a little bit weird. You usually save that for far later in the conversation, when you’re running out of things to say to the pretty girl to try to hook up with her. (And don’t even get me started about the American dating scene.)

And so, for all the wonderful parks, bars, tacos, restaurants, pirate shops and museums of the city; the incredible beauty and varied terrain of the North Bay; the charm and chilled suburbia of North Berkeley in the East; and the innovation and serenity of Silicon Valley just south, I still miss Sydney and the culture I grew up with for twenty years. I don’t mean that in a yearning way or mean to imply that San Francisco is somehow inadequate, because it rocks: I’m having a wonderful time experiencing new things, and it was the right decision to move here. This is where I should be at this stage in my life. Sydney will always be where my heart is, but right now, San Francisco is home, and it’s as fantastic as I hoped it would be.

GHC's testsuite[1] contains a test encoding001 (in the I/O library section) that generates files in various unicode encodings including one using UTF-8 with byte order markers, namely encoding001.utf16.utf8_bom. On Mac OS X 10.6 (Snow Leopard), this file causes the indexing process of Spotlight to hang. More precisely, the mds (meta dataserver) process appears to go into a loop (eating all cycles of one processor core) — it appears to hang in the library libmecap trying to parse what it probably believes to be Japanese or Chinese text.

Interestingly, the file command regards the file to be "Unicode text, UTF-32, big-endian".

Permalink | Leave a comment  »

Goanna for Visual Studio is out of beta. Version 1.0 is available for download now, for both Visual Studio 2008 and 2005. You can also watch a short introductory video on using Goanna here.

TomMD posted a nice introduction to using the interface generator C->Haskell

Permalink | Leave a comment  »

Here is the language specification for blocks (that is lambda abstractions) for C, Objective-C & C++ as implemented in the Clang compiler and used in Mac OS X 10.6 (Snow Leopard):

Permalink | Leave a comment  »

Here is a video of Roman Leshchinskiy's talk on our work on implementing Data Parallel Haskell (DPH), which he presented at the Haskell Implementors' Workshop (co-located with ICFP'09):

Permalink | Leave a comment  »

Video of my talk at the Haskell Implementors' Workshop: 

Permalink | Leave a comment  »

Apple released the source code of one of the core technologies in Snow Leopard: http://libdispatch.macosforge.org/
 
This is an interesting move, as discussed at http://www.macresearch.org/grand-central-now-open-all — it will be very interesting to see whether this will lead to a wider adoption of Grand Central Dispatch beyond Mac OS.

Permalink | Leave a comment  »

The slides from my talk Haskell Arrays, Accelerated (Using GPUs) at the Haskell Implementors’ Workshop (that was co-located with ICFP 2009 in Edinburgh) are now available. The talk introduces a novel framework, based on an embedded domain-specific language of multi-dimensional array computations, targeting GPUs and other acceleration hardware.

Haskell Arrays Accelerated with GPUs

Permalink | Leave a comment  »

The slides from my talk Haskell Arrays, Accelerated (Using GPUs) at the Haskell Implementors’ Workshop (that was co-located with ICFP 2009 in Edinburgh) are now available. The talk introduces a novel framework, based on an embedded domain-specific language of multi-dimensional array computations, targeting GPUs and other acceleration hardware.

The forth beta release of Goanna for Visual Studio 2008 is now available. Get it here!

This release comes with some minor bug fixes, and a significant speed increase for C++ projects with large header files (like the Boost libraries). Hopefully we are nearing the end of our Beta period.

We have made Beta 3 of Goanna for Visual Studio 2008 available. There are many bug fixes and user interface enhancements, including:

• Right-click support for Solution Folders.
• A Goanna icon on the toolbar.
• Control-flow ordering of short-circuit operators (&& and ||).
• Solution-wide settings panel.
• Several common false positives have been eliminated.
• Auto-detection of less common MSVC macros in the build process.

You can download it now!

Here's the latest addition to our family, Alfie, a 2 year old long haired Chihuahua.

Alfie's previous owners had recently moved and were not able to keep him in their new apartment so he has come to live with us. He's already managed to find the spot on the floor which is nice and sunny in the morning. He seems to be thoroughly enjoying it in this picture.

To make Goanna fast enough for the desktop, we have to keep our control flow models simple. In the past we combined short-circuit operators in our models into single events, which means we missed some bugs. But some new tricks mean we can have finer-grained control flow models.


int ret;
if (x > 0 && (ret = foo()) > 0) {
/* ... */
}
return ret;


There’s a bug here, and that is that if x <= 0, ret is not initialised when you try to return it. With the condition statement as a single event, Goanna could not tell that the first half of the && could run without the second half running.

Well, we developed some techniques that let us handle larger control flow graphs. So that latest nightly version of Goanna reports this:


Goanna - analyzing file example.c
Number of functions: 1
example.c:12: warning: Goanna - Variable `ret' may be uninitialized
Total runtime : 0.04 seconds


So our next release will help you catch even more bugs!

On Thursday July 23rd we held the 17th meeting of FP-Syd, the Sydney Functional Programming group. The meeting was held at Google's Sydney offices and we had about 28 people attending to hear our two presentations.

First up we had Jonathan Lange with a presentation titled "Monads and Twisted" where he introduced the asynchronous event handling in Python's Twisted Framework. During a brief introduction to Twisted he showed how callbacks are registered for future events. He then went on to show how the function signatures for these callbacks were very similar to those for Monadic bind and return and that these callbacks obeyed all three of the monad laws.

Next up we had Paul Steckler demonstrating how he has been using Ocaml's camlp4 macro pre-processor in his work on the Goanna static analysis tool. Paul mentioned that documentation for camlp4 is rather poor and that to figure out some things he actually needed to read the camlp4 source code. It does however seem to be a powerful pre-processor system.

A big thanks to James Kozianski and Google for providing the meeting venue and some light refreshments.

The next meeting of FP-Syd happens this week.

Giving Posterous a whirl…

Posted via email from Just Testing | Comment »

Haskell played a pivotal role in achieving this results. The Haskell kernel model described in our 2006 Haskell Workshop paper formed the basis for the verified high-performance C implementation and the kernel model used for verification — for details, see Klein et al.’s forthcoming SOSP paper.

Just to let you know that Goanna for Visual Studio is now available for download. We are classing it as Beta at this time yet we’re pleased with the progress we’ve made so far, and trust that you will be too. We very much look forward to any and all feedback on this release, and welcome comments to Ralf via ralf[at]redlizards.com . Thank you for your patience and we look foward to hearing from you.

Tim Sweeney shares his vision of the future of high-end computer graphics and games programming.  Functional programming and data parallelism play an important role.

I've been playing with Google Chrome Dev Builds of late. That is the web browser by Google, not the OS or any other tenuously related project that has a similar name. It seems nice and fast. And even though its billed as work in progress, it seems quite stable to me.

But alas there are no add-ons. And while I'm prepared to accept that some of my favourites, vimpretor and rikaichan, are a bit esoteric. The world without adblock is a pretty scary place that I'm not sure I want to deal with. All those banner-adds and the like really lower the tone of the place. This seems amusing as I believe that chrome basically means to sex things up.

From the lifestyle section:

USING a solarium increases a person’s risk of developing melanoma by 15 per cent and the risk rises to 75 per cent for those who used them when they were younger than 30, a major review has found.

I suspect that the melanoma rate among under 30s sunbed users isn’t 75%, and what the Herald meant to say was “the risk rises by 75 per cent” or “the increase in the risk rises to 75 per cent”.

The mistake may be obvious, but why not take the trouble to say what you mean, instead of something completely different?

I used to be a keen windsurfer and once attended a training camp/holiday in Greece. We covered advanced maneuvers such as 360’s, forward rolls and duck gybes etc. The instructor always said, “Doesn’t matter if you pull it off, just so long as it looks good!”

The reason for this story is that at Red Lizards we have a mantra of “Bringing higher quality software to market faster”, and so the flip side of this coin is that we can’t ship a release until it is of sufficiently high quality. Double edged sword perhaps, yet this is the business we chose.

Here’s the rub; our Visual Studio release looks good and even if I say so, it looks really good BUT…. it’s not ready from a quality perspective. We’ve been running some reasonably large projects through it (e.g. Quake III, Google’s Chromium and others) and we’re not satisfied with the bug warnings and reporting.

I previously posted that we’d have the MSVS release up in July, yet we’ve slipped and are now tracking for mid to end August, for which I apologise.

If you have some spare cycles, are interested in being an early Beta tester and are working with a large project code base, please contact Ralf  via ralf[at]redlizards.com and we’ll work on providing you with early access to a pre-release. Thank you for your patience and support.