WinDirStat runs out of memory

avogelba commented 10 years ago

Originally reported by: Jim Babka (Bitbucket: jimbabka, GitHub: Unknown)

I have a 600GB drive with huge numbers of small files (mostly HTML/CSS files for multiple copies of sites I support) that only has 83 GB free. I can no longer run WinDirStat 1.1.2 - it gets about 75% through it's scan, then runs out of memory (the memory usage peaks at 1.4GB). I see mention of a 64-bit build, but have no idea how to get a hold of it. Is there something I can do to reduce its memory usage? Alternatively, is there a place I can get this 64-bit build?

In any case, this needs to be addressed somehow.

Bitbucket: https://bitbucket.org/windirstat/windirstat/issue/112

avogelba commented 9 years ago

Original comment by Alexander Riccio (Bitbucket: alexander_riccio, GitHub: Unknown):

The crash immediately after launch was probably due to compiling with AVX2 support, which is still relatively new. As long as you have a processor that supports AVX, then you should be fine with the latest build.

avogelba commented 10 years ago

Original comment by Oliver (Bitbucket: assarbad, GitHub: assarbad):

@Alexander Riccio: biggest downside is actually that it requires admin rights. But that's not a big deal, I think. The idea for the future would regardless be to provide a shortcut that leads to elevation. Makes it easier also with respect to the discrepancy between reported used/free space and what we get to see.

avogelba commented 10 years ago

Original comment by Jim Babka (Bitbucket: jimbabka, GitHub: Unknown):

FYI, turning off "Show file types" with the original made no difference to me.

avogelba commented 10 years ago

Original comment by Jim Babka (Bitbucket: jimbabka, GitHub: Unknown):

I tried running your new version on my system, and it crashed immediately after I chose the drive to scan. Running it as administrator made no difference.

avogelba commented 10 years ago

Original comment by Alexander Riccio (Bitbucket: alexander_riccio, GitHub: Unknown):

In retrospect, turning off the feature that was causing problems - well, it's not the most groundbreaking idea.

That said, I have great news. After swapping std::map & std::sort in (replacing CMap & _qsort), it now takes just a few minutes (tops) for scanning & drawing! In fact, the 'drawing' phase, which used to take more than an hour on my computer, usually finishes in ~1.2 seconds!

If you wan't to try the super-alpha build, I've uploaded a copy. It's super stripped down for speed & development - I've tweaked many things other than the drawing code.

Note that it's inside an encrypted 7z archive, which itself is inside a zip file - Wordpress.com won't let me upload any kind of executable.

There is one annoying bug at the moment - the Treemap initially renders a giant black rectangle; toggling "Show Treemap" solves the problem.

avogelba commented 10 years ago

Original comment by Alexander Riccio (Bitbucket: alexander_riccio, GitHub: Unknown):

Now that's A LOT of file types! :)

As more confirmation that this is indeed the root cause - unchecking 'show treemap' and 'show file types' (or whatever the options are called) eliminates the hours long lockup.

I won't even call this a workaround, but we're getting somewhere!

avogelba commented 10 years ago

Original comment by Jim Babka (Bitbucket: jimbabka, GitHub: Unknown):

Now we may be getting somewhere. I ran it again (and let it take the 1 hour 45 minutes needed to finish). I then tried to count the number of file types in the upper right, but there are way more than I can count. Here's what the upper right window looked like after scrolling down 2000 entries:

Note that the scroll bar is still close to the top. The main culprit is Clover recording files - I have around 400,000 of them, and each has a file type that is guaranteed to be unique (they are base 36 hash codes - for example, clover.dbk7dtzbhuyn4vo2). There are plenty of other file types, but that's probably in the neighborhood of 2-3K total. Note that I also seem to have a lot of files with types like "DLL{hex number}".

avogelba commented 10 years ago

Original comment by Alexander Riccio (Bitbucket: alexander_riccio, GitHub: Unknown):

I've been investigating the rendering performance. Surprisingly - most of the workload is not "drawing".

there'sTheProblem.PNG

Before windirstat actually does any drawing (i.e. creating CRects, the MFC name for the rectangles), windirstat decides on the color of each file type. All known file types are stored in a dictionary (CMap), where the string that represents the file type (i.e. ".txt") is the key, and the value is a struct that holds the number of files of that type, the total size of those files, and the color of that type. On my latest build - where everything else is already optimized - this constitutes 90-95% of the workload, and 3-5% involved in a related sorting operation. Nearly all of that 90-95% involves lookups in the aforementioned dictionary.

I haven't studied CMap in detail, but I find it a bit bizarre that lookups in a dictionary (which is intended to enable fast lookups) would be so terribly slow. That said, it does seem that there is a critical point, somewhere up in the high hundreds, where lookups become horrifically slow.

Do you have any idea (roughly) how many different file types you were scanning?

CMap isn't type safe, which certainly doesn't help. (C++ is all about type safety!)

avogelba commented 10 years ago

Original comment by Jim Babka (Bitbucket: jimbabka, GitHub: Unknown):

Update: turning off 8.3 had a minor impact on the size scan (1 hour 10 minutes down to 1 hour), but no impact on the graphical rendering (still taking over 45 minutes from the time WinDirStat finishes the size scan to when the colored boxes view appears). Again, I massively reduced the number of files (now down to 5 million items and 4 million files from 7 and 6 million, respectively), so it's not running out of memory anymore, but it is taking forever.

Just a thought - is there any way that the graphical rendering could be multi-threaded, so that it would use multiple CPUs? Again, I have 8 CPUs

it has one CPU pegged. The good thing is that I can still use my system while the rendering is going on (since I have 7 other CPUs available), but if it was possible for it to use, say, 6 of the 8, then that would make things much better. Clearly there's no point in multi-threading the actual disk scan, since the disk is the bottleneck there.

Jim Babka

avogelba commented 10 years ago

Original comment by Alexander Riccio (Bitbucket: alexander_riccio, GitHub: Unknown):

Short file name creation has a little-known (but well documented) performance impact.

A member of MSFT's File Server Team has some dramatic charts..

One Microsoft PFE (They are the best of the best, of the best, at microsoft) was quite surprised to see the performance effect 8.3 short name creation had on a server he was debugging.

This ancient Microsoft article recommends turning it off for heavily populated directories.

This slightly newer article describes a bit about why this happens.

The way WinDirStat currently walks a directory is roughly the optimal method* insofar as it is using the (stable) Windows API - It's so stable that Microsoft keeps crappy features (i.e. short name creation) & incorrect/buggy implementations around so there are no breaking changes. This method involves a system call for every directory & item in the system, which is tiny for each individual call, but with 10^6+ calls to make, it adds up.

There are other ways, most notably reading & parsing the Master File Table (MFT) directly; that's very fast. Another program that walks directories, NTFS-Search, can load/read/parse the WHOLE MFT in just a few seconds, and thereafter perform near-instantaneous (by-name) file searches.

However, parsing the MFT, does have downsides. Microsoft does NOT have any obligation (or any good reason) to support programs that don't use the Windows API, and by the nature of low-level acess to the raw storage, there are no APIs. NTFS is fairly well documented*, but this stil involves a ton of work & too often leads to brittle code. Oh, and this requires ADMINISTRATOR privliges.

I'm working on this myself - and plan to devote quite a bit of time to this over the next ~month. Although NTFS-search and other MFT parsing apps STOPPED working the other day, mysteriously. I'm not sure if this is a Win 8.1 thing, as a NTFS-Search runs fine on the Win 7 PC I have. I'm still investigating.

Funny sidenote about the path length limit; I've seen Microsoft software violating this - Internet explorer's temporary internet file cache (somehow) manages to create files with 254+ character paths. I was writing a (python) tool that needed to do some directory walking, and I'd get cryptic errors whenever it got to the temporary internet files; I could never actually handle them, I could only say something like "Hey! There's an evil filename over here somewhere!".

*1 I think

*2 That is, for a closed-source, proprietary, filesystem.

avogelba commented 10 years ago

Original comment by Jim Babka (Bitbucket: jimbabka, GitHub: Unknown):

I never knew about short name creation. I'll try it tomorrow when I'm back in the office.

As for file sizes, the vast majority of these files are under 10K (including Java source and class files, HTML, JavaScript and CSS files). There are a large number of big zip files (300M to over 1G), plus some DB2 backup files that are over 1G. The overall size is over 300G.

As for nesting levels, there are some very deep (around 25 directories deep). In fact, if I'm not careful to keep my top directory names short, I run afoul of a 254 character path length limit that some windows utilities have (e.g. Zip file exploring).

avogelba commented 10 years ago

Original comment by Alexander Riccio (Bitbucket: alexander_riccio, GitHub: Unknown):

Short name creation can tremendously (exponentially) slow directory walking. Have you tried turning it off?

Also: how large were these files, and how deeply were they nested? I'm investigating WinDirStat's performance in depth.

avogelba commented 10 years ago

Original comment by Jim Babka (Bitbucket: jimbabka, GitHub: Unknown):

When WinDirStat was completely failing, there were over 7.5 million items, including 6 million files and 1.5 million subdirectories. I have deleted a lot, and now have it down to 4.3 million files and over 1 million subdirectories. Now, it takes WinDirStat over an hour to count up the files, but then it hangs for 30 minutes while it is apparently trying to render the graphical representation. It will eventually come back and show me something, but if I then make any change that causes it to refresh (e.g. deleting a directory), it's hung for another 30 minutes. During this time, windirstat.exe is completely using up one of my 8 CPUs.

avogelba commented 10 years ago

Original comment by Alexander Riccio (Bitbucket: alexander_riccio, GitHub: Unknown):

Compiling 1.1.2 with /LARGEADDRESSAWARE might be a viable workaround - how many files are on this drive??

daviddeleeuw commented 1 year ago

I have a large filesystem (NTFS 64 bit block, about 30 TB used, about 25 million files). When using Windirstat I get stuck at a little less than 10 Million. Tried to switch off unnecessary animations. Have loads of memory (32 GB). I dont need the graphics stuff, just try to identify large directorie-branches (with over 50000 files) that were not used over a year or so. Any settings, upgrades I missed ? David de Leeuw

avogelba / WinDirStats

WinDirStat runs out of memory #112