220 6896 article Path: news.gmane.org!not-for-mail From: "Billy O'Neal" Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Compressing Optional Date: Wed, 2 Oct 2013 12:08:20 -0700 Lines: 409 Approved: news@gmane.org Message-ID: References: <9a40a660-b48b-49b7-9d39-85810a55ebcf@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=90e6ba614a764b786c04e7c6cdf0 X-Trace: ger.gmane.org 1380740944 30618 80.91.229.3 (2 Oct 2013 19:09:04 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 2 Oct 2013 19:09:04 +0000 (UTC) To: std-proposals Original-X-From: std-proposals+bncBDKLBLVE6ADBBTW6WGJAKGQEATE7CYQ@isocpp.org Wed Oct 02 21:09:07 2013 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-ie0-f200.google.com ([209.85.223.200]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1VRRnF-0007Fi-8r for gclcip-std-proposals@m.gmane.org; Wed, 02 Oct 2013 21:09:05 +0200 Original-Received: by mail-ie0-f200.google.com with SMTP id tp5sf4305875ieb.11 for ; Wed, 02 Oct 2013 12:09:04 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :x-original-sender:x-original-authentication-results:reply-to :precedence:mailing-list:list-id:list-post:list-help:list-archive :list-subscribe:list-unsubscribe:content-type; bh=QfeqSx4owK5/GsdzfJlpdP7GR37MwgSBdH5KI6utvjg=; b=RLVfXUnWGSyThwZbL7cnTNVN5tbYeTLRUQeDoMJD/oGL4UiBEPHgaCkBIwm4FUZwRo Rjy0tZZWBBbjubHxIvqpavbJpXdPQJEQfYSXMZ8vpq+ooX1fwf/WIDrL6aIM4PCSx/tb zcYlElNkROH3gkemPfDyt/ZmY0AdZvokk+iP4V7UkV503aGfEQcrzDxS+6WKmX+tphFS gZObni0hXilZV3c2uMswzt/DWUTWpsCXG+cklotvev7bO4LiXsrhN7qpytaUfq5c0H3v Pc7vghbEVMcNBCZTkS3yzW7rdwly7o832T615rI3WdjkCnRTWMUqQvuwvrzv7E4joolL EzDg== X-Received: by 10.42.118.194 with SMTP id y2mr1604772icq.19.1380740944277; Wed, 02 Oct 2013 12:09:04 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.50.128.169 with SMTP id np9ls1149835igb.27.gmail; Wed, 02 Oct 2013 12:09:01 -0700 (PDT) X-Received: by 10.60.134.230 with SMTP id pn6mr2968292oeb.52.1380740941318; Wed, 02 Oct 2013 12:09:01 -0700 (PDT) Original-Received: from mail-ie0-x22b.google.com (mail-ie0-x22b.google.com [2607:f8b0:4001:c03::22b]) by mx.google.com with ESMTPS id sp4si3247857oeb.46.1969.12.31.16.00.00 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 02 Oct 2013 12:09:01 -0700 (PDT) Received-SPF: pass (google.com: domain of billy.oneal@gmail.com designates 2607:f8b0:4001:c03::22b as permitted sender) client-ip=2607:f8b0:4001:c03::22b; Original-Received: by mail-ie0-f171.google.com with SMTP id at1so2984168iec.30 for ; Wed, 02 Oct 2013 12:09:00 -0700 (PDT) X-Received: by 10.42.62.196 with SMTP id z4mr2276616ich.49.1380740940657; Wed, 02 Oct 2013 12:09:00 -0700 (PDT) Original-Received: by 10.43.166.67 with HTTP; Wed, 2 Oct 2013 12:08:20 -0700 (PDT) In-Reply-To: <9a40a660-b48b-49b7-9d39-85810a55ebcf@isocpp.org> X-Original-Sender: billy.oneal@gmail.com X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of billy.oneal@gmail.com designates 2607:f8b0:4001:c03::22b as permitted sender) smtp.mail=billy.oneal@gmail.com; dkim=pass header.i=@gmail.com; dmarc=pass (p=NONE dis=NONE) header.from=gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: 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:6896 Archived-At: --90e6ba614a764b786c04e7c6cdf0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Do we really want to compress this? optional> is certainly an anti-pattern. Billy O'Neal https://github.com/BillyONeal/ http://stackoverflow.com/users/82320/billy-oneal Malware Response Instructor - BleepingComputer.com On Wed, Oct 2, 2013 at 11:57 AM, Andrzej Krzemie=C5=84ski wrote: > I can think of two ways to optimize the storage size for tr2::optional fo= r > certain T's -- at the cost of potentially adding run-time overhead when > checking for the disengaged state: > > 1. For optional>, use one bool-size value for storing two > engaged/disengaged flag > 2. For certain T's where not all bit-patterns represent a meaningful valu= e > some special value can be used to indicate a disengaged optional and no > additional disengaged flag is needed. > > Re 1. > optional> can be specialized to the following representation: > > class optional > { > uint_of_size engaged_; > raw_storage_of_size 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>::operator bool() const { > return !(engaged_ & 0x10); > } > > The value access retuning a type-punned myself: > > optional const& optional>::operator*() const { > return reinterpret_cast 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> from > optional. > > This could be generalized to optional>> > > Re 2. > Second optimization works for types where there is a value (or bit-patter= n > 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 programme= rs > to easily customize optional for their types, another interface could be > standardized: a type trait: > > template > struct optional_optimized_disengaged_state_traits > { > constexpr static bool is_optimized =3D false; > constexpr static raw_storage_of_size const& value(); > }; > > If you want, you can specialize this trait to enable the optimization: > > template > struct optional_optimized_disengaged_state_traits > { > constexpr static bool is_optimized =3D true; > constexpr static raw_storage_of_size const& value() { > return cast( (T*)1 ); > } > }; > > template <> > struct optional_optimized_disengaged_state_traits > { > constexpr static bool is_optimized =3D true; > constexpr static raw_storage_of_size const& value() { > return cast( 0x10 ); > } > }; > > Now, checking for disengaged state can be implemented by memcmp: > > explicit optional::operator bool() const { > return memcmp (&value_, &optional_optimized_disengaged_state_traits:= : > 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 > > -- > > --- > 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/. > --=20 ---=20 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 e= mail 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-proposa= ls/. --90e6ba614a764b786c04e7c6cdf0 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Do we really want to compress this? optional<optional&l= t;T>> is certainly an anti-pattern.
<= br clear=3D"all">
Billy O'Neal
Mal= ware Response Instructor - BleepingComputer.com


On Wed, Oct 2, 2013 at 11:57 AM, Andrzej= Krzemie=C5=84ski <akrzemi1@gmail.com> wrote:
I can think of two ways to optimize the storage = size for=20 tr2::optional for certain T's -- at the cost of potentially adding=20 run-time overhead when checking for the disengaged state:

1. For optional<optional<T>>, use one bool-size value for stor= ing two engaged/disengaged flag
2. For certain T's where not all bit-patterns represent a meaningful valu= e 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 represent= ation:

class optional <= br>{
=C2=A0 uin= t_of_size<bool> engaged_;
=C2=A0 raw_storage_of_size<<= /span>T> = value_;
= };

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

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

The value access retuning a type-punned my= self:

optional<T> <= /span>const& optional<optional<T>>= ::operator*() const {
=C2=A0 return reinterpret_cast<optional<T> const<= span style=3D"color:rgb(102,102,0)">&>(*this);
}
=

In the inner optional we check for engaged stat= e without the bit-mask.

Well, type-punning doesn't work with constexpr functions, but I wonder if th= e same effect cannot be achieved by deriving=20 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:
<= div>a pointer with address 0x1
or a bool with bit pattern 0x1= 0.

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

template= <typename T>
struct optional_opti= mized_disengaged_state_traits
{
=C2=A0 conste= xpr static bool is_optimize= d =3D false;
=C2=A0 constexpr static raw_storage_of_s= ize<T> const& value();
};

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

template = <typename T= >
struct optional_opti= mized_disengaged_state_traits&l= t;T*>
{
=C2=A0 constexpr static bool is_optimized =3D tru= e;
=C2=A0 constexpr static raw_storage_of_s= ize<T> const& value() {
=C2=A0 =C2=A0 return= cast( (T*)1 );
=C2=A0 }
};

template = <>
struct optional_optimized_disenga= ged_state_traits<bool>
{
=C2=A0 constexpr static bool is_optimized =3D tru= e;
=C2=A0 constexpr static raw_storage_of_s= ize<bool> const& value() {
=C2=A0 =C2=A0 return= cast( 0x10 );
=C2=A0 }
};

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

explicit optional<<= span>T>::operator bool() const {
=C2=A0 return memcmp= (&value_, &optional_optimized_disengaged_stat= e_traits<T>::value(), sizeof(<= span>value_));
}

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

Regards,
&rzej

<= /div>

--
=C2=A0
---
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-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/gro= up/std-proposals/.

--
 
---
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-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/<= /a>.
--90e6ba614a764b786c04e7c6cdf0-- .