I notice this uses C99 syntax like: for (size_t i; ... There is precedent in remove.c (sep 2008) for that so I thinks it's fine.
Note I noticed some good info on heaps and sorts in this output: echo "import heapq; print heapq.__about__" | python So I think this patch is a fine improvement and should be pushed with the following tweaks... @@ -1,30 +1,35 @@ From: Paul Eggert <egg...@cs.ucla.edu> Date: Fri, 13 Mar 2009 12:24:22 -0700 -Subject: [PATCH] Use a heap for the internal merge. +Subject: [PATCH] sort: Use a heap to speed up the internal merge -With random data and a 64-way merge this sped up 'sort' by 5% on our -tests. Sorry, I don't know how to put multiple authors in the patch. -However, the authors are: - -Alexander Nguyen <v...@seas.ucla.edu> -Paul Eggert <egg...@cs.ucla.edu> - -We've both signed papers. - ------ - -src/sort.c (mergefps): When merging a line with a K-way merge, update a -heap rather than doing a linear insertion. This improves the -overall performance of 'sort' from O(N*K) to O(N log K). +* src/sort.c (mergefps): When merging a line with a K-way merge, update +a heap rather than doing a linear insertion. This improves the overall +performance of 'sort' from O(N*K) to O(N log K), which in testing with +random data and 64-way merge sped up 'sort' by 5%. (less_than, swap): New functions. (sortlines_temp): Rename local variable so that it doesn't shadow the new 'swap' function. +* THANKS: Add Alexander Nguyen who coauthored this commit. --- + THANKS | 1 + src/sort.c | 140 +++++++++++++++++++++++++++++------------------------------- - 1 files changed, 67 insertions(+), 73 deletions(-) + 2 files changed, 68 insertions(+), 73 deletions(-) +diff --git a/THANKS b/THANKS +index 46d077b..55f0035 100644 +--- a/THANKS ++++ b/THANKS +@@ -23,6 +23,7 @@ Alberto Accomazzi albe...@cfa0.harvard.edu + aldomel aldo...@ix.netcom.com + Alen Muzinic zv...@fly.cc.fer.hr + Alexander V. Lukyanov l...@netis.ru ++Alexander Nguyen v...@seas.ucla.edu + Allen Hewes al...@decisiv.net + Axel Dörfler ax...@pinc-software.de + Alexandre Duret-Lutz dure...@epita.fr diff --git a/src/sort.c b/src/sort.c -index 7b0b064..0e22aff 100644 +index 7b0b064..ab80e14 100644 --- a/src/sort.c +++ b/src/sort.c @@ -2060,6 +2060,25 @@ compare (const struct line *a, const struct line *b) @@ -32,7 +37,7 @@ } +/* If CUR is a vector of lines, and ORD a vector of indexes into CUR, -+ then return true if the line ORD[A] less less than the line ORD[B] ++ then return true if the line ORD[A] is less than the line ORD[B] + in CUR, using a stable comparison. */ +static bool +less_than (struct line const *const *cur, size_t const *ord, _______________________________________________ Bug-coreutils mailing list Bug-coreutils@gnu.org http://lists.gnu.org/mailman/listinfo/bug-coreutils
