Quote:
Originally Posted by
DGPickett
I suppose your could write a sort that used a tournament space as big as available ram to write temp files each with one sorted sequence, and then all the files can be merged by sort -m, or a tree of sort -m's, an always 2 pass sort.
The idea of the progressive merge sort was to live with the cache and RAM limits dynamically without knowing where they are. And in real life, sometimes the amount of available RAM or CACHE varies with other activities, so it is not good to have a fragile fit.
BTW, the tournament write can write strings far longer than the tournament table size. If the input was already sorted, it would be written as one string. You write the smallest item >= the last item written, so with random data, I am guessing a 64K leg tournament would write 96K items a sorted string, but my math is a bit weak. Someone show me up.
If you wanted to code it in a single process, you could write all sorted strings to one temp drive, write the starting offsets of each sorted string on a second temp file and fix the tournament size at something fitting comfortably within upper cache. The input file could be mmap()'s so actual records to be written are in RAM, just offsets in the tournament table. After the first pass, you know you have N strings to merge, so mmap() the output files and merge them. Since there are just 3 files open at a time, no fd limit woes. The mmap() lets your read from N different points in the first temp file. The one temp file write of all input data creates a huge change in working set size. Writing just one main file at a time minimizes write buffer cost. The original reading, although through mmap() page faults, is generally sequential. The second read uses just N-2N pages to buffer the sequential string reads. The latency is even pretty low, essentially 0 from last read to first write.
I may be dense, but I don't see the point in such suggestions. My files are huge, much bigger than any SSD I can afford. No matter how you cut it, the file won't fit in RAM or my SSD drive, and there's going to be a lot of comparison, and a lot of disk head motion in the process of the sort. I'm using GNU sort because I have it and it works out of the box in such cases.
Having played around with my test file long enough to become familiar with the basics, and get a more accurate picture of how sort works, I sorted my 1.4TB file starting noon yesterday using sort's default settings other than directing temporary files to an empty spare drive.
It started at around 12:30 PM yesterday finished at 9:37 AM today. I guess I had misread the code that computes the buffer size; I was expecting 2GB temporaries, and in fact they were more like 11.24 GB, and there were 117 such files except that the last one was shorter. It took around 4 minutes to create the early ones, and they were all done in about 8.5 hours. Then 112 of them were merged in 7 batches of 16, creating files of 179.8 GB each, taking about 7.5 hours. Finally the 7 large and the 5 remaining small temporaries were merged into the output in about 6 hours.
for comparison, just copying the file to the temp drive, and then to the result drive took 6.6 hours, compared to about 21 hours for the sort.
I'm hoping to cut hours off that time by setting a bigger batch_size and not merge any of the data twice. I may also fool with the buffer_size to see if there's a way to reduce compute overhead. I'll start by cutting temporary size in half and doubling the batch size.