Compressing Voxel Worlds

A friend of mine, Arthur, is developing a voxel-based game and found himself having to deal with large volumes of data. Unlike 2½D games where the map is essentially a 2D expanse with occasional relief, his game allows the definition of things in full (discrete) 3D.

To avoid loading the entire map in memory, he made the wise design decision of making his world tile-based, so that it can, simultaneously, reduce the working set as well as having an essentially open map, by loading only a small set of visible world blocks at all time. So together we took a look at compressing these world blocks, and it turned out that we can do a lot with fairly simple algorithms and VLCs.

Shellsort

The game is different whether we consider external data structures—that live partially or totally on disk or over the network—or internal data structures residing entirely in local memory. For one thing, none of the courses I had on data structures I had really prepared me to deal adequately with (large) external data structures; it was always assumed that the computer’s memory was somehow spacious enough to hold whatever data you needed.

However, when you’re dealing with files, you can’t really assume that you can access random locations to read, write, or exchange data at low cost, and you have to rethink your algorithms (or change plans altogether) to take the cost of slow external media into account. Sometimes an algorithm that doesn’t look all that useful in main memory suddenly makes more sense in external memory because of the way it scans its data. One of these algorithms is the Shellsort.

RetroComputing

There are plenty of web sites and museums dedicated to the computers of yore. While most of them now seems quaint, and delightfully obsolete, there are probably a lot of lessons we could re-learn and apply today, with our modern computers.

If you followed my blog for some time, you know that I am concerned with efficient computation and representation of just about everything, applied to workstation, servers, and embedded systems. I do think that retro-computing (computing using old computers or the techniques of old computer) has a lot to teach us, and not only from an historical perspective.

/* no comments (part I) */

Comments have always bothered me. Not that I do not find them useful. It’s that we never know really how to use them properly. They’re also quite hard to maintain so that they follow the current state of the code. Comments tend to be written by the original programmer then never really updated to follow the latest modifications.

In addition to be concise, informative, to-the-point, comments should be written in the most precise language possible, one where words are chosen so that there are no unwanted overtones, no innuendos, and no obscene language. English is the new lingua franca, and this means that comments, in order to achieve collaboration with as many different people as possible, must be written in English. That might be a problem when you’re dealing with non-native speakers.

The CFM-01

In a previous post, I presented the CFM-00, a “cluster” of 8 Pentium III at 500MHz, assembled into one MDF casing. The assembly was rather clean-cut given the rather rudimentary materials (MDF and threaded rods) but the resulting computing power is dismal (but that’s no surprise). We have about 2GHz of computing power, and at 128MB of ram per node, it makes running even just a remote shell not that responsive.

A few months ago, my friend Christopher came to me with a data center clearing deal with Pentium III 1GHz 1U rack-mount (with 512MB of RAM) servers for $15, and I got eight of them to build the CFM-01, the successor to the CFM-00. But I did not strip the motherboards from their casing this time, I built an inexpensive rack out of slotted angle steel.

The Perfect Instruction Set

The x86 architecture is ageing, but rather than looking for re-invention, it only saw incremental extensions (especially for operating system instructions and SIMD) over the last decade or so. Before getting to the i7 core, we saw a long series of evolutions—not revolutions. It all started with the 8086 (and its somewhat weaker sibling, the 8088), which was first conceived as an evolutionary extension to the 8085, which was itself binary compatible with the 8080. The Intel 8080’s lineage brings us to the 8008, a 8 bits of data, 14 bits of address micro-processor. Fortunately, the 8008 isn’t a double 4004. The successors of the 8086 include (but the list surely isn’t exhaustive) the 80186, the 80286, the 80386, first in the series to include decent memory protection for multitasking, then the long series of 486, various models of Pentium, Core 2 and i7.

So, just like you can trace the human lineage to apes, then to monkeys, and eventually to rodent-like mammals, the x86 has a long history and is still far from being perfect, and its basic weakness, in my opinion, is that it still use the 1974 8080 accumulator-based instruction set architecture. And despite a number of very smart architectural improvements (out of order execution, branch prediction, SIMD), it still suffers from the same problems the 8085 did: the instruction set is not orthogonal, it contains many obsolete complex instructions that aren’t used all that much anymore (such as the BCD helpers), and that everything has to be backwards compatible, meaning that every new generation still is more of the same, only (mostly) faster.

But what would be the perfect instruction set? In [1], the typical instruction set is composed of seven facets (to which I add an eighth):

Suggested Reading: Find the Bug: A Book of Incorrect Programs

Adam Barr — Find the Bug: A Book of Incorrect Programs — Addison-Wesley, 2010, 306p. ISBN 0-321-22391-8

(Buy at Amazon.com)

This short book (306 p, but a quick read) asks us to debug 50 short programs written in 5 different languages: C, Python, Java, Perl, and x86 assembly. The book offers quite verisimilar code snippets, each of which containing exactly one bug; forfeiting the results. Barr proposes a taxonomy of bugs, from the logical bug to the off by one, and we must debug the programs with him.

C++ Logging

It seems that logging is something we do in about every program we write. Logging complements the standard output with richer messages and detailed information. And each time it seems like we’re asking ourselves how to do that exactly.

Of course, there are already existing logging frameworks out there, but I was wondering how much work it implied. I wanted something that would integrate seamlessly to the existing C++ streams: it had to behave exactly as a classical ostream from the programmer’s point of view, but had to insert timestamps and manage message priorities. The simplest way to do so is probably to have a class that inherits from ostream or similar and that already overloads all the operator<<s.

Suggested Reading: Optimizing Compilers for Modern Architectures

Randy Allen, Ken Kennedy — Optimizing Compilers for Modern Architectures — Morgan Kaufmann, 2002, 790 pp. ISBN 1-55860-286-0

(Buy at Amazon.com)

The book presents all the high-performance and vectorizing optimizations a compiler should be able to perform on source code while using trade-offs from the underlying architecture (with considerations such as the memory hierarchy and the instruction set) and the semantics of the language.

Extending C++’s using statement

If you’re using C++ as your principal programming language as I do, you certainly know some or most of its capabilities, some of its limitations, and you’re surprised once in a while by a new construct or feature you never thought of even trying in C++.

Having inherited most of its basic behavior from C, C++ still has many quirks and omissions that keeps C++ from becoming a true next-generation language. I’m thinking, as a best example of this, the absence of true arrays. Arrays are pointers to stuff, sometimes you can get the size of the array, most of the times you’re stuck with the size of the pointer, which is of no use and forces the user to manipulate explicitly array meta-data (curiously enough, it wouldn’t ask for much to be able to know the size of an array all the time because new[] and delete[] do hide meta-data to do exactly that).