those moments

i very much enjoyed work yesterday. my colleague and i improved the runtime of a tool used mostly in-house by a factor of 100. fun. much fun. it now runs so fast the other guys will think it doesn't work.

i have read a book or two about optimizations and it is really interesting how much of applies to the real world. main conclusion (it is so obvious it really hurts)


never think about optimization until you know whats going on!


the program we put on steroids was know to be slow. it worked quite well for relatively small inputs but goes nuts when hitting bigger (10mb) chunks of 3D data. i did a huge improvement some time ago by using trivial caching. i picked up the cache-idea because the profiler i use told me exactly where 90% of the work was done: looking up strings. which was surprising since i suspected the algorithm itself but, profiler says "looking up strings" so i optimized "looking up strings". bingo.

the reason to look again on the tool in question was an actual bug where the algorithm was wrong a little bit. the bugreport mentioned a 150mb file as the input .. hehe .. i couldn't even RUN this in reasonable time to check out the bugfix. so my colleague and i discussed the whole algorithm in detail and pros and cons and "lets write it from scratch" and so on. next day i actually was closing the bug (since it fixed the problem which could be shown for much smaller files) and wanted to take a screenshot of what the profiler would tell me, so i would have a starting point when coming back to the speed issue later. i ran the profiler and ...

wow, what the heck? sscanf sucks big time!

as it turned out the actual problem was reading in LOTS of numbers (indices, vertices, texture coordinates) from a huge string. the program spent more than 40 minutes on just reading the numbers from the "big" 150mb file and was not even finished when we got tired and stopped it.

so, i have actually never done this before but the compiler said "sscanf is bad" so be it. i had even seen the sscanf popping up in the profiler when i did the first speedup but dropped further investigation by telling myself "well, we have to parse the numbers, face it".

but that slow? we started to write our own little StringToNumber function. as dan bernstein pointed out at 3.3:

The essence of user interfaces is parsing: converting an unstructured sequence of commands, in a format usually determined more by psychology than by solid engineering, into structured data.

and

The parser often has bugs: it fails to handle some inputs according to the documented interface. The quoter often has bugs: it produces outputs that do not have the right meaning.

the key to success now was the fact that we already do a preprocessing step to transform bad formated (valid, but bad for parsing) input into good (technically not valid anymore, but good to parse) one. but sscanf is prepared to be ultra flexible and ready for bad input, it throws away unneeded whitespaces, endlines etc. but all this flexibility comes at a price: speed. and since we eliminated the bad, bad formated input already we could skip exactly that: the error checking.

the resulting code looked somewhat similar like this but after the change our own function did not even stick its nose out of the crowd. in fact it ran so fast, we first really thought it was not really working. we took a "medium" sized input file (10mb) and timed the improvements: 4 minutes and 43 seconds down to 2 seconds. crazy.

so, conclusions:

1. do not draw any assumptions without backing them up


2. use a profiler (i use oprofile at home but at work i am a vtune fan boy


3. do not drop the idea of replacing a standard function by your own if the profiler says so :)

btw, the function that the profiler complains about now is called 'fprintf("%f")' ... hehe.


happy coding!

why to use a distributed vcs

almost a year ago i got my hands onto mercurial, a "new" bastard from the new and "hyped" distributed version control systems (vcs). i played around with it for a while and considered it pretty practical for my own needs, mostly for my own home brew software and some of my config files. until then i used mostly svn ... and so did fluxbox.

if you are working alone on some stuff, the distributed nature of the vcs doesnt really matter at first. but then, it does:

sitting at the airport without wifi i changed some of my config files and commited. i changed some work related project stuff and commited. without access to the company's vpn, because it is quite natural that some of the customers are not going to give you some visitor account so that you can transfer data "home" :) uh oh, danger danger. well, i could commit, store the stuff on the encrypted part of my laptop and then sync with the company repository when i am back home.

for fluxbox henrik and i played around with git as one of the other distributed vcs with a big "hype" in the last years (it was developed by linus for doing the version control at the linux kernel). at that time i had already some knowledge in using hg (which i still prefer for my stuff because it works much better on win32 [a must for the company i am working at]) but we wanted to test alternatives anyway to see what works better for fluxbox. henrik choose to use git at wayfinder where he works and so he become a bit pro-git and "anti"-hg just because he was more familiar with git. they work pretty much similar anyway, so i didn't really bothered and the rest of the gang didn't as well.

why did we even toying around with git / hg? i mean, we used svn for a couple of years, cvs before that. well, basically we went away from cvs for some reasons, partly because lack of features, partly because hosting the repository at sf.net started to suck. cvs was not available 24/7 (or better became a bit unstable on the servers from sf.net back then) and since the centralized nature of the vcs we decided to switch over to a more "reliable" alternative, which was berlios.de at those days. all was good until berlios.de seemed to have hit the same problems as sf.net some time before. but what if the central server does not work ... very unfortunate if you think of pushing changes to the server as well as fetching the latest changes.

notice: at the moment i just were covering reliability, i never mentioned merging or working on different branches. at the moment it was just a "if the central server goes away for whatever reasons, we are fucked".

another really important issue was, that for each new feature i had some directories with a fresh copy the current version. you can call it "branch" but it was not a real branch since it was not really tracked by the vcs. if each of us devs at fluxbox would have to make all the ideas public they are currently working on and pushing it into the one central repository, that place would become pretty much crowded. and that would be for useful stuff as well as for stuff that shouldn't see the daylight at all. so, i tended to not create a branch back in the cvs/svn days because some of the ideas were just rough material. but the downside was clear: no version control of my own code. bummer.

things are different now: i have my own little sandbox here, filled with some ideas PLUS the version control. if the central server we decided to use to publish the official fluxbox repository over at http://git.fluxbox.org/" dies or becomes unavailable ... well, thats bad for sure but all of the dev team PLUS all anonymous contributors can continue to keep track of their changes. and if the stuff from some of the contributors is worth sucking it into the main line of the project, well, thats just fine: it ends up in the main line as if the contributor had write access to the repository.

and thats better for all of us.

if you need a deeper and better explanation and/or further discussion in the topic of distributed vcs, then go and take a look over there.

user interface babblings

a couple of weeks back i tried out "enso", a software made by aza raskin and his folks at humanized.com". its a small tool which allows to handle several common tasks on windows via the keyboard (and the keyboard only). its in a way the same that "we" over at #fluxbox advise people to better work on their keybindings for fluxbox instead of wasting their time on the menu or on fancy icons on the workspace.

there is a joke about the only purpose of a xserver is to be a shell multiplexer (aka more than just one xterm open at the same time)... which is basically true :) at least i prefer to type in a set of commands into the good old command line instead of having to click myself through a deep hierarchy of items just to do the same. and even "shortcuts" placed visually on my desktop don't help because after a short period of time they become so many that things become messy.

on one hand the new fancy looking interfaces from mac os, vista or compiz and its companions are interesting but they don't solve the fundamental problem of how to present a lot of graphical items on the display. at least i don't need my 3 or 4 windows being rotated around on a cube, i doubt thats useful for anyone. the same goes for, as how i would call it, the "transparency hell". it is completely insane to write in a transparent gvim.

but on the other hand i tend to see user interfaces coming along which mostly allow to focus on just a couple of items and then allowing the user to zoom very fast to related items. and for those new interfaces all these play and gaming toys like rotating cubes with a firefox mapped onto it (which is very easy once you are able to use opengl textures :)) are going to be the shoulders of giants someone else referred to some time ago.

expect things like this to come. all the local search engines like google desktop, spotlight and others already show the way. i expect bigger screens with less simultaneous open windows but at a much speedier way to find related information.

btw, aza gave a little presentation at google, check it out.