Friday, October 24, 2008

Practical Stuff: Models, Theories, Abstractions

by Jesper Larsson

They are usually mentioned only in a few fields, but models are actually everywhere in computing. In fact, it is the key concept that lets computers do things for people to find interesting.

The word model can mean many things, some of which are shown in the collage below. I am not talking about any of those. Nor am I talking about the technical use in logic (an assignment of constants to variables that makes a sentence true), despite the close tie between logic and computing – particularly databases.

Models Photos by Nguyễn Thành Lam, Erik Hersman, Richard Smith, MaZzuk (some rights reserved).

No, I am talking about a model in the sense of an abstraction. A simplified representation of something. A framework for naming and envisioning non-physical objects to allow reasoning about them and shaping theories about them. Often by use of metaphors – analogous concepts picked from a well known domain.

The picture below is an example of a sort of abstract model that most computer users encounter. It shows a set of folders, or files, which in turn are the contents of another folder. But of course, they are not really folders. Folders are made of paper and kept in file cabinets. These are just images on the screen that symbolize something that we think about as analogous to real folders.

Folders The physical constructs beyond the abstraction is not something the average user needs to be concerned with. In fact, the folders can, and do in this case, represent quite different things. Some of the folders in the picture are things that are kept on my local hard drive, but some are network connections. Since they, from a certain aspect, all support the same set of operations, we can interact with them using the simplified view that they are a homogeneous set of objects. That is part of the model of this file browser interface.

Computers operate through level upon level of models, starting (unless you want to get metaphysical) with voltages in electrical circuits, progressing to boolean logic, machine language, and so on, and perhaps via one or several virtual machines, up to, finally, the model that the user of the program understands.

Intuitive Models

Models were not invented for computing. Everybody thinks intuitively in levels of abstraction. Generally, people have no problem accepting that if you look under the surface of the simplified concepts we accept as objects or concepts – things of various kinds – you find a more fine-grained physical level of existence, which is quite different from what we usually perceive.

But strangely enough, some people, computing professionals in fact, sometimes fail to understand that the model can be independent of the lower physical level. I have suffered from this myself, and perhaps I still do in some areas, but I have gotten a lot better over the last few years.

Programming Languages

When I have told people that I develop high-performance systems in Java, I have often (less now than a few years ago) had the surprised reaction “but Java is so slow, how can you get it fast enough?”

Java is a language which, like other programming languages, expresses sequences of logical (in a wider sense) operations. How could a language possibly be slow, or fast for that matter? Consider the following Java code that calculates a number in the Fibonacci sequence:
    long s = 0, t = 1;
    for (int i = 0; i < n; ++i) {
        long u = s + t;
        s = t;
        t = u;

Now, take a look at the equivalent code in C++:
    long s = 0, t = 1;
    for (int i = 0; i < n; ++i) {
        long u = s + t;
        s = t;
        t = u;

Which one is faster? How can any of them be faster? They are exactly the same! (Java and C++ are closely related languages with the same basic syntactic elements.)

Now, perhaps you think I am just being difficult. Obviously, what people mean when they say that Java is slower than C++ is not that the language per se is slow. It is that code compiled with a Java compiler and executed in a Java runtime environment is slower than the same code compiled by a C++ compiler and run by the operating system directly. This is because the Java runtime environment is a virtual machine – an interpreted system. It is a program that looks at one instruction at the time and changes its state accordingly, just like the physical machine that the operating system is running on. This extra level adds overhead.

Is this true, then?

It certainly was true – about ten years ago. But then just-in-time compiling came into use. Virtual machines with this feature did not execute instructions directly, but compiled them to machine code the first time it saw them, and fed the machine code into the physical machine. This could get almost as fast as compiling directly, but it still had the overhead of compiling in runtime.

Finally, the HotSpot virtual machine arrived. It did not just compile everything it saw. It gathered statistics about which parts of the code was run more often, and made a greater effort to produce efficient code for the more frequent parts.

About five years ago, when I got into a discussion with someone who claimed that Java was inevitably slower than C++ for tight loops, I did a comparison between Java and C++ execution, on tight-loop code similar to the Fibonacci calculation code above. The Java code executed in the HotSpot virtual machine was significantly faster than the C++ code compiled by GCC with full optimization and run directly on the physical machine.

The explanation is that the Java environment, doing the compiling in runtime, has more information at its disposal than the C++ compiler. Hence, it is able to generate more efficient machine code.

This was (and still is, I imagine) astonishing to a lot of people, stuck with the interpretation overhead stigma.

The point of all this is that the language – the model, so to speak – does not determine whether executing code is efficient or not. The language is just a way of expressing transitions from one machine state to the next. What ultimately should matter for efficiency is the computational complexity of computing the next state. There is, in theory, absolutely no reason why code expressed in one model should be less efficient than another. If the system is smart enough, it can execute it in the most efficient way anyway. This is the true meaning of the word optimization.

What is called optimization in practice is not really optimization, because it rarely finds the optimal code. It just finds code that is, hopefully, better than a naive translation from high level language to machine code. I suppose true optimization in general is impossible. (I have not found an actual proof, but it feels like it would be related to computing Kolmogorov complexity.) However, in every case where the system can recognize a piece of code that expresses something it has an efficient execution method for, it can use that method.

The evolution of Java systems is an excellent example of how an improved implementation can increase performance without changing the model.

Next Time: Data Models

The main point that I want to make about misunderstood models has, as you might expect (and as promised at the end of the previous post), to do with database systems. But this post is already quite long, and I do not want to cram in the most important subject at the end. You may already have guessed the essence of it, but for the details I again have to refer you to a future post.


mattias said...

very insightful, thanks!

Simon said...

Great. Looking forward to the next. Models is a topic in focus for us at the moment.

Håkan (hakke) said...

I love modelling and am rather uninterested in the implementation. Your text certainly supports my desire to keep these two apart, and not let efficiency issues obscure the modelling work.

All I now need to do is to develop trust in the implementers of thuis world, so that I can faithfully delegate the task of runtime optimisation. This, I am sure, will not come easy to me.

Jesper Larsson said...

Håkan: I am not sure how much of your comment is sarcasm and how much is wishful thinking, but the conclusion that you can safely leave efficiency issues to someone else is wrong for several reasons. Some of the reasons are regrettable and some are not.

Håkan (hakke) said...

Oh, if I was sarcastic it was only aimed at myself. I am eager to deal with the things I like, abstractions and such, and rather lazy when it comes to more practical matters. (And still not very good at delegating stuff and not poking my nose into what is done, and how.)

By sharing your insights I will hopefully learn more on the subject of modelling and implementation. I will certainly enjoy more, so far I have been reading with a smile. Not a smile of sarcasm, but the smile that comes from being enriched. Thanks!

Jesper Larsson said...

An anonymous commenter just posted a kind comment ("Very pleasant reading. Looking forward to more posts.") which I decided to reject because it was not in English. Thanks for the compliment, Anonymous, but please make any future comments in English (Google Translate is nice), since this blog is directed at an international audience.