Re: [Texmacs-dev] General efficiency of TeXmacs

[Joris van der Hoeven]

On Mon, Jun 15, 2009 at 06:09:46PM +0200, David Allouche wrote:
> How would const references help avoiding reference counting?

Any function call which takes indirect TeXmacs objects as its arguments
(such as strings, trees, etc.) will call copy operators on entry and
destructors on exit. This means that the reference counters are
systematically increased and decreased, even if the objects are read-only.
When passing const references instead, actual copying will only take
place if we build new objects. Increasing the reference counter
when constructing a new object is reasonable anyway and should
not involve a lot of overhead with respect to GCs.

Once again, I more and more believe that GCs should and can be avoided,
because their behaviour is unpredictable. Reference counting involves
a small overhead, but this can be reduced to almost zero by
the use of const references.

> A large amount of the no-op reference counting done by texmacs occurs for
> method parameters: when a counted pointer is passed into a method call, it
> is incremented when entering the method, and decremented when unwinding the
> method's stack frame. This is particularly bad in tree-traversal code when
> all tree_rep objects in a tree are touched on recursive descent and then
> again on unwinding, causing many cache misses.
> 
> Presumably, good speedups could be achieved by using uncounted pointers when
> the compiler could prove that 1. the callees do not store the pointer in
> data structures 2. the pointer cannot be returned up the call stack above
> the caller that own the last counted reference to the object.
> 
> I failed to find a way to get the C++ compiler to prove point 2, that did
> not require major changes to the texmacs code, so I gave up on this
> approach. Some of the newer C++ 0x language features might make it possible
> to solve this problem.

The standard way to do is to use const methods in addition to const references.
We systematically do this in mathemagix.

> While we speak of memory management, I had suspected for a long time that
> one cause of texmacs slowness is bad time-space locality for the omnipresent
> tree-string structure. IIRC, the small-objects allocator of texmacs uses a
> naive LIFO free-list approach to reusing memory. I suspect that it leads to
> tree structures where neighboring nodes are scattered in memory.

They are, but this is not necessarily bad for modern types of memory,
with many cache lines. I remember that we looked at the cache misses once;
almost 90% of them were due to guile...

> One project that could potentially have large benefits in reducing memory
> management overhead and cache misses would be to use contiguous buffers for
> both tree and string blocks forming a single structure. The blocks
> themselves would not be managed (no GC or refcounting), and the structure
> would be periodically repacked (maybe using a copying gc approach) to
> reclaim memory add inserted blocks at the ideal place in the structure.

I have been considering this approach in a more ad hoc way,
for the main edit tree, which would be easier to implement.
I did not try yet, though. However, memories are quite clever nowadays;
I am not sure that we would win a lot.

Best wishes, Joris