3 ms·

What is the optimal algorithm for defragmentation? Some sort of sort?

by melony 5y ago

TacticalCoder 5y ago
Curious too here! I wouldn't be surprised if there was some kind of a dynamic programming algo similar to 0-1 knapsack.
maxerickson 5y ago
What is being measured? You've got contiguous space, speed, total time, wear.
jaimex2 5y ago
Bubble sort obviously.
LeoPanthera 5y ago
There wasn't just one. Some defrag tools from the days of DOS would actually let you pick. A commonly used one was to try to place the contents of the same directory adjacent to each other on the disk surface, to minimize latency. I can't remember which it is, but either the center or the outside edge of a disk read faster, so another common trick was to place all the files necessary to boot the system there, to reduce boot times.
- rmahan 5y ago
  Angular velocity of the edge of the plate is higher, so it is faster than the center. However this only applies to plates that have the same data density on the inside and outside rings.
chiph 5y ago
Depends on the drive technology. For SSDs you want to avoid extra writes as those wear down the cells. For traditional hard drives you can consolidate empty space to reduce cluster waste, or go for broke and just place everything in order (most fun to watch). Probably the best way would be to group frequently accessed files near each other so the heads traveled less distance. So far as the algorithm, what I observed is the program would look at how much room was needed to place the next file, then clear that many blocks out of the way by moving them to the end of the drive. Then copy the blocks for the file to form a contiguous stretch of blocks. And repeat. You wanted to have as much free space as the largest file (plus a little), but I think some of them were able to move large files in pieces. Back in the days of Windows NT we had a network share with 8+ million files on it (a lot for the time) and we had a serious fragmentation problem, where it could take a second or more to read a file. Most of the defraggers just gave up, or weren't making any progress, but we eventually found one that worked (PerfectDisk, maybe?)
magicalhippo 5y ago
Obviously you want to consolidate fragments. But especially for HDDs there's different tradeoff of placing stuff near the outside compared to towards the center, which also depends on workload ie streaming vs random access, heavy read/write vs mostly read-only. With PerfectDisk[1] you can decide how you wanted the disk laid out. And it did make a measurable difference in the cases I tested. For SSDs fragmentation is less of an issue, but it's not completely gone. Especially on Windows with NTFS, where one can run into issues with heavily fragmented files[2][3]. We actually have this very issue with a client in production these days, due to the DB log file causing heavy fragmentation. [1]: https://www.raxco.com/home/products/perfectdisk-pro https://www.raxco.com/home/products/perfectdisk-pro [2]: https://support.microsoft.com/en-us/topic/a-heavily-fragmented-file-in-an-ntfs-volume-may-not-grow-beyond-a-certain-size-da1c0dfd-a5a1-90b4-4bf7-b65b13ef9d35 https://support.microsoft.com/en-us/topic/a-heavily-fragment... [3]: https://support.assurestor.com/support/solutions/articles/16000104076-the-requested-operation-could-not-be-completed-due-to-a-file-system-limitation https://support.assurestor.com/support/solutions/articles/16...

What is the optimal algorithm for defragmentation? Some sort of sort?

by melony 5y ago

What is the optimal algorithm for defragmentation? Some sort of sort?

TacticalCoder 5y ago

Curious too here! I wouldn't be surprised if there was some kind of a dynamic programming algo similar to 0-1 knapsack.

maxerickson 5y ago

What is being measured? You've got contiguous space, speed, total time, wear.

jaimex2 5y ago

Bubble sort obviously.

LeoPanthera 5y ago

There wasn't just one. Some defrag tools from the days of DOS would actually let you pick. A commonly used one was to try to place the contents of the same directory adjacent to each other on the disk surface, to minimize latency. I can't remember which it is, but either the center or the outside edge of a disk read faster, so another common trick was to place all the files necessary to boot the system there, to reduce boot times.

rmahan 5y ago
Angular velocity of the edge of the plate is higher, so it is faster than the center. However this only applies to plates that have the same data density on the inside and outside rings.

chiph 5y ago

Depends on the drive technology. For SSDs you want to avoid extra writes as those wear down the cells. For traditional hard drives you can consolidate empty space to reduce cluster waste, or go for broke and just place everything in order (most fun to watch). Probably the best way would be to group frequently accessed files near each other so the heads traveled less distance. So far as the algorithm, what I observed is the program would look at how much room was needed to place the next file, then clear that many blocks out of the way by moving them to the end of the drive. Then copy the blocks for the file to form a contiguous stretch of blocks. And repeat. You wanted to have as much free space as the largest file (plus a little), but I think some of them were able to move large files in pieces. Back in the days of Windows NT we had a network share with 8+ million files on it (a lot for the time) and we had a serious fragmentation problem, where it could take a second or more to read a file. Most of the defraggers just gave up, or weren't making any progress, but we eventually found one that worked (PerfectDisk, maybe?)

magicalhippo 5y ago

Obviously you want to consolidate fragments. But especially for HDDs there's different tradeoff of placing stuff near the outside compared to towards the center, which also depends on workload ie streaming vs random access, heavy read/write vs mostly read-only. With PerfectDisk[1] you can decide how you wanted the disk laid out. And it did make a measurable difference in the cases I tested. For SSDs fragmentation is less of an issue, but it's not completely gone. Especially on Windows with NTFS, where one can run into issues with heavily fragmented files[2][3]. We actually have this very issue with a client in production these days, due to the DB log file causing heavy fragmentation. [1]: https://www.raxco.com/home/products/perfectdisk-pro https://www.raxco.com/home/products/perfectdisk-pro [2]: https://support.microsoft.com/en-us/topic/a-heavily-fragmented-file-in-an-ntfs-volume-may-not-grow-beyond-a-certain-size-da1c0dfd-a5a1-90b4-4bf7-b65b13ef9d35 https://support.microsoft.com/en-us/topic/a-heavily-fragment... [3]: https://support.assurestor.com/support/solutions/articles/16000104076-the-requested-operation-could-not-be-completed-due-to-a-file-system-limitation https://support.assurestor.com/support/solutions/articles/16...