I've been thinking about how you'd go about efficiently sorting data 
stored on magnetic tape.

The key thing about tape is that it's sequential. We'll also assume that 
it holds more data than you can actually fit into main memory, as was 
the case in the days of old.

You can of course wind tape forward and backwards, and presumably with a 
sufficiently expensive tape transport system you can do this quite 
accurately. You can't do it particularly fast, however. Fundamental 
limits such as friction prevent that. (If you wind the tape fast enough, 
it'll overheat and melt.)

Presumably the tape transport system isn't accurate enough to do an 
in-place sort on tape. (Even if it is, the seek times are probably going 
to be prohibitively high if we want to read a record, rewind one record, 
re-record that record, read the next record, rewind one record, 
re-record this record, etc.) This limits us to tape-to-tape operations.

So, we have this set of constraints:
- We have so much data that only tape is large enough to hold it.
- Tape provides efficient sequential access, but has very long seek times.
- Moving data around on a single tape is infeasible.
- Tape is presumably much slower than main memory for read/write access 
(in addition to the huge seek latency).
- Only a finite number of records will fit into main memory at once.
- We want to sort our data in the smallest amount of wall-clock time.

So what are our options here? Well, since in-place sorting is basically 
out of the question, we're going to need at least two tapes, an input 
and an output. We *could* do something like read one tape, bubble-sort 
it, and write the results onto the other tape. Then rewind both tapes, 
swap input and output, and start again. Repeat until the data is sorted.

Trouble is, this requires both tapes to be rewound approximately O(n) 
times. If we're sorting a few million records, we're going to have to 
read the tape end-to-end and rewind to the beginning a few million 
times. Since presumably even just rewinding a big reel of tape is quite 
a timely operation (never mind winding it past the pick-up head slowly 
enough to read it), this is going to take a rather drastic amount of time.

At the opposite end of the spectrum, we could read as much data as 
possible into main memory, sort that chunk completely (which is just a 
normal in-memory sort, using any algorithm we like), and write the 
sorted block out to tape #1. We then read in the next chunk, sort, and 
write to tape #2. We continue in this fashion until there is no more 
data to read. Finally, we rewind all the tapes and do a multi-way merge 
operation.

Trouble is, if we have 1 million records to sort and only 1 thousand 
records fit in memory, we're going to need 1 thousand tapes and tape 
drives. (!) This, presumably, is prohibitively expensive.

So far, we have a 2-tape bubble-sort, which is absurdly slow, and an 
unlimited-tape merge-sort, which requires a ridiculous number of tape 
drives.

Let's back up for a moment here. What fundamental operations can we do?

- We can read a chunk of unsorted data into memory and completely sort 
it. Since main memory is fast and has random access, we can use any 
algorithm we like for this. And presumably this part of the task is so 
much faster than tape access that we can regard it as almost 
instantaneous by comparison.

- We can read data from one or more input tapes and write it out to one 
or more output tapes.

Looking at the second item, this basically amounts to allowing splits 
and merges:

- We can take unsorted input data and split it into several output 
ranges, as per one iteration of a quick-sort.

- We can take several tapes of sorted data and merge it together onto a 
single output tape, as per a single iteration of merge-sort.

Trouble is, both quick-sort and merge-sort are recursive algorithms, and 
to implement them on tape would require an unbounded number of tapes, 
which isn't really practical. Even if you can somehow arrange the data 
onto tapes so that you can fit lots of different tapes through only a 
limited number of tape drives, you're still going to spend more time 
rewinding tapes than actually doing useful processing.

This is where my musings on the min-heap come in. I was thinking, you 
could take an input tape, read data off of it into a min-heap, keep 
reading until main memory is full, and then remove the top item (the 
minimum element) and put it onto the output tape. Something like this:

   REPEAT
     READ NEXT RECORD FROM INPUT TAPE
     INSERT INTO MIN HEAP
     IF HEAP IS FULL
       REMOVE MINIMUM RECORD
       WRITE ONTO OUTPUT TAPE
   UNTIL END-OF-INPUT-TAPE
   REPEAT
     REMOVE MINIMUM RECORD
     WRITE ONTO OUTPUT TAPE
   UNTIL HEAP-IS-EMPTY

If you think about it, it's sort of like a bubble-sort, but instead of 
comparing just two items, you compare as many as you can hold in memory 
at once. Like a bubble-sort, it has the property that the "stones" fall 
to the bottom very quickly, but the "bubbles" rise to the top quite 
slowly. (If the heap holds N items, each bubble can only rise a maximum 
of N slots further up the tape on each pass.)

So it's *like* a bubble-sort, but better. N times better, actually 
(where N is the maximum size of the heap). Indeed, for a 2-element 
min-heap, it degenerates into a real bubble-sort, of the kind we all 
know and hate.

Even so, a bubble-sort over N elements requires up to N passes, whereas 
this new hybrid sort requires up to N-H passes, where H is the maximum 
heap size. For a million items and a thousand-element heap, that's not 
much of a reduction, actually. (It's 0.1% faster.)

What you can do is split the input data into many smaller datasets, and 
thus reduce the work required to sort them. You could read the input 
tape and partition it onto, say, 10 output tapes, and then repeatedly 
heap-bubble the 10 tapes in parallel until they're all sorted, and 
finally scan them all to merge them back together. That would result in 
roughly a 100-fold speed-up in the sorting process.

That got me thinking about how you determine the optimum pivot values. 
Ideally you'd want to look at the histogram of the data and move the 
pivot values until there's roughly the same amount of data between each 
pair. So first you'd need to scan the input tape to find the min and max 
values, and then maybe split the range between those into, say, 1000 
buckets, rewind the input tape and count how many items fall into each 
range.

Trouble is, the data might be clumped very unevenly. So maybe what we 
need to do is

1. Scan for the min and max values.
2. Linearly divide up the space and scan for a 1000-point histogram.
3. Partition the resulting histogram into 10 equal-looking ranges, split 
each new super-range into 100 sub-ranges, and scan the tape a third time 
for another 1000-point histogram (but now with unequal bucket sizes to 
hopefully better sample the data).

Maybe 2 histogram passes isn't enough? Maybe the process could be made 
iterative, such that it repeats until the bucket edges stop changing? 
Perhaps there should be special handling for particularly sparse 
buckets? Come to think of it, does each of the final computed buckets 
even need to be a contiguous range? The sorting algorithm doesn't 
require that - but maybe the storage requirements of keeping track of 
all the buckets makes it necessary...

Then again, all this assumes that we're going to carefully split the 
data and then just concat-merge it. You could of course do it the other 
way around - and *that* requires no such special processing. Just take 
the input data, copy it onto multiple tapes in any old fashion that you 
fancy, and do the careful bit when you come to merge the sorted results 
back together.

Ideally we want to do either a quick-sort or a merge-sort. But these 
both require recursive splitting or merging. We don't have enough tapes 
for that. We could put all the fragments onto the same tape, but now 
we're in danger of requiring a lot of seeking to find the data we want, 
and that'll be slow.

I did think to myself that you could begin by reading unsorted chunks, 
sorting them in-memory and writing them to tape. You now have a tape of 
N-item sorted chunks. You could then read N/2 records from the first 
chunk, seek forward N/2 records, and read N/2 records from the second 
chunk, and write the N merged results to the output. Repeat until you 
get to the end of the input tape, and then rewind it to the beginning 
and go about merging the second halves of all the chunks.

Trouble is, you're going to have to end up seeking in bigger and bigger 
steps with each subsequent pass. Eventually it's going to get just too slow.

Then I though to myself, why not have the chunks on two input tapes? 
That way, if the chunks are already sorted, you don't even need to hold 
the whole chunk in memory at once. You can just merge them as they read 
off the two input tapes, and write the results onto the single output tape.

Single output tape. Yeah, that means that after the first merge cycle, 
you now have all your data on one tape, and you've going to have to 
start seeking around again. Except that, wait, you could have two output 
tapes, and just alternate between then as you're writing. So all the odd 
chunks go on one tape, and all the even chunks go on the other. And then 
you can rewind everything and start again in the opposite direction, 
with bigger chunks. Repeat until you're done.

This approach requires you to have 4 tapes / tape drives. It also 
requires the tapes to be read / rewound / written / rewound 
approximately log N - log C times (where C is the initial chunk size - 
presumably the largest chunk size you can sort in-memory). That doesn't 
sound too bad. Better still, there's now no seeking at all. Just 
sequential reads and writes.

Still, when a pass finishes, all four tapes are going to have to rewind 
to the beginning before the next pass can start. The computer itself is 
going to be doing nothing while we wait for the tapes to rewind. Is 
there some way that we can add a modest number of additional tape drives 
and keep the computer busy?

You could have two sets of 4 tapes, but they're all going to tend to end 
up rewinding at the same time. That doesn't seem to buy much.

You could have 4 "big" tapes and 4 "small" tapes, where you basically 
put half as much data onto the small tapes. At any time you're reading 
from two tapes and writing to two other tapes. When you're reading from 
two big tapes, you write half the data to two small tapes, rewind them 
and write to the other two small tapes while the first two small tapes 
are rewinding. By the time you've finished reading the two big tapes, 
the first two small tapes should have finished rewinding, so while the 
other tapes are rewinding, the two small tapes act as input and the two 
hitherto unused big tapes act as output. By the time you get to the end 
of the small tapes, the other two small tapes should have finished 
rewinding.

By this arrangement, I think you can keep the machine running 
constantly. There's always some tape rewound and ready for reading, and 
some other tapes rewound and ready for writing.

It seems that by adding more tape drives, it ought to be possible to get 
the job done even faster. I need to go meditate on this...

Post a reply to this message