The Speed Disk algorithm

[OS923]

I frequently read that Speed Disk uses a patented algorithm. (I have great difficulty finding that patent.) How does it work?

[IIO]

it might be a form of block sort algo, but i doubt that anyone can tell you by heart.

[OS923]

UltraDefrag works like this: it tries to move a file after the last relocated file at the start. If something is in the way, then this is moved to the end of the free space.

Speed Disk is totally different. It moves many file fragments at the same time. These fragments can be moved several times while the files remain fragmented.

I think that I should start with a simulation that is merely a drawing where the blocks are seen as a puzzle that has to be solved, like the towers of Hanoi.

[IIO]

you think you could tell the algo from watching its GUI?

[OS923]

Yes, it looks like recursion and range locking.

I'll explain it with goto instead of recursion:

1. Scan the directory.

2. Calculate the end state.

3. Search all fragments whose final destination is in the current empty space.

4. If there are such fragments then move them and go to step 3.

5. Search all loops like A has to be moved to space that is taken by B, which has to be moved to space that is taken by C, which has to be moved to space that is taken by A.

6. If there are such loops then move the smallest fragment in each loop to somewhere in empty space and go to step 3.

7. Search all overlapping source and destination like A has to be moved to space that is taken by A.

8. If there are such fragments then shift them like a blockmove of overlapping source and destination.

The unsolved problem is now in step 6 that there may not be an empty space that can contain some fragment that has to be moved. Then the fragment has to be split in smaller parts, but there may not be enough space in the extents records to contain a description of those fragments. In most cases you could select the file in the loop that has unused space in the extents record but this won't always be possible.