Hehe interesting. I have to read up on the knapsack problem. You know what the worst part is? I actually am a CS grad LOL.
Ouch
What strikes me as odd is that with Windows, you can gradually notice a degradation of performance over time as the file system gets more and more fragmented. However using Linux at work and using various tools when doing builds and such, I notice the times are always the same yet in Windows it gets slower and slower and slower over time, till one day I cannot stand it anymore and I make it a point to defrag over the weekend. I wonder if disk fragmentation is not the cause of that drop in performance over time then what is?
Simple way to verify:
Defragment the disk, then see if the performance is back. If not, fragmentation was not the problem.
My personal experience with FreeBSD is that performance is so utterly horrible compared to Windows to begin with, that fragmentation is not really a factor in the total performance.
Fragmentation DOES happen on UFS (the fsck tools can report the fragmentation ratio), you just can't do anything about it.
Thing is just, I have this box with a disk that is capable of about 60 mb/s in Windows, but with FreeBSD I get about 10 mb/s.
Different filesystems may have different strategies for allocation, but it's just impossible to have a fragmentation-free system. Fragmentation will ALWAYS happen when you delete one file, then re-use that space for a new file of different size.
But actually it's not the filesystem itself, but the allocation strategy. It's perfectly possible to continue using NTFS, but change the allocation strategy, so you will get a different fragmentation profile. I wouldn't be surprised if Microsoft tweaks this strategy every now and then, so eg XP may have way different fragmentation issues than Windows 7, even though they both use NTFS, and can access eachothers partitions.