Adventskalender 10. Dezember 2023 - Bibliothek für Quellcodeverleih

[paedubucher]

Bibliothek für Quellcodeverleih

Diese Woche wurden bereits Zahlen auf dem DAMPF-Stack in ihre Primfaktoren zerlegt. Die Performance war weder mit PHP (mod_php, PHP-FPM) noch mit Python berauschend.

Besinnen wir uns also auf das gute, alte C und verzichten wir für einmal auf das Web! Doch wie können wir die Programmlogik dennoch wiederverwendbar machen, zumal wir auf das Web als Deployment-Mechanismus verzichten müssen? Hierzu soll eine sogenannte Shared Library verwendet werden!

factorizer: Ein Programm zum Faktorisieren von Primzahlen

Zunächst einmal soll ein C-Programm zur Faktorisierung von Primzahlen geschrieben werden. Zur Faktorisierung müssen als erstes Primzahlen bis zu einer bestimmten Obergrenze gefunden werden können:

Code: Alles auswählen

int *primes_up_to(int x)
{
    int i = 0, j = 0;
    int *primes = NULL;

    if (x < 2) {
        primes = (int *)malloc(sizeof(int));
        primes[0] = 0;
        return primes;
    }

    primes = (int *)malloc(sizeof(int) * x);
    memset(primes, 0, x);

    for (i = 2, j = 0; i <= x; i++) {
        if (is_prime(i)) {
            primes[j++] = i;
        }
    }

    return primes;
}

bool is_prime(int x)
{
    if (x < 2) {
        return false;
    }
    for (int i = 2; i <= x / 2; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

Dies bewerkstelligt die Funktion primes_up_to zusammen mit der Hilfsfunktion is_prime. Der grösste Unterschied zur PHP-Implementierung ist das Memory-Management: Da ein Array von Primzahlen zurückgegeben werden soll, muss hierfür mit malloc Platz reserviert werden. Da es schwer abzuschätzen ist, wie viele Primzahlen bis zur Obergrenze auftauchen werden, wird einfach Platz für x Primzahlen reserviert. Das Array ist 0-terminiert, wodurch ein Element am Ende benötigt wird ‒ Platz ist ja genug da. Die Elemente werden einfach alle mit 0 initialisiert. Wird eine unsinnige Obergrenze (x < 2) verlangt, wird einfach ein Array bestehend aus dem 0-Element zurückgeliefert. Der Aufrufer kann dann über die Ergebnisse iterieren, bis der Wert 0, der ja bekanntlich keine Primzahl ist, erreicht worden ist.

Auch die Faktorisierung einer einzelnen Zahl wurde sehr ähnlich wie in PHP gelöst:

Code: Alles auswählen

int *factorize(int x)
{
    int i = 0, j = 0, n = 0;
    int *primes = NULL, *factors = NULL;

    if (x < 1) {
        factors = (int *)malloc(sizeof(int));
        factors[0] = 0;
        return factors;
    }

    n = log2(x) + 1; // heuristic: log2(16) = 4, fits "worst" case  [2, 2, 2, 2]
    primes = primes_up_to(sqrt(x));
    factors = (int *)malloc(sizeof(int) * (n + 1));
    memset(factors, 0, n + 1);

    for (i = 0, j = 0; primes[i] != 0 && x > 1;) {
        if (x % primes[i] == 0) {
            factors[j++] = primes[i];
            x /= primes[i];
        } else {
            i++;
        }
    }
    if (x > 1) {
        factors[j] = x;
    }
    free(primes);

    return factors;
}

Auch hier spielt das Memory-Management wieder eine Rolle. Da man a priori nicht weiss, in wie viele Primfaktoren eine Zahl zerlegt werden kann, muss eine Heuristik beigezogen werden. Im “schlimmsten” Fall, d.h. bei Zweierpotenzen wie 32 oder 1024, wird ein Array von 2en ‒ der kleinsten Primzahl ‒ zurückgegeben. Die Anzahl der 2en kann mit dem 2er-Logarithmus berechnet werden. So erhalten wir von einer Zahl x maximal log2(x) Primfaktoren. Ein weiteres Element für die 0-Terminierung wird ebenfalls angefügt.

Weiter müssen die gefundenen Primzahlen nach der Faktorisierung mit free wieder entsorgt werden. (Da wir eine Library schreiben, wissen wir nicht, wie unser Code verwendet werden wird. Soll er in einem langlaufenden Serverprozess zum Einsatz kommen, darf auf keinen Fall Memory geleaked werden.)

Das Programm zur Faktorisierung sieht dann folgendermassen aus:

Code: Alles auswählen

#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool is_prime(int);
int *primes_up_to(int);
int *factorize(int);

int main(int argc, char *argv[])
{
    int lower = 0, upper = 0, i = 0, j = 0;

    if (argc < 3) {
        fprintf(stderr, "usage: %s [lower] [upper]\n", argv[0]);
        return 1;
    }

    lower = atoi(argv[1]);
    upper = atoi(argv[2]);
    if (lower > upper) {
        fprintf(stderr, "[lower] must be <= [upper], was %d > %d\n", lower, upper);
        return 1;
    }

    for (i = lower; i <= upper; i++) {
        printf("%d: ", i);
        int *factors = factorize(i);
        for (j = 0; factors[j] != 0; j++) {
            printf("%d ", factors[j]);
        }
        free(factors);
        putchar('\n');
    }

    return 0;
}

Der gesamte Code ist auf NoPaste zu finden.

Der Benutzer muss das Programm mit einer Unter- und Obergrenze aufrufen ‒ und wird über einen falschen Gebrauch über stderr informiert. Das Programm wird mithilfe von einem Makefile gebaut (hierzu sollte das Paket build-essential installiert sein):

Code: Alles auswählen

factorize: factorize.c
    gcc -Wall -std=c99 $^ -lm -o $@

Das Programm factorize wird anhand des Quellcodes in factorize.c gebaut. Mit -Wall werden alle Warnungen angezeigt. Es wird der Standard C99 mit -std verwendet. Die Variable $^ beinhaltet eine Liste aller Abhängigkeiten; hier ist das bloss factorize.c. Mithilfe von -lm wird die Mathematik-Library (math.h) dynamisch zugelinkt. Die Ausgabe findet mit dem Parameter -o und der automatischen Variable $@ in die Datei factorize statt.

Das Programm kann folgendermassen gebaut und ausgeführt werden:

Code: Alles auswählen

$ make
gcc -Wall -std=c99 factorize.c -lm -o factorize

$ ./factorize 10 20
10: 2 5
11: 11
12: 2 2 3
13: 13
14: 2 7
15: 3 5
16: 2 2 2 2
17: 17
18: 2 3 3
19: 19
20: 2 2 5

Die erste Spalte zeigt die Zahlen des gewünschten Bereichs an; in der zweiten Spalte werden dann die Primfaktoren dargestellt.

libfactorizer.so: Eine Programmbibliothek zur Faktorisierung von Primzahlen

Zwar läuft das Programm korrekt, doch lassen sich die eigentlichen Berechnungsfunktionen nicht in einem anderen Kontext wiederverwenden, etwa in einem CGI-Programm, welches andere Anforderungen an Eingabe/Ausgabe stellt als ein Kommandozeilenprogramm.

Die wiederverwendbaren Funktionen sollen darum in eine Shared Library ausgelagert werden, gegen die dann ein Anwendungsprogramm gelinkt werden kann. Dies würde u.a. auch die Aktualisierung oder Ersetzung der Library erlauben, ohne dass das Anwendungsprogramm neu kompiliert werden müsste.

Zuerst sollen die Funktionsdeklarationen in eine Header-Datei factorize.h ausgelagert werden:

Code: Alles auswählen

#ifndef foo_h
#define foo_h

extern int *factorize(int);
extern int *primes_up_to(int);
extern bool is_prime(int);

#endif

Hier gibt es zwei Unterschiede zur bisherigen Deklaration:

1. Alle Definitionen sind in das Präprozessor-Paar #ifndef/#endif eingeschlossen. Die ganzen Deklarationen sollen nur ausgeführt werden, wenn das Symbol foo_h noch nicht definiert ist, welches dann sogleich mit den Deklarationen zusammen definiert wird. (Das verhindert Mehrfachdeklarationen, wenn ein grösseres Programm die gleiche Header-Datei mehrmals einfügt.)
2. Die Funktionen sind mit dem Schlüsselwort extern deklariert. Dies weist den Compiler darauf hin, dass die Funktion in einer externen Library zu finden ist, die später dazugeklinkt wird.

Die Funktionen sind dann in einer etwas reduzierten Datei factorize.c abgelegt (hier gekürzt wiedergegeben):

Code: Alles auswählen

#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#include "factorize.h"

int *factorize(int x)
{
    // ...
}

int *primes_up_to(int x)
{
    // ...
}

bool is_prime(int x)
{
    // ...
}

Die Deklarationen werden aus der Header-Datei factorize.h herangezogen. Die Funktion main fehlt hingegen. Diese wurde in eine separate Datei main.c ausgelagert, die nicht zur Library gehört, sondern diese bloss verwendet (hier auch gekürzt wiedergegeben):

Code: Alles auswählen

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

#include "factorize.h"

int main(int argc, char *argv[])
{
    // ...
}

Bauen der Programmbibliothek

Aus der Datei factorize.c soll nun eine Bibliotheksdatei namens libfactorize.so erstellt werden. (Das Präfix lib ist eine Konvention, auf die sich der Linker zum Auflösen der Abhängigkeiten verlässt.) Die Kompilierung erfolgt in zwei Schritten, welche im Makefile definiert werden:

Code: Alles auswählen

libfactorize.so: factorize.o
        gcc -shared $^ -o $@

factorize.o: factorize.c
        gcc -c -Wall -fpic $^ -o $@

Das untere Target factorize.o ist eine Objektdatei, welche einen Zwischenschritt zur Library darstellt. Der Compiler wird mit dem Flag -c aufgerufen, welches ihn anweist, das Programm nur zu kompilieren und nicht zu linken. Das Flag -fpic sorgt dafür, dass position-independent code (PIC) generiert wird: Code, der nicht davon abhängig ist, an welchen genauen Adressen die Instruktionen zu liegen kommen. (Es werden relative statt absolute Offsets für Adressen verwendet.) Diese Option ist für eine externe Programmbibliothek sehr wichtig. (Für ausführbare Programme existiert die verwandte -fpie-Option.)

Das obere Target libfactorize.so ist die fertig gelinkte Library, welche auf Basis des Targets factorize.o erstellt wird. Hier ist das Flag -shared wichtig, das dafür sorgt, dass das Ergebnis von anderen Programmen verlinkt werden kann.

Die Library wird folgendermassen kompiliert:

Code: Alles auswählen

$ make libfactorize.so
gcc -c -Wall -fpic factorize.c -o factorize.o
gcc -shared factorize.o -o libfactorize.so

Nun soll das Programm factorize auf Basis von main.c und der Library libfactorize.so gebaut werden, wozu ein weiteres Target im Makefile definiert wird:

Code: Alles auswählen

factorize: main.c libfactorize.so
        gcc -L./ -Wall $^ -lfactorize -lm -o $@

Da sich die Library im gleichen Verzeichnis befindet, wird der Suchpfad hierfür mit dem Flag -L als ./ angegeben. Wichtig ist auch das Flag -lfactorize, welches die Library libfactorize.so (l wird zu lib erweitert) hinzulinkt, wie es auch mit der libm (für math.h) passiert.

Das Ergebnis ist ein Anwendungsprogramm, das leider noch nicht funktioniert:

Code: Alles auswählen

$ make factorize
gcc -L./ -Wall main.c libfactorize.so -lfactorize -lm -o factorize

$ ./factorize 10 12
./factorize: error while loading shared libraries: libfactorize.so: cannot open shared object file: No such file or directory

Library zur Ausführung finden

Die Library libfactorize.so kann offenbar nicht gefunden werden, obwohl sie im gleichen Verzeichnis liegt. Mithilfe von ldd(1) kann dies veranschaulicht werden:

Code: Alles auswählen

$ ldd factorize
        linux-vdso.so.1 (0x00007ffea84ff000)
        libfactorize.so => not found
        libm.so.6 => /usr/lib/libm.so.6 (0x00007fc36079f000)
        libc.so.6 => /usr/lib/libc.so.6 (0x00007fc3605bd000)
        /lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2 (0x00007fc3608b9000)

Die Library libfactorize.so kann ‒ im Gegensatz etwa zur libm.so.6 und zur libc.so.6 ‒ nicht gefunden werden.

Zur Laufzeit kann der Suchpfad für Libraries mithilfe der Umgebungsvariable LD_LIBRARY_PATH um weitere Verzeichnisse ergänzt werden:

Code: Alles auswählen

$ LD_LIBRARY_PATH="./:$LD_LIBRARY_PATH" ./factorize 10 12
10: 2 5
11: 11
12: 2 2 3

Zwar könnte diese Umgebungsvariable per export-Anweisung für die ganze Shell-Session gesetzt werden, es gibt aber eine bessere Variante: Die Library soll systemweit auffindbar gemacht werden.

Library systemweit konfigurieren

Zunächst soll die Library an einen passenden Ort für die systemweite Verwendung verschoben werden und Lese-/Ausführungsberechtigungen für alle Benutzer erhalten:

Code: Alles auswählen

$ sudo mv libfactorize.so /usr/local/lib/
$ sudo chmod 755 /usr/local/lib/libfactorize.so

Leider wird diese noch nicht von ldconfig(8) gefunden:

Code: Alles auswählen

$ sudo ldconfig -p | grep factor

Der Suchpfad für Shared Libraries kann jedoch ergänzt werden. Entweder geschieht das in der Datei /etc/ld.so.conf, welche alle *.conf-Dateien eines Unterverzeichnisses einfügt:

Code: Alles auswählen

include /etc/ld.so.conf.d/*.conf

So ist es sinnvoller, eine separate Datei in /etc/ld.so.conf.d/ anzulegen, etwa namens factorize.conf mit folgendem Inhalt:

Code: Alles auswählen

/usr/local/lib/

Der Library-Cache muss neu aufgebaut werden, damit die Änderung greift:

Code: Alles auswählen

$ sudo ldconfig
$ sudo ldconfig -p | grep factor
        libfactorize.so (libc6,x86-64) => /usr/local/lib/libfactorize.so

Nun klappt’s auch mit der Auflösung der Library und der Ausführung des Programms:

Code: Alles auswählen

$ ldd factorize | grep factor
        libfactorize.so => /usr/local/lib/libfactorize.so (0x00007f5c911e3000)

$ ./factorize 10 12
10: 2 5
11: 11
12: 2 2 3

Fazit

Ein in C geschriebenes Kommandozeilenprogramm zur Faktorisierung von Primzahlen wurde in eine Library und in eine Anwendung, welche diese Library verwendet, aufgeteilt. Die Organisation des Quellcodes und das Bauen der Artefakte wurden dadurch wesentlich komplizierter. Auch muss die Library auffindbar gemacht werden: Entweder bei der jeweiligen Ausführung, oder aber systemweit für alle künftigen Ausführungen. Der Vorteil, der darin besteht, dass nun verschiedene Programme auf die Funktionalität zurückgreifen können, wurde teuer erkauft. Doch kann sich dieser je nach Funktionsumfang der Library durchaus lohnen.

Übungen

Wer sich selber etwas mit C, Shared Libraries und dem ganzen Kompilier- sowie Konfigurationsvorgang einer Shared Library befassen möchte, kann sich an folgenden Übungen versuchen:

1. Erstelle eine weitere Library namens libprime.so, welche die beiden Funktionen primes_up_to und is_prime beinhaltet. Die neue Library soll systemweit zur Verfügung stehen.
2. Passe die bestehende Library libfactorize.so so an, dass sie nur noch die Funktion factorize enthält und anbietet. Diese soll entsprechend auf die neue Library libprime.so zurückgreifen.
3. Baue das Anwendungsprogramm factorize auf Basis der neuen Libraries und stelle sicher, dass die Abhängigkeiten zur Laufzeit aufgelöst werden können.

Gerne könnt Ihr euer Makefile hier posten. Vielleicht kennt jemand noch ein paar nützliche Flags für GCC in diesem Zusammenhang oder baut das Ganze lieber mithilfe von LLVM.

[Meillo]

Toller Beitrag! Mit schon dem zweiten anspruchsvollen C-Tuerchen steigen wir technisch ganz schoen tief ein.


Ein paar inhaltliche Anmerkungen:

- Statt der Kombination von malloc(3)+memset(3) ist es einfacher, gleich calloc(3) zu verwenden. Insofern nicht groesste Performance noetig ist (fuer die man jedoch besser das Speichermanagement sowieso aus den heissen Schleifen nach aussen verschiebt), sollte man malloc(3) immer durch calloc(3) ersetzen.

- Wenn in der Usage-Message die zwei Argument Pflicht sind, dann solltest du sie nicht in eckige Klammern setzen, weil die Optionalitaet symbolisieren. ... das ist sicherlich ein Ueberbleibsel einer frueheren Codeversion, in der sie noch optional waren.

- Wie du schon schreibst, ist das Array in primes_up_to() schrecklich ueberdimensioniert, waehrend das in factorize() eine gute Annaeherung hat. Hier waere eine etwas bessere Abschaetzung sinnvoll. Bis 10 sind etwa die Haelfte Primzahlen, bis 100 etwa ein Viertel, bis 1000 etwa ein Sechstel, bis 1 Million etwa ein Zwoelftel. Hier gibt es online sicherlich Anhaeherungsfunktionen, die gar nicht so genau sein muessen, aber statt 1000 Elementen fuer die benoetigten 168 Primzahlen halt nicht 1000 sondern vielleicht nur 200-300 reservieren. ... wobei das alles dann wiederum wohl egal ist, weil die Laufzeit das groessere Problem als der Speicherverbrauch ist. 1000 mal 4 Bytes sind gerade mal 4KB. Bei einer Million Zahlen werden erst 4MB fuer das Array verbraucht. Ob das dann 4 oder 1 MB sind, ist letztlich egal.

- Zum Laufzeitvergleich kann man diesen Shellbefehl heranziehen:

Code: Alles auswählen

time for i in `seq 1 1000`; do factor $i; done

... aber hier geht's ja eigentlich nicht um Primfaktorzerlegung, sondern um Shared Libs.

Jetzt braeuchte es noch ein Tuerchen, wo diese Lib aus PHP und Python heraus genutzt wird.

[chrbr]

Hallo paedubucher,
das ist ein toller Beitrag. Für einen C-Laien wie mich ist das eine hervorragende Einführung, die ich mit Sicherheit nachvollziehen werde.
Vielen Dank für das Türchen,
Christoph

[Livingston]

- Wie du schon schreibst, ist das Array in primes_up_to() schrecklich ueberdimensioniert, waehrend das in factorize() eine gute Annaeherung hat. Hier waere eine etwas bessere Abschaetzung sinnvoll.

Die definitive Obergrenze ist die Quadratwurzel. Dafür gibt's auch einen schönen Algo, der noch nicht mal fetten Speicher verbraucht.
Oje, da war ich grad am falschen Ende der Gedankenkette -> maximale Größe eines einzelnen Faktors

[paedubucher]

- Statt der Kombination von malloc(3)+memset(3) ist es einfacher, gleich calloc(3) zu verwenden. Insofern nicht groesste Performance noetig ist (fuer die man jedoch besser das Speichermanagement sowieso aus den heissen Schleifen nach aussen verschiebt), sollte man malloc(3) immer durch calloc(3) ersetzen.

Danke, das kannte ich noch gar nicht

- Wenn in der Usage-Message die zwei Argument Pflicht sind, dann solltest du sie nicht in eckige Klammern setzen, weil die Optionalitaet symbolisieren. ... das ist sicherlich ein Ueberbleibsel einer frueheren Codeversion, in der sie noch optional waren.

Das mit den eckigen Klammern sollte nicht Optionalität ausdrücken, sondern ist eine pädagogische Konvention, die ausdrücken soll, dass der ganze Ausdruck [foo] durch etwas anderes ersetzt werden soll. (Meine Schüler würden sonst einfach die String-Literale hinschreiben…) Aber das wird verständlicherweise als Optionalität verstanden; so sollte ich mich von dieser Konvention verabschieden.

- Wie du schon schreibst, ist das Array in primes_up_to() schrecklich ueberdimensioniert, waehrend das in factorize() eine gute Annaeherung hat. Hier waere eine etwas bessere Abschaetzung sinnvoll.

Offenbar ist n/log(n) schon eine sehr gute Annäherung (siehe Prime Number Theorem).

Wenn ich die Zahlen von 1.000.000 bis 1.000.100 damit faktorisiere, komme ich von 413.912 auf 144.040 Bytes runter

Siehe 42040.

Jetzt braeuchte es noch ein Tuerchen, wo diese Lib aus PHP und Python heraus genutzt wird.

Es gibt eine CGI-Variante von factorize.c, die aber bei nebenläufigen Requests nicht so gut performed Der Query-String wird mit strtok geparsed, was mir immer wieder aufs Neue Rätsel aufgibt. Ich poste den Code dann noch, wenn ich die virtuelle DAMPF-Maschine das nächste mal anwerfe. (Nachtrag: Ups, das CGI-Programm ging leider verloren…)

[Meillo]

- Wenn in der Usage-Message die zwei Argument Pflicht sind, dann solltest du sie nicht in eckige Klammern setzen, weil die Optionalitaet symbolisieren. ... das ist sicherlich ein Ueberbleibsel einer frueheren Codeversion, in der sie noch optional waren.

Das mit den eckigen Klammern sollte nicht Optionalität ausdrücken, sondern ist eine pädagogische Konvention, die ausdrücken soll, dass der ganze Ausdruck [foo] durch etwas anderes ersetzt werden soll. (Meine Schüler würden sonst einfach die String-Literale hinschreiben…) Aber das wird verständlicherweise als Optionalität verstanden; so sollte ich mich von dieser Konvention verabschieden.

Bei Usage-Meldungen stehen eckige Klammern eigentlich immer fuer etwas Optionales. Es irritiert sehr, wenn das anders genutzt wird.

Fuer Platzhalter werden oft Grossbuchstaben verwendet (das finde ich sinnvoll), z.B.:

tr [OPTION]... SET1 [SET2]

Man sieht, dass die Optionen und das Set2 optional sind. Man sieht, dass Option, Set1 und Set2 Platzhalter sind, die durch konkrete Werte ersetzt werden muessen. Und man sieht, dass es von Option mehrere geben kann.

Ich finde es wichtig, dass die Puenktchen ohne Leerzeichen anschliessen. Hier nochmal ein Beispiel:

cat [OPTION]... [FILE]...

Noch ein letztes Beispiel:

Usage: ./lightsout [-l LEVEL]

Als alternative Konvention in Manpages kenne ich noch die von Tcl, wo optionale Argument in Fragezeichen eingeschlossen sind und Platzhalter kursiv/unterstrichen ausgezeichnet sind, siehe z.B.: https://manpages.debian.org/bookworm/tc ... cl.en.html
(Nachtrag zur Einordnung: In Tcl sind das keine Befehle, sondern Funktionen ... die dort syntaktisch allerdings wie Shellbefehle aufgerufen werden.)

... und dann gab's noch irgendwelche Manpages, in denen Pflichtargumente in geschweiften Klammern notiert waren, aber ich habe vergessen, wo ich das gesehen habe.

[inne]

Hallo.

(auch wenn TRex mich wegen meines Setups abgestraft und angemault hat)
Mal ein dickes Dankeschön für diese Anleitung. Als Hobby und Laie wünscht man sich solche Anleitungen.

[paedubucher]

Mal ein dickes Dankeschön für diese Anleitung. Als Hobby und Laie wünscht man sich solche Anleitungen.

Danke für die Rückmeldung! Ich werde meine ganzen Türchen noch einmal nachbereiten und noch überarbeitet auf meiner Webseite veröffentlichen.

[Meillo]

Mal ein dickes Dankeschön für diese Anleitung. Als Hobby und Laie wünscht man sich solche Anleitungen.

Danke für die Rückmeldung! Ich werde meine ganzen Türchen noch einmal nachbereiten und noch überarbeitet auf meiner Webseite veröffentlichen.

Toll. Ich biete mich auch gerne als Testleser an.