Re: [Texmacs-dev] Re: TeXmacs+Axiom

[Henri Lesourd]

Josef Weidendorfer wrote:

> I tried to come up with an extreme case to be able to reproduce how
> this works. I made up one single paragraph with around 100 lines and
> _lots_ of font changes (around 6 per line).
> Finally I got a latency of around 1/3 of a second from typing one char
> to display. This made some observations possible.
> (I really do not think this is a "typical" paragraph).
>
>  
No, it is not a typical paragraph, but IMHO, no other editor than TeXmacs
spends so much time (1/3 of a second...) on such an example (we would
have to check if it is really true, but chances are...).


> This is from a fresh CVS checkout today.
>
> IMHO there are a few optimizations possible:
>
> * Most of the time, you append characters at the end of the paragraph.
> I imagined that this should be faster than typing in the middle, but
> this assumption obviously is wrong; the whole paragraph is relayouted
> even in this case. Of course, this is totally correct.
>
> We could cheat here: do only a relayout from the typing position to
> the end of the paragraph after every key, and a complete relayout
> only when idle.
> However, I did not check the code if this is easily possible at all.
>
>  
What other, simpler editors do when something is inserted inside
a line is optimize in such a way that they only perform a BitBlt
on the right side of the line, and then they just print the inserted
characters at the position of the cursor, then move the cursor.

This way, the performed operations are (roughly) :
a) BitBlt-ing the right side of the current line ;
b) Printing a string at the position of the cursor, then moving the cursor ;
c) updating your internal datastructure (i.e., performing some kind of
 strcat() operation) to memoize the fact that a new string has been 
inserted
 somewhere ;

The operations a) and b) are operations on the physical screen that are 
fast,
and c) is very fast as well.


The root of the problem is that TeXmacs doesn't operates this way, what it
does is that it rewrites a tree datastructure which represents the 
markup into
a box datastructure which represents what should be drawn on the screen.

These datatructures are heavy, and in any case, no matter of how intelligent
you are, this two-step (i.e. : generating the box tree ==> drawing the 
boxes)
algorithm will remain more costly than a simpler one.

By the way, I remember pretty well writing a compiler, and I observed
that you can divide the compilation time by two if you do not generate
a syntactic tree that you traverse later to generate the assembly langage,
namely, if you can find a way of generating the assembly language
directly from a slighly improved version of your tokenized source
code. The conclusion to be drawn from this example is that the
very traversal and building of the datastructures *IS* significant,
especially if you use them only once. In the case of a compiler,
it even costs you 50% of your time !

Since long, I suspect the same kind of problem occurs in the typesetting
code of TeXmacs, although it is perhaps not the only thing to consider.


As a result of this, even for operations as simple than inserting a string
somewhere, several rewriting steps and memory allocations and desallocations
are involved. It is rather likely that even with clever optimizations that
try not to redo everything all the time, and even if these things are done
in a *very* clever way, the TeXmacs rendering algorithm is, and will
remain one order of magnitude slower than the much more leightweight,
usual way of typesetting algorithms in editors.

My opinion is that you just can't have it both ways : either you want
the kind of quality that stems out of LaTeX-like typesetting algorithms,
and then it is costly (or more precisely : what you want is the clarity
of the code implementing the algorithms. It means building a datastructure).

Or either, you implement some simpler, and even a little bit crap rendering
algorithm for wysiwyg editing, and then it is faster, but the quality can
be lower in some cases, perhaps the updating is not complete all the
time, etc. We should perhaps look at implementing a rendering mode
like that if we really want to boost typesetting speed, because no other
way will succeed, except waiting one more Moore's law cycle of improvement
of computer speed...


> * When typing faster than display latency, it can last a few seconds
> before you see anything of your typing. This means that:
> (1) relayouting seems to be done for key press (otherwise it should
>     last a maximum of 0.3 seconds to display after fast typing)
> (2) any redrawing gets completely suppressed when texmacs is busy
>
> (2) is really bad in conjunction with (1). Texmacs should check before
> any relayout is triggered whether there is a further key press already
> in the input queue, and avoid useless relayouts.
> (2) seems to be a bug in the current version according to your
> description?
>  
I agree with you, I never liked (2). It seems to me that it raises
other concerns, and thus, in many respects, it is deceiving and
difficult to implement correctly.


> In strange cases, typesetting seems to become a bottleneck.
>
> Just for the record, here is a small oprofile report for this "relayout
> bottleneck", only texmacs.bin process, for events "CPU_CLK_UNHALTED"
> (= time) and INSTR_RETIRED (number of executed assembly instructions,
> not so important).
>
>    CPU_CLK_UNHALT...|INST_RETIRED:8...|
>      samples|      %|  samples|      %|
>    ------------------------------------
>        25343 81.7648     31711 85.0001 texmacs.bin
>         3887 12.5407      3924 10.5181 libguile.so.17.0.1
>          942  3.0392       925  2.4794 libc-2.5.so
>          552  1.7809       664  1.7798 libpthread-2.5.so
>
> And in more detail...
>
> [Note that there is really nothing to optimize in the following
> functions if the above suggested optimizations can be done!]
>
>  
We would have to be sure that the time spent is really spent for the 
reason we
expect (namely, unnecessary trials to redo typesetting). But it seems 
likely to
be something like that, and perhaps it could be more precisely tuned...