Business is on hold

Back in November, I started working as a Data Scientist at uSwitch, an utility price comparison site. I am very fortunate to be able to work with so many smart and passionate people there. There is so much that I am learning in fact, I haven’t had time to do much else. Although my ridiculous 4-hour commute is also a factor. I didn’t even notice that EUR/USD dropped 1000 pips! As such, I am officially putting my own business and research on hold until further notice. I will continue to post relevant technical discussions on this blog. All of my existing clients have been notified and arrangements made way back before I began my employment. Thank you for all your support!

Algorithmic ownage

I felt good when I simplified one of my algorithms and sped it up 10 times. I felt so good that I even wrote an entire blog post about it patting myself on the back. Then last week I got an email from Kevin of Keming Labs suggesting a few alternatives.

First of all, his solutions looked much cleaner than mine. Then over the weekend I was able to incorporate his 3 algorithms into my program. I ran a few benchmarks and here are the average of 2 tests using a dataset of 28,760 items.

My algorithm. Elapsed time: 68372.026532 msecs.
Kevin’s solution #1. Elapsed time: 156.940976 msecs.
Kevin’s solution #2. Elapsed time: 60.165483 msecs.
Kevin’s solution #3. Elapsed time: 296.162042 msecs.

Total ownage.

That’s what I like about sharing my work; once in a blue moon, a random person drops by and generously show me how I can improve a solution 1,000 times! Now the ball is in my hands to understand what he has done and improve myself.

Collaborating and learning, that’s why I open source.

Update: I’ve done some more digging and it seems that one of the reasons for the drastic improvement in performance is due to the use of transients in the built-in functions. Lesson of the day, leverage the language’s inherent optimization by staying with core data structures and functions as much as possible.

Eureka moment on design patterns for functional programming

Understanding design patterns for object-oriented programming made my life easier as a Java programmer. So I have been looking for a comparable book for functional programming ever since my sojourn into this age-old paradigm. It looks as though I’m not the only one looking too. But the thing is, I think I’ve just had a revelation of sort.

There is one and only one guideline to designing functional architectures — Keep it simple.

Simple as in keeping your functions having one purpose only. Simple as in work with the data directly and don’t conjure unnecessary intermediaries. Simple, as elaborated by Rich Hickey in his talk, Simple Made Easy.

Much of this is conveyed in Bloch’s Effective Java — item #5: Avoid creating unnecessary objects, item #13: minimize accessibility of classes and members, for examples. As Majewski said in a stackoverflow reply, “the patterns movement started because object-oriented programming was often turning into ‘spaghetti objects’”. So keeping it simple are what design patterns ultimately strive for.

“Functional programming is a restricted style of programming, so it didn’t need to grow a set of restricted conventions to limit the chaos.” As such, there is no design pattern book for functional programming. I didn’t get that earlier this year. But something clicked recently.

During the past few months, I’ve been doing some consulting and open source projects solving algorithmic problems with Clojure. One problem in a project that I was faced with this week is calculating the occurrence of each distinctive element within a list of elements.

Say we have a list, coll = (“orange”, “bottle”, “coke”, “bottle”). The output would be something like [("orange", "bottle", "coke") (1 2 1)]

This is my first solution.

The specs are not exactly as I described but the concept remains. What I did is to use tail calls (it’s supposed to be fast, isn’t it?) to aggregate each counter to produce a vector of counts. Then I map each pair of fragment with its corresponding count to generate a final output collection. Sounds overly complicated, doesn’t it? This is the first warning of a bad functional design.

For a collection of 30,000 items, this function took 11 minutes to compute on my notebook. This looks like a good place to exploit the parallel nature of this problem. Specifically, the counting of each fragment is independent of other fragments. Thus, there’s no need for the program to wait for one fragment to finish to process the next. I simplified the program to remove this inherent assumption of procedural processing.

Here is the gist of the refactored code where each function only does one job. Since the processing are modularised, I can parallelize the algorithm easily with the use of pmap instead of map on the last line.

I’ve split the first function into 3 functions (2 shown here). As Hickey said in his talk, simplifying can often produce more, not less, functions. Yet, the program is not only easier to read and runs in less than a minute. An order of magnitude faster!

There are still lots for me to learn. I want to find more challenging projects to push my own limits. But rather than solving arbitrary problems, I prefer to tackle real-world challenges. So if you know of anyone that can benefit from collaborating with a functional developer to build robust and scalable software, please pass along my contact. I offer a 15% referral reward for successful paid jobs too.

I’ve quit my day job and moved to the UK to do this full time

My wife is pursuing graduate study at Oxford. So I’m taking this rare opportunity to quit my day job and concentrate on developing trading systems full time. I am also doing some consulting to keep in touch with civilization. I have just one project at the moment building a customer relation system for a friend’s financial services startup.

Now for some self-promotion. I specialise in building software systems for information discovery, and of course, trading systems too. If you know of any business that can make use of an information discovery system for better customer relation, inventory management, etc, then please forward my contact information.

That’s it for the public service announcement. I’ll be off to my first meetup this Sunday to hack on an open source statistical computing platform. I can’t wait to meet some very smart people!

Local Hadoop test cluster up and running

Thanks to Cloudera’s CDH3 image, I have a virtual machine with Hadoop on CentOS 5 working. I’m more of an Ubuntu guy, so CentOS is a new for me. But nothing Google couldn’t solve.

I also ran into a Hadoop exception about the java heap space. I couldn’t find a solution online so I just bumped up the memory on the virtual machine and it solved the problem.

In any case, I managed to run the pi calculation example on my local Hadoop cluster.

Building a distributed back-tester with Hadoop on Amazon AWS

Testing is arguably the single most important aspect of trading system development. You can’t tell how well an idea works unless you test it out. Testing can also help you identify weaknesses or strengths in your model. The downside to testing is that it takes time to churn through those gigabytes of data.

Backtesting is inherently a linear process. You feed in your tick data into your algorithm and expect some actions. You can’t really make use of fork/join to let other threads steal from the process queue as the later process depends on results from the earlier calculations. However, often times than not, you’re interested in testing many variations of a strategy. This is where MapReduce comes into play.

MapReduce is a Google software framework. It is inspired by the map and reduce functions ubiquitous in functional programming. They are as common as for-loops in the Java world.

The map function partitions an input into smaller problems and run them concurrently, e.g. each of the strategy’s variant is executed on a node.

The reduce function takes the results from all the nodes and aggregate them to get an output, e.g. back-test results from each strategy.

Having used functional programming for some time now, using map/reduce is very natural for me. Where my knowledge falls short is in implementing a distributed infrastructure for running these map and reduce with massive scaling beyond my own multi-core computer.

It just so happens that Amazon AWS has a hosted Hadoop PaaS. Where Hadoop is the Apache’s framework for MapReduce. Hardware, check. Framework, check. This will be the first second system that I’ll be working on in my goal to build a complete trading R&D platform.

Expect some technical discussions in the coming months as I work my way through. Now, where should I start…