Issue 5368: Reduce allocations in Grob dimension caching

https://sourceforge.net/p/testlilyissues/issues/5368/

Reduce allocations in Grob dimension caching
Add Optional<T> offering some of the features of C++17 std::optional.

For those who are not familiar with std::optional yet, the most useful fact to know is that you assign directly to it like a value, but you read from it with pointer syntax.  I didn't invent it, but go ahead and blame me for using it, if you feel the urge.

I profiled input/regression/rest-dot-position.ly with callgrind, collecting data during Book::process, and found that these changes reduce cycles attributed to malloc and free to about 90% of what they were.  They reduce overall cycles attributed to Book::process to 99% of what they were.

I don't know how the use of malloc and free scales in larger scores.

[dak, 2018-07-05 12:20:27]

Overall, I consider the problem you are trying to address here real: allocation
of the relevant values seems like completely overblown and it does appear that
the allocation/indirection is mainly being used in lieu of a flag.

The "boring" way for that would be just to actually add the flag in question.

Can you line out other use cases here that would warrant the complexity of
dragging in a mechanism like this?

In its current version, it does not work satisfiably with types involving
non-trivial construction/destruction.  That makes it reek of a single-use class
and then it seems hard to justify all the expense over just using explicit
addition of a flag and removal of the indirection.

So what additional uses would you consider this useful for?

The actual objective of not actually allocating memory for the caches here is
valid, and the resulting assembly code should likely be similar to what gets
likely produced by this patch.

I'd like to see some rationale for the amount of semi-general-purpose tooling to
get there, and more current or future uses of it may go a long way towards that.

https://codereview.appspot.com/359770043/diff/1/flower/include/optional.hh
File flower/include/optional.hh (right):

https://codereview.appspot.com/359770043/diff/1/flower/include/optional.hh#ne...
flower/include/optional.hh:30: // type at all times, even when it presents
itself as empty.
The way against that would be to have
char [sizeof (T)] value_space_;
and instantiate and destroy it with placement new syntax, right?

You are currently replacing optional Real values where construction/deletion is
not really relevant.  Should we try anticipating other uses?

https://codereview.appspot.com/359770043/diff/1/flower/include/optional.hh#ne...
flower/include/optional.hh:40: typedef const T Optional::*bool_type;
I don't think we should be dragging an idiom like that into a single
class/template like this.

In particular when it comes with additional baggage like the comparison operator
business in order to actually work as intended.

[Dan Eble, 2018-07-05 21:32:25]

On 2018/07/05 12:20:27, dak wrote:
> I'd like to see some rationale for the amount of semi-general-purpose tooling
to
> get there, and more current or future uses of it may go a long way towards
that.

The rationale is that std::optional is fit for this situation and if LilyPond
were built with C++17 I would simply have used it.  The interface of this
Optional is a subset of std::optional, so when the project leaders determine
that it is reasonable to require C++17 to build LilyPond, discarding this
Optional should be straightforward.

> flower/include/optional.hh:30: // type at all times, even when it presents
> itself as empty.
> The way against that would be to have
> char [sizeof (T)] value_space_;
> and instantiate and destroy it with placement new syntax, right?

Yes, though I haven't studied any existing implementations.  There might be
concerns related to alignment which either require features of newer C++ or
implementation-defined behavior (unions come to mind).  I'm sure you can imagine
my reluctance to try to reproduce that feature of std::optional without a unit
testing framework or routine uses in the LilyPond code.  If there were a current
use case and we could be reasonably sure that implementation errors would not go
undiscovered, I wouldn't be opposed to looking into the GNU implementation of
std::optional to see what could be borrowed; but I'm not very interested in
spending that time strictly in anticipation of other uses.  I have no passion to
work on Optional for its own sake; it's just that "new Real" caught my attention
and I couldn't let it stand.

>
https://codereview.appspot.com/359770043/diff/1/flower/include/optional.hh#ne...
> flower/include/optional.hh:40: typedef const T Optional::*bool_type;
> I don't think we should be dragging an idiom like that into a single
> class/template like this.
> 
> In particular when it comes with additional baggage like the comparison
operator
> business in order to actually work as intended.

This could be dealt with by throwing out the implicit conversion to bool and
implementing has_value() instead.  It would still be a subset of the interface
of std::optional.  Example:

    if (dim_cache_[a].offset_.has_value ())
      return *dim_cache_[a].offset_;

[dak, 2018-07-06 09:12:32]

On 2018/07/05 21:32:25, Dan Eble wrote:
> On 2018/07/05 12:20:27, dak wrote:
> > I'd like to see some rationale for the amount of semi-general-purpose
tooling
> to
> > get there, and more current or future uses of it may go a long way towards
> that.
> 
> The rationale is that std::optional is fit for this situation and if LilyPond
> were built with C++17 I would simply have used it.

Any C++17 lookalike package is _not_ "simply using it" but a maintenance sink of
itself.  And a semi-lookalike always requires double-checking in what respects
it does and does not do the same job.  Write code once, debug it twice.  Not to
mention profile it twice.

Reimplementing and then maintaining C++17 features and eventually possibly
phasing out and replacing them by "the real thing" in 4 years or so is not the
same as "simply using them".

> The interface of this
> Optional is a subset of std::optional, so when the project leaders determine
> that it is reasonable to require C++17 to build LilyPond, discarding this
> Optional should be straightforward.

Let me remind you that your project on "use std;" was hampered by us not having
been able to rid ourselves yet of std-vector.hh.

So I'd really like to see more of a possible use case than dimension caching
which could possibly just be done using a sentinel value (+nan.0 maybe?) or an
explicit flag.  How many lines are we actually talking about here?

The actual code using the dimension cache is just in grob.cc, and your patch
results in a line count change of +10, -17 here.  The way it looks, you could
likely even keep all of the grob.cc changes (the const_cast looks icky though)
and just wrap your interface into dimension-cache without some semi-specialized
variant of std::optional if there is no obvious other use for it.  It can then
still at some future point of time conveniently be replaced with std::optional
once we consider that available.  And in the mean time we would not have to
think about a semi-implemented specialized substitute template class and all the
hassles that might bring along.

So do you see any other obvious candidates for std::optional we might want to
address using the generic mechanism of a template class, or would we be better
off leaving the cost of generalization for a future time when we can just use
the generalized solution that somebody else has to bother with keeping in
working order?

[Dan Eble, 2018-07-06 20:21:50]

On 2018/07/06 09:12:32, dak wrote:
> On 2018/07/05 21:32:25, Dan Eble wrote:
> > On 2018/07/05 12:20:27, dak wrote:
> > The rationale is that std::optional is fit for this situation and if
LilyPond
> > were built with C++17 I would simply have used it.
> 
> Any C++17 lookalike package is _not_ "simply using it" 

not what I said

> Let me remind you that your project on "use std;" was hampered by us not
having
> been able to rid ourselves yet of std-vector.hh.

I recall that isnan was the final problem before I left off trying.

> off leaving the cost of generalization for a future time when we can just use
> the generalized solution that somebody else has to bother with keeping in
> working order?

Expect an update.

[haberg-1_telia.com, 2018-07-06 22:02:54]

> On 6 Jul 2018, at 11:12, dak@gnu.org wrote:
> 
> On 2018/07/05 21:32:25, Dan Eble wrote:
> 
>> The rationale is that std::optional is fit for this situation and if
> LilyPond
>> were built with C++17 I would simply have used it.
> 
> Any C++17 lookalike package is _not_ "simply using it" but a maintenance
> sink of itself.  And a semi-lookalike always requires double-checking in
> what respects it does and does not do the same job.  Write code once,
> debug it twice.  Not to mention profile it twice.
> 
> Reimplementing and then maintaining C++17 features and eventually
> possibly phasing out and replacing them by "the real thing" in 4 years
> or so is not the same as "simply using them".

Use __cplusplus. Later C++ versions also have a 'using' version of typedef,
which I found useful for transforming code. 

For example, if you already have introduced your own Optional type:
#if __cplusplus >= 201703L
using Optional = std::optional;
#else
class Optional ...
#endif
and test if it compiles both with and without C++17.

One can do it the other way around, too:
#if __cplusplus < 201703L
namespace std {
  using optional = Optional;
}
#endif
and use std::optional, or mix them until all Optional have been removed.

[Dan Eble, 2018-07-06 22:13:17]

On Jul 6, 2018, at 18:02, Hans Åberg <haberg-1@telia.com> wrote:
One can do it the other way around, too:
#if __cplusplus < 201703L
namespace std {
 using optional = Optional;
}
#endif

Ugh.  That’s too pragmatic [even] for me.

I specifically avoided naming my class "optional" to avoid confusion with the
standard type--but this is strictly academic now, as I’ve already moved it into
Dimension_cache and reduced its interface.  I'll update the patch once the
regression tests have passed.

[Dan Eble, 2018-07-06 22:16:09]

Hide Optional in Dimension_cache and pare it down

[haberg-1_telia.com, 2018-07-06 22:19:29]

> On 7 Jul 2018, at 00:13, nine.fierce.ballads@gmail.com wrote:
> 
> On Jul 6, 2018, at 18:02, Hans Åberg <haberg-1@telia.com> wrote:
> One can do it the other way around, too:
> #if __cplusplus < 201703L
> namespace std {
> using optional = Optional;
> }
> #endif
> 
> Ugh.  That’s too pragmatic [even] for me.

That came up on the Bison list in the context of the typed C++ parser, as a
workaround for not having C++17 std::variant.

> I specifically avoided naming my class "optional" to avoid confusion
> with the standard type--but this is strictly academic now, as I’ve
> already moved it into Dimension_cache and reduced its interface.

The technique is useful for transforming code, though.

[Dan Eble, 2018-07-06 22:26:35]

On 2018/07/06 22:19:29, haberg-1_telia.com wrote:
> The technique is useful for transforming code, though.

Into what? :)

[dak, 2018-07-07 07:35:11]

Hans Åberg <haberg-1@telia.com> writes:

>> On 6 Jul 2018, at 11:12, dak@gnu.org wrote:
>> 
>> On 2018/07/05 21:32:25, Dan Eble wrote:
>> 
>>> The rationale is that std::optional is fit for this situation and if
>>> LilyPond were built with C++17 I would simply have used it.
>> 
>> Any C++17 lookalike package is _not_ "simply using it" but a maintenance
>> sink of itself.  And a semi-lookalike always requires double-checking in
>> what respects it does and does not do the same job.  Write code once,
>> debug it twice.  Not to mention profile it twice.
>> 
>> Reimplementing and then maintaining C++17 features and eventually
>> possibly phasing out and replacing them by "the real thing" in 4 years
>> or so is not the same as "simply using them".
>
> Use __cplusplus. Later C++ versions also have a 'using' version of
> typedef, which I found useful for transforming code.

This is totally not addressing the objection at all.

Sort of (excuse the role assignments) mother saying "it's not nice to
break your brother's toys" and the father supporting her by saying "it's
less effort using a hammer".

-- 
David Kastrup

[dak, 2018-07-07 11:06:11]

LGTM

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc
File lily/grob.cc (left):

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc#oldcode325
lily/grob.cc:325: *dim_cache_[a].offset_ += y;
This is more an "as you like it" suggestion: operator priority of * as opposed
to [] . -> is not always clear to everybody, so *(dim_cache_[a].offset_) += y;
might be a consideration.  On the other hand, it's ugly.  And it's not like
pointer-to-members operators .* and ->* which inexplicably have priority _less_
than * making for "in theory, we can now write even more compound expressions
without using parens except that nobody will understand them except the
compiler, so we have to add more sanity parens than we otherwise would need to".

At any rate, I digress, sorry.  C++ language design is a topic getting me into
heavy breathing.  This was just to say "consider parenthising".  It's ok to
consider and reject it.  In this case it makes the expressions less similar, but
they actually _are_ dissimilar, the former working on the value container
(filling it and marking it filled) and giving a container expression as result,
the latter working on the container content and giving a double expression as
result.

This similarity is part of the std::optional design and of course it's not
really the job of parens to change that.

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc
File lily/grob.cc (right):

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc#newcode322
lily/grob.cc:322: if (!dim_cache_[a].offset_.has_value ())
Actually, conversion to bool and direct assignment make for a bit of an ugly
combination in the std::optional design: if I read the docs correctly, after

double x = dim_cache_[a].offset_ = 0.0;
  
x would likely contain 1.0.  Or, if explicit conversion intervenes, at least

bool x = dim_cache_[a].offset_ = 0.0;

would result in a true value.

So particularly since we are using offset_ here in numerical context, I am more
amenable to your use of has_value rather than bool conversion here.  It's too
easy to forget the * operator and we do test doubles for being zero by just
using them as a boolean in several places.

So independent of the whole business of having a separate optional class or not,
for this particular use I consider the explicit use of has_value that you do
here an improvement.

https://codereview.appspot.com/359770043/diff/20001/lily/include/dimension-ca...
File lily/include/dimension-cache.hh (right):

https://codereview.appspot.com/359770043/diff/20001/lily/include/dimension-ca...
lily/include/dimension-cache.hh:62: Optional<Real> offset_;
Here we come to, uh, another learning experience.  The myopic view of reviewers.
 Our conversation could likely have benefited from the following exchange:

    I see no point in a templated class for something that is used only once.

    Ah, but it is used for Real as well as Interval, independent uses though
both within the dimension-cache framework.

    Oh.  I see.  I have overlooked this.

Now I'm fine with pulling this limited-use templated class into the dimension
cache definition for now where we know that it matches the requirements of the
particular uses here.  And I'd suggest just sticking with it for now.  I think
it's a good solution even though the review process was tarnished by me not
realizing what we were actually talking about.

https://codereview.appspot.com/359770043/diff/20001/lily/include/dimension-ca...
lily/include/dimension-cache.hh:72: void clear ()
Is there some incentive for "clear" over "reset"?  If it conceptually matches
what "reset" for the elements does (does it?), it may make sense matching the
naming as well.

https://codereview.appspot.com/359770043/diff/20001/lily/include/grob.hh
File lily/include/grob.hh (right):

https://codereview.appspot.com/359770043/diff/20001/lily/include/grob.hh#newc...
lily/include/grob.hh:44: mutable Dimension_cache dim_cache_[NO_AXES];
Not particularly happy about this kind of tame-the-const approach, but it's
already in paper-score code from 2010 so it's not exactly new.

[Dan Eble, 2018-07-07 14:48:27]

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc
File lily/grob.cc (left):

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc#oldcode325
lily/grob.cc:325: *dim_cache_[a].offset_ += y;
On 2018/07/07 11:06:11, dak wrote:
> This is more an "as you like it" suggestion: operator priority of * as opposed
> to [] . -> is not always clear to everybody, so *(dim_cache_[a].offset_) += y;
> might be a consideration.  On the other hand, it's ugly.  And it's not like

I would have no problem adding parentheses, but how do you rate the beauty of
using value_or() here as in Patch Set 1?

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc
File lily/grob.cc (right):

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc#newcode322
lily/grob.cc:322: if (!dim_cache_[a].offset_.has_value ())
On 2018/07/07 11:06:11, dak wrote:

> double x = dim_cache_[a].offset_ = 0.0;
> x would likely contain 1.0.

No, declaring the conversion operator "explicit" causes the compiler to reject
that.  In a situation where you actually wanted to convert like that, you would
need to cast.  Explicit conversion would also protect you from

    double x = dim_cache_[a].offset_ + 1.0;

> bool x = dim_cache_[a].offset_ = 0.0;
> would result in a true value.

Well, even bool x = 0.0 would cause me to question the state of mind of the
programmer.

I agree that bool x = optional_something is a danger, but I don't think you
would be likely to type that unless you were trying to use optional<bool>. That
is one good reason to use something other than optional<bool> when you want a
tri-valued variable.

https://codereview.appspot.com/359770043/diff/20001/lily/include/dimension-ca...
File lily/include/dimension-cache.hh (right):

https://codereview.appspot.com/359770043/diff/20001/lily/include/dimension-ca...
lily/include/dimension-cache.hh:62: Optional<Real> offset_;
On 2018/07/07 11:06:11, dak wrote:
> Here we come to, uh, another learning experience.  The myopic view of
reviewers.
>  Our conversation could likely have benefited from the following exchange:

Well, I'm sorry for my part of the misunderstanding too.  I'm sure I read "used
only once" as "used only in the dimension cache."

https://codereview.appspot.com/359770043/diff/20001/lily/include/dimension-ca...
lily/include/dimension-cache.hh:72: void clear ()
On 2018/07/07 11:06:11, dak wrote:
> Is there some incentive for "clear" over "reset"?  If it conceptually matches
> what "reset" for the elements does (does it?), it may make sense matching the
> naming as well.

It was already called clear () and I was trying not to change more than I had
to.

In this case I don't really like either of those names because they are used in
the standard library to make an object as if it had just been initialized, but
this leaves parent_ untouched.  It smells like something is not quite right in
the design here, but I'm trying very hard not to branch out into any further
refactoring in this area.

https://codereview.appspot.com/359770043/diff/20001/lily/include/grob.hh
File lily/include/grob.hh (right):

https://codereview.appspot.com/359770043/diff/20001/lily/include/grob.hh#newc...
lily/include/grob.hh:44: mutable Dimension_cache dim_cache_[NO_AXES];
On 2018/07/07 11:06:11, dak wrote:
> Not particularly happy about this kind of tame-the-const approach

This is a matter of habitual correctness, though in this case you won't see the
problems that omitting "mutable" could cause because no instance of any kind of
Grob is ever truly const (I partly assume).

In general, if no instance variables are declared mutable, the compiler may
place a const instance in unwritable memory, where your internal implementation
using const_cast has no hope of working as intended.  For this reason, members
that are changed in const methods should be declared mutable.

Not having to use const_cast to modify those members blessed with "mutable" then
justifies approaching remaining appearances of const_cast with suspicion.

[dak, 2018-07-07 15:13:19]

Still LGTM.

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc
File lily/grob.cc (left):

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc#oldcode325
lily/grob.cc:325: *dim_cache_[a].offset_ += y;
On 2018/07/07 14:48:27, Dan Eble wrote:
> On 2018/07/07 11:06:11, dak wrote:
> > This is more an "as you like it" suggestion: operator priority of * as
opposed
> > to [] . -> is not always clear to everybody, so *(dim_cache_[a].offset_) +=
y;
> > might be a consideration.  On the other hand, it's ugly.  And it's not like
> 
> I would have no problem adding parentheses, but how do you rate the beauty of
> using value_or() here as in Patch Set 1?

Reads clumsy to me, though it's basically the same as our robust_scm2* .  Let's
just leave this one alone for now.

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc
File lily/grob.cc (right):

https://codereview.appspot.com/359770043/diff/20001/lily/grob.cc#newcode322
lily/grob.cc:322: if (!dim_cache_[a].offset_.has_value ())
On 2018/07/07 14:48:27, Dan Eble wrote:

> Well, even bool x = 0.0 would cause me to question the state of mind of the
> programmer.

lily/bar-check-iterator.cc:      if (where->main_part_)

Pretty much the same.  We are not using all that many inexact numbers in a
similar manner I guess but numerics used as conditions are not that infrequent
although it's admittedly more integers (like size ()) used in that manner.

https://codereview.appspot.com/359770043/diff/20001/lily/include/dimension-ca...
File lily/include/dimension-cache.hh (right):

https://codereview.appspot.com/359770043/diff/20001/lily/include/dimension-ca...
lily/include/dimension-cache.hh:72: void clear ()
On 2018/07/07 14:48:27, Dan Eble wrote:

> It was already called clear () and I was trying not to change more than I had
> to.
> 
> In this case I don't really like either of those names

So just not wanting to condone either and not touching anything.

Ok with me.