You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucy.apache.org by nw...@apache.org on 2015/11/07 18:06:36 UTC
[2/6] lucy git commit: Avoid intermediate copies during SortEx merge
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 <we...@aevum.de>
Authored: Thu Nov 5 18:05:02 2015 +0100
Committer: Nick Wellnhofer <we...@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;
}
}