History realisieren



  • hallo..

    Ich bin mit meinem Hex Editor so gut wie fertig. Ein mehr oder weniger großes Problem hab ich noch:
    Der User soll natürlich einzelne Bytes der geöffneten Datei ändern können, dies soll aber nicht gleich direkt in der Datei geschehen, sondern in so einer History mir Rückgängig Funktion. Soweit so gut. Ich habe mir folgenden Algorithmus dazu überlegt: Es wird eine CList und ein char Array mitgeführt, in dem Array wird immer hinten dran die letzte Änderung geschrieben und in der (sortieren) CList die BytePosition in der Datei + der Index im Array.
    Wenn ich jetzt an irgendeine Position in der Datei scrolle, wird durch eine binäre Suche aus der sortierten CList ein Wert herausgesucht, dessen BytePosition sich gerade im Bildschirmausschnitt befindet. Ab diesem Zeichen wird dann soweit vor und soweit nach hinten gelaufen bis die Positionen sich nicht mehr im Ausschnitt befinden und daher auch nicht mehr gezeichnet werden müssen.
    Shit.. ich hoffe das ist HALBWEGS verständlich .. 😞

    jedenfalls funktioniert das alles so.. ALLERDINGS VERDAMMT LANGSAM!
    Man muss sich vorstellen, dass sich in so einem Bildschirmausschnitt 600 Zeichen
    befinden können, die in einer Schleife einmal durchlaufen werden müssen...

    Welche Techniken gibt es da noch??
    Ich kann auch nicht einfach die datei kopieren und an einer kopie herumpfuschen und die änderungen dann zurückschreiben, weil ich damit rechnen muss, dass 4GB Dateien bearbeitet werden...

    bitte danke
    m.



  • Halte einfach eine Kopie der Datei im Speicher.

    Die liste mit den Änderungen ist ja nur bei einem 'Rückgängig Button' wichtig, und da änderst du einfach die Kopie (im Speicher)

    Ne, ich verstehe dein Problem nicht ganz.



  • Ja, bei einer 150 KB Datei wäre das ja ansich kein Problem aber sobald ich größere aufmache krieg ich doch sofort nen Heap Overflow-> wie gesagt, ich muss bis zu 4 GB aufmachen können...



  • bin mir auch nicht ganz sicher ob ich es verstanden hab, nagut
    falls ich es richtig verstanden hab würde ich es mal gaaaaanz simpel versuchen:
    (t.w. pseudo code - ich steh mit der c syntax etwas auf kriegsfuss)

    // komplett neue(primitive) historystruktur:
    ULONG * Done_Pos; //wo wurde was geändert
    byte  * Done_What; //etc.
    LONG  Done_Count;
    
    // zum anzeigen:
    ulong start_anzeige;
    ulong ende_anzeige;
    byte*ausgabebuffer;
    //start+endpunkt berechnen buffer reservieren+füllen etc.
    
    //änderungen reinsetzen:
    LONG i;
    for (i=0;i<Done_count;i++)
        if(Done_Pos[i]>=start_anzeige && Done_Pos[i]<ende_anzeige)
           ausgabebuffer[Done_Pos[i]-start_anzeige]=Done_What[i];
    //buffer darstellen
    

    selbst wenn du etliche tausend schritte in der history hast dürfte der vorgang
    nur wenige ms dauern

    (schätzwert 1/100 s bei 100.000 undo schritten und 1GHz rechner)



  • Es wird ja wohl niemand die komplette Datei auf einmal bearbeiten. Was hältst Du von einem Cache-System. Du holst Dir immer ne gute Portion an Daten um die Position wo Du gerade bist, die änderst Du dann auch gleich mit. Die Liste mit den Änderungen erzeugst Du nebenbei. Mit ca. 10 bis 20 Puffern à 10KB müßtest Du da eigentlich schon ziemlich weit kommen. Dann mußt Du die Updates wenigstens nicht so oft erzeugen.
    Außerdem kannst Du die History-Liste ja zweimal halten, einmal nach Zeit sortiert und einmal nach Position, das dürfte die Suche auch erheblich beschleunigen, einmal Position finden und dann abarbeiten ab dort.

    MfG Jester



  • also danke erstmal für deine antwort, Lui.. ich hab mich jetzt ein paar minuten mit deinem Codebeispiel auseinander gesetzt aber das kann ich bei mir so nicht anwenden..

    @Jester

    ja.. so ein Caching system wäre ansich nicht verkehrt, aber was ist wenn der user in einer großen Datei schön überall verteilt und kreuz und quer änderungen macht? Ich muss ja immer davon ausgehen dass irgend wo wirr in der Datei herumgepfuscht wird.
    Das binäre Suchen, ob sich ein verändertes Zeichen gerade im Sichtbarkeitsbereich befindet, ist der wenigste Aufwand. Bei echt großen Datein sind das so 20 Schleifendurchläufe..
    Das eigentlich langsame müsste erst kommen, nachdem das zeichen gefunden wurde:
    Nämlich das Zurücklaufen von der Position bis zum Anfang des Sichtbarkeitsbereiches und anschließend das Laufen bis zum Ende des SB.

    Außerdem kannst Du die History-Liste ja zweimal halten, einmal nach Zeit sortiert und einmal nach Position, das dürfte die Suche auch erheblich beschleunigen, einmal Position finden und dann abarbeiten ab dort.
    *
    Das mach ich im Prinzip. Ich habe ja die CList in der sich in der richtigen Reihenfolge verweise auf die zu ändernden daten befinden.
    Die Positionen speichere ich in einem extra Array daneben mit.

    das ganze ist irgend wie ein scheiß
    es muss noch einen anderen weg geben..



  • /dev/null schrieb:

    ja.. so ein Caching system wäre ansich nicht verkehrt, aber was ist wenn der user in einer großen Datei schön überall verteilt und kreuz und quer änderungen macht?

    Also, Du hast ne 4GB-Datei die editiert wird. Also kannst Du Dich davon verabschieden die ganze Datei im Speicher zu halten. Das heißt Du mußt irgendwelche Optimierungen durchführen die den wahrscheinlichen Fall betreffen. In den ungünstigen Fällen kann's dann halt schon mal länger dauern.
    Wie wahrscheinlich ist es, daß jemand mit nem Hex-Editor eine 4GB-Datei öffnet und anfängt kreuz und quer drin rumzuschreiben? Ziemlich unwahrscheinlich oder? Vielmehr wird man sich auf ein paar Stellen einschießen und dort relativ lokal Änderungen vornehmen. Das heißt ein Cache-System das eine Umgebung nach vorne und hinten um eine Position herum zwischenspeichert dürfte recht günstig sein.

    So, jetzt benutzt einer den Editor und schaut sich irgendeinen Ausschnitt der Datei an. Datei im Cache->garnichts passiert, Datei nicht im Cache->wird eingelagert. Das einlagern in den Cache ist natürlich etwas aufwendiger:

    Zunächst bestimmen wir eine Stelle, ab der wir in den Cache reinwollen. Es ist unter umständen sinnvoll ein Stück weiter vorne anzufangen, weil der Benutzer ein Stück zurück scrollen könnte. Dann bestimmmen wir mit einer binären Suche die Stelle in der History wo die Modifikation für's erste Zeichen steht. Da die Modifikationen alle nach Position sortiert sind laufen wir jetzt einfach Schritt für Schritt durch, bis wir alle Daten, die im Cache landen sollen verarbeitet haben.

    Die Cache-Architektur könntest Du je nach Dateigröße auch noch anpassen. Für eine kleine Datei könnte Vollassoziativ günstig sein, aber die Vergleiche werden für sehr viele Cache-Lines zu aufwendig, so daß ein satzassoziativer Cache sinnvoller wird. Wenn's wirklich schnell gehen muß könntest Du es auch mit Direct-Mapped versuchen, das erhöht allerdings die Chance von Cache-Misses drastisch.

    Wieviele Zeichen passen eigentlich auf den Bildschirm?
    Das wäre möglicherweise ne gute Maßeinheit für die Bildschirmgröße.
    Und einlagern in den Cache tust Du dann nur Stücke, die an vielfachen Adressen der Bildschirmgröße liegen (vom Dateianfang gerechnet), dann hast Du das Problem mit überlappenden Bildschirmseiten im Cache, die dann beide geupdated werden müßten nicht.

    MfG Jester



  • wow.. danke für diese mega antwort 🙂

    Ich ersetze gerade die CList durch eine selbst ausprogrammierte doppelt verkettete Liste um eine gewisse Performancesteigerung zu erlangen (bin schon gespannt ob das was bringt..)

    Wenn diese letzte Möglichkeit auch nichts bringt, werde ich wohl nicht um solche von Jester angesprochene Cache pages herum kommen 😞
    Das wird ziemlich Ar***kompliziert werden befürchte ich 😉

    Was Vollassoziativ, satzassoziativer und Direct-Mapped bedeutet muss ich mir erst ansehen.. 🙂

    @Jesters Frage: Wieviele Zeichen auf einer Seite angezeigt werden: ~600

    mfG
    matthias



  • /dev/null schrieb:

    Wieviele Zeichen auf einer Seite angezeigt werden: ~600

    Dann würde ich 2KB als Cache-Line nehmen. Dann hast Du gut Platz außenrum.

    Bei den verschiedenen Cache-Arten geht es im wesentlichen darum, wie man die Daten in den Cache reinschreibt und sie dort eben findet. Denn das muß ja möglichst schnell gehen.

    Zunächst mal holt man sich die Adresse des Bytes, also den Offset vom Beginn der Datei. Das sind in Deinem Fall wohl 32 Bit.
    Irgendwie müssen wir an soner Zahl jetzt sehen wo wir in den Cache gucken müssen. Zunächst lagern wir mal nur Zeichen in den Cache, die an einer durch 2048=2^11 teilbaren Adresse anliegen, das heißt die unteren 11 Bit dieser Adresse geben sozusagen nur den Offset an, wie weit wir in die Cache-Zeile schauen müssen. Dann haben wir noch 21 Bit übrig. Jetzt gibt's mehrere Möglichkeiten:

    Wir können einfach in jede Cache-Zeile für alle Adressen benutzen. Dann müssen wir für jede Cache-Zeile einen Vergleich opfern. Bei sagen wir mal 100 Cache-Zeilen, also 100 Vergleiche. Das ist wohl zu viel.
    Das heißt man speichert für jede Zeile noch den sogenannten Tag, diese 21 Bit eben mit und vergleicht die dann. Das kostet natürlich Zeit. Das wäre dann vollassoziativ.

    Eine andere Möglichkeit wäre DirectMapped: Man sag, okay ich habe 128 Cache-Lines, also geben die nächsten 7 Bit der Adresse (immer von hinten gerechnet) die Cache-Zeile an. Und nur die restlichen 21-7=14 Bit sind der Tag. Damit liegt kommt eine bestimmte Speicherstelle der Datei auch immer in eine feste Cache-Zeile und ist somit sehr leicht aufzuspüren. Allerdings kann es da halt passieren, das zwei ständig benötigte Dateistücke sich ständig gegenseitig verdrängen, weil sie in die gleiche Zeile müssen. Bei vollassoziativ (AV) wäre das kein Problem, jeder würde seine eigene Zeile kriegen.

    Des wegen gibt es noch eine Mischform: n-fach satzassoziativ.
    Wir Teilen unsere 128 Cache-Lines in 16 Blöcke ein, jede davon mit 8 Lines. Dann verwenden wir von den 21 Bit Adresse 4 für die Adressierung des Blocks und dort innerhalb arbeiten wir mit den restlichen 17 Bit vollassoziativ weiter. Dadurch brauchen wir aber nur 8 Vergleiche und das Problem, mit der Verdrängung wie bei DM-Caches haben wir auch nicht ganz so arg.

    Ich denke der satzassoziative ist für Dein Problem am besten geeignet. AV wird meist in Hardware gegossen (prozessor-cache und so), weil da die Vergleiche parallel ablaufen können.

    Wieso schreibst Du eigentlich die list selber? Was hältst Du von std::list?

    MfG Jester


Log in to reply