[Pachi] Converting tree children linked lists to arrays

Petr Baudis pasky at ucw.cz
Sun Sep 7 15:02:17 CEST 2014

On Sun, Sep 07, 2014 at 11:10:36AM +0200, Petr Baudis wrote:
>   Hi!
>   (That email went in three different directions, so I'm trying
> to keep the stuff untangled. :-)
>   (Short intro: It should be quite faster if we allocated all tree
> children node structures en bloc during node expansion - eat less
> memory and better locality.  I gave up on that project but Sthalik
> offered to help.)
> On Fri, Aug 08, 2014 at 06:55:11PM +0200, Stanisław Halik wrote:
> > FWIW, still remember the discussed project to do with removing
> > needless indirection.
> > 
> > Since discussing it on IRC was a pain... is node sibling pointer
> > needed when turning child node pointers galore into an array? There
> > was code that relies on the sibling pointer, and hardly able to make
> > it up to spec without getting the underlying idea.
>   I don't *really* remember either. :-)
>   But how would I find out?
> 	git grep sibling
> and go through all the matches (there isn't that many of them).  From
> cursory examination, it seems in all of them (besides current tree
> manipulation code) sibling pointer is used just for iteration, so if
> we had an array instead we could get rid of it.
>   I think getting rid of this pointer was supposed to be one of the
> advantages here.
> 				Petr Baudis
> _______________________________________________
> Pachi mailing list
> Pachi at v.or.cz
> http://rover.ms.mff.cuni.cz/mailman/listinfo/pachi

On Sun, Sep 07, 2014 at 11:14:00AM +0200, Stanisław Halik wrote:
> First attempt at struct node refactor failed when the 'sibling'
> struct member turned out to be essential. Some logic for node
> frobbing depends critically on that particular member.

  Hmm, which of it?

> I can do the tedious work since you're the brainiac here. As such:

  Hehe. Well, figuring out exactly how to shuffle stuff is about as hard
as shuffling itself; and I gave it up because I didn't have time for it
for the first time and it's definitely not better now. :-(  So I cannot
help with detailed speccing out / planning, though I'll try to answer
specific questions.

> Decide which stuff to reorganize. Whether node 'children' member can
> be safely realloc'd[1] without care for reentrancy. Elaborate
> whether struct nodes are shared between threads here.

  Nodes are definitely shared between threads.  Once it's connected
to the tree, we cannot manipulate it anymore, besides updating the
winrate etc. stats.

> Which stuff can't be touched. 'children' are the point here, but
> let's arrive at what to keep, otherwise another refactor failure...

  Right now, each node is a self-contained object that carries all
the stats, and parent/sibling/firstchild pointers; children are
in a linked list, connected by sibling pointers.

  My general idea was to add a "nodeset" object, which, at once, holds
*all* nodes that are children of a particular node.  Something like

	struct nodeset {
		struct node *parent;
		struct node nodes[];

	struct node {
		/* index in nodeset, so that we can derive (struct nodeset *)
		 * from (struct node *); there could be an even more
		 * clever way to use pointer alignments to encode
		 * the necessary information in just a few bits. But
		 * this can be also improved later. */
		unsigned short i;

		/* NULL pointer until tree_node_expand(), which
		 * allocates the nodeset and wires it up. */
		struct nodeset *children;

		struct move_stats u, prior, ...;

If the ``i`` business seems weird, we can just stuff parent pointer
in each child for now and go from there later.

  It's possible even more radical change may be feasible - breaking
down the struct node completely and keep all the stats of all children
in separate "vectors".  So:

	struct nodeset {
		struct nodeset *parent;

		// array of values, one for each child
		struct move_stats *u, *prior, *...;
		struct nodeset **children;

But it would make a lot of stuff complicated (how do you refer to
a particular node, besides a (struct nodeset *, int) tuple, eew?)
and I'm not sure if it would improve performance by a lot or not at all.

				Petr Baudis
	Life is short, the craft long, opportunity fleeting, experiment
	treacherous, judgment difficult.  -- Hippocrates

More information about the Pachi mailing list