Re: Efficiency of alist vs. vector/array

[David Kastrup]

Urs Liska  writes:

> Am 19.07.2017 um 10:43 schrieb David Kastrup:
>> Urs Liska  writes:
>>
>>> Obviously I didn't make myself clear enough and probably I should have
>>> invested the time for a minimal example. When sloppily using the word
>>> "override" I didn't mean "\override" but applying a value to a grob
>>> property in a grob callback function.
>>>
>>> I have a data structure idTweaks, currently using an alist:
>>>
>>> idTweaks = #'()
>>>
>>> This alist gets populated with elements consisting of a key and a
>>> #'(property . value) pair with
>>>
>>> idTweak =
>>> #(define-void-function (id prop val)(string? symbol? scheme?)
>>>(set! idTweaks (assoc-set! idTweaks id (cons prop val
>>>
>>> using commands like
>>>
>>> \idTweak "id-1" color #red
>>> \idTweak "id-2" extra-offset #'(2 . -2)
>> You are aware that
>>
>> idTweaks.id-1.color = #red
>> idTweaks.id-2.extra-offset = #'(2 . -2)
>>
>> would have done the same?
>
> No!
> (but only if id-1 were a symbol, right?

Ouch.  I grow old.  In Scheme, it is, but of course not in LilyPond.

idTweaks.1.color

would actually work (but be something different) and

idTweaks."id-1".color = #red

would work in current versions (and be the same as your code).

I had a longstanding idea where LilyPond would accept alists which could
use either a hash or vector rather than a pair as element (or even
tail?) of an alist.  Obviously that could speed up some operations (and
at least the default grob properties would not significantly slow down
the lookup of either them or unset properties).  One would also be able
to "compress" such lists on-demand and convert them into hashtables.

-- 
David Kastrup

___
lilypond-user mailing list
lilypond-user@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-user

Re: Efficiency of alist vs. vector/array

[Urs Liska]

Am 19.07.2017 um 10:43 schrieb David Kastrup:
> Urs Liska  writes:
>
>> Obviously I didn't make myself clear enough and probably I should have
>> invested the time for a minimal example. When sloppily using the word
>> "override" I didn't mean "\override" but applying a value to a grob
>> property in a grob callback function.
>>
>> I have a data structure idTweaks, currently using an alist:
>>
>> idTweaks = #'()
>>
>> This alist gets populated with elements consisting of a key and a
>> #'(property . value) pair with
>>
>> idTweak =
>> #(define-void-function (id prop val)(string? symbol? scheme?)
>>(set! idTweaks (assoc-set! idTweaks id (cons prop val
>>
>> using commands like
>>
>> \idTweak "id-1" color #red
>> \idTweak "id-2" extra-offset #'(2 . -2)
> You are aware that
>
> idTweaks.id-1.color = #red
> idTweaks.id-2.extra-offset = #'(2 . -2)
>
> would have done the same?

No!
(but only if id-1 were a symbol, right?

>> In the callback stage the callback function looks up if a grob has an
>> 'id property and if there's a matching entry in idTweaks:
>>
>> #(define (apply-tweaks grob)
>>(let*
>> ((id (ly:grob-property grob 'id))
>>  (tweak (if (null? id)
>> #f
>> (assoc-ref idTweaks id
>> (if tweak
>> (ly:grob-set-property! grob (car tweak) (cdr tweak)
> At any rate: yes it would make sense to use a hashtable here.  

OK, good to know (and be confirmed).

> It would
> also make a lot of sense to use 'id-1 (namely a symbol) rather than
> "id-1" for lookup since symbols are much easier and faster to compare
> for equality than strings are (and can be compared using eq? rather than
> equal?).  

In fact in my real example I *do* change the typecheck of the id
property to use symbols, but I didn't want to complicate the minimal
example :-)

> I wouldn't tamper with the alist-based property handling of
> grobs though.

I didn't think about such a thing.

Best
Urs

-- 
u...@openlilylib.org
https://openlilylib.org
http://lilypondblog.org


___
lilypond-user mailing list
lilypond-user@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-user

Re: Efficiency of alist vs. vector/array

[David Kastrup]

Urs Liska  writes:

> Obviously I didn't make myself clear enough and probably I should have
> invested the time for a minimal example. When sloppily using the word
> "override" I didn't mean "\override" but applying a value to a grob
> property in a grob callback function.
>
> I have a data structure idTweaks, currently using an alist:
>
> idTweaks = #'()
>
> This alist gets populated with elements consisting of a key and a
> #'(property . value) pair with
>
> idTweak =
> #(define-void-function (id prop val)(string? symbol? scheme?)
>(set! idTweaks (assoc-set! idTweaks id (cons prop val
>
> using commands like
>
> \idTweak "id-1" color #red
> \idTweak "id-2" extra-offset #'(2 . -2)

You are aware that

idTweaks.id-1.color = #red
idTweaks.id-2.extra-offset = #'(2 . -2)

would have done the same?

> In the callback stage the callback function looks up if a grob has an
> 'id property and if there's a matching entry in idTweaks:
>
> #(define (apply-tweaks grob)
>(let*
> ((id (ly:grob-property grob 'id))
>  (tweak (if (null? id)
> #f
> (assoc-ref idTweaks id
> (if tweak
> (ly:grob-set-property! grob (car tweak) (cdr tweak)

At any rate: yes it would make sense to use a hashtable here.  It would
also make a lot of sense to use 'id-1 (namely a symbol) rather than
"id-1" for lookup since symbols are much easier and faster to compare
for equality than strings are (and can be compared using eq? rather than
equal?).  I wouldn't tamper with the alist-based property handling of
grobs though.

-- 
David Kastrup

___
lilypond-user mailing list
lilypond-user@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-user

Re: Efficiency of alist vs. vector/array

[Urs Liska]

Obviously I didn't make myself clear enough and probably I should have
invested the time for a minimal example. When sloppily using the word
"override" I didn't mean "\override" but applying a value to a grob
property in a grob callback function.

I have a data structure idTweaks, currently using an alist:

idTweaks = #'()

This alist gets populated with elements consisting of a key and a
#'(property . value) pair with

idTweak =
#(define-void-function (id prop val)(string? symbol? scheme?)
   (set! idTweaks (assoc-set! idTweaks id (cons prop val

using commands like

\idTweak "id-1" color #red
\idTweak "id-2" extra-offset #'(2 . -2)

In the callback stage the callback function looks up if a grob has an
'id property and if there's a matching entry in idTweaks:

#(define (apply-tweaks grob)
   (let*
((id (ly:grob-property grob 'id))
 (tweak (if (null? id)
#f
(assoc-ref idTweaks id
(if tweak
(ly:grob-set-property! grob (car tweak) (cdr tweak)

Finally in the music the callback is registered and ids assigned to grobs:

{
  \override NoteHead.before-line-breaking = #apply-tweaks
  \override Script.before-line-breaking = #apply-tweaks
  \once \override NoteHead.id = "id-1"
  c' d' -\tweak #'id "id-3" \f e' -\tweak #'id "id-2" ->
}

In this case three items have an id but only two have a tweak assigned:
the c' notehead will be red and the accent on the e will be offset.

(With some additional complexity this can be extended to store lists of
tweaks to an object (e.g. override both color and extra-offset) and to
access the notecolumn, e.g. to shift a note horizontally when still in
the before-line-breaking stage).


Am 18.07.2017 um 18:52 schrieb David Kastrup:
> Urs Liska  writes:
>
>> What I do *not* know is: would that be worth it (apart from the
>> educational value) in real life? In that project I had a song of a few
>> pages containing about 5.600 IDs. It's not clear how many override
>> that would get when finished, but let's assume it'll grow to a few
>> hundred and take 100 as a hypothetical reference.
> Why?  If you do \override without \temporary, any previous alist element
> with the given id set in the same context will be removed first.
>
> So where do you get the 100?

The 100 is a hypothetical number of tweaks that I may need to apply when
I'm going to bring the score to publication quality.
The 5.600 is the actual number of 'id tweaks produced by the external
script that has generated the .ly file.

My question is: an alist is obviously not the ideal data structure for
this setting as it will require 5.600 alist lookups with 555.000 actual
comparisons. If idTweaks was something that can be searched binarily it
would be 5.500x8 (for the unused ids) + 100x4 (for the actual matches)
comparisons, which is significantly less.

The question (at my learning stage) is: does it really matter in that
order of magnitude or would it be "premature optimization" to look for
an improved algorithm/data structure?
And how would the perspective of dramatically bigger scores affect that
estimate?

>
>> My gut feeling is that's really a lot of unnecessary stuff, and one
>> should try to improve where possible. OTOH I don't really have
>> substantial experience wtih this tpic and don't know how that relates
>> to what's going on in the whole compilation process. OTOH what would
>> be if I consider using such a setting for a full symphony with maybe
>> 100.000 grobs and 1.000 overrides? Would I then have to consider a
>> better data structure? Would I then have to think about a totally
>> different approach?
>>
>> Any food for thought, educated guesses, advice?
> You could use an object property just for storing the id of a grob if
> the override machinery (which works in context hierarchies and handles
> subproperties) is not needed.
>
> Check out make-object-property in the manual.

This probably doesn't apply to my original use-case but I'll do that
anyway, of course.

Best
Urs

-- 
u...@openlilylib.org
https://openlilylib.org
http://lilypondblog.org


___
lilypond-user mailing list
lilypond-user@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-user

Re: Efficiency of alist vs. vector/array

[David Kastrup]

Urs Liska  writes:

> What I do *not* know is: would that be worth it (apart from the
> educational value) in real life? In that project I had a song of a few
> pages containing about 5.600 IDs. It's not clear how many override
> that would get when finished, but let's assume it'll grow to a few
> hundred and take 100 as a hypothetical reference.

Why?  If you do \override without \temporary, any previous alist element
with the given id set in the same context will be removed first.

So where do you get the 100?

> My gut feeling is that's really a lot of unnecessary stuff, and one
> should try to improve where possible. OTOH I don't really have
> substantial experience wtih this tpic and don't know how that relates
> to what's going on in the whole compilation process. OTOH what would
> be if I consider using such a setting for a full symphony with maybe
> 100.000 grobs and 1.000 overrides? Would I then have to consider a
> better data structure? Would I then have to think about a totally
> different approach?
>
> Any food for thought, educated guesses, advice?

You could use an object property just for storing the id of a grob if
the override machinery (which works in context hierarchies and handles
subproperties) is not needed.

Check out make-object-property in the manual.

-- 
David Kastrup

___
lilypond-user mailing list
lilypond-user@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-user