[Alg] Efficiënt bestandsnamen opslaan en doorzoeken

[ErikKo]

Geachte tweakers,

Ik heb een stukje software met momenteel 27.000+ bestandsnamen.
Deze zijn opgeslagen als absoluut pad in de database.

De software scant een bepaalde map, en kijkt of er nieuwe bestanden zijn. Momenteel gebeurt dit dmv een scan van de harddisk inladen, alle bestandsnamen selecteren uit de database, en met een dubbele loop vergelijken. Een snelheid van O(n^2) dus. Kortom, huilen.

Wat zouden jullie aanraden om dit proces te versnellen?

Ik had het volgende idee:
- De string van het absolute pad representeren als numerieke waarde. (past dit? int32? int64?)
- Vanuit deze waardes een Red-Black Tree bouwen.
- Deze RB-Tree opbouwen bij het opstarten van de software, en in het geheugen houden. (Space usage: O(n))
Aangezien zowel insertion als searching O(log n) tijd kost, zal dit behoorlijk schelen tegenover O(n^2).

Zijn jullie het eens met deze optimalisatie, of hebben jullie betere ideeen?

Overigens niet onbelangrijk:
OS: Windows Server 2008 R2
Taal: C/C++
DB: Sqlite3

Overigens scan ik momenteel met een recursieve functie die gebruik maakt van FindNextFile. Kan dit sneller?

[Soultaker]

Als je toch alle bestandsnamen in het geheugen hebt, dan kun je die het beste eerst sorteren (O(N log N) stringvergelijkingen) en dan vergelijken met een gesorteerde lijst uit de database (een beetje database kan met de juiste index zo de bestandsnamen in de juiste volgorde aanleveren).

Als dat te traag is (het sorteren van strings met grote overlap in prefix kan traag zijn) zou ik eerder een hashtable gebruiken dan een binary tree (die precies hetzelfde probleem heeft, dat strings paarsgewijs vergeleken moeten worden) of eventueel een trie (die mogelijk meer geheugen gebruikt). Beide zijn set-structuren. Je gooit dan simpelweg alle aanwezige bestanden in de set, en haalt vervolgens één voor één de bestanden in de database op, en gooit ze uit de set. Wat je overhoudt in de set zijn nieuwe bestanden.

De FindNextFile() API is de voor zover ik weet de standaard-API onder Windows om files te listen, dus dat lijkt me een prima methode. Ik denk niet dat je aan die kant veel kunt optimaliseren. (Onder Unix kun je wel naar de modification time van directories kijken, maar daar zitten ook weer een aantal haken en ogen aan, en ik weet niet of dat onder Windows ook kan.)

[ Voor 18% gewijzigd door Soultaker op 04-01-2011 21:18 ]

[Reptile209]

Twee dingen:
1) Je zou kunnen denken aan een service die een hook op het bestandssysteem heeft, zodat je real-time de wijzigingen aan bestanden kunt monitoren. Dan hoef je niks meer te zoeken en weet je precies wat er gebeurt.

Als dat te hard-core wordt:
2) Waarom maak je geen gebruik van de 'tree' die al vanzelf in het pad zit opgenomen? Dus waarom zou je steeds tegen het hele pad gaan vergelijken, in plaats van een eigen tree te bouwen die het complete pad vormt? Dan sla je bovendien veel minder informatie op, omdat je niet steeds de complete string hoeft mee te sjouwen.

[Janoz]

Door in je originele oplossing bijde lijsten te sorteren kun je vervolgens gewoon lineair door de lijsten heen lopen en de verschillen bepalen. Dat is alvast een stuk efficienter.

[Soultaker]

Reptile209 schreef op dinsdag 04 januari 2011 @ 21:20:
2) Waarom maak je geen gebruik van de 'tree' die al vanzelf in het pad zit opgenomen? Dus waarom zou je steeds tegen het hele pad gaan vergelijken, in plaats van een eigen tree te bouwen die het complete pad vormt? Dan sla je bovendien veel minder informatie op, omdat je niet steeds de complete string hoeft mee te sjouwen.

Dit is eigenlijk een soort trie waarbij bestand- en directorynamen als letters gezien worden. Geen gek idee als je in het geheugen werkt. Maar het nadeel is dat zulke structuren niet heel makkelijk in een relationele database op te slaan zijn. (Het kan wel, natuurlijk, maar diverse operaties worden er heel wat ingewikkelder van.)

[.oisyn]

Soultaker schreef op dinsdag 04 januari 2011 @ 21:14:
De FindNextFile() API is de voor zover ik weet de standaard-API onder Windows om files te listen, dus dat lijkt me een prima methode. Ik denk niet dat je aan die kant veel kunt optimaliseren.

Je kunt de MFT uitlezen (iig op NTFS), dat is enorm veel sneller maar dan moet je applicatie wel admin-rechten hebben.

Overigens heb ik ooit eens een indexeer-tool gemaakt met een eigen custom database implementatie. Ik ging eerst voor de trie oplossing (met per node een letter), maar een btree zoals een gemiddelde rdb implementatie die gebruikt bleek een heel stuk sneller. Maar goed, ik wilde een substring search kunnen doen op bestandsnaam, voor alle files op al m'n partities.

[ Voor 47% gewijzigd door .oisyn op 05-01-2011 01:09 ]

[ErikKo]

Reptile209 schreef op dinsdag 04 januari 2011 @ 21:20:
Je zou kunnen denken aan een service die een hook op het bestandssysteem heeft, zodat je real-time de wijzigingen aan bestanden kunt monitoren. Dan hoef je niks meer te zoeken en weet je precies wat er gebeurt

In mijn geval overbodig: Bestanden worden momenteel handmatig toegevoegd.Een scan aanzwengelen is een kleine moeite.

.oisyn schreef op dinsdag 04 januari 2011 @ 21:49:
Je kunt de MFT uitlezen (iig op NTFS), dat is enorm veel sneller maar dan moet je applicatie wel admin-rechten hebben.

Momenteel zijn vooral de string comparisons de bottleneck. Wanneer ik een fatsoenlijk algoritme heb zou ik hier nog naar kunnen kijken. Thx!

Bedankt voor jullie reacties. Ik heb even gezocht en ben erachter gekomen dat ik een hoop algoritmes gemist heb in mijn zoektocht. Momenteel zijn B-tree en Trie de meest interessante.

[RobIII]

ErikKo schreef op woensdag 05 januari 2011 @ 00:10:
Momenteel zijn vooral de string comparisons de bottleneck

Dat is goed mogelijk maar ik wil 't toch even gevraagd hebben: heb je dat gemeten of is dat puur op gut-feel?

[Verwijderd]

Als het puur om nieuwe bestanden gaat kan je toch gewoon de File Creation stamp (of modification stamp) gebruiken om te kijken of je een nieuw bestand hebt ?
Als je toevoegt in je DB laat je die gewoon checken via een unique index ?

Overigens kan je op windows ook (ligt wel aan je config) checken op datum tijd van folder/subfolders.

(of alleen op de unique index, SqlLite zal geen probleem hebben met 27000+ items denk ik)


Of ligt je probleem gecompliceerder ?

[ Voor 26% gewijzigd door Verwijderd op 05-01-2011 00:38 ]

[Soultaker]

ErikKo schreef op woensdag 05 januari 2011 @ 00:10:
Ik heb even gezocht en ben erachter gekomen dat ik een hoop algoritmes gemist heb in mijn zoektocht. Momenteel zijn B-tree en Trie de meest interessante.

Seriously? Er zit een hash table in je standard library en je gaat zelf een B-tree of een trie bouwen? (Niet dat een trie heel ingewikkeld is, maar toch.) Je eigen datastructuur implementeren lijkt me de minst zinnige optie van de gegeven suggesties, maar wat je wil.

[ Voor 16% gewijzigd door Soultaker op 05-01-2011 01:16 ]

[Gomez12]

Persoonlijk zou ik (afhankelijk van dirstructuur) tijdens het read-next file een hash van een dir-inhoud maken. Dan kijken of die hash al in de DB staat, zoja dan hoeft er geen comparison overheen.

[.oisyn]

Ik hou nooit van dat soort oplossingen, voor een 100% robuust systeem zul je toch een compare moeten doen als de hashes overeenkomen. De kans op collisions is met een goede hashfunctie wellicht klein, maar niet nul. Je zou als optimalisatie de directory modification times kunnen opslaan. Als die niet gewijzigd is dan zijn er iig geen files verwijderd, aangemaakt of hernoemd in die directory (maar mogelijk wel in subdirs, dus je moet sowieso nog dieper scannen). Een andere mogelijkheid is gebruik maken van NTFS journals, dan kun je precies zien welke files zijn aangepast sinds je vorige synchronisatie van het journal (wel zorgen dat de journal buffer groot genoeg is, anders mis je updates).

ErikKo schreef op woensdag 05 januari 2011 @ 00:10:
Bedankt voor jullie reacties. Ik heb even gezocht en ben erachter gekomen dat ik een hoop algoritmes gemist heb in mijn zoektocht. Momenteel zijn B-tree en Trie de meest interessante.

Mja, ik was er vergeten bij te vermelden dat voor mijn case het over miljoenen files aan data ging die ik niet in het geheugen wil hebben. Een B-Tree is daarvoor handig omdat je makkelijk grote chunks van en naar file kunt swappen. Als je alles gewoon in het geheugen houdt zou ik zeker niet voor die datastructuur kiezen.

[ErikKo]

RobIII schreef op woensdag 05 januari 2011 @ 00:14:
Dat is goed mogelijk maar ik wil 't toch even gevraagd hebben: heb je dat gemeten of is dat puur op gut-feel?

Met debuggen heb ik 'gemeten'. Het scannen kost grofweg 20 seconden. Daarna de string comparisons erop los gelaten. Ruim 20 minuten later op volle CPU sprong hij terug voor debuggen.

Verwijderd schreef op woensdag 05 januari 2011 @ 00:33:
Als het puur om nieuwe bestanden gaat kan je toch gewoon de File Creation stamp (of modification stamp) gebruiken om te kijken of je een nieuw bestand hebt ?
Als je toevoegt in je DB laat je die gewoon checken via een unique index ?
(...)
(of alleen op de unique index, SqlLite zal geen probleem hebben met 27000+ items denk ik)

Dat zijn nog steeds 27000+ losse queries die ik op sqlite moet loslaten. (Tenzij ik je idee fout begrijp) Dat duurde verbazingwekkend lang; Langer dan alles ophalen en een-op-een laten vergelijken. Dat was namelijk mijn eerste theorie "Een database is op zoeken geoptimaliseerd". Het zoeken wel, maar niet het uitvoeren van een hele query. (Database open/lock, zoeken, database close/unlock)

Soultaker schreef op woensdag 05 januari 2011 @ 01:14:
Seriously? Er zit een hash table in je standard library en je gaat zelf een B-tree of een trie bouwen? Je eigen datastructuur implementeren lijkt me de minst zinnige optie van de gegeven suggesties, maar wat je wil.

Yup. Bewust voor gekozen. Vond het een goed excuus om mijn kennis een beetje op te frissen met algoritmes.

.oisyn schreef op woensdag 05 januari 2011 @ 01:36:
Mja, ik was er vergeten bij te vermelden dat voor mijn case het over miljoenen files aan data ging die ik niet in het geheugen wil hebben. Een B-Tree is daarvoor handig omdat je makkelijk grote chunks van en naar file kunt swappen. Als je alles gewoon in het geheugen houdt zou ik zeker niet voor die datastructuur kiezen.

Daar kwam ik na enig onderzoek inderdaad ook achter. Ik zag dat allerlei filesystems gebruik maken van een B-Tree. Na wat in te lezen waarvoor deze voornamelijk gunstig is, werd me al snel duidelijk dat ik dit niet zocht.

Heb daarom ook voor de Trie gekozen, welke ik overigens al grotendeels geimplementeerd heb. Binnenkort misschien de verschillende gemeten tijden eens vergelijken.

[RobIII]

ErikKo schreef op woensdag 05 januari 2011 @ 03:09:
[...]
Met debuggen heb ik 'gemeten'. Het scannen kost grofweg 20 seconden. Daarna de string comparisons erop los gelaten. Ruim 20 minuten later op volle CPU sprong hij terug voor debuggen.

Dus de IO (die een factor <shitload> trager is dan wat dan ook in het hele systeem) kost 20 seconden en string comparisons daarna 20 minuten? Ik zou echt héél serieus gaan twijfelen aan mijn meetmethode. Het kan zijn dat ik je verkeerd begrijp, en if so: niets gezegd, maar anders: dit slaat als een tang op een varken.

Heb je er al eens een profiler op los gelaten? En kun je eens in pseudo-code je algoritme beschrijven en exacte aantallen noemen (give or take a few; ballpark figures maar niets uit de duim gezogen).

ErikKo schreef op woensdag 05 januari 2011 @ 03:09:
Dat zijn nog steeds 27000+ losse queries die ik op sqlite moet loslaten.

27k+ queries duurt op een beetje DBMS (en dan durf ik dat zelfs voor SQL Lite nog wel te beweren) no way in hell 20 minuten tenzij je ergens iets fout doet. Dat zou 27000 / 1200 = 22,5 queries per seconde betekenen

ErikKo schreef op woensdag 05 januari 2011 @ 03:09:
Dat duurde verbazingwekkend lang;

Onmogelijk lang zelfs IMHO. Maak je niet voor elke query een nieuwe verbinding ofzo? Gebruik je überhaupt indexen?

ErikKo schreef op woensdag 05 januari 2011 @ 03:09:
Het zoeken wel, maar niet het uitvoeren van een hele query. (Database open/lock, zoeken, database close/unlock)

Huh? Zoals ik al zei: je hoeft niet voor elke actie de DB te openen en een lock is (wat ik zo van je verhaal begrijp) ook helemaal nergens voor nodig Pas als je gaat wijzigen wordt dat laatste interessant.

[Gomez12]

.oisyn schreef op woensdag 05 januari 2011 @ 01:36:
Ik hou nooit van dat soort oplossingen, voor een 100% robuust systeem zul je toch een compare moeten doen als de hashes overeenkomen. De kans op collisions is met een goede hashfunctie wellicht klein, maar niet nul.

Tja, het is een snelheid vs robuustheid tradeoff.

Ander alternatief wat ik voor wat grotere operaties gebruik ( nog steeds niet toppunt van efficientie wel makkelijk te implementeren ) is om het eerst gewoon in een "staging" table te gooien zonder indexen etc.
Dan index over staging table leggen, then let sql sort it out:)
daarna staging table leeggooien en daarna index over staging table verwijderen

[Verwijderd]

Heb ff simpele meting gedaan (code in delphi, sqllite via diSqllite library):
(als je gaat meten moet je de eerste meting achterwege laten, windows buffert nogal als je de findfile, findnext api gebruikt).

dit is met verre van geoptimaliseerde code, (zoeken op gehele bestandsnaam in db).

FileScan op locale drive

FileScan Only
Found : 17316 files.
In : 1941 folders.
took 562 msecs.

FileScan + CheckUpdate EmptyDB (Single Query, No Transaction)
Found : 17316 files.
In : 1941 folders.
took 294968 msecs.

FileScan + CheckUpdate EmptyDB (Double Query, Transaction)
Found : 17316 files.
In : 1941 folders.
took 138015 msecs.

FileScan + CheckUpdate FullDB
Found : 17316 files.
In : 1941 folders.
took 124453 msecs.


extra files toegevoegd ter controle:

FileScan + CheckUpdate FullDB
Found : 17321 files.
In : 1942 folders.
took 127094 msecs.

[ Voor 14% gewijzigd door Verwijderd op 05-01-2011 10:57 ]

[Janoz]

Gomez12 schreef op woensdag 05 januari 2011 @ 07:32:
[...]

Tja, het is een snelheid vs robuustheid tradeoff.

Maar dat hoeft niet. Je kunt ook extra snelheid krijgen zonder in te boeten op robuustheid. Het is dus helemaal geen tradeoff.

[djc]

Je zou ook eens naar http://msdn.microsoft.com...a365465%28v=VS.85%29.aspx kunnen kijken (afhankelijk van hoe je applicatie werkt; als je ergens een daemon hebt of het niet erg vindt om er een te hebben is het gebruik van dit soort APIs wel verreweg de snelste manier).

[ErikKo]

Dan deed en doe ik het dus momenteel helemaal fout... Ik dacht dat ik inderdaad indexen gebruik, maar weet het niet meer zeker. Dat zal best een verschil maken dan.

[Verwijderd]

ErikKo schreef op woensdag 05 januari 2011 @ 12:57:
Dan deed en doe ik het dus momenteel helemaal fout... Ik dacht dat ik inderdaad indexen gebruik, maar weet het niet meer zeker. Dat zal best een verschil maken dan.

ik run 'm eens zonder indexen (kan ff duren )

Found : 17322 files.
In : 1943 folders.
took 129703 msecs.


bijna net zo snel als met (nu sqllite buffert veel en het is maar eens simpele tabel en query), maar toch ?

[ Voor 23% gewijzigd door Verwijderd op 05-01-2011 13:29 ]

[DataGhost]

Als je nou eens gewoon alle bestanden uit de database in een set gooit (zit als het goed is in je library) (O(n log n)) en vervolgens alle filesystem-bestanden een voor een toevoegt aan de set (O(n log n)) en na elke insert kijkt of de set groter is geworden (O(1)) kan je daarmee precies, in O(n log n) totaal, zien of en welke bestanden nieuw zijn. Is dat niks?

[Verwijderd]

Blijkbaar heb ik nu ineens een raar probleem, zit te testen in SqliteSpy merk ik wel groot verschil met index.

Run m'n " testtool weer eens en uitkomst:


Found : 17326 files.
In : 1946 folders.
took 1391 msecs.

(blijkbaar was er iets mis met de index in eerst gebruikte db).

Na paar kunnen runnen resultaat:

Lege database (vacuumed!)
Found : 17326 files.
In : 1946 folders.
took 2375 msecs.

Gevulde Database
Found : 17326 files.
In : 1946 folders.
took 1359 msecs.

[ Voor 39% gewijzigd door Verwijderd op 05-01-2011 14:48 ]

[RobIII]

ErikKo schreef op woensdag 05 januari 2011 @ 12:57:
Dan deed en doe ik het dus momenteel helemaal fout... Ik dacht dat ik inderdaad indexen gebruik, maar weet het niet meer zeker. Dat zal best een verschil maken dan.

Dan nog snap ik je conclusie niet dat de bottleneck in je string-compares zouden zitten.

[ErikKo]

Ik heb toch maar eens wat metingen gedaan omdat jullie me niet geloven.
Het scannen van de harddisk kostte 29 seconden.
En ik had me vergist, ik doe voor ieder bestand nog steeds een query op de database om te kijken of hij er al in staat. De code durf ik niet te posten. Er gebeurt meer in de loop dan de bedoeling was...
Deze tijd kwam neer op 1687 sec = 28.12 mins. Mijn gevoel zat er dus niet ver vandaan.

[Verwijderd]

ErikKo schreef op woensdag 05 januari 2011 @ 17:05:
Ik heb toch maar eens wat metingen gedaan omdat jullie me niet geloven.
Het scannen van de harddisk kostte 29 seconden.

Een locale schijf of een netwerk schijf ??

(mijn resultaat nogmaals, alleen scannen van schijf, is wel een 2e loop zal nog ff snel rebooten en dan nog eens meten)

code:

FileScan Only
Found : 17316 files.
In : 1941 folders.
took [b]562 [/b]msecs.

> eerste keer is hier ook rond de 29seconden

En ik had me vergist, ik doe voor ieder bestand nog steeds een query op de database om te kijken of hij er al in staat. De code durf ik niet te posten. Er gebeurt meer in de loop dan de bedoeling was...
Deze tijd kwam neer op 1687 sec = 28.12 mins. Mijn gevoel zat er dus niet ver vandaan.

tsja, moet MEER dan de bedoeling was altijd gebeuren, of alleen bij nieuwe files ?

mij lijkt een en ander in de logica niet te kloppen

[ Voor 6% gewijzigd door Verwijderd op 05-01-2011 17:14 ]

[ErikKo]

Verwijderd schreef op woensdag 05 januari 2011 @ 17:09:
Een locale schijf of een netwerk schijf ??

Lokale schijf.

Toen ik de code schreef kwam 'performance' niet eens in me op. (Lang geleden) Binnen de loop, bij ieder bestand, werden variabelen gemaakt (malloc) en vrijgemaakt (free). Niet alleen bij nieuwe bestanden. Door een fatsoenlijke var te malloc'en kan dit al buiten de loop.

Maargoed, klein verschilletje, jouw meetresultaten zijn op 17000+ bestanden, waar mijn resultaten op 27000+ bestanden zijn. Dat wil nog wel schelen.

[RobIII]

ErikKo schreef op woensdag 05 januari 2011 @ 20:40:

Maargoed, klein verschilletje, jouw meetresultaten zijn op 17000+ bestanden, waar mijn resultaten op 27000+ bestanden zijn. Dat wil nog wel schelen.

Dan nog is 20 min "string compares" zoals jij dat beweerd absurd.

Maar zolang je het vertikt relevante(!) code te posten of in ieder geval in pseudo-code je algoritme uit de doeken te doen blijft het koffiedik kijken en kunnen we niet meer doen dan je blijven vertellen dat je waarschijnlijk iets fout doet. Ik zie niet waar je nog met dit topic naar toe wil als je niet met wat meer info over de brug gaat komen.

[Verwijderd]

ErikKo schreef op woensdag 05 januari 2011 @ 20:40:
[...]
Maargoed, klein verschilletje, jouw meetresultaten zijn op 17000+ bestanden, waar mijn resultaten op 27000+ bestanden zijn. Dat wil nog wel schelen.

Ja goed, wil het ook op 170.000 bestanden testen hoor

Maar je moet van die string-compare af, gewoon door je files heen lopen en direct zoeken, sqllite buffert genoeg over het algemeen. Je gaat het niks sneller maken door apart je database naar een stringlist/tree te halen en dan nog eens je file-tree ophalen en dan die vergelijken.

Sla je je filetree nu ook eerst op in een lijst ?

mijn (pseudo code):

Aanroep:

code:

    ScanFolderForFiles("d:\de\folder\die\gescanned\moet\worden", "*.*", doRecursive, DoNewFolder, DoNewFile)

ScanFolderForFiles, is dan een routine die ik vaker gebruik, die alle bestanden in de opgegeven folder die voldoen aan de filemask ("*.*") afloopt en een event (DoNewFile) aanroept.
Indien doRecursive dan loopt ie nog even alle folders in de opgegeven folder aan en roept dan dus zich zelf aan voor iedere subfolder met wederom doRecursive

DoNewFile

code:

  parameters(AFilename : string; var AKeepScanning : bool)

  sqlliteQry.query = 'SELECT filename FROM files WHERE filename=AFilename
  sqlliteQry.active = true
  if sqlliteQry.Eof then
  {
      <insert new record code> of <doe iets met file code>
  }

[ Voor 41% gewijzigd door Verwijderd op 05-01-2011 21:16 ]

[Gomez12]

RobIII schreef op woensdag 05 januari 2011 @ 21:00:
[...]
Dan nog is 20 min "string compares" zoals jij dat beweerd absurd.
...
kunnen we niet meer doen dan je blijven vertellen dat je waarschijnlijk iets fout doet.

Waarschijnlijk, waarschijnlijk? Of ik heb ergens iets gemist en hij gebruikt veel en veel meer dan alleen fat-entries of het is gewoon zeker dat hij iets extreem fout doet...

27.000 bestandjes enkel op filename en creation date comparen met een dbase mag imho in het allerslechtste geval 1 min duren en dat is dan nog zonder specifieke optimalisaties etc.
En dan nog moet er ruwweg geschat 80% van de tijd in I/O gaan zitten.

Sorry hoor, maar 27.000 string comparisons met een dbase involved mag gewoon niet lang duren.

Zo ondertussen word ik wel eens benieuwd wat er nu precies aan data vergaard wordt en wat er vergeleken wordt, ik gok dat ik binnen 10 minuten een php-script heb wat dit zonder uitzonderlijke optimalisaties etc binnen 2 minuten doet.
Zo ongeveer de enige manier die ik zie om 20 minuten over zoiets te doen is voor elke file afzonderlijk een nieuwe dbase connectie op te starten en een paar losse query's te draaien ( eerst 1 select om te zien of het bestaat of daarna een update of een insert afhankelijk van het resultaat van de select ) en daarna de connectie weer te sluiten, en waarschijnlijk moet ik zelfs daarvoor nog de standaard OS-filesystem cache aardig verneuken omdat ik anders onder die tijd blijf.

We hebben het afaik niet over rocket science, maar gewoon over wat FS-functies die een meervoudige array retourneren van max 1024 bytes per entry. Oftewel je hebt het over max 27 MB comparen met ongeveer 27 MB, dat mag gewoon geen tijd kosten.... Dat moet gewoon allemaal in memory kunnen ( of je moet minder dan 60MB over hebben, maar dan heb je hele andere problemen met je 386 )

[RobIII]

Gomez12 schreef op donderdag 06 januari 2011 @ 00:25:
[...]

Waarschijnlijk, waarschijnlijk?

Waarschijnlijk ja. Het kan ook goed zijn dat TS iets niet of verkeerd vermeld heeft waardoor straks iedereen zoiets heeft van "ooooh, maar dat verandert de zaak". Zolang we geen code gezien hebben of de exacte omstandigheden etc. is er weinig over te zeggen behalve, en dat ben ik met je eens, dat er op ons gevoel in ieder geval ergens waarschijnlijk niet goed is TS blijft helaas aardig in gebreke met harde feiten:

ErikKo schreef op woensdag 05 januari 2011 @ 03:09:
[...]
Met debuggen heb ik 'gemeten'. Het scannen kost grofweg 20 seconden. Daarna de string comparisons erop los gelaten. Ruim 20 minuten later op volle CPU sprong hij terug voor debuggen.

ErikKo schreef op woensdag 05 januari 2011 @ 17:05:
Ik heb toch maar eens wat metingen gedaan omdat jullie me niet geloven.
Het scannen van de harddisk kostte 29 seconden.
...
Deze tijd kwam neer op 1687 sec = 28.12 mins. Mijn gevoel zat er dus niet ver vandaan.

Dat is (eerste post) niet "meten"; zoals eerder gezegd was een profiler hier beter op z'n plek geweest (behalve als de code aan de oppervlakte al zo gaar is dat je de bottleneck zo al spot; en die kant gaat 't nu hard naar toe):

ErikKo schreef op woensdag 05 januari 2011 @ 17:05:
ik doe voor ieder bestand nog steeds een query op de database om te kijken of hij er al in staat. De code durf ik niet te posten. Er gebeurt meer in de loop dan de bedoeling was...

En verder is je post niet heel veel meer dan een echo van mijn eerdere post(s)

[ Voor 70% gewijzigd door RobIII op 06-01-2011 00:39 ]

[ErikKo]

Nou nou nou... Wordt wel vaak benadrukt dat ik waarschijnlijk iets fout heb gedaan. Daar was ik zelf ook al achter... Het ging ook over de oude situatie, die ik met de implementatie van de Trie grotendeels overbodig heb gemaakt. Het kost momenteel nog <10 seconden. Allemaal bedankt voor jullie reacties!

[Gomez12]

ErikKo schreef op donderdag 06 januari 2011 @ 01:12:
Nou nou nou... Wordt wel vaak benadrukt dat ik waarschijnlijk iets fout heb gedaan. Daar was ik zelf ook al achter... Het ging ook over de oude situatie, die ik met de implementatie van de Trie grotendeels overbodig heb gemaakt. Het kost momenteel nog <10 seconden. Allemaal bedankt voor jullie reacties!

Ik zou je bijna vragen om je stukje code te nomineren voor het WTF topic, meer dan 20 minuten naar <10 seconden is toch opzich wel een redelijk unieke prestatie...

Enkel begrijp ik iets niet goed, eerst duurde de I/O al 29 sec. en nu is het totaal onder de 10 sec, waar is die I/O dan gebleven? Oftewel meet je wel goed?

[ErikKo]

Ik vermoed omdat de schijf verschillende keren gescand heeft, de files gecached zijn of iets dergelijks?
De tweede keer op een schijf naar een bestand zoeken gaat ook altijd sneller...

[RobIII]

ErikKo schreef op donderdag 06 januari 2011 @ 02:05:
Ik vermoed

Ik vermoed, ik denk, ik dacht, ik meende... Misschien is het handiger als je nou eens gaat meten. Meten = weten. En meten doe je met een profiler.

[Verwijderd]

Twee runs, direct achter elkaar (91000+ files):

Found : 91875 files.
In : 6191 folders.
took 136000 msecs.

Found : 91875 files.
In : 6191 folders.
took 6359 msecs.

Windows cached dus zeer veel.


en met iets meer files (435000+)
Found : 435854 files.
In : 30399 folders.
took 479813 msecs.
Found : 436014 files.
In : 30399 folders.
took 31734 msecs.

[ Voor 31% gewijzigd door Verwijderd op 06-01-2011 09:55 ]