Algo Optimierung

Hallo,
die folgende Funktion komprimiert einen String per LZSS (LZ77) Algorithmus:
Dabei wird ein konstant großer Textbuffer hinter dem Cursor hinterher geschoben ("Sliding Window" das sich zwischen sw_start und sw_end befindet).
Sollte nun vor dem Cursor ein 3 oder mehr Bytes langer Text erscheinen, den es in dem Buffer bereits gibt, kann dieser Text durch einen zwei Byte Verweis auf den Buffer (Offset+Länge) abgekürzt werden.

Damit der Dekompressor weiß, ob er einfach das Zeichen ausgeben soll, oder es sich um ein 2 Byte Codeword handelt verwende ich FlagBytes, die jeweils für die nächten 8 Einheiten 8 (Bit) Flags speichern, die zeigen, ob es ein Literal oder ein Codeword ist.

Hoffentlich ist es nun verständlich, was der Algo macht. Mein Problem: Er ist viel zu langsam. Ich habe gehört, das liegt primär an der Größe des Buffers, da die lineare Stringsuche zu lange dauert und in der Regel andere Suchmethoden verwendet werden. Jedoch braucht String.find() selbst bei einem sehr großen Fenster weniger als 1 ms um ein Match zu finden. Hoffentlich könnt ihr mir ein paar Optimierungen für den Algo vorschlagen:

while (sw_end < len) {
        // Start des SW feststellen
        if (sw_end <= maxoffset) sw_start = 0; else sw_start = sw_end - maxoffset;

        // Größtes Match suchen
        matchsize = 3;
        matchpos  = 0;
        currmatch = text.substr(sw_end,matchsize);
        matchpos  = text.substr(sw_start, sw_end-sw_start).find( currmatch );
        while (matchpos!=string::npos && matchsize < maxlen + 2 && matchsize + sw_end < len) {
            ++matchsize;
            goodpos   = matchpos;
            currmatch = text.substr(sw_end,matchsize);
            matchpos  = text.substr(sw_start, sw_end-sw_start).find( currmatch );
        }

        // Mind. 3 Byte Match? -> Codeword schreiben
        if ( (--matchsize) > 2 ) {

            // Offset & Länge des Matches ermitteln
            matchoffset = goodpos - sw_start;

            // Flag 1 für Codeword schreiben
            result[flagpos] |= (1 << currflag);

            // Codeword hinzufügen (matchsize = matchsize + 2, denn 0-2 werden nie genutzt)
            codeword  = (matchoffset << 3) | (matchsize - 2);
            result   += tobytes(codeword,2);

            // Fenster weiterschieben
            sw_end += matchsize;

        // Ansonsten -> Literal schreiben
        } else {
            result += text[sw_end];
            ++sw_end;
        }

        // Ist aktuelles Flag-Byte voll?
        if ( (++currflag) > 7 && sw_end < len ) {
            currflag = 0;
            result += flagbyte;
            flagpos = result.length() - 1;
        } 

    } // Ende: Hauptschleife

Vielen Dank,
Neo

Jester

Hallo!

Ich denke schon, daß man da einiges verbessern kann. Insbesondere das Matching sieht recht ineffizient aus. Hab's aber nicht allzu genau angeschaut.

Mein Vorschlag wäre:

Brich die Funktion mal auf in mehrere Unterfunktionen. Zum Beispiel:

findBestMatch(...);
encode(...);
writeFlagByte(...);

etc.

Dann wird die Codestruktur klarer und Du kannst mit dem Profiler mal drüber gehen und nachschaun an welcher Stelle wirklich Zeit verbraten wird.
Danach dürfte es auch leichter sein so eine kleine Teilfunktion zu verbessern, als dieses komplette Monstrum mit all seinen Variablen. Da muß man ja immer Angst haben, daß man was kaputt macht wenn ne Variable anfaßt.

Baus doch mal um und poste die neue Version, dann fällt sicher einigen von uns was ein.

MfG Jester

Weil sonst nix konkretes kam, kann ich nur empfehlen bei der Suche und den Vergleichen das erzeugen von Strings zu vermeiden. Es werden hier ja ständig suchfenstergrosse temporäre Strings angelegt, das ist nicht billig, erst recht nicht, wenn das mal in einer Mutlithreaded-Umgebung eingesetzt werden soll, weil da halt dauernd Speicher besorgt und freigegeben wird. Also evtl. lieber auf was eigenes setzen, um in Teilbereichen nach Teil-Strings zu suchen, statt die die Teilbereiche auszuschneiden. Natürlich gibt es noch Tricks beim suchen, aber wenn man die Zahl der Stringerzeugungen reduziert (oder ganz abbaut) sollte das schon flotter werden.

Hi,
danke für die Tipps.

Wie schon erwähnt habe ich mal die find() Zeit gestoppt und jedes mal weniger als 1 ms gemessen, selbst bei sehr großen Fenstern. Also würdest du generell zu einer anderen Suchmethode (Suffix Search, Bin Tree) raten? Falls, könntest du kurz erläutern was dir da vorschwebt, denn ich ich kann mir nicht vorstellen einen binären Baum auf Strings anzuwenden.

Gruß,
Neo

Hutzli

Ich habe gerade eine langweilige sechsstündige Bahnfahrt hinter mir, und da hab ich mir zum Zeitvertreib mal den Code angesehen.

Generell hab ich nicht versucht den Code neu zu schreiben, denn dann kann man den Unterschied ja so schlecht vergleichen, daher hier nur ein paar kleine Änderungen. Generell sollte man sowas aber nur mittels Profiler-Einsatz optimieren, die Erfahrung zeigt, das dies viel zielgerichteter ist als die Methode des scharfen Blicks. Aber das sei zur Übung überlassen.

Aus:

while (matchpos!=string::npos && matchsize < maxlen + 2 && matchsize + sw_end < len) {
            ++matchsize;
            goodpos   = matchpos;
            currmatch = text.substr(sw_end,matchsize);
            matchpos  = text.substr(sw_start, sw_end-sw_start).find( currmatch );
        }

wird zum Beispiel:

while (matchpos!=std::string::npos && matchsize < maxlen + 2 && matchsize + sw_end < len) {
            ++matchsize;
            goodpos   = matchpos;
            currmatch = text.substr(sw_end,matchsize);
            matchpos  = text.substr(sw_start+matchpos, sw_end-sw_start-matchpos).find( currmatch );
            if( matchpos!=std::string::npos )
                matchpos += goodpos;
        }

Grund: Es lohnt nicht, den Anfang nochmal zu durchsuchen, die längere Folge kann ja nur ab dem letzten Treffer auftreten.

Das hat in einem schnellen Test bei optimiertem Code auf dem VC++ Faktor 2.6 gebracht.

Dann die vielen erzeutgen substrings, das sollte gegen eine Suchfunktion ersetzt werden die im String statt in Substrings suchen kann. Leider gibt es da nix brauchbares, also muß man Hand anlegen.

Ich hab ja Zeit gehabt, daher hab ich drei Versuche gemacht, die auf anderen Plattformen nicht generell zum gleichen Ergebnis führen müssen, insbesondere ohne Optimierung ist das Zeitverhalten deutlich anders, das sollte man aber nicht als Anhaltspunkt nehmen.

Erst der faule Ansatz (der unter dem VC++ nicht gut wirkt):

std::string::size_type findSubstring( const std::string& text, std::string::size_type txtoff, std::string::size_type txtlen, std::string::size_type searchoff, std::string::size_type searchlen )
{
	const char* txt = text.data()+txtoff;
	const char* srch = text.data()+searchoff;
	const char* end = txt+txtlen-searchlen;
	while( txt < end && memcmp( txt, srch, searchlen ) ) txt++;
	return txt < end ? txt - (text.data()+txtoff) : std::string::npos;
}

Aus der Suche wird dann:

matchsize = 3;
        matchpos = findSubstring( text, sw_start, sw_end-sw_start, sw_end, matchsize );
        while (matchpos!=std::string::npos && matchsize < maxlen + 2 && matchsize + sw_end < len) {
            ++matchsize;
            goodpos  = matchpos;
            matchpos = findSubstring( text, matchpos+sw_start, sw_end-sw_start-matchpos, sw_end, matchsize );
            if( matchpos!=std::string::npos )
                matchpos += goodpos;
        }

Dann der Ansatz von Hand, der deutlich besser aussah, keine Ahnung was memcmp in der ersten Version so bremst, müsste man in die Implementation schauen, egal:

std::string::size_type findSubstring( const std::string& text, std::string::size_type txtoff, std::string::size_type txtlen, std::string::size_type searchoff, std::string::size_type searchlen )
{
	const char* txt = text.data()+txtoff;
	const char* srch = text.data()+searchoff;
	const char* end = txt+txtlen-searchlen;
	while( txt < end )
	{
		const char *t = txt, *s = srch;
		for( size_t i = searchlen; i && *t++ == *s++; --i );
		if( i ) txt++; else break;
	}
	return txt < end ? txt - (text.data()+txtoff) : std::string::npos;
}

Schon besser, Faktor 4.6 gegenüber dem Original. Aber man kann noch einen drauflegen (zum Verständnis ein wenig nach Boyer-Moore) suchen:

std::string::size_type findSubstring( std::string::const_iterator  windowBegin, std::string::const_iterator windowEnd, std::string::size_type matchLen )
{
    if( matchLen>windowEnd-windowBegin )
        return std::string::npos;

    std::string::size_type charsToSkip[256];
    std::string::const_iterator patternIter, patternEnd = windowEnd + matchLen;
    std::string::const_iterator textIter = windowBegin + matchLen;

    for( unsigned idx = 0; idx < 256; ++idx )  charsToSkip[idx] = patternEnd - windowEnd + 1;
    for( patternIter = windowEnd; patternIter < patternEnd; ++patternIter ) charsToSkip[unsigned char(*patternIter)] = patternEnd-patternIter;

    patternIter = patternEnd;

    while( patternIter > windowEnd )
    {
        while( *--textIter != *--patternIter )
        {
            textIter += std::max(std::string::size_type(patternEnd - patternIter)+1, charsToSkip[unsigned char(*textIter)]);
            if( textIter > windowEnd ) return std::string::npos;
            patternIter = patternEnd;
        }
    }
    return textIter - windowBegin;
}

Dazu braucht die Suchschleife nochmal eine Anpassung:

matchsize = 3;
        matchpos = findSubstring( text.begin()+sw_start, text.begin()+sw_end, matchsize );
        while (matchpos!=std::string::npos && matchsize < maxlen + 2 && matchsize + sw_end < len) {
            ++matchsize;
            goodpos  = matchpos;
            matchpos = findSubstring( text.begin()+sw_start+matchpos, text.begin()+sw_end, matchsize );
            if( matchpos!=std::string::npos )
                matchpos += goodpos;
        }

So, jetzt sind wir bei einem Faktor>10 gegenüber dem Original, das soll es erstmal gewesen sein.

Wichtig: Die Beschleunigungesangaben basieren auf dem Lauf über einen längeren Text (aus Wikipedia) und auf dem Optimierten Code aus dem Microsoft Visual C++ Toolkit 2003. Andere Compiler mit anderen Optimizern erreichen andere Ergebnisse und natürlich beeinflusst auch die Plattform das Ergebnis, in diesem Fall liefen alle Tests auf einem Pentium-M, also ymmv

Zudem ist das natürlich nicht das Ende der Fahnenstange, aber das Ende meines Akkus. Und Du willst ja auch noch ein bisserl Spaß haben.

Hutzli

Achja, nochwas: Irgendwie glaube ich so wäre es richtiger:

// Offset & Länge des Matches ermitteln
            matchoffset = goodpos; // <---- kein '- sw_start' mehr

Denn die Positionen die der find() auf den substr() liefert, sind ja schon ab sw_start.