Bytecode interpreters, virtual machines, emulators

Lately I've been working on programming a utility that translates more or less natural text to more cryptic firewall statements. In the translation process, I use two passes: the first pass translates to bytecode, and the second pass translates from bytecode to the final output. A huge advantage of using the intermediate bytecode stage is that this makes it possible to easily support multiple kinds of firewalls while having only one syntax for the input. The code for the output generator is completely decoupled from the input parser code. Cross compilers work in the same way. Modern compilers like gcc also work in a different way; they support multiple frontends for compiling different programming languages.

When I was still a student, I once wrote an assembler/disassembler for a nonexistent architecture. While a nonexistent architecture may seem an odd choice, I was inspired by the Java bytecode that executes in a virtual machine rather than on a real CPU. The professor did not give me a straight A only because I had not actually written the virtual machine that would run the code. The instruction set was rather extensive and implementing the full virtual machine would have been too much work for the limited time of the assignment. The feeling of what if always stuck with me however.

An emulated CPU has the following properties:

• a bunch of general purpose registers
  
• a program counter (this is just an address; the instruction pointer)
• a stack pointer
• a flags register (with a zero, sign, carry, overflow flag)
• optionally: interrupt flag or current interrupt level
  
• optionally: supervisor mode flag or current privilege level
  

Emulated interrupts enable you to let the system interact with I/O devices much like it happens in real computers. Whenever an I/O device is ready, it will interrupt the CPU, which will then automatically jump to the Interrupt Service Routine (ISR). The address of the ISR is read from an interrupt vector table that typically resides at a low memory address.
The supervisor mode or privilege levels offer the possibilities of implementing a sturdy “operating system” in the virtual machine, adding a hypervisor, and ultimately having virtual machines running in virtual machines.

The instruction set needs to have load, store, arithmetic operations like add, subtract, multiply and divide, logical operations like and, or, exclusive or, and bitwise operations like bit shifting and possibly bit rotation. Furthermore you need a jump (goto) instruction and a set of instructions for conditional branching, and push/pop to work with the stack. Lastly you could add some privileged instructions like loading the flags register or resetting the machine. At the bare minimum, there are about 25 instructions to be implemented. By comparison, the 8086 CPU has about 75 different instructions.

For a memory model, 64K ought to be enough for anybody ... Or you could give the system very little real memory and implement paging and swapping. Implementation wise, the virtual memory management could take place in either the guest or the host ... (when implemented in the host, the guest OS would never know its memory was being swapped in and out!)
A related issue is protected memory: can the current process write to a given address or not? Early micro-computers did not have support for paging, but they did have read-only memory in the form of ROM. You probably want to have memory mapped I/O, an interrupt vector table and some display memory representing the screen.

One of the problems I've always had with this model is that programming for such an emulated system is hell as you would need to write everything in its assembly language. To overcome this problem, you would really need to make a high level compiler generate the code. Nowadays we have gcc and if you're handy it should be possible to have it generate code for platform X.

Now let us take a step back and get back to bytecode interpreters. Java, Perl, PHP, Python, various kinds of BASIC and even some MUD codes all use a stack machine at the heart of their bytecode interpreters. The stack machine is the simplest kind of processor: it has no registers and its instructions only manipulate a stack. The lack of registers make both compilation and execution (or emulation) easy. Interpreted languages benefit from bytecode because interpreting bytecode is faster than having to go through the language parsing procedures all the time.

A bytecode interpreter for a scripting language is quite different from a full blown system emulator. For a bytecode interpreter, you can make up your own opcodes for any common operation you like. There is no need for an opcode to perform only low level operations; they can be high level operations just the same. For example, Python has opcodes for slicing strings. Until Python 3, print was a statement with an opcode equivalent rather than being a function. It's not cheating, it increases performance.

It's good fun designing your own bytecode interpreting virtual machine. There are a lot design of choices to be made beforehand. Do you want to fully emulate a CPU or not? Maybe you want to emulate any other hardware components? Will you write anything like a system BIOS in bytecode? Are you going to develop a self-hosting system? How far are you willing to take it?

Lion: Yet Another Review

Cheerios, finally a new blog post after a long while. Haven't I been programming a lot lately? Well, yes and no. I've been working real hard on synctool, which is a sysadmin tool written in Python for doing software configuration management on clusters of computers. In github the development branch is now something like 180 commits ahead of the stable branch. After which I got the flu and after that I was on a well deserved long vacation. Just when I got back home, Apple released Mac OS X Lion so I had some interesting upgrading to do. In the past, I sometimes blogged about Ubuntu (Linux) upgrades, nowadays “I'm a mac” (sorry — btw, still doing lots of things with Linux at work) so I'll write about my experiences with the Lion.

Surprise surprise
Upgrading to Lion is a breeze. Just buy it from the App Store, download the program and off you go. After an hour or so you are now running Mac OS X Lion. It's as easy as that. But wait, as a sysadmin, there are a few things here that are making me feel uneasy.

I got Lion from the App Store, so I have no CD-ROM to install the system from if my system ever breaks. Apple solved this partially by including a system restore partition on your hard drive. Eww. Uhm. Well ... OK. I guess..?

Apparently there is a way to create a Lion install CD-ROM but Apple does not tell you how. It is (apparently) reserved to “power users” (or should I say “hackers”?). Doing so is not easy especially because the Lion installer magically disappears from your hard drive after the upgrade is done. After downloading the 4 gig or so installer I had to download it again to upgrade my laptop. This is not such a nice thing for Apple to do.

Upgrading my laptop took a bit more work. It's an older model white macbook with only 1 gig of memory. Lion only works on systems with 2 gigs of memory or more, so I had to do a small hardware upgrade first. I can't really explain, but Lion uses a ton of memory even though the running apps do not show big memory footprints in Activity Monitor.

Gimme gimme new features
Lion offers a number of new things. There isn't an awful lot, but then again, it was only 29 dollars or something. Some of those things were good, and some of those were bad. I love my Mac enough to blog about it and I do like Lion but grrrrrowls ... I'll give you the bad first.

Ironically most of Lion's biggest selling points were pretty useless to me. Honestly, it's mostly marketing hype. Here's why: my main system is a 27 inch iMac. Gimmicks like Launchpad and fullscreen Mail are nice on a laptop, but they are not useful (just plain awful) on a 27 inch screen. Lion's features are mostly ideal for laptops but not for desktop Macs.

• new UI. Really? Yeah, but you have to look super hard to notice. And then when you do notice, it annoys the crap out of you because it does not look better than Leopard. Except for the squared buttons, which looks more like Microsoft Windows?
• full screen apps. Great feature, but on large displays it is not useful. You just drown in this amazingly large screen. Which is kind of fun actually, because a regular PC never does that to me.
• 3 column layout for Mail. Oh wow. I hate it. It's a cheap Outlook imitation if you ask me. And it's ugly.
• Launchpad. A big screen full of icons. Great. Sigh. I will never use it.
• new trackpad gestures. Yeah, I do have a trackpad with my iMac. I'm just not comfortable with four and five finger gestures, rotating your hand, etc. For photo editing, I use a mouse (!)
• Mission Control. Where did Expose go??
• Dashboard is awful on a large display. It was nice in Leopard, the screen would fade out to darkness and your widgets would appear. You would click next to a widget in the void and the whole thing would zoom out and you would return to your desktop. In Lion, the whole desktop slides offscreen to the right (a dazzling animation that gives you a headache) and you are presented with a million (really, a million!) tiny knobs that are some kind of Lego base plate, and you can't even change that annoying background without hacking into your system library folder (!!!)
• AirDrop. Maybe Lion's coolest feature, but it doesn't work with my old macbook. I don't even blame Apple for this because it is an older model and the WiFi chip in this macbook does not have the needed functionality, but as said, AirDrop is unfortunately useless to me.
• FileVault now has whole disk encryption. To a lot of people, this feature came like five years too late. On the other hand, this feature is arguably useless to everyone. It enables you to encrypt even your system files, files that are identical on any Lion installation. Moreover, even though Apple denies it, FileVault makes your system noticeably slower.

Apps that broke:

• PowerPC apps simply don't work anymore. Apple removed the brilliant Rosetta software. I say brilliant because it allowed me to play WarCraft 3 (for PowerMac) on my intel Leopard system flawlessly.
• TrueCrypt / MacFUSE. I found a website that offered up-to-date MacFUSE software that fixed the problem. But it was not on the official MacFUSE website. Odd. Very odd. But it really does work now.
• Some folks say that Spaces is broken in Lion because Apple changed it. I don't use Spaces but looking at Mission Control, I believe them.
• Printing from Google Chrome crashes the app. Of course, it's all Google's fault and you should use Safari. But I'm pretty sure that I could print from the Chrome browser before.
  
• Lion removed my compilers and did so even without asking. gcc, clang, make, all gone. Insane! Apple decided that thou shalt use Xcode 4 on a Lion system. It's free, and thou shalt download the 4 gig Xcode 4 installer from the App Store and you are not given any option to install only the command-line tools. So I spent some additional hours to get my programming environment back in order again.

The Good Stuff
So, is Lion all useless? No, here's what I do like about it:

• More system programs are 64-bits binaries.
• The OS kernel runs in 64-bits mode now, which is faster than 32-bits mode on modern CPUs.
  
• ASLR has now been implemented properly or so they say. Address randomization is important for security; it helps prevent system crackers to gain root access by smashing the stack. I find this to be a very important feature because I do online banking with my system, and who doesn't, nowadays.
• The price is fair, even for a guy like me who has been spoiled rotten for years with Linux and GNU where software is typically free (as in beer — yes, RMS says you can make money from it but everyone is getting it for free anyway. But wait, isn't that exactly the same in the Windows world? Hmmm).
• The arrows on the scroll bars are gone. I'm not too crazy about the new scroll bars, but you have to admit that no one was seriously clicking those arrows anymore and removing them is a bold move. No doubt Ubuntu and other Linuxes will follow this example, as will Microsoft.

I Still Love You
Despite my criticism on Lion I have to say that I'm still very much in love with the Mac OS. It just works. I can't put it any other way. I love working with it. I love programming for it. I love its strangely brilliant Objective-C. I love digging in the docs of its Objective-C API. I love its brilliant BSD UNIX that is its core. I love that you can sit down and get some work done rather than having to click away popup after popup as your system is begging for attention because it needs you to be a sysadmin night after night. I love that OS upgrades do not totally break your system and that you do not have to spend a full weekend on hacking away in it in a futile attempt to fix it. I love how you can copy gigabyte files around and the whole desktop remains responsive. I love how my old white macbook runs the latest Mac OS X smoothly and without feeling sluggish at all. I love the finger scroll with inertia on the Magic Mouse that seems to ‘just know’ where you want to scroll to. I love the beautiful screen fonts. They are not ugly like on other platforms. And I love how the Dashboard worked in Leopard. No other OS in the world implemented widgets in this way and it was done exactly right. And I love Spotlight. Spotlight has to be the only desktop search tool that does not grind on your hard drive as it is rebuilding an index every single day from a daily cron job.

I could go on and on. There are few things in Mac OS that I do not like. The Finder does not behave like Windows Explorer — but then again, it is not a Windows application. The default settings for PageUp and PageDown in the Terminal and Xcode editor appear broken as they do not react intuitively. Launchpad is rubbish. They messed with my favorite app, the Dashboard.
Other than that, the Mac is still insanely great.

Update: In System Preferences|Mission Control, uncheck “Show Dashboard as a space” to get the old Dashboard behavior back.

Quaternion versus Matrix performance

When doing 3D graphics programming, you will be dealing with vertices, vectors, translations and rotations. OpenGL will happily do the translations and rotations for you, but in some cases you will want to do the math by yourself anyway. For example, I like keeping the orientation of an object around so I can rotate it whenever I like (like in an animation or game loop or heartbeat routine). At that point, OpenGL is not involved. Later, a drawing routine is invoked that calls OpenGL to do the necessary rendering to display.

OpenGL uses matrices to represent 3D space in memory, so it makes sense to store the orientation of the object in a matrix as well. The 3D space is actually represented in a 4x4 matrix, which is generally written as an array of 16 floats. Now, there are some gotchas like the column major format to layout the matrix in memory and the right-handedness rule, but once you got that right, all the drawing routine really has to do call glMultMatrix() on your 'matrix' array of float values, and the object will (hopefully, if you got everything else right as well) appear under the desired angles. That's easy.
Multiplying matrices together to make combined rotations is not an easy task and takes 4x16 = 64 floating point multiply operations! There are 4x12 = 48 add/subtract operations as well, but I assume that the multiplications have the worst impact on performance. If you want to do a rotate in a glRotate-style you will have to setup the matrix first, which adds another 24 multiply operations in the worst case, without counting the multiplications and the sqrt() call needed to normalize the vector.

There is another way of storing orientation, and it's the quaternion. This is something like a vector in complex 4D space and consists of "something like" a <x,y,z> vector and an additional w component. What, only 4 values? Yup, that's all. The memory footprint of a quaternion is really small compared to that of a matrix. (By the way, this is a non-issue to me because modern computers have plenty of memory — even the mobile devices do. But maybe you have some whack project in which you want keep tons of different orientations and memory becomes a problem). Because there are only 4 values, initializing a quaternion is dirt cheap in terms of CPU usage. Multiplying quaternions is also relatively cheap with only 16 floating point multiply operations. There are 12 add/subtract operations as well, but I assume that the multiplications have the worst impact on performance. Again, not counting the operations needed to normalize the rotation vector.
So, are quaternions the golden egg? Well, yes and no. Yes, they are great, but the main drawback is that OpenGL works with matrices. Converting the quaternion back to a matrix costs 27 multiplies.

In my book (I keep a little black book to pen down these kinds of numbers) 16+27 = 43 is still less than the 88 that matrices cost. However, there is a special case where matrices will still be faster. The trick is that when working with matrices, initially, you will have the identity matrix. Since multiplying the identity matrix with another matrix equals that other matrix (check this yourself, it's fun ...), you can greatly optimize the first matrix rotation, as it requires no multiply at all. This requires that you keep a flag on the matrix saying that it is identity. Or you can make a separate routine that simply initializes the matrix in its first rotated state. It makes for an embarrassingly fast rotate call, especially if you were going to do just one rotation of the object.
Of course, this is cheating. You can cheat in a similar way with quaternions, saving an extracted copy of its corresponding matrix and flagging it as dirty whenever it needs to be updated. Just keep in mind that if you rotate the object all the time, you will have to extract the matrix for use with OpenGL all the time.

I want to end this post with a couple of remarks:

1. Quaternions are apparently terrific for combined rotations. If you hardly do combined rotations, matrices will be faster. If you do combined rotations all the time (like for animating skeletons and such) then you probably already knew that quaternions are the way to go.
   
2. Quaternions produce less floating point drift than matrices, because they do less multiply operations than when multiplying matrices. They do drift however, and don't let anybody tell you that they don't.
   
3. In my post I made a remark about modern computers having enough memory ("640K ought be enough for anybody ..."). The same goes for CPU power, really. However, on mobile devices it probably does pay off to investigate app performance not only because of the less powerful CPU, but also because of battery power consumption.
4. I got to writing this blog entry because I spent a day wondering why my matrix rotation around an arbitrary axis gave weird results. The quaternion code did work, until I passed in a vector that was not normalized and it displayed the exact same weird result! That was an eye-opener. After normalizing said vector, the matrix code gave just as good results.
   
5. Over a year ago, when I wrote in my blog about quaternions for the first time, I made a remark that NeHe's code has a sign wrong somehow. To my surprise, my model was rotating clockwise using my own quaternion code. I fixed it to have it rotate anti-clockwise. Either I got the matrix column major layout wrong before, or my other project was working with different axis. Anyway, NeHe's quaternion code is probably alright after all. I didn't use it. By the way, I saw wikipedia too now shows code examples for quaternions.

Database performance in practice

For a project at work, I wanted to put some syslog messages into a database so you would be able to query the dataset easily and most importantly, quickly. To my surprise, this was not as easy as I thought it would be. Database engines are not the magic tools they promise to be.

The main problem with syslog data is its volume. The relevant logging lines of several machines combined, gathered over three years time was about 50 million records. You would think a database would be able to hold 50 million records ...

MongoDB

MongoDB is a fairly recent new high performance database engine. MongoDB is "web-scale" meaning that you can spread load over multiple servers. I have only one server so web-scale doesn't apply in this case. MongoDB doesn't understand SQL, but instead it uses a Javascript interface. I don't like SQL much so initially I was quite happy with MongoDB. There is some controverse around MongoDB because it defers commits to disk (which means undetected data loss in case of a power outage) in order to gain performance but in this case I could live with it and this wasn't a show stopper.

It comes with nice Python bindings so developing the app was quickly done. MongoDB doesn't require you to define any schemas or anything at all so it's very easy to get something working quickly.

Tests with a months worth of syslog data were satisfactory so I decided to load up all the data, with records dating back as long as three years. This took a while so I let it run overnight.

Queries now took a long time to complete. Unacceptably long. To cut down on query time, I took the extreme measure to make a subset of the data that contained only three months worth of data.

I read that querying on datetime objects was slow, so I broke it down to year/month/day numbers and used that instead. When adding these columns, the database files on disk blew up from 50 gigs to 120 gigs. Disk space was not really an issue on this system, but really, 120 gigabytes?

Memory usage was much worse though, to the point it became unbearable. MongoDB uses the mmap() system call to map on-disk files into memory, with the unfortunate consequence that when you do a costly query, it will consume all system memory. Linux has a-OK memory management so your system won't die on the spot, but it was clearly having a hard time. Since I didn't want to dedicate the full box to MongoDB, this was a no-go and Mongo had to go.

MySQL

MySQL is a famous free relational database and would have been many a person's first choice anyway, so I decided to give it a go. One of the reasons I don't like SQL databases is that you have sit down and take the time to set it up. Create the database, the user(s), set passwords, write the schema etcetera before you can start. What you get in return for this investment is that you can give certain users or apps read-only rights to the database (which is kind of important when dealing with logging data) and you can easily review what attributes and data types you used to create the tables with.

Tests with a months worth of syslog data were satisfactory so I decided to load up all the data, with records dating back as long as a year. This was practically impossible. Inserting rows into MySQL goes alright for a while and then it slows down, and slows down more and more until the point were it takes minutes to insert data into the database! I tried improving this with transactions (do multiple inserts and commit) and it didn't help!

Fifty M records is too much for MySQL. MySQL's on-disk and in-memory footprint were formidable, but who cares when you can't even put some data in your database. You can do tricks with partitioning in MySQL but I didn't try it because it creates new issues to consider. Someone said I should use PostgreSQL, but I was already too tired to try.

'Proprietary' solution

I was convinced that a modern PC should be able to handle 50 million records, so I decided to do it the hardcoded way using a packed struct and dump that into a binary file. Database lovers cringed and called me an idiot but I let them. Using some shortcuts, it was possible to cram a syslog line into just 48 bytes — and this includes two magic bytes to detect possible data corruption. The total amounts to 2.5 gigabytes which takes about half a minute to read through from disk, but the subset is only a few hundred megs and is processed much quicker.

Because the data can be packed so small, it's no problem doing a linear search to find what you are looking for. A linear scan through memory may be an inefficient way of searching but it finishes in a split second so no further optimisations are necessary at this point. Mind you, there is no indexing going on because I'm not trying to imitate a database engine.

What's also cool about this data is that when you are searching by date, you can skip through the data using a binary partitioning method (just like bsearch() does). Moreover, data can be easily partitioned by writing to a new data file every month.

The major drawback of this solution is of course development time. It's written in C for performance reasons and as a consequence the program is not yet fully featured, and it will take considerable effort before it is.

Conclusion

Databases are generic tools that keep you from writing lots of code that have to do with storing and searching through data. In that respect, databases are like what scripting languages are compared to low-level programming languages. You can outperform (or maybe in this case I should say, outmaneuver) them but whether it's a smart thing to go that way depends.

The given problem can probably be solved using MySQL by dynamically creating a new partition each month and adapting the application to work with that. I'm pretty confident that it will work but this too will require some more work to get done.

What bothers me is that database engines are overkill for the small data store problems (where you would typically use some ASCII flat format file to put all records in), while at the same time these heavyweight tools cripple under the load when you put a lot of records into them. All of a sudden you have to be a database expert for solving a seemingly simple problem.

Update (March 14, 2011)
I set up a MySQL db with the archive storage engine and partitioned it by month. It's currently loaded with 150 million records (!) and counting ... It's holding up nicely. We will get some more experience with it in the coming weeks, but so far, I'm quite impressed with it especially because it is running on a rather cheap and simple PC server.