Why is Windows so slow?

Interestingly enough Joel Spolsky mentioned something related to the directory listing problem more than 10 years ago. See:

http://www.joelonsoftware.com/articles/fog0000000319.html

In Joel's opinion it is an algorithm problem. He thinks that there is an O(n^2) algorithm in there somewhere causing trouble. And since one does not notice the O(n^2) unless there are hundreds of files in a directory it has not been fixed.

I believe that is probably the problem with Windows in general. Perhaps there are a lot of bad algorithms hidden in the enormous and incredibly complex Windows code base and they are not getting fixed because Microsoft has not devoted resources to fixing them.

Linux on the other hand benefits from the "many eyes" phenomenon of open source and when anyone smart enough notices slowness in Linux they can simply look in the code and find and remove any obviously slow algorithms. I am not sure all open source software benefits from this but if any open source software does, it must certainly be Linux as it is one of the most widely used and discussed pieces of OS software.

Now this is total guesswork on my part but it seems the most logical conclusion. And by the way, I am dual booting Windows and Linux and keep noticing all kinds weird slowness in Windows. Windows keeps writing to disk all the time even though my 6 GB of RAM should be sufficient, while in Linux I barely hear the sound of the hard drive.

I don't think there's an O(n^2) algorithm in there. I just created a directory with 100,000 entries. Listing it (from Cygwin, no less, using 'time ls | wc') takes 185 milliseconds. The directory is on a plain-jane 7.2k 1TB drive, though of course it's hot in cache from having been created. 'dir > nul', mind you, is quite a bit slower, at over a second.

I think the fact that is hot in cache may have influenced things here.

You only did one test, so you have no idea what the complexity curve is. Do at least three tests, with 1000, 10,000 and 100,000 entries and graph the results. Three tests is still pretty skimpy to figure out what the curve is, so do tests at 10 different sizes.

Also, Joel's complaint was about the Windows Explorer GUI (specifically, opening a large recycle bin takes hours). Cygwin `ls` is using a completely different code path. Your experiment does suggest that Joel's problem is in the GUI code, though, and not the NTFS filesystem code.

Along the same line, I've never understood Windows' propensity to swap out the kernel. I might have tons of free memory and half my kernel is swapped out. In fact, I've never figured out how to get it not swapped out, no matter how much memory I put in.

I just wish the "many eyes" phenomenon worked equally well for device drivers.

Unfortunately most of the drivers are in the long tail of unpopular devices. This results in greatly reducing the average number of eyes per driver.

This has a double effect: there are less developers who can attempt to fix problems with a driver and second, the incentive seems smaller - make general I/O 0.5% faster and you're a hero of the public, fix a critical problem in an unpopular device driver and maybe 1 person notices.

You could try this (from an elevated command-prompt), but the general consensus is that it has a small (if any) effect:

reg add "HKLM\System\CurrentControlSet\Control\Session Manager\Memory Management" -v DisablePagingExecutive -d 0x0 -t REG_DWORD -f

Disable it with: reg add "HKLM\System\CurrentControlSet\Control\Session Manager\Memory Management" -v DisablePagingExecutive -d 0x1 -t REG_DWORD -f

More discussion here: http://serverfault.com/questions/12150/does-the-disablepagin...

The easiest way (if you have enough memory) is just disable the paging file.

For all you know you're seeing the HDD cache and not any kind of filesystem caching. evmar mentions SSD making a difference for workloads that should fit in RAM, which means HDD caching also would, for a very modest workload.

Exactly. I'm afraid this isn't a solvable problem. Device makers must be responsible for device drivers, open source or not.

Oh, the OS treeview is dreadful, everyone who's seriously coded on Windows knows that.

As to actual complexity curve (which, knowing what I do about NTFS, I'm fairly sure is O(n log n)), I don't really care about it; since it hasn't shown up in a serious way at n=100000, it's unlikely to realistically affect anyone badly. Even if 1 million files (in a single directory!) took 18.5 seconds, it wouldn't be pathological. Other limits like disk bandwidth and FS cache size seem like they'd hit in sooner.

The OP specifically mentions doing it twice to make sure the cache is hot: "Do it twice and time how long it takes. The reason to time only the second run is to give the OS a chance to cache data in ram"

I know it's not the HDD cache. I can monitor physical disk requests vs logical filesystem requests (diskmon vs procmon). But I repeated it anyway on my SSD, and the results are the same.

I think the recursive search is the thing that is broken.

Which version of Windows? In my experience certain things will freeze up explorer XP/Server2k3 effectively indefinitely while on Vista/7/Server2k8 there is a progress meter and everything is stable.

"Linux on the other hand benefits from the "many eyes" phenomenon of open source and when anyone smart enough notices slowness in Linux they can simply look in the code and find and remove any obviously slow algorithms."

More like Linux benefits from "many budgets and priorities". If someone at Microsoft spots an obviously slow algorithm, they may not be allowed to fix it, rather than working on whatever they're supposed to be working on, which probably doesn't include "fixing shipped, mature code that pretty much works in most cases."

On the Linux side, someone can decide it's really freakin' important to them to fix a slow bit, and there's little risk of it being a career-limiting move.

Generally, they are. They get their Windows compatibility certification and everything.

Oh, wait, you mean for Linux? Good luck with that. The sad thing is that either providing drivers for Linux or providing detailed enough specs that drivers can be written by the OSS community offers little for no payback for the effort. As a Linux user, I feel lucky that any hardware manufacturers even acknowledge people might be running something other than Microsoft.

When you're in bed with Microsoft, you probably have even more reasons to blow off the OSS community. The sweaty chair-chucker wouldn't like it, and you don't want to get him angry. You wouldn't like him when he's angry.

Since we're talking about optimization, if you're on a SSD you should disable prefetching--which is essentially a technique for older (read: shittier) computers.

Windows 7 x64. But I am talking about the command-line, not the UI. The UI controls (whether in Explorer or in other apps) generally don't react well to non-human sized input.

That's what they used to say about IE vs the open source community. But somehow, programmers' nature finds a way...