for-Optimierung

otze

Warum Aua? Dieses Konstrukt ist so unnnatürlich, dass ich erstmal analysiere, ob es überhaupt einen Sinn hat, rückwärts zu iterieren. Das kostet mich im Zweifelsfall, je nach Codekenntnis, 10-30 Minuten, bevor ich daran weiter arbeiten kann. Das ist genauso, wie bei Leuten, die ihre Laufvariablen vor dem Loop deklarieren wo ich den ganzen Folgecode durchsuche, ob der Wert der Variablen noch irgendwo benutzt wird.

An so ein Konstrukt gehört ein Kommentar. Mit Begründung(also Benchmark).

Und zu dem Zweiten Teil: das hast du natürlich getestet? Ich habe da nicht mehr so viel Vertrauen in meine Compiler.

cooky451

otze schrieb:

Warum Aua? Dieses Konstrukt ist so unnnatürlich,

What? Ich benutze das in etwa 10 mal öfter als das "normale" Konstrukt, und offen gesagt finde ich es wesentlich leichter zu lesen. Ich bevorzuge es auch, wenn Performance garkeine Rolle spielt.

otze schrieb:

dass ich erstmal analysiere, ob es überhaupt einen Sinn hat, rückwärts zu iterieren. Das kostet mich im Zweifelsfall, je nach Codekenntnis, 10-30 Minuten, bevor ich daran weiter arbeiten kann.

Wie lang sind denn deine Schleifen, dass man da 10 Minuten dran lesen kann?

otze schrieb:

Das ist genauso, wie bei Leuten, die ihre Laufvariablen vor dem Loop deklarieren wo ich den ganzen Folgecode durchsuche, ob der Wert der Variablen noch irgendwo benutzt wird.

Wenn das ernsthaft ein relevanter Zeitfaktor ist kann man den Code eh gleich in die Tonne kloppen, weil der Gültigkeitsbereich offensichtlich zu groß ist.

otze schrieb:

An so ein Konstrukt gehört ein Kommentar. Mit Begründung(also Benchmark).

Ich denke sowas ist Allgemeinwissen, ich schreib' ja auch nicht bei jedem std::transform daneben dass die Reihenfolge nicht garantiert ist.

otze schrieb:

Und zu dem Zweiten Teil: das hast du natürlich getestet? Ich habe da nicht mehr so viel Vertrauen in meine Compiler.

Klar habe ich das getestet.

pumuckl

cooky451 schrieb:

otze schrieb:

Warum Aua? Dieses Konstrukt ist so unnnatürlich,

What? Ich benutze das in etwa 10 mal öfter als das "normale" Konstrukt, und offen gesagt finde ich es wesentlich leichter zu lesen. Ich bevorzuge es auch, wenn Performance garkeine Rolle spielt.

Das ist relativ untypisch. Was sagen deine Kollegen dazu, für wie lesbar halten sie den Code? Wenn man nicht gerade für sich selbst entwickelt ist Lesbarkeit das oberste Gebot - und da spielen Konventionen eine wichtige Rolle, denen dein Konstrukt nicht so recht entspricht.

cooky451 schrieb:

otze schrieb:

dass ich erstmal analysiere, ob es überhaupt einen Sinn hat, rückwärts zu iterieren. Das kostet mich im Zweifelsfall, je nach Codekenntnis, 10-30 Minuten, bevor ich daran weiter arbeiten kann.

Wie lang sind denn deine Schleifen, dass man da 10 Minuten dran lesen kann?

Man weiß beim unkommentieren Code nicht, ob dieses Konstrukt eine (i.d.R. nutzlose) Performanceoptimierung ist, oder ob die Iteration rückwärts einen semantischen Zweck erfüllt.

cooky451

pumuckl schrieb:

Das ist relativ untypisch. Was sagen deine Kollegen dazu, für wie lesbar halten sie den Code? Wenn man nicht gerade für sich selbst entwickelt ist Lesbarkeit das oberste Gebot - und da spielen Konventionen eine wichtige Rolle, denen dein Konstrukt nicht so recht entspricht.

Nicht, dass ich Arbeitskollegen hätte als fast Student, aber die Leute, die ich kenne, hätten damit keine Probleme. Ich verstehe offen gesagt auch nicht so ganz, was daran schwer zu lesen sein soll. Es ist eine Zeile Code, auch wenn ich die noch nie gesehen habe, kann ich in etwa so schnell erfassen was die macht wie ich lesen kann?

qwertfdassffds schrieb:

Man weiß beim unkommentieren Code nicht, ob dieses Konstrukt eine (i.d.R. nutzlose) Performanceoptimierung ist, oder ob die Iteration rückwärts einen semantischen Zweck erfüllt.

Das ist kein Argument dafür per "default" die langsamere Variante zu wählen. Ich weiß bei unkommentiertem Code nicht, ob das vorwärts Iterieren einen semantischen Zweck erfüllt, oder ob man das optimieren kann. Deshalb schreibe ich überall da, wo es einen Zweck erfüllt, ein Kommentar, und überall wo es egal ist, eben halt keinen. Würde anders ja auch wenig Sinn machen.

pumuckl

cooky451 schrieb:

Es ist eine Zeile Code, auch wenn ich die noch nie gesehen habe, kann ich in etwa so schnell erfassen was die macht wie ich lesen kann?

Nein, eben nicht. Stell dir vor, du bist im Straßenverkehr. Du siehst ein quadratisches, türkisfarbenes Schild an einer Kreuzung, auf dem fett STOP steht. Du weißt, nachdem du es dir angeschaut hast und den Text gelesen hast, was gemeint ist. Wunderst dich aber, warum es nicht das übliche, rote Stop-Schild ist, bei dem du nichtmal mehr richtig liest, sondern in einem Sekundenbruchteil erfasst, welches Schild du vor dir hast (selbst, wenn es auf arabisch ist).

Das gleiche passiert beim Lesen des Quelltextes. Über das typische for(int i = 0; bla bla...) huscht jeder kurz drüber, ohne die Konzentration auf die wesentlichen Aspekte des Quelltextes zu ignorieren. Bei deinem Rückwärtskonstrukt muss man erstmal anhalten und genau nachlesen, was gemeint ist. Natürlich geht das ziemlich fix, trotzdem stört es den Lesefluss, vor Allem wenn man sich fragt, wo der Haken ist, und warum du nicht die übliche Version genommen hast. Man analysiert das Ganze nochmal und stellt fest, dass es keinen unterschied gibt, trotzdem ist es ein Stolperstein. Man verliert das Wesentliche aus dem Fokus, völlig unnötigerweise. Code, der mit solchen unüblichen Konstrukten durchsetzt ist, liest sich genauso holperig wie ein text, der in einem ungewöhnlichen, unflüssigen Text geschrieben wurde. Man kanns lesen, es ist aber sicher keine Freude.

Eisflamme

Nun, der Standard ist eben das vorwärts iterieren. Das hat man gelernt, das nutzt man im Regelfall und das ist man auch gewohnt in fremden Codes zu sehen. Findest Du es nicht nachvollziehbar, dass jemand in Deinen Code schaut und sich deswegen überlegt (wieso HIER rückwärts, wieso bricht er mit dem, was man normalerweise macht?). Auch in einer kurzen Schleife mit einer Funktion, die über eine Bildschirmseite gibt, kann das natürlich je nach Aufrufstack-Tiefe und iteriertem Objekt ein komplexer Code sein, über den man dann doch Mal genau nachdenkt.

Auch wenn Du den Code ohne Performance-Gewinn vorziehen würdest: die meisten schreiben es nicht so, daher ist es erstmal unüblich und somit verwirrender. Und Verwirrung steht guter Lesbarkeit quasi gegenüber.

Edit: Bis hier hat das pumuckl viel cooler erklärt.

Und dann würde mich Dein Benchmark-Programm interessieren, das zeigt, dass die Variante performanter ist. Hast Du die zufällig gerade zur Hand?

cooky451

Hmja, aber wenn man's 3 mal gelesen hat ist es genau so drin wie die andere Variante. Und selbst wenn man völlig verwirrt ist und aus dem Konzept kommt verliert man so höchstens 3 mal eine Minute, das ist es definitiv wert.

@Eisflamme
Ja, er wäre beim ersten mal verwirrt. Vielleicht beim zweiten mal. Danach ist es aber egal. Ich bin andererseits offen gesagt eher geschockt, dass das nicht alle so machen. Ich muss immer schon schmunzeln wenn ich die andere Variante sehe wo es doch offensichtlich ist, dass es auch rückwärts ginge.

Ich hab' mal nen relativ aufwendigen Benchmark geschrieben mit Matrizen etc., den finde ich allerdings gerade nicht. Aber ich hab hier mal kurz was zusammengefrickelt. (Hoffentlich ohne Fehler.)

#include <chrono>
#include <vector>
#include <iostream>

template <typename Clock = std::chrono::steady_clock>
class stopwatch
{
	typename Clock::time_point last_;

public:
	stopwatch()
		: last_(Clock::now())
	{}

	void reset()
	{
		*this = stopwatch();
	}

	typename Clock::duration elapsed() const
	{
		return Clock::now() - last_;
	}

	typename Clock::duration tick()
	{
		auto now = Clock::now();
		auto elapsed = now - last_;
		last_ = now;
		return elapsed;
	}
};

template <typename T, typename Rep, typename Period>
T duration_cast(const std::chrono::duration<Rep, Period>& duration)
{
	return duration.count() * static_cast<T>(Period::num) / static_cast<T>(Period::den);
}

void foo(std::vector<char>& v)
{
	stopwatch<> timer;
	for (int i = v.size(); i-- != 0; )
		v[i] = 77;
	std::cout << "Foo time: " << duration_cast<float>(timer.elapsed()) << '\n';
}

void bar(std::vector<char>& v)
{
	stopwatch<> timer;
	for (int i = 0; i != v.size(); ++i)
		v[i] = 44;
	std::cout << "Bar time: " << duration_cast<float>(timer.elapsed()) << '\n';
}

int main()
{
	std::size_t n;
	std::cin >> n;
	std::vector<char> v(n * 1024 * 1024);
	foo(v);
	bar(v);
}

Am besten ein paar mal hintereinander laufen lassen, damit der RAM vorbereitet ist. n zwischen 512 und 1024 sollte gute Ergebnisse bringen.

Michael E.

cooky451 schrieb:

for (auto i = foo(); i-- != 0; )

Wenn foo einen vorzeichenlosen Typen zurückgibt, hast du eine Endlosschleife. So viel zum Thema "gut lesbar".

Edit: Gilt natürlich nur, wenn du deinen Code erst mal auf das anpasst, was der OP geschrieben hat, nämlich eine Iteration von 0 bis foo() -1 und nicht wie bei dir eine Iteration von 1 bis foo(). Also gleich zwei Fehler in "so einem einfachen Code".

cooky451

Michael E. schrieb:

cooky451 schrieb:
for (auto i = foo(); i-- != 0; )
Wenn foo einen vorzeichenlosen Typen zurückgibt, hast du eine Endlosschleife. So viel zum Thema "gut lesbar".

Falsch. Wird der zweite Satz dadurch richtiger?

Michael E. schrieb:

cooky451 schrieb:
for (auto i = foo(); i-- != 0; )
Wenn foo einen vorzeichenlosen Typen zurückgibt, hast du eine Endlosschleife. So viel zum Thema "gut lesbar".

Dein Kommentar zeigt wirklich Mängel in der Lesbarkeit auf, aber anders als Du denkst...

Michael E.

cooky451 schrieb:

Falsch. Wird der zweite Satz dadurch richtiger?

Siehe Edit:

Edit: Gilt natürlich nur, wenn du deinen Code erst mal auf das anpasst, was der OP geschrieben hat, nämlich eine Iteration von 0 bis foo() -1 und nicht wie bei dir eine Iteration von 1 bis foo(). Also gleich zwei Fehler in "so einem einfachen Code".

cooky451

Michael E. schrieb:

Edit: Gilt natürlich nur, wenn du deinen Code erst mal auf das anpasst, was der OP geschrieben hat, nämlich eine Iteration von 0 bis foo() -1 und nicht wie bei dir eine Iteration von 1 bis foo(). Also gleich zwei Fehler in "so einem einfachen Code".

Langsam wird's lustig. Aber dafür verstehe ich etwas mehr was pumuckl meint.

otze

cooky451 schrieb:

[..] Wie lang sind denn deine Schleifen, dass man da 10 Minuten dran lesen kann?
[...] Wenn das ernsthaft ein relevanter Zeitfaktor ist kann man den Code eh gleich in die Tonne kloppen, weil der Gültigkeitsbereich offensichtlich zu groß ist.

Ich arbeite hier mit zum Teil 15 Jahre alten open source code der von Wissenschaftlern und Studenten geschrieben wurde. Was meinst du, ist die durchschnittliche Codequalität? Natürlich wandert der Code in die Tonne, den neu zu schreiben ist gerade mein Job. Aber dafür muss ich erstmal verstehen was er macht. Und ich habe das Gefühl, dass es so kleine Abweichungen von der Konvention sind, die am meisten Zeit fressen.

Es gibt ja noch eine andere Konvention, die in einer zeitrelevanten Schleife eingesetzt werden kann:

std::size_t end = funct();
for(std::size_t i = 0; i != end; ++i){...}

kostet mich im durchschnitt 2 Sekunden zu verstehen. wenn ich nun das mit deiner Variante vergleiche stellt sich natürlich wiederholt die Frage, ob da nicht doch noch irgendwas passiert, immerhin hättest du die Schlife auch wie oben schreiben können.

//edit meine Tastatur liegt im persönlichen Krieg mit dem "e"

Michael E.

cooky451 schrieb:

Langsam wird's lustig. Aber dafür verstehe ich etwas mehr was pumuckl meint.

Was ist so lustig? Ein typischer realer Ersatz von foo wäre vector::size(). Was passiert hier?

#include <vector>
#include <iostream>
using namespace std;

int main()
{
        vector<int> foo(2, 0);
        for(auto i = foo.size(); i >= 0; --i)
        {
                cout << i << endl;
                if(i > 1000) break;
        }
}

Ausgabe:

cooky451

Michael E. schrieb:

Was ist so lustig? Ein typischer realer Ersatz von foo wäre vector::size(). Was passiert hier?

Wenn du noch ein bisschen überlegst und dir den Code anguckst den ich gepostet habe, wirst du verstehen warum das lustig ist.
Tipp: Die von dir geschriebene Schleife ist zu meiner grundverschieden.

@otze
Also ich weis nicht. Mir sind die ganzen Varianten alle gleich geläufig, und offen gesagt ist mir völlig egal was davon man benutzt, ich kann das alles gleich gut lesen. Und per default die langsamere Variante zu benutzen leuchtet mir einfach nicht ein.

pumuckl

cooky451 schrieb:

Und selbst wenn man völlig verwirrt ist und aus dem Konzept kommt verliert man so höchstens 3 mal eine Minute, das ist es definitiv wert.

Ist es das? Zwei parallele Konventionen, für Schleifen, die nur dann semantisch gleichwertig sind, wenn die Reihenfolge keine Rolle spielt. Und als Ergebnis kriegen wir eine schnellere Ausführung des Schleifenkopfes (wie viel schneller eigentlich?), dessen Performanceimpakt vielleicht in einem von hundert Fällen wirklich was ausmacht (wenn überhaupt). Richtig auszahlen wird sich sowas vermutlich nur, wenn man Schleifen über riesige Bereiche hat (Numerik, Bildverarbeitung, ...?), deren Schleifenrümpfe nur sehr wenig Zeit benötigen (sonst fällt der Schleifenkopf prozentual nicht ins Gewicht und man sollte eher an der Anzahl der Iterationen schrauben). Vielleicht abgesehen von besagten speziellen Bereichen, wo solche Schleifen häufig vorkomemn, sehe ich da keinerlei Gewinn. Oder anders gesagt: Dem Ottonormalentwickler kommt nur höchst selten ein Fall unter, wo das Konstrukt eine messbare Optimierung darstellt. Das als allgemeinen Standard zu propagieren, der keines Kommentars bedarf, ist absurd. Wenn du in einem Projekt arbeitest, in dem ein großer Teil der Schleifen davon profitieren, dann machs im Projekt zum Standard. Ich bin zufälligerweise mit der Performanceoptimierung in einem Projekt vertraut, in dem viele Schleifen vorkommen, bei denen Reihenfolge keine Rolle spielt (aktuarieller Rechenkern für Lebensversicherungssoftware). Auch solche Schleifenoptimierungen sind dort schon erwägt worden, weil Performance hier wirklich eine Rolle spielt. Es bringt nur kein Ergebnis, das die Aufwände für eine entsprechende Umstellung rechtfertigen würde.

cooky451 schrieb:

Am besten ein paar mal hintereinander laufen lassen, damit der RAM vorbereitet ist. n zwischen 512 und 1024 sollte gute Ergebnisse bringen.

.. und wie sind die Ergebnisse?

Mein Benschmark liefert folgendes:

klassisch
5000000 0s
dekrementierend
5000000 0.0179735s
abgefahren
5000000 0.0135209s

interessanterweise ist selbst die Variante mit counting_iterator (s.u.) und Algorithmus geringfügig schneller als die dekrementierende Variante

und hier ist der Code dazu

int foo() { return 1000*(2000 + 8000); }

int main()
{
    using namespace std;
    Watch uhr;
    {
        cout << "klassisch" << endl;
        Watch::Stopper stopper( uhr );
        int counter = 0;
        int bla = foo();
        for( int i=0; i<bla; ++i )
            counter += i % 2? +i: -i;
        cout << counter << " " << uhr << endl;
    }
    {
        cout << "dekrementierend" << endl;
        Watch::Stopper stopper( uhr );
        int counter = 0;
        for( int i=foo(); i-- != 0; )
            counter += i % 2? +i: -i;
        cout << counter << " " << uhr << endl;
    }
    {
        cout << "abgefahren" << endl;
        Watch::Stopper stopper( uhr );
        int counter = 0;
        for_each( boost::counting_iterator< int >(0), boost::counting_iterator< int >(foo()), [&counter]( int i ) { counter += i % 2? +i: -i; } );
        cout << counter << " " << uhr << endl;
    }
}

Michael E.

cooky451 schrieb:

Michael E. schrieb:

Was ist so lustig? Ein typischer realer Ersatz von foo wäre vector::size(). Was passiert hier?

Wenn du noch ein bisschen überlegst und dir den Code anguckst den ich gepostet habe, wirst du verstehen warum das lustig ist.
Tipp: Die von dir geschriebene Schleife ist zu meiner grundverschieden.

Sorry, mein Fehler. Bin noch nicht wach. Ich dürfte aber meinen Punkt rübergebracht haben, dass ich deine Variante nicht so leserlich finde

cooky451

Michael E. schrieb:

Ich dürfte aber meinen Punkt rübergebracht haben, dass ich deine Variante nicht so leserlich finde

Ja, irgendwie war das die bestmögliche Argumentation.