Prestatiewinst much?!

Door Bubbles op dinsdag 3 april 2012 10:11 - Reacties (12)
Categorie: Programming, Views: 3.718

Al programmerend loop je soms tegen interessante problemen aan. Zo heb ik momenteel wat werk waarbij ik zowel wat nieuwe systemen moet maken, als oude systemen (ook wel bekend als Legacy code) moet vervangen . Leuk om zo eens in de keuken van een bedrijf te kunnen kijken; daar valt namelijk een hoop van te leren.

Zo ben ik onder andere bezig met het integreren van 2 losse systemen naar 1 geheel en daarbij gelijk een overhaul van de code uit te voeren. Het oude systeem liep, vanwege prestatieproblemen op de database, slechts één keer per dag. Of beter gezegd: per nacht. Het verzoek was om die limitatie eraf te halen, zodat er vaker updates gedaan konden worden; ook tijdens werktijd.

Wat er uiteindelijk gedaan moest worden was een XML bestand inlezen, de nodes die daarin staan (een stuk of 25.000) vergelijken met de objecten in de database (verspreid over 7 verschillende types), aanpassen waar nodig (toevoegen, wijzigen, of, als ze niet meer in het XML-bestand staan, verwijderen) en de gewijzigde nodes in XML bestand opslaan, omdat die nodig zijn voor een derde systeem.

Aangezien 25.000 keer gaan lopen babbelen met de database in zeer korte tijd al heel gauw een niet-meer-zo-zeer-korte-tijd wordt, werd er voor gekozen om de inhoud van de database in te lezen in wat collections in de code: de database wordt maar 1 keer intensief benaderd en alle objecten zitten dan in het geheugen, wat uiteraard een stuk sneller benaderbaar is dan harddisk- of netwerk-I/O. Voor het gemak had ik al die objecten in een generic list (per type) gefrot. Gaat lekker snel. Al was het maar omdat NHibernate/C# een .ToList() functie heeft als de volledige inhoud van een database tabel wordt opgehaald.

Behalve dan als je per node die je inleest, nadat je hebt uitgezocht wat voor een type het is, die moet opzoeken in je List of die al in de database zat, zo ja, nog eens moet opzoeken in een schaduw-List die je bijhoudt voor het verwijderen van objecten in de database en na afloop van het doorlopen van de XML ook nog eens door je volledige database-List moet gaan om te kijken welke objecten niet meer in het XML-bestand voorkomen (en daarvoor diende de schaduw-List), zodat je die uit de database kan verwijderen. Het werkt, maar je krijgt de indruk dat het toch sneller zou moeten kunnen: ruim een minuut doorlooptijd is toch best stevig voor iets wat volledig in het geheugen zit.

Enter the Dictionary (of HashMap, voor de Java-programmeurs onder ons): een key/value pair wat wordt opgeslagen, waarbij op de key (hash) gezocht kan worden, zonder gelijk de zware operatie van een volledig object ophalen te moeten doen. Dictionaries zijn wel wat zwaarder in het toevoegen van objecten: een key mag maar 1 keer bestaan en daarop moet worden gecontroleerd. Een List daarentegen mag dubbele elementen bevatten en is op dat vlak een stuk lichter in gebruik.

Toch maar besloten om de Dictionary een kans te geven, dus alle Lists vervangen en code aangepast voor gebruik van een Dictionary. In de logging werd al netjes op verschillende plekken in de code bijgehouden waar hij zat en op welk tijdstip dat was (nauwkeurig tot 1/1000-ste van een seconde). Handig om de prestatiewinst te meten dus. En dat het wat sneller zou zijn had ik wel verwacht maar de resultaten waren simpelweg verbluffend:

ActieList<T>Dictionary<K,V>
Toevoegen/Wijzigen42,167 s0,094 s
Verwijderen21,429 s0,012 s

Hou er rekening mee dat hierbij al gelijk de acties zitten dat de database daadwerkelijk wordt aangepast. Exact dezelfde dataset is gebruikt, het enige wat gewijzigd is, zijn de collections die werden gebruikt. De database bevindt zich in dit geval lokaal op een laptop-hardeschijf, ergo: niet snel dus.

Verschillen van zo'n 450 (voor toevoegen en wijzigen) tot 1780 (vewijderen) keer zo snel zijn best extreem te noemen! Een zelfde soort actie moest worden uitgehaald voor een tweede XML-bestand met 16.000 nodes, die op min-of-meer dezelfde manier werd doorlopen. De totale doorlooptijd van het programma bedroeg na de aanpassing slechts 7 seconden. 3 daarvan voor connectie met de database starten, 3 seconden om de volledige database in te lezen in het geheugen (geheugengebruik zo'n 100MB) 0,8 seconden om de XML files (2 stuks) met wijzigingen weg te schrijven en de resterende 0,2 seconden om daadwerkelijk alle vergelijkingen en aanpassingen te kunnen doen. En dat zijn prima tijden om ook tijdens productietijd te kunnen doen. Daar zou een gebruiker amper last van moeten hebben. Missie geslaagd dus!

-bubbles out-

Volgende: Langdurig onopgelost ongedierte 04-'12 Langdurig onopgelost ongedierte
Volgende: #DoYourBit 10-'11 #DoYourBit

Reacties


Door Tweakers user KnoxNL, dinsdag 3 april 2012 10:30

Leuk, en zelfs voor mij als non-programmeur goed te volgen. Mag je best trots op zijn.

Door Tweakers user TIGER79, dinsdag 3 april 2012 10:33

Een vraagje, op welk systeem heb je de tests gedraaid ?
Want je hebt het wel over "nauwkeurig tot 1/1000-ste van een seconde" maar dat kan natuurlijk alleen op een echte RTOS... Windows bijv heeft sowieso cpu time slices van zo'n 15 ms... dat is ook de maximale tijd-resolutie...
Voor de rest kun je op internet enorm veel vinden over dit soort onderzoeken, ook over itereren door arrays, wanneer een List of een Vector te gebruiken ivm performance enz enz..
Maar wel een leuk stukje om te lezen, ik zie er graag andere voorbij komen !

Door Tweakers user Xiphalon, dinsdag 3 april 2012 10:37

Tja. List<T>.Find is een O(n) operatie, en Dictionary<K,V>.Item() benadert O(1).

Door Tweakers user CodeCaster, dinsdag 3 april 2012 10:46

Rule of thumb: als je meer moet bewerken (zoeken, updaten, verwijderen) dan toevoegen, is een Dictionary al snel sneller.

Daarnaast kun je, als je XML ook de database-ID's bevat, het ID als (integer) key gebruiken. Over een integer key wordt namelijk geen hash berekend (tenminste, de hashcode van een int is diezelfde int), wat het inlezen van de data in je dictionary ook nog eens sneller maakt.

[Reactie gewijzigd op dinsdag 3 april 2012 10:46]


Door Tweakers user Bubbles, dinsdag 3 april 2012 10:47

TIGER79 schreef op dinsdag 03 april 2012 @ 10:33:
Een vraagje, op welk systeem heb je de tests gedraaid ?
Lokaal op de laptop: Windows Vista. Intel C2D P8600 (2,4 GHz) processor.
Want je hebt het wel over "nauwkeurig tot 1/1000-ste van een seconde" maar dat kan natuurlijk alleen op een echte RTOS... Windows bijv heeft sowieso cpu time slices van zo'n 15 ms... dat is ook de maximale tijd-resolutie...
Heb je daar ook een bron van? In mijn logging (via Log4Net) zie ik verschillende tijden voorbij komen met een verschil van o.a. 0,001, 0,002, 0,003 en ook meer seconden; een stuk preciezere resolutie dan 0,015 seconden die jij aanhaalt.
Voor de rest kun je op internet enorm veel vinden over dit soort onderzoeken, ook over itereren door arrays, wanneer een List of een Vector te gebruiken ivm performance enz enz..
Maar wel een leuk stukje om te lezen, ik zie er graag andere voorbij komen !
Er zijn inderdaad genoeg site die aanhalen wanneer je welke collection zou moeten gebruiken. Maar niets zo leuk als een eigen real-life test met meetbare resultaten. :D

[Reactie gewijzigd op dinsdag 3 april 2012 11:06]


Door Tweakers user TIGER79, dinsdag 3 april 2012 11:02

Eerste stukje dat ik erover tegenkom, maar er is meer van way betrouwbare bronnen, alleen zit op het werk ;)
http://blog.4dotnet.nl/76...-tijd-in-stapjes-van-15ms

Door Tweakers user Bubbles, dinsdag 3 april 2012 11:44

In je stukje dat je aanhaalt wordt ook verteld dat bij andere manieren van aanroepen, tijden veel preciezer kunnen zijn en je niet meer afhankelijk bent van de default Windows timeslice. Gezien de resultaten in de logfile, verwacht ik dat Log4Net dat ook doet.

Door Tweakers user DRaakje, dinsdag 3 april 2012 11:55

Heb je ook al eens gekeken hoe de performance van hashset is? Tijdens oplossen van een paar euler problemen, goede ervaringen mee gehad.

Door Tweakers user TIGER79, dinsdag 3 april 2012 12:46

wat ze aankaarten is juist dat de standaard Windows timeslice wordt aangepast, je kunt deze (indien je software daarop loopt) niet zomaar even overrulen... Oftewel, de aangekaarte methodes timeBeginPeriod() zijn juist van windows en die stellen een Windows-vaiabele in : http://msdn.microsoft.com...d757624%28v=vs.85%29.aspx

oftewel je software zit in Windows global settings te "kutten" :P

Door Tweakers user FlowinG, dinsdag 3 april 2012 14:06

Ziet er goed uit :)

Wat ook wel goed werk (en hoe ik een implementatie heb gemaakt), is een hash code van het hele object (database rij of xml node) berekenen en deze opslaan.

Initieel hoef je dan alleen alle records op te halen met id en hascode. Deze stop je dan in een Dictionary<> en ga je vergelijken met je XML. Degene waarbij de hash niet meer klopt, ga je uiteindelijk updaten. Updaten kan je vervolgens in een of meerdere threads doen terwijl de mainthread verder gaat met vergelijken van alle records.

Over gewijzigde records bereken je een nieuwe hash en deze update je dan weer tegelijkertijd met de rest van je updates.

Door Tweakers user RobIII, dinsdag 3 april 2012 16:53

TIGER79 schreef op dinsdag 03 april 2012 @ 12:46:
oftewel je software zit in Windows global settings te "kutten" :P
Bullshit. De standaard timers hebben inderdaad vaak een resolutie van ~10 tot ~15ms (en dat is doorgaans vaak meer dan genoeg) maar er zijn ook high resolution timers beschikbaar waar, o.a., de Stopwatch class gebruik van maakt waar je tot op de tick nauwkeurig kunt meten (maar die is dan wel frequentie-afhankelijk).

Het staat zelfs in 't artikel dat je notabene zelf aanhaalt:
Gelukkig zijn er andere manieren om het aantal ms te bepalen:
hardware timer gebruiken: met QueryPerformanceFrequency + QueryPerformanceCounter kun je met micro en nano secondes werken!
Neemt niet weg dat Log4Net, standaard althans, (volgens mij) gewoon gebruik maakt van een DateTime.Now oid die inderdaad maar een resolutie heeft van ~10 ~15 ms (en zelfs meer, 55ms, op Win9X :P )

Simpel testje:

C#:
1
2
for (int i = 0; i < 1000; i++)
    log.Debug(string.Empty);


... en een date-format op HH:mm:ss,ffffff geeft bij mij intervallen van 15,6ms.

Hetzelfde geintje met een Stopwatch:

C#:
1
2
3
4
var sw = new Stopwatch();
sw.Start();
for (int i = 0; i < 1000; i++)
    log.Debug(sw.ElapsedTicks);


...is verdomd nauwkeurig; hou dit in je achterhoofd! Eigenlijk krijg je dan zoiets:

C#:
1
2
3
4
var sw = new Stopwatch(); 
sw.Start(); 
for (int i = 0; i < 1000; i++)
    log.Debug(sw.ElapsedTicks / (double)Stopwatch.Frequency);


Dat geeft bij mij zoiets.

[Reactie gewijzigd op dinsdag 3 april 2012 17:36]


Door Tweakers user Fiander, maandag 16 april 2012 18:09

Mag ik vragen waarom je er voor hebt gekozen om dit client side op te lossen ?

Maak een storedprocedure, laat je XML als parameter mee sturen,
en gebruik het MERGE statement om te inserten/updaten/deleten waar nodig.
je hoeft dat alleen maar de XML te versturen, en mbv het merge statement word de tabel welke je aan wil passen maar één keer geraakt.

http://technet.microsoft.com/en-us/library/cc879317.aspx

Reageren is niet meer mogelijk