summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorChen Guo <chenguo4@ucla.edu>2010-12-10 13:13:36 -0800
committerPaul Eggert <eggert@cs.ucla.edu>2010-12-11 00:29:13 -0800
commitc9db0ac6decb8121097d67e13659748ff3b3bcd6 (patch)
treeaf7175a3ef804ef7e2de5aafb9e93b273cc15ade /src
parentd1f700355630c2d6e22ebff9de5f15b10aa14185 (diff)
downloadcoreutils-c9db0ac6decb8121097d67e13659748ff3b3bcd6.tar.xz
sort: preallocate merge tree nodes to heap.
* src/sort.c: (merge_tree_init) New function. Allocates memory for merge tree nodes. (merge_tree_destory) New function. (init_node) New function. (sortlines) Refactor node creation code to init_node. Remove now superfluous arguments. All callers changed. (sort) Initialize/destory merge tree. Refactor root node creation to merge_tree_init.
Diffstat (limited to 'src')
-rw-r--r--src/sort.c170
1 files changed, 111 insertions, 59 deletions
diff --git a/src/sort.c b/src/sort.c
index 36e3b19fb..b724f3dc1 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -239,6 +239,8 @@ struct merge_node
size_t nlo; /* Total Lines remaining from LO. */
size_t nhi; /* Total lines remaining from HI. */
struct merge_node *parent; /* Parent node. */
+ struct merge_node *lo_child; /* LO child node. */
+ struct merge_node *hi_child; /* HI child node. */
unsigned int level; /* Level in merge tree. */
bool queued; /* Node is already in heap. */
pthread_mutex_t lock; /* Lock for node operations. */
@@ -3137,6 +3139,83 @@ sequential_sort (struct line *restrict lines, size_t nlines,
}
}
+struct merge_node * init_node (struct merge_node *, struct merge_node *,
+ struct line *restrict, unsigned long int,
+ size_t, bool);
+
+
+/* Initialize the merge tree. */
+static struct merge_node *
+merge_tree_init (unsigned long int nthreads, size_t nlines,
+ struct line *restrict dest)
+{
+ struct merge_node *merge_tree = xmalloc (2 * nthreads * sizeof *merge_tree);
+
+ struct merge_node *root_node = merge_tree;
+ root_node->lo = root_node->hi = root_node->end_lo = root_node->end_hi = NULL;
+ root_node->dest = NULL;
+ root_node->nlo = root_node->nhi = nlines;
+ root_node->parent = NULL;
+ root_node->level = MERGE_END;
+ root_node->queued = false;
+ pthread_mutex_init (&root_node->lock, NULL);
+
+ init_node (root_node, root_node + 1, dest, nthreads, nlines, false);
+ return merge_tree;
+}
+
+/* Destroy the merge tree. */
+static void
+merge_tree_destroy (struct merge_node *merge_tree)
+{
+ free (merge_tree);
+}
+
+/* Initialize a merge tree node. */
+
+struct merge_node *
+init_node (struct merge_node *parent, struct merge_node *node_pool,
+ struct line *restrict dest, unsigned long int nthreads,
+ size_t total_lines, bool lo_child)
+{
+ size_t nlines = (lo_child)? parent->nlo : parent->nhi;
+ size_t nlo = nlines / 2;
+ size_t nhi = nlines - nlo;
+ struct line *lo = dest - total_lines;
+ struct line *hi = lo - nlo;
+ struct line **parent_end = (lo_child)? &parent->end_lo : &parent->end_hi;
+
+ struct merge_node *node = node_pool++;
+ 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_mutex_init (&node->lock, NULL);
+
+ if (nthreads > 1)
+ {
+ unsigned long int lo_threads = nthreads / 2;
+ unsigned long int hi_threads = nthreads - lo_threads;
+ node->lo_child = node_pool;
+ node_pool = init_node (node, node_pool, lo, lo_threads,
+ total_lines, true);
+ node->hi_child = node_pool;
+ node_pool = init_node (node, node_pool, hi, hi_threads,
+ total_lines, false);
+ }
+ else
+ {
+ node->lo_child = NULL;
+ node->hi_child = NULL;
+ }
+ return node_pool;
+}
+
+
/* Compare two merge nodes A and B for priority. */
static int
@@ -3375,10 +3454,8 @@ merge_loop (struct merge_node_queue *queue,
}
-static void sortlines (struct line *restrict, struct line *restrict,
- unsigned long int, size_t,
- struct merge_node *, bool,
- struct merge_node_queue *,
+static void sortlines (struct line *restrict, unsigned long int, size_t,
+ struct merge_node *, bool, struct merge_node_queue *,
FILE *, char const *);
/* Thread arguments for sortlines_thread. */
@@ -3389,19 +3466,15 @@ struct thread_args
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;
+ /* Merge node. Lines from this node and this node's sibling will merged
+ to this node's parent. */
+ struct merge_node *const node;
/* True if this node is sorting the lower half of the parent's work. */
bool lo_child;
@@ -3422,9 +3495,9 @@ static void *
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->queue,
- args->tfp, args->output_temp);
+ sortlines (args->lines, args->nthreads, args->total_lines,
+ args->node, args->lo_child, args->queue, args->tfp,
+ args->output_temp);
return NULL;
}
@@ -3453,49 +3526,32 @@ sortlines_thread (void *data)
have been merged. */
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 *queue,
- FILE *tfp, char const *temp_output)
+sortlines (struct line *restrict lines, unsigned long int nthreads,
+ size_t total_lines, struct merge_node *node, bool lo_child,
+ struct merge_node_queue *queue, FILE *tfp, char const *temp_output)
{
- /* Create merge tree NODE. */
- size_t nlines = (lo_child)? parent->nlo : parent->nhi;
- size_t nlo = nlines / 2;
- size_t nhi = nlines - nlo;
- struct line *lo = dest - total_lines;
- struct line *hi = lo - nlo;
- struct line **parent_end = (lo_child)? &parent->end_lo : &parent->end_hi;
-
- 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_mutex_init (&node.lock, NULL);
+ size_t nlines = node->nlo + node->nhi;
/* Calculate thread arguments. */
unsigned long int lo_threads = nthreads / 2;
unsigned long int hi_threads = nthreads - lo_threads;
pthread_t thread;
- struct thread_args args = {lines, lo, lo_threads, total_lines, &node,
- true, queue, tfp, temp_output};
+ struct thread_args args = {lines, lo_threads, total_lines,
+ node->lo_child, 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,
- queue, tfp, temp_output);
+ sortlines (lines - node->nlo, hi_threads, total_lines,
+ node->hi_child, false, queue, tfp, temp_output);
pthread_join (thread, NULL);
}
else
{
/* Nthreads = 1, this is a leaf NODE, or pthread_create failed.
Sort with 1 thread. */
+ size_t nlo = node->nlo;
+ size_t nhi = node->nhi;
struct line *temp = lines - total_lines;
if (1 < nhi)
sequential_sort (lines - nlo, nhi, temp - nlo / 2, false);
@@ -3503,16 +3559,16 @@ sortlines (struct line *restrict lines, struct line *restrict dest,
sequential_sort (lines, nlo, temp, false);
/* Update merge NODE. No need to lock yet. */
- node.lo = lines;
- node.hi = lines - nlo;
- node.end_lo = lines - nlo;
- node.end_hi = lines - nlo - nhi;
+ node->lo = lines;
+ node->hi = lines - nlo;
+ node->end_lo = lines - nlo;
+ node->end_hi = lines - nlo - nhi;
- queue_insert (queue, &node);
+ queue_insert (queue, node);
merge_loop (queue, total_lines, tfp, temp_output);
}
- pthread_mutex_destroy (&node.lock);
+ pthread_mutex_destroy (&node->lock);
}
/* Scan through FILES[NTEMPS .. NFILES-1] looking for a file that is
@@ -3788,20 +3844,16 @@ sort (char * const *files, size_t nfiles, char const *output_file,
{
struct merge_node_queue queue;
queue_init (&queue, 2 * nthreads);
+ struct merge_node *merge_tree =
+ merge_tree_init (nthreads, buf.nlines, line);
+ struct merge_node *end_node = merge_tree;
+ struct merge_node *root_node = merge_tree + 1;
- 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_mutex_init (&node.lock, NULL);
-
- sortlines (line, line, nthreads, buf.nlines, &node, true,
- &queue, tfp, temp_output);
+ sortlines (line, nthreads, buf.nlines, root_node,
+ true, &queue, tfp, temp_output);
queue_destroy (&queue);
- pthread_mutex_destroy (&node.lock);
+ pthread_mutex_destroy (&root_node->lock);
+ merge_tree_destroy (merge_tree);
}
else
write_unique (line - 1, tfp, temp_output);