Urs Liska<address@hidden> writes:
Am 07.08.2010 09:14, schrieb David Kastrup:
Graham Percival<address@hidden> writes:
On Thu, Aug 05, 2010 at 05:26:15AM -0700, ornello wrote:
In my installation, Lilypond runtime seems to increase exponentially (at
least not linearly) with the number of pages to engrave. Is there any option
to speed up Lilypond, e.g. by removing time-consuming engravers, such that
the performance only increases (almost) linearly with the number of pages?
There's a section in the Learning manual called "speeding up
lilypond", or something like that. This sounds like a good place
to look.
Essentially exponential behavior can't really be cured with anything
except fixing the algorithm.
Can one expect a program like LilyPond to work in a linear fashion?
The question is not what one can expect, but what one can achieve. I do
think that the optimization problem can be reduced essentially to one of
linear programming. That's what TeX's linebreaking does. The reason
that this has not been extended to TeX's pagebreaking is
a) memory requirements at its creation time were such that it was
utterly infeasible to keep significantly more than one page in-memory.
b) page composition was done using an "output routine" provided by the
user, in a language that was not side-effect free and requiring global
assignments.
Both of these constraints are not inherently present with Lilypond.
Linear programming techniques for this optimization problem are
basically O(n), where things like maximum measures per line/page
contribute a large constant factor depending on things like font and
paper size. Combined page/line breaking has an expensive impact on that
factor, but you still have basically linear performance for finding the
optimum candidate among a set with exponentially growing size.
IIUC a linear increase could only be expected if lily would just
"walk" through the score from beginning to end. But if it has to
process the score as a whole (i.e. "still know at the end what was at
the beginning" or "know the end before typesetting the first barline")
I find it quite natural that its usage of processing time and probably
memory increases exponentially.
Whether or not you consider it "natural" to walk through the whole
candidate space without pruning, it is useless for non-trivial scores.
While practically any software may be improved and optimized I think
that if the scores become too complex to be handled within an
acceptable amount of time the only real solution is new hardware.
I repeat: you can't fight exponential complexity with hardware (or with
peephole optimization).