Compressing Optional

[Andrzej Krzemieński]

I can think of two ways to optimize the storage size for tr2::optional for certain T's -- at the cost of potentially adding run-time overhead when checking for the disengaged state:

1. For optional<optional<T>>, use one bool-size value for storing two engaged/disengaged flag

2. For certain T's where not all bit-patterns represent a meaningful value some special value can be used to indicate a disengaged optional and no additional disengaged flag is needed.

Re 1.
optional<optional<T>> can be specialized to the following representation:

class optional
{
  uint_of_size<bool> engaged_;
  raw_storage_of_size<T> value_;
};

Assuming that bool is never stored in 1-bit, and that its 'true' value is stored in the least significant bit. We can use the second least significant bit to store the information about the engaged state of the outer optional. "1" indicates a disengaged state. You check it with the following expression:

explicit optional<optional<T>>::operator bool() const {
  return !(engaged_ & 0x10);
}

The value access retuning a type-punned myself:

optional<T> const& optional<optional<T>>::operator*() const {
  return reinterpret_cast<optional<T> const&>(*this);
}

In the inner optional we check for engaged state without the bit-mask.

Well, type-punning doesn't work with constexpr functions, but I wonder if the same effect cannot be achieved by deriving optional<optional<T>> from optional<T>.

This could be generalized to optional<optional<optional<T>>>

Re 2.

Second optimization works for types where there is a value (or bit-pattern not representing any value) that is guaranteed never to make sense:

a pointer with address 0x1

or a bool with bit pattern 0x10.

For such types optional doesn't need to use a separate flag, but use the special value to indicate a disengaged state. In order to allow programmers to easily customize optional for their types, another interface could be standardized: a type trait:

template <typename T>
struct optional_optimized_disengaged_state_traits
{
  constexpr static bool is_optimized = false;
  constexpr static raw_storage_of_size<T> const& value();
};

If you want, you can specialize this trait to enable the optimization:

template <typename T>
struct optional_optimized_disengaged_state_traits<T*>
{
  constexpr static bool is_optimized = true;
  constexpr static raw_storage_of_size<T> const& value() {
    return cast( (T*)1 );
  }
};

template <>
struct optional_optimized_disengaged_state_traits<bool>
{
  constexpr static bool is_optimized = true;
  constexpr static raw_storage_of_size<bool> const& value() {
    return cast( 0x10 );
  }
};

Now, checking for disengaged state can be implemented by memcmp:

explicit optional<T>::operator bool() const {
  return memcmp (&value_, &optional_optimized_disengaged_state_traits<T>::value(), sizeof(value_));
}

Again, I am not sure if this could be made to work with constexpr functions. If not it is worth considering sacrificing the constexpr requirements in order to enable such optimizations.

Regards,
&rzej

[Nevin Liber]

On 2 October 2013 13:57, Andrzej Krzemieński <akrz...@gmail.com> wrote:

I can think of two ways to optimize the storage size for tr2::optional for certain T's -- at the cost of potentially adding run-time overhead when checking for the disengaged state:

Is this anything more than an implementation detail (and therefore not on topic for this forum)? 

For such types optional doesn't need to use a separate flag, but use the special value to indicate a disengaged state. In order to allow programmers to easily customize optional for their types, another interface could be standardized: a type trait:

I have yet to see *any* benchmarks of real world programs where adding such complexity would be a net benefit to anyone, let alone most users.

If people really wish to go down this route, I can't stop them, other than to say that in all likelihood I will argue and vote strongly against such a proposal.

 

template <typename T>
struct optional_optimized_disengaged_state_traits<T*>
{
  constexpr static bool is_optimized = true;
  constexpr static raw_storage_of_size<T> const& value() {
    return cast( (T*)1 );
  }
};

Are you sure that doesn't invoke undefined behavior?  This stuff is really tricky to get right, and users generally have less freedom than compiler vendors, since vendors can define undefined behavior any way they like to make things work.

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

[Billy O'Neal]

Do we really want to compress this? optional<optional<T>> is certainly an anti-pattern.

Billy O'Neal

https://github.com/BillyONeal/

http://stackoverflow.com/users/82320/billy-oneal

Malware Response Instructor - BleepingComputer.com

--
 
---
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/.

[Thiago Macieira]

On quarta-feira, 2 de outubro de 2013 11:57:48, Andrzej Krzemieński wrote:
> template <typename T>
> struct optional_optimized_disengaged_state_traits<T*>
> {
> constexpr static bool is_optimized = true;
> constexpr static raw_storage_of_size<T> const& value() {
> return cast( (T*)1 );
> }
> };

You cannot assume that a pointer of value 1 is invalid. In fact, there's only
one pointer whose value is invalid and that's null (and such a pointer doesn't
have to be stored as a bitwise zero).

You can only assume that if you know the platform's ABI. That's not the case
for this forum, we have to assume all possibilities may exist.

> template <>
> struct optional_optimized_disengaged_state_traits<bool>
> {
> constexpr static bool is_optimized = true;
> constexpr static raw_storage_of_size<bool> const& value() {
> return cast( 0x10 );
> }
> };

And again, this only works if the user isn't abusing the type for storing
something else. Since optional::operator* returns an lvalue reference to the
data, the user could be storing anything there or casting to other values via
type-punning (strict aliasing is only broken if you write one type and read
another).

No, you must assume that all bits are used by the user, unless the user tells
you that there are certain bit patterns that won't be used. That probably
means a user-defined specialisation of std::optional.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358

[Alisdair Meredith]

I thought about merging the engaged bits, but you must spell out very carefully what our concurrency guarantees are in this case.  Can I read the outer optional's engaged state while changing the engagement of the inner optional?

Sent from my iPhone

[David Stone]

On Wednesday, October 2, 2013 1:30:03 PM UTC-6, Thiago Macieira wrote:

On quarta-feira, 2 de outubro de 2013 11:57:48, Andrzej Krzemieński wrote:
> template <typename T>
> struct optional_optimized_disengaged_state_traits<T*>
> {
>   constexpr static bool is_optimized = true;
>   constexpr static raw_storage_of_size<T> const& value() {
>     return cast( (T*)1 );
>   }
> };

You cannot assume that a pointer of value 1 is invalid. In fact, there's only
one pointer whose value is invalid and that's null (and such a pointer doesn't
have to be stored as a bitwise zero).

Which is why this is being proposed as a possible class that the user / vendor could specialize, rather than a specialization that should be defined for all pointers in the standard as a guarantee. If my code will only run on such a system (or if I'm the compiler vendor and I know that this compilation of this code is only running on such a system), then this could simplify the creation of such a compressed optional.

[David Stone]

On Wednesday, October 2, 2013 1:07:38 PM UTC-6, Nevin ":-)" Liber wrote:

On 2 October 2013 13:57, Andrzej Krzemieński <akrz...@gmail.com> wrote:

I can think of two ways to optimize the storage size for tr2::optional for certain T's -- at the cost of potentially adding run-time overhead when checking for the disengaged state:

Is this anything more than an implementation detail (and therefore not on topic for this forum)? 

No more than std::allocator_traits.

I have yet to see *any* benchmarks of real world programs where adding such complexity would be a net benefit to anyone, let alone most users.

If people really wish to go down this route, I can't stop them, other than to say that in all likelihood I will argue and vote strongly against such a proposal.

I have a video game playing program that would need such an optimization before I could consider using optional as a data member for some of my classes. I make a large number of copies as I evaluate various game states (the copying is so that I can restore to a previous state). Approximately 60-70% of my time is spent in new and delete due to contained std::vector elements, despite my focus on the most compact data representation possible. I can measure the performance of my program primarily by two things: the depth of search and the size of my classes.

In one situation, I had a std::vector that had either one or two elements. By replacing this with a std::array<element_type, 2> and using a special sentinel value, I was able to emulate the std::vector approach. It was as though I had a vector of capacity 2 that had a size of 1 if the value at 2 was that sentinel value. This allowed me to avoid the space overhead of sizeof(std::size_t) * 2 by not having to directly store a size and a capacity and removed an extra call to new.

A situation that I am facing right now that I am optimizing is a class that can exist up to 48 times in a game state, so an overhead of one byte could lead to 48 more bytes. One of the many patterns that many of my classes face (including this one) is that I need to store a counter for how long a condition has existed (and this counter has a known upper limit, for instance, 10). My current implementation is to use a magic value of std::numeric_limits<uint8_least_t>::max() to simulate an optional value, but I feel it would improve the clarity of my code to be able to make the counter itself just optional (as the counter doesn't conceptually exist at all if the effect is not yet in play). I would not use std::optional for this if that had an overhead of one byte per counter I applied this to.

My algorithm can search a specified number of turns ahead in the game. It is primarily by reducing the size of my data structures that I was able to reduce the run time at a depth of 4 (my current depth) from some unknown amount of time (which I estimate at about 70 days) down to about 20 seconds. I don't know exactly how much of this can be attributed to reduction in the size of data structures, but I did perform reductions incrementally and saw significant performance improvements each time. My hope is that the reduction in size I am working on right now will allow me to do depth=5 in a reasonable time frame (less than a minute rather than 20-30 minutes).

[Billy O'Neal]

It seems like you should just define a type that has the semantics you want for those requirements.

Billy O'Neal

https://github.com/BillyONeal/

http://stackoverflow.com/users/82320/billy-oneal

Malware Response Instructor - BleepingComputer.com

--

[David Stone]

And I could call that type optional<counter_type>.

[Daniel Krügler]

2013/10/2 Andrzej Krzemieński <akrz...@gmail.com>:

> template <typename T>
> struct optional_optimized_disengaged_state_traits<T*>
> {
> constexpr static bool is_optimized = true;
> constexpr static raw_storage_of_size<T> const& value() {
> return cast( (T*)1 );
> }
> };

Note that this function could not be used in constant expressions,
because the (implied) use of reinterpret_cast is not valid in this
context.

- Daniel