Friday May 30, 2008

GridBagLayout for the Computer Scientists

I am by no means a hardcore GUI programmer. The best I've done is a couple of quick hacks written in Tcl/Tk. And even that somehow left me with an uneasy feeling that "things could have been better". One area that's always bothered me is how monolithic GUI components tend to be. This is especially problematic in the day and age of mobile, decentralized computing (why can't my A/V remote "jump" back and forth between my cell phone and my PDA?). This is a tough problem to tackle and the best attempt at resolving this seems to be a research project from Laboratorio de Sistemas Universidad Rey Juan Carlos Omero: Ubiquitous User Interface.

The next biggest issue is how difficult it tends to be when it comes to specifying the desired visual style of the GUI layout. Especially under dynamic constraints such as changing window sized and DPIs. Regardless of toolkits and platforms, the layout managers always end up either too simplistic and dumb or downright esoteric. There's got to be a better way! And there is.

Don't mind its scary title, the idea behind the approach is pure elegance: the layout is all about virtual grids (to which all object align) and the user defined constraints for how the grid cells related to each other. Of course, with the typical constraint being X is supposed to be twice as large as Y these constraints are of a nice, linear kind. Once the user is done specifying the constraints the solution actually comes from the computer (ain't it what computers are good for?). What's even better it can be easily recalculated under changing conditions without \*any\* feedback from the application. The Auckland Layout Model just works. Their example page is pretty convincing, even if the syntax desperately needs sweetening. Definitely this stuff is worth keeping an eye on!

Monday Jan 14, 2008

Cuckoo hashing: reinventing the wheel?

It is now a well accepted fact that not quite everything has yet been invented. But sure some thing have: the wheel, the internet search and hashing algorithm being just a few examples. At least I used to be of that opinion until a friend of mine pointed me to the radically new hashing method called Cuckoo hashing. I guess next thing on the list to be reinvented is the wheel, the internet search -- I'm not so much worried about.

Sunday Nov 25, 2007

OpenMP 3.0 tasking model: as smooth as Cilk?

There are 3 reasons behind this blog entry: first of all, the OpenMP 3.0 specification is now available for public comment. That in turn, made OpenMP ARB's CEO Larry Meadows proclaim The Birth of OpenMP 3.0 and introduce the most anticipate new feature: the tasking model. Finally, I've just got back from Super Computing '07 in Reno where OpenMP BOF took place and clearly showed that the OpenMP 3.0 tasking model is not well understood and, worse yet, it seems to be missing a number of important capabilities. Before I jump to my critique, let me just point out one thing. There is no doubt in my mind, that OpenMP 3.0 represents a step in the right direction, yet I can't help but notice its slow pace of development. If it took us 10 years to get to the point where explicit tasks are possible how long would it take us to make them actually useful? And in the meantime, wouldn't programmers be better off sticking to something like Cilk or Rapid Minds frameworks? [Read More]

Thursday Oct 11, 2007

Transistor overproduction crisis

With every single IT publication now explaining the difficulty of parallelism and multithreaded programming, one has to wonder why do we have to go to all this trouble of managing multicore in software. Isn't it all just a manifestation of a desperate hardware industry trying to ram surplus of transistors down developer's throats much the same way industrial agriculture rams the surplus of crops? Are multicore chips going to be as much a damage to your brain as soft drinks (AKA liquid corn) are a damage to your stomach? And finally, is there a better way? In other words, what is the ethanol revolution of the hardware industry?[Read More]

Monday Jun 18, 2007

If you think that XML is the answer, chances are you misunderstood the question

But people try to apply XML to everything they see nevertheless. Sometimes, however, the results are not just sad, but downright spooky:
Date: Wed, 23 May 2007 10:11:57 +0200
From: Lluis Batlle 
Subject: Re: [9fans] XML
To: Fans of the OS Plan 9 from Bell Labs <>

Lately I've been told at work to use a library in C. Most calls have
the signature

  ErrorType function(const char \*xml);

I have to pass to them xmls of more than two levels deep, attributes,
and around ten elements.

When I asked why such interface to a library, claiming that it was
uncomfortable to me, the lib developer told me that in fact
xml-parameter-passing was one of the techniques he liked most, and
helped him solve a lot of problems easily.

Saturday Jun 16, 2007

C++ STL: still paying for what I don't use.

One of the great tenets of C++ has always been: "you don't pay for what you don't use". Bjorn seems to use this very line everytime he bashes Java or LISP-like languages. The later is especially noteworthy since he is usually pretty honest in acknowledging that functional languages do posses a number of important qualities such as having an expressive power of writing qsort as a trivial two liner
 qsort []     = []
 qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
at the expense of wasting quite a lot of precious resources such as RAM and CPU cycles.

Now, from time to time I see folks showing examples of C++ code bordering on the same expressive power. Take this little word counter ($ wc -w) for example:
int main() {
   std::cout << std::distance(std::istream_iterator(std::cin),
   return 0;
It looks impressive if nothing else, and since it is, after all, C++ everybody expects it to perform quite well. But does it?

To answer this question without dragging the reader into the dark realms of assembly language or black art of performance measurements I would really love to have a good old Cfront around. Or any other tool for that matter that would be able to retrace what exactly all the templates and overloaded functions got expanded into. Alas, I don't know of any such tool (if you do -- please leave a comment!). So bear with me while I'll be using my stop watch ;-)

For the speed trial lets compare it to the similar code written in C (and to make it fair I am going to even use scanf instead of a handcrafted code):
int main()
    int count;
    char buf[65535];
    for (count = 0; scanf("%s", buf) != EOF; count++)
    return printf("count %d\\n", count);
Not that I am surprised, but C++ version ended up being 1.5 slower on my machine. And if you compile the above example into .s file and look at what main() turned out to be you can see a reason why. There is about 6 function calls there. Pretty much nothing got inlined or computed in-place.

Bad implementation of a fine idea? Perhaps (I tried two: G++ and Sun Studio). But it makes one wonder why in 28 years the world hasn't yet seen a good implementation. It's not that the industry hasn't tried, you know.

Am I hearing the ghostly murmur of Algol 68 or is it just my imagination?

Saturday Mar 31, 2007

What does dynamic linking and communism have got in common?

It is simple enough, really – both were ideas that sounded nice in theory but came crushing down during their first serious brush with reality. And since there's no shortage of experts trying to explain how come communism wasn't meant to be – I'm going to focus on the other one. But before I do, I want to make it extra clear that this article is about dynamic linking and not dynamic loading. The later one consists of dlopen(3)/dlsym(3)/dlclose(3) and is a fine idea. Dynamic linking on the other hand is all about magic that makes your application work, even though bits and pieces of it might be in places you've never heard of. And, of course, as any magic it does promise a lot. Among the biggest claims of the dynamic linking (as it is currently implemented in UNIX and similar OSes) are the following three:
  1. all applications are capable of sharing common code at runtime, thus reducing total memory footprint of an entire system
  2. all applications can reference common code without actually storing it as part of their ELF (or similar) file image, thus reducing total storage footprint of an entire system
  3. you can fix problems in common code, thus benefiting all of the applications available on your systems at once
May be there are others, but these three are most commonly cited in favor of justifying the mind boggling complexity of the modern dynamic linkers (and if you don't believe me how complex they are – try asking our resident Solaris linker guru) and even bigger complexity of how, what I referred to as, "common code" is supposed to be packaged and delivered in order for the magic to work. Of course, given the price we pay in complexity I would expect dividends to be quite significant. Unfortunately, they are not.
The rest of this article discusses why dynamic linking does not deliver on any of its promises and why, just as communism, it might be an idea that only works in an ideal world (as a curious footnote I must add that just as communism done right seems to be doing quite well in one particular eastern country, dynamic linking within a binary compatibility guarantee of one particular OS gets as closed to being true to its promises as one can get).
The goal of this article is not to present an alternative model (I still don't have a 100% satisfactory one even for dynamic linking; not to mention communism) but to merely make the reader question whether static linking is, in fact, long dead and buried or may be the people who try very hard to make us think that way have just spent too much time in an ivory tower and haven't seen the real world in a while.
With that, let me start with tackling the last purported benefit of dynamic linking (an ability to fix problems in common code) not only because it is the easiest to knock down, but also, because once knocked it virtually eliminates the first two benefits completely. An ability to fix problems in common code and effectively addressing it once instead of doing it as many times as you have applications sharing that common code sounds really nice till you ask yourself -- what is a "problem"? What is a bug? And could it be that one application's problem is something that a second application depends upon in order to work properly? The answer to the last question is a resounding YES and there's no better example than a very prominent C++ compiler vendor who had to leave a pretty nasty C++ ABI bug unfixed for a number of years just because any possible fix would break all previously compiled applications. And of course, since C++ runtime library is dynamically linked into any application written in C++ that was unacceptable. You see, in real world programs have bugs. Worse yet -- the line between a bug and a feature sometimes gets quite blurry. That is especially true for common code. Why? For two obvious reasons: first of all, since most likely than not you didn't write the code shared by different applications yourself you have no way of knowing whether your usage patters of that common code do indeed trigger a bug, or whether they are just an example of GIGO principle. Second and most importantly -- you are very likely not to have any control over the common code and even if you can prove that the problem is indeed a bug you'd rather workaround it than wait for a vendor to issue a patch. These two issues combined create a very unpleasant situation where problems in common code now become unfixable not because we can't fix them for good, but because the old buggy behavior is now something that quite a few applications depend upon. This is a classical "doomed if you do, doomed if you don't" principle at work. But where does it leave us as far as dynamic linking goes? In a mess! And a big one at that. All of a sudden we have a system where half of the applications want that piece of common code fixed and the other half wants it broken. All of a sudden we have to make sure that we CAN isolate applications that still depend on an old buggy behavior and the magic of dynamic linking just starts getting blacker and blacker with abominations like LD_LIBRARY_PATH and DSO symbol versioning. What we've got on our hands now is a simple situation where common code becomes segmented in a sense that it is common among just a subset of applications. And that is the point where dynamic linking just breaks. There's no way for my application to be sure that the same common code I tested it with is the one that is being in use. And for any serious software vendor that is just unacceptable. You see, serious software vendors care about their customers and they don't play finger pointing games saying things like: it is all your fault you should have not upgraded that shared library over there. What do they do instead? Well, just try to do
find . -name \\.so
to see for yourself. If you do that with any commercial piece of software (or even free large ones like Open Office) don't be surprised to see things like private versions of being repackaged and redelivered. It is much safer for them to do that instead of constantly dreading the ugly upgrade of /lib/
But wait! Haven't it just annulled the first and the second claims that the dynamic linking had? Sure it did. There's no sharing possible between /lib/ and /opt/bigapp/lib/ None. The memory gets wasted as much as the diskspace does. It might as well be static linking at that point.
In fact, static linking would be quite beneficial for the application since if done right with the smart compiler it would enable things like: not wasting precious CPU cycles on position independent code (if you think PIC is free see Performance Analyzer in action), doing interprocedural optimization, cross-file inlining and template elimination. And a few others. And unlike dynamic linking you can be dead certain that the very same code you tested would be working at your customer's site. Not only that -- but when you do need to fix it, you fix wouldn't break anybody else.
Ain't this the magic?

Sunday Feb 11, 2007

Babbage: Tesla of computing ?

I've always known that Charles Babbage had a few good ideas on how to build computing devices. Yet, it was only after a friend of mine had pointed me at Babbage was a true genius post when I realized that Babbage was the sort of a guy who could have turned the world into a different direction had he succeded. For anybody interested in the history of computing -- this is a must read.

Thursday Nov 09, 2006

Performers of the world -- UNITE!

This is perhaps a bit of old news, but since I turned out to be forgetful enough not to blog about it when it was time here it goes. Together with Federico Lucifredi we've created a mailing list on google groups dedicated to everything computer performance. Personally I don't anticipate this list to be a high traffic one but more of meeting place for everybody who's interested in making computers run faster to hang around. So that when anybody has a question our collective intelligence can be easily accessible. Also the list seems like a perfect place for distributing information on performance related events, papers and ideas.

Long story short -- if you know anybody who fits our profile make this person join today!

Sunday Oct 22, 2006

Is Java still incompatible with UNIX ?

I remember how when I first heard of Java back in '96 I got pretty excited not because of the OOP language it offered (I was already sold on C++) and not because of the grandeur API it had (I simply don't believe in APIs more complex than LEGO bricks) but because its JVM offered a glimpse of what at the time seemed like a potential escape from the conundrum of modern CPUs – they all are but a VM for a C language. The only reason you've got MMUs in every decent CPU these days is because C VM has to support pointers. If only JVM could be efficiently cast in iron...

Unfortunately this particular nut proved to be quite difficult to crack. The demise of the Project Barcelona was even more frustrating, simply because its premise, requiring a single “instance” of JVM for running all Java applications – even from different users, seemed to be an ideal compromise between the difficulty of switching all the way to JVM-based CPUs and constantly having to lug a pretty hefty JVM around for running even the tiniest Java application (just for fun, try measuring how much RAM and CPU cycles would be consumed by a “Hello World” written in on your system). All of that, of course, means that 10 years later I find myself in a situation where when I have to implement a bunch of small GUI tools and utilities according to the UNIX tooling principle – each tool is small, convenient, does exactly one thing but does it well – Java is still not a good choice for me. I simply can not afford spending that amount of resources every time I need an 'echo' or 'ls' functionality of the GUI world. Platforms (such as NetBeans) are even worse in that regard, since not only do I have to tax myself with JVM, but each instance of JVM would have to suck in a fat layer of the platform itself. Since all of the JVMs are separate it means no sharing whatsoever even if I use the very same NetBeans classes in all of my little tools. Is Java still incompatible with basic UNIX philosophy ? You decide – for me the answer is clear and my only hope is that with Sun OpenSourcing Java somebody will pick up where Project Barcelon left off. But for now – I guess I have to teach myself some Qt :-(

Friday Jul 28, 2006

Why Plan9 is relevant today

I just can't resist to publish the following two writeups on why Plan 9 is as relevant today as ever. It comes from Skip Tavakkolian and it was originally posted to For those who are still not convinced here's a link to the project of Microsoft + Whirlpool where they connect two most unlikely gadgets together. I'm sure it is painful to do under Windows. And I know how easy it is under Plan 9. Enjoy!

Skip says:
The future is now.  how many digital gizmos does a person 
have? mobile phone, ipod, digital camera, pots phone. throw 
in a pda, a laptop and a desktop and there it is.

what's the killer app for plan9?  the vector is toward 
distributed access to resources.  9grid is extending the 
sharing to process space. we're betting on our shared name 
space system.  apps for collaboration are another area of 
possibility; checkout VN's solutions based on inferno.  
plan9 doesn't need to be "in your face" to be useful.  the
way we're using plan9, it is transparent to the end user.

the amount of success is directly related to the amount 
of money behind the os or platform. linux offered real 
savings on acquisition and maintenance over windows; 
windows' success was in providing a common platform for 
"productivity" applications, that had positive returns 
on investment to the user and revenue to the app developer 
- the largest being ms itself.

once a killer app is created that shows a clear advantage 
for using plan9 over other os, it will be adopted.  
availability of p9p means that app developers can take 
advantage of the model, while still satisfying any dictated 
requirements for a more known os; this is likely to be the 
case early in the adoption curve, despite the fact that 
plan9 is much easier to learn and maintain than other os

Friday Jun 30, 2006

On LEGO bricks and OS design

It is not always that we can explain our deep attraction to particular patterns be they real or imaginary. To some extent that is exactly what makes art so subjective. But even in the realms of programming these matters hardly become any clearer. Why does the majority of computer scientists and programmers find recursion particularly exciting ? Well, I guess we can speculate all we want but it won't get us any closer to really answering this question.

Now, as I've told everybody time and again -- I love Plan9. I think its the most elegantly designed and implemented OS since the dawn of UNIX. And anything else (be it Linux or Solaris) just pales in comparison not only in the pure artistic sense, but also in a number of very practical areas. I truly believe that Plan9 and its ideas were somewhat ahead of their time and anybody seriously considering a fully networked world of devices ranging from one bit sensors to full fledged humans must study Plan9. Its like that old LISP saying: "If you don't know LISP you're bound to reinvent it. Poorly".

An excellent introduction into Plan9 philosophy does a nice job of explaining the 3 key ideas on which Plan9 is built:
    "The view of the system is built upon three principles. First, resources are named and accessed like files in a hierarchical file system. Second, there is a standard protocol, called 9P, for accessing these resources. Third, the disjoint hierarchies provided by different services are joined together into a single private hierarchical file name space. The unusual properties of Plan 9 stem from the consistent, aggressive application of these principles."
but it does nothing to help understand why so many smart people find them (and especially the first one) particularly exciting and somehow very powerful.

It took me a number of years of thinking about it, one trip to Madrid and a conversation with the brilliant computer scientist named Nemo to finally come as close to a conscious explanation as one can get.

Its rather simple, really, as an application developer my ideal world would be the one where I can reuse useful components/services literally in a manner of LEGO bricks. The world where a component that gives me a "binary editor" capability would be equally easily accessible from my debugger, my editor, the application I use to edit fonts, etc. Ideally I shouldn't even care about where component resides or what language/infrastructure it is implemented in. A SOA of sorts.

Do we live in an ideal world ? Not really, but before I state why Plan 9 comes as close to it as one would hope to get, lets look at some of the "proposed" solutions to this universal reusability problem.

Java comes to mind right away. Its widespread and it abstracts you sufficiently enough from the outside world, so that you don't have to care how to create threads or windows -- its all part of the grandure API. It also provides the level of reusability I've mentioned via [Net]Beans and such. However, the unbelievably high price you have to pay for this is that you absolutely have to remain in Java's world. Both from an VM and from an API standpoint. Suppose I even have that binary editor module coded as a [Net]Bean and it works fine in that framework, but can I get to it from my favorite editor ? From my favorite debugger ? From a command line prompt ? No! I have to use Java and Java alone to "glue" this piece of functionality to the rest of my working environment.

It is sort of like having LEGO bricks which not only do not stick to each other if you put 'em together, but require a particular brand of glue to form any sort of complex structure. The glue called Java in my previous example, or the glue called C language, or what not...

Now, the question becomes is it even possible to have anything at all which would let my LEGO bricks just stick together ?

My answer is -- yes and it is called files!

Files are my true universal glue, the lowest common denominator of sorts, the one and only API present in absolutely \*all\* common programming languages and systems.

It takes a bit of time to realize just how far the lack of files as a universal glues pushed various developers. Do you know that when you do "getline a < /inet/tcp/lport/rhost/rport" in (g)awk the right thing happens ? Do you realize how much extra code was duplicated and how many bugs were reintroduced ? Same question about all these jolly Java APIs -- sure its fun to reinvent the wheel, but you should at least start from wood, not from carbon molecules...



Top Tags
« June 2016