Benchmarking C compilers for Commodore Amiga

There are a lot of great programming tools for classic Amiga computers, some of them absolutely unique for this platform, like AMOS or Amiga E. AMOS is a very powerful Basic dialect with a wide set of graphics and sound commands that allow you to create entertainment software, especially games, in no time. Amiga E is an advanced, multi-paradigm programming language, featuring flexible types, powerful module system and very short compilation times.

There is also AREXX, which is Amiga port of REXX programming language popular on IBM mainframes. Every decent Amiga software offers so called "AREXX port", which is a set of commands that can be called from an AREXX script. This is a very powerful tool, which allows you to write a script that, for example, calls a graphics software to make thumbnails for a set of images, than an archiver to put them into a compressed file, and than another program to upload that file to an ftp server. Modern software very rarely allows you to control it with external scripts, and even if it does, you must use some clunky tools like AutoIt, which simulate keystrokes and mouse clicks. Sometimes a program can be called from command line, but than you must learn how to parse its output if you want to know more than just whether the operation failed or not. In AmigaOS, thanks to AREXX, automation is a heck of a lot easier, because there is a single communication standard with clearly defined interfaces for every software written for this platform.

Of course there are also traditional programming languages avaiable, like ubiquitous ANSI C. Doing some research on Amiga programming tools I managed to make a couple of them work. Three of them run natively on classic Amiga: Aztec C 5.0a, Dice C 3.16, and SAS C 6.58. Another two are cross compilers, which run under Linux on PC, but produce native Amiga executables: vbcc 0.9b and m68k-amigaos-gcc, which is a port of gcc 2.95 generating code for Motorola MC68xxx CPU family. There is also a vbcc build for Windows available on Github.
I decided to make a simple benchmark to compare the compilation times, executable sizes and their execution times. Of course you cannot make definite judgement just by one benchmark, but I needed at least a basic reference to start with. At one time a popular benchmark was a sieve of Eratosthenes, so I decided to implement one. I also used AmigaOS timer device to measure execution time of the generated executables. If you are interested in the source code you can get it from here.

Except from cross compiling, I made all tests on Amiga 600 with 2MB Chip RAM, 1MB FastRAM and Workbench 2.0. As a rule of thumb, you should always make tests on real hardware - emulators are not 100% cycle perfect, and they always run on top of a multitasking operating system, which introduces additional interference. I also ran each test 10 times, rejected the highest and the lowest result, and took an average from the remaining ones. I didn't measure compilation time for cross compilers, as they run on PC, and not on Amiga.
All in all, the results are as follows:

Compiler	Compilation time	Executable size	Execution time
Aztec C 5.0a	37 seconds	12032 bytes	3114 miliseconds
gcc 2.95	-	12072 bytes	809 miliseconds
Dice C 3.16	31 seconds	7092 bytes	1332 miliseconds
SAS C 6.58	55 seconds	14612 bytes	1597 miliseconds
vbcc 0.9b	-	12764 bytes	1306 miliseconds

As you can see, for this particular test, Dice C is a clear winner among the native compilers: not only was it the quickest, but also produced the smallest and the fastest executable code. Execution time of the code compiled by Dice C was almost on par with the code produced by vbcc, which ran on incomparably more powerful machine and could perform a lot more optimisations. Not surprisingly, the fastest executable was produced by gcc.

Don't throw your old computer away!

I have had quite a break in posting to my blog, mostly because I spent last year collecting and playing around with vintage computers. As a kid I only had C64 and Amiga 1200 before I got a PC, so I decided to make up for it and buy a couple of machines popular in my country those days. It turned out to be so much fun that I got completely lost in it. I was absolutley amazed how much retrocomputing is alive and how many people are actually actively involved in it.

Let's start with Atari. 8-bit Atari machines were one of the most powerful home computers of the late seventies and early eighties. They featured an incredibely powerful graphics chip, Antic, which allowed fully programmable graphics modes. You could even use more than one screen resolution at a time, a trick that was later only possible on Amiga thanks to the Copper chip. No wonder if you take into account that both Atari and Amiga graphics chipsets were designed by the same man, Jay Miner.
There is a lot of great software written for the 8-bit Atari computers, and new one is still being developed. My favourite game for 8-bit Atari is Yoomp!, created in 2007 by a demoscene group taQuart, and there are also many great tools, like SpartaDOS X, which gives you the power comparable to CP/M or MS-DOS. Once I put SpartaDOS X on a programmable cartridge I never looked back at any other Atari DOS again. SpartaDOS X also works great with new Atari storage devices, like SIO2SD or Side, which use modern flash memory and not only can seamlessly replace your regular Atari disk drive (Side can also work as a hard drive), but also allow you to exchange data with a regular PC easily. Speaking of hardware - today, apart from buying a flash based disk drive for your Atari, you can also upgrade memory (up to 1MB, bank switched), install a graphic card (VideoBoard XE) or even a CPU accelerator (based on 16-bit MOS 65c816, compatible with 8-bit MOS 6502 originally mounted in Atari 400/800/XL/XE).

16-bit Atari computers can also be upgraded. Two most popular upgrades are Satandisk and Ultrasatan, which are flash based hard drives compatible with Atari ST/STE and Falcon. You can also replace original disk drive with HxC and use floppy images saved on regular pendrive as floppy disks. This is a very comfortable solution, because quality floppies are becoming more and more difficult to buy (those produced today are much less reliable than original ones). If you have enough RAM in your Atari, you can even connect to the Internet thanks to NetUSBee device. Additional RAM is required not by the device itself, but by the software. I have Atari STFM with 4MB RAM and I can comfortably use some simple software for FTP or IRC, I even managed to open a few simple web pages with Crystal Web Browser. Unfortunately in most cases I ended up seeing garbage (I use freeware CAB v1.5, which comes form 1996 and does not support any modern web standard) or running out of memory. Still, connecting to the global network from a 16-bit computer, designed before the beginning of the Internet revolution, is an unforgettable experience.

Atari had many comptetiors at the time. One of them was Commodore, run by Jack Tramiel, who later left the company and bought Atari. Commodore machines were very famous in 1980s and 1990s due to two very popular lines of computers: VIC-20/C64 and Amiga. VIC-20 was the first home computer to sell one million units, and C64 is listed in the Guiness World Records as the best selling single computer model in history, with estimated number of around 12.5 million units sold. Unfortunately, I don't have any VIC-20 in my collection, but I have a C64 and I use two hardware extensions with it: Epyx Fastload Reloaded cartridge and SD2IEC flash based disk drive emulator. Epyx has built-in software to accelerate disk operations (up to five times), but if you don't want to buy a cartridge you can use SJLOAD, which is a software only fastloader. From my experience SJLOAD works as well as Epyx, but I just find the cartridge more comfortable to use (plus it has some additional software, like memory monitor, extended DOS commands, etc). As for SD2IEC - it's quite cheap and works with most software, but unfortunately cannot serve as a full replacement for the original disk drive. A real 1541 has it's own MOS 6502 CPU and RAM, which is extensivelly used by some utilities, like fastloaders, and although SD2IEC can emulate some of them, it does not contain a full MOS 6502 emulation and therefore some programs, like GEOS, will not work with SD2IEC. So if you are not tight on budget, I'd recommend buying a device like Ultimate or UK1541, both of which offer full 1541 hardware emulation.

If you are lucky Amiga owner, you can also enjoy a few interesting hardware extensions. You can replace your floppy disk with HxC, or Gotek, which is much cheaper option than HxC. I have Gotek drive emulator working in my Amiga 600 and so far experienced absolutely no problems with it, so in my opinion it's worth buying. If you have Amiga with IDE controller on board (like A600 or A1200), you can buy a very cheap CF to IDE adapter, which allows you to use Compact Flash cards as hard drives, because they have built-in controllers which work with IDE protocol. Amiga also features probably the most powerful (and most expensive) CPU accelerators in the market. Some of them, like FPGA based Vampire 600, can speed up your machine up to one hundred times! If you have Amiga 1200 you can extend it with PowerPC CPU card, 256 MB RAM, dedicated graphics card, install the latest version of Amiga OS (an operating system designed for Amiga computers, still actively developed) and work on it almost like on any other modern computer. It's because Amiga hardware architecture, combined with dedicated software, makes it much less resource hungry than an Intel based PC.

There is also one more computer brand that holds a special place in my heart: Sinclair. Sir Clive Sinclair is often compared to Steve Jobs, not only because of his temper, but also because he was one of the greatest visioners of his era. He was the first one to introduce pocket calculators in 1972 and pocket TV in 1978, he also introduced the first affordable (priced less than 100 GBP, a few times less than the competition) home computer to the British market: ZX80. It featured a 3.5MHz CPU, only 1kB RAM, no high resoultion graphics (only text mode), no sound chip and no disk drive - you could only use a tape recorder as a storage device. It was very little even those days, but ZX80 was extremely cheap and became a huge success. Sir Clive Sinclair supposedly said that at that price, everyone would want a computer, even if they had absolutely no idea what to do with it. Apart from that, Sinclair devices were always designed to look slick and elegant. Even today, white ZX80 looks beautiful, and so do all later black models. ZX80 featured a built-in Basic interpreter and, despite it's horrible keyboard, allowed users to write their own programs, and many future programmers began their careers from it.
ZX80's successor, ZX81, featured a black case and the same hardware capabilities, but due to more compact chip design it was even cheaper. It also fixed a lot of ZX80 problems (especially screen flickering) and became the first European computer to sell over one million units. ZX81 became successful in United States, where it was sold by Timex as TS1000. In fact, a company called Zebra Systems sells ZX81 kits until today. An essential hardware extension for every ZX81 is a memory pack, which adds more RAM to the system. It's true that 1kB may be enough even to play chess, but most software for "Zeddy" requires at least 16kB RAM. You can also use your PC as a tape recorder and make tapeutils load software into ZX81 - just remember to use mono audio lead (regular stereo leads will not work) and set the PC audio output volume to maximum (ZX81 requires a strong input signal). If it's not enough for you, there is a ZXpand interface, which adds 32kB RAM, allows instant software loading from a flash card, and features an AY sound interface.

But the most successful Sinclair computers were ZX Spectrum 48k and it's descendants. It was also the most often cloned computer, especially in communist countries, which were cut off from the world computer markets due to Cocom regulations. As a consequence, most of Sinclair fans beyond Britain are located in Eastern Europe. Russian ZX Spectrum scene is especially strong, and they even developed their own, extended models, most famous of them being Pentagon and Scorpion.
The most problematic hardware part of ZX Spectrum was its keyboard, but you can easily buy a new membrane and replace it yourself, following one of many online tutorials - it requires only a screwdriver, and a bit of patience.
If you have a fully functioning Spectrum you can, just as with ZX81, use a PC as a tape recorder. There are two programs that I would recommend using: OTLA and PlayTZX. The first one recognizes a lot of different tape formats (TAP, TZX) and can work in "turbo mode", which due to a smart audio signal modulation allows loading programs a few times faster. Unfotrunately, some games, especially copy protected, don't load with OTLA. In this case, you can try PlayTZX, or its Windows counterpart, winTZX. PlayTZX is a console only tool, which can work only with files encoded in TZX format (it's less popular format than TAP), while winTZX can work with both TAP and TZX files. On the other hand, TAP and TZX formats are very similar, and there are many tools to convert between those two formats to be found online. To avoid load errors remember to use a mono audio lead and very loud audio output (just as with ZX81). It is also important to use verified TAP and TZX files: I found that many of them available online are somehow broken, and although they work with emulators, they fail to load into real hardware. So far the most reliable source of Sinclair software I know is World Of Spectrum - I never found a single file which would refuse to load with a real computer.
And, of course, just as for all aforementioned computers, there is also a flash based storage device for ZX Spectrum: Divide. Just as ZXpand, it connects directly to the system bus through the expansion port, which allows you not only to use TAP and TZX files, but also emulator snapshots (SNA). It means that you can, for example, freeze a game state in a software Spectrum emulator on PC and load it directly into Speccy.

There are of course dozens of computers from the "good old times" that you can have fun with: Apple, Acorn, Amstrad, even an old PC. If you have such computer - don't throw it away! Instead, try to put a new life in it and give it to someone who can still find it enjoyable - like your kid or a geek friend. If not, just sell it online - there are many people out there who will be happy to have it.

Pushing the limits

Today I'm not going to write about ultra fast Hadoop clusters or insanely scalable, globally-distributed databases. This time I want to take you on the journey in the totally opposite direction, straight into the rabbit hole.

Let's say you want to display a nice looking rainbow on the screen of you TV, like this one:

Because a static picture is a little boring, you also want to animate it, so that the rainbow moves up (or down) the screen. The question is: what hardware do you need for this and what will be the software requirements?

What if I tell you that all you need is a computer with 1.8 MHz CPU, 48 kilobytes of RAM and the program that takes 29 (twenty nine) bytes? Yes, bytes. Less than the number of letters in this sentence. If you don't believe me, you can download a zip archive containing the software from this location. Inside you will find a file rainbow.xex which you can run on any Atari 800/800XL emulator, or even on the real hardware if you still have one (you can use a device like SIO2SD to transfer files to the Atari). I have run it on a real Atari 800XL connected to a plasma TV through a composite video lead, and it works perfectly.

How is that possible? The secret lies in talking directly to hardware. 8-bit computers have very limited resources, so any software layer which is not absolutely necessary is just a waste of memory and CPU cycles. A simple example is a boolean value, which can have one of two states: true or false. Any computer in the world, no matter how simple or complicated, needs only one bit to understand boolean values: 1 for true and 0 for false. Since a byte consists of 8 bits, you can store 8 different boolean values in one byte. Yet, in today's software world, the Java boolean primitive takes entire byte, and the simplest Boolean class:

public final class Boolean
{
    public static final Boolean TRUE = new Boolean(true);
    public static final Boolean FALSE = new Boolean(false);
    private final boolean value;

    public Boolean(boolean value) {
        this.value = value;
    }

    public boolean booleanValue() {
        return value;
    }
}

compiles in Java 7 to 451 bytes of bytecode, not to mention it requires a few hundred megabytes runtime environment to load. This is the cost of having programmer friendly, enterprise grade, programming tools and languages.

Going back to the example, the algorithm to make Atari display the rainbow is quite simple:

1. Initialize graphic mode.
2. Read current scanline from Atari display chip - Antic. Antic creates image on a TV screen drawing it line by line, from left to right, 50 times (PAL) or 60 times (NTSC) per second. The horizontal resolution of an Atari screen is 240 pixels (including borders), which means that the scanline number can have values from 0 (first line) to 239 (last line).
3. If the line number is 0, increase the counter, which is used to calculate the colour palette shift. Increasing the counter on every new frame adds the animation effect to the rainbow picture.
3. Wait for Antic to finish drawing the current line on the screen (we don't want to change color in the middle of the line).
4. Change background colour to the value obtained from Antic (Atari has a total palette of 256 colors) summed up with the current shift value.
5. Repeat from point 2.

This algorithm can be easily translated into a C program:

#include <atari.h>

#define SDMCTL (*((unsigned char*)0x22F))

int main() {
  unsigned char line, counter = 0;

  SDMCTL = 0; // disable display in BASIC screen area
  while (1) {
    line = ANTIC.vcount;  // read current screen line
    if (!line) counter++; // increase color shift on new frame
    ANTIC.wsync = line;   // block CPU until vertical sync
    GTIA_WRITE.colbk = line + counter; //change background color
  }
  return 0;
}

To compile this program on a PC, you can use a cross-platform cc65 compiler:

cl65 -t atari -o rainbow.xex rainbow.c

However, the resulting executable is 1104 bytes long. Let's make the compiler to output the assembly code to see the CPU instruction list it produced:

cc65 -t atari rainbow.c

The assembly source code in the resulting rainbow.s file looks like this:

    jsr     decsp1
    lda     #$00
    jsr     pusha
    ldx     #$00
    lda     #$00
    sta     $022F
L0008:  ldx     #$00
    lda     $D40B
    ldy     #$01
    sta     (sp),y
    ldy     #$01
    ldx     #$00
    lda     (sp),y
    jsr     bnega
    jeq     L000E
    ldy     #$00
    ldx     #$00
    lda     (sp),y
    pha
    clc
    adc     #$01
    ldy     #$00
    sta     (sp),y
    pla
L000E:  ldy     #$01
    ldx     #$00
    lda     (sp),y
    sta     $D40A
    ldy     #$01
    ldx     #$00
    lda     (sp),y
    jsr     pushax
    ldy     #$02
    ldx     #$00
    lda     (sp),y
    jsr     tosaddax
    sta     $D01A
    jmp     L0008
    ldx     #$00
    lda     #$00
    jmp     L0002
L0002:  jsr     incsp2
    rts

Quite long, isn't it? If you understand the assembly language, you will probably notice a few problems here. First, the program jumps a few times to some strange subroutines (like pusha, bnega, tosaddax, etc.), which does not seem necessary. Second, it uses a lot of reads and writes to the stack (although the algorithm uses only two local variables (line and counter). Third, some instructions are completely unnecessary (like LDX, which loads data to never used CPU index register X).

Fortunately, the cc65 compiler provides some optimizations: you can use "‑Oi" and "‑Os" command line switches to inline all subroutines and get rid of jsr instructions, you can also make local variables to be stored under fixed memory address instead of the stack through "‑Cl". Also, using "‑Or" switch enables register variables, which is particularly interesting, because it does not make CPU use physical registers (since MOS 6502 processor used in the 8-bit Atari has only one general purpose register, called accumulator), but it makes variables to be stored in first 256 bytes of physical memory, called zero page. The advantage of using zero page is using less CPU cycles to access it: 8-bit memory addresses (from 0 to 255) are decoded faster by 8-bit processing unit than 16-bit addresses (from 0 to 65535 - the memory limit in Atari 800XL is 64KB).

Let's see what happens if we turn the optimizations on:

cc65 -Cl -Osir -t atari rainbow.c

The resulting assembly code is now much smaller:

    lda     #$00
    sta     L0004
    sta     $022F
L000A:  lda     $D40B
    sta     L0003
    lda     L0003
    bne     L0010
    lda     L0004
    clc
    adc     #$01
    sta     L0004
L0010:  lda     L0003
    sta     $D40A
    lda     L0003
    clc
    adc     L0004
    sta     $D01A
    jmp     L000A

To produce a working executable, we have to assemble and link it:

ca65 rainbow.s && cl65 -t atari -o rainbow.xex rainbow.o

Still, the resulting code is 630 bytes long. This is because the compiler still includes some Atari specific code from the standard library. We can work around this using an assembler (like xasm or MADS). But first, we need to clean up the assembly code a bit:

    org $2000  ; start address

    lda #$00  ; load accumulator with 0
    sta $cb   ; store it in memory
    sta $022f ; disable display in BASIC screen area
loop
    lda $d40b ; read current screen line into accumulator
    sta $cc   ; store it in zero page
    lda $cc   ; load current line number from memory
    bne skip  ; if it's not zero jump to code at 'skip' label
    lda $cb   ; load counter from memory into accumulator
    clc       ; clear carry flag
    adc #$01  ; add 1 to accumulator
    sta $cb   ; store counter in memory
skip
    lda $cc   ; load current line number from memory
    sta $d40a ; block CPU until vertical sync
    lda $cc   ; load current line number from memory
    clc       ; clear carry flag
    adc $cb   ; add counter to the line number
    sta $d01a ; change background colour
    jmp loop  ; repeat

I added some comments to make clear what's going on in the code. So, let's assemble it:

xasm rainbow.s /o:rainbow.xex

Now rainbow.xex is only 45 bytes long! Two first bytes are the executable file header ($FFFF) and the next two are memory address the program should be loaded into ($2000). The rest is pure CPU instruction list.

But we can still make it smaller, using some knowledge the compiler does not have. First, we don't need to init the counter stored at $cb memory address, because we don't care about it's initial value (it gets increased infinitely anyway), so we can get rid of "sta $cb" instruction. Second, we don't need "lda $cc" right after "sta $cc" and "sta $d40a", because the "sta" instruction doesn't change the accumulator state, so there's no need to reload it. We can also replace the whole procedure of loading counter from memory into accumulator, adding 1 and storing it back in memory, with only one instruction - "inc $cb" - which increases the memory value by 1. Finally, we don't need "clc" to clear the carry flag (the flag indicating that a mathematical operation resulted in value which does not fit in 8 bits) before adding line number and counter, because Atari colour palette can have only 256 values, so it doesn't matter if the addition result fits in 8 bits or not.

After making the changes, the code now looks as follows:

    org $2000 ; start address

    lda #$00  ; load accumulator with 0
    sta $022f ; disable display in BASIC screen area
loop
    lda $d40b ; read current screen line into accumulator
    sta $cc   ; store it in zero page
    bne skip  ; if it's not zero jump to code at 'skip' label
    inc $cb   ; increase counter in memory by 1
skip
    lda $cc   ; load current line number from memory
    sta $d40a ; block CPU until vertical sync
    adc $cb   ; add counter to the line number
    sta $d01a ; change background colour
    jmp loop  ; repeat

After assembling it with xasm, the resulting executable is now only 33 bytes long. However, we can still cut the instruction list down. You may notice that there is no need to load and store accumulator at $cc memory address, because its state doesn't change between "sta $cc" and "lda $cc" - so we can safely remove those instructions:

    org $2000 ; start address

    lda #$00  ; load accumulator with 0
    sta $022f ; disable display in BASIC screen area
loop
    lda $d40b ; read current screen line into accumulator
    bne skip  ; if it's not zero jump to code at 'skip' label
    inc $cc   ; increase counter in memory by 1
skip
    sta $d40a ; block CPU until vertical sync
    adc $cc   ; add counter to the line number
    sta $d01a ; change background colour
    jmp loop  ; repeat

As we got rid of another couple of bytes, rainbow.xex is now exactly 29 bytes after assembling.

Lessons learned:
1. Compilation with default compiler options sucks.
2. A smart compiler can do a really great job optimizing code.
3. There is always a way for a programmer to optimize it even more.
4. Programming old computers is fun.

How to deal with blocking operations

In distributed environment even simple things become complicated. One of the most trivial examples is a counter. If you have only one instance of an application running, then you can simply store the counter in a database table with the counter's id and value, for example:

| ID | VAL |
------------
| 0  |  1  |

and increase its value with a simple query:

UPDATE counters SET val=val+1 WHERE id=0

However, when there are many clients trying to increase the counter simultaneously (for example multiple frontends displaying the number of visitors to the website), you may experience some serious slowdowns. It's because updating a row in a database is a blocking operation, which means that during update the row is locked to prevent the situation when multiple process try to modify it at the same time. There are two basic types of locks: write locks and read locks. A write lock is a basic and most often used type of lock, which does not allow modifying a value while another change is in progress. You can still read the row value, but in this case two subsequent reads can return two different values, because the change could have taken place just between them. When this becomes an issue, you can use a read lock, which prevents other processes from reading the row until the change is done. Depending on how your database is configured, locking the counter row will become more or less painful, but it still needs to be done sequentially to ensure its value is correct. This way, simple operation of increasing the visitors counter can become a serious bottleneck to the whole website.

I have prepared an example application which simulates such case. You can download a zipped archive from here. It was prepared in Linux, but in case you work in Windows you should also be able to compile it with Cygwin - just make sure to install mysql development libraries (you need mysql_config.exe binary in your PATH).
First, prepare the database and set up the tables. All example assume that you have a MySQL database running on localhost, with test database called "test" and password "root" for the root user. If your environment differs, modifiy respective variables:

mysql -u root -proot test < counter.sql

Now, compile the example code which works on the counter:

make sync

This example simulates ten simultaneous blocking counter updates. Each transaction starts one second after the previous one, but it takes two seconds to complete, so the transactions overlap and block one another.
When you run the resulting binary you should see the output similar to the following:

Begin #1
Update #1
Begin #2
Update #2
Begin #3
Update #3
Commit #1
Begin #4
Update #4
Begin #5
Update #5
Commit #2
Begin #6
Update #6
Begin #7
Update #7
Commit #3
Begin #8
Update #8
Begin #9
Update #9
Commit #4
Begin #10
Update #10
Commit #5
Commit #6
Commit #7
Commit #8
Commit #9
Commit #10
Counter value: 10, time elapsed: 20.015499s

You can notice that commits do not take place immediately after updates. This is because each transaction must wait for all previous ones to complete. As a result the test takes around 20 seconds, which is the sum of time needed to finish all transactions. In this scenario, the more clients try to modifiy the counter, the longer it takes to complete. Finally, the system becomes overloaded, some of the operations time out, client processes fail to set the correct counter value, and the user experience is a disaster.

There are couple of ways to solve the problem. Some of them involve spending time and money to build a NoSQL cluster based on some fashionable technology, like Hadoop or Cassandra. A cheaper and smarter way involves implementing so called "optimistic locking". The main idea behind this technique is to decrease to the minimum the time you spend in lock. Operation based on optimistic locking takes three phases:

• read the value
• modify the value
• compare and swap

The last operation is the only one that needs to be atomic. In short, it reads the value you want to modify and if didn't change from the first read, it replaces the old value with the new one. If comparison fails, it means that another process has already modified the value, and we need to roll back.
Optimistic locking is a good solution, but it still can lead to failures while updating counter value, and it also requires clients to implement some strategy on how to deal with update failure: "Should I repeat the operation?", "At what intervals?", "How many times before giving up?", etc.

Another way is to get rid of blocking opeartions at all, and replace them with non-blocking ones. It can be done easily by introducing queues. Putting a new value into a queue does not affect any existing values, so it doesn't need any read or write locks. With every new request you just insert a new row into the queue table, and there is a single, separate process which updates the counter and removes the rows it has read form the queue. Because there are no concurrent processes working on the counter, there is no problem of blocking. Also, the worker can read new inserts in batches instead of single records, which can give a huge performance boost with fast growing queue (if there are a hundred new tasks waiting in the queue, you can increase the counter by a hundred in one step). The queue is safe, because each insert has its own unique id, so deleting records from the queue does not interfere with inserting new ones. Also, when updating fails, the inserts are not lost, but they remain in the queue for later processing. The only drawback is that when you read the counter value it is still a little bit behind, but for purposes such as the number of visitors to the website, it can be easily accepted.

Going back to the example. Compile the code with:

make async

This will rebuild the code to use queue instead on changin the counter directly. When you now run it, you should see the output similar to the following:

Begin #1
Insert #1
Begin #2
Insert #2
Commit #1
Begin #3
Insert #3
Commit #2
Begin #4
Insert #4
Begin #5
Insert #5
Commit #3
Begin #6
Insert #6
Commit #4
Commit #5
Begin #7
Insert #7
Commit #6
Begin #8
Insert #8
Commit #7
Begin #9
Insert #9
Commit #8
Begin #10
Insert #10
Commit #9
Commit #10
Counter value: 20, time elapsed: 11.023697s

As you can see, the whole operation now took much faster to complete, because the new transactions didn't have to wait for the previous ones to finish.

Hacking Linux executables with LD_PRELOAD code injection

Executable code can be stored on disk in many different formats. In MS-DOS, programs which didn't use more than one 64kB memory segment, could be simply saved in a COM file, which contained only machine code, with no additional metadata. When instructed to run such file, operating system loaded it into a first free memory segment at address 0x100, initialized code segment register (CS), data segment registers (DS, ES) and stack segment register (SS) to point to that segment and then passed control to the first instruction located at the beginning of the file. More complicated executables contained an EXE header with some additional informaton required by the operating system, like the number of memory blocks the program needs or initial values of the segment registers.

Nowadays, applications compiled for multitasking operating systems often use dynamically shared libraries, so the executable file headers also contain information about required libraries and functions included from those libraries. In Linux, you can get that data with readelf. For example, using command:

readelf -s /usr/bin/users

gives the following information (I stripped some of the output to increase readability):

Symbol table '.dynsym' contains 58 entries:
  Num: Type Bind   Vis     Name
    1: FUNC GLOBAL DEFAULT utmpxname@GLIBC_2.2.5 (2)
    2: FUNC GLOBAL DEFAULT free@GLIBC_2.2.5 (2)
    3: FUNC GLOBAL DEFAULT abort@GLIBC_2.2.5 (2)
    4: FUNC GLOBAL DEFAULT __errno_location@GLIBC_2.2.5 (2)
    5: FUNC GLOBAL DEFAULT strncpy@GLIBC_2.2.5 (2)
    6: FUNC GLOBAL DEFAULT strncmp@GLIBC_2.2.5 (2)
    7: FUNC GLOBAL DEFAULT _exit@GLIBC_2.2.5 (2)
    8: FUNC GLOBAL DEFAULT __fpending@GLIBC_2.2.5 (2)
    9: FUNC GLOBAL DEFAULT qsort@GLIBC_2.2.5 (2)
   10: FUNC GLOBAL DEFAULT textdomain@GLIBC_2.2.5 (2)
   11: FUNC GLOBAL DEFAULT endutxent@GLIBC_2.2.5 (2)
   12: FUNC GLOBAL DEFAULT fclose@GLIBC_2.2.5 (2)
   13: FUNC GLOBAL DEFAULT bindtextdomain@GLIBC_2.2.5 (2)
   14: FUNC GLOBAL DEFAULT dcgettext@GLIBC_2.2.5 (2)
   15: FUNC GLOBAL DEFAULT __ctype_get_mb_cur_max@GLIBC_2.2.5 (2)
   16: FUNC GLOBAL DEFAULT strlen@GLIBC_2.2.5 (2)
   17: FUNC GLOBAL DEFAULT __stack_chk_fail@GLIBC_2.4 (3)
   18: FUNC GLOBAL DEFAULT getopt_long@GLIBC_2.2.5 (2)
   19: FUNC GLOBAL DEFAULT mbrtowc@GLIBC_2.2.5 (2)
   20: FUNC GLOBAL DEFAULT __overflow@GLIBC_2.2.5 (2)
   21: FUNC GLOBAL DEFAULT strrchr@GLIBC_2.2.5 (2)
   22: FUNC GLOBAL DEFAULT lseek@GLIBC_2.2.5 (2)
   23: FUNC GLOBAL DEFAULT memset@GLIBC_2.2.5 (2)
   24: FUNC GLOBAL DEFAULT __libc_start_main@GLIBC_2.2.5 (2)
   25: FUNC GLOBAL DEFAULT memcmp@GLIBC_2.2.5 (2)
   26: FUNC GLOBAL DEFAULT fputs_unlocked@GLIBC_2.2.5 (2)
   27: FUNC GLOBAL DEFAULT calloc@GLIBC_2.2.5 (2)
   28: FUNC GLOBAL DEFAULT strcmp@GLIBC_2.2.5 (2)

As you can see in the last line, users executable calls a strcmp function from the standard Linux GNU C Library library. This function compares two strings given as its arguments and returns 0 if the strings are equal, positive value if the first string is greater than the second one, and negative value otherwise.

You can take advantage of the fact that the program uses a function from an external library to modify its behaviour without touching its code. All you have to do is to substitute strcmp with your own function. You can do it by writing your own dynamic library with custom strcmp and load it before the code of the users executable is initialized.

First, let's create a very simple library mylib.c with this code:

int strcmp(const char* s1, const char* s2) {
  for (; *s1 == *s2; s1++, s2++) {
    if (*s1 == '\0') {
      return 0;
    }
  }
  return ((*(unsigned char*)s1 > *(unsigned char*)s2) ? -1 : 1);
}

and compile it with the following command:

gcc mylib.c -shared -Wl,-soname,mylib -o mylib.so -fPIC

As you probably noticed, it behaves opposite to the original strcmp function: it returns negative value when the second string is greater than the first one, and positive value otherwise.

Now all you have to do is to inject the custom library code into the running program. Fortunately, Linux allows you to load your own dynamic libraries before starting any executable with LD_PRELOAD environment variable. We can take advantage of this feature - just compare the results of the two following commands:

[adam@ubuntu:~]$ users
adam eve

[adam@ubuntu:~]$ LD_PRELOAD="./mylib.so" users
eve adam

Because we reversed the behaviour of the strcmp function, and users executable relies on it, we managed to change the result of the command (user logins are reversed in the second example) without even touching it.

Google used the same trick to create TCMalloc, which is a faster modification of the standard Linux malloc.

OSV - operating system for the cloud

Cloud development requires design oriented towards environment with reduced performance. With many virtual servers occupying one physical machine a lot of processing power is consumed by context switching, reducing overall performance of all virtual instances.

OSV is a new operating system designed specifically for instances running in the cloud, written in C++ (which, as a side note, proves that Linus Torvalds was wrong when he claimed that C++ is not suitable for writing a system kernel). OSV reduces a lot of overhead found in the traditional operating systems, like kernel memory protection. If you ever worked with operating system which does not use such protection (like AROS or MorphOS), especially on hardware with x86 architecture, you must have observed a huge performance gain on those systems. Of course the biggest drawback of this approach is that a badly written application can crash the whole machine. However, since OSV does not run directly on hardware, but on top of a hypervisor (such as Xen or KVM) such crash affects only a virtual cloud instance, not the whole server. Moreover, OSV runs a standard Java Virtual Machine, which provides automatic memory management and necessary level of protection by itself, so no extra effort from the operating system is needed to ensure software stability.

Will OSV become sucessful? It's hard to say at the moment, but it surely shows a new trend, where not only hardware and applications, but also operating systems evolve to fit the new reality which cloud computing creates. If you are interested in trying out OSV yourself, here are some instructions how to run an Amazon EC2 instance with OSV on-board.

Waiting for the seamless cloud

You may not have heard about memristor, the long sought fundamental circuit element (next to resistor, capacitor and inductor), but this invention can be the greatest revolution in computer industry since introducing the transistor. Memristors have simpler construction than transistors and don't require external power source to retain information. Last year Crossbar Inc. unveiled their RRAM non-volatile memory technology with shockingly impressive characteristics: 1 terabyte of data on a single chip with 20 times faster access than offered by traditional NANDs.

But this is just the beginning. When technology evolves, it may be able to replace not only flash drives, but also DRAMs, which will have a huge impact on the whole computer industry. Imagine a device with only one memory space, used both as data storage and for running applications. Moreover, applications are loaded into memory only once, and they stay there even when you turn the power off. You can take off the battery from the smartphone and replace it with a new one, and after turning the power on you instantly get your device just as you left it.

Sounds familiar? If you ever worked with Smalltalk you already know the whole idea. If you didn't, I strongly encourage you to try out Squeak or Pharo. They are both open source Smalltalk implementations, and they provide complete, object-oriented working environment. What is unique about Smalltalk is that you can start applications, create new workspaces, build classes and objects, and when you quit, the whole environment is saved in an image, and restored on the next session. At first sight it looks like simple hibernation, but it isn't. In Smalltalk you can build applications without writing the source code in a traditional way. You just create an object, dynamically add properties and methods to it, and it becomes a part of the current environment. When you want to distribute the application you just distribute the image, which has all the application code, libraries, and necessary tools.

RRAM is a technology which will eventually allow to implement the old Smalltalk idea on the hardware level and finally separate virtual machines from underlying hardware. Currently, every time a virtual machine crashes, a new instance needs to be started from scratch and configured. Although this process can be automated with tools like Puppet, it still takes time and makes applications run from scratch. With RRAM-based cloud the problem will not exist any more: you will be able to save the state of a virtual machine at any moment and than spawn it or move it to another physical location (server, rack unit, or even datacenter) within seconds. More important, the state of all the applications will be preserved, which means that, for example, you will not loose user sessions even if you move a virtual machine to another location.

In my opinion it will be a next big step in cloud computing evolution. Now the cloud instances are mostly stateless, and require external storage or cache to keep user data. With the new memory chips they will be able to preserve their state even while moving across different hardware, and this process will become absolutely seamless for the end user - just the same way the GSM networks work today, keeping your call running even when you switch between base transceiver stations while talking.