On Mon, Mar 31, 2008 at 2:29 AM, Paul Eggert <[EMAIL PROTECTED]> wrote:
> Alas, that patch assumes C99, and we can't assume that quite yet.
> Also, it mishandles nmerge values that are "too large" (you'll get
> core dumps or worse on many hosts). That being said, it might be
> worth adding an option like that (it's a bit specialized, but it's a
> big performance win in some cases).
>
Ah, yes I see. Thanks for the feedback. Please allow me to take
another stab at this.
For the first issue: I've replaced the variable-length arrays in
mergefps with pointers xnmalloc'd storage.
For the second: I've introduced a small dedicated function for
validating and applying changes to nmerge. In addition to checking
bounds I also added a check for sort_size to ensure that it's still at
least MIN_SORT_SIZE after an nmerge adjustment.
Thanks again,
Bo
--- coreutils-6.10/src/sort.c 2008-03-29 18:55:54.000000000 -0400
+++ coreutils-6.10-modified/src/sort.c 2008-03-31 09:23:36.000000000 -0400
@@ -223,13 +223,13 @@
};
/* During the merge phase, the number of files to merge at once. */
-#define NMERGE 16
+#define NMERGE_DEFAULT 16
/* Minimum size for a merge or check buffer. */
#define MIN_MERGE_BUFFER_SIZE (2 + sizeof (struct line))
/* Minimum sort size; the code might not work with smaller sizes. */
-#define MIN_SORT_SIZE (NMERGE * MIN_MERGE_BUFFER_SIZE)
+#define MIN_SORT_SIZE (nmerge * MIN_MERGE_BUFFER_SIZE)
/* The number of bytes needed for a merge or check buffer, which can
function relatively efficiently even if it holds only one line. If
@@ -281,6 +281,10 @@
/* Program used to (de)compress temp files. Must accept -d. */
static char const *compress_program;
+/* Maximum number of files to merge in one go. If more than this
+ number are present, temp files will be used. */
+static int nmerge = NMERGE_DEFAULT;
+
static void sortlines_temp (struct line *, size_t, struct line *);
/* Report MESSAGE for FILE, then clean up and exit.
@@ -341,6 +345,7 @@
decompress them with PROG -d\n\
-k, --key=POS1[,POS2] start a key at POS1, end it at POS2 (origin 1)\n\
-m, --merge merge already sorted files; do not sort\n\
+ --merge-batch-size=N merge at most this many inputs at once\n\
"), stdout);
fputs (_("\
-o, --output=FILE write result to FILE instead of standard output\n\
@@ -391,7 +396,8 @@
{
CHECK_OPTION = CHAR_MAX + 1,
COMPRESS_PROGRAM_OPTION,
- RANDOM_SOURCE_OPTION
+ RANDOM_SOURCE_OPTION,
+ NMERGE_OPTION
};
static char const short_options[] = "-bcCdfgik:mMno:rRsS:t:T:uy:z";
@@ -414,6 +420,7 @@
{"output", required_argument, NULL, 'o'},
{"reverse", no_argument, NULL, 'r'},
{"stable", no_argument, NULL, 's'},
+ {"merge-batch-size", required_argument, NULL, NMERGE_OPTION},
{"buffer-size", required_argument, NULL, 'S'},
{"field-separator", required_argument, NULL, 't'},
{"temporary-directory", required_argument, NULL, 'T'},
@@ -1030,6 +1037,34 @@
#endif
}
+static void
+specify_nmerge (int oi, char c, char const *s)
+{
+ uintmax_t n;
+ enum strtol_error e = xstrtoumax (s, NULL, 10, &n, NULL);
+
+ if (e == LONGINT_OK)
+ {
+ nmerge = n;
+ if (nmerge == n)
+ {
+ if (nmerge >= 2)
+ {
+ /* Need to re-check that we meet the minimum
+ requirement for memory usage with the new,
+ potentially larger, nmerge */
+ sort_size = MAX (sort_size, MIN_SORT_SIZE);
+ return;
+ }
+ e = LONGINT_INVALID;
+ }
+ else
+ e = LONGINT_OVERFLOW;
+ }
+
+ xstrtol_fatal (e, oi, c, long_options, s);
+}
+
/* Specify the amount of main memory to use when sorting. */
static void
specify_sort_size (int oi, char c, char const *s)
@@ -2014,15 +2049,20 @@
mergefps (struct sortfile *files, size_t ntemps, size_t nfiles,
FILE *ofp, char const *output_file)
{
- FILE *fps[NMERGE]; /* Input streams for each file. */
- struct buffer buffer[NMERGE]; /* Input buffers for each file. */
+ FILE **fps = xnmalloc(nmerge, sizeof *fps);
+ /* Input streams for each file. */
+ struct buffer *buffer = xnmalloc(nmerge, sizeof *buffer);
+ /* Input buffers for each file. */
struct line saved; /* Saved line storage for unique check. */
struct line const *savedline = NULL;
/* &saved if there is a saved line. */
size_t savealloc = 0; /* Size allocated for the saved line. */
- struct line const *cur[NMERGE]; /* Current line in each line table. */
- struct line const *base[NMERGE]; /* Base of each line table. */
- size_t ord[NMERGE]; /* Table representing a permutation of fps,
+ struct line const **cur = xnmalloc(nmerge, sizeof *cur);
+ /* Current line in each line table. */
+ struct line const **base = xnmalloc(nmerge, sizeof *base);
+ /* Base of each line table. */
+ size_t *ord = xnmalloc(nmerge, sizeof ord);
+ /* Table representing a permutation of fps,
such that cur[ord[0]] is the smallest line
and will be next output. */
size_t i;
@@ -2195,6 +2235,11 @@
}
xfclose (ofp, output_file);
+ free(fps);
+ free(buffer);
+ free(ord);
+ free(base);
+ free(cur);
}
/* Merge into T the two sorted arrays of lines LO (with NLO members)
@@ -2382,7 +2427,7 @@
merge (struct sortfile *files, size_t ntemps, size_t nfiles,
char const *output_file)
{
- while (NMERGE < nfiles)
+ while (nmerge < nfiles)
{
/* Number of input files processed so far. */
size_t in;
@@ -2390,33 +2435,33 @@
/* Number of output files generated so far. */
size_t out;
- /* nfiles % NMERGE; this counts input files that are left over
+ /* nfiles % nmerge; this counts input files that are left over
after all full-sized merges have been done. */
size_t remainder;
/* Number of easily-available slots at the next loop iteration. */
size_t cheap_slots;
- /* Do as many NMERGE-size merges as possible. */
- for (out = in = 0; out < nfiles / NMERGE; out++, in += NMERGE)
+ /* Do as many nmerge-size merges as possible. */
+ for (out = in = 0; out < nfiles / nmerge; out++, in += nmerge)
{
FILE *tfp;
pid_t pid;
char *temp = create_temp (&tfp, &pid);
- size_t nt = MIN (ntemps, NMERGE);
+ size_t nt = MIN (ntemps, nmerge);
ntemps -= nt;
- mergefps (&files[in], nt, NMERGE, tfp, temp);
+ mergefps (&files[in], nt, nmerge, tfp, temp);
files[out].name = temp;
files[out].pid = pid;
}
remainder = nfiles - in;
- cheap_slots = NMERGE - out % NMERGE;
+ cheap_slots = nmerge - out % nmerge;
if (cheap_slots < remainder)
{
/* So many files remain that they can't all be put into the last
- NMERGE-sized output window. Do one more merge. Merge as few
+ nmerge-sized output window. Do one more merge. Merge as few
files as possible, to avoid needless I/O. */
size_t nshortmerge = remainder - cheap_slots + 1;
FILE *tfp;
@@ -2430,7 +2475,7 @@
in += nshortmerge;
}
- /* Put the remaining input files into the last NMERGE-sized output
+ /* Put the remaining input files into the last nmerge-sized output
window, so they will be merged in the next pass. */
memmove(&files[out], &files[in], (nfiles - in) * sizeof *files);
ntemps += out;
@@ -2995,6 +3040,10 @@
mergeonly = true;
break;
+ case NMERGE_OPTION:
+ specify_nmerge (oi, c, optarg);
+ break;
+
case 'o':
if (outfile && !STREQ (outfile, optarg))
error (SORT_FAILURE, 0, _("multiple output files specified"));
_______________________________________________
Bug-coreutils mailing list
Bug-coreutils@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-coreutils
