Automatisierte Performance Tests

[Tobse]

Hallo zusammen,

ich arbeite gerade an einem B-Tree Index für Datensätze in einem speziellen Format. Vorab: ja, ich weiss, müsste ich nicht machen, es gibt genug fertiges. Aber: es macht mir spaß mich damit zu beschäftigen; deshalb mache ich es. Es geht hier nicht um Code, der produktiv sein soll.

Der Index an sich funktioniert nun auch so, wie ich mir es vorstelle. Aber der Punkt ist: einen Index nutzt man der Performance wegen. Also denke ich, dass es Sinn macht, performance tests zu automatisieren.
Was das lesen aus dem Index angeht meine ich auch schon einen guten Ansatz gefunden zu haben: ich vergleiche die Performance vom lesen aus den Datensätzen für jeweils mit und ohne Index. Mithilfe des Index muss es dann um den Faktor XY schneller sein; dadurch sollte der Test auch auf unterschiedlichster Hardware aussagekräftig sein. (Den Faktor habe ich auf versch. Hardware gemessen und einen realistischen Wert in den Test geschrieben). Ist das eurer Meinung nach ein sinnvolles vorgehen?

Nun möchte ich aber testen, wie die Schreib-Performance ist. Erwartungsgemäß nimmt der Zeitaufwand pro geschriebenem Datensatz mit der Größe des Index exponentiell zu. Wie teste ich das am besten automatisiert? Meine Messwerte haben leider zu viel Varianz; wenn ich prüfen möchte ob meine gemessenen Schreib-Zeiten exponentiell zunehmen gibt es immer ein paar Ausreisser nach oben oder unten, welche den Test fehlschlagen lassen. Ich habe probiert, immer 50 oder 100 Schreibvorgänge als ganzes zu messen (also + overhead für die Schleife).

Grüße und schönes WE

 

[Thallius]

Eigentlich Must du beim Schreiben ja nur die Zeit messen die dein Index um hinzufügen braucht. Das Schreiben des eigentlichen Datensätzen sollte ja immer gleich schnell sein, da er „einfach hinten an die Tabelle angehängt wird“ oder beim updaten nur eine Spalte geändert wird. Das sollte aber immer gleich schnell oder langsam sein.

Also kannst du doch einfach eine Routine Schreiben, die zufällig x Einträge zu deinem Index hinzufügt und misst dann wie lange es bei den ersten 100, den zweiten 100 oder eben 1000 oder 10000 braucht. Wie groß deine Messmenge ist hängt ja hauptsächlich von der Auflösung des Timers ab.

Gruß

Claus

 

[Tobse]

Eigentlich Must du beim Schreiben ja nur die Zeit messen die dein Index um hinzufügen braucht. Das Schreiben des eigentlichen Datensätzen sollte ja immer gleich schnell sein, da er „einfach hinten an die Tabelle angehängt wird“ oder beim updaten nur eine Spalte geändert wird. Das sollte aber immer gleich schnell oder langsam sein.

Diese Variable habe ich eliminiert - die Tests finden 100% im RAM statt. Die Methode, welche den Datensatz dann tatsächlich in die Menge aller Datensätze einfügt, wird auch im Test nicht aufgerufen.

Also kannst du doch einfach eine Routine Schreiben, die zufällig x Einträge zu deinem Index hinzufügt und misst dann wie lange es bei den ersten 100, den zweiten 100 oder eben 1000 oder 10000 braucht. Wie groß deine Messmenge ist hängt ja hauptsächlich von der Auflösung des Timers ab.

Dachte ich eigentlich auch. Das ist mein Code bis jetzt:

// Kotlin code

// parameter
val batchSize = 50
val nBatches = 100
val nWarumpBatches = 20
// zählt die Datensätze
var nItem = 0
// speichert die gemessenen zeiten in mikrosekunden
val batchTimesMicros = mutableListOf<Double>()

// in java: for(int nBatch = 1;nBatch <= nBatches + nWarumpBatches;nBatch++)
for (nBatch in 1 .. nBatches + nWarumpBatches) {
    val batchStartedAt = System.nanoTime()
    for (nItemInBatch in 1 .. batchSize) {
        // hier wird ein zufälliger datensatz (eigentlich nur ein feld eines datensatzes) erstellt und dem index hinzugefügt
        // der zweite parameter ist die info, welche der index speichern soll; im realen szenario
        // wird diese zahl benutzt, um den tatsächlichen Datensatz wiederzufinden.
        // dieser aufruf in worten: an der stelle (parameter 2) ist ein datensatz, dessen feld den wert (parameter 1) hat.
        index.onInserted(Atom(randomString()), nItem++)
    }

    if (nBatch > nWarumpBatches) {
        batchTimesMicros.add(((System.nanoTime() - batchStartedAt) / 1000).toDouble())
    }
}

Das Problem ist aber, dass die gemessenen Datensätze zu stark variieren. Ich bekomme die Validierung nicht so hin, dass die Varianzen sinnvoll ignoriert werden. Stelle ich die erlaube Varianz so ein, dass Sie für die ersten Batches Sinn macht (+- 1 Millisekunde), ist die Varianz für die späteren Datensätze zu klein (schlägt z.B. fehl weil maximal 45ms pro Batch erlaubt, aber 48 gebraucht). Stelle ich die erlaubte Varianz so ein, dass die späteren Messwerte gelten, ist die Varianz für die ersten Datensätze lächerlich groß: Die übliche insert-dauer für die ersten 100 Datensätze war so bei 1-2 Millisekunden; mit der nötigen Varianz wären dann aber auch 18 Millisekunden erlaubt. Viel zu hoch.

 

[Tobse]

Habe mir die Daten nochmal angesehen... anscheinend war meine Prämisse falsch. Die Zeit zum Einfügen steigt linear zur Menge an bereits bestehenden Datensätzen im Index...

Hier 400 Messwerte (in Mikrosekunden) für das Hinzufügen von jeweils 50 Datensätzen:

 

[mrBrown]

Anstatt die Datensätze immer weiter zum gleichen hinzuzufügen, könnte man den Index mit n Einträgen erstellen, und diesem dann einmalig zB 100 hinzufügen und dafür die Zeit messen.
Das ganze dann einfach m-Mal wiederholen.
Die gemessenen Zeiten sind dann immer für hinzufügen von 100 in einen n-großen Index, das sollte ja vergleichbar sein?

Statt reiner Varianz würde ich dann eher die k kleinsten Werte betrachten (zB 0,95-Quantil), dann sind Ausreißer aufgrund von äußeren Bedingungen abgefangen.

 

[Tobse]

Die gemessenen Zeiten sind dann immer für hinzufügen von 100 in einen n-großen Index, das sollte ja vergleichbar sein?

Theoretisch; da ist 100 aber wahrscheinlich zu klein. Eigentlich sollte der B-Tree in allen Operationen (Lesen, Einfügen, Löschen) im Worst Case O(log n) Performance haben. Ich muss die Menge an Datensätzen auf jeden Fall so wählen, dass darin das O(log n) auch erkennbar ist.

Statt reiner Varianz würde ich dann eher die k kleinsten Werte betrachten (zB 0,95-Quantil), dann sind Ausreißer aufgrund von äußeren Bedingungen abgefangen.

Das ist eine gute Idee! Probiere gleich mal, ob mein Test damit reproduzierbarer wird.

 

[mrBrown]

Theoretisch; da ist 100 aber wahrscheinlich zu klein. Eigentlich sollte der B-Tree in allen Operationen (Lesen, Einfügen, Löschen) im Worst Case O(log n) Performance haben. Ich muss die Menge an Datensätzen auf jeden Fall so wählen, dass darin das O(log n) auch erkennbar ist.

Das ganze natürlich für unterschiedlich große n

Bspw 100 einfügen bei Größe 0, 100, 10000. Dann hat man 3 Samples, die man vergleichen kann.
Die 100 ist aus den Fingern gesaugt, die dienen ja nur dazu, einen Durchschnittswert für das entsprechende n zu bekommen. Man könnte auch 1 nehmen, und dann das ganze einfach öfter laufen lassen.

 

[Tobse]

Bspw 100 einfügen bei Größe 0, 100, 10000. Dann hat man 3 Samples, die man vergleichen kann.

Und wie vergleiche ich die dann? Absolute Werte möchte ich ja nicht nehmen, damit ich den Test auf verschiedener Hardware ausführen kann.

 

[mrBrown]

die kannst du relativ miteinander vergleichen, so wie du es doch jetzt auch schon machst?

Ist aber eig überflüssig, die Ausreißer rausnehmen sollte reichen

 

[Tobse]

die kannst du relativ miteinander vergleichen, so wie du es doch jetzt auch schon machst?

Ah, verstehe. Also wenn ich die Ausreisser filtere (habe sowohl dein 0,95-Quantil als auch 2-Sigma Standardabweichung probiert), klappt es ganz gut. Der Test schlägt auf schwächeren Maschinen bei der ersten Ausführung noch fehl, bei weiteren kappt es dann aber.

Den Grund für die Lineare Laufzeit habe ich nun auch gefunden. Nach einer Änderung kann ich jetzt mit O(1) in den Index schreiben - das macht auch den Performance-Test stabiler.