What a year!
Now and then we release some interesting code. Here some of the
highlights from the technical reports published in 2012.
- 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.
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.
Assume that you have a component framework like a collection of
collections of nodes. A collection of type C1
contains several collections of type C2, and each
collection of type C2 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 C2 and all nodes in the whole
collection of type C1. 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 C2 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.