220 18744 <69177b02-6042-4c47-ba24-90d8a7aa157c@isocpp.org> article Path: news.gmane.org!not-for-mail From: vlovich@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Compressing std::optional Date: Wed, 24 Jun 2015 10:00:17 -0700 (PDT) Lines: 365 Approved: news@gmane.org Message-ID: <69177b02-6042-4c47-ba24-90d8a7aa157c@isocpp.org> References: <4359ebfb-5e20-42c1-84a0-16ef6201db33@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_1312_406570771.1435165217659" X-Trace: ger.gmane.org 1435165230 28796 80.91.229.3 (24 Jun 2015 17:00:30 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 24 Jun 2015 17:00:30 +0000 (UTC) Cc: vlovich@gmail.com To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBCFIZX46Q4HRBI6EVOWAKGQETMJK55A@isocpp.org Wed Jun 24 19:00:22 2015 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yh0-f70.google.com ([209.85.213.70]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Z7o29-0007Dl-Kp for gclcip-std-proposals@m.gmane.org; Wed, 24 Jun 2015 19:00:21 +0200 Original-Received: by yhb65 with SMTP id 65sf35608910yhb.3 for ; Wed, 24 Jun 2015 10:00:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:cc:message-id:in-reply-to:references:subject :mime-version:content-type:x-original-sender:reply-to:precedence :mailing-list:list-id:x-spam-checked-in-group:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=5F/DhnRKu9kcs+sQb4fr/TNGdoB/VASw5dv3KWtsELo=; b=S+QPG/HXkHWiXiNUlfs0q3324VnwQ7pHOeyfwWBXpijqp8FWprvs19yhCUMIvx1Tdr IUHASQZ3J/KWn2S/GQXSSM5fp5GJis9WbOBwxBmimliFcq8+52+De802ATbPxy6vZhQ/ 76WJktlsGc+JiteLnVcgsfXaHvhCdM/AYdDu9Aob+LMRAxiRG3RD8vs+o6frGUPi763H wOLnf46Dp/LKxVP/N5i/JCbEPetT7p4DP+q3KktR27ixeNRTb/8p+nhewgRUTfDVEw7T 8jrtYJsqQ1hC5MsqfVKjV4xkpaPZzY8YiANn67/5FsdsO4K6lvEaYXo7ysYrmlEYEhU7 w+Zw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:date:from:to:cc:message-id:in-reply-to :references:subject:mime-version:content-type:x-original-sender :reply-to:precedence:mailing-list:list-id:x-spam-checked-in-group :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=5F/DhnRKu9kcs+sQb4fr/TNGdoB/VASw5dv3KWtsELo=; b=fuvNBx0d7DgE/RxdspTjmv0d95InpfvhngLckgdT7j2C+N6vWVBd2X3xgshVbH3/Vy ndzkw7CLgdHGaHaM2b2vM03THmRSyx9Tm7rpwb7hMtMn11cFm/CkH2tYrCokwdlPFkq0 dSNy0PwQ3X/F2yKhPn0WosVGsMc8FS8OQI4J3+NzB6l5Gx9VAoMg49BeQy4OBphtpmwt SRtYRY4dcq2ctw6KR4MULBZ4u9DswopStAByhze0T0yZ/Bn91jwWRJo2ivShewcADmMF BBn0SwguSfEXIu9umimDwUmQIbvgKYy1TIKYDzT5AI6/mfjGpC+T+syq/W23MvwEEbIt L4qw== X-Gm-Message-State: ALoCoQlqVcYe+1U0ZwaUSELABP4OKOLFAatgjnCL7NdqPf2nb23+Mci6VS3SxGv05vOxyUUBr9Ee X-Received: by 10.13.204.213 with SMTP id o204mr3266818ywd.51.1435165220512; Wed, 24 Jun 2015 10:00:20 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.107.19.32 with SMTP id b32ls627086ioj.84.gmail; Wed, 24 Jun 2015 10:00:19 -0700 (PDT) X-Received: by 10.50.4.34 with SMTP id h2mr106985igh.7.1435165219796; Wed, 24 Jun 2015 10:00:19 -0700 (PDT) In-Reply-To: <4359ebfb-5e20-42c1-84a0-16ef6201db33@isocpp.org> X-Original-Sender: vlovich@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:18744 Archived-At: ------=_Part_1312_406570771.1435165217659 Content-Type: multipart/alternative; boundary="----=_Part_1313_2089467090.1435165217659" ------=_Part_1313_2089467090.1435165217659 Content-Type: text/plain; charset=UTF-8 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. On Wednesday, June 24, 2015 at 9:55:50 AM UTC-7, vlo...@gmail.com wrote: > > 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 > > class optional { > public: > optional(std::nullopt_t) > { > std::get<0>(_data).set_initialized(reinterpret_cast(&std::get< > 1>(_data)), false); > } > > optional(const T&) > { > std::get<0>(_data).set_initialized(reinterpret_cast(&std::get< > 1>(_data)), true); > } > ... > bool is_initialized() const > { > return std::get<0>(_data).is_initialized(); > } > ... > private: > std::tuple> _data; > }; > > default_optional_initialization_storage would comply with the interface > for optional_initialization_storage & look something like: > > > struct default_optional_initialization_storage { > template > bool is_initialized(T*) const > { > return _initialized; > } > > template > 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::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>) > - 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 email to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/. ------=_Part_1313_2089467090.1435165217659 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Forgot to mention.  The reader may ask that this shou= ld just be left to users to implement their own class.  std::optional = is non-trivial to get the interface & implementation right (moreso I th= ink than even something like vector).
A customization point solves an op= timization problem that many may have in a much simpler way without having = to try to implement the entire optional interface.

On Wednesday, Jun= e 24, 2015 at 9:55:50 AM UTC-7, vlo...@gmail.com wrote:
Hi,

I'd like to bring up t= his topic again.  I know Andrzej brought it up a couple of years ago f= or 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 a= dd 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 structur= e.  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 op= tionals.  For example, protobuf uses bit-packing for this.
The main limitation, at least as I see it, of the Andrzej's traits impleme= ntation is that it cannot be customized per-instance of optional.  Thi= s is probably fine for user-defined types but makes this optimization not p= ossible for built-in types.  It's not uncommon to have only certain in= stances of built-in types have invalid bit-patterns (e.g. NaN for double, m= aximum value for size_t as reported by std::string).


T= o that end, my proposal to accomplish something like this would require add= ing a secondary template parameter that defines the storage of the initiali= zation state.  Here is a straw-man skeleton example of what the std::o= ptional class interface might look like. constexpr omitted for simplicity b= ut I don't see anything preventing it & optional_storage is the hypothe= tical :


template <typename T, typename S =3D default_optional_= initialization_storage>
class<= span style=3D"color:#000"> optional {
public<= /span>:
&nb= sp;   optional(std::nullopt_t)
    {
        std::get<0>(_data).set_initializ= ed(reinterpret_cast<T*>(&std::get<1>(= _data)), false= );
  &= nbsp; }=

    optional(const T&)
  =   {
        std::get<0>(_data).set_initialized(reinterpret_cast<= T*>(&std::get<1>(_data)), true);
    }
 &= nbsp;  ...
    bool is_initialized() = const
    {
     =   return std::get<0>(_data).is_initialized();
    }
    ...
private:
    std::<= span style=3D"color:#000">tuple<S, aligned_storage_t= <sizeof(T)&= gt;> _data;
};

default_optional_initial= ization_storage would comply with the interface for optional_initialization= _storage & look something like:


<= /p>

struct default_optional_= initialization_storage {
    t= emplate <typename T>
    bool is_initialized(= T*) co= nst
    {
     =   return _initialized;
  &n= bsp; }<= br>
    template <typename T>
    void set_in= itialized(<= span style=3D"color:#660">T*, bool= initialized<= /code>)
    {
     =    _initialized =3D initialized;
=     }

  &= nbsp; bool _initialized =3D false;
};
=


<= code>

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

struct<= span style=3D"color:#000"> nan_optional_storage {
    bool is_initialized(double* value)= const
    {
      =   return !std::isnan(*value)
    }
=
    void set_initializ= ed(double* value, bool initialized)
    {
  =       if (!initialized) {
   &nb= sp;        *value =3D std::numeric_limit= s<double>::quite_NaN();
      &= nbsp; }
    }
};


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 jus= t 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 bu= ilt-in types (e.g. not even pointer types would optimize the nullptr case b= y default).
  • The sentinel-value use-case would probably be important= enough that a simple API for expressing such a sentinel value would be val= uable (something like optional<double, sentinel<double, nan("")>&g= t;)
  • This is purely a customization point to apply domain-specific k= nowledge 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 t= his 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 optio= nal monad and should be a distinct type.  I'm not sure I really see wh= y (purity of mapping C++ to theoretical CS aside).
Thanks for read= ing,
Vitali

--

---
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/<= /a>.
------=_Part_1313_2089467090.1435165217659-- ------=_Part_1312_406570771.1435165217659-- .