Compressing std::optional

[vlo...@gmail.com]

Hi,

I'd like to bring up this topic again.  I know Andrzej brought it up a couple of years ago for tr2 but I think I have a different take.
First, I'd like to motivate the discussion with the limitations of the current approach.

• For small types optional can double the size of storage
• Overhead can add up when stored in arrays (& most of it due to padding if the sizeof(T) > 1).
• Cannot be used as a drop-in in a memory-mapped structure.  In these scenarios it's not uncommon to have a sentinel value.
• Cannot be used in as a drop-in in existing code that uses a sentinel (i.e type-safety)
• Lots of overhead when a struct contains lots of optionals.  For example, protobuf uses bit-packing for this.

The main limitation, at least as I see it, of the Andrzej's traits implementation is that it cannot be customized per-instance of optional.  This is probably fine for user-defined types but makes this optimization not possible for built-in types.  It's not uncommon to have only certain instances of built-in types have invalid bit-patterns (e.g. NaN for double, maximum value for size_t as reported by std::string).

To that end, my proposal to accomplish something like this would require adding a secondary template parameter that defines the storage of the initialization state.  Here is a straw-man skeleton example of what the std::optional class interface might look like. constexpr omitted for simplicity but I don't see anything preventing it & optional_storage is the hypothetical :

template <typename T, typename S = default_optional_initialization_storage>
class optional {
public:
    optional(std::nullopt_t)
    {
        std::get<0>(_data).set_initialized(reinterpret_cast<T*>(&std::get<1>(_data)), false);
    }

    optional(const T&)
    {
        std::get<0>(_data).set_initialized(reinterpret_cast<T*>(&std::get<1>(_data)), true);
    }
    ...
    bool is_initialized() const
    {
        return std::get<0>(_data).is_initialized();
    }
    ...
private:
    std::tuple<S, aligned_storage_t<sizeof(T)>> _data;
};

default_optional_initialization_storage would comply with the interface for optional_initialization_storage & look something like:


struct default_optional_initialization_storage {
    template <typename T>
    bool is_initialized(T*) const
    {
        return _initialized;
    }

    template <typename T>
    void set_initialized(T*, bool initialized)
    {
        _initialized = initialized;
    }

    bool _initialized = false;
};

An example for hiding the state as via NaN for double:

struct nan_optional_storage {
    bool is_initialized(double* value) const
    {
        return !std::isnan(*value)
    }

    void set_initialized(double* value, bool initialized)
    {
        if (!initialized) {
            *value = std::numeric_limits<double>::quite_NaN();
        }
    }
};


Some of my thoughts on this sample code:

• It is by no means an exaustive implementation and I'm sure there's lots of nitpicking to be done over details/naming/etc.  I just want to get a sense of does something like this even make sense.
  
• This is purely a mechanism through which optional can be optimized with domain-specific knowledge.  There is no optimization suggested for built-in types (e.g. not even pointer types would optimize the nullptr case by default).
• The sentinel-value use-case would probably be important enough that a simple API for expressing such a sentinel value would be valuable (something like optional<double, sentinel<double, nan("")>>)
• This is purely a customization point to apply domain-specific knowledge to optimize optional.  There is no optimization available by default.
• The careful reader will note that the bit-packing case has not been addressed.  I am not quite certain how to actually achieve this since the storage lives external to the optional<> itself.  Passing through some kind of ctx in all optional APIs?
• It has been suggested by some that this no longer represents the CS concept of an optional monad and should be a distinct type.  I'm not sure I really see why (purity of mapping C++ to theoretical CS aside).

Thanks for reading,
Vitali

[vlo...@gmail.com]

Forgot to mention.  The reader may ask that this should just be left to users to implement their own class.  std::optional is non-trivial to get the interface & implementation right (moreso I think than even something like vector).
A customization point solves an optimization problem that many may have in a much simpler way without having to try to implement the entire optional interface.

[Jeffrey Yasskin]

I'd be happy to see a paper fleshing this out. I don't think anyone
was opposed to the idea, but it would have slowed down the initial
optional<> proposal if it had been included. Now is a great time to
try to add the feature.

> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposal...@isocpp.org.
> To post to this group, send email to std-pr...@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.

[vlo...@gmail.com]

I was hoping that it was purely just to get a solid foundation in place.  I'll try to write-up a proposal & post it to the ML for feedback.

[Nevin Liber]

On 24 June 2015 at 17:58, 'Jeffrey Yasskin' via ISO C++ Standard - Future Proposals <std-pr...@isocpp.org> wrote:

I'd be happy to see a paper fleshing this out. I don't think anyone
was opposed to the idea, but it would have slowed down the initial
optional<> proposal if it had been included.

Ahem.  I was strongly against it when it came up on this list two years ago, and I'm still strongly against it now.  This could be slightly tapered by proposing a separate type instead of shoehorning it into optional.  If it were to be shoehorned into optional, I'd be strongly against optional going into C++17, and that would make me sad.

Either way, I believe that it would take a significant amount of committee time to discuss.  You have to revisit every issue that optional and variant touched, including the issues with the empty state of variant, because now you may not be able to no throw construct the disengaged state.  All this for a type that is so important yet hasn't been implemented by the people claiming it is so important.

It isn't fair to encourage someone to write up a paper and fly to Kona if we aren't going to spend enough time to give useful feedback.  Do you really think we'll have that light a load in Kona?

--

 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  (847) 691-1404

[Fabio Fracassi]

On 25.06.2015 03:47, Nevin Liber wrote:

On 24 June 2015 at 17:58, 'Jeffrey Yasskin' via ISO C++ Standard - Future Proposals <std-pr...@isocpp.org> wrote:

I'd be happy to see a paper fleshing this out. I don't think anyone
was opposed to the idea, but it would have slowed down the initial
optional<> proposal if it had been included.

Ahem.  I was strongly against it when it came up on this list two years ago, and I'm still strongly against it now.  This could be slightly tapered by proposing a separate type instead of shoehorning it into optional.

I think a separate type should be part of the design discussion, but I for one would prefer this to be integrated into optional because I see this as a semantically identical optimization.

If it were to be shoehorned into optional, I'd be strongly against optional going into C++17, and that would make me sad.

I on the other hand would be rather sad if we couldn't use optional to improve code like string::find without introducing overhead.

Either way, I believe that it would take a significant amount of committee time to discuss.  You have to revisit every issue that optional and variant touched,

I don't think this is a fair characterization. There are some interactions and probably subtleties that need to be disscussed, but hardly every interaction. It is mostly an implementation detail.

including the issues with the empty state of variant, because now you may not be able to no throw construct the disengaged state.

I don't see how this follows, we could very well specify this to be no-throw, without inhibiting any of the motivating use-cases.

Best regards

Fabio

[Tony V E]

Are you only against it because it might delay optional, or for technical/design reasons?

(avoiding delay is a valid reason to me, just wondering if there were other objections)

--

[Nevin Liber]

On 25 June 2015 at 09:31, Tony V E <tvan...@gmail.com> wrote:

Are you only against it because it might delay optional, or for technical/design reasons?

Both.

If optional significantly changes, then any user experience we have so far gets thrown out the window. I'm fine if that happens because of the user experience, but I'm not fine with that for the purposes of invention.  Especially if optional is a vocabulary type being targeted for C++17.

As for technical considerations:

One of the mental models we used for designing optional was that it is a T with an extra state.  This customization breaks that model.

We would have to revisit every single line of optional to see if it still holds true.

For purposes of this, lets assume I want an optional<string> where string("Geronimo") is the unengaged state.

Let us start with the simplest constructors:

  constexpr optional() noexcept;

  constexpr optional(nullopt_t) noexcept;

They are obviously no longer noexecept(true).  Do we make that conditionally noexcept?  If so, how?  This customization will be as complicated as allocators (such as a noexcept_on_nullopt_t_construction_or_assignment member type derived from bool_type).

How about assignment?  Take

    optional<T>& operator=(nullopt_t) noexcept;

Besides the noexcept issue, what state is the optional left in when an exception is thrown?  Beats me.

And those are the simpler things.  We haven't even gotten to the more controversial stuff, like heterogeneous comparisons and ordering.

And there may language issues.  As proposed:

    template <typename T>
    void set_initialized(T*, bool initialized)

The T* being passed may be a pointer to uninitialized storage and not a T.  Is that legal?

LEWG likes to "time box" discussions (which I strongly disagree with, because it basically means we aren't giving the author enough feedback to make useful progress, making it poor use of both the author's time and the committee's time.  If we don't have the time to adequately discuss things, why are we soliciting for more stuff?).  Based on how much committee time has been and will be spent on optional and variant, do you really think we can get through this kind of proposal in only an hour or two?  I don't.

Now, a significant portion of the complexity goes away if it is a separate type, because a separate type can just store a T instead of a block of storage it has to manage, the ordering can be identical to T, etc.

[vlo...@gmail.com]

Somehow my reply e-mail had been swallowed.

On Thursday, June 25, 2015 at 8:35:23 AM UTC-7, Nevin ":-)" Liber wrote:

On 25 June 2015 at 09:31, Tony V E <tvan...@gmail.com> wrote:

Are you only against it because it might delay optional, or for technical/design reasons?

Both.

If optional significantly changes, then any user experience we have so far gets thrown out the window. I'm fine if that happens because of the user experience, but I'm not fine with that for the purposes of invention.  Especially if optional is a vocabulary type being targeted for C++17.

As for technical considerations:

One of the mental models we used for designing optional was that it is a T with an extra state.  This customization breaks that model.

We would have to revisit every single line of optional to see if it still holds true.

For purposes of this, lets assume I want an optional<string> where string("Geronimo") is the unengaged state.

Let us start with the simplest constructors:

  constexpr optional() noexcept;

  constexpr optional(nullopt_t) noexcept;

They are obviously no longer noexecept(true).  Do we make that conditionally noexcept?  If so, how?  This customization will be as complicated as allocators (such as a noexcept_on_nullopt_t_construction_or_assignment member type derived from bool_type).

How about assignment?  Take

    optional<T>& operator=(nullopt_t) noexcept;

Besides the noexcept issue, what state is the optional left in when an exception is thrown?  Beats me.

I’m not as familiar with the issues so I’m probably misunderstanding your concern.  Is it that every custom specialization of optional must be able to no-throw construct the disengaged state?  I think you raise a good point with noexcept.  I would probably solve that in v1 by just mandating that setting the disengaged state must be a nothrow operation & throwing will invoke std::terminate (just as it does now).  If a throwable version of this becomes desirable, the stricter semantics could probably be weakend and maintain backward compatability; starting with maintaining existing noexcept semantics seems like the right first step.

And those are the simpler things.  We haven't even gotten to the more controversial stuff, like heterogeneous comparisons and ordering.

Can you clarify why you think those would be affected?  I'm sure I'm missing something obvious.  It seems to me like whatever comparison/ordering is defined currently would work equally since it has to take into account the disengaged state which is now accessible via a function call instead of assuming it's in a separate boolean.

And there may language issues.  As proposed:

    template <typename T>
    void set_initialized(T*, bool initialized)

The T* being passed may be a pointer to uninitialized storage and not a T.  Is that legal?

That was just a strawman.  I'm still mulling over how it would actually be implemented & it's definitely.  It would be good to know if this is illegal; at first glance it doesn't seem so since it doesn't seem uncommon to have a pointer to uninitialized storage (e.g. std::vector after a reserve).
 

LEWG likes to "time box" discussions (which I strongly disagree with, because it basically means we aren't giving the author enough feedback to make useful progress, making it poor use of both the author's time and the committee's time.  If we don't have the time to adequately discuss things, why are we soliciting for more stuff?).  Based on how much committee time has been and will be spent on optional and variant, do you really think we can get through this kind of proposal in only an hour or two?  I don't.

I’m just following the process as outlined in https://isocpp.org/std/submit-a-proposal
I’ve floated the idea.
The next step I was planning on proposing a first draft of a paper for more feedback of what a concrete proposal might look like.

Perhaps after I’ve done steps 2 & 3 we can see if the process has been completed in time for submitting it for Kona & whether the proposal is as complicated as you fear?
I certainly appreciate your feedback.  I hadn't thought about noexcept & I'll make sure to incorporate it in the proposal.  Are there any issues you forsee?
 

Now, a significant portion of the complexity goes away if it is a separate type, because a separate type can just store a T instead of a block of storage it has to manage, the ordering can be identical to T, etc.

I like Fabio's phrasing; this is a semantically identical optimization.  Introducing a new type for an implementation detail doesn't seem, at least at first glance, to be a desirable behaviour.  In any case, I will certainly raise your concerns in the draft as a point
of discussion.

[Nevin Liber]

On 25 June 2015 at 12:58, <vlo...@gmail.com> wrote:

I’m not as familiar with the issues so I’m probably misunderstanding your concern.  Is it that every custom specialization of optional must be able to no-throw construct the disengaged state?

No, but you weren't proposing to specialize optional.  You were proposing to add a second policy-like template parameter to optional.  Those are two very different things.

If you are specializing it, I really have to question why it has to be spelled o-p-t-i-o-n-a-l, as it really isn't substitutable in generic constructs (which is the main reason to have them spelled the same way).  Shades of vector<bool> all over again...

 

And those are the simpler things.  We haven't even gotten to the more controversial stuff, like heterogeneous comparisons and ordering.

Can you clarify why you think those would be affected?  I'm sure I'm missing something obvious.  It seems to me like whatever comparison/ordering is defined currently would work equally since it has to take into account the disengaged state which is now accessible via a function call instead of assuming it's in a separate boolean.

The disengaged state is smaller than every state of T, in both homogeneous (optional<T> vs optional<T>) and heterogeneous (optional<T> vs T) comparisons.  Do you intend for that to hold, in which case comparing two engaged optionals now behaves differently than comparing the values they hold.

 

And there may language issues.  As proposed:

    template <typename T>
    void set_initialized(T*, bool initialized)

The T* being passed may be a pointer to uninitialized storage and not a T.  Is that legal?

That was just a strawman.  I'm still mulling over how it would actually be implemented & it's definitely.  It would be good to know if this is illegal; at first glance it doesn't seem so since it doesn't seem uncommon to have a pointer to uninitialized storage (e.g. std::vector after a reserve).

A pointer, such as char* or void*, to uninitialized storage is okay; I'm not sure about a pointer of type T* to uninitialized storage.

 

 Perhaps after I’ve done steps 2 & 3 we can see if the process has been completed in time for submitting it for Kona & whether the proposal is as complicated as you fear?

Are you planning on coming to Kona to present it?  If not, my advice is to get someone who was involved with the discussions around optional to do a deep dive into your proposal and champion it.  Jeffrey and Tony are two good candidates, if they are going and you can convince them.

 

I certainly appreciate your feedback.  I hadn't thought about noexcept & I'll make sure to incorporate it in the proposal.  Are there any issues you forsee?

I really don't have the time to look at it in detail.  I've already spent (some say wasted) way too much of my life on optional and variant as it is...

[vlo...@gmail.com]

On Thursday, June 25, 2015 at 11:54:07 AM UTC-7, Nevin ":-)" Liber wrote:

On 25 June 2015 at 12:58, <vlo...@gmail.com> wrote:

I’m not as familiar with the issues so I’m probably misunderstanding your concern.  Is it that every custom specialization of optional must be able to no-throw construct the disengaged state?

No, but you weren't proposing to specialize optional.  You were proposing to add a second policy-like template parameter to optional.  Those are two very different things.

If you are specializing it, I really have to question why it has to be spelled o-p-t-i-o-n-a-l, as it really isn't substitutable in generic constructs (which is the main reason to have them spelled the same way).  Shades of vector<bool> all over again...

Well to get an optimized policy, the user would have to specialize it with their user-defined policy object.  Is that not the right terminology?  In any case what I meant to say is that does every possible policy need to meet these criteria?  I agree the answer is yes where it would otherwise cause complexity in the optional API itself (which seems to be the case with the noexcept cases you pointed out).

And those are the simpler things.  We haven't even gotten to the more controversial stuff, like heterogeneous comparisons and ordering.

Can you clarify why you think those would be affected?  I'm sure I'm missing something obvious.  It seems to me like whatever comparison/ordering is defined currently would work equally since it has to take into account the disengaged state which is now accessible via a function call instead of assuming it's in a separate boolean.

The disengaged state is smaller than every state of T, in both homogeneous (optional<T> vs optional<T>) and heterogeneous (optional<T> vs T) comparisons.  Do you intend for that to hold, in which case comparing two engaged optionals now behaves differently than comparing the values they hold.

I'm probably being a little thick.  Can you clarify with the following implementation of equality where you would see a problem with the implementation?

bool operator==(const optional<T, P1>& lhs, const optional<T, P2>& rhs)
{
    if (!lhs.is_initialized() ^ rhs.is_initialized()) {
        return false;
    }

    if (lhs.is_initialized() && rhs.is_initialized()) {
        return *lhs == *rhs;
    }

    return true;
}

I'm not sure I see a scenario in which it matters what policy lhs or rhs have but you clearly have a lot more expertise working with optional & variant :).

 

And there may language issues.  As proposed:

    template <typename T>
    void set_initialized(T*, bool initialized)

The T* being passed may be a pointer to uninitialized storage and not a T.  Is that legal?

That was just a strawman.  I'm still mulling over how it would actually be implemented & it's definitely.  It would be good to know if this is illegal; at first glance it doesn't seem so since it doesn't seem uncommon to have a pointer to uninitialized storage (e.g. std::vector after a reserve).

A pointer, such as char* or void*, to uninitialized storage is okay; I'm not sure about a pointer of type T* to uninitialized storage.

I could be misreading it but libc++ seems to use a pointer of type T* to store the internal storage, not char*/void*.  It's always possible that libc++ has a bug here but I can't think of any good reason it would be disallowed.  Also, I'm pretty sure that placement new can be given a pointer to an uninitialized memory location, although that's of course mostly a language feature so it could have special-casing.
 

 Perhaps after I’ve done steps 2 & 3 we can see if the process has been completed in time for submitting it for Kona & whether the proposal is as complicated as you fear?

Are you planning on coming to Kona to present it?  If not, my advice is to get someone who was involved with the discussions around optional to do a deep dive into your proposal and champion it.  Jeffrey and Tony are two good candidates, if they are going and you can convince them.

I have nothing against coming to Kona.  I would certainly be interested in presenting it but I can also work to get champions too.  I haven't even presented a draft of a proposal so perhaps discussing Kona is a bit premature?
For all I know there are intractable problems that come up when I flush it out fully.
 

[Nevin Liber]

On 25 June 2015 at 14:22, <vlo...@gmail.com> wrote:

On Thursday, June 25, 2015 at 11:54:07 AM UTC-7, Nevin ":-)" Liber wrote:

On 25 June 2015 at 12:58, <vlo...@gmail.com> wrote:

I’m not as familiar with the issues so I’m probably misunderstanding your concern.  Is it that every custom specialization of optional must be able to no-throw construct the disengaged state?

No, but you weren't proposing to specialize optional.  You were proposing to add a second policy-like template parameter to optional.  Those are two very different things.

If you are specializing it, I really have to question why it has to be spelled o-p-t-i-o-n-a-l, as it really isn't substitutable in generic constructs (which is the main reason to have them spelled the same way).  Shades of vector<bool> all over again...

Well to get an optimized policy, the user would have to specialize it with their user-defined policy object.  Is that not the right terminology?

vector<bool> is a specialization of vector, and has a different interface than vector.  That is very different than, say, providing an allocator (which is basically a policy) to a vector.

 

  In any case what I meant to say is that does every possible policy need to meet these criteria? 

It is in the interface for optional, so either it does or you change the interface.  You get to explore the design space.

 

The disengaged state is smaller than every state of T, in both homogeneous (optional<T> vs optional<T>) and heterogeneous (optional<T> vs T) comparisons.  Do you intend for that to hold, in which case comparing two engaged optionals now behaves differently than comparing the values they hold.

I'm probably being a little thick.  Can you clarify with the following implementation of equality where you would see a problem with the implementation?

bool operator==(const optional<T, P1>& lhs, const optional<T, P2>& rhs)
{
    if (!lhs.is_initialized() ^ rhs.is_initialized()) {
        return false;
    }

    if (lhs.is_initialized() && rhs.is_initialized()) {
        return *lhs == *rhs;
    }

    return true;
}

Say you use NaN for your disengaged value.

float f = std::numeric_limits<float>::quiet_NaN();

assert(!(f==f));

assert(!(optional<float>(f) == optional<float>(f))); // fails

assert(!(optional<float>(f) == f)); // fails

assert(!(f == optional<float>(f))); // fails

Now, I'm perfectly willing (although others on the committee are not) to say that non-regular types such as float are insane, and equality comparisons aren't a problem for regular types.

However, ordered comparisons are different.  Using string("Geronimo") as the disengaged value:

string s = "Geronimo";

string t = "Geronim";

assert(t < s);

assert(optional<string>(t) < optional<string>(s)); // fails

assert(optional<string>(t) < s); // fails

assert(t < optional<string>(s)); // fails

Is that the desired behavior?  As part of your proposal, you explore the design space, pick something, and then LEWG will debate it if they really want the feature.

 

I have nothing against coming to Kona.  I would certainly be interested in presenting it but I can also work to get champions too.  I haven't even presented a draft of a proposal so perhaps discussing Kona is a bit premature?
For all I know there are intractable problems that come up when I flush it out fully.

My general advice is that people attend a meeting or two before making a proposal, so that can see what they are in for.  Roughly speaking, it's like defending a dissertation in front of a panel of people who don't really care if you graduate.  You are the domain expert fielding tough questions from other (domain and non-domain) experts, as well as from people like me.

I do realize that it sometimes takes a proposal to get an employer to send someone to a meeting, in which case I advise not picking something too ambitious.  IMO, this is a very ambitious proposal.  Of course, other committee members may feel otherwise and be willing to put in the preparatory effort so that it gets a fair chance.  We are all volunteers and speak only for ourselves or those we represent, as no one speaks for the committee.

[Sam Kellett]

My general advice is that people attend a meeting or two before making a proposal, so that can see what they are in for.  Roughly speaking, it's like defending a dissertation in front of a panel of people who don't really care if you graduate.  You are the domain expert fielding tough questions from other (domain and non-domain) experts, as well as from people like me.

I do realize that it sometimes takes a proposal to get an employer to send someone to a meeting, in which case I advise not picking something too ambitious.  IMO, this is a very ambitious proposal.  Of course, other committee members may feel otherwise and be willing to put in the preparatory effort so that it gets a fair chance.  We are all volunteers and speak only for ourselves or those we represent, as no one speaks for the committee.

As a neutral and with all due respect: perhaps you shouldn't be the one who provides tips and advice on submitting a proposal? Given how strongly opposed you to this proposal I'm slightly worried that your advice may be misconstrued as a slightly underhanded way to scare away a feature you're not a fan of instead of letting it live or die by it's own right.

(Important: not saying this is what you're doing at all, I just wanted to point out that it could easily be interpreted this way.)

[jgot...@gmail.com]

On Thursday, June 25, 2015 at 4:09:16 AM UTC-4, Fabio Fracassi wrote:

On 25.06.2015 03:47, Nevin Liber wrote:

Either way, I believe that it would take a significant amount of committee time to discuss.  You have to revisit every issue that optional and variant touched,

I don't think this is a fair characterization. There are some interactions and probably subtleties that need to be disscussed, but hardly every interaction. It is mostly an implementation detail.

  One major difference between your proposed optional<T> and the current version is the constructors and assignment operators that take a T value.  Currently, if I write code like

optional<size_t> x;
// ...
x = function_returning_a_size_t();

I can assume after the assignment that x contains a value so I don't have to check it.  If we use your version of optional that uses a sentinel value (for instance std::string::npos) and the function I called can return that value, I can no longer make that assumption.  This is a subtle difference that can easily cause code to fail.

Joe Gottman

[vlo...@gmail.com]

On Thursday, June 25, 2015 at 12:59:58 PM UTC-7, Nevin ":-)" Liber wrote:

On 25 June 2015 at 14:22, <vlo...@gmail.com> wrote:

On Thursday, June 25, 2015 at 11:54:07 AM UTC-7, Nevin ":-)" Liber wrote:

On 25 June 2015 at 12:58, <vlo...@gmail.com> wrote:

I’m not as familiar with the issues so I’m probably misunderstanding your concern.  Is it that every custom specialization of optional must be able to no-throw construct the disengaged state?

No, but you weren't proposing to specialize optional.  You were proposing to add a second policy-like template parameter to optional.  Those are two very different things.

If you are specializing it, I really have to question why it has to be spelled o-p-t-i-o-n-a-l, as it really isn't substitutable in generic constructs (which is the main reason to have them spelled the same way).  Shades of vector<bool> all over again...

Well to get an optimized policy, the user would have to specialize it with their user-defined policy object.  Is that not the right terminology?

vector<bool> is a specialization of vector, and has a different interface than vector.  That is very different than, say, providing an allocator (which is basically a policy) to a vector.

 

  In any case what I meant to say is that does every possible policy need to meet these criteria? 

It is in the interface for optional, so either it does or you change the interface.  You get to explore the design space.

 

The disengaged state is smaller than every state of T, in both homogeneous (optional<T> vs optional<T>) and heterogeneous (optional<T> vs T) comparisons.  Do you intend for that to hold, in which case comparing two engaged optionals now behaves differently than comparing the values they hold.

I'm probably being a little thick.  Can you clarify with the following implementation of equality where you would see a problem with the implementation?

bool operator==(const optional<T, P1>& lhs, const optional<T, P2>& rhs)
{
    if (!lhs.is_initialized() ^ rhs.is_initialized()) {
        return false;
    }

    if (lhs.is_initialized() && rhs.is_initialized()) {
        return *lhs == *rhs;
    }

    return true;
}

Say you use NaN for your disengaged value.

float f = std::numeric_limits<float>::quiet_NaN();

assert(!(f==f));

assert(!(optional<float>(f) == optional<float>(f))); // fails

This is actually still true.  I'm assuming you meant if you include a policy where it's folded into the nan:
assert (!(optional<float, nan_sentinel>(f) == optional<float, nan_sentinel>(f))); // fails because both are disengaged as per the policy
assert (!(optional<float, nan_sentinel>(f) == optional<float>(f))); // fails because lhs is disengaged.

assert(!(optional<float>(f) == f)); // fails

This still passes.  However:
assert (!(optional<float, nan_seninel>(f) == f))) // fails because lhs is disengaged.

If NaN is a valid value, then you either need to find a different sentinel or realize that an optimized policy won't work for you.

assert(!(f == optional<float>(f))); // fails

Now, I'm perfectly willing (although others on the committee are not) to say that non-regular types such as float are insane, and equality comparisons aren't a problem for regular types.

However, ordered comparisons are different.  Using string("Geronimo") as the disengaged value:

string s = "Geronimo";

string t = "Geronim";

assert(t < s);

assert(optional<string>(t) < optional<string>(s)); // fails

assert(optional<string>(t) < s); // fails

assert(t < optional<string>(s)); // fails

Is that the desired behavior?  As part of your proposal, you explore the design space, pick something, and then LEWG will debate it if they really want the feature.

Yes it is.  The sentinel value is defined to be the disengaged state & cannot be represented as a valid value.  If the above assertions are unexpected then the policy
is incorrectly implemented.
 

[vlo...@gmail.com]

Correct.  That's why optional<size_t> continues to behave the same way.  For example, for the std::string API you could do:

using optional_find = std::optional<size_t, optional_find_policy>;
optional_find x = std::string{"abcd"}.find("efg");
assert (!x);

which is much more elegant I think.

I've prototyped the code forked from Andrzej's branch here: https://github.com/vlovich/Optional

I've updated test_optional to show what it might look like.

[vlo...@gmail.com]

Oh.  I misread this.  So actually in the current implementation I prototyped (https://github.com/vlovich/Optional), this would still hold.
The problem is that disengaged is false & so disengaged != "engaged".  However, for consistency this should actually be true.  I need to fix the comparison operators
to understand comparison against a sentinel.

[Jeffrey Yasskin]

On Wed, Jun 24, 2015 at 6:47 PM, Nevin Liber <ne...@eviloverlord.com> wrote:
> On 24 June 2015 at 17:58, 'Jeffrey Yasskin' via ISO C++ Standard - Future
> Proposals <std-pr...@isocpp.org> wrote:
>>
>> I'd be happy to see a paper fleshing this out. I don't think anyone
>> was opposed to the idea, but it would have slowed down the initial
>> optional<> proposal if it had been included.
>
>
> Ahem. I was strongly against it when it came up on this list two years ago,
> and I'm still strongly against it now. This could be slightly tapered by
> proposing a separate type instead of shoehorning it into optional. If it
> were to be shoehorned into optional, I'd be strongly against optional going
> into C++17, and that would make me sad.

Ah, here are the old threads:
https://groups.google.com/a/isocpp.org/d/msg/std-proposals/cXneqUj-5oo/jszGOPPXK1cJ
and https://groups.google.com/a/isocpp.org/d/msg/std-proposals/WBkQCiKXEZc/nLE4jQGYEfgJ.

> Either way, I believe that it would take a significant amount of committee
> time to discuss. You have to revisit every issue that optional and variant
> touched, including the issues with the empty state of variant, because now
> you may not be able to no throw construct the disengaged state.

It depends on the decisions the paper makes, and how well it justifies
them. Several folks have now suggested ways around the disengaged
constructor throwing, but there are clearly other issues to work
through.

> It isn't fair to encourage someone to write up a paper and fly to Kona if we
> aren't going to spend enough time to give useful feedback. Do you really
> think we'll have that light a load in Kona?

It's worth getting the paper just so there's something concrete to
talk about. We can run it around the LEWG mailing list to see if
there's enough interest to ask someone to come to Kona to present it,
or we can talk it over in Kona without the author present, as long as
someone's enthusiastic enough to explain it to everyone.

[Tony V E]

On Thu, Jun 25, 2015 at 2:53 PM, Nevin Liber <ne...@eviloverlord.com> wrote:

On 25 June 2015 at 12:58, <vlo...@gmail.com> wrote:

 

Are you planning on coming to Kona to present it?  If not, my advice is to get someone who was involved with the discussions around optional to do a deep dive into your proposal and champion it.  Jeffrey and Tony are two good candidates, if they are going and you can convince them.

Nothing beats presenting a paper yourself!

I'm hoping to go, if I can manage funding (click here to donate?:-).

If I go, I'd gladly champion it - whether I agree or not with the particular proposal, I've spent a lot of time thinking about optional, so I think I could present it.  (And present it fairly. I tend to see all sides of a discussion, to the point of not being able to decide myself.)

For this proposal in particular:

- it does bother the "old C coder" inside me that sometimes optional won't be as efficient as it could be if I could tell it what the empty value was

- I don't want to delay optional (at least not for this reason :-)

- I don't think this need delay optional, but every paper does take committee time, so it does have a cost regardless

[Tony V E]

However, ordered comparisons are different.  Using string("Geronimo") as the disengaged value:

string s = "Geronimo";

string t = "Geronim";

assert(t < s);

assert(optional<string>(t) < optional<string>(s)); // fails

assert(optional<string>(t) < s); // fails

assert(t < optional<string>(s)); // fails

Is that the desired behavior?  As part of your proposal, you explore the design space, pick something, and then LEWG will debate it if they really want the feature.

Yes it is.  The sentinel value is defined to be the disengaged state & cannot be represented as a valid value.  If the above assertions are unexpected then the policy
is incorrectly implemented.

A more realistic example might be "<insert name here>".

You just assume no one has that name, and the rest of your code treats it like it treats other optionals.

Yes that is different behaviour than string, and different behaviour than the default optional<string>, but it is also a different type, so that's OK.
And I can see the value in it.

Devil may be in the details, however.

[Andrzej Krzemieński]

The main criticism of this proposal was that it affects the optional's semantics:

optional<double, nan_optional_storage> od {2.3};
double d = compute_val();

assert (od); // contains value
*od = d;
assert (od); // contains value?


The second assertion always holds in normal optional. In the "optimized" version, it depends on the value of d.



 

[Christopher Jefferson]

On 26 June 2015 at 21:14, Andrzej Krzemieński <akrz...@gmail.com> wrote:

> The main criticism of this proposal was that it affects the optional's
> semantics:
>
> optional<double, nan_optional_storage> od {2.3};
> double d = compute_val();
>
> assert (od); // contains value
> *od = d;
> assert (od); // contains value?
>
> The second assertion always holds in normal optional. In the "optimized"
> version, it depends on the value of d.

I have used an 'optimised optional' of the type suggested in this
paper for years. At some point I decided to forbid this case -- a user
should be completely unable to tell any space optimisation is being
performed (except the object is smaller obviously). That does mean you
can't compress types such as int or double.

Chris

[Tony V E]

In what cases *can* you compress then?

[Tony V E]

The main criticism of this proposal was that it affects the optional's semantics:

optional<double, nan_optional_storage> od {2.3};
double d = compute_val();

assert (od); // contains value
*od = d;
assert (od); // contains value?


The second assertion always holds in normal optional. In the "optimized" version, it depends on the value of d.



I see that as both a criticism and a feature.

Feature:
I suspect it is often the behaviour requested.
ie compute_val() is an old (maybe 3rd party) function documented to return NaN when there is no valid value.

Now newer code wants to use a more formal optional<>.  Either it does

if (is_nan(d))

   od = {};

else

   od = d;

or it just does

od = d;

and it magically works.

Criticism:

vector<bool>

I'm not sure it rises to the level of vector<bool>, but that is the spectre.

Tony

[Christopher Jefferson]

Any type where at least one bit pattern isn't used in a valid object.

Personally, I mainly compress containers (std::vector, std::list,
std::map, etc.).

I know on any system I care about malloc is never going to return
(void*)1, so any object which contains a pointer can assign that value
to a pointer to represent disengaged.

Chris

[Tony V E]

>> I have used an 'optimised optional' of the type suggested in this
>> paper for years. At some point I decided to forbid this case -- a user
>> should be completely unable to tell any space optimisation is being
>> performed (except the object is smaller obviously). That does mean you
>> can't compress types such as int or double.
>>
>> Chris
>
>
> In what cases *can* you compress then?

Any type where at least one bit pattern isn't used in a valid object.

Personally, I mainly compress containers (std::vector, std::list,
std::map, etc.).

I know on any system I care about malloc is never going to return
(void*)1, so any object which contains a pointer can assign that value
to a pointer to represent disengaged.

Chris

but how do you know that in my usage of optional<void*>, I also use (void*)1 for special meaning (besides the use inside optional).

ie I can still have:

void * some_function(); // returns (void*)1 in some case

optional<void *> ov = some_function();

assert( ! ov.empty() );

ie you still need to know the problem domain.  Same as using NaN or 0 or whatever.

The user can still "tell" the optimization exists.  Or, more likely, trip over in some rare case.

I think it is valuable to hear that you have experience with a compressed optional, but I wonder if the eventual answer is that you would abandon it completely.

And/or although it may be reasonable to assume your code base need not worry about (void *)1, the standard has a larger codebase to consider.

[Christopher Jefferson]

I certainly wouldn't compress optional<void*> for the reasons you outline, but within STD::vector, I might know more, such as promises about the alignment of memory, or knowledge of STD::allocator.

In the case of vector, in GCC there are 3 pointers start, end, capacity which satisfy start <= end <= capacity. I can therefore easily make a never occurring state by assigning start > end.

I am going to think more carefully about the nan-compression case given earlier. I would not put it in the standard, but I can see the benefit of letting users write it -- if they then assign a nan they are in trouble, but that is their own fault!

[David Krauss]

Any time the underlying type has unused states that can be inspected after destruction. For example, enumerations and standard-layout classes with constructors. The underlying type needs to cooperate.

Bit-patterns are tricky. Here’s an approach that might be valid — discuss:

struct small_fsm {

    char state;

    small_fsm() : state( 0 ) {}

};

void invalidate_representation( small_fsm * invalid_ptr )

    { * reinterpret_cast< char * >( invalid_ptr ) = 42; } // not a member access!

bool is_valid_representation( small_fsm const * questionable_ptr )

    { return * reinterpret_cast< char const * >( questionable_ptr ) != 42; }

I used a small_fsm * parameter instead of void * here so the mechanism can accommodate enumeration types. Using a member function would exclude enumerations and using a void * would prevent overloading non-member functions. (Enumerations don’t have constructors, but value-initialization sounds good enough.)

Anyway, the functions operating on potentially unconstructed objects can’t use member accesses and need to leverage the shaky POD lifetime rules.

The optimization is useful, but any proposal would need to set it on a good foundation. numeric_limits::quiet_NaN is not a good foundation. Some NaN could perhaps be, but only if the platform reserves it specifically to use by std::optional. This isn’t something the user can do.

Besides object lifetime issues, please, don’t let ever let specializations behave differently from the primary template. I’m not clear how that issue crept in, but this extension should be completely within the as-if rule, except for inspection of some traits class or ADL function. And adding a traits template parameter needs really good justification. Why shouldn’t the payload be encapsulated instead? (E.g., use std::optional< never_quiet_nan< double > >. The payload is not a complete double. Strong typedefs might come in handy here.)

On a related note, implementations should already be free to compress optional< polymorphic_class_type >, by nulling the vtable pointer. The user can’t do this, but the implementation can and probably should. Likewise for std::vector… there’s plenty of room inside the as-if rule for this optimization. The extension should only be about helping the user to work within the as-if rule too.

But, bear in mind that you’re already allowed to specialize std::optional for your own types, according to [namespace.std] §17.6.4.2.1. The niche could very well be filled by a third-party base class, say boost::basic_optional, containing ADL function calls like the above. Such a utility could well be more usable than one designed to fit within standard library conventions.

[vlo...@gmail.com]

Hey David, I really like the idea of a basic_optional a lot better & can provide a better foundation for doing something like compressing the optional state for many optionals into a bit-field (e.g. protobuf) which is one the problems left unsolved.
I also like the idea of encapsulating the sentinel'ness as you propose (e.g. std::optional<never_quiet_nan<double>>) instead of having a separate traits.  Can you elaborate a bit on how this could be accomplished?  Right now optional has a boolean
field.  My original design moved that boolean field into the policy/traits & used the empty base-class optimization to get rid of it when unnecessary.  In the std::optional<never_quiet_nan<double>> example, would never_quiet_nan have a static constexpr member
boolean that said "I understand how to read/write my state from the value"?  Or would there be an ADL traits class that parametrized this?

The std::vector & polymorphism cases I think are less compelling for as-if as I can't imagine a use-case where you would store either in optional.  std::vector has a natural empty state & using optional<vector<X>> seems more likely to be a poor design
than anything else.  Polymorphic classes tend to be prone to slicing when used as a value-type.  optional for enum classes (enums too?) would be possible if there were reflection so that you could query for an out-of-range value to use as a sentinel.
As you say, an implementation would be free to optimize these if it felt important under the as-if rule so there would be no need to specify it in the proposal.

I was hoping to get to writing up the proposal this weekend but it looks like probably it will end up next weekend.  If you have any more thoughts on the matter feel free to email me directly.

[David Krauss]

On 2015–06–28, at 3:47 AM, vlo...@gmail.com wrote:

Hey David, I really like the idea of a basic_optional a lot better & can provide a better foundation for doing something like compressing the optional state for many optionals into a bit-field (e.g. protobuf) which is one the problems left unsolved.
I also like the idea of encapsulating the sentinel'ness as you propose (e.g. std::optional<never_quiet_nan<double>>) instead of having a separate traits.  Can you elaborate a bit on how this could be accomplished?  Right now optional has a boolean
field.  My original design moved that boolean field into the policy/traits & used the empty base-class optimization to get rid of it when unnecessary.  In the std::optional<never_quiet_nan<double>> example, would never_quiet_nan have a static constexpr member
boolean that said "I understand how to read/write my state from the value"?  Or would there be an ADL traits class that parametrized this?

I’m thinking like this:

// Thin wrapper:

template< typename float_t >

struct never_quiet_nan {

    float_t value = 0;

    operator float_t & () { return value; }

    operator float_t const & () const { return value; }

};

// ADL object representation functions:

template< typename float_t >

void invalidate_representation( never_quiet_nan< float_t > * invalid_ptr )
    { * reinterpret_cast< float_t * >( invalid_ptr ) = std::numeric_limits< float_t >::quiet_NaN; }

template< typename float_t >

bool is_valid_representation( never_quiet_nan< float_t > const * questionable_ptr )
    { return std::isnan( * reinterpret_cast< float_t const * >( questionable_ptr ) ); }

The std::vector & polymorphism cases I think are less compelling for as-if as I can't imagine a use-case where you would store either in optional.  std::vector has a natural empty state & using optional<vector<X>> seems more likely to be a poor design
than anything else. 

One use-case of std::optional is for output parameters. Those are already an anti-pattern per se, but still I think a blanket statement that optional<vector> should never happen is too strong.

Under as-if, it’s a question of how many priorities a standard library can implement before they need to freeze their ABI.

Polymorphic classes tend to be prone to slicing when used as a value-type.  optional for enum classes (enums too?) would be possible if there were reflection so that you could query for an out-of-range value to use as a sentinel.

Just ask the user for invalidate_representation and is_valid_representation. Enumerations aren’t closed so reflection can’t really discover invalid values.

As you say, an implementation would be free to optimize these if it felt important under the as-if rule so there would be no need to specify it in the proposal.

I was hoping to get to writing up the proposal this weekend but it looks like probably it will end up next weekend.  If you have any more thoughts on the matter feel free to email me directly.

My hands are full… I’m procrastinating here already :P .

Good luck!

[Vicente J. Botet Escriba]

Le 26/06/15 22:14, Andrzej Krzemieński a écrit :

>
> W dniu środa, 24 czerwca 2015 18:55:50 UTC+2 użytkownik vlo...@gmail.com
> napisał:
>> Hi,
>>
>> I'd like to bring up this topic again. I know Andrzej brought it up a
>> couple of years ago for tr2 but I think I have a different take.
>> First, I'd like to motivate the discussion with the limitations of the
>> current approach.
>>

>> - For small types optional can double the size of storage
>> - Overhead can add up when stored in arrays (& most of it due to

>> padding if the sizeof(T) > 1).

>> - Cannot be used as a drop-in in a memory-mapped structure. In these

>> scenarios it's not uncommon to have a sentinel value.

>> - Cannot be used in as a drop-in in existing code that uses a sentinel
>> (i.e type-safety)
>> - Lots of overhead when a struct contains lots of optionals. For

Andrzej is right

*od = d;


is odd and can only be caught if operator* returns a proxy :( This proxy
could check for the value and throw an exception.


Clearly this is another possibly null type, with different space and
time constraints.

Vicente

[David Krauss]

This discussion should already be steered clear of that problem. Perhaps reply to a newer post?

[Vitali Lovich]

On Jun 28, 2015, at 7:38 AM, David Krauss <pot...@mac.com> wrote:

On 2015–06–28, at 3:47 AM, vlo...@gmail.com wrote:

Hey David, I really like the idea of a basic_optional a lot better & can provide a better foundation for doing something like compressing the optional state for many optionals into a bit-field (e.g. protobuf) which is one the problems left unsolved.
I also like the idea of encapsulating the sentinel'ness as you propose (e.g. std::optional<never_quiet_nan<double>>) instead of having a separate traits.  Can you elaborate a bit on how this could be accomplished?  Right now optional has a boolean
field.  My original design moved that boolean field into the policy/traits & used the empty base-class optimization to get rid of it when unnecessary.  In the std::optional<never_quiet_nan<double>> example, would never_quiet_nan have a static constexpr member
boolean that said "I understand how to read/write my state from the value"?  Or would there be an ADL traits class that parametrized this?

I’m thinking like this:

// Thin wrapper:

template< typename float_t >

struct never_quiet_nan {

    float_t value = 0;

    operator float_t & () { return value; }

    operator float_t const & () const { return value; }

};

// ADL object representation functions:

template< typename float_t >

void invalidate_representation( never_quiet_nan< float_t > * invalid_ptr )
    { * reinterpret_cast< float_t * >( invalid_ptr ) = std::numeric_limits< float_t >::quiet_NaN; }

template< typename float_t >

bool is_valid_representation( never_quiet_nan< float_t > const * questionable_ptr )
    { return std::isnan( * reinterpret_cast< float_t const * >( questionable_ptr ) ); }

Hmmm... And how would optional decide what state it needs to store?

The std::vector & polymorphism cases I think are less compelling for as-if as I can't imagine a use-case where you would store either in optional.  std::vector has a natural empty state & using optional<vector<X>> seems more likely to be a poor design
than anything else. 

One use-case of std::optional is for output parameters. Those are already an anti-pattern per se, but still I think a blanket statement that optional<vector> should never happen is too strong.

Under as-if, it’s a question of how many priorities a standard library can implement before they need to freeze their ABI.

Polymorphic classes tend to be prone to slicing when used as a value-type.  optional for enum classes (enums too?) would be possible if there were reflection so that you could query for an out-of-range value to use as a sentinel.

Just ask the user for invalidate_representation and is_valid_representation. Enumerations aren’t closed so reflection can’t really discover invalid values.

As you say, an implementation would be free to optimize these if it felt important under the as-if rule so there would be no need to specify it in the proposal.

I was hoping to get to writing up the proposal this weekend but it looks like probably it will end up next weekend.  If you have any more thoughts on the matter feel free to email me directly.

My hands are full… I’m procrastinating here already :P .

Good luck!

--

---
You received this message because you are subscribed to a topic in the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this topic, visit https://groups.google.com/a/isocpp.org/d/topic/std-proposals/46J1onhWJ-s/unsubscribe.
To unsubscribe from this group and all its topics, send an email to std-proposal...@isocpp.org.

[David Krauss]

On 2015–06–29, at 12:19 AM, Vitali Lovich <vlo...@gmail.com> wrote:

Hmmm... And how would optional decide what state it needs to store?

Initialize the disengaged state with invalidate_representation. Construct the object to engage. Query engagement with is_valid_representation.