Just about three years ago, I created the
automatic rule-based time
tracker (arbtt), a tool that quietly runs in the background, records
your current windows and their titles, and allows you to later process
this data using, well, rules. By now, I have almost half a million
records, spanning 317 days of me working at the computer. Processing
this amount of data has become very memory-hungry: It takes 1G of RAM to
process my data. Other users, with a presumably higher sampling rate,
report even worse performance, which finally made me approach the problem again.
Naturally, one wonders why it is such a memory hog, after all it
takes just one run over the data to produce a report. The data itself is
a lazy list so the garbage collector should the be able to drop the
seen elements immediately.
But arbtt is able to print several reports in one run; there is even
an option (
--each-category) that creates a number of reports based on
the data itself. The code was structured that first a number of values
that are possibly used by several reports are first created one and then
re-used by the reports. And then there is the issue of the filters: The
user specifies a what predicates are interesting (e.g., those where he
was active) and some reports need to know not only which samples were
matched, but also distinguish the consecutive runs of selected samples.
Lots of reasons that made it hard to not use the list of of samples
several times, which causes it to be completely retained in memory. The
idea of completely rewriting everything in a much more imperative way
was not appealing. But luckily Haskell s good abstraction possibilities can help here.
What is the correct way to traverse a lazy list and calculate some information about it? It is a strict left fold, i.e. an algorithm that can be represented as arguments to
foldl' :: (s -> x -> s) -> s -> [x] -> s
For those who are new to folds: The first argument is a function that processes one element from the list, returning the new state of the processing. The second argument is the initial state. And
foldl' can apply such an algorithm to a list to return a final state.
So obviously I had to express my reports as left folds. To think clearer about it, I gave them a name. I also added a finishing step to the mix, which is handy:
data LeftFold x a = forall s. LeftFold
start :: s,
process :: s -> x -> s,
finish :: s -> a
A value of type
LeftFold x a is then an algorithm that traverses a list of
xes and returns something of type
a. The
forall s. means that the user of such a processor must not make any assumptions about the type of the state. I also have a function that runs such a list processor, simply by invoking
foldl' with the arguments stored in the
LeftFold constructor:
runLeftFold :: LeftFold x a -> [x] -> a
runLeftFold (LeftFold st1 p1 f1) xs = f1 (foldl' p1 st1 xs)
Now, as a Haskell programmer, I am searching for monads everywhere, and it really would have been nice if this were a monad, as they are very easy to compose. But unfortunately, they do not form a monad. If they did then I could decide after running one processor and looking at the result how I would want to process the list now, but this obviously contradicts with the desire to traverse the list only once.
But there is the monad s smaller ugly sibling, the applicative functor. One can still somewhat nicely compose them to form more complex algorithms, just with more restrictions. Here is my instance:
instance Functor (LeftFold x) where
fmap f (LeftFold st1 p1 f2) = LeftFold st1 p1 (f . f2)
instance Applicative (LeftFold x) where
pure x = LeftFold () const (const x)
LeftFold st1 p1 f1 <*> LeftFold st2 p2 f2 = LeftFold
start = st1 :!: st2,
process = \(s1 :!: s2) x -> p1 s1 x :!: p2 s2 x,
finish = \(s1 :!: s2) -> f1 s1 (f2 s2)
The
:!: operator is a
strict tuple constructor. This is important, as otherwise the fold would be come a lazy one, I would be building up huge numbers of thunks and performance would be very bad. For the same reason every list processor should make sure that its state does not build thunks once it is in weak head normal form.
Now I am at a abstraction level that I feel comfortable working in, by writing functions that combine the list processors in various ways. Probably the most important one for me is already present in the libraries (here with a specialized type):
sequenceA :: [LeftFold x a] -> LeftFold x [a]
This is the whole trick: Now I can, based on the user input, run any number and selection of reports in one single list traversal. I find it very elegant that under the hood , the strict tuples are nested at precisely the right depth depending on the length of the list.
As hinted at before, I do some interesting stuff that was previously represented as lists of lists of values. Expressing these as left folds was a bit tricky, but again, the complexity is contained in the combinators that I wrote (although it still gets confusing, check out
processIntervalReport in Stats.hs):
monoidFold :: Monoid m => LeftFold m m
mapElems :: LeftFold y a -> (x -> y) -> LeftFold x a
filterWith :: (x -> Bool) -> LeftFold (Bool :!: x) a -> LeftFold x a
onSelected :: LeftFold x a -> LeftFold (Bool :!: x) a
onJusts :: LeftFold x a -> LeftFold (Maybe x) a
onAll :: LeftFold x a -> LeftFold (Bool :!: x) a
runOnGroups :: (x -> x -> Bool) -> LeftFold x y -> LeftFold y z -> LeftFold x z
runOnIntervals :: LeftFold x y -> LeftFold y z -> LeftFold (Bool :!: x) z
lfLength :: LeftFold x Int
lfFirst :: LeftFold x (Maybe x)
lfLast :: LeftFold x (Maybe x)
toList :: LeftFold x [x]
concatFold :: LeftFold [x] [x]
As a result, the program now only requires 10MB and runs 18% faster.
If you wonder why, in the definition of
runLeftFold, I do not apply the finish function strictly: That is intentional; I am actually passing the result of a processor that calculates some often required data (e.g. total time recorded) as an argument to all the list processors. (Near the end of the main function in
stats-main.hs) This loop works fine as long as I am using these only in the
finish functions.
There is one downside to this approach: I cannot easily calculate stuff on demand
and share it between two reports. Previously, I could just bind this to a variable, pass it to all reports, only if at least one is interested it would be evaluated and if several are interested, the result would be shared. I do not have a good solution for this yet.
The code above is in the self-contained module
LeftFold.hs in the arbtt sources.
Several People have had this idea before, here is
one blog post by Max Rabkin.
Flattr this post
good to see that there are again Bug Squashing Parties going on, & that
quite a few people send patches to the Bug Tracking System &/or make
Non-Maintainer Uploads. here are my contributions for this week:
How to get it
As St phane mentioned in the python3-lxc blog entry, the API hasn t yet been finalized and llxc itself is in an early state and many changes are planned, so it s definitely not meant for production use yet, but since we believe in release early, release often in the free software community, here goes
Currently, llxc.py itself is *very* Ubuntu specific and its only been tested on Ubuntu 12.04, but that will be fixed once more of its kinks have been ironed out. Some people are also working on getting python3-lxc on other distributions, which will help a lot.
The llxc.py script itself is hosted on Github: 
Heyya, World!
I ve just got to 
Thoughts about DRI.Next
On the way to the X Developer s Conference in Nuremberg, Eric and I
chatted about how the DRI2 extension wasn t really doing what we
wanted. We came up with some fairly rough ideas and even held an
I was invited as a panelist for the 
I'm just back from having spent a week in Helsinki. Despite some minor irritations (the light-switches were always too damn low) it was a lovely trip.
There is a lot to be said for a place, and a culture, where shrugging and grunting counts as communication.
Now I'm back, catching up on things, and mostly plotting and planning how to handle my backups going forward.
Filesystem backups I generally take using backup2l, creating
local incremental backup archives then shipping them offsite using
rsync. For my personal stuff I have a bunch of space on a
number of hosts and I just use rsync to literally copy my
~/Images, ~/Videos, etc..
In the near future I'm going to have access to a backup server which will run rsync, and pretty much nothing else. I want to decide how to archive my content to that - securely.
The biggest issue is that my images (.CR2 + .JPG) will want to be encrypted remotely, but not locally. So I guess if I re-encrypt transient copies and rsync them I'll end up having to send "full" changes each time I rsync. Clearly that will waste bandwidth.
So my alternatives are to use incrementals, as I do elsewhere, then GPG-encrypt the tar files that are produced - simple to do with backup2l - and us rsync. That seems like the best plan, but requires that I have more space available locally since :
We've been thinking about getting a dog for ages,
but it's been difficult to work out the logistics when we've been
travelling so much. Well, today's the day!
Hey, long time no see!
Okay, so what's new in FusionForge land these days? Well, I guess the
most prominent news is that we've just declared 5.2 stable. It's been
uploaded to 
Some days ago I moved to 
Last week, I was 
We had a very very nice little party with our family and a small group of friends Of course, due to the nature of our life, we could not forego inviting our family and friends in Argentina, as well as those in other parts of the world, so we set up a simple video stream so that our friends could follow along And they did, with much greater success than what I expected!
So, besides those people present with us in Cuernavaca, we had people tuning in (at least to the degree I could get from the log files) from Argentina (Buenos Aires, Paran , Formosa), Austria, Canada, France, Germany, Hungary, Italy, Macedonia, Mexico, Poland, Spain, Sweden and the United States.
This next Saturday (September 29) we will have a second party, to which our friends in Mexico are invited, at home. And for the people from far away,, 
A couple days ago, I woke up to this exciting series of text messages
from a unfamiliar phone number.
Because I've not received a reply in the last couple days, because it
was a Seattle phone number but I haven't lived in Seattle for years,
and because I don't know of anyone in Seattle who was about to give
birth, I'm pretty confident that this was indeed a case of misdirected
text messages!
But whoever you are: Congratulations! I know it was a mistake, but
that really made my day!
Data, once put on the internet, are quite hard to delete. You can most likely delete (or ask for deleting) them from place where it has been originally distributed, but you can be never sure where else it has appeared.
Recently, I've seen several requests to remove some data from 
