Icon Ressource

Ressource [C] CpyCat Funktion, verkettet Strings schlauer als strcat

german

Aktives Mitglied
devCommunity-Experte
german erstellte eine neue Ressource:

[C] CpyCat Funktion, verkettet Strings schlauer als strcat - Tschüss mit "Schlemiel the painter's algorithm"

Vor ~20 Jahren hatte Joel Spolsky (langjähriger Microsoft Entwickler und Mitbegründer von StackOverflow) auf seiner Seite einen interessanten Artikel gepostet.
Es geht im Grunde darum zu verstehen, was die Effizienz von Code beeinflusst und warum es auch mal interessant sein kann hinter die Kulissen der Implementierung zu schauen, um ein Verständnis dafür zu entwickeln.
In einem Abschnitt zieht er die Analogie...
Erfahre mehr über diese Ressource...
 

Lowl3v3l

Mitglied
devCommunity-Experte
Hmm das ist interessant, weißt du zufällig, wie der verglichen mit der C++-Standardbibliothek performt?
 

german

Aktives Mitglied
devCommunity-Experte
Oh, ich glaube das ist Äpfel mit Birnen vergleichen. Hab so einen Vergleich deshalb auch noch nicht gemacht. Einerseits brauchst du bei C++ Klassen natürlich keine Nullterminierung suchen, weil die Länge bekannt ist. Andererseits sind Speicherallokationen teuer und zumindest in meinem Beispiel bin ich nicht davon ausgegangen, sich ggf. erst mal Speicher vom Heap zu holen und womöglich den vorhandenen String in einen neuen Bereich rüber kopieren zu müssen wo man wieder Platz hat, was anhängen zu können.
 

Lowl3v3l

Mitglied
devCommunity-Experte
Naja C++-Strings müssen nicht immer Speicher holen und wenn da intern Moves benutzt werden können gäbe es keine neue Allokation, daher hatte mich das interessiert^^
 

german

Aktives Mitglied
devCommunity-Experte
Ja klar. Wobei Moves aber am Ende nur eine Umschreibung dafür sind, in welchem Scope der Compiler den String anlegt. Mit Stringverkettung hat das nicht wirklich was zu tun, denn du kannst es zwar move nennen wenn du was von einem Speicherbereich in den anderen schiebst, ist aber in dem Fall auch nur kopieren. Wann Speicher allokiert wird und wann nicht, ist zudem unklar. Gibt ja neben size() auch noch capacity(). Wie viel da am Stück geholt wird und in welchen Stepps ist abhängig von der jeweiligen Implementierung.
Davon abgesehen ist die Aufnahme von string_views in den Standard ein recht gutes Indiz dafür, dass die Performance der string Klasse nicht zufriedenstellend ist. Und das offenbar signifikant, denn string_views sind ähnlich gefährlich wie Pointer und im Normalfall hätte man wahrscheinlich die Finger davon gelassen..
 

german

Aktives Mitglied
devCommunity-Experte
@Lowl3v3l Hab mal einen schmutzigen und somit nicht eindeutigen Testcode geschrieben. (Sinnvoller wäre eine zufällige Zeichenfolge gewesen, aber für einen ersten Eindruck reichts.)
C++:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <memory>
#include <chrono>
#include <string>
#include <cstring>

// returns the time elapsed between two calls (the return value of the first call is undefined)
double GetDuration()
{
  static std::chrono::time_point<std::chrono::high_resolution_clock> previous{};
  const auto current = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double> elapsed = current - previous;
  previous = current;
  return elapsed.count();
}

char* CpyCat(char* dest, char** const pEndptr, const char* src)
{
  if (dest != nullptr && src != nullptr)
  {
    char* it = (pEndptr == nullptr) ? dest : *pEndptr;
    if (it == nullptr)
      for (it = dest; *it != '\0'; ++it);

    for (; (*it = *src++) != '\0'; ++it);
    if (pEndptr != nullptr)
      *pEndptr = it;
  }

  return dest;
}

void test_strcat(const char* const ntstr)
{
  GetDuration();
  std::unique_ptr<char[]> buffer{ std::make_unique<char[]>(800032) };
  for (size_t i{}; i < 100000U; ++i)
  {
    std::strcat(buffer.get(), ntstr);
  }

  std::cout << GetDuration() << '\t' << __func__ << std::endl;
}

void test_CpyCat(const char* const ntstr)
{
  GetDuration();
  std::unique_ptr<char[]> buffer{ std::make_unique<char[]>(800032) };
  char* endptr{ buffer.get() };
  for (size_t i{}; i < 100000U; ++i)
  {
    CpyCat(buffer.get(), &endptr, ntstr);
  }

  std::cout << GetDuration() << '\t' << __func__ << std::endl;
}

void test_string_append(const std::string& str)
{
  GetDuration();
  std::string buffer{};
  for (size_t i{}; i < 100000U; ++i)
  {
    buffer.append(str);
  }

  std::cout << GetDuration() << '\t' << __func__ << std::endl;
}

void test_string_append_prealloc(const std::string& str)
{
  GetDuration();
  std::string buffer{};
  buffer.reserve(800032);
  for (size_t i{}; i < 100000U; ++i)
  {
    buffer.append(str);
  }

  std::cout << GetDuration() << '\t' << __func__ << std::endl;
}

int main()
{
  const std::string part{ "abcdefgh" };
  test_strcat(part.c_str());
  test_CpyCat(part.c_str());
  test_string_append(part);
  test_string_append_prealloc(part);
}
Auf meinem ollen Netbook macht das ...

Mit VS 2019:
1587570612336.png



Mit MinGW (gcc 9.2.0):
1587570733496.png
 

asc

Neues Mitglied
devCommunity-Experte
AMD Ryzen 5 2600x
Ubuntu 18.04.4 LTS (WSL)

Code:
> g++ -O2 gstrtest.cpp
> ./a.out
19.6999 test_strcat
0.0011542       test_CpyCat
0.0010108       test_string_append
0.0003906       test_string_append_prealloc

> g++ -O3 gstrtest.cpp
> ./a.out
19.6518 test_strcat
0.0008585       test_CpyCat
0.001014        test_string_append
0.0003924       test_string_append_prealloc

> clang++ -O2 gstrtest.cpp
> ./a.out
0.921466        test_strcat
0.0012218       test_CpyCat
0.0010705       test_string_append
0.0003994       test_string_append_prealloc

> clang++ -O3 gstrtest.cpp
> ./a.out
0.916459        test_strcat
0.0008248       test_CpyCat
0.0010611       test_string_append
0.0004034       test_string_append_prealloc
std::string mit genug Kapazität scheint recht aggressiv optimiert zu werden.
Was CLANG bei test_strcat macht weiß ich nicht, aber scheinbar wirkt es (19s <-> 1s) :D
 
Zuletzt bearbeitet:

german

Aktives Mitglied
devCommunity-Experte
Sehr cool :D
Der Unterschied zwischen strcat und selbst gerollt ist ausreichend erklärt. Enorme Unterschiede zwischen den einzelnen strcat Implementationen hab ich auch gesehen. Die Vermutung liegt nahe, dass das mit der Art und Weise zusammenhängt wie die Suche der Nullterminierung optimiert ist (analog strlen). Womöglich wie viele Bytes auf einem Ritt verglichen bzw. kopiert werden (Registerbreite).
Zu append(): Dort ist ganz klar zu sehen was wiederholte Speicherallokationen und das mögliche Umkopieren in einen anderen Speicherbereich ausmachen. Ziemlich eindeutig ist also - jede Vermutung über die erwartete Stringlänge (selbst eine falsche) ist besser als gar keine. Sich bei längeren zu erwartenden Strings schon mal per reserve() Speicher zu holen macht einfach Sinn, wenn man damit die Zeit nahezu dritteln kann.
Der Unterschied zwischen test_CpyCat() und test_string_append_prealloc() hat IMHO zwei Einflussgrößen:
- Was macht der Compiler (und am Ende auch die CPU) aus dem char-weisen Kopieren in der Schleife.
- Wie ist append() optimiert, wie viele Bytes werden am Stück kopiert.
 
Zuletzt bearbeitet:
Oben Unten