What a year!

Now and then we release some interesting code. Here some of the highlights from the technical reports published in 2012.

2012-1

In this report we describe a binary-search program that performs O(1) branches and hence also O(1) branch mispredictions per search. How is this possible? The key is that an instruction like x = (a[i] < a[j]) does not generate a branch. And then you unroll the loop; the unrolling idea comes from Bentley's programming pearls.

2012-2

From this report you can find, among other things, a program that executes another program---a clean-up procedure---incrementally. The clean-up procedure executes O(k) instructions. Instead of doing this work in one shot, we distribute the work for k following data-structure operations by performing O(1) work per operation. Hence, each operation takes O(1) worst-case time. This kind of deamortization is considered trivial in the algorithm literature, but I have seldom seen it programmed. Here you can see such a program in live! It is a state machine having about 40 states and in connection with each data-structure operation about 30 state transitions are performed.

2012-3

Assume that you have a component framework like a collection of collections of nodes. A collection of type C₁ contains several collections of type C₂, and each collection of type C₂ contains several nodes of type N. Now your task is to program iterators for this data structure, say you want to iterate over all nodes in a single collection of type C₂ and all nodes in the whole collection of type C₁. Trivial? Yes, to be compatible with your standard library you write some hundreds lines of code and after an afternoon I do not expect you to be happy. The next day the collection of type C₂ should also support another traversal order. By reading the code in this report, you will learn that there are smart ways of doing all this.

Happy new year!

All rights reserved Jyrki Katajainen.