Re: Using/requiring Cairo

[David Kastrup]

Han-Wen Nienhuys <address@hidden> writes:

> On Sat, Jun 24, 2017 at 12:43 PM, David Kastrup <address@hidden> wrote:
>> What does that mean?  Mainly a viable migration strategy where we might
>> be able to drop catering for a whole lot of graphics programming
>> ourselves by introducing a dependency on Cairo.  I am not overly
>
> what "catering for graphic programming" mean? There is graphical
> programming, but a lot of it is done already. Moving towards a new
> library will be a big undertaking, so it could use more justification.
>
>> enthused about the programming quality of Cairo but LilyPond's quality
>> tends to be worse in the same departments
>
> gee, thanks.

Shrug.  What do you expect of large amount of code that's written once
and basically left alone afterwards?  The SVG backend produces sort-of
experimental code (and still has font/spacing problems that "should not
be there").  There are significant remaining parts of the internals that
work with radians instead of degrees (like all graphics formats,
libraries and backends use, including PostScript/PDF), leading to
numerical pain because right angles have no numerically stable
representation.

Basically everything dealing with transformation matrices or
coefficients unpacks Scheme lists (instead of uniform arrays or records
matched to C data structures) into reals and back.

There is, both in C as well as in Scheme, code like

(define (make-bezier-sandwich-stencil coords thick)
   (make-path-stencil
       `(moveto
           ,(car (list-ref coords 0))
           ,(cdr (list-ref coords 0))
         curveto
           ,(car (list-ref coords 1))
           ,(cdr (list-ref coords 1))
           ,(car (list-ref coords 2))
           ,(cdr (list-ref coords 2))
           ,(car (list-ref coords 3))
           ,(cdr (list-ref coords 3))
         curveto
           ,(car (list-ref coords 4))
           ,(cdr (list-ref coords 4))
           ,(car (list-ref coords 5))
           ,(cdr (list-ref coords 5))
           ,(car (list-ref coords 0))
           ,(cdr (list-ref coords 0))
         closepath)
       thick
       1
       1
       #t))

that goes to a lot of effort to just juggle data from one Scheme
representation into another Scheme representation, without an actual
representation useful for efficient processing.

There is code like

(define (bezier-part-min-max x1 x2 x3 x4)
  ((lambda (x) (list (reduce min 10000 x) (reduce max -10000 x)))
   (map
    (lambda (x)
      (+ (* x1 (expt (- 1 x) 3))
         (+ (* 3 (* x2 (* (expt (- 1 x) 2) x)))
            (+ (* 3 (* x3 (* (- 1 x) (expt x 2))))
               (* x4 (expt x 3))))))
    (if (< (+ (expt x2 2) (+ (expt x3 2) (* x1 x4)))
           (+ (* x1 x3) (+ (* x2 x4) (* x2 x3))))
        (list 0.0 1.0)
        (filter
         (lambda (x) (and (>= x 0) (<= x 1)))
         (append
          (list 0.0 1.0)
          (map (lambda (op)
                 (if (not (eqv? 0.0
                                (exact->inexact (- (+ x1 (* 3 x3)) (+ x4 (* 3 
x2))))))
                     ;; Zeros of the bezier curve
                     (/ (+ (- x1 (* 2 x2))
                           (op x3
                               (sqrt (- (+ (expt x2 2)
                                           (+ (expt x3 2) (* x1 x4)))
                                        (+ (* x1 x3)
                                           (+ (* x2 x4) (* x2 x3)))))))
                        (- (+ x1 (* 3 x3)) (+ x4 (* 3 x2))))
                     ;; Apply L'hopital's rule to get the zeros if 0/0
                     (* (op 0 1)
                        (/ (/ (- x4 x3) 2)
                           (sqrt (- (+ (* x2 x2)
                                       (+ (* x3 x3) (* x1 x4)))
                                    (+ (* x1 x3)
                                       (+ (* x2 x4) (* x2 x3)))))))))
               (list + -))))))))

which just is better done in C, and even better left in the
responsibility of people who specialize in maintaining a graphics
library rather than a music typesetting program.

Stencils and their compositions are represented in Scheme data
structures that take considerable time to traverse and interpret even
though they aren't actually traversed and interpret in Scheme itself all
that much.

We've had reports where large works exhausted a 32bit address space.

Cairo is just modeled around a different programming model and data
structures suitable for the processing that its API provides.

>> and it's also hugely inefficient due to using Scheme data structures
>> and programming where they are rather inappropriate and waste a
>> humongous amount of resources.
>
> Show some numbers? How much is "humongous", and how much faster will
> it be with the snazzy new Cairo infrastructure?
>
> $ time ./out/bin/lilypond input/regression/mozart-hrn-3.ly
> GNU LilyPond 2.19.63
> Processing `input/regression/mozart-hrn-3.ly'
> Parsing...
> Interpreting
> music...[8][16][24][32][40][48][56][64][72][80][88][96][104][112][120]
> Preprocessing graphical objects...
> Interpreting music...
> Interpreting music...
> Interpreting music...[8][16][24][32][40][48]
> Preprocessing graphical objects...
> Interpreting music...
> Interpreting
> music...[8][16][24][32][40][48][56][64][72][80][88][96][104][112][120][128][136][144]
> Preprocessing graphical objects...
> MIDI output to `mozart-hrn-3.midi'...
> MIDI output to `mozart-hrn-3-1.midi'...
> MIDI output to `mozart-hrn-3-2.midi'...
> Finding the ideal number of pages...
> Fitting music on 3 or 4 pages...
> Drawing systems...
> Layout output to `/tmp/lilypond-vi9Khi'...
> Converting to `mozart-hrn-3.pdf'...
> GS ps->pdf done: took 0.48000000 secs
> Deleting `/tmp/lilypond-vi9Khi'...
> PS done: took 0.60000000 secs
> Success: compilation successfully completed
>
> real 0m3.225s
> user 0m2.997s
> sys 0m0.209s
>
>
> Assuming you did everything optimally, you could shave off about 20%
> of the end-to-end runtime in this case.

Uh, that's just the PostScript->PDF conversion.  "Preprocessing
graphical objects" spends a lot of time with graphics data.  So does
"Finding the ideal number of pages".  So does "Drawing systems".

> A simpler alternative could be to revisit how the PS is structured;
> it's hard to believe this is a good way to place text, for example:
>
> 5.3676 -165.1853 moveto /TeXGyreSchola-Regular 3.44335938 output-scale
> div selectfont
> 0.5804 0.0000 0.0000 /exclam
> 0.7512 0.0000 0.0000 /t
> 0.6146 0.0000 0.0000 /i
> 0.5463 0.0000 0.0000 /space

There seems little point in worrying about how to structure PS if you
don't actually need PS in the first place.

> Also, the PS could be written to a pipe, so GS runs in parallel to
> Lily. Some of the time in GS could overlap with LilyPond.

That does not decrease the CPU time spent so it would just make a bit
better use of a multiprocessor setup.  But I don't think that the time
LilyPond starts writing PostScript output to the time it ends writing it
is all that long anyway.

>> It would be a large amount of work to bring LilyPond's graphics
>> programming up to scratch.  Moving to Cairo's data structures alone
>> would be quite advantageous and would likely speed up backend
>> operations significantly.
>
> which ones? In terms of graphics, the backend just does interval
> unions and offsets (floating point comparisions and additions) through
> the Stencil object.

LilyPond 2.16+ thoroughly works with stencil outlines.  I don't think
you are familiar with files like lily/stencil-integral.cc .

> Unless you also restructure how objects are grouped, it's going to be
> similar.
>
> I can't recall seeing stencil evaluation ever figure prominently on a
> profile.

Outlining stencils gave us quite a significant performance hit, and this
concerns stencil evaluation exclusively.

>> We might also be able to forego creating PostScript as an
>> intermediate stage to creating PDF and create bitmap formats without
>> using PostScript as well (again, this should really speed up things).
>
> that's the first realistic speed up; the PDF => PNG step seems
> expensive.

It's actually PS => PNG, so it's using Ghostscript once instead of
twice.  Which is still one time more often than desirable.

>> The first step would likely just involve moving to Cairo data
>> structures while keeping most of the current code except where the
>> code would duplicate Cairo API calls in a reasonably straightforward
>> way.
>
> I would suggest trying make a GUILE binding of sorts for Cairo, adding
> that in parallel to existing GS support, and hacking untili you have
> feature parity. Then drop the GS support, and migrate the cairo data
> structures more towards the core of the program as needed.

The cost of the Cairo dependency is significant, so it would certainly
help if the payback was significant as well.

>
> I strongly recommend being in a state where the Cairo support is
> half-merged but only half-working.
>
> timiing patch follows.

-- 
David Kastrup