4 ms·

Interestingly enough Joel Spolsky mentioned something related to the directory listing problem more than 10 years ago. See: http://www.joelonsoftware.com/artic

by hristov 15y ago

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 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.

prewett 15y ago
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.
- jstclair 15y ago
  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-disablepagingexecutive-registry-change-have-any-actual-effect http://serverfault.com/questions/12150/does-the-disablepagin... The easiest way (if you have enough memory) is just disable the paging file.
  - gospelwut 15y ago
    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.
fauigerzigerk 15y ago
I just wish the "many eyes" phenomenon worked equally well for device drivers.
- praptak 15y ago
  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.
  - fauigerzigerk 15y ago
    Exactly. I'm afraid this isn't a solvable problem. Device makers must be responsible for device drivers, open source or not.
    - ConceptJunkie 15y ago
      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.
      - mdda 15y ago
        That's what they used to say about IE vs the open source community. But somehow, programmers' nature finds a way...
barrkel 15y ago
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.
- hristov 15y ago
  I think the fact that is hot in cache may have influenced things here.
  - barrkel 15y ago
    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"
- prewett 15y ago
  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.
  - barrkel 15y ago
    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.
jonhendry 15y ago
"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.

by hristov 15y ago

prewett 15y ago

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.

jstclair 15y ago
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-disablepagingexecutive-registry-change-have-any-actual-effect http://serverfault.com/questions/12150/does-the-disablepagin... The easiest way (if you have enough memory) is just disable the paging file.
- gospelwut 15y ago
  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.

fauigerzigerk 15y ago

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

praptak 15y ago
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.
- fauigerzigerk 15y ago
  Exactly. I'm afraid this isn't a solvable problem. Device makers must be responsible for device drivers, open source or not.
  - ConceptJunkie 15y ago
    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.
    - mdda 15y ago
      That's what they used to say about IE vs the open source community. But somehow, programmers' nature finds a way...

barrkel 15y ago

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.

hristov 15y ago
I think the fact that is hot in cache may have influenced things here.
- barrkel 15y ago
  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"
prewett 15y ago
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.
- barrkel 15y ago
  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.

jonhendry 15y ago

"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.