Issue 561640045: Copy alist instead of deep copy on Grob clone (Closed)
Description Copy alist instead of deep copy on Grob clone
On the MSDM score, ly_deep_copy takes 1.58% of runtime according a
grpof. Removing it shows a consistent 1.4% improvement in user
time.
The deep copy was introduced together with the separation of object
properties and value properties. This is because the Grob substition
needs did a recursive rewrite of all properties, and the equivalent
for value (ie. non-object) properties is to do a deep copy.
The deep copy does not really solve a problem, because the reader
calling get_property cannot distinguish grob-local values from
immutable, shared values. The sort of modification that a deep copy
protects against would modify the shared data in this case, leading to
bugs.
Patch Set 1 #Patch Set 2 : expand description #Patch Set 3 : description #
MessagesTotal messages: 16
Please give reasons for changes, ie why isn't it necessary to do a deep copy? Is it currently not failing a test, are the shallow copies immutable anyway, is there some other guarantee? IMO pushing less changes with strictly better descriptions will get us further in the long run.
Sign in to reply to this message.
expand description
Sign in to reply to this message.
On 2020/04/13 20:44:47, hahnjo wrote: > Please give reasons for changes, ie why isn't it necessary to do a deep copy? Is > it currently not failing a test, are the shallow copies immutable anyway, is > there some other guarantee? Done.
Sign in to reply to this message.
it's hard to say if this makes a measurable difference: $ grep -C1 User.time timing-deepcopy.txt Command being timed: "lilypond -I carver MSDM" User time (seconds): 56.16 System time (seconds): 0.73 -- Command being timed: "./out/bin/lilypond.baseline -I carver MSDM" User time (seconds): 56.50 System time (seconds): 0.76 -- Command being timed: "lilypond -I carver MSDM" User time (seconds): 56.27 System time (seconds): 0.80 -- Command being timed: "./out/bin/lilypond.baseline -I carver MSDM" User time (seconds): 56.13 System time (seconds): 0.73 -- Command being timed: "lilypond -I carver MSDM" User time (seconds): 56.39 System time (seconds): 0.79 -- Command being timed: "./out/bin/lilypond.baseline -I carver MSDM" User time (seconds): 56.28 System time (seconds): 0.68
Sign in to reply to this message.
On 2020/04/13 21:01:11, hanwenn wrote: > it's hard to say if this makes a measurable difference: > > [...] So then ... why do it at all? From a code perspective, a deep copy looks saner in terms of "encapsulation" (one principle of object-oriented programming). If there is no provable gain, I'm for leaving the current code alone until there is good reason to change - "premature optimization is the root of all evil"
Sign in to reply to this message.
On 2020/04/14 07:00:56, hahnjo wrote: > On 2020/04/13 21:01:11, hanwenn wrote: > > it's hard to say if this makes a measurable difference: > > > > [...] > > So then ... why do it at all? From a code perspective, a deep copy looks saner > in terms of "encapsulation" (one principle of object-oriented programming). If > there is no provable gain, I'm for leaving the current code alone until there is > good reason to change - "premature optimization is the root of all evil" As I described in the commit message, this code doesn't protect anything, because get_property can also return values from the immutable list. Due to timing variability, we can't quantify performance changes below 1% of impact, but if we add 10 of them in a row, we do get measurable impact. For the Mutable_properties change, we saw seemingly consistent performance differences, which we could tease apart from deep copy change by separating out the commit.
Sign in to reply to this message.
On 2020/04/14 07:24:10, hanwenn wrote: > On 2020/04/14 07:00:56, hahnjo wrote: > > On 2020/04/13 21:01:11, hanwenn wrote: > > > it's hard to say if this makes a measurable difference: > > > > > > [...] > > > > So then ... why do it at all? From a code perspective, a deep copy looks saner > > in terms of "encapsulation" (one principle of object-oriented programming). If > > there is no provable gain, I'm for leaving the current code alone until there > is > > good reason to change - "premature optimization is the root of all evil" > > As I described in the commit message, this code doesn't protect anything, > because get_property can also return values from the immutable list. get_property uses data backed by mutable_property_alist_, right? So if we do a deep copy there, a copied grob can return different data than the original one. Whereas a copy of the list returns the same references which can be modified from both instances of the object. At least that's the way it works in C++, is there a difference with SCM values? > Due to timing variability, we can't quantify performance changes below 1% of > impact, but if we add 10 of them in a row, we do get measurable impact. > > For the Mutable_properties change, we saw seemingly consistent performance > differences, which we could tease apart from deep copy change by separating out > the commit. We did see a measurable difference with the Mutable_properties change, so this cannot be the reason. I never said it was, it was just a guess.
Sign in to reply to this message.
On Tue, Apr 14, 2020 at 9:28 AM <jonas.hahnfeld@gmail.com> wrote: > > On 2020/04/14 07:24:10, hanwenn wrote: > > On 2020/04/14 07:00:56, hahnjo wrote: > > > On 2020/04/13 21:01:11, hanwenn wrote: > > > > it's hard to say if this makes a measurable difference: > > > > > > > > [...] > > > > > > So then ... why do it at all? From a code perspective, a deep copy > looks saner > > > in terms of "encapsulation" (one principle of object-oriented > programming). If > > > there is no provable gain, I'm for leaving the current code alone > until there > > is > > > good reason to change - "premature optimization is the root of all > evil" > > > > As I described in the commit message, this code doesn't protect > anything, > > because get_property can also return values from the immutable list. > > get_property uses data backed by mutable_property_alist_, right? Use the Source, Jonas! https://github.com/lilypond/lilypond/blob/0c00cd98e81b27325bed5891b950fe7f0f0... it reads from the immutable_list_ if there is no override in the mutable property list. If anything modifies an indirect value they get from get_property, they break the entire formatting process in a grotesque way, because they'd potentially be modifying shared state that is kept in immutable_property_alist_. -- Han-Wen Nienhuys - hanwenn@gmail.com - http://www.xs4all.nl/~hanwen
Sign in to reply to this message.
On 2020/04/14 09:39:18, hanwenn wrote: > On Tue, Apr 14, 2020 at 9:28 AM <mailto:jonas.hahnfeld@gmail.com> wrote: > > > > On 2020/04/14 07:24:10, hanwenn wrote: > > > On 2020/04/14 07:00:56, hahnjo wrote: > > > > On 2020/04/13 21:01:11, hanwenn wrote: > > > > > it's hard to say if this makes a measurable difference: > > > > > > > > > > [...] > > > > > > > > So then ... why do it at all? From a code perspective, a deep copy > > looks saner > > > > in terms of "encapsulation" (one principle of object-oriented > > programming). If > > > > there is no provable gain, I'm for leaving the current code alone > > until there > > > is > > > > good reason to change - "premature optimization is the root of all > > evil" > > > > > > As I described in the commit message, this code doesn't protect > > anything, > > > because get_property can also return values from the immutable list. > > > > get_property uses data backed by mutable_property_alist_, right? > > Use the Source, Jonas! I find this statement inappropriate: I'm not going to read through 100k LOC to find the one thing that is possibly different from what I remember. That is why I ask if I'm missing something. > https://github.com/lilypond/lilypond/blob/0c00cd98e81b27325bed5891b950fe7f0f0... > > it reads from the immutable_list_ if there is no override in the > mutable property list. Ack, that's also what the two names suggested. The code in Grob's copy constructor does a copy of mutable_property_alist_. As far as I understand it contains those elements that have been changed for the Grob? So I'm thinking about the following situation (not real code, just conceptually): Grob g1; g1.set_property("key", "value"); Grob g2(g1); g2.set_property("key", "value2"); set_property will change mutable_property_alist_, and with this change both Grobs will share some of it. So I can't help, but this looks like the g1.get_property("key") will probably return "value2" at the end, no?
Sign in to reply to this message.
On 2020/04/14 10:22:01, hahnjo wrote: > On 2020/04/14 09:39:18, hanwenn wrote: > > On Tue, Apr 14, 2020 at 9:28 AM <mailto:jonas.hahnfeld@gmail.com> wrote: > > > > > > On 2020/04/14 07:24:10, hanwenn wrote: > > > > On 2020/04/14 07:00:56, hahnjo wrote: > > > > > On 2020/04/13 21:01:11, hanwenn wrote: > > > > > > it's hard to say if this makes a measurable difference: > > > > > > > > > > > > [...] > > > > > > > > > > So then ... why do it at all? From a code perspective, a deep copy > > > looks saner > > > > > in terms of "encapsulation" (one principle of object-oriented > > > programming). If > > > > > there is no provable gain, I'm for leaving the current code alone > > > until there > > > > is > > > > > good reason to change - "premature optimization is the root of all > > > evil" > > > > > > > > As I described in the commit message, this code doesn't protect > > > anything, > > > > because get_property can also return values from the immutable list. > > > > > > get_property uses data backed by mutable_property_alist_, right? > > > > Use the Source, Jonas! > > I find this statement inappropriate: I'm not going to read through 100k LOC to > find the one thing that is possibly different from what I remember. That is why > I ask if I'm missing something. Sorry! > https://github.com/lilypond/lilypond/blob/0c00cd98e81b27325bed5891b950fe7f0f0... > > > > it reads from the immutable_list_ if there is no override in the > > mutable property list. > > Ack, that's also what the two names suggested. The code in Grob's copy > constructor does a copy of mutable_property_alist_. As far as I understand it > contains those elements that have been changed for the Grob? So I'm thinking > about the following situation (not real code, just conceptually): > Grob g1; > g1.set_property("key", "value"); > Grob g2(g1); > g2.set_property("key", "value2"); > > set_property will change mutable_property_alist_, and with this change both > Grobs will share some of it. So I can't help, but this looks like the > g1.get_property("key") will probably return "value2" at the end, no? The code now calls ly_alist_copy(), which constructs a new alist with the same keys and values, so your scenario will continue to work correctly. A deep copy protects against something like Grob g1; g1.set_property("key", scm_cons(1,2)); Grob g2(g1); SCM v = g2.get_property("key"); scm_set_cdr_x(v, 3) but this protection only works if the set_property was called beforehand. If you do this for a something that comes out of the immutable list, it'll be a disaster.
Sign in to reply to this message.
On 2020/04/14 19:14:29, hanwenn wrote:
> On 2020/04/14 10:22:01, hahnjo wrote:
> > On 2020/04/14 09:39:18, hanwenn wrote:
> > > it reads from the immutable_list_ if there is no override in the
> > > mutable property list.
> >
> > Ack, that's also what the two names suggested. The code in Grob's copy
> > constructor does a copy of mutable_property_alist_. As far as I understand
it
> > contains those elements that have been changed for the Grob? So I'm thinking
> > about the following situation (not real code, just conceptually):
> > Grob g1;
> > g1.set_property("key", "value");
> > Grob g2(g1);
> > g2.set_property("key", "value2");
> >
> > set_property will change mutable_property_alist_, and with this change both
> > Grobs will share some of it. So I can't help, but this looks like the
> > g1.get_property("key") will probably return "value2" at the end, no?
>
> The code now calls ly_alist_copy(), which constructs a new alist with the same
> keys and values,
> so your scenario will continue to work correctly.
>
> A deep copy protects against something like
>
> Grob g1;
> g1.set_property("key", scm_cons(1,2));
> Grob g2(g1);
> SCM v = g2.get_property("key");
> scm_set_cdr_x(v, 3)
>
> but this protection only works if the set_property was called beforehand. If
you
> do this for a something that comes out of the immutable list, it'll be a
> disaster.
My point is that there is some shared memory by two different Grobs. This can
potentially lead to problems and very surprising behavior. Given that there's no
measurable performance impact, I remain opposed to this change.
Sign in to reply to this message.
On 2020/04/14 20:07:17, hahnjo wrote:
> On 2020/04/14 19:14:29, hanwenn wrote:
> > On 2020/04/14 10:22:01, hahnjo wrote:
> > > On 2020/04/14 09:39:18, hanwenn wrote:
> > > > it reads from the immutable_list_ if there is no override in the
> > > > mutable property list.
> > >
> > > Ack, that's also what the two names suggested. The code in Grob's copy
> > > constructor does a copy of mutable_property_alist_. As far as I understand
> it
> > > contains those elements that have been changed for the Grob? So I'm
thinking
> > > about the following situation (not real code, just conceptually):
> > > Grob g1;
> > > g1.set_property("key", "value");
> > > Grob g2(g1);
> > > g2.set_property("key", "value2");
> > >
> > > set_property will change mutable_property_alist_, and with this change
both
> > > Grobs will share some of it. So I can't help, but this looks like the
> > > g1.get_property("key") will probably return "value2" at the end, no?
> >
> > The code now calls ly_alist_copy(), which constructs a new alist with the
same
> > keys and values,
> > so your scenario will continue to work correctly.
> >
> > A deep copy protects against something like
> >
> > Grob g1;
> > g1.set_property("key", scm_cons(1,2));
> > Grob g2(g1);
> > SCM v = g2.get_property("key");
> > scm_set_cdr_x(v, 3)
> >
> > but this protection only works if the set_property was called beforehand. If
> you
> > do this for a something that comes out of the immutable list, it'll be a
> > disaster.
>
> My point is that there is some shared memory by two different Grobs. This can
> potentially lead to problems and very surprising behavior. Given that there's
no
> measurable performance impact, I remain opposed to this change.
My point is that all Grobs already share memory, but you are right that if there
were no performance upside, it seems an unnecessary risk to take.
I did some better structured measurements, with interleaved runs on MSDM:
$ python f.py out.txt
[55.57, 56.29, 55.43, 56.31, 55.44, 55.89, 55.21, 56.14]
1st
avg 55.4125
med 55.435
stddev 0.149
2nd
avg 56.1575
med 56.215
stddev 0.194
med diff 1.407053 %:
This is consistent with the profile data I have. There I see:
1.58 2.49 0.13 115613 0.00 0.00
ly_deep_copy(scm_unused_struct*)
(1.58% of runtime is this function.)
16394155
ly_deep_copy(scm_unused_struct*) [79]
0.00 0.00 40/115613
Accidental_engraver::update_local_key_signature(scm_unused_struct*) [422]
0.00 0.00 123/115613
set_context_property_on_children(Context*, scm_unused_struct*,
scm_unused_struct*) [425]
0.13 0.00 115450/115613 Grob::Grob(Grob const&) [81]
[79] 1.6 0.13 0.00 115613+16394155 ly_deep_copy(scm_unused_struct*)
[79]
16394155
ly_deep_copy(scm_unused_struct*) [79]
ie. virtually all non-recursive calls come from Grob::Grob.
Sign in to reply to this message.
description
Sign in to reply to this message.
On 2020/04/15 22:23:44, hanwenn wrote: > description now I remember why the deep copy was there. I've updated the description.
Sign in to reply to this message.
On 2020/04/15 22:15:04, hanwenn wrote:
> On 2020/04/14 20:07:17, hahnjo wrote:
> > On 2020/04/14 19:14:29, hanwenn wrote:
> > > On 2020/04/14 10:22:01, hahnjo wrote:
> > > > On 2020/04/14 09:39:18, hanwenn wrote:
> > > > > it reads from the immutable_list_ if there is no override in the
> > > > > mutable property list.
> > > >
> > > > Ack, that's also what the two names suggested. The code in Grob's copy
> > > > constructor does a copy of mutable_property_alist_. As far as I
understand
> > it
> > > > contains those elements that have been changed for the Grob? So I'm
> thinking
> > > > about the following situation (not real code, just conceptually):
> > > > Grob g1;
> > > > g1.set_property("key", "value");
> > > > Grob g2(g1);
> > > > g2.set_property("key", "value2");
> > > >
> > > > set_property will change mutable_property_alist_, and with this change
> both
> > > > Grobs will share some of it. So I can't help, but this looks like the
> > > > g1.get_property("key") will probably return "value2" at the end, no?
> > >
> > > The code now calls ly_alist_copy(), which constructs a new alist with the
> same
> > > keys and values,
> > > so your scenario will continue to work correctly.
> > >
> > > A deep copy protects against something like
> > >
> > > Grob g1;
> > > g1.set_property("key", scm_cons(1,2));
> > > Grob g2(g1);
> > > SCM v = g2.get_property("key");
> > > scm_set_cdr_x(v, 3)
> > >
> > > but this protection only works if the set_property was called beforehand.
If
> > you
> > > do this for a something that comes out of the immutable list, it'll be a
> > > disaster.
> >
> > My point is that there is some shared memory by two different Grobs. This
can
> > potentially lead to problems and very surprising behavior. Given that
there's
> no
> > measurable performance impact, I remain opposed to this change.
>
> My point is that all Grobs already share memory, but you are right that if
there
>
> were no performance upside, it seems an unnecessary risk to take.
>
> I did some better structured measurements, with interleaved runs on MSDM:
>
> $ python f.py out.txt
> [55.57, 56.29, 55.43, 56.31, 55.44, 55.89, 55.21, 56.14]
> 1st
> avg 55.4125
> med 55.435
> stddev 0.149
> 2nd
> avg 56.1575
> med 56.215
> stddev 0.194
> med diff 1.407053 %:
A bit of explanation which number is which version would have helped. But I
think I can confirm the improvement, on my system from 41.7s to 40.3s; if you
think that there's no drawback from omitting the deep copy, I'm fine with this
patch.
Sign in to reply to this message.
commit a456a5946c21cb63c64640a758e7faf829d98fa2 Author: Han-Wen Nienhuys <hanwen@lilypond.org> Date: Mon Apr 13 20:57:51 2020 +0200 Copy alist instead of deep copy on Grob clone
Sign in to reply to this message.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
