Re: Using/requiring Cairo

[Han-Wen Nienhuys]

On Sat, Jun 24, 2017 at 5:54 PM, David Kastrup <address@hidden> wrote:
> 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.

Well, I stand corrected then.

> 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.

I suppose that functions like

  https://www.cairographics.org/manual/cairo-Paths.html#cairo-path-extents

would be a boon.

I was tickled to reply to your mail, because it was full of complaints
('hugely inefficient', 'humongous amount of resources'), without any
measurements. Optimizing code without measuring is common pitfall, and
I would not want you to fall in it.

I would be much more supportive if you could show some numbers where
memory/CPU is used right now, and could show some data how much Cairo
would improve on things. It's quite possible that you are right,  but
then it should be easy to come up with some supporting data.

>>> 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.

Another approach could be to integrate it, and use it to replace all
bounding box computations, but continue to use Scheme expression =>
string => PS => PDF approach for the evaluation. That would let you
get rid of some of the crummy code you quoted. In addition, you could
create a cross-test mode, where you compare the Cairo bounding boxes
with the traditional ones, to find bugs.

-- 
Han-Wen Nienhuys - address@hidden - http://www.xs4all.nl/~hanwen