[std-proposals] Compressing std::optional

[v***@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

[v***@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.

Post by v***@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
template <typename T, typename S = default_optional_initialization_storage
class optional {
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();
}
...
std::tuple<S, aligned_storage_t<sizeof(T)>> _data;
};
default_optional_initialization_storage would comply with the interface
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;
};
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();
}
}
};
- 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

['Jeffrey Yasskin' via ISO C++ Standard - Future Proposals]

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.

Post by v***@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
template <typename T, typename S = default_optional_initialization_storage>
class optional {
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();
}
...
std::tuple<S, aligned_storage_t<sizeof(T)>> _data;
};
default_optional_initialization_storage would comply with the interface for
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;
};
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();
}
}
};
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
--
---
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
Visit this group at
http://groups.google.com/a/isocpp.org/group/std-proposals/.

[v***@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.

Post by 'Jeffrey Yasskin' via ISO C++ Standard - Future Proposals
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.

Post by v***@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

Post by v***@gmail.com
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

Post by v***@gmail.com
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

Post by v***@gmail.com
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,

Post by v***@gmail.com
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

Post by v***@gmail.com
template <typename T, typename S =

default_optional_initialization_storage>

Post by v***@gmail.com
class optional {
optional(std::nullopt_t)
{

std::get<0>(_data).set_initialized(reinterpret_cast<T*>(&std::get<1>(_data)),

Post by v***@gmail.com
false);
}
optional(const T&)
{

std::get<0>(_data).set_initialized(reinterpret_cast<T*>(&std::get<1>(_data)),

Post by v***@gmail.com
true);
}
...
bool is_initialized() const
{
return std::get<0>(_data).is_initialized();
}
...
std::tuple<S, aligned_storage_t<sizeof(T)>> _data;
};
default_optional_initialization_storage would comply with the interface

for

Post by v***@gmail.com
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;
};
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();
}
}
};
It is by no means an exaustive implementation and I'm sure there's lots

of

Post by v***@gmail.com
nitpicking to be done over details/naming/etc. I just want to get a

sense

Post by v***@gmail.com
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

Post by v***@gmail.com
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

Post by v***@gmail.com
API for expressing such a sentinel value would be valuable (something

like

Post by v***@gmail.com
optional<double, sentinel<double, nan("")>>)
This is purely a customization point to apply domain-specific knowledge

to

Post by v***@gmail.com
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

Post by v***@gmail.com
storage lives external to the optional<> itself. Passing through some

kind

Post by v***@gmail.com
of ctx in all optional APIs?
It has been suggested by some that this no longer represents the CS

concept

Post by v***@gmail.com
of an optional monad and should be a distinct type. I'm not sure I

really

Post by v***@gmail.com
see why (purity of mapping C++ to theoretical CS aside).
Thanks for reading,
Vitali
--
---
You received this message because you are subscribed to the Google

Groups

Post by v***@gmail.com
"ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send

an

Post by v***@gmail.com
Visit this group at
http://groups.google.com/a/isocpp.org/group/std-proposals/.

[Nevin Liber]

On 24 June 2015 at 17:58, 'Jeffrey Yasskin' via ISO C++ Standard - Future

Post by 'Jeffrey Yasskin' via ISO C++ Standard - Future Proposals
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:***@eviloverlord.com> [phone]

[Fabio Fracassi]

Post by Nevin Liber
On 24 June 2015 at 17:58, 'Jeffrey Yasskin' via ISO C++ Standard -
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.

Post by Nevin Liber
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.

Post by Nevin Liber
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.

Post by Nevin Liber
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

[j***@gmail.com]

Post by Nevin Liber
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

[v***@gmail.com]

Post by j***@gmail.com

Post by Nevin Liber
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

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.

[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)

Post by Nevin Liber
On 24 June 2015 at 17:58, 'Jeffrey Yasskin' via ISO C++ Standard - Future

Post by 'Jeffrey Yasskin' via ISO C++ Standard - Future Proposals
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?
--
--
---
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
Visit this group at
http://groups.google.com/a/isocpp.org/group/std-proposals/.

[Nevin Liber]

Post by Tony V E
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.
--
Nevin ":-)" Liber <mailto:***@eviloverlord.com> [phone]

[v***@gmail.com]

Somehow my reply e-mail had been swallowed.

Post by Nevin Liber

Post by Tony V E
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.
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.
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

Post by Nevin Liber
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.

Post by Nevin Liber
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).

Post by Nevin Liber
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?

Post by Nevin Liber
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.
--

Post by Nevin Liber
691-1404

[Nevin Liber]

Post by v***@gmail.com
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...

Post by v***@gmail.com
And those are the simpler things. We haven't even gotten to the more

Post by Nevin Liber
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.

Post by v***@gmail.com

Post by Nevin Liber
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.

Post by v***@gmail.com
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.

Post by v***@gmail.com
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...
--
Nevin ":-)" Liber <mailto:***@eviloverlord.com> [phone]

[v***@gmail.com]

Post by Nevin Liber

Post by v***@gmail.com
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

Post by Nevin Liber

Post by v***@gmail.com

Post by Nevin Liber
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 :).

Post by Nevin Liber

Post by v***@gmail.com

Post by Nevin Liber
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.

Post by Nevin Liber
Perhaps after I’ve done steps 2 & 3 we can see if the process has been

Post by v***@gmail.com
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.

Post by Nevin Liber

Post by v***@gmail.com
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...
--
691-1404

[Nevin Liber]

Post by v***@gmail.com

Post by Nevin Liber

Post by v***@gmail.com
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.

Post by v***@gmail.com
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.

Post by v***@gmail.com
The disengaged state is smaller than every state of T, in both homogeneous

Post by Nevin Liber
(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.

Post by v***@gmail.com
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.
--
Nevin ":-)" Liber <mailto:***@eviloverlord.com> [phone]

[Sam Kellett]

Post by Nevin Liber
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.)

[v***@gmail.com]

Post by Nevin Liber

Post by v***@gmail.com

Post by Nevin Liber

Post by v***@gmail.com
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.

Post by v***@gmail.com
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.

Post by v***@gmail.com
The disengaged state is smaller than every state of T, in both

Post by Nevin Liber
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

Post by Nevin Liber
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
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.

Post by Nevin Liber
I have nothing against coming to Kona. I would certainly be interested in

Post by v***@gmail.com
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.
--
691-1404

[v***@gmail.com]

Post by v***@gmail.com

Post by Nevin Liber

Post by v***@gmail.com

Post by Nevin Liber

Post by v***@gmail.com
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.

Post by v***@gmail.com
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.

Post by v***@gmail.com
The disengaged state is smaller than every state of T, in both

Post by Nevin Liber
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
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
assert (!(optional<float, nan_seninel>(f) == f))) // fails because lhs is
disengaged.

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.

If NaN is a valid value, then you either need to find a different sentinel

Post by v***@gmail.com
or realize that an optimized policy won't work for you.
assert(!(f == optional<float>(f))); // fails

Post by Nevin Liber
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
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.

Post by Nevin Liber
I have nothing against coming to Kona. I would certainly be interested

Post by v***@gmail.com
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.
--

[Tony V E]

Post by Nevin Liber
However, ordered comparisons are different. Using string("Geronimo") as
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 &

Post by Nevin Liber
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.

[Tony V E]

Post by Nevin Liber
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

['Jeffrey Yasskin' via ISO C++ Standard - Future Proposals]

Post by Nevin Liber
On 24 June 2015 at 17:58, 'Jeffrey Yasskin' via ISO C++ Standard - Future

Post by 'Jeffrey Yasskin' via ISO C++ Standard - Future Proposals
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.

Post by Nevin Liber
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.

Post by Nevin Liber
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.

[Andrzej Krzemieński]

Post by v***@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
template <typename T, typename S = default_optional_initialization_storage
class optional {
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();
}
...
std::tuple<S, aligned_storage_t<sizeof(T)>> _data;
};
default_optional_initialization_storage would comply with the interface
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;
};
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();
}
}
};
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]

Post by v***@gmail.com
The main criticism of this proposal was that it affects the optional's
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]

On Fri, Jun 26, 2015 at 4:20 PM, Christopher Jefferson <

Post by Christopher Jefferson

Post by v***@gmail.com
The main criticism of this proposal was that it affects the optional's
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

In what cases *can* you compress then?

[Christopher Jefferson]

Post by Tony V E
On Fri, Jun 26, 2015 at 4:20 PM, Christopher Jefferson

Post by Christopher Jefferson

Post by v***@gmail.com
The main criticism of this proposal was that it affects the optional's
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

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

[Tony V E]

Post by Christopher Jefferson

Post by Tony V E

Post by Christopher Jefferson
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]

Post by Tony V E

Post by Christopher Jefferson

Post by Tony V E

Post by Christopher Jefferson
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).

Post by Tony V E
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.

Post by Tony V E
The user can still "tell" the optimization exists. Or, more likely, trip

over in some rare case.

Post by Tony V E
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.

Post by Tony V E
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.

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!

Post by Tony V E
--
---
You received this message because you are subscribed to the Google Groups

"ISO C++ Standard - Future Proposals" group.

Post by Tony V E
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at

http://groups.google.com/a/isocpp.org/group/std-proposals/.

[David Krauss]

Post by Christopher Jefferson
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 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.

[v***@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.

Post by Tony V E
On Fri, Jun 26, 2015 at 4:20 PM, Christopher Jefferson <

Post by Christopher Jefferson
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 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.
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.

[David Krauss]

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!

[Vitali Lovich]

Post by David Krauss

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?

template< typename float_t >
struct never_quiet_nan {
float_t value = 0;
operator float_t & () { return value; }
operator float_t const & () const { return value; }
};
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?

Post by David Krauss

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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[David Krauss]

Post by Vitali Lovich
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.

[Tony V E]

Post by v***@gmail.com
The main criticism of this proposal was that it affects the optional's
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

[Vicente J. Botet Escriba]

Post by Andrzej Krzemieński

Post by v***@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
template <typename T, typename S = default_optional_initialization_storage
class optional {
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();
}
...
std::tuple<S, aligned_storage_t<sizeof(T)>> _data;
};
default_optional_initialization_storage would comply with the interface
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;
};
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();
}
}
};
The main criticism of this proposal was that it affects the optional's

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.

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?

Post by Vicente J. Botet Escriba
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