Haskell, HPC and Crypto Get Together 22nd May 2008

Last night's get together was attended by about 15 men (women in technology take note) from a variety of backgrounds (students, cryptographers, investment bank staff.) Beers were consumed and nonsense talked - then we toddled off to Kurz and Lang for some bratwurst around eight as is our tradition (from our days in Zurich with a well known Swiss bank.)

The conclusion of the evening was that there is a place for Haskell in the city - why? Well here's two extracts from and article on Haskell and Performance on Planet Haskell written by Neil Mitchell:

Haskell's multi-threaded performance is amazing

A lot of clever people have done a lot of clever work on making multi-threaded programming in Haskell both simple and fast. While low-level speed matters for general programming, for multi-threaded programming there are lots of much higher-level performance considerations. Haskell supports better abstraction, and can better optimise at this level, outperforming C.

The trend is for higher-level optimisation

As time goes buy, higher-level programs keep getting faster and faster. The ByteString work allows programmers to write high-level programs that are competitive with C. Performance enhancements are being made to the compiler regularly, pointer tagging, constructor specialisation etc. are all helping to improve things. More long term projects such as Supero and NDP are showing some nice results. Optimisation is a difficult problem, but progress is being made, allowing programs to be written in a higher-level.

and that it would be a good idea to form a Functional Programming get together on a reasonably regular basis - so watch this space.

Haskell, HPC and Crypto - Beer in the Evening

We're organising another "beer in the evening" event somewhere round about Smithfield in London to discuss Haskell, multi-core, HPC, Security and all sorts really - so if you fancy having a beer or two with a gang of gnarly, middle-aged architects, programmers and scientists (attractive huh?) then you'll be very welcome.

We will be meeting on the 22nd May - details are here

To participate, please add your name to the Doodle Poll entitled Haskell + Beer. This is so we know how many buckets of chips to order...

As All Bar One has now closed, we will be in the Bishop's Finger, Smithfield. I'm planning on getting there around 530pm. My mobile number is zero seven eight three zero three six eight zero two four - when you get there give me a call. There's a good chance we'll get some of the beers paid for too but no promises yet.

Topics for discussion/contention

• Crypto in Haskell (Dominic is Mr Haskell Crypto btw). Opportunities for parallelism (e.g.)
  
• Is Haskell and multi-core the best solution to meet the projected demand for simulation in finance or has FPGA yet to have it's day?
  
• Challenges of Haskell and high performance messaging integration. 2.4 million messages per second (not transactions) are now possible using tools like LBM from 29West.
  
• The K language (an APL derivative), Fortran, Objective-C, LISP and Smalltalk gained a small foothold in the eighties/nineties in quantitative analytics but C++ remained the main language of implementation due to availability of skillset (K programmers are like hen's teeth.) Java and now C# are now the de facto implementation languages but have serious issues for high frequency finance - will Haskell be able to make an impact or will it be another marginal language used by quants.
• Is Haskell capable of high performance?
  
• Haskell and distributed memory (memcached) performance aspects
• Haskell Data Parallelism versus state of the art FPGA approaches. Check out HPCPlatform's offering btw.
• I hear rumours that Haskell is being rolled out to the HPC team of a major investment bank in Canary Wharf - watch this space...
  

More topics very welcome.

Haskell Cryptographic Library - New Release

Having had quite a few contributions lately, I've released a new version of the Haskell Cryptographic Library. It now contains an implementation of TEA and BubbleBabble.

Haskell - The Next Mainstream Programming Language?

Steve sent a pdf by Tim Sweeney of Epic Games entitled "The Next Mainstream Language: A Game Developers Perspective". He commented "While Sweeney doesn't exactly embrace Haskell, he seems certain that some variant will prevail".

Sweeney's 67 page presentation is a worthwhile read. It summarises the logistics of a multi-player online game - Even250K lines of C++, highly object orientated and garbage collected with associated scripts and data files. Object state evolves with gameplay. Typically there's around 1000 classes with 10K objects active during play. Events touch about 5 objects on average.

Numerical computation (for intersect detection, graph traversal etc) uses around 5 GFlops, Shading is inherently data parallel, performed on the GPU using a custom language (HLSL.) It uses around 500 GFLops

The resultant code is performance-sensitive and requires highly modular design of reliable code. Sweeney comments that C++ is poorly equiped for concurrency. This is bourne out by my own experience in the early nineties with Roguewave (remind me to tell you about the eek! bug one day.) A truism is that analysing performance isn't a simple matter of identifying "hot spots" and optimising that code - or writing assembly language to get around an issue. This is never done as Sweeney notes. Event timing and handling, data structure construction, execution path may have to be revisitied resulting in a lack of productivity. A the end of the day - you have to compromise performance vs productivity.

Sweeney then proceeds to deconstruct C++ as a language and Object-Orientation as a principle. As you've probably found yourself, sometimes the base class has to change - leading to significant refactoring. In particular, he slates the inability of C++ compiler to handle dynamic failure, contrasting how Haskell handles this with ease. C# also comes in for a wry observation: it exposes 10 types of integer-like data types, none of which are those defined by Pythagoras...

Pushing Haskell, he hypothesises that 80% of CPU effort could be parallelised using Haskel ST - the Strict State Thread module and, further still, that programmer "hints" can be used to guide parallelisation - stating that Haskell's Monadic nature is a natural fit for parallelisation - imperative programming is perhaps the "wrong trousers".

As I found to my cost, "shared concurrency is [indeed] hopelessly intractible" in my "Why events are a bad idea" post. I too got in a mess with manual synchronisation. Sweeney also suggests as the quoted paper does, that message passing is the recipe for high performance because, when combined with software tranactional memory and multiple threads, the overhead of synchronisation is bearable when the object population his rate is small (~ 5 per 10000 per message.)

The article then concludes with his musings on the next generation language. All-in-all, a nice empirical paper from the coal face.

Next, I'll cast my eye on Erlang - there's buzz there too from the finance crowd, but I know what my next language is going to be - and hit begins with H...

Logging Sins, Hierarchical Tuples and Effective Security Architecture

Logging Sins, Hierarchical Tuples and Effective Security Architecture

There are many sins in logging, none so amusing than this one I saw recently:

+++ ALERT : SEVERE : Invalid Market Order Submission ... Hence, releasing the Trader Order in Panic... +++ALERT : SEVERE+++

In the old days, we used to return a number which was then looked up in a decode table. This lead to obscure code and errors which were quite severe when the DBA messed up the decode table...

However, as an aid to debugging, self-describing code can be useful. So if you're tempted, try tuples - they're quite neat. They're a feature of functional languages, in particular Haskell. Here are some real examples:

TIB.SEND.TOALGO.AMENDTRADERORDER
TIB.SEND.TOALGO.ORDER.CANCEL
LBM.CALLBACK.INVOKE
LBM.CALLBACK.RETURN

Without commentary, you can deduce what's happening with this code and these messages. Tuples are cool. They can also be used to describe design patterns. I wrote a paper a while back which I presented at the IISyG on Security Architecture Patterns - I'll post the deck soon on the enhyper subversion server. I took an idea from the Antipatterns book on naming of "antipatterns" and crystallised the methodology to this tuple for describing a pattern:

{GENERAL, LESS GENERAL, SPECIFIC, MORE SPECIFIC}

Applied to the concept of security, this tuple looks like this:

Generic Security Concept.Application Context.Application Instance.Configuration

So I came up with patterns which looked like this:

DataTransfer.BBCP
SecrecyJurisdiction.Authentication.SSH.PasswordlessCertificate
Authentication.Applicaiton.JavaClient.OracleOID

Now the beauty of this scheme is that people are lead to logically to the comprehension of the solution by hierarchical decomposition. Add the ability to have arbitrary tuple lengths and encourage stereotypes and you now have well known patterns which you can back by implementations. Now here's the killer part - get security risk to certify/risk assess the implementation so you now have effective security in a risk compliant manner.

Unfortunately, this bright idea foundered for two reason - banks are here to make money, not develop software and security risk guys found it difficult to think like developers.

Functional Programming meets #crypto

We met up last night as mentioned in for a Functional Programming Beer in the Evening event and had a thoroughly enjoyable evening. Dr Dominic Steinitz, Nigel Stuckey of Systemgarden, Steve Wart and I spent several hours talking about a variety of topics ranging from FP through to Cryptography.

Nigel, Steve and I met at a tier 1 we all worked for through an internal chat channel I ran on cryptography called #crypto which was a hot bed of financial crypto interest. I had been following the great Robert Hettinga and his rants on bearer security and his promotion of FC in general. Through this I met and became friends with Ian Grigg who runs the Financial Cryptography website which is always worth a read as Ian challenges conventional wisdom and crypto practise from a more business related angle.

Dominic is an active member of the Haskell community and hopefully will be joining the enhyper blog and contributing his expertise. Dominic wrote the cryptographic functions (sha1, rsa, blowfish etc) in Haskell and maintains the library on one of the Haskell webservers. I'm going to create a subversion respository with public access for Dominic's work to allow the community to contribute to the Haskell crypto effort so watch this space.

Nigel will also be contributing to the Enhyper blog - his expertise in platform management is world-class, gained through the development of Harvest at System Garden.

We talked in detail about the evolution of specialist languages in Finance, in particular K and Smalltalk. Steve Wart is a smalltalk programmer and outlined a fantastic sounding system he worked on for a Candadian power company so I hope he's going to expand on that here. Dominic and I discussed stream fusion at length and I think I understand it - however, I'm not going to steal his thunder as he promises to write an article on data parallelism. Nigel and Steve had a lively debate on Second Life and discussed the additon of models of ancient buildings as a mechanism for historical education. We finished the evening with a sausage and sauerkraut at Kurz and Lang in Smithfield which was reminiscent of Zurich night life.

Time to Embrace New Data Parallel Programming Models?

In "The rise and fall of High Performance Fortran: An Historical Object Lesson" there's a several lessons to be learned but of significant relevance to the development and adoption of Functional Programming Languages in finance was the promise offered by data parallel architectures.

Data parallelism is the ability to run sequences of instructions which are broadcast to processing units in lock-step, on different elements of data in parallel. This was first implemented in hardware in the 1960's and was classifed as SIMD - Single Instruction Multiple Data

This is the mechanism is now in implemented in software and part of the Glasgow Haskell Compiler and is explored in detail in the presentation "Nested Data Parallelism in Haskell" where they state that it's the only way to take advantage of 100's of cores and that it can even be run on GPUs. Like Handel-C, Haskell has par and seq statements allowing the programmer to parallelise and sequentialise instructions. They also introduce a new concept called stream fusion which is non-recursive allowing data to be "bused"from one stream to another inline - now I'm not sure I fully understand the implications of this but I'm sure going to find out.

Functional Programming Beer In The Evening Event Redux

Following our last meet up last week to speak about Functional Programming in the Finance. I'm setting up another beer around Smithfield in London, 14th June 2007, with Dominic Steinitz who has made considerable contribution Functional Programming via his Haskell crypto library and paper on Trends in Functional Programming. We'll be talking about Haskell in particular but also about Erlang and its use in service based analytics.

Following our last meet, Someone sent me a link to a pdf entitled Caml Trader: Adventures of a Functional Programmer on Wall Street by Yaron Minsky of Jane Street Capital which confirms the rise of FP in finance. Worth a read.

So if you fancy joining us, we'll be in the Long Lane Pub in Long Lane near Smithfield from 6pm onwards. Drop me a note (rgb at enhyper.com) or call my mobile +44 791 505 5 three eight zero.

Skillsets for the HFF Future

So which languages are going to succeed in the world of High Frequency Finance? Well you can bet your bottom dollar it's not going to be C# or C++. Both generate buggy and leaky solutions and are too reliant on third party libraries of unknown veracity. You can also rule out the raft of scripting languages - no matter how much the developers like them: Perl, Python, Ruby et al have good geek factor, however they don't cut it in production systems.

So we're left with C and the functional languages. C is considered as a weird throwback to the 70's by most nascent programmers. What most of them do not realise is that the C# CLR, Java Virtual Machine (parts of), Ruby, Perl, Python, Apache, Linux, Solaris, C++ etc etc are all written in C. The main reason for this is performance, simplicity, robustness. C has it's share of problems, but in general it's a fairly good language.

So, why are all the quantitative libraries in Investment Banks written in C++? And why are they mostly single threaded? The answer is hubris on the part of the programmers and, as previously outlined, the difficulty in coding thread safe libraries.

Well, times have changed I'm afraid. C++ has to die because it does not translate into hardware - a route where tremendous performance gains are to be had. C is looking weak in light of the scalability models which can take advantage of multi-core within the functional languages. The future in the short term is C but watch for the rise of Erlang and Haskell. Their time has come.

Why Events are a Bad Idea (for high concurrency servers)

And Why Mixing Events and Threads is Even Worse

I've just been badly burned by mixing two paradigms - threading and events. All was working fine until the day before go live; the testers started to pour 400 stock baskets through the system rather than 40 which resulted in one of those issues which make your heart sink as a programmer. Between 5 and 15 stocks would go into pending which meant that there was a threading issues somewhere and it was go live that evening. Tracking it down was to prove difficult due to poor separation of duties between the threads resulting from the design having its origins as a single threaded, serial set of calls which took data from an event generated on one side and generated a modified message dispatched to the receiver and vice versa. In retrospect, the problem would have been solved by having single queue between the two threads, following the asynchronous put/take connector pattern. This would have ensured complete separation and higher throughput.

Mutex Spaghetti

As it happens, it was impossible in the time available, to redesign the solution and the simplest course of action was to go back, reluctantly, to a single threaded implementation. Time to test was a major factor here, however, not before some time was spent playing the mutex game. I started mutexing at a very low granularity which appeared to fix the issue (or break things completely) almost - I was down to one or two trades pending - which was not good enough.

Adding additional mutexes, it quickly became apparent that it's very easy to get in a mess either by blocking on an already locked mutex or by adding too many mutexes which means you end up in a mess anyway. After four hours of mutex soup - I made the decision to remediate the code back to single-threaded code. Performance, at the moment is not an issue.

So the moral of the story is look for a design pattern which fits your code - understand it and think the design through, we seldom have time, but if you can, use UML to build a sequence diagram - then you'll see the call chain and understand conflict between threads.

A friend of mine related the story of Sun's attempts to make the solaris kernel mt safe - this was a much harder task than they anticipated. Most of their effort was centred around protecting the key data structures rather and changing the programming paradigm so that users took the responsibility for data allocation.

Another pointed out an article on slashdot this morning "Is Parallel Programming Just Too Hard?" which raises some concerns which, as we can see from the above, seem to be valid. If you're going to write parallel threads, you have to spend time on the design - it takes three times the effort and you really need to use patterns, example code and sequence diagrams. I hacked it and got away with it - to a point. If performance proves an issue, and you can bet it will at some stage soon, then it will be back to the drawing board - and this time, the design will come first.

Interestingly, threading versus events is an interesting debate which this paper: "Why Events Are A Bad Idea (for high concurrency servers)" argues well and threading comprehensively wins the day as a paradigm over events. I've always been of the opinion that separation of duties via a thread is intuitively faster than event dispatch - this paper goes a way to prove my intuition right.

Finally, there's a well deserved mention for Functional Programming Languages such as Erlang and Haskell, which has much promise for multi-core programming as outlined in these excellent slides: Data Parallel for Haskell.