Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Je kunt ook een cookievrije versie van de website bezoeken met minder functionaliteit. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie

Door , , reacties: 138, views: 131.252 •

Conclusie

Onze totale geheugenbesparing ten opzichte van een 'naïeve' implementatie loopt door de besproken technieken waarschijnlijk richting de 2 gigabyte. Dat is genoeg om ruimschoots binnen de eerder genoemde maximale heap size van 4GB te blijven.

Daarmee is echter niet gezegd dat iedereen maar meteen moet beginnen met dit soort optimalisaties. De meeste genoemde ideeën kosten extra rekentijd bij het aanmaken van objecten, verbloemen complexiteit of doen aannames die strijdig kunnen zijn met defensive coding-principes. Erger nog, ze kunnen bij verkeerd gebruik juist extra geheugen kosten.

Tijdens de ontwikkeling van onze Java-code bleek echter dat de besproken methoden en technieken niet in de standaard-'toolkit' van onze programmeurs zaten. Dat is niet zo vreemd; dergelijke optimalisaties maken doorgaans geen deel uit van een standaard-Java-cursus. Ook in de praktijk is het niet gebruikelijk dat er meer dan een paar duizend objecten in het geheugen worden gehouden.

Het is precies daarom dat we dit artikel hebben gepubliceerd; andere Java-programmeurs hoeven zo het wiel niet opnieuw uit te vinden. Nogmaals, het blind in elke applicatie toepassen van deze technieken is niet de bedoeling. Gebruik altijd een goede geheugenprofiler om uit te zoeken welke optimalisaties werkelijk de moeite waard zijn en probeer ook de nadelen van je optimalisatie te vinden. Dat scheelt je niet alleen veel werk, maar voorkomt ook dat je jezelf met nodeloos complexe code allerlei nieuwe problemen op de hals haalt. Zoals vaak wordt gezegd: "Premature optimization is the root of all evil."


Door Arjen van der Meijden

- Lead Developer

In Oktober 2001 begonnen met als voornaamste taak het technisch beheer van het forum. Daarna doorgegroeid tot senior developer en software architect. Nu lead developer, met een leidinggevende taak aan het team van programmeurs en systeembeheerders van Tweakers.net.

Reacties (138)

Reactiefilter:-11380136+1125+232+33
Ik moet eerlijk bekennen dat ik niet zo thuis ben in deze wereld, maar het was wel erg interessant om te lezen.

Ik vind het ook erg leuk om te zien dat jullie een artikel als deze maken en hierbij niet alleen inzage geven over het hoe/wat, wat voor iemand als mij erg interessant is, maar ook dat jullie deze informatie delen zodat anderen hier wellicht iets aan hebben. Erg gaaf van jullie! :)

Ik word echt serieus steeds nieuwsgieriger naar Tweakers 7.0! :o

[Reactie gewijzigd door Perkouw op 8 mei 2012 08:16]

Ik was al bij de eerste pagina de draad kwijt. Geen flauw idee wat alle termen inhouden en als het op 1 april was gepubliceerd, zou ik toch gaan twijfelen of het een grap was.

Ik vermoed dat meer tweakers dit zullen hebben, misschien is een linkje of 2, 3 naar pagina's waar meer wordt uitgelegd wel handig?
Voor de tweakers die dit niet zullen volgen heeft het ook niet veel nut om het toch te willen begrijpen :P Want het is eigenlijk alleen nuttig voor java programmeurs die toch wel /iets/ aan serieuze applicaties hebben gemaakt.

Hoe dan ook, wat ik hier niet volg is waarom dit niet met een traditionele database wordt gedaan (die desgewenst volledig in het geheugen kan worden geladen) en van daaruit gewoon in php te query'en. Zover ik kan zien zou dit geenszins sneller moeten zijn en ik heb met veel grotere datasets gewerkt in traditionele databases op minimale hardware die net zo snel werkten als de pricewatch (de load was misschien niet /zo/ hoog als de pricewatch, maar ook nog redelijk zwaar).

Edit: Las nu pas de comments van ACM hieronder, dus dat verklaart de motivatie bij tweakers al blijf ik bij de indruk dat een normale database (die geoptimalizeerd is voor dit soort taken) beter zou werken dan dit (het is niet zonder reden dat het maken van een database complex is, en wat tweakers hier praktisch heeft gedaan is z'n eigen custom database bouwen).

Edit2: Wij werken hier op werk trouwens met een database van een klant (het gros van alle wetenschappenlijke artikelen globaal) en daar hebben ze het opgelost met 1 lucene of solr systeem (ik hou me er persoonlijk niet direct mee bezig en heb het alleen van een collega gehoort) voor ongeveer 1/4 van de velden/kolommen (waar veel op wordt gezocht) en een tweede systeem (veel trager) voor het doorzoeken van /alle/ velden/kolommen (veel trager dus) die dus in een normale database zitten. Lijkt me dat dat bij tweakers ook wel praktisch was geweest, want ik denk dat 90% van alle bezoekers misschien dezelfde top 5 filters in de gros van de gevallen gebruiken alleen (als je een laptop zoekt gaan niet veel mensen bijv. filteren op welke specifieke gpu ze willen hebben).

[Reactie gewijzigd door David Mulder op 8 mei 2012 10:51]

Ik vind dit juist een van de weinige artikelen die ik zelf interessant vind. Dit soort artikelen verwacht ik veel meer van Tweakers.net.

Ik dacht dat dit een site was voor Nerds, niet voor mensen die vrijwel niets van IT weten, no offence. Ik vind het ook heel raar dat je dit een grap zou kunnen vinden. Geeft vooral iets aan over de verschuiving van de wacht, de afgelopen 12 jaar.

Maar zeg Tweakers, just checking, jullie zitten qua data toch niet met user data op de werkstationnetjes te devven hoop ik?

[Reactie gewijzigd door Q op 8 mei 2012 21:24]

Ik dacht dat dit een site was voor Nerds, niet voor mensen die vrijwel niets van IT weten, no offence. Ik vind het ook heel raar dat je dit een grap zou kunnen vinden. Geeft vooral iets aan over de verschuiving van de wacht, de afgelopen 12 jaar.
Dat valt wel mee denk ik, hoewel de bezoekers hier al lang geen puisterige, bleke nerds zonder sociale vaardigheden en met een aversie voor zonlicht meer zijn. IT is nogal een breed vakgebied. Misschien is Nas T wel heel goed in casemodding of overclocking, misschien werkt hij bij een TD en soldeert hij in z'n vrije tijd betere componenten op zijn moederbord. Dat iemand geen Java kan programmeren wil niet zeggen dat hij niks op T.net te zoeken heeft.

Zo heb ik zelf Werktuigbouwkunde gestudeerd. Ik heb iets van C++ programmeren geleerd, maar daar houdt het ook op en ik ben het al vergeten hoe het moest. Ik heb er bij mijn werk nooit mee te maken. Computers zijn een hobby voor me, ik bouw mijn eigen PC en installeer hem. Tweak wat zodat de prestaties verbeteren, maar daar houdt het op.

[Reactie gewijzigd door Grrrrrene op 12 mei 2012 17:34]

Die je 'nu' in de pricewatch krijgt? Dat is functionaliteit die helemaal niets met deze java-code te maken heeft. Sterker nog, de java-code waar dit artikel over gaat is nog niet eens in productie genomen, terwijl die prijshighlight die jij noemt volgens mij al een jaar bestaat ;)
Volgens mij heeft de gemiddelde Tweaker niet zo'n heel veel moeite met cijfertjes vergelijken. En voor niks gaat de zon op...
Leuk artikel! Ben even;) bezig met een hijskraan berekenen; maar wanneer ik thuis ben kan ik weer in het echt interessante spul duiken. Erg leuk dit soort artikelen! Zoals ik wel vaker geroepen heb bij dit soort artikelen: Meer, meer, meer!!
Als proffesioneel (java-) programmeur kan ik dit artikel wel appercieren!
Ik hou van de voorzichtigheid waarmee de methodes worden aangereikt.
Een grote tabel / overzicht met gebruikte technieken en hun winst was nog welkom geweest.
Voor de rest: doe zo voort!
Leuk artikel, maar niet zo heel nuttig voor de gemiddelde Java applicatie, omdat die de data gewoonlijk uit de database haalt. Indexeren kan je dan bijv met Lucene doen en dan ben je al eigenlijk klaar. Mocht de database te traag worden, dan zou je bijvoorbeeld MongoDB kunnen gebruiken.
Desondanks wel nuttig, het geeft wel aan dat een simpel lusje om strings aan elkaar te plakken al gauw redelijk wat data verstookt, iets wat veel ontwikkelaars al snel vergeten. Als daarna echter de garbage collector afgaat is het probleem ook weer verholpen...

Was het niet handiger geweest om alleen de nieuwe artikelen in het geheugen te houden, van bijvoorbeeld de laatste maand ofzo? Ik kan me voorstellen dat de oude artikelen zelden of nooit bekeken worden. Hierdoor hoef je ze al niet eens in het geheugen te laden. Om relevante artikelen te bepalen zou je dan alleen wat steekwoorden in het geheugen bij te hoeven houden, en klaar ben je. of nog mooier: de top 8000 artikelen. Artikelen die worden opgevraagd uit de cache krijgen een nieuwe timestamp, en de oudste artikelen vallen er zo vanzelf uit...

Naja, er zal ongetwijfeld wel goed over nagedacht zijn, maar ik kan me zo voorstellen dat dit niet altijd zo door kan blijven gaan... Op en gegeven moment loop je toch uit je geheugenruimte, ondanks al je compressie.
Volgens mij werkt een database ook met zo'n cache.
Het probleem is hierbij dat MySQL en MongoDB de complexe filtering niet efficient kunnen verwerken. Althans, niet in combinatie met het ophalen van facet-informatie en een goede schatting van het aantal items dat in totaal nog aan je filters voldoet.

Daar zou je op zich wel Lucene of Solr voor kunnen gebruiken, maar wij hebben uiteraard nog net dat beetje extra complexiteit wat Lucene/Solr ook niet zomaar praktisch maakt. Bovendien moet je voor een Lucene-index (of MongoDB-collection) alles tot op het laagste niveau denormalizeren in losse "documenten".
Als er dus relatief veel van die afgeleide data verandert, ben je continu met hele complexe bijwerk-operaties bezig.
Door deze applicatie hebben we e.e.a. kunnen vereenvoudigen omdat we met referenties naar objecten kunnen werken en daardoor niet steeds de inhoud ervan hoeven te dupliceren.

Qua ram-geheugen heb ik hieronder al een opmerking geplaatst. 10 jaar aan verzamelde gegevens past in een 4GB heap... dus we gaan er van uit dat we nog wel even mee kunnen, ook al groeit het tegenwoordig wel wat harder dan in het begin :)

Voor wat betreft de garbage collector: vergeet niet dat geheugen gebruiken ook impact op je rekentijd heeft, niet enkel op de absolute hoeveelheid RAM die gebruikt wordt. En bovendien is die absolute hoeveelheid ook eindig (dat is zelfs een van je opmerkingen over onze opzet ;) )

[Reactie gewijzigd door ACM op 8 mei 2012 09:19]

Er zijn andere (commerciële) oplossingen beschikbaar vandaag die de problemen die je aanhaalt zeer efficiënt kunnen oplossen (filtering met facets + counts en eenvoudige en ogenblikkelijke updates)
De oplossing die wij ontwikkelen en commercialiseren lijkt immers te voldoen aan de eisen die je stelt en alle nodige features aan te bieden (en meer). (Stuur een DM indien je meer info wil, 'k wil hier niet "spammen")

Kan je een inschatting geven van de hoeveelheid tijd/werk die in deze optimalisaties gestoken is? (Die mythische manmaanden enzo :) )
Misschien eens kijken naar ElasticSearch of soortgelijk, kun je een stuk meer mee.
Volgens mij kan daar nauwelijks meer mee dan met Lucene of Solr, het grootste voordeel is dat het een stuk eenvoudiger is om die databases schaalbaar in te zetten. Maar met onze relatief compacte dataset (het past tenslotte nog binnen 4GB ;) ) is dat wat overbodig om verticaal over meerdere machines uit te smeren.
Volledig offtopic: Heel erg leuk om eens een uitgebreid stuk over programmeren te zien. Zie ik veels te weinig op Tweakers!

Ik hoop dat nog vele van dit soort artikels zullen verschijnen! (java, c#, php, c++)
Komt waarschijnlijk doordat de meuk de op tweakers.net komt door redacteurs geschreven zijn. En dit waarschijnlijk door een developer.

Developers zijn nou eenmaal niet zo geinstresseerd (althans ik...) in het schrijven van een artikel. We tikken al genoeg af op een dag :)
Inderdaad, erg leuk om eens een programmeer artikel te lezen. Ik ben zelf C++-er en schrijf geen Java, maar ik vond het toch leuk om dit eens door te lezen. Enkele van de genoemde technieken zijn natuurlijk net zo goed bruikbaar in C++ als in Java. Voor mij is dit veel interessanter als de zoveelste benchmark van weer een nieuw mobieltje of de volgende patentenrechtzaak, maar ik begrijp dat dat persoonlijk is.
Leuk artikel, maar zoals elhopo ook aangeeft toch mijn bedenkingen naar lange termijn visie...

Hoe is daarmee rekening gehouden?
Deze omgeving bevat nu artikelen en producten die in de afgelopen 10 jaar zijn verzameld... en dat binnen een geheugengebruik dat nu goed in het RAM van een eenvoudige workstation past (ik gebruik zelf een jvm met 4GB heap). Dus we verwachten dat het nog wel even duurt voor het onpraktisch wordt om voor dit doel RAM-geheugen te gebruiken.

Wel willen we tzt nog een stuk gegevens toevoegen wat wel aanzienlijk meer is dan die paar GB, dat komt waarschijnlijk in een normale on-disk lucene-index voor het doorzoeken en verder de reeds bestaande database als bron voor de objecten zelf en wellicht een eenvoudige cache-laag die slechts de hot-items in geheugen houdt.

Puur qua interfaces en opzet zou dat allemaal vrij goed binnen de huidige omgeving moeten passen. Maar er zitten vast nog haken en ogen aan om door te voeren :P
Ik vraag me af hoe nuttig het is om optimalisaties te doen speciaal voor ontwikkelomgevingen? Waarom zou je niet 1/10de of 1/5de van de data kunnen gebruiken voor de ontwikkeling? Of geef iedereen een snelle SSD en benader vanaf daar de data :p

Zelf heb ik dit soort dingen (weliswaar met een stuk minder data) opgelost met Lucene Solr maar daar had ieder document inderdaad dezelfde structuur, ik kan me voorstellen dat het lastiger wordt als ieder document er anders uit ziet.

Misschien wel leuk om deze back-end te open-sourcen? O-)

[Reactie gewijzigd door Ramon op 8 mei 2012 10:20]

Goed artikel, zo zie ik er graag meer.
Informatief en goed artikel. Ik kan zelf ook nog wel aanraden om, mocht je bvb toch in een krappe memory omgeving werken bvb nog op 32bit productiemachines (triest, ik weet het) moeten werken waar je af en toe toch grotere hoeveelheden gegevens in memory nodig hebt en niet op voorhand weet hoeveel, kan je beter gebruik maken van een linkedlist, kost extra geheugen qua datastructuren maar er moet niet 1 blok continuous gealloceerd worden.

Als je dan bvb een blok van 100mb hebt, en je moet plots een dubbel zo grote arraylist hebben gaat hij intern een dubbel zo groot blok alloceren en dan de bestaande data overkopieren waardoor er tijdelijk 300mb in use is, of je in het ergste geval een out of memory kan krijgen.
Een linked list kost niet alleen extra geheugen, maar is ook langzamer om te doorlopen. In vergelijking met een array vele malen langzamer zelfs. Wanneer je dit gewoon nodig hebt omdat je programma anders helemaal niet draait is de trade-off uiteraard acceptabel, maar in het algemeen zal een trip naar de hardwareboer toch een betere investering zijn.

Een alternatief is niet een standaard linked list te gebruiken maar één die in chunks werkt -- dus niet elk elementje zijn eigen node, maar arrays in een node. Hiermee reduceer je de overhead van de list maar hou je de mogelijkheid extra elementen toe te voegen zonder te moeten kopiëren. Dit vergt wel codeerwerk als nog niet iemand een library hiervoor gemaakt heeft in jouw taal, natuurlijk.

De extreme vorm hiervan is maar één zo'n chunk hebben en geen list. 200 MB array up-front vragen en die gebruiken tot het op is. Hiermee zet je geheugenbeheer buiten spel en het is dus ook nog eens lekker snel. Nadeel: dit werkt niet goed als je heel veel verschillende soorten data hebt (je kunt niet voor alles 200 MB gaan reserveren), het programmeert niet fijn omdat je zelf het gebruik bij moet houden en ingebouwde limieten (zelfs als ze niet hard-coded zijn) zijn natuurlijk de pest om te beheren en onderhouden ("er is nog geheugen over, waarom doet het programma het niet?"/"ik wil alleen maar een bestand van één regeltje openen, waarom doet het programma het niet?")
Als je in een (Java) de iterator gebruikt (of de for-each loop), dan is loop-en over de LinkedList net zo efficient (nl O(n)) als over een array (of ArrayList). Als je iedere keer get(index) gebruikt dan is het inderdaad O(n2)
LinkedList is waarschijnlijk in de praktijk iets minder efficient ivm het steeds moeten volgen en bijwerken van referenties naar objecten. Terwijl de ArrayList-iteratie een array-pointer heeft en een integer die geincrement wordt.
De ArrayList is waarschijnlijk net iets cache-vriendelijker ivm het netjes op een rij staan van de benodigde referenties, waardoor het opvragen van de referentie naar een volgend element meer kans heeft om (bijv door een pre-fetch) al in het cache-geheugen van de cpu te zitten.

Daarentegen is iterator.remove() weer veel goedkoper bij de LinkedList omdat er enkel maar twee Nodes aangepast hoeven te worden, ipv een arraycopy om het verwijderde element te overschrijven... maar het is in de praktijk nog best lastig goed te voorspellen welke van de twee het snelst zal zijn in zo'n situatie. Vergeet niet dat de ene O(n) de andere niet is (bijvoorbeeld omdat het in het ene geval n * 1ms is en in het andere geval n * 100ms).

Het is allemaal in dit geval nogal theoretisch geneuzel en het is goed mogelijk dat de overhead van beide iterators zo marginaal is vergeleken met je algoritme, dat je beter daar op kan concentreren :)

Ik zou dan ook vooral een List-implementatie kiezen die het best bij je requirements past (bijv. efficiente random-access of juist goedkope iteratie-deletes).
En als beperkt geheugengebruik een eis is, dan is een ArrayList die verder niet meer aangepast wordt en direct met de goede grootte was geconstrueerd de beste keuze :P

't Is overigens wat mij betreft de eerste keuze voor een List, tenzij je toevallig de andere eigenschappen van een LinkedList goed kunt gebruiken (bijv omdat je 'm als een Deque, Queue of Stack wilt gebruiken).
Het is zelfs tegenwoordig zo, dat zelfs met relatief kleine lijst grotes array lists sneller zijn bij random insert en delete operaties dan linked lists. Dat komt voornamelijk door de caches in de cpu's. Als je gehele arraylist makkelijk in de cache past, dan is het invoegen van een element ergens random in de lijst sneller ondanks dat de helft van de array opgeschoven moet worden dan met een linkedlist, waarbij om de goede node te vinden al misschien vele memory operaties gedaan moeten worden omdat alle nodes random in het geheugen verspreid staan. Elke geheugen actie kost in de orde van 100 keer zoveel tijd dan een normale cache hit. Daarom dat tegenwoordig in bijna alle gevallen een array list beter performed dan linked lists.
Mooi artikel, het gaat ook goed diep in op het onderwerp :) Ik ben altijd een beetje huiverig voor het (over)optimaliseren van de performance van je code. Vaak zie je namelijk dat het de leesbaarheid/ onderhoudbaarheid/ complexiteit van je code niet ten goede komt. Maar een aantal van de genoemde optimalisaties kan in een aantal gevallen zonder problemen worden doorgevoerd. Nogmaals, mooi artikel :)

Op dit item kan niet meer gereageerd worden.



Populair: Samsung Smartphones Processors Sony Microsoft Games Apple Consoles Politiek en recht Smartwatches

© 1998 - 2014 Tweakers.net B.V. Tweakers is onderdeel van De Persgroep en partner van Computable, Autotrack en Carsom.nl Hosting door True

Beste nieuwssite en prijsvergelijker van het jaar 2013