3. Maximale Performance für strip()

Maximale Performance für strip()


  • Hallo,

    ich würde gerne die lstrip/rstrip/strip Reihe von Funktionen implementieren, mit maximaler Performance (warum sonst C++ nehmen), einfach aus Spaß. Mir ist klar, dass es das schon als Lib gibt. Ich mache das aus "educational purposes". Hier ist meine Version:

    #pragma once

#include <string>
#include <string_view>

namespace detail { constexpr auto ws = " \t\v\r\n\f"; }

[[nodiscard]] std::string lstrip(std::string_view str, char ch);
[[nodiscard]] std::string rstrip(std::string_view str, char ch);
[[nodiscard]] std::string strip(std::string_view str, char ch);

[[nodiscard]] std::string lstrip(std::string_view str, std::string_view chars = detail::ws);
[[nodiscard]] std::string rstrip(std::string_view str, std::string_view chars = detail::ws);
[[nodiscard]] std::string strip(std::string_view str, std::string_view chars = detail::ws);

std::string_view view_lstrip(std::string_view str, char ch);
std::string_view view_rstrip(std::string_view str, char ch);
std::string_view view_strip(std::string_view str, char ch);

std::string_view view_lstrip(std::string_view str, std::string_view chars = detail::ws);
std::string_view view_rstrip(std::string_view str, std::string_view chars = detail::ws);
std::string_view view_strip(std::string_view str, std::string_view chars = detail::ws);

/*! Implementation !*/

namespace detail {
    template<class Return, class Separator>
    Return lstrip(std::string_view str, Separator ch) {
        auto first = str.find_first_not_of(ch);
        return first == std::string::npos ? "" : Return{str.substr(first)};
    }

    template<class Return, class Separator>
    Return rstrip(std::string_view str, Separator ch) {
        auto last = str.find_last_not_of(ch);
        return last == std::string::npos ? "" : Return{str.substr(0, last + 1)};
    }

    template<class Return, class Separator>
    Return strip(std::string_view str, Separator ch) {
        auto first = str.find_first_not_of(ch);
        auto last = str.find_last_not_of(ch);
        return first == std::string::npos ? "" : Return{str.substr(first, last - first + 1)};
    }
} // namespace detail

inline std::string lstrip(std::string_view str, char ch) {
    return detail::lstrip<std::string>(str, ch);
}

inline std::string rstrip(std::string_view str, char ch) {
    return detail::rstrip<std::string>(str, ch);
}

inline std::string strip(std::string_view str, char ch)  {
    return detail::strip<std::string>(str, ch);
}

inline std::string lstrip(std::string_view str, std::string_view chars) {
    return detail::lstrip<std::string>(str, chars);
}

inline std::string rstrip(std::string_view str, std::string_view chars) {
    return detail::rstrip<std::string>(str, chars);
}

inline std::string strip(std::string_view str, std::string_view chars)  {
    return detail::strip<std::string>(str, chars);
}

inline std::string_view view_lstrip(std::string_view str, char ch) {
    return detail::lstrip<std::string_view>(str, ch);
}

inline std::string_view view_rstrip(std::string_view str, char ch) {
    return detail::rstrip<std::string_view>(str, ch);
}

inline std::string_view view_strip(std::string_view str, char ch) {
    return detail::strip<std::string_view>(str, ch);
}

inline std::string_view view_lstrip(std::string_view str, std::string_view chars) {
    return detail::lstrip<std::string_view>(str, chars);
}

inline std::string_view view_rstrip(std::string_view str, std::string_view chars) {
    return detail::rstrip<std::string_view>(str, chars);
}

inline std::string_view view_strip(std::string_view str, std::string_view chars) {
    return detail::strip<std::string_view>(str, chars);
}

    Meine Frage: Habe ich schon das Optimum erreicht? Oder kann man es besser machen? Wie man sieht habe ich 4 Fälle betrachtet: Man braucht ein neues std::string Object, oder möchte nur einen string_view (schneller), und man sucht nach mehreren Zeichen, oder nur einem einzigen (schneller).

    Freue mich über jede Anregung.

    0

  • Also erstmal würde ich vermeiden einen Leerstring per "" zu erstellen, das geht mit Return{} effizienter.

    Und dann würde ich den Test auf npos wegmachen. Dummerweise gibt's keine string Funktionen die Zeiger zurückgeben. Aber man kann sowas einfaches wie trim (BTW wo findet man das unter dem Namen strip?) ja auch selbst implementieren. Womit es dann trivial wird den Vergleich zu vermeiden.
    z.B.

    template <class Return, class Separator>
Return rstrip(std::string_view str, Separator ch) {
    auto b = str.data();
    auto e = first + str.size();
    while (e > b && e[-1] == ch)
        e--;
    return Return{b, e};
}

    Dann kannst du dich noch spielen und gucken wie man den Loop anders schreiben könnte, so dass er besser optimiert werden kann. Loop Unrolling könnte für den Compiler z.B. einfacher sein wenn man einen "klassischen" for loop schreibt (for (size_t i = len; i > 0 ; i--)).

    0

  • Also das "" durch Return{} zu ersetzen macht bei mir bei rstrip nichts aus aber bei lstrip recht viel.. Also guter Tipp!

    Strip heißt es in Python (ich versuche gerade die "tollen" String-Funktionen aus Python in C++ zu programmieren, da in C++ einige nützliche Dinge fehlen), und die Unicode Version von Java heißt glaube auch strip. Ich kann ja nochmal alle Funktionen als trim definieren, dann funktioniert beides 😃

    Die handgeschriebene Version läuft auf 1 Mio Iterationen wenige ms schneller, bei ca. 50ms Laufzeit. Das Problem ist halt, dass es für mehrere Zeichen die getrimmed werden sollen gleich noch komplizierter wird (muss eine weitere Implementierung schreiben), und ich denke spätestens da ist die standard Funktion schneller. Bei rstrip, wo ich ja den Vergleich sparen kann, ist es sogar schneller als die handgeschriebene Version (auch wenns nur knapp 1ms ist). Bei "," vs ',' suchen oder std::string vs std::string_view Return-Wert sind die Unterschiede schon >= 30%, aber ich denke ich bin zu faul alle Versionen von Hand zu implementieren. Klar, ich sagte maximale Performance, aber wie gesagt in manchen Fällen war ja die handgeschriebene Version nicht mal schneller. Bei ltrim habe ich den größten Vorteil gesehen (etwa 5% schneller)

    Der Vergleich macht meine Version tatsächlich auch wenige ms langsamer auf 1Mio Iterationen. Das Tolle ist, dass npos + 1 == 0 und somit substr(0, 0) sowieso ein leerer String ist (bei rstrip). Da spart man sich den Test gleich mal.

    Mir ist bei strip noch eine andere Optimierung eingefallen (dank Deiner Idee mit der Version von Hand): Man kann den Test auf npos gleich nach dem ersten 'find_first_of' machen, und gleich rausspringen. Das ist gleich mal doppelt so schnell (bzw. nicht halb so schnell), wenn z. B. der String nur aus Leerzeichen besteht. Sonst bringt es natürlich auch nicht wirklich viel.

    Jetzt sieht's bei mir so aus:

        template<class Return, class Separator>
    Return lstrip(std::string_view str, Separator ch) {
        auto first = str.find_first_not_of(ch);
        return first == std::string::npos ? Return{} : Return{str.substr(first)};  // Return{} anstatt "", evtl. hier von Hand implementieren (Ticken schneller)
    }
    template<class Return, class Separator>
    Return rstrip(std::string_view str, Separator ch) {
        auto last = str.find_last_not_of(ch);
        return Return{str.substr(0, last + 1)};  // Vergleich überflüssig, substr(0, npos + 1) == substr(0,0)
    }

    template<class Return, class Separator>
    Return strip(std::string_view str, Separator ch) {
        auto first = str.find_first_not_of(ch);
        if (first == std::string::npos) return {};  // anstatt return ""  ---- und frühzeitig rausspringen bei Strings mit nur trim-Zeichen
        auto last = str.find_last_not_of(ch);
        return Return{str.substr(first, last - first + 1)};
    }
    0
Anmelden zum Antworten