This is actually an interesting topic in both theory and practice.
When you have several "holes" of free space to choose from, which hole
should be chosen? This problem occurs everywhere you have computers:
Disk, memory, heap management, ...
If you have complete knowledge of the future --- if you know the
individual sizes of articles to come in the future --- then there is a
way to choose the best hole. In some other applications, this
knowledge of the future is available, so that's that. Not Yarn, of
course.
In simple terms, there are several obvious options. Best fit ---
choose the smallest hole that fits the article. Worst fit --- choose
the largest hole (and of course, the unused portion of the hole becomes
a new hole; this also applies to best fit). First fit --- choose the
first one you encounter in scanning the space, as Yngvar has described.
Random --- pick one from random.
It turns out that results are a bit counter-intuitive. I was taught
that someone did some experiments, and the result, best fit is the most
inefficient, worst fit is somewhat the best.
-- Albert Y.C. Lai trebla@io.org http://www.io.org/~trebla/