mayya-sharipova commented on code in PR #16794:
URL: https://github.com/apache/lucene/pull/16794#discussion_r4233716467
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/HnswConcurrentMergeBuilder.java:
##########
@@ -159,6 +232,138 @@ public OnHeapHnswGraph build(int maxOrd) throws
IOException {
return getCompletedGraph();
}
+ /**
+ * Joins {@link #graphs} into the graph like {@link MergingHnswGraphBuilder}
does, but with all
+ * workers. Graphs are joined one after the other: adding the join sets of
all graphs before the
+ * other nodes of any of them builds a noticeably worse graph. Since the
join sets only depend on
+ * the graphs being joined, they are all computed beforehand, one task per
graph.
+ */
+ private void joinGraphs(int maxOrd, AtomicLong cumulativeWorkTimeNs) throws
IOException {
+ long startNs = System.nanoTime();
+ List<Callable<JoinPlan>> planTasks = new ArrayList<>(graphs.length);
+ for (int g = 0; g < graphs.length; g++) {
+ HnswGraph graph = graphs[g];
+ int[] ordMap = ordMaps[g];
+ planTasks.add(() -> JoinPlan.create(graph, ordMap));
+ }
+ JoinPlan[] plans =
taskExecutor.invokeAll(planTasks).toArray(JoinPlan[]::new);
+ if (infoStream.isEnabled(HNSW_COMPONENT)) {
+ infoStream.message(
+ HNSW_COMPONENT,
+ String.format(
+ Locale.ROOT,
+ "computed the join sets of %d graphs in %.2f ms",
+ plans.length,
+ (System.nanoTime() - startNs) / 1_000_000.0));
+ }
+
+ // the nodes of the joined graphs that are fully inserted, and so usable
as entry points
+ InsertedNodes inserted = new InsertedNodes(maxOrd);
+ for (int g = 0; g < plans.length; g++) {
+ JoinPlan plan = plans[g];
+ plans[g] = null; // not needed once joined
+ runInBatches(
+ plan.joinSetNodes.length,
+ cumulativeWorkTimeNs,
+ (worker, start, end) -> {
+ for (int i = start; i < end; i++) {
+ worker.addJoinSetNode(plan.ordMap[plan.joinSetNodes[i]],
inserted);
+ }
+ });
+ runInBatches(
+ plan.otherNodes.length,
+ cumulativeWorkTimeNs,
+ (worker, start, end) -> {
+ for (int i = start; i < end; i++) {
+ worker.addJoinedNode(plan, plan.otherNodes[i], inserted);
+ }
+ });
+ }
+ }
+
+ /**
+ * How a graph is joined: its join set, its other nodes, and how to read the
graph. Nodes are
+ * ordinals of the graph being joined; {@code ordMap} maps them to ordinals
of the merged graph.
+ *
+ * @param graph the graph being joined
+ * @param graphLock guards {@code graph}, which workers read concurrently
+ * @param ordMap maps ordinals of {@code graph} to ordinals of the merged
graph
+ * @param joinSetNodes the join set of {@code graph}, sorted
+ * @param otherNodes the other nodes of {@code graph}, sorted
+ */
+ private record JoinPlan(
+ HnswGraph graph, Lock graphLock, int[] ordMap, int[] joinSetNodes, int[]
otherNodes) {
+
+ static JoinPlan create(HnswGraph graph, int[] ordMap) throws IOException {
+ IntHashSet j = UpdateGraphsUtils.computeJoinSet(graph);
+ // sort for stability
+ int[] joinSetNodes = j.toArray();
Review Comment:
joinSetNodes + otherNodes together hold every node of the graph: ~4 bytes
per vector, which is a lot.
Could the join set be a FixedBitSet instead, with otherNodes dropped? The
other-nodes phase could batch over [0, size) and skip set bits, and the
join-set phase could walk it with nextSetBit. That brings it down to 1 bit per
vector.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
