220 18743 <4359ebfb-5e20-42c1-84a0-16ef6201db33@isocpp.org> article Path: news.gmane.org!not-for-mail From: vlovich@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Compressing std::optional Date: Wed, 24 Jun 2015 09:55:49 -0700 (PDT) Lines: 449 Approved: news@gmane.org Message-ID: <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_1089_1110554904.1435164949798" X-Trace: ger.gmane.org 1435164956 23839 80.91.229.3 (24 Jun 2015 16:55:56 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 24 Jun 2015 16:55:56 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBCFIZX46Q4HRBF6CVOWAKGQE5N7KUZA@isocpp.org Wed Jun 24 18:55:55 2015 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-qk0-f198.google.com ([209.85.220.198]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Z7nxp-0003tp-ES for gclcip-std-proposals@m.gmane.org; Wed, 24 Jun 2015 18:55:53 +0200 Original-Received: by qkca12 with SMTP id a12sf49203271qkc.1 for ; Wed, 24 Jun 2015 09:55:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:message-id: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=iLaOH5cIrclHB+MRXfVHHCuq7gRVp2MUyWgwgQBHJLc=; b=rcN0Oz2ioRoP037BoOzvavmNraF4UJ7qzF8DQrce9+RtAF2AfL+NqnHSZquqrLVkMJ UJZbooVQ7GeCS13gueG8dKCF4pVmb4ThIaoXNNvip2wpeYmnCl+N2LxNRqoyvOyj5TfP Aj/zNlTJSAWrnGgHpOpwXtLT1cfBuMO4cLtm+cNmJTWk8+ysyHpomm8m01C4CGb/+yIa EsNqBrC2zy+dv4h4l2p1KsIFgUy2JDA/ZIafoEaiKfZddxA0B4CUs72zz40BqbEVv52K gGDZIMqODdl/9wuhoJNbaeBHaQ+SK1sn/gOwrebMzU+USXtlp/IGyGHlNDvX9fZAJFB4 CgjQ== 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:message-id: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=iLaOH5cIrclHB+MRXfVHHCuq7gRVp2MUyWgwgQBHJLc=; b=K2GSr5TBdXzDnYT1V1VLxT1DRy/Gcfihe+Nek7+a1egFPBR/Su42fpP0RSveZad/B0 ug/zuYvIFM73X1/SGCdbLAnNPr5bLJK3wkVr1euZIi8CMyZm1xuJPhF0SuvHGW3UE7xn EZd6ZVxUAqof9V0Arun4j/pc47R66OQwoDX2zGqUT7wMHyYdzARVjgO0wEqP1OIhfP1z /X5fT3r2/jJdplz33qhrFyUXELjsSQ0rLFN4JGAQcGzU2faPmXcdkeYe45HCFP8aHBM6 RUvHuOJc7l6Ny0KwOBmHuCDOOCE4i7QBHSWKKYKoKgKpl2xfVbzt8cvGAQQFlQQz6yv/ ZR6w== X-Gm-Message-State: ALoCoQneLJYGnZXZgFq5Wvf+OjM7Ho7RmEMq5e7TH89HBjMwOW1OPlgQXu5T7rRz/MZR7eqBimIg X-Received: by 10.140.151.65 with SMTP id 62mr54022880qhx.1.1435164952452; Wed, 24 Jun 2015 09:55:52 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.107.165.208 with SMTP id o199ls693468ioe.13.gmail; Wed, 24 Jun 2015 09:55:51 -0700 (PDT) X-Received: by 10.50.142.39 with SMTP id rt7mr107453igb.17.1435164951755; Wed, 24 Jun 2015 09:55:51 -0700 (PDT) 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:18743 Archived-At: ------=_Part_1089_1110554904.1435164949798 Content-Type: multipart/alternative; boundary="----=_Part_1090_1315895451.1435164949798" ------=_Part_1090_1315895451.1435164949798 Content-Type: text/plain; charset=UTF-8 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_1090_1315895451.1435164949798 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
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 l= imitations of the current approach.
  • For small types optional can= double the size of storage
  • Overhead can add up when stored in arra= ys (& most of it due to padding if the sizeof(T) > 1).
  • Canno= t be used as a drop-in in a memory-mapped structure.  In these scenari= os 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 exampl= e, 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 us= er-defined types but makes this optimization not possible for built-in type= s.  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 a= s reported by std::string).


To that end, my proposal t= o 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 m= ight look like. constexpr omitted for simplicity but I don't see anything p= reventing it & optional_storage is the hypothetical :


=

template= <typename T, typename S =3D 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=
 =   {<= /span>
  =       return std::get<0>(_data).is_initialized();
    }
    ...
private:
    std::tuple<= S,<= span style=3D"color: #000;" class=3D"styled-by-prettify"> aligned_storage_t= <sizeof(T)>> _data;
};

default_optiona= l_initialization_storage would comply with the interface for optional_initi= alization_storage & look something like:


struct default_optional_initialization_storage {
    template <typename T>
&n= bsp;   bool is_= initialized(T*) const
    {
        return _= initialized;
    }

    template <typename T>
    void<= span style=3D"color: #000;" class=3D"styled-by-prettify"> set_initialized(T*, = bool initialized<= /code>)
    {        _initialized =3D initialized;
    }

    bool _initialized =3D false;
};


<= /p>An example for hiding the state as via NaN for double:

struct nan_optional_storage {
    bool is_initialized(double* value) cons= t
 = ;   {
        return !std::= isnan(*value)
    }

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


<= /span>Some of my thoughts on this sample code:
  • It is by n= o 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 do= es something like this even make sense.
  • This is purely a mechan= ism 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 sen= tinel-value use-case would probably be important enough that a simple API f= or expressing such a sentinel value would be valuable (something like optio= nal<double, sentinel<double, nan("")>>)
  • This is purely = a customization point to apply domain-specific knowledge to optimize option= al.  There is no optimization available by default.
  • The carefu= l 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 o= f 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 d= istinct 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 &= 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_1090_1315895451.1435164949798-- ------=_Part_1089_1110554904.1435164949798-- .