From 18d0f99a0978f1d9061adb72791c69d8827027f8 Mon Sep 17 00:00:00 2001
From: Jean-loup Gailly <jloup@gailly.net>
Date: Sat, 2 Jul 2011 00:04:50 +0200
Subject: [PATCH] UCT: allocate all children nodes at once and contiguously

This improves memory locality and greatly reduces the number
of costly atomic instructions.
---
 uct/tree.c | 20 +++++++++++++-------
 1 file changed, 13 insertions(+), 7 deletions(-)

diff --git a/uct/tree.c b/uct/tree.c
index 74c3f5f..90177b3 100644
--- a/uct/tree.c
+++ b/uct/tree.c
@@ -35,7 +35,7 @@ tree_alloc_node(struct tree *t, int count, bool fast_alloc)
 			return NULL;
 		assert(t->nodes != NULL);
 		n = (struct tree_node *)(t->nodes + old_size);
-		memset(n, 0, sizeof(*n));
+		memset(n, 0, nsize);
 	} else {
 		n = calloc2(count, sizeof(*n));
 	}
@@ -592,21 +592,25 @@ tree_expand_node(struct tree *t, struct tree_node *node, struct board *b, enum s
 	memset(map_prior, 0, sizeof(map_prior));
 	memset(map_consider, 0, sizeof(map_consider));
 	map.consider[pass] = true;
+	int child_count = 1; // for pass
 	foreach_free_point(b) {
 		assert(board_at(b, c) == S_NONE);
 		if (!board_is_valid_play(b, color, c))
 			continue;
 		map.consider[c] = true;
+		child_count++;
 	} foreach_free_point_end;
 	uct_prior(u, node, &map);
 
 	/* Now, create the nodes. */
-	struct tree_node *ni = tree_init_node(t, pass, node->depth + 1, t->nodes);
+	struct tree_node *ni = tree_alloc_node(t, child_count, t->nodes);
 	/* In fast_alloc mode we might temporarily run out of nodes but this should be rare. */
 	if (!ni) {
 		node->is_expanded = false;
 		return;
 	}
+	tree_setup_node(t, ni, pass, node->depth + 1);
+
 	struct tree_node *first_child = ni;
 	ni->parent = node;
 	ni->prior = map.prior[pass]; ni->d = TREE_NODE_D_MAX + 1;
@@ -619,6 +623,7 @@ tree_expand_node(struct tree *t, struct tree_node *node, struct board *b, enum s
 				b->symmetry.x2, b->symmetry.y2,
 				b->symmetry.type, b->symmetry.d);
 	}
+	int child = 1;
 	for (int j = b->symmetry.y1; j <= b->symmetry.y2; j++) {
 		for (int i = b->symmetry.x1; i <= b->symmetry.x2; i++) {
 			if (b->symmetry.d) {
@@ -635,17 +640,18 @@ tree_expand_node(struct tree *t, struct tree_node *node, struct board *b, enum s
 				continue;
 			assert(c != node->coord); // I have spotted "C3 C3" in some sequence...
 
-			struct tree_node *nj = tree_init_node(t, c, node->depth + 1, t->nodes);
-			if (!nj) {
-				node->is_expanded = false;
-				return;
-			}
+			struct tree_node *nj = first_child + child++;
+			tree_setup_node(t, nj, c, node->depth + 1);
 			nj->parent = node; ni->sibling = nj; ni = nj;
 
 			ni->prior = map.prior[c];
 			ni->d = distances[c];
 		}
 	}
+	if (b->symmetry.type == SYM_NONE && child != child_count) {
+		fprintf(stderr, "child %d child_count %d\n", child, child_count);
+		assert(child == child_count);
+	}
 	node->children = first_child; // must be done at the end to avoid race
 }
 
-- 
2.11.4.GIT