[ZODB-Dev] [BTrees] considerable optimization potential
in"intersection"
Dieter Maurer
dieter at handshake.de
Thu Aug 5 14:14:21 EDT 2004
Tim Peters wrote at 2004-8-4 23:17 -0400:
> ...
>> Would you mind when I tried to optimize "intersection"?
>
>I think it would be great if you wrote it in Python.
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. 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.
I may be wrong, but I have the feeling that the "C" level
is the right place to attack.
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 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.
--
Dieter
More information about the ZODB-Dev
mailing list