[ZODB-Dev] [BTrees] considerable optimization potential in"intersection"

[Tim Peters]

[Dieter Maurer]
>>> Would you mind when I tried to optimize "intersection"?

[Tim Peters]
>> I think it would be great if you wrote it in Python.

[Dieter]
> I do not think that this is a good idea:
>
>   To optimize intersection for a minimal number of loads,
>   the tree structure is very essential (to be able to
>   skip whole subhierarchies).
>
>   But, this structure is not exposed at the Python level...
>
> I know that you crack this structure for the tree display and checking
> code. It appears that you use pickling/unpickling there.

That is what I had in mind, but note that check.py doesn't even import
pickle.  That's not necessary.  It calls __getstate__() methods to expose
the internal structure, and those are dirt cheap when you're *aiming* at
orders-of-magnitude speeds.
 
> But, intersection should work efficiently for both in-memory and
> out-of-memory structures. It should not be necessary to pickle the tree
> in order to get its structure.

It doesn't; it gets the state of one node at a time, if and when it needs
the state for a node.  Getting the state for a node does not cause anything
to be loaded beyond the node's own state.  check.py *eventually* calls
__getstate__ on every node in the tree, one at a time, and that's why it
ends up loading the whole tree.  But displaying the entire tree, or checking
the entire tree, plainly require loading the entire tree.
 
> I may be wrong, but I have the feeling that the "C" level is the right
> place to attack.

You haven't said what it is you intend to optimize, so I can only guess that
we'd be better off if it were coded in Python.  The only use cases presented
so far (yours and Andreas's) were obviously doable with a very simple Python
loop (which Andreas gave).  You have to know that the sizes are very
different in order to be sure it will pay off, though.  If you can worm
around that in C, you can worm around that in Python too, but the Python
code will be a lot easier to develop and maintain, and won't be a mass of
refcounting, NULL pointer, and persistent-notification bugs waiting to bite.

> Note also, that intersection is non-destructive. Reading the input trees
> requires that the nodes are loaded from ZODB before access and that they
> stay there while we access them.

I'm not sure what you're saying there.  Doing, for example,
btree.__getstate__(), where btree is the root of a BTree, does not load any
child nodes.  It does create ghosts for them (if and only if they're not
already in memory), but that's true if you try to look at anything in btree
from C code too.  Writing it in Python will automatically unghostify nodes
as, when and if needed, and get all the refcounting straight.

> I know, there are macros for this effect. Otherwise, the structure
> is straight forward: intersection needs not to worry about "first leaf
> pointers" and "leaf chain" and other subleties that make plague other
> algorithms.

It indeed doesn't have to worry about maintaining BTree invariants, since
it's not mutating anything.  Depending on what you have in mind, though, it
may be very useful to *exploit* the 3 different kinds of pointers.

BTW, although we haven't advertised it, in ZODB 3.3 the bucket next pointer,
and the btree firstbucket pointer, are available from Python as attributes.
This wasn't intended for dirty tricks <wink>, it was a start at trying to
make all these things more friendly for subclassing (there are cases where
application code could benefit by customizing now-rigid bucket and btree
policies, like the max-node-size and how-to-split policies).