lucy-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nwelln...@apache.org
Subject [2/6] lucy git commit: Avoid intermediate copies during SortEx merge
Date Sat, 07 Nov 2015 17:06:36 GMT
Avoid intermediate copies during SortEx merge


Project: http://git-wip-us.apache.org/repos/asf/lucy/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucy/commit/bd22f8dc
Tree: http://git-wip-us.apache.org/repos/asf/lucy/tree/bd22f8dc
Diff: http://git-wip-us.apache.org/repos/asf/lucy/diff/bd22f8dc

Branch: refs/heads/master
Commit: bd22f8dc6c918a9627c87063b60f7f5854a6184c
Parents: 75a1c6e
Author: Nick Wellnhofer <wellnhofer@aevum.de>
Authored: Thu Nov 5 18:05:02 2015 +0100
Committer: Nick Wellnhofer <wellnhofer@aevum.de>
Committed: Thu Nov 5 18:05:02 2015 +0100

----------------------------------------------------------------------
 core/Lucy/Util/SortExternal.c | 23 ++++++++++++++++-------
 1 file changed, 16 insertions(+), 7 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucy/blob/bd22f8dc/core/Lucy/Util/SortExternal.c
----------------------------------------------------------------------
diff --git a/core/Lucy/Util/SortExternal.c b/core/Lucy/Util/SortExternal.c
index 55ac9a2..6b6fc22 100644
--- a/core/Lucy/Util/SortExternal.c
+++ b/core/Lucy/Util/SortExternal.c
@@ -305,34 +305,43 @@ S_absorb_slices(SortExternal *self, SortExternalIVARS *ivars,
                             ivars->scratch, ivars->scratch_cap * sizeof(Obj*));
     }
 
-    // Exploit previous sorting, rather than sort buffer naively.
-    // Leave the first slice intact if the number of slices is odd. */
+    // Divide-and-conquer k-way merge.
     while (num_slices > 1) {
         uint32_t i = 0;
         uint32_t j = 0;
+        Obj **dest = ivars->scratch;
 
         while (i < num_slices) {
             if (num_slices - i >= 2) {
                 // Merge two consecutive slices.
                 const uint32_t merged_size = slice_sizes[i] + slice_sizes[i + 1];
                 Sort_merge(slice_starts[i], slice_sizes[i],
-                           slice_starts[i + 1], slice_sizes[i + 1], ivars->scratch,
+                           slice_starts[i + 1], slice_sizes[i + 1], dest,
                            sizeof(Obj*), compare, self);
                 slice_sizes[j]  = merged_size;
-                slice_starts[j] = slice_starts[i];
-                memcpy(slice_starts[j], ivars->scratch, merged_size * sizeof(Obj*));
+                slice_starts[j] = dest;
+                dest += merged_size;
                 i += 2;
                 j += 1;
             }
             else if (num_slices - i >= 1) {
-                // Move single slice pointer.
+                // Move last slice.
+                memcpy(dest, slice_starts[i], slice_sizes[i] * sizeof(Obj*));
                 slice_sizes[j]  = slice_sizes[i];
-                slice_starts[j] = slice_starts[i];
+                slice_starts[j] = dest;
                 i += 1;
                 j += 1;
             }
         }
         num_slices = j;
+
+        // Swap scratch and buffer.
+        Obj      **tmp_buf = ivars->buffer;
+        uint32_t   tmp_cap = ivars->buf_cap;
+        ivars->buffer      = ivars->scratch;
+        ivars->buf_cap     = ivars->scratch_cap;
+        ivars->scratch     = tmp_buf;
+        ivars->scratch_cap = tmp_cap;
     }
 }
 


Mime
View raw message