bug#7489: [coreutils] over aggressive threads in sort

[Paul Eggert]

On 11/29/2010 02:46 PM, Paul Eggert wrote:
> My current guess, by the way,
> is that it's not a bug that can be triggered: it's merely
> useless code that is harmless and can safely be removed.

I removed it as part of the following series of cleanup
patches.  These are intended merely to refactor the code
and simplify it a bit, to make it easier to fix the CPU
spinlock bug.  Please feel free to undo anything that
looks at all questionable.

While we're on that subject, I assume that
if we want to fix it by doing the last pass in memory rather
than to stdout, we need to allocate a bit more memory at
the start, basically N * (1 + log2(N)) cells instead of
N (log2(N)) cells.  This is enough to hold the extra pass
of output.  If this isn't right, Chen, please let me know.

>From 6c2452cd9f58c30e2e451c57d49384a2df785e3e Mon Sep 17 00:00:00 2001
From: Paul Eggert <address@hidden>
Date: Fri, 3 Dec 2010 14:27:02 -0800
Subject: [PATCH 1/7] sort: Clarify comments

* src/sort.c: Improve comments a bit.
---
 src/sort.c |   81 +++++++++++++++++++++++++++++++++++++++++++----------------
 1 files changed, 59 insertions(+), 22 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index 5c368cd..3d89a32 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -105,7 +105,7 @@ struct rlimit { size_t rlim_cur; };
 #endif
 
 /* Maximum number of lines to merge every time a NODE is taken from
-   the MERGE_QUEUE.  Node is at LEVEL in the binary merge tree,
+   the merge queue.  Node is at LEVEL in the binary merge tree,
    and is responsible for merging TOTAL lines. */
 #define MAX_MERGE(total, level) (((total) >> (2 * ((level) + 1))) + 1)
 
@@ -196,6 +196,7 @@ struct buffer
   bool eof;                    /* An EOF has been read.  */
 };
 
+/* Sort key.  */
 struct keyfield
 {
   size_t sword;                        /* Zero-origin 'word' to start at. */
@@ -3072,7 +3073,9 @@ mergelines (struct line *restrict t, size_t nlines,
 }
 
 /* Sort the array LINES with NLINES members, using TEMP for temporary space.
-   NLINES must be at least 2.
+   Do this all within one thread.  NLINES must be at least 2.
+   If TO_TEMP, put the sorted output into TEMP, and TEMP is as large as LINES.
+   Otherwise the sort is in-place and TEMP is half-sized.
    The input and output arrays are in reverse order, and LINES and
    TEMP point just past the end of their respective arrays.
 
@@ -3134,9 +3137,7 @@ sequential_sort (struct line *restrict lines, size_t 
nlines,
     }
 }
 
-/* Compare two NODEs for priority. The NODE with the higher (numerically
-   lower) level has priority. If tie, the NODE with the most remaining
-   lines has priority. */
+/* Compare two merge nodes A and B for priority.  */
 
 static int
 compare_nodes (void const *a, void const *b)
@@ -3149,9 +3150,9 @@ compare_nodes (void const *a, void const *b)
 }
 
 /* Lock a merge tree NODE.
-   Note spin locks were seen to perform better than mutexes
-   as long as the number of threads is limited to the
-   number of processors.  */
+   Spin locks were seen to perform better than mutexes when the number
+   of threads is limited to the number of processors, assuming 'sort'
+   never waits when writing to stdout.  */
 
 static inline void
 lock_node (struct merge_node *node)
@@ -3190,8 +3191,8 @@ queue_init (struct merge_node_queue *queue, size_t 
reserve)
   pthread_cond_init (&queue->cond, NULL);
 }
 
-/* Insert NODE into priority QUEUE. Assume caller either holds lock on NODE
-   or does not need to lock NODE. */
+/* Insert NODE into QUEUE.  The caller either holds a lock on NODE, or
+   does not need to lock NODE.  */
 
 static void
 queue_insert (struct merge_node_queue *queue, struct merge_node *node)
@@ -3203,7 +3204,7 @@ queue_insert (struct merge_node_queue *queue, struct 
merge_node *node)
   pthread_cond_signal (&queue->cond);
 }
 
-/* Pop NODE off priority QUEUE. Guarantee a non-null, spinlocked NODE. */
+/* Pop the top node off the priority QUEUE, lock the node, return it.  */
 
 static struct merge_node *
 queue_pop (struct merge_node_queue *queue)
@@ -3218,10 +3219,12 @@ queue_pop (struct merge_node_queue *queue)
   return node;
 }
 
-/* If UNQIUE is set, checks to make sure line isn't a duplicate before
-   outputting. If UNIQUE is not set, output the passed in line. Note that
-   this function does not actually save the line, nor any key information,
-   thus is only appropriate for internal sort. */
+/* Output LINE to TFP, unless -u is specified and the line compares
+   equal to the previous line.  TEMP_OUTPUT is the name of TFP, or
+   is null if TFP is standard output.
+
+   This function does not save the line for comparison later, so it is
+   appropriate only for internal sort.  */
 
 static void
 write_unique (struct line const *line, FILE *tfp, char const *temp_output)
@@ -3238,7 +3241,11 @@ write_unique (struct line const *line, FILE *tfp, char 
const *temp_output)
 }
 
 /* Merge the lines currently available to a NODE in the binary
-   merge tree, up to a maximum specified by MAX_MERGE. */
+   merge tree.  Merge a number of lines appropriate for this merge
+   level, assuming TOTAL_LINES is the total number of lines.
+
+   If merging at the top level, send output to TFP.  TEMP_OUTPUT is
+   the name of TFP, or is null if TFP is standard output.  */
 
 static size_t
 mergelines_node (struct merge_node *restrict node, size_t total_lines,
@@ -3305,7 +3312,9 @@ mergelines_node (struct merge_node *restrict node, size_t 
total_lines,
   return merged_lo + merged_hi;
 }
 
-/* Insert NODE into QUEUE if it passes insertion checks. */
+/* Insert NODE into QUEUE if it is not already queued, and if one of
+   NODE's children has available lines and the other either has
+   available lines or has exhausted its lines.  */
 
 static void
 check_insert (struct merge_node *node, struct merge_node_queue *queue)
@@ -3325,7 +3334,7 @@ check_insert (struct merge_node *node, struct 
merge_node_queue *queue)
     }
 }
 
-/* Update parent merge tree NODE. */
+/* Insert NODE's parent into QUEUE if the parent can now be worked on.  */
 
 static void
 update_parent (struct merge_node *node, size_t merged,
@@ -3346,8 +3355,11 @@ update_parent (struct merge_node *node, size_t merged,
     }
 }
 
-/* Repeatedly pop QUEUE for a NODE with lines to merge, and merge at least
-   some of those lines, until the MERGE_END node is popped. */
+/* Repeatedly pop QUEUE for a node with lines to merge, and merge at least
+   some of those lines, until the MERGE_END node is popped.
+   TOTAL_LINES is the total number of lines.  If merging at the top
+   level, send output to TFP.  TEMP_OUTPUT is the name of TFP, or is
+   null if TFP is standard output.  */
 
 static void
 merge_loop (struct merge_node_queue *queue,
@@ -3384,13 +3396,33 @@ static void sortlines (struct line *restrict, struct 
line *restrict,
 
 struct thread_args
 {
+  /* Source, i.e., the array of lines to sort.  This points just past
+     the end of the array.  */
   struct line *lines;
+
+  /* Destination, i.e., the array of lines to store result into.  This
+     also points just past the end of the array.  */
   struct line *dest;
+
+  /* Number of threads to use.  If 0 or 1, sort single-threaded.  */
   unsigned long int nthreads;
+
+  /* Number of lines in LINES and DEST.  */
   size_t const total_lines;
+
+  /* Parent node; it will merge this node's output to the output
+     of this node's sibling.  */
   struct merge_node *const parent;
+
+  /* True if this node is sorting the lower half of the parent's work.  */
   bool lo_child;
+
+  /* The priority queue controlling available work for the entire
+     internal sort.  */
   struct merge_node_queue *const merge_queue;
+
+  /* If at the top level, the file to output to, and the file's name.
+     If the file is standard output, the file's name is null.  */
   FILE *tfp;
   char const *output_temp;
 };
@@ -3407,7 +3439,10 @@ sortlines_thread (void *data)
   return NULL;
 }
 
-/* There are three phases to the algorithm: node creation, sequential sort,
+/* Sort lines, possibly in parallel.  The arguments are as in struct
+   thread_args above.
+
+   The algorithm has three phases: node creation, sequential sort,
    and binary merge.
 
    During node creation, sortlines recursively visits each node in the
@@ -3683,7 +3718,7 @@ merge (struct sortfile *files, size_t ntemps, size_t 
nfiles,
     }
 }
 
-/* Sort NFILES FILES onto OUTPUT_FILE. */
+/* Sort NFILES FILES onto OUTPUT_FILE.  Use at most NTHREADS threads.  */
 
 static void
 sort (char * const *files, size_t nfiles, char const *output_file,
@@ -3967,6 +4002,8 @@ set_ordering (char const *s, struct keyfield *key, enum 
blanktype blanktype)
   return (char *) s;
 }
 
+/* Initialize KEY.  */
+
 static struct keyfield *
 key_init (struct keyfield *key)
 {
-- 
1.7.2


>From 5e87272634c4f5459808ec5d5c15d1710a2a5bbe Mon Sep 17 00:00:00 2001
From: Paul Eggert <address@hidden>
Date: Fri, 3 Dec 2010 14:39:23 -0800
Subject: [PATCH 2/7] sort: tune struct_merge_node slightly

* src/sort.c (struct merge_node): 'lock' is now the actual lock,
not a pointer to the lock; there's no need for indirection here.
Make 'level' unsigned int instead of size_t, since it is a
bit-shift count; also, move it next to a bool so that it's more
likely to take less space.  All uses changed.
(sortlines, sort): Spell out initialization instead of using an
initializer.  This makes the initializer a bit easier to understand,
and avoids unnecessary stores into the spin lock.
---
 src/sort.c |   40 +++++++++++++++++++++++++---------------
 1 files changed, 25 insertions(+), 15 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index 3d89a32..141af52 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -238,10 +238,10 @@ struct merge_node
   struct line **dest;           /* Pointer to destination of merge. */
   size_t nlo;                   /* Total Lines remaining from LO. */
   size_t nhi;                   /* Total lines remaining from HI. */
-  size_t level;                 /* Level in merge tree. */
   struct merge_node *parent;    /* Parent node. */
+  unsigned int level;           /* Level in merge tree. */
   bool queued;                  /* Node is already in heap. */
-  pthread_spinlock_t *lock;     /* Lock for node operations. */
+  pthread_spinlock_t lock;      /* Lock for node operations. */
 };
 
 /* Priority queue of merge nodes. */
@@ -3157,7 +3157,7 @@ compare_nodes (void const *a, void const *b)
 static inline void
 lock_node (struct merge_node *node)
 {
-  pthread_spin_lock (node->lock);
+  pthread_spin_lock (&node->lock);
 }
 
 /* Unlock a merge tree NODE. */
@@ -3165,7 +3165,7 @@ lock_node (struct merge_node *node)
 static inline void
 unlock_node (struct merge_node *node)
 {
-  pthread_spin_unlock (node->lock);
+  pthread_spin_unlock (&node->lock);
 }
 
 /* Destroy merge QUEUE. */
@@ -3477,10 +3477,17 @@ sortlines (struct line *restrict lines, struct line 
*restrict dest,
   struct line *lo = dest - total_lines;
   struct line *hi = lo - nlo;
   struct line **parent_end = (lo_child)? &parent->end_lo : &parent->end_hi;
-  pthread_spinlock_t lock;
-  pthread_spin_init (&lock, PTHREAD_PROCESS_PRIVATE);
-  struct merge_node node = {lo, hi, lo, hi, parent_end, nlo, nhi,
-                            parent->level + 1, parent, false, &lock};
+
+  struct merge_node node;
+  node.lo = node.end_lo = lo;
+  node.hi = node.end_hi = hi;
+  node.dest = parent_end;
+  node.nlo = nlo;
+  node.nhi = nhi;
+  node.parent = parent;
+  node.level = parent->level + 1;
+  node.queued = false;
+  pthread_spin_init (&node.lock, PTHREAD_PROCESS_PRIVATE);
 
   /* Calculate thread arguments. */
   unsigned long int lo_threads = nthreads / 2;
@@ -3516,7 +3523,7 @@ sortlines (struct line *restrict lines, struct line 
*restrict dest,
       merge_loop (merge_queue, total_lines, tfp, temp_output);
     }
 
-  pthread_spin_destroy (&lock);
+  pthread_spin_destroy (&node.lock);
 }
 
 /* Scan through FILES[NTEMPS .. NFILES-1] looking for a file that is
@@ -3793,16 +3800,19 @@ sort (char * const *files, size_t nfiles, char const 
*output_file,
               struct merge_node_queue merge_queue;
               queue_init (&merge_queue, 2 * nthreads);
 
-              pthread_spinlock_t lock;
-              pthread_spin_init (&lock, PTHREAD_PROCESS_PRIVATE);
-              struct merge_node node =
-                {NULL, NULL, NULL, NULL, NULL, buf.nlines,
-                 buf.nlines, MERGE_END, NULL, false, &lock};
+              struct merge_node node;
+              node.lo = node.hi = node.end_lo = node.end_hi = NULL;
+              node.dest = NULL;
+              node.nlo = node.nhi = buf.nlines;
+              node.parent = NULL;
+              node.level = MERGE_END;
+              node.queued = false;
+              pthread_spin_init (&node.lock, PTHREAD_PROCESS_PRIVATE);
 
               sortlines (line, line, nthreads, buf.nlines, &node, true,
                          &merge_queue, tfp, temp_output);
               queue_destroy (&merge_queue);
-              pthread_spin_destroy (&lock);
+              pthread_spin_destroy (&node.lock);
             }
           else
             write_unique (line - 1, tfp, temp_output);
-- 
1.7.2


>From a7beff9385827f47b97e089cfe15f2761c9a1efd Mon Sep 17 00:00:00 2001
From: Paul Eggert <address@hidden>
Date: Fri, 3 Dec 2010 15:01:21 -0800
Subject: [PATCH 3/7] sort: put queue arg first

* src/sort.c (queue_check_insert, queue_check_insert_parent): Make
the queue arg first, for consistency with other functions such as
queue_insert that put the queue arg first.  Rename from
check_insert and update_parent, respectively.  All callers
changed.
---
 src/sort.c |   16 ++++++++--------
 1 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index 141af52..af4b20c 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3312,12 +3312,12 @@ mergelines_node (struct merge_node *restrict node, 
size_t total_lines,
   return merged_lo + merged_hi;
 }
 
-/* Insert NODE into QUEUE if it is not already queued, and if one of
+/* Into QUEUE, insert NODE if it is not already queued, and if one of
    NODE's children has available lines and the other either has
    available lines or has exhausted its lines.  */
 
 static void
-check_insert (struct merge_node *node, struct merge_node_queue *queue)
+queue_check_insert (struct merge_node_queue *queue, struct merge_node *node)
 {
   size_t lo_avail = node->lo - node->end_lo;
   size_t hi_avail = node->hi - node->end_hi;
@@ -3334,17 +3334,17 @@ check_insert (struct merge_node *node, struct 
merge_node_queue *queue)
     }
 }
 
-/* Insert NODE's parent into QUEUE if the parent can now be worked on.  */
+/* Into QUEUE, insert NODE's parent if the parent can now be worked on.  */
 
 static void
-update_parent (struct merge_node *node, size_t merged,
-               struct merge_node_queue *queue)
+queue_check_insert_parent (struct merge_node_queue *queue,
+                           struct merge_node *node, size_t merged)
 {
   if (node->level > MERGE_ROOT)
     {
       lock_node (node->parent);
       *node->dest -= merged;
-      check_insert (node->parent, queue);
+      queue_check_insert (queue, node->parent);
       unlock_node (node->parent);
     }
   else if (node->nlo + node->nhi == 0)
@@ -3378,8 +3378,8 @@ merge_loop (struct merge_node_queue *queue,
         }
       size_t merged_lines = mergelines_node (node, total_lines, tfp,
                                              temp_output);
-      check_insert (node, queue);
-      update_parent (node, merged_lines, queue);
+      queue_check_insert (queue, node);
+      queue_check_insert_parent (queue, node, merged_lines);
 
       unlock_node (node);
     }
-- 
1.7.2


>From 66d448d0757c3ad3cd11f20142aeeefbdcdd354e Mon Sep 17 00:00:00 2001
From: Paul Eggert <address@hidden>
Date: Fri, 3 Dec 2010 15:04:31 -0800
Subject: [PATCH 4/7] sort: simplify write_unique

* src/sort.c (write_unique): Simplify slightly so that there is
just one call to write_line, not two.
---
 src/sort.c |    9 +++++----
 1 files changed, 5 insertions(+), 4 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index af4b20c..1faf171 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3231,13 +3231,14 @@ write_unique (struct line const *line, FILE *tfp, char 
const *temp_output)
 {
   static struct line saved;
 
-  if (!unique)
-    write_line (line, tfp, temp_output);
-  else if (!saved.text || compare (line, &saved))
+  if (unique)
     {
+      if (saved.text && ! compare (line, &saved))
+        return;
       saved = *line;
-      write_line (line, tfp, temp_output);
     }
+
+  write_line (line, tfp, temp_output);
 }
 
 /* Merge the lines currently available to a NODE in the binary
-- 
1.7.2


>From 809431a68369189a3bc4be2388fdb0f20922c4e0 Mon Sep 17 00:00:00 2001
From: Paul Eggert <address@hidden>
Date: Fri, 3 Dec 2010 15:11:46 -0800
Subject: [PATCH 5/7] sort: fix problems with merge node dest pointer

* src/sort.c (mergelines_node): Return void, not size_t.  All
callers changed.  Change *node->dest here, not in caller.
Do not change node->dest: it's not needed and could cause problems
on (mostly theoretical) hosts that do not allow adding integers to
null pointers.
(queue_check_insert_parent): Omit MERGED parameter; no longer needed.
All callers changed.
---
 src/sort.c |   13 +++++--------
 1 files changed, 5 insertions(+), 8 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index 1faf171..f7296d6 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3248,7 +3248,7 @@ write_unique (struct line const *line, FILE *tfp, char 
const *temp_output)
    If merging at the top level, send output to TFP.  TEMP_OUTPUT is
    the name of TFP, or is null if TFP is standard output.  */
 
-static size_t
+static void
 mergelines_node (struct merge_node *restrict node, size_t total_lines,
                  FILE *tfp, char const *temp_output)
 {
@@ -3277,6 +3277,7 @@ mergelines_node (struct merge_node *restrict node, size_t 
total_lines,
       else if (node->nlo == merged_lo)
         while (node->hi != node->end_hi && to_merge--)
           *--dest = *--node->hi;
+      *node->dest = dest;
     }
   else
     {
@@ -3302,7 +3303,6 @@ mergelines_node (struct merge_node *restrict node, size_t 
total_lines,
           while (node->hi != node->end_hi && to_merge--)
             write_unique (--node->hi, tfp, temp_output);
         }
-      node->dest -= lo_orig - node->lo + hi_orig - node->hi;
     }
 
   /* Update NODE. */
@@ -3310,7 +3310,6 @@ mergelines_node (struct merge_node *restrict node, size_t 
total_lines,
   merged_hi = hi_orig - node->hi;
   node->nlo -= merged_lo;
   node->nhi -= merged_hi;
-  return merged_lo + merged_hi;
 }
 
 /* Into QUEUE, insert NODE if it is not already queued, and if one of
@@ -3339,12 +3338,11 @@ queue_check_insert (struct merge_node_queue *queue, 
struct merge_node *node)
 
 static void
 queue_check_insert_parent (struct merge_node_queue *queue,
-                           struct merge_node *node, size_t merged)
+                           struct merge_node *node)
 {
   if (node->level > MERGE_ROOT)
     {
       lock_node (node->parent);
-      *node->dest -= merged;
       queue_check_insert (queue, node->parent);
       unlock_node (node->parent);
     }
@@ -3377,10 +3375,9 @@ merge_loop (struct merge_node_queue *queue,
           queue_insert (queue, node);
           break;
         }
-      size_t merged_lines = mergelines_node (node, total_lines, tfp,
-                                             temp_output);
+      mergelines_node (node, total_lines, tfp, temp_output);
       queue_check_insert (queue, node);
-      queue_check_insert_parent (queue, node, merged_lines);
+      queue_check_insert_parent (queue, node);
 
       unlock_node (node);
     }
-- 
1.7.2


>From 68bdf2752625e74a4783b441f69e79a7bd65ab5c Mon Sep 17 00:00:00 2001
From: Paul Eggert <address@hidden>
Date: Fri, 3 Dec 2010 15:23:43 -0800
Subject: [PATCH 6/7] sort: clarify queue_check_insert

* src/sort.c (queue_check_insert): Clarify body a bit, and remove
no-longer-needed comment.
---
 src/sort.c |   16 +++++-----------
 1 files changed, 5 insertions(+), 11 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index f7296d6..3ed7c5b 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3319,18 +3319,12 @@ mergelines_node (struct merge_node *restrict node, 
size_t total_lines,
 static void
 queue_check_insert (struct merge_node_queue *queue, struct merge_node *node)
 {
-  size_t lo_avail = node->lo - node->end_lo;
-  size_t hi_avail = node->hi - node->end_hi;
-
-  /* Conditions for insertion:
-     1. NODE is not already in heap.
-     2. NODE has available lines from both it's children, OR one child has
-          available lines, but the other has exhausted all its lines. */
-  if ((!node->queued)
-      && ((lo_avail && (hi_avail || !(node->nhi)))
-          || (hi_avail && !(node->nlo))))
+  if (! node->queued)
     {
-      queue_insert (queue, node);
+      bool lo_avail = (node->lo - node->end_lo) != 0;
+      bool hi_avail = (node->hi - node->end_hi) != 0;
+      if (lo_avail ? hi_avail || ! node->nhi : hi_avail && ! node->nlo)
+        queue_insert (queue, node);
     }
 }
 
-- 
1.7.2


>From 49c7f475ddcba334d76ef364d65882802c26163e Mon Sep 17 00:00:00 2001
From: Paul Eggert <address@hidden>
Date: Fri, 3 Dec 2010 15:39:50 -0800
Subject: [PATCH 7/7] sort: merge_queue -> queue

* src/sort.c (struct thread_args, sortlines_thread, sortlines, sort):
Rename "merge_queue" to "queue", for consistency with other functions
that just use the name "queue" for these things.
---
 src/sort.c |   22 +++++++++++-----------
 1 files changed, 11 insertions(+), 11 deletions(-)

diff --git a/src/sort.c b/src/sort.c
index 3ed7c5b..a4c2cbf 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -3411,7 +3411,7 @@ struct thread_args
 
   /* The priority queue controlling available work for the entire
      internal sort.  */
-  struct merge_node_queue *const merge_queue;
+  struct merge_node_queue *const queue;
 
   /* If at the top level, the file to output to, and the file's name.
      If the file is standard output, the file's name is null.  */
@@ -3426,7 +3426,7 @@ sortlines_thread (void *data)
 {
   struct thread_args const *args = data;
   sortlines (args->lines, args->dest, args->nthreads, args->total_lines,
-             args->parent, args->lo_child, args->merge_queue,
+             args->parent, args->lo_child, args->queue,
              args->tfp, args->output_temp);
   return NULL;
 }
@@ -3459,7 +3459,7 @@ static void
 sortlines (struct line *restrict lines, struct line *restrict dest,
            unsigned long int nthreads, size_t total_lines,
            struct merge_node *parent, bool lo_child,
-           struct merge_node_queue *merge_queue,
+           struct merge_node_queue *queue,
            FILE *tfp, char const *temp_output)
 {
   /* Create merge tree NODE. */
@@ -3486,13 +3486,13 @@ sortlines (struct line *restrict lines, struct line 
*restrict dest,
   unsigned long int hi_threads = nthreads - lo_threads;
   pthread_t thread;
   struct thread_args args = {lines, lo, lo_threads, total_lines, &node,
-                             true, merge_queue, tfp, temp_output};
+                             true, queue, tfp, temp_output};
 
   if (nthreads > 1 && SUBTHREAD_LINES_HEURISTIC <= nlines
       && pthread_create (&thread, NULL, sortlines_thread, &args) == 0)
     {
       sortlines (lines - nlo, hi, hi_threads, total_lines, &node, false,
-                 merge_queue, tfp, temp_output);
+                 queue, tfp, temp_output);
       pthread_join (thread, NULL);
     }
   else
@@ -3511,8 +3511,8 @@ sortlines (struct line *restrict lines, struct line 
*restrict dest,
       node.end_lo = lines - nlo;
       node.end_hi = lines - nlo - nhi;
 
-      queue_insert (merge_queue, &node);
-      merge_loop (merge_queue, total_lines, tfp, temp_output);
+      queue_insert (queue, &node);
+      merge_loop (queue, total_lines, tfp, temp_output);
     }
 
   pthread_spin_destroy (&node.lock);
@@ -3789,8 +3789,8 @@ sort (char * const *files, size_t nfiles, char const 
*output_file,
             }
           if (1 < buf.nlines)
             {
-              struct merge_node_queue merge_queue;
-              queue_init (&merge_queue, 2 * nthreads);
+              struct merge_node_queue queue;
+              queue_init (&queue, 2 * nthreads);
 
               struct merge_node node;
               node.lo = node.hi = node.end_lo = node.end_hi = NULL;
@@ -3802,8 +3802,8 @@ sort (char * const *files, size_t nfiles, char const 
*output_file,
               pthread_spin_init (&node.lock, PTHREAD_PROCESS_PRIVATE);
 
               sortlines (line, line, nthreads, buf.nlines, &node, true,
-                         &merge_queue, tfp, temp_output);
-              queue_destroy (&merge_queue);
+                         &queue, tfp, temp_output);
+              queue_destroy (&queue);
               pthread_spin_destroy (&node.lock);
             }
           else
-- 
1.7.2