Best bang for the buck

A disk is full. Which folders do you clean up first, and when do you stop? Sort them by size, add them up, and stop at the point on the curve nearest the origin.

Whose idea this is. The method on this page, the running-total curve with its y-axis turned over and the point nearest the origin taken as the cutoff, is the author's own (Michael Carnright), worked out and first written as a script for clearing space on crowded drives. The script here, bang_for_the_buck.py, is a fresh implementation of it. The last section, Related ideas, is other people's work and is there for comparison.

The problem

When a drive fills up, the space is almost never spread evenly. A handful of folders hold most of it and a long tail of small ones hold the rest. Cleaning up a folder costs roughly the same effort whatever its size: you have to look at it, decide, and archive or delete it. So the first few big folders buy a lot of space each, and every folder after that buys less. Somewhere along the list it stops being worth it. The question is where.

The method

Measure every folder directly under the full mount point or directory and sort them largest first: s₁ ≥ s₂ ≥ … ≥ s_N, with total T.
Take the running total S_k = s₁ + … + s_k, the space freed by cleaning up the first k.
Scale both axes to 0–1 and turn the y-axis over, so it counts the space still left:

x_k = k / N y_k = 1 − S_k / T d_k = √(x_k² + y_k²)

The curve now runs from (0, 1), nothing done and everything left, to (1, 0), everything done and nothing left. The origin is the ideal: no effort and no space left, which no real drive reaches.
The point on the curve nearest the origin, by Pythagoras, is the cutoff. Clean up the first k folders and stop.

Because both axes are scaled, the answer doesn't depend on whether the drive is gigabytes or petabytes, or whether it holds twenty folders or twenty thousand. It only depends on how uneven the sizes are. If every folder is the same size the curve is the straight line from (0, 1) to (1, 0), and its nearest point is halfway: there is no shortcut, so do half and look again. The more uneven the sizes, the deeper the curve bows towards the origin and the earlier the cutoff.

Try it

Folders: Unevenness:

Folder i gets size 1 / i^a with a little noise; a is the unevenness. At 0 every folder is the same size.

Blue: the running-total curve, y turned over. Orange: the quarter circle through the nearest point; nothing on the curve lies inside it. Red: the cutoff.

Running the script

bang_for_the_buck.py needs Python 3 and nothing else. It measures on-disk size, does not follow symbolic links, and skips anything it may not read.

python3 bang_for_the_buck.py /path/to/full/drive        # folders and files directly in it
python3 bang_for_the_buck.py -f /path/to/full/drive     # every file under it instead
python3 bang_for_the_buck.py --all /path/to/full/drive  # the whole list, cutoff marked
python3 bang_for_the_buck.py --csv /path/to/full/drive  # the curve as CSV, for plotting

Run on /usr/share on a Mac it printed:

   #      size  running  name
   1     65.0M    24.6%  tokenizer/
   2     48.6M    42.9%  firmware/
   3     26.6M    53.0%  morphun/
   4     23.7M    62.0%  vim/
   5     21.3M    70.0%  man/
   6     15.8M    76.0%  icu/
   7     12.7M    80.8%  langid/
   8     10.4M    84.7%  terminfo/

Act on 8 of 37 entries (21.6%) to reach 224.2M of 264.5M (84.7%).

Eight folders out of thirty-seven hold 85% of the space. By this measure the ninth isn't worth the effort of looking at it.

Related ideas

None of this section is the author's. These are better-known ideas that land in the same place from other directions.

The Pareto principle. The "80/20 rule", named by Joseph Juran after Vilfredo Pareto's observation about the spread of land ownership: most of an effect comes from a few causes. The curve here measures how true that is of one particular drive, and says where the few end.
The Lorenz curve. Economists plot the cumulative share of a total against the cumulative share of the population to show inequality. Sorted largest first and turned over, that is the curve on this page; how far it bows is what the Gini coefficient measures.
The ROC curve's nearest corner. One standard way to choose a cutoff on a receiver operating characteristic curve is to take the point nearest the perfect corner (0, 1): the same "distance to the ideal point" rule.
Knee and elbow finding. Choosing the number of clusters by the "elbow" of a curve is common in data analysis, and Satopää, Albrecht, Irwin and Raghavan's Kneedle algorithm (2011) finds knees by scaling both axes to 0–1, as here, then taking the point furthest from the straight line between the ends rather than nearest the origin.