Blog
From wikidev.net
Occasional 'computer science'-related notes by Gabriel Wicke.
July 2011: Software development and consulting: Open for business.
Since April I have ramped up my consulting, hosting and software development work again. A very interesting project I am just completing for Record Bay (http://www.recordbay.de/) is a highly optimized GrabCut (http://research.microsoft.com/en-us/um/cambridge/projects/visionimagevideoediting/segmentation/grabcut.htm) implementation for ARM processors, especially the various iPhones. Improved memory locality and conversion to fixed-point math dropped the run time on the iPhone 3G from about 4 minutes to 25 seconds. The actual implementation is all new, but uses a lot of the infrastructure from the excellent OpenCV (http://opencv.willowgarage.com/wiki/) computer vision library. The relatively simple data clustering algorithms (K-Means (http://en.wikipedia.org/wiki/K-means_clustering) or the PCA (http://en.wikipedia.org/wiki/Principal_component_analysis)-derived Orchard-Bouman Clustering (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.5595&rep=rep1&type=pdf)) used in this case for color classification renewed my long-held interest in machine learning and exploratory data analysis. If you have a project along these lines, drop me a line (mailto:wicke@wikidev.net) ;)
This was my first larger C++ project. I have long preferred the simplicity and efficiency of C combined with the compactness of Python, but after my forays into Haskell I actually liked what I saw in modern C++ and the Boost libraries (http://www.boost.org/). The Haskell background helps to quickly recognize the high-level ideas behind some (occasionally baroque) C++ template tricks. For example, traits in C++ can provide a very basic replacement for Haskell's type classes. Lack of support for static checking of type constraints and compiler error messages in template-heavy code are weak points, but can be worked around with care and experience.
January-March 2011: Writing a research proposal about Robust Distributed Transactional Memory
From January to March I worked at Kiel University. During this time, I continued some work on ByteMap (http://dev.wikidev.net/hg/trie), but mainly wrote a research proposal about highly robust and self-organizing distributed state with transactional and weaker consistency semantics. I am especially interested in how far transactional primitives in programming languages can be meaningfully stretched towards high availability by exploiting type-based semantics for reconciliation after a limited network partition. Locality is especially fundamental in distributed settings, which suggests either extensions to allow the programmer to directly express locality properties, or dynamic locality optimization based on observed usage patterns. My proposal still awaits some tweaks by Frank Huch (http://www-ps.informatik.uni-kiel.de/~fhu/) and Michael Hanus (http://www.informatik.uni-kiel.de/~mh/), after which it will be submitted to DFG.
Thesis finished 1 Dec 2010
Today I have handed in the final version (http://dev.wikidev.net/hg/trie/raw-file/452a5f9674f4/thesis/thesis.pdf) of my Diploma thesis with the title "ByteMap: Persistent and Locality-Optimized Trie for Disk and Memory". Yay! Soonish I'll receive a Diplom, the German equivalent (not quite, but close) to a masters degree.
Not surprisingly, not all features dreamed up made it to implementation. I spent a lot of time on the low-level storage management code, which includes both a Slub and a Buddy allocator, ensures consistency using allocation logging and uses memory mapping of Slubs to delegate buffer management and paging to the operating system. An (afaik) new idea of allocation spaces is used to improve locality of allocations and reduce the size of internal links (important for array-based tries) to 16 bits. The trie can still address a full 64-bit address space, but the degrees of freedom of outgoing links from each individual node is limited.
On the way back from Kiel I got stuck with the car in a big snowdrift for the first time in my life ;) A few minutes later our neighbor tried to pass me with his 4wd, but got equally stuck. The neighbor's tractor eventually pulled us both out. I was lucky not to get stuck two hours earlier on my way to uni, with dead-tree copies of my thesis on the back seat..
Back alive Oct 2010
After no activity on these pages for a long time I have decided to write something about my current projects and ideas again.
I am currently in the final stages of my diploma thesis at Uni Kiel (http://www.uni-kiel.de), a disk-persistent, transactional trie data structure written in Haskell. You can follow my progress here (http://dev.wikidev.net/hg/trie). There is also a presentation (http://dev.wikidev.net/hg/trie/raw-file/tip/talks/proposal/Presentation.html) about the early stages available.
