Ein funktionaler Blick auf modulare Algorithmen

Im Blog-Beitrag vom August 2014 haben wir die Modularisierung von Bildverarbeitungsalgorithmen mit der Template-basierten Policy im Vergleich zum dynamischen Polymorphismus basierten Strategy-Muster in Bezug auf Geschwindigkeit verglichen. Wir werden erneut die Laufzeit von (fast) denselben pixelweisen Operationen auf Bildern vergleichen. Diesmal betrachten wir jedoch verschiedene funktionale Modularisierungstechniken. Wir werden Funktionszeiger, Lambdas und abgeleitete Funktoren an Algorithmen übergeben und verschiedene Argumenttypen wie std::function oder generische Typen verwenden.

Hinweis

Diesen Artikel habe ich ursprünglich auf englisch geschrieben und im August 2023 mit ChatGpts Hilfe ins Deutsche übersetzt. Das ist eine seltene und alte Ausnahme. Üblicherweise schreibe ich Artikel auf deutsch und die Übersetzung ins Englische passiert in Kollaboration mit einer Maschine.

Unser Algorithmus ist eine binäre Operation auf zwei Bildern. Er durchläuft die beiden Eingangsbilder und ein Ausgangsbild. Dabei wird eine pixelweise binäre Operation auf den Eingangsbildern angewendet und das Ergebnis im Ausgangsbild gespeichert. Die pixelweise binäre Operation wird als First-Class-Citizen-Funktion als verschiedene Argumenttypen übergeben:

• std::function
• template Argument
• Funktionszeiger
• Basisklasse von Funktoren mit dynamischer Polymorphie

Als Eingabe für die Funktionsargumente verwenden wir Lambda-Funktionen, Funktionszeiger und abgeleitete Funktoren.

Funktionale Modularisierung

In diesem Abschnitt beschreiben wir sehr kurz, wie man Modularisierung durch das Übergeben von Funktionen anwendet. Zeitmessungen sind Gegenstand des nächsten Abschnitts.

Der einfache Bildtraversierungsalgorithmus ist im folgenden Beispiel dargestellt:

void binary(SomeFuncArgType op, const Image& im_in1, const Image& im_in2,
            Image& im_out, unsigned width, unsigned height)
{
    for (unsigned y = 0u; y < height; y++)
        for (unsigned x = 0u; x < width; x++)
            im_out[x + y * width] = op(im_in1[x + y * width], 
                                       im_in2[x + y * width]);
}

wobei SomeFuncArgType ein Platzhalter für die nachfolgenden Typen und die Klasse Image ein Vektor von Gleitkommazahlen ist, d.h.

using Image = std::vector<float>;

Im Folgenden zeigen wir nur die unterschiedlichen Funktionssignaturen, da die Implementierungen identisch sind.

std::function

Der Typ std::function ist ein generischer Funktionswrapper. Man kann std::function verwenden, um Funktionszeiger oder Funktoren/Lambdas zu speichern. Die Verwendung von std::function zur Modularisierung des Algorithmus ist in der folgenden Signatur dargestellt.

void binary_func(std::function<float(float, float)> op, 
                 const Image& im_in1, const Image& im_in2, 
                 Image& im_out, unsigned width, unsigned height);

Template-Argument

Wie bei std::function kann man Funktoren/Lambdas und Funktionszeiger an den Algorithmus mittels Template-basierter Signatur übergeben.

template <typename F>
void binary_template(F op, const Image& im_in1, const Image& im_in2,
                     Image& im_out, unsigned width, unsigned height);

Roher Zeiger

Die rohe Zeiger-Signatur ist C-kompatibel.

void binary_pointer(float (*op)(float, float), const Image& im_in1, 
                    const Image& im_in2, Image& im_out, unsigned width, 
                    unsigned height)

Man kann Funktionszeiger von freien Funktionen entweder per Adresse oder direkt übergeben, d.h.

binary_pointer(&free_func, ...);
binary_pointer(free_func, ...);

Auch Lambdas, wenn die keine Variablien aus ihrer Umgebung erfassen, können als Funktionszeiger übergeben werden. Diese letzte Möglichkeit wird in unseren Experimenten ignoriert.

Basisklasse von Funktoren mit Dynamische Polymorphie

Mit der abstrakten Basisklasse BaseFunctor ergibt sich folgende Signatur.

void binary_dyn_poly(const BaseFunctor& op, const Image& im_in1, 
                     const Image& im_in2, Image& im_out, unsigned width,
                     unsigned height);

Hinweis

Die Algorithmen der Standardbibliothek erhalten ihr Prädikat per Wert. Daher ist dieser Fall der einzige, bei dem wir for-Schleifen nicht durch std::transform ersetzen konnten. Die Ausführungsgeschwindigkeit ist jedoch in allen anderen Fällen für beide Varianten ähnlich.

Binäre Pixelweise-Operationen

Für zwei Additionen (eine gewöhnliche und eine unnötig komplizierte) und eine Maximum-Operation verwenden wir Lambdas,

auto add_lambda = [](float a, float b) { return a + b; };
auto add_complicated_lambda = [](float a, float b) 
{ 
    return std::sqrt(a * a) + std::sqrt(b * b); 
};
auto maximum_lambda = [](float a, float b) { return std::max(a,b); };

Funktionszeiger von freien Funktionen

auto add_func (float a, float b) { return a + b; }
auto add_complicated_func(float a, float b) 
{ 
    return std::sqrt(a * a) + std::sqrt(b * b); 
}
auto maximum_func(float a, float b) { return std::max

(a, b); }

und abgeleitete Funktoren von der abstrakten Basisklasse

struct AddFunctor : public BaseFunctor
{ 
    virtual float operator()(float a, float b) const override
    {
        return a + b; 
    } 
};
struct AddComplicatedFunctor : public BaseFunctor
{ 
    virtual float operator()(float a, float b) const override 
    {
        return std::sqrt(a*a) + std::sqrt(b*b); } 
    };
struct MaxFunctor : public BaseFunctor
{ 
    virtual float operator()(float a, float b) const override
    {
        return std::max(a, b); 
    } 
};

Geschwindigkeitsmessungen

Wir wenden die pixelweisen binären Operationen mit gleichen Operanden auf einen std::vector<float> von 1024x1024 Nullen 100 Mal mit jedem Ansatz an. Als Benchmark verwenden wir die minimale Laufzeit in Mikrosekunden ($\mu{\rm s}$) über die 100 Durchläufe. Wir verwenden einen Intel Core i7-6700HQ CPU @ 2,60 GHz Mobilprozessor. Als Compiler verwenden wir GCC 5.4 und Clang 3.9 unter Ubuntu 16.04 sowie Visual Studio 2017 unter Windows 10 (alle 64 Bit). Wir haben im Release-Modus kompiliert.

Wir werden 8 Paare von Argumenttypen (Signatur) und übergebenen Typen berücksichtigen:

• Zeiger, der als std::function übergeben wird
• Lambda, die als std::function übergeben wird
• abgeleiteter Funktor, der als std::function übergeben wird
• Lambda, die an ein templatbasiertes Argument übergeben wird
• Zeiger, der an ein templatbasiertes Argument übergeben wird
• abgeleiteter Funktor, der an ein templatbasiertes Argument übergeben wird
• Zeiger, der als Zeiger übergeben wird
• abgeleiteter Funktor, der als Basisklasse von Funktoren übergeben wird

Für jede pixelweise binäre Operation werden wir die Paare nach einem Straf-Score für den Vergleich über Compiler sortieren. Hierfür ordnen wir die Paare nach ihren Laufzeiten. Jedem Paar wird ein Straf-Score von $(t_{\rm cur} - t_{\rm prev}) // 100$ zugeordnet, wobei $t_{\rm cur}$ die Laufzeit des aktuellen Paares ist, $t_{\rm prev}$ die Laufzeit des vorherigen besseren Paares ist und $//$ die Ganzzahldivision bezeichnet. Das endgültige Ranking ergibt sich aus der Summe der Straf-Scores über die verschiedenen Compiler und wird in den folgenden Tabellen dargestellt. Zusätzlich enthalten die Tabellen die minimale Laufzeit in Mikrosekunden für jeden Compiler.

add

komplizierte Addition

Maximum

Besonderheit

Visual Studio 2017 ist unglaublich schnell für den komplizierten Additionsfall, wenn die Lambda-Funktion an die Template-basierte Algorithmusimplementierung übergeben wird. Dies erfordert weitere Untersuchungen und könnte zu einem weiteren Blog-Beitrag führen.