UNIX for Advanced & Expert Users

Hi.

You may wish to look over the documentation for msort. It has numerous options that standard sort does not. Some might be useful for your task:

Code:

msort - sort records in complex ways
http://billposer.org/Software/msort.html
http://freecode.com/projects/msort

However, for tasks that can be done with both:
Best wishes ... cheers, drl

I'm pretty sure that the buffer-size parameter controls only pass 1, which is where actual sorting occurs. It controls the size of the first set of temporary files. All subsequent passes are merges. Moreover, the default on my system is similar to what I get when I specify 4g, and is distinctly sub-optimal.

In testing, the gain was real but not big. The elephant in the room here seems to be the number of passes, and I/O time is a large percent of the total. While threading improves overlap, they're still competing for use of the same input and output files and directories.
Fair enough. But RAM is already 32GB, which maxes out my motherboard. Input, temporaries and output are already on three separate drives. Swap is separate and on an SSD, but I don't think I'm using it. So I'm squeezing out percentages. Fortunately, some of them are worth the effort; I'm already running about twice as fast as the built-in defaults, which have over-large buffers and not enough streams in a batch.

I know. I am concerned you might be making your buffers too large -- ideal settings for 1 process would be twice what your computer can handle when doubled. Halve the buffer size and number of files every time you double the number of threads. Individually their efficiency could go down a bit, but collectively they can get masses more work done if you have enough cache to keep up with them.

You might look into increasing the writeback time on your temp partition. Spending all your I/O time writing changes that are going to be invalidated 60 seconds later could be a waste, let the disk cache do the thrashing.

Which means leaving some RAM for disk cache of course. Using all available RAM forces it to do more I/O. 50/50 for sort vs cache might be a good split off the cuff.

I wonder if your SSD might be a better temp folder than swap -- like you say, you're not using it, and forcing your system to eat into swap can really interfere with caching. An ssd could support a much larger number of streams, potentially.

Well defragged disk helps, as sort is doing sequential passes merging data. As a pattern, sequential is the fastest, if the adjacent file pages are really adjacent disk pages.

If sort has a big RAM footprint, it can move out of place items farther on each pass, as each pass reads from all sorted input streams into RAM and the smallest <= last is written to the newest temp output.

Fast sort space is critical, too, more critical than fast swap, but both are nice.

My SSD is nowhere near big enough for /tmp, so that is assigned to a dedicated 2TB SATA drive. It would be large enough for these tests on a 14GB file, but my real workload has TB-sized inputs, so I test accordingly.

The tests seem to confirm that my buffers are too large. I was testing with 1 GB and larger, based on what the default settings are. But I'm going to be redoing the tests with smaller buffers and larger batches. So long as I can keep it down to 2 passes through the data, it may be much better that way. I wouldn't be surprised to find the best arrangement is 2,000 512-megabyte temporary files merged in a single pass. It all depends on how smart the merge is. If it bubble-sorts, of course, I'm sunk.

I'll have to research writeback time. However, when my input file is larger than RAM, I would expect all temps to be flushed before they get used.

---------- Post updated at 07:30 AM ---------- Previous update was at 07:19 AM ----------

Defragged? I'm not sure how to do that on Linux, so I am using a fresh 2-TB drive formatted ext4 and directing sort to use it for temporaries. It's otherwise empty.

I've got 32 GB RAM and a 64-bit CPU. That's big enough for the whole test file, but the parameters to sort don't let it work that way.

Sort space vs swap space? Not sure, but I guess you mean disk. They're all SATA-III, 7200-RPM.

---------- Post updated at 08:00 AM ---------- Previous update was at 07:30 AM ----------

Thanks for the pointer. I had never seen msort. A quick look at the documentation makes it clear that for the current task, GNU sort will be just fine, but I'll keep msort in mind.

ext4 partitions are relatively easy to defrag, being designed with runtime defragmentation in mind (yes, runtime -- no need to unmount) via the e4defrag utility. There's no point defragging an empty partition, but check that your input and output partitions aren't a mess after all this testing. The process of merge-sorting doesn't work that way. No matter how big your buffers are, it has to do the same number of merges on the same number of elements of the same sizes, nearly all of them tiny... Starting with billions of 2-element merges, half the number of 4-element merges, etc, etc, etc. (A little oversimplification, but the merging options don't substantially change this.) That's why pushing buffers to ridiculous sizes is so little help -- they're nearly always dead weight except for the final merge, when it's never going to be big enough to matter anyway.

Nice to know. I tried e4defrag and it showed a fragmentation score of 0 on all directories.

I'm still a bit new to this, even after peeking at the source code. But it seems to me that there are two distinct phases to GNU sort. Both are merge sorts, but there's a big difference between merging in RAM and merging disk files. The main point of my optimizing effort turned out to be minimizing the number of file merges. Here's how I think of it now:

If all of the data can fit in the specified buffer, no temporary files will be created, and the output of the single in-RAM merge will go to the output file.

Otherwise, buffer-loads of data will be merged in RAM, and output to temporary files. There will be at least 2 of these, and perhaps a great many. These will be merged <batch-size> files at a time, with all the I/O time you'd expect. It's therefore desirable to ensure that no more than <batch-size> temporary files are created. If that's impossible, then limit it to the square, or even the cube of that number. Both buffer-size and batch-size affect the achievement of these goals.

Of course, even this is an oversimplification. It ignores effects of the TLB, of the L1 and L2 caches, and the kernel's buffer cache. Thus my interest in measuring actual times.

This is not going well, and I don't know why. Successive runs report quite different times. It's true the system is used for other things, but not heavily -- it's all my personal use. This is showing up in elapsed time, but not much in either system or user time. Odd. Moreover, the results of the second runs were consistently worse than the first. I'm trying third runs now.