Thursday 17 June 2010

Poul-Henning Kamp popularizes algorithm research

"Think you've mastered the art of server performance? Think again." Poul-Henning Kamp recently published this article with the quote, which basically says that a binary-heap tree structure is inefficient and should not be used. Poul-Henning (PHK) has recently spent more of his spare time on blogging and making his views known to the public, and he writes articles that often spark great debates.

In this particular case, PHKs knowledge about virtual memory and high performance in cache-intensive applications makes him complain that so many fellow programmers consider a binary tree in memory efficient. However, the counter-argument is that this is known knowledge among algorithm experts, and some actually complain that PHK's article was published in ACM despite of that.

However, how many of you have attended an algorithm conference lately in order to get updated with the latest news? Probably not many. And even if you dig into algorithm science, the sheer number of algorithms for rare cases is overwhelming. PHKs article may not benefit many directly. Many programmers don't use much RAM, develop in frameworks that anticipate that there is more physical RAM than needed (Java, .net), or don't want to invest time into extra performance. But it does illustrate how programmers should innovate their algorithms while solving problems, and the article definitely applies to Delphi programming.

Many great things were achieved because somebody tried to do things just a little better.

1 comment:

Anonymous said...

This is not really earth shattering news. Already in the 2003-2005 timeframe this (binary trees are a nono) were popularized.

One of the problems of better alternatives (like Judy Trees), are their relative complexity.