Jörn Horstmann, 2004-03-02

Update 2005-08-06: Die Messungen wurden damals mit Java 1.4 und der Client-VM durchgeführt. Mit Version 1.5 und der Server-VM sollte der Unterschied deutlich geringer Ausfallen. Ich bin allerdings noch nicht dazu gekommen erneut zu messen.

Ein genetischer Algorithmus ist eine Metaheuristik die zur Lösung von NP-schweren Optimierungs­problemen eingesetzt werden kann.

Bekannte Probleme zu deren Lösung genetische Algorithmen eingesetzt wurden sind das Resource Constrained Project Scheduling Problem (RCPSP), das Travelling Salesman Problem (TSP) und das Vehicle Routing Problem (VRP).

Da die Laufzeit des Algorithmus bis zum Finden einer guten Lösung mitunter sehr lang sein kann spielt die Performance einer Implementierung eine große Rolle. Im folgenden wird daher der Performance­unterschied zwischen einer Implemen­tierung in C und einer äquivalenten Implemen­tierung in Java untersucht.

Der hier vorgestellte genetische Algorithmus arbeitet auf einer Permutation einer Menge von n Zahlen zwischen 0 und n. Diese Kodierung bezeichnet im Falle des RCPSP die Reihenfolge in der Aktivitäten nach der seriellen oder parallelen Methode eingeplant werden sollen.

Bei der Mutation werden zwei aufeinanderfolgende Elemente mit einer Wahrscheinlichkeit von 0,1 miteinander vertauscht. Die Rekombination wählt zunächst einen Zufallswert zwischen 0 und n. Alle Elemente bis zu diesem Index werden aus dem Vater-Individuum übernommen. Danach werden alle Elemente des Mutter-Individuums durchlaufen, wenn diese noch nicht im Nachfolger vorhanden sind werden sie an diesen angehängt. Der Nachfolger hat dann die gleiche Länge wie seine Eltern-Individuen.

Der verwendete Quellkode stammt aus einem Projekt an der Berufsakademie Stuttgart und wurde im Rahmen der Vorlesung SE-Projekt ursprünglich in Java eintwickelt. Um umfangreichere Unter­suchungen über den Einfluß von Parametern zu machen war das Programm zu langsam und wurde daher in C neu geschrieben.

Da während des Neuschreibens weitere Teile des Programms geändert und optimiert wurden konnte nicht genau nachvollzogen werden welchen Anteil der C-Compiler an der Geschwindigkeits­steigerung hatte. Dieser Vergleich soll nun an einer reduzierten Version des Quellkodes nachgeholt werden.

Der hier verwendete Java-Quellkode orientiert sich stark an der C-Version, das Anlegen neuer Objekte in der cross-Methode wird im Gegensatz zur ursprünglichen Version vermieden.

Ergebnisse

Die Ergebnisse wurden auf einem Compaq Evo N610c mit 1,8 GHz Pentium IV erzielt. Die Startzeiten der Java VM wurden dabei mit gemessen, diese haben bei längeren Individuen aber kaum Einfluß auf die Laufzeit

test.c

Compilieren mit gcc test.c -o test.exe -std=c99 -O3 -march=pentium4.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*#include <assert.h>*/

#define ITERATIONS 100000
#define MAX_SIZE 200
#define BITMAP_SIZE ((MAX_SIZE / 32)+1)

#define RANDOM_DOUBLE() ((double)rand()/(RAND_MAX+1))
#define RANDOM_INT(x)   ((int)x*(double)rand()/(RAND_MAX+1))

typedef unsigned int uint;
typedef unsigned char uchar;

typedef struct List {
    uint size;
    uint data[MAX_SIZE];
    uint bitmap[BITMAP_SIZE];
} List;

void List_init(List *this)
{
    memset(this,0,sizeof(List));
}

int List_contains(List *this,uint i)
{
    return 0 != (this->bitmap[i >> 5] & ((uint)1 << (i & 31)));
}

void List_set(List *this,uint i)
{
    /*assert(!List_contains(this,i));*/
    this->data[this->size++] = i;
    this->bitmap[i >> 5] |= ((uint)1 << (i & 31));
}

void List_remove(List *this,uint i)
{
    /*assert(List_contains(this,i));*/
    int j = 0;
    while (j < this->size && this->data[j] != i) {
        j++;
    }
    if (j < this->size) {
        for (int k=j;k<this->size;k++)
            this->data[k] = this->data[k+1];
        this->size--;
        this->bitmap[i >> 5] &= ~((uint)1 << (i & 31));
    }
}

int List_empty(List *this)
{
    return this->size == 0;
}

void List_shuffle(List *this)
{
    List_init(this);
    for (int i=0;i<MAX_SIZE;i++) {
        List_set(this,i);
    }
    for (int i=0;i<MAX_SIZE;i++) {
        int j = RANDOM_INT(MAX_SIZE);
        int tmp       = this->data[i];
        this->data[i] = this->data[j];
        this->data[j] = tmp;
    }
}

void List_mutate(List *this)
{
    for (int i=0;i<MAX_SIZE-1;i++) {
        if (RANDOM_DOUBLE() < 0.1) {
            int tmp         = this->data[i];
            this->data[i]   = this->data[i+1];
            this->data[i+1] = tmp;
        }
    }
}

void cross(List *l1, List *l2, List *out)
{
    List_init(out);

    int idx = RANDOM_INT(MAX_SIZE);

    for (int i=0;i<idx;i++) {
        List_set(out,l1->data[i]);
    }
    for (int i=0;i<MAX_SIZE;i++) {
        if (!List_contains(out,l2->data[i]))
            List_set(out,l2->data[i]);
    }
    List_mutate(out);
}

int main(int argc, char *argv[])
{
    List list1,list2,list3;

    for (int i=0;i<ITERATIONS;i++) {
        /*printf("%d\n",i);*/
        /*List_init(&list1);*/
        List_shuffle(&list1);
        /*List_init(&list2);*/
        List_shuffle(&list2);

        cross(&list1,&list2,&list3);
    }
    return 0;
}

test.java

Compilieren mit javac test.java.

import java.io.*;
import java.util.*;

class MyList
{
    static final int MAX_SIZE    = 200;
    static final int BITMAP_SIZE = ((MAX_SIZE / 32)+1);

    private int   size;
    private int[] data;
    private int[] bitmap;

    public MyList()
    {
        this.size   = 0;
        this.data   = new int[MAX_SIZE];
        this.bitmap = new int[BITMAP_SIZE];
        this.init();
    }

    void init()
    {
        this.size = 0;
        java.util.Arrays.fill(this.data  ,0);
        java.util.Arrays.fill(this.bitmap,0);
    }

    boolean contains(int i)
    {
        return 0 != (this.bitmap[i >> 5] & ((int)1 << (i & 31)));
    }

    void set(int i)
    {
        this.data[this.size++] = i;
        this.bitmap[i >> 5] |= (1 << (i & 31));
    }

    int get(int i)
    {
        return this.data[i];
    }

    void remove(int i)
    {
        int j = 0;
        while (j < this.size && this.data[j] != i) {
            j++;
        }
        if (j < this.size) {
            for (int k=j;k<this.size;k++)
                this.data[k] = this.data[k+1];
            this.size--;
            this.bitmap[i >> 5] &= ~(1 << (i & 31));
        }
    }

    boolean empty()
    {
        return this.size == 0;
    }

    void shuffle()
    {
        this.init();
        for (int i=0;i<MAX_SIZE;i++) {
            set(i);
        }
        for (int i=0;i<MAX_SIZE;i++) {
            int j = (int)(MAX_SIZE*Math.random());
            int tmp      = this.data[i];
            this.data[i] = this.data[j];
            this.data[j] = tmp;
        }
    }

    void mutate()
    {
        for (int i=0;i<MAX_SIZE-1;i++) {
            if (Math.random() < 0.1) {
                int tmp         = this.data[i];
                this.data[i]   = this.data[i+1];
                this.data[i+1] = tmp;
            }
        }
    }

    void cross(MyList l1,MyList l2)
    {
        this.init();
        int idx = (int)(MAX_SIZE*Math.random());

        for (int i=0;i<idx;i++) {
            set(l1.get(i));
        }
        for (int i=0;i<MAX_SIZE;i++) {
            int x = l2.get(i);
            if (!contains(x))
                set(x);
        }
        mutate();
    }
}

public class test
{
    final static int ITERATIONS = 100000;

    public static void main(String[] args)
    {
        MyList list1 = new MyList();
        MyList list2 = new MyList();
        MyList list3 = new MyList();
        for (int i=0;i<ITERATIONS;i++) {
            list1.shuffle();
            list2.shuffle();
            list3.cross(list1,list2);
        }
    }
}

bench.c

Compilieren mit gcc bench.c -o bench.exe.

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

int main(int argc, char *argv[])
{
    LARGE_INTEGER Timestamp,Frequency;
    unsigned int t1,t2;
    /*double delta;*/
    double c_time,java_time,ratio;

    // fits into LowPart on my Pentium IV 1.8 GHz
    QueryPerformanceFrequency(&Frequency);

    /*printf("%ld, %ld\n",Timestamp.HighPart,Timestamp.LowPart);*/
    /*printf("%ld, %ld\n",Frequency.HighPart,Frequency.LowPart);*/

    printf("c\n");
    QueryPerformanceCounter(&Timestamp);
    t1 = Timestamp.LowPart;
    system("test.exe");
    QueryPerformanceCounter(&Timestamp);
    t2 = Timestamp.LowPart;
    c_time = (double)1000.0/Frequency.LowPart*(t2 - t1);
    printf("%12.2f\n",c_time);

    printf("java\n");
    QueryPerformanceCounter(&Timestamp);
    t1 = Timestamp.LowPart;
    system("java test");
    QueryPerformanceCounter(&Timestamp);
    t2 = Timestamp.LowPart;
    java_time = (double)1000.0/Frequency.LowPart*(t2 - t1);
    printf("%12.2f\n",java_time);

    printf("c / java: %.2f\n",c_time/java_time);
    printf("java / c: %.2f\n",java_time/c_time);

    return 0;
}