Memory overhead for trees?

[François Pinard]

[Aahz]

> I think the memory savings afforded by tuples probably makes a fair bit
> of sense, and I think the Timbot would concur based on comments it has
> made in the past.

If I read you correctly, you assert that tuples are significantly more
economical than lists?  I know they are, but I thought it was essentially
because of an indirect pointer from the object to a separately allocated
array, plus some more overhead for the management of that array with the
mallocator.  I guess it doubles (or so) the memory requirements for nodes
that are binary, and might be less important for nodes having many children.

[François]

> >Could I hope that sub-classing tuples or lists could be done with only
> >little, or maybe no extra memory cost, compared to using tuples or lists
> >directly?  Surely, the idea of sub-classing is very attractive, from the
> >comfort resulting from possible specialised methods over the built-ins.

[Aahz]

> The only way you'd achieve real memory savings in a subclass would be
> through the __slots__ mechanism.

No doubts.  I was thinking of sub-classing tuples or lists, together with
using `__slots__ = []', of course.  My question was about the extra memory
overhead per node, if any, coming from the sub-classing.  At first glance,
I do not see why there would be any, but as I'm not really acquainted with
Python internals, my intuitions might be wrong.

Surely, LISP is very memory-economical in memory for generic trees, and
it's probably hard to beat except for very special cases.  Even for wide
trees that could use Python tuples to hold all children, the sparing of the
`cdr' cells is quickly overwhelmed by the memory overhead from the object
prefix of each sub-tree, whatever its Python representation may be.

-- 
François Pinard   http://www.iro.umontreal.ca/~pinard