------=_Part_12_20737642.1380995200568
Content-Type: text/plain; charset=ISO-8859-1

Often we need to do bitwise manipulations such as finding the next power of
2, counting trailing zeros, and so on.

I'd like to propose a new <bitops> header which will contain a set of
constexpr bit manipulation functions.

Why standardize this?
1) These are low level basic primitives that can be used in a wide variety
of applications and domains.
2) Many cpus provide special instructions for these operations which are
not available to the programmer without implementation specific support.
3) The most efficient implementation varies greatly between platforms
(built in instructions? loops? arithmetic? table lookup?), thus it belongs
in the standard so that library implementers can sort out the differences
on each platform
4) Many compilers already provide intrinsics for a lot of these operations,
so a lot of the work is already done. We just need a standard wrapper.
5) operator>> for signed integral types behavior is implementation defined.
There are no standard primitives to explicitly state logical shift and
arithmetic shift. Also there is no circular shift or rotate.
6) This is a very simple library addition that has no dependencies.

https://github.com/fmatthew5876/stdcxx/blob/master/bitops/include/bitops.hh

Questions:
1) Naming, as always. Should we prefer short names to make complicated
expressions easier to understand? Or long names which are more descriptive
but make expressions more cumbersome?
2) Whats missing? We should add operations even if they are trivial because
making an expression out of words is much easier to understand than a
collection of cryptic logical operators. We should also add operations that
have special cpu instructions on most common platforms.
3) What to name the functions?
4) How should we constrain the templates for integral types? Or should we?
5) Should we allow char*/uint8_t*/void* for the alignment functions?
6) Should this be merged with my other byteorder proposal?
https://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/EY5l56it-Jw
7) What should we name the functions?
8) Did I mention naming????

--

---
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_12_20737642.1380995200568
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Often we need to do bitwise manipulations such as finding =
the next power of 2, counting trailing zeros, and so on.<div><br></div><div=
>I'd like to propose a new &lt;bitops&gt; header which will contain a set o=
f constexpr bit manipulation functions.</div><div><br></div><div>Why standa=
rdize this?</div><div>1) These are low level basic primitives that can be u=
sed in a wide variety of applications and domains.</div><div>2) Many cpus p=
rovide special instructions for these operations which are not available to=
 the programmer without implementation specific support.</div><div>3) The m=
ost efficient implementation varies greatly between platforms (built in ins=
tructions? loops? arithmetic? table lookup?), thus it belongs in the standa=
rd so that library implementers can sort out the differences on each platfo=
rm</div><div>4) Many compilers already provide intrinsics for a lot of thes=
e operations, so a lot of the work is already done. We just need a standard=
 wrapper.</div><div>5) operator&gt;&gt; for signed integral types behavior =
is implementation defined. There are no standard primitives to explicitly s=
tate logical shift and arithmetic shift. Also there is no circular shift or=
 rotate.</div><div>6) This is a very simple library addition that has no de=
pendencies.</div><div><br></div><div><a href=3D"https://github.com/fmatthew=
5876/stdcxx/blob/master/bitops/include/bitops.hh">https://github.com/fmatth=
ew5876/stdcxx/blob/master/bitops/include/bitops.hh</a><br></div><div><br></=
div><div>Questions:</div><div>1) Naming, as always. Should we prefer short =
names to make complicated expressions easier to understand? Or long names w=
hich are more descriptive but make expressions more cumbersome?</div><div>2=
) Whats missing? We should add operations even if they are trivial because =
making an expression out of words is much easier to understand than a colle=
ction of cryptic logical operators. We should also add operations that have=
 special cpu instructions on most common platforms.</div><div>3) What to na=
me the functions?</div><div>4) How should we constrain the templates for in=
tegral types? Or should we?</div><div>5) Should we allow char*/uint8_t*/voi=
d* for the alignment functions?</div><div>6) Should this be merged with my =
other byteorder proposal?&nbsp;<a href=3D"https://groups.google.com/a/isocp=
p.org/forum/#!topic/std-proposals/EY5l56it-Jw">https://groups.google.com/a/=
isocpp.org/forum/#!topic/std-proposals/EY5l56it-Jw</a></div><div>7) What sh=
ould we name the functions?</div><div>8) Did I mention naming????</div></di=
v>

<p></p>

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

------=_Part_12_20737642.1380995200568--

.

On Oct 5, 2013, at 1:46 PM, fmatthew5876@gmail.com wrote:

> Often we need to do bitwise manipulations such as finding the next power =
of 2, counting trailing zeros, and so on.
>=20
> I'd like to propose a new <bitops> header which will contain a set of con=
stexpr bit manipulation functions.
>=20
> Why standardize this?
> 1) These are low level basic primitives that can be used in a wide variet=
y of applications and domains.
> 2) Many cpus provide special instructions for these operations which are =
not available to the programmer without implementation specific support.
> 3) The most efficient implementation varies greatly between platforms (bu=
ilt in instructions? loops? arithmetic? table lookup?), thus it belongs in =
the standard so that library implementers can sort out the differences on e=
ach platform
> 4) Many compilers already provide intrinsics for a lot of these operation=
s, so a lot of the work is already done. We just need a standard wrapper.
> 5) operator>> for signed integral types behavior is implementation define=
d. There are no standard primitives to explicitly state logical shift and a=
rithmetic shift. Also there is no circular shift or rotate.
> 6) This is a very simple library addition that has no dependencies.
>=20
> https://github.com/fmatthew5876/stdcxx/blob/master/bitops/include/bitops.=
hh
>=20
> Questions:
> 1) Naming, as always. Should we prefer short names to make complicated ex=
pressions easier to understand? Or long names which are more descriptive bu=
t make expressions more cumbersome?
> 2) Whats missing? We should add operations even if they are trivial becau=
se making an expression out of words is much easier to understand than a co=
llection of cryptic logical operators. We should also add operations that h=
ave special cpu instructions on most common platforms.
> 3) What to name the functions?
> 4) How should we constrain the templates for integral types? Or should we=
?
> 5) Should we allow char*/uint8_t*/void* for the alignment functions?
> 6) Should this be merged with my other byteorder proposal? https://groups=
..google.com/a/isocpp.org/forum/#!topic/std-proposals/EY5l56it-Jw
> 7) What should we name the functions?
> 8) Did I mention naming????

I am very enthusiastically in favor of ctz, clz and popcount, and I think t=
hose are good names (pop_count is a reasonable alternate for the third).  I=
 can take or leave the other algorithms.  I have no objection to them.  But=
 we have desperately needed ctz, clz and popcount for years now, and I'm am=
azed that neither C nor C++ has added them yet.  Imho it is just as importa=
nt to be able to write low-level code (i.e. give me *that* machine instruct=
ion) as it is to be able to write high-level code.  And it seems to me C an=
d C++ have not kept up with modern machine architecture (except for C++11 a=
tomics).

One possibile alternative for these three functions, instead of templating =
them is to overload:

unsigned           clz(unsigned x);
unsigned long      clz(unsigned long x);
unsigned long long clz(unsigned long long x);

I've purposefully left out types smaller than unsigned because of integer p=
romotion rules, and I've purposefully left out signed integral types becaus=
e bit manipulations are much less error prone on unsigned types.

That being said, I believe the need for these three functions is so great, =
I would vote in favor of them however they are packaged.

Here is a one application that I find very motivating for ctz.  Please feel=
 free to use it in any proposal you write.  This is the best gcd algorithm =
I've come across if there is a quality (one or two instruction) ctz under t=
he hood:

unsigned long long
gcd(unsigned long long x, unsigned long long y)
{
    if (x =3D=3D 0)
        return y;
    if (y =3D=3D 0)
        return x;
    unsigned int cf2 =3D std::ctz(x | y);
    x >>=3D std::ctz(x);
    while (true)
    {
        y >>=3D std::ctz(y);
        if (x =3D=3D y)
            break;
        if (x > y)
            std::swap(x, y);
        if (x =3D=3D 1)
            break;
        y -=3D x;
    }
    return x << cf2;
}

<disclaimer> I did not discover the binary gcd algorithm (obviously).  But =
I did code up this implementation of it.  And have thoroughly performance t=
ested it against the variant using operator%.

Howard

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

.

On Sat, Oct 5, 2013 at 3:35 PM, Howard Hinnant <howard.hinnant@gmail.com> w=
rote:
> I am very enthusiastically in favor of ctz, clz and popcount, and I think=
 those are good names (pop_count is a reasonable alternate for the third). =
 I can take or leave the other algorithms.  I have no objection to them.  B=
ut we have desperately needed ctz, clz and popcount for years now, and I'm =
amazed that neither C nor C++ has added them yet.  Imho it is just as impor=
tant to be able to write low-level code (i.e. give me *that* machine instru=
ction) as it is to be able to write high-level code.  And it seems to me C =
and C++ have not kept up with modern machine architecture (except for C++11=
 atomics).

I also +N for popcount.  But chosen from ffs fls ctz clz is tricky :)

> One possibile alternative for these three functions, instead of templatin=
g them is to overload:
>
> unsigned           clz(unsigned x);
> unsigned long      clz(unsigned long x);
> unsigned long long clz(unsigned long long x);
>
> I've purposefully left out types smaller than unsigned because of integer=
 promotion rules, and I've purposefully left out signed integral types beca=
use bit manipulations are much less error prone on unsigned types.

I usually prefer templates because integer promotion can
promote a signed value to an unsigned one which drove
me mad.  In template we can static_assert them.

However, unfortunately, when standardizing arithmetical
algorithms, opinions from C committee will probably
jump in and finally we decide to use suffixes, like special
math functions :(

--=20
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

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

.

------=_Part_1821_1615427.1381018177170
Content-Type: text/plain; charset=ISO-8859-1



On Saturday, October 5, 2013 3:35:05 PM UTC-4, Howard Hinnant wrote:
>
> I am very enthusiastically in favor of ctz, clz and popcount, and I think
> those are good names (pop_count is a reasonable alternate for the third).

I can take or leave the other algorithms.  I have no objection to them.

I've used the align functions many times when implementing memory
allocators. I've heard that some embedded hardware guys would like to be
able to use saturated addition and that some cpus have native support for
it.


> But we have desperately needed ctz, clz and popcount for years now, and
> I'm amazed that neither C nor C++ has added them yet.  Imho it is just as
> important to be able to write low-level code (i.e. give me *that* machine
> instruction) as it is to be able to write high-level code.  And it seems to
> me C and C++ have not kept up with modern machine architecture (except for
> C++11 atomics).
>

I am in total agreement, the only way you can write efficient high level
abstractions is if you implement it with efficient low level primitives.
Curious, where else do you think C++ is behind the hardware? C++ is
supposed to be a low level language, so there is no excuse for not exposing
common hardware features.


>
> One possibile alternative for these three functions, instead of templating
> them is to overload:
>
> unsigned           clz(unsigned x);
> unsigned long      clz(unsigned long x);
> unsigned long long clz(unsigned long long x);
>
> I've purposefully left out types smaller than unsigned because of integer
> promotion rules, and I've purposefully left out signed integral types
> because bit manipulations are much less error prone on unsigned types.




> That being said, I believe the need for these three functions is so great,
> I would vote in favor of them however they are packaged.
>
> Here is a one application that I find very motivating for ctz.  Please
> feel free to use it in any proposal you write.  This is the best gcd
> algorithm I've come across if there is a quality (one or two instruction)
> ctz under the hood:
>
> unsigned long long
> gcd(unsigned long long x, unsigned long long y)
> {
>     if (x == 0)
>         return y;
>     if (y == 0)
>         return x;
>     unsigned int cf2 = std::ctz(x | y);
>     x >>= std::ctz(x);
>     while (true)
>     {
>         y >>= std::ctz(y);
>         if (x == y)
>             break;
>         if (x > y)
>             std::swap(x, y);
>         if (x == 1)
>             break;
>         y -= x;
>     }
>     return x << cf2;
> }
>
> <disclaimer> I did not discover the binary gcd algorithm (obviously).  But
> I did code up this implementation of it.  And have thoroughly performance
> tested it against the variant using operator%.
>
> Another one is a CSV file parser I wrote once which used SSE instructions.
It was blazing fast and it also required ctz().
Also related to that:
http://www.strchr.com/sse2_optimised_strlen


> Howard
>
>

--

---
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_1821_1615427.1381018177170
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Saturday, October 5, 2013 3:35:05 PM UTC-4, How=
ard Hinnant wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;marg=
in-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">I am very en=
thusiastically in favor of ctz, clz and popcount, and I think those are goo=
d names (pop_count is a reasonable alternate for the third). &nbsp;&nbsp;</=
blockquote><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left=
: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">I can take or leave=
 the other algorithms. &nbsp;I have no objection to them. &nbsp;</blockquot=
e><div>I've used the align functions many times when implementing memory al=
locators. I've heard that some embedded hardware guys would like to be able=
 to use saturated addition and that some cpus have native support for it.</=
div><div>&nbsp;</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;m=
argin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">But we ha=
ve desperately needed ctz, clz and popcount for years now, and I'm amazed t=
hat neither C nor C++ has added them yet. &nbsp;Imho it is just as importan=
t to be able to write low-level code (i.e. give me *that* machine instructi=
on) as it is to be able to write high-level code. &nbsp;And it seems to me =
C and C++ have not kept up with modern machine architecture (except for C++=
11 atomics).
<br></blockquote><div><br></div><div>I am in total agreement, the only way =
you can write efficient high level abstractions is if you implement it with=
 efficient low level primitives.</div><div>Curious, where else do you think=
 C++ is behind the hardware? C++ is supposed to be a low level language, so=
 there is no excuse for not exposing common hardware features.</div><div>&n=
bsp;</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left:=
 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br>One possibile alternative for these three functions, instead of templat=
ing them is to overload:
<br>
<br>unsigned &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; clz(unsigned x);
<br>unsigned long &nbsp; &nbsp; &nbsp;clz(unsigned long x);
<br>unsigned long long clz(unsigned long long x);
<br>
<br>I've purposefully left out types smaller than unsigned because of integ=
er promotion rules, and I've purposefully left out signed integral types be=
cause bit manipulations are much less error prone on unsigned types.</block=
quote><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8=
ex;border-left: 1px #ccc solid;padding-left: 1ex;">&nbsp;</blockquote><bloc=
kquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-l=
eft: 1px #ccc solid;padding-left: 1ex;">
<br>That being said, I believe the need for these three functions is so gre=
at, I would vote in favor of them however they are packaged.
<br>
<br>Here is a one application that I find very motivating for ctz. &nbsp;Pl=
ease feel free to use it in any proposal you write. &nbsp;This is the best =
gcd algorithm I've come across if there is a quality (one or two instructio=
n) ctz under the hood:
<br>
<br>unsigned long long
<br>gcd(unsigned long long x, unsigned long long y)
<br>{
<br>&nbsp; &nbsp; if (x =3D=3D 0)
<br>&nbsp; &nbsp; &nbsp; &nbsp; return y;
<br>&nbsp; &nbsp; if (y =3D=3D 0)
<br>&nbsp; &nbsp; &nbsp; &nbsp; return x;
<br>&nbsp; &nbsp; unsigned int cf2 =3D std::ctz(x | y);
<br>&nbsp; &nbsp; x &gt;&gt;=3D std::ctz(x);
<br>&nbsp; &nbsp; while (true)
<br>&nbsp; &nbsp; {
<br>&nbsp; &nbsp; &nbsp; &nbsp; y &gt;&gt;=3D std::ctz(y);
<br>&nbsp; &nbsp; &nbsp; &nbsp; if (x =3D=3D y)
<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;
<br>&nbsp; &nbsp; &nbsp; &nbsp; if (x &gt; y)
<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; std::swap(x, y);
<br>&nbsp; &nbsp; &nbsp; &nbsp; if (x =3D=3D 1)
<br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;
<br>&nbsp; &nbsp; &nbsp; &nbsp; y -=3D x;
<br>&nbsp; &nbsp; }
<br>&nbsp; &nbsp; return x &lt;&lt; cf2;
<br>}
<br>
<br>&lt;disclaimer&gt; I did not discover the binary gcd algorithm (obvious=
ly). &nbsp;But I did code up this implementation of it. &nbsp;And have thor=
oughly performance tested it against the variant using operator%.
<br>
<br></blockquote><div>Another one is a CSV file parser I wrote once which u=
sed SSE instructions. It was blazing fast and it also required ctz().</div>=
<div>Also related to that:</div><div><a href=3D"http://www.strchr.com/sse2_=
optimised_strlen">http://www.strchr.com/sse2_optimised_strlen</a><br></div>=
<div>&nbsp;</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">Howard
<br>
<br></blockquote></div>

<p></p>

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

------=_Part_1821_1615427.1381018177170--

.

------=_Part_2046_26217456.1381018717016
Content-Type: text/plain; charset=ISO-8859-1

Here's a reference explaining why it would be good to have the 3 shifts
(logical, arithmetic, circular), saturated math, and nibble swapping.
http://embeddedgurus.com/stack-overflow/2012/06/optimizing-for-the-cpu-compiler/

I've also needed arithmetic shift. I just used a signed shift because it
worked on my platform, but that's not standards compliant.

--

---
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_2046_26217456.1381018717016
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Here's a reference explaining why it would be good to have=
 the 3 shifts (logical, arithmetic, circular), saturated math, and nibble s=
wapping.<div><a href=3D"http://embeddedgurus.com/stack-overflow/2012/06/opt=
imizing-for-the-cpu-compiler/">http://embeddedgurus.com/stack-overflow/2012=
/06/optimizing-for-the-cpu-compiler/</a><br></div><div><br></div><div>I've =
also needed arithmetic shift. I just used a signed shift because it worked =
on my platform, but that's not standards compliant.</div></div>

<p></p>

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

------=_Part_2046_26217456.1381018717016--

.

On s=E1bado, 5 de outubro de 2013 17:09:37, fmatthew5876@gmail.com wrote:
> > I am very enthusiastically in favor of ctz, clz and popcount, and I thi=
nk=20
> > those are good names (pop_count is a reasonable alternate for the
> > third).  =20
> I can take or leave the other algorithms.  I have no objection to them. =
=20

POSIX already specifies "clz" as "ffs" (find first set). Maybe we should co=
nsider=20
taking ffs and add "fls" to match.

--=20
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

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

.

On Sat, Oct 5, 2013 at 8:44 PM, Thiago Macieira <thiago@macieira.org> wrote:
> POSIX already specifies "clz" as "ffs" (find first set). Maybe we should consider
> taking ffs and add "fls" to match.

POSIX only standardized ffs, which was a BSD extension.
GNU extension has ffsl and ffsll, FreeBSD has fls variants.
But all of them take signed types.  I don't think that's a right
approach (and I don't care; if we only standardize the bitwise
functions for C++, mangled names will distinguish them.)

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--

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

.

On Sat, Oct 5, 2013 at 3:35 PM, Howard Hinnant <howard.hinnant@gmail.com> wrote:
> One possibile alternative for these three functions, instead of templating them is to overload:
>
> unsigned           clz(unsigned x);
> unsigned long      clz(unsigned long x);
> unsigned long long clz(unsigned long long x);

BTW I think they should return int...

fmatthew5876, take a look at this:

  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3646.pdf

Network working group want to standardize hton* ntoh*,
and above is the decision they made (which already
passed LEWG and LWG).  They defined generic cases,
and deleted all specializations other than unsigned types
(or you can learn from 26.5.1.1/1 by saying "specializations
are undefined unless blah blah blah").  Then they defined
existing practice (as in POSIX) in terms of the generic case.
But for bitwise algorithms, POSIX ffs is the only (and
uncommon) prior art.  I think you can safely ignore them.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--

---
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_1909_9800873.1381026971892
Content-Type: text/plain; charset=ISO-8859-1

I've updated git with some of the comments from everyone. Thank you all for
helping out!

On Saturday, October 5, 2013 9:23:16 PM UTC-4, Zhihao Yuan wrote:
>
> On Sat, Oct 5, 2013 at 3:35 PM, Howard Hinnant <howard....@gmail.com<javascript:>>
> wrote:
> > One possibile alternative for these three functions, instead of
> templating them is to overload:
> >
> > unsigned           clz(unsigned x);
> > unsigned long      clz(unsigned long x);
> > unsigned long long clz(unsigned long long x);
>
> BTW I think they should return int...
>
> fmatthew5876, take a look at this:
>
>   http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2013/n3646.pdf
>
> Network working group want to standardize hton* ntoh*,
> and above is the decision they made (which already
> passed LEWG and LWG).  They defined generic cases,
> and deleted all specializations other than unsigned types
> (or you can learn from 26.5.1.1/1 by saying "specializations
> are undefined unless blah blah blah").
>
>
Thats a pretty cool trick.

How do you do this part effectively though?
template <>
c o n s t e x p r unsigned i n t e g r a l
hton ( unsigned i n t e g r a l h o s t ) noexcept ;

for clz() and friends I just explicitly created specializations for the 3
unsigned int types.

But then there is other stuff is is_pow2(T t). This should be overloaded
for every integral type but not for any other type.
Whats the best way to  accomplish that? enable_if?
Is there any good resource on doing this kind of overload control with
templates?

Thanks!

--

---
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_1909_9800873.1381026971892
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>I've updated git with some of the comments from every=
one. Thank you all for helping out!</div><div><br>On Saturday, October 5, 2=
013 9:23:16 PM UTC-4, Zhihao Yuan wrote:<blockquote class=3D"gmail_quote" s=
tyle=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-le=
ft: 1ex;">On Sat, Oct 5, 2013 at 3:35 PM, Howard Hinnant &lt;<a href=3D"jav=
ascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"LIRdvxDbj0YJ">howard..=
...@gmail.com</a>&gt; wrote:
<br>&gt; One possibile alternative for these three functions, instead of te=
mplating them is to overload:
<br>&gt;
<br>&gt; unsigned &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; clz(unsigned x);
<br>&gt; unsigned long &nbsp; &nbsp; &nbsp;clz(unsigned long x);
<br>&gt; unsigned long long clz(unsigned long long x);
<br>
<br>BTW I think they should return int...
<br>
<br>fmatthew5876, take a look at this:
<br>
<br>&nbsp; <a href=3D"http://www.open-std.org/JTC1/SC22/WG21/docs/papers/20=
13/n3646.pdf" target=3D"_blank">http://www.open-std.org/JTC1/<wbr>SC22/WG21=
/docs/papers/2013/<wbr>n3646.pdf</a>
<br>
<br>Network working group want to standardize hton* ntoh*,
<br>and above is the decision they made (which already
<br>passed LEWG and LWG). &nbsp;They defined generic cases,
<br>and deleted all specializations other than unsigned types
<br>(or you can learn from <a href=3D"http://26.5.1.1/1" target=3D"_blank">=
26.5.1.1/1</a> by saying "specializations
<br>are undefined unless blah blah blah"). &nbsp;<br>
<br></blockquote><div><br></div>Thats a pretty cool trick.&nbsp;<div><br></=
div><div>How do you do this part effectively though?</div><div><div>templat=
e &lt;&gt;</div><div>c o n s t e x p r unsigned i n t e g r a l</div></div>=
<div>hton ( unsigned i n t e g r a l h o s t ) noexcept ;&nbsp;</div></div>=
<div><br></div><div>for clz() and friends I just explicitly created special=
izations for the 3 unsigned int types.</div><div><br></div><div>But then th=
ere is other stuff is is_pow2(T t). This should be overloaded for every int=
egral type but not for any other type.</div><div>Whats the best way to &nbs=
p;accomplish that? enable_if?</div><div>Is there any good resource on doing=
 this kind of overload control with templates?</div><div><br></div><div>Tha=
nks!</div><div><br></div></div>

<p></p>

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

------=_Part_1909_9800873.1381026971892--

.

On Sat, Oct 5, 2013 at 10:36 PM,  <fmatthew5876@gmail.com> wrote:
> How do you do this part effectively though?
> template <>
> c o n s t e x p r unsigned i n t e g r a l
> hton ( unsigned i n t e g r a l h o s t ) noexcept ;

I guess they just specialized each one.  If your implementation
is already generic, you don't need to care about those;
static_assert(is_unsigned<T>(), ...); is enough.

> for clz() and friends I just explicitly created specializations for the 3
> unsigned int types.

Yes, that's what that trick for (when your implementation
is not generic, like __built_clz*).

> But then there is other stuff is is_pow2(T t). This should be overloaded for
> every integral type but not for any other type.
> Whats the best way to  accomplish that? enable_if?

static_assert.  enable_if can help if you want user
to specialize is_pow2...

> Is there any good resource on doing this kind of overload control with
> templates?

static_assert and = delete gives you hard error.
enable_if for simple cases (customization), tag
dispatching for complex cases (you probably
won't reach this...)  Another useful pattern is to
have a main template and an overload set
instead of specializations, usually seen in
arithmetic functions:

  http://en.cppreference.com/w/cpp/numeric/math/pow

Explanation is at here:

  http://www.gotw.ca/publications/mill17.htm

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--

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

.

On Sat, Oct 5, 2013 at 10:36 PM,  <fmatthew5876@gmail.com> wrote:
> But then there is other stuff is is_pow2(T t). This should be overloaded for
> every integral type but not for any other type.

Emm, I don't think your `is_pow2` can work with signed integers,
because signed integers may have 1's complement or signed
magnitude representations (although I don't think those systems
still exist LOL).  Basically I think the whole bitwise proposal
should only work with unsigned integers because that one
requires 2's complement.  If user want to apply `is_pow2` on
their signed integers, they'd better be required to perform
explicit conventions.

And the "main template + an overload set" pattern I just
suggested don't work well as bitwise operations' interfaces,
because overloading permits type promotions (which is
good for arithmetic operations).  But they are still good
for implementation, if you need to handle some glitches.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--

---
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_1970_3443530.1381032273817
Content-Type: text/plain; charset=ISO-8859-1



On Saturday, October 5, 2013 11:43:00 PM UTC-4, Zhihao Yuan wrote:
>
> On Sat, Oct 5, 2013 at 10:36 PM,  <fmatth...@gmail.com <javascript:>>
> wrote:
> > But then there is other stuff is is_pow2(T t). This should be overloaded
> for
> > every integral type but not for any other type.
>
> Emm, I don't think your `is_pow2` can work with signed integers,
> because signed integers may have 1's complement or signed
> magnitude representations (although I don't think those systems
> still exist LOL).


My particular implementation may not work if the platform is not using 2's
compliment. However, detecting whether a signed integer is a power of 2
could still be useful no?
If someone decides to implement on another platform without 2's compliment,
then they will have to implement is_pow2() there as well.


> Basically I think the whole bitwise proposal
> should only work with unsigned integers because that one
> requires 2's complement.  If user want to apply `is_pow2` on
> their signed integers, they'd better be required to perform
> explicit conventions.
>
> And the "main template + an overload set" pattern I just
> suggested don't work well as bitwise operations' interfaces,
> because overloading permits type promotions (which is
> good for arithmetic operations).  But they are still good
> for implementation, if you need to handle some glitches.
>
> --
> Zhihao Yuan, ID lichray
> The best way to predict the future is to invent it.
> ___________________________________________________
> 4BSD -- http://4bsd.biz/
>

--

---
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_1970_3443530.1381032273817
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Saturday, October 5, 2013 11:43:00 PM UTC-4, Zh=
ihao Yuan wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin=
-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On Sat, Oct 5,=
 2013 at 10:36 PM, &nbsp;&lt;<a href=3D"javascript:" target=3D"_blank" gdf-=
obfuscated-mailto=3D"0JhLyfuHANIJ">fmatth...@gmail.com</a>&gt; wrote:
<br>&gt; But then there is other stuff is is_pow2(T t). This should be over=
loaded for
<br>&gt; every integral type but not for any other type.
<br>
<br>Emm, I don't think your `is_pow2` can work with signed integers,
<br>because signed integers may have 1's complement or signed
<br>magnitude representations (although I don't think those systems
<br>still exist LOL). &nbsp;</blockquote><div>&nbsp;</div><div>My particula=
r implementation may not work if the platform is not using 2's compliment. =
However, detecting whether a signed integer is a power of 2 could still be =
useful no?</div><div>If someone decides to implement on another platform wi=
thout 2's compliment, then they will have to implement is_pow2() there as w=
ell.</div><div>&nbsp;</div><blockquote class=3D"gmail_quote" style=3D"margi=
n: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">Bas=
ically I think the whole bitwise proposal
<br>should only work with unsigned integers because that one
<br>requires 2's complement. &nbsp;If user want to apply `is_pow2` on
<br>their signed integers, they'd better be required to perform
<br>explicit conventions.
<br>
<br>And the "main template + an overload set" pattern I just
<br>suggested don't work well as bitwise operations' interfaces,
<br>because overloading permits type promotions (which is
<br>good for arithmetic operations). &nbsp;But they are still good
<br>for implementation, if you need to handle some glitches.
<br>
<br>--=20
<br>Zhihao Yuan, ID lichray
<br>The best way to predict the future is to invent it.
<br>______________________________<wbr>_____________________
<br>4BSD -- <a href=3D"http://4bsd.biz/" target=3D"_blank">http://4bsd.biz/=
</a>
<br></blockquote></div>

<p></p>

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

------=_Part_1970_3443530.1381032273817--

.

On Sun, Oct 6, 2013 at 12:04 AM,  <fmatthew5876@gmail.com> wrote:
> My particular implementation may not work if the platform is not using 2's
> compliment. However, detecting whether a signed integer is a power of 2
> could still be useful no?

Hmm, I see.  But I don't know whether it's useful.  Another
thing is, if it's useful, this function may need to go <cmath>.
Make your decision then go LEWG and Numerics study group :)

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--

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

.

Please do write this up and send it in to the numerics study group.
Like Howard said, our primitives have fallen behind the processors'
capabilities.

I've included some comments below, but the numerics SG should own
this, so they could override anything I say here.

I hated the acronyms at first glance, but they seem to have a wide
history, so we should probably resist the temptation to rename them.

I'm nervous about using overloading for clz, since its result depends
on the word size. fls() seems to avoid that problem?

I agree with omitting signed variants.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3542.html
does the same.

I'd probably only include one of clz or ffs, since they look redundant?

Is parity needed, or do compilers optimize popcount(x)%2 into the same
instruction? Mention which compilers you test so that people can
replicate or extend your results.

std::align does something like your align_up(). You should explain why
both are needed in your paper.

saturating arithmetic is useful but seems like it belongs somewhere
else. Are interleave_bits and swap_nibbles general-purpose enough to
want to put them in the standard library?

It'd be nice to avoid the constraint on the shl/shr/rotl/rotr variants
that their argument is non-negative. I assume that's there so the
compiler can directly emit machine instructions without checking?




On Sat, Oct 5, 2013 at 10:46 AM,  <fmatthew5876@gmail.com> wrote:
> Often we need to do bitwise manipulations such as finding the next power of
> 2, counting trailing zeros, and so on.
>
> I'd like to propose a new <bitops> header which will contain a set of
> constexpr bit manipulation functions.
>
> Why standardize this?
> 1) These are low level basic primitives that can be used in a wide variety
> of applications and domains.
> 2) Many cpus provide special instructions for these operations which are not
> available to the programmer without implementation specific support.
> 3) The most efficient implementation varies greatly between platforms (built
> in instructions? loops? arithmetic? table lookup?), thus it belongs in the
> standard so that library implementers can sort out the differences on each
> platform
> 4) Many compilers already provide intrinsics for a lot of these operations,
> so a lot of the work is already done. We just need a standard wrapper.
> 5) operator>> for signed integral types behavior is implementation defined.
> There are no standard primitives to explicitly state logical shift and
> arithmetic shift. Also there is no circular shift or rotate.
> 6) This is a very simple library addition that has no dependencies.
>
> https://github.com/fmatthew5876/stdcxx/blob/master/bitops/include/bitops.hh
>
> Questions:
> 1) Naming, as always. Should we prefer short names to make complicated
> expressions easier to understand? Or long names which are more descriptive
> but make expressions more cumbersome?
> 2) Whats missing? We should add operations even if they are trivial because
> making an expression out of words is much easier to understand than a
> collection of cryptic logical operators. We should also add operations that
> have special cpu instructions on most common platforms.
> 3) What to name the functions?
> 4) How should we constrain the templates for integral types? Or should we?
> 5) Should we allow char*/uint8_t*/void* for the alignment functions?
> 6) Should this be merged with my other byteorder proposal?
> https://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/EY5l56it-Jw
> 7) What should we name the functions?
> 8) Did I mention naming????
>
> --
>
> ---
> 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/.

--

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

.

On s=E1bado, 5 de outubro de 2013 22:02:23, Jeffrey Yasskin wrote:
> Is parity needed, or do compilers optimize popcount(x)%2 into the same
> instruction? Mention which compilers you test so that people can
> replicate or extend your results.

GCC 4.7: { return __builtin_parity(x); }
        popcntl %edi, %eax
        andl    $1, %eax

As for the is_pow2, I'd leave it out. It's equivalent to popcount(x) <=3D 1=
=20
(strictly a power of 2 for =3D=3D 1).

Then again, comparing popcount here has resulted in four instructions, wher=
eas=20
the AND trick resulted in three (not counting the zero extension). The=20
compiler might know better which alternative is faster.

--=20
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

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

.

------=_Part_2200_17539602.1381064912938
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable



On Sunday, October 6, 2013 1:02:23 AM UTC-4, Jeffrey Yasskin wrote:
>
> Please do write this up and send it in to the numerics study group.=20
> Like Howard said, our primitives have fallen behind the processors'=20
> capabilities.=20
>
> I've included some comments below, but the numerics SG should own=20
> this, so they could override anything I say here.=20
>
> I hated the acronyms at first glance, but they seem to have a wide=20
> history, so we should probably resist the temptation to rename them.=20
>

I agree. Also its much easier to write a long expression with ctz() then=20
with count_trailing_zeroes().=20


> I'm nervous about using overloading for clz, since its result depends=20
> on the word size. fls() seems to avoid that problem?=20
>
>
If we have overloads for all sizes, then will this really be a problem?
Also overloading is necessary for templates.

What we might consider is adding suffxed versions which call the template=
=20
versions:
int ctzs(unsigned short t) { return ctz(t); }
int ctzl(unsigned long t) { return ctz(t); }
int ctzll(unsigned long long t) { return ctz(t); }
=20

> I agree with omitting signed variants.=20
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3542.html=20
> does the same.=20
>
> I'd probably only include one of clz or ffs, since they look redundant?=
=20
>

Maybe they are:
http://gcc.godbolt.org/#%7B%22version%22%3A3%2C%22filterAsm%22%3A%7B%22labe=
ls%22%3Atrue%2C%22directives%22%3Atrue%2C%22commentOnly%22%3Atrue%7D%2C%22c=
ompilers%22%3A%5B%7B%22source%22%3A%22%23include%20%3Ccstring%3E%5Cn%23incl=
ude%20%3Ccstdlib%3E%5Cn%5Cn%5Cnint%20ffs(int%20t)%20%7B%5Cn%20%20return%20_=
_builtin_ffs(t)%3B%5Cn%7D%5Cn%5Cnint%20clz(int%20t)%20%7B%5Cn%20%20return%2=
0__builtin_clz(t)%3B%5Cn%7D%5Cn%5Cnint%20ctz(int%20t)%20%7B%5Cn%20%20return=
%20__builtin_ctz(t)%3B%5Cn%7D%22%2C%22compiler%22%3A%22%2Fusr%2Fbin%2Fg%2B%=
2B-4.8%22%2C%22options%22%3A%22-O3%20-march%3Dnative%20-std%3Dc%2B%2B11%22%=
7D%5D%7D

However, I'd still include both for 3 reasons:
1) In the future (or maybe even now), one cpu may be able to do each in one=
=20
instruction
2) Half of the purpose of this library is to be able to write easy to read=
=20
bitwise expressions. So having a separate ffs() and ctz()  makes sense even=
=20
if they are almost the same thing. I want to avoid writing a "RSIC" style=
=20
interface.
3) Adding a few extra functions which just wrap the others (in this case=20
its just ctz()-1) takes 2 seconds to implement. It costs basically nothing.


> Is parity needed, or do compilers optimize popcount(x)%2 into the same=20
> instruction? Mention which compilers you test so that people can=20
> replicate or extend your results.=20
>
Either way I'd be included to have both for reasons mentioned above.=20

>
> std::align does something like your align_up(). You should explain why=20
> both are needed in your paper.=20
>

std::align is pretty heavy weight and has a very specific purpose. A good=
=20
use for both align_up and align_down processing an array of bytes with simd=
=20
instructions which require aligned loads and stores. I've used it for this=
=20
before.=20
std::align could be implemented using align_up.

>
> saturating arithmetic is useful but seems like it belongs somewhere=20
> else. Are interleave_bits and swap_nibbles general-purpose enough to=20
> want to put them in the standard library?=20
>
I'd like to get an embedded guy in the talk to help with this. If its=20
important for them I'd like to help them out. Also if a lot of common cpus=
=20
have instructions for these things we should add them merely on the=20
principle of exposing the hardware better.=20

>
> It'd be nice to avoid the constraint on the shl/shr/rotl/rotr variants=20
> that their argument is non-negative. I assume that's there so the=20
> compiler can directly emit machine instructions without checking?=20
>

You mean on t or s?

I had a variant where s was signed and you could shift left or right=20
depending on sign. I should add those back in. For the others, yes it=20
should be assumed unsigned so the compiler can do it without a check.

Thanks for your valuable feedback!=20

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

------=_Part_2200_17539602.1381064912938
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Sunday, October 6, 2013 1:02:23 AM UTC-4, Jeffr=
ey Yasskin wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">Please do wri=
te this up and send it in to the numerics study group.
<br>Like Howard said, our primitives have fallen behind the processors'
<br>capabilities.
<br>
<br>I've included some comments below, but the numerics SG should own
<br>this, so they could override anything I say here.
<br>
<br>I hated the acronyms at first glance, but they seem to have a wide
<br>history, so we should probably resist the temptation to rename them.
<br></blockquote><div><br></div><div>I agree. Also its much easier to write=
 a long expression with ctz() then with count_trailing_zeroes().&nbsp;</div=
><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin=
-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br>I'm nervous about using overloading for clz, since its result depends
<br>on the word size. fls() seems to avoid that problem?
<br>
<br></blockquote><div><br></div><div>If we have overloads for all sizes, th=
en will this really be a problem?</div><div>Also overloading is necessary f=
or templates.</div><div><br></div><div>What we might consider is adding suf=
fxed versions which call the template versions:</div><div>int ctzs(unsigned=
 short t) { return ctz(t); }<br></div><div>int ctzl(unsigned long t) { retu=
rn ctz(t); }</div><div>int ctzll(unsigned long long t) { return ctz(t); }<b=
r></div><div>&nbsp;</div><blockquote class=3D"gmail_quote" style=3D"margin:=
 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">I agr=
ee with omitting signed variants.
<br><a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n354=
2.html" target=3D"_blank">http://www.open-std.org/jtc1/<wbr>sc22/wg21/docs/=
papers/2013/<wbr>n3542.html</a>
<br>does the same.
<br>
<br>I'd probably only include one of clz or ffs, since they look redundant?
<br></blockquote><div><br></div><div>Maybe they are:</div><div><a href=3D"h=
ttp://gcc.godbolt.org/#%7B%22version%22%3A3%2C%22filterAsm%22%3A%7B%22label=
s%22%3Atrue%2C%22directives%22%3Atrue%2C%22commentOnly%22%3Atrue%7D%2C%22co=
mpilers%22%3A%5B%7B%22source%22%3A%22%23include%20%3Ccstring%3E%5Cn%23inclu=
de%20%3Ccstdlib%3E%5Cn%5Cn%5Cnint%20ffs(int%20t)%20%7B%5Cn%20%20return%20__=
builtin_ffs(t)%3B%5Cn%7D%5Cn%5Cnint%20clz(int%20t)%20%7B%5Cn%20%20return%20=
__builtin_clz(t)%3B%5Cn%7D%5Cn%5Cnint%20ctz(int%20t)%20%7B%5Cn%20%20return%=
20__builtin_ctz(t)%3B%5Cn%7D%22%2C%22compiler%22%3A%22%2Fusr%2Fbin%2Fg%2B%2=
B-4.8%22%2C%22options%22%3A%22-O3%20-march%3Dnative%20-std%3Dc%2B%2B11%22%7=
D%5D%7D">http://gcc.godbolt.org/#%7B%22version%22%3A3%2C%22filterAsm%22%3A%=
7B%22labels%22%3Atrue%2C%22directives%22%3Atrue%2C%22commentOnly%22%3Atrue%=
7D%2C%22compilers%22%3A%5B%7B%22source%22%3A%22%23include%20%3Ccstring%3E%5=
Cn%23include%20%3Ccstdlib%3E%5Cn%5Cn%5Cnint%20ffs(int%20t)%20%7B%5Cn%20%20r=
eturn%20__builtin_ffs(t)%3B%5Cn%7D%5Cn%5Cnint%20clz(int%20t)%20%7B%5Cn%20%2=
0return%20__builtin_clz(t)%3B%5Cn%7D%5Cn%5Cnint%20ctz(int%20t)%20%7B%5Cn%20=
%20return%20__builtin_ctz(t)%3B%5Cn%7D%22%2C%22compiler%22%3A%22%2Fusr%2Fbi=
n%2Fg%2B%2B-4.8%22%2C%22options%22%3A%22-O3%20-march%3Dnative%20-std%3Dc%2B=
%2B11%22%7D%5D%7D</a></div><div><br></div><div>However, I'd still include b=
oth for 3 reasons:</div><div>1) In the future (or maybe even now), one cpu =
may be able to do each in one instruction</div><div>2) Half of the purpose =
of this library is to be able to write easy to read bitwise expressions. So=
 having a separate ffs() and ctz() &nbsp;makes sense even if they are almos=
t the same thing. I want to avoid writing a "RSIC" style interface.</div><d=
iv>3) Adding a few extra functions which just wrap the others (in this case=
 its just ctz()-1) takes 2 seconds to implement. It costs basically nothing=
..</div><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin: 0;=
margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br>Is parity needed, or do compilers optimize popcount(x)%2 into the same
<br>instruction? Mention which compilers you test so that people can
<br>replicate or extend your results.
<br></blockquote><div>Either way I'd be included to have both for reasons m=
entioned above.&nbsp;</div><blockquote class=3D"gmail_quote" style=3D"margi=
n: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br>std::align does something like your align_up(). You should explain why
<br>both are needed in your paper.
<br></blockquote><div><br></div><div>std::align is pretty heavy weight and =
has a very specific purpose. A good use for both align_up and align_down pr=
ocessing an array of bytes with simd instructions which require aligned loa=
ds and stores. I've used it for this before.&nbsp;</div><div>std::align cou=
ld be implemented using align_up.</div><blockquote class=3D"gmail_quote" st=
yle=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-lef=
t: 1ex;">
<br>saturating arithmetic is useful but seems like it belongs somewhere
<br>else. Are interleave_bits and swap_nibbles general-purpose enough to
<br>want to put them in the standard library?
<br></blockquote><div>I'd like to get an embedded guy in the talk to help w=
ith this. If its important for them I'd like to help them out. Also if a lo=
t of common cpus have instructions for these things we should add them mere=
ly on the principle of exposing the hardware better.&nbsp;</div><blockquote=
 class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1=
px #ccc solid;padding-left: 1ex;">
<br>It'd be nice to avoid the constraint on the shl/shr/rotl/rotr variants
<br>that their argument is non-negative. I assume that's there so the
<br>compiler can directly emit machine instructions without checking?
<br></blockquote><div><br></div><div>You mean on t or s?</div><div><br></di=
v><div>I had a variant where s was signed and you could shift left or right=
 depending on sign. I should add those back in. For the others, yes it shou=
ld be assumed unsigned so the compiler can do it without a check.</div><div=
><br></div><div>Thanks for your valuable feedback!&nbsp;</div></div>

<p></p>

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

------=_Part_2200_17539602.1381064912938--

.

------=_Part_2233_9693637.1381067597558
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable



On Sunday, October 6, 2013 1:43:57 AM UTC-4, Thiago Macieira wrote:
>
> On s=E1bado, 5 de outubro de 2013 22:02:23, Jeffrey Yasskin wrote:=20
> > Is parity needed, or do compilers optimize popcount(x)%2 into the same=
=20
> > instruction? Mention which compilers you test so that people can=20
> > replicate or extend your results.=20
>
> GCC 4.7: { return __builtin_parity(x); }=20
>         popcntl %edi, %eax=20
>         andl    $1, %eax=20
>
> As for the is_pow2, I'd leave it out. It's equivalent to popcount(x) <=3D=
 1=20
> (strictly a power of 2 for =3D=3D 1).=20
>

But whats the most efficient way to implement is_pow2()? Using popcount as=
=20
you did or using t & (t-1) as I did? What if a particular platform doesn't=
=20
have a popcount instruction and has to do it manually with a loop or table?
The most efficient implementation of is_pow2() depends entirely on the=20
platform, thus it should be standardized.

Also again it helps the users. They just need to call is_pow2(). They don't=
=20
need to think about using either popcount or masking. They don't need to=20
spend an hour or more of their workday looking up and profiling the most=20
efficient is_pow2() implementation. Redoing the same work hundreds have=20
already done on their own (and likely making mistakes if they are not=20
experts).

Whenever I need one of these bitwise functions. I always have to start=20
googling and looking at all those bit twiddling references. I'd like to=20
stop doing that, at least for the most common ones.

>
> Then again, comparing popcount here has resulted in four instructions,=20
> whereas=20
> the AND trick resulted in three (not counting the zero extension). The=20
> compiler might know better which alternative is faster.=20
>
> --=20
> Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org=20
>    Software Architect - Intel Open Source Technology Center=20
>       PGP/GPG: 0x6EF45358; fingerprint:=20
>       E067 918B B660 DBD1 105C  966C 33F5 F005 6EF4 5358=20
>
>

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

------=_Part_2233_9693637.1381067597558
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Sunday, October 6, 2013 1:43:57 AM UTC-4, Thiag=
o Macieira wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On s=E1bado, =
5 de outubro de 2013 22:02:23, Jeffrey Yasskin wrote:
<br>&gt; Is parity needed, or do compilers optimize popcount(x)%2 into the =
same
<br>&gt; instruction? Mention which compilers you test so that people can
<br>&gt; replicate or extend your results.
<br>
<br>GCC 4.7: { return __builtin_parity(x); }
<br>&nbsp; &nbsp; &nbsp; &nbsp; popcntl %edi, %eax
<br>&nbsp; &nbsp; &nbsp; &nbsp; andl &nbsp; &nbsp;$1, %eax
<br>
<br>As for the is_pow2, I'd leave it out. It's equivalent to popcount(x) &l=
t;=3D 1=20
<br>(strictly a power of 2 for =3D=3D 1).
<br></blockquote><div><br></div><div>But whats the most efficient way to im=
plement is_pow2()? Using popcount as you did or using t &amp; (t-1) as I di=
d? What if a particular platform doesn't have a popcount instruction and ha=
s to do it manually with a loop or table?</div><div>The most efficient impl=
ementation of is_pow2() depends entirely on the platform, thus it should be=
 standardized.</div><div><br></div><div>Also again it helps the users. They=
 just need to call is_pow2(). They don't need to think about using either p=
opcount or masking. They don't need to spend an hour or more of their workd=
ay looking up and profiling the most efficient is_pow2() implementation. Re=
doing the same work hundreds have already done on their own (and likely mak=
ing mistakes if they are not experts).</div><div><br></div><div>Whenever I =
need one of these bitwise functions. I always have to start googling and lo=
oking at all those bit twiddling references. I'd like to stop doing that, a=
t least for the most common ones.</div><blockquote class=3D"gmail_quote" st=
yle=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-lef=
t: 1ex;">
<br>Then again, comparing popcount here has resulted in four instructions, =
whereas=20
<br>the AND trick resulted in three (not counting the zero extension). The=
=20
<br>compiler might know better which alternative is faster.
<br>
<br>--=20
<br>Thiago Macieira - thiago (AT) <a href=3D"http://macieira.info" target=
=3D"_blank">macieira.info</a> - thiago (AT) <a href=3D"http://kde.org" targ=
et=3D"_blank">kde.org</a>
<br>&nbsp; &nbsp;Software Architect - Intel Open Source Technology Center
<br>&nbsp; &nbsp; &nbsp; PGP/GPG: 0x6EF45358; fingerprint:
<br>&nbsp; &nbsp; &nbsp; E067 918B B660 DBD1 105C &nbsp;966C 33F5 F005 6EF4=
 5358
<br>
<br></blockquote></div>

<p></p>

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

------=_Part_2233_9693637.1381067597558--

.

On Sun, Oct 6, 2013 at 6:08 AM,  <fmatthew5876@gmail.com> wrote:
> On Sunday, October 6, 2013 1:02:23 AM UTC-4, Jeffrey Yasskin wrote:
>> I'm nervous about using overloading for clz, since its result depends
>> on the word size. fls() seems to avoid that problem?
>>
>
> If we have overloads for all sizes, then will this really be a problem?

Think of extended and user-defined integer types?

> Also overloading is necessary for templates.
>
> What we might consider is adding suffxed versions which call the template
> versions:
> int ctzs(unsigned short t) { return ctz(t); }
> int ctzl(unsigned long t) { return ctz(t); }
> int ctzll(unsigned long long t) { return ctz(t); }

Oh, I meant that the templated version was potentially better since
mismatched types will cause compile errors. A simple overload set will
accept implicit conversions that might cause problems.

Or the overload set might be fine. This is a question that'll come up
during discussion, so you should try to address it in your paper, but
if you think you have a convincing rationale, don't let my concern
force a change.

>> I agree with omitting signed variants.
>> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3542.html
>> does the same.
>>
>> I'd probably only include one of clz or ffs, since they look redundant?
>
>
> Maybe they are:
> http://gcc.godbolt.org/#%7B%22version%22%3A3%2C%22filterAsm%22%3A%7B%22la=
bels%22%3Atrue%2C%22directives%22%3Atrue%2C%22commentOnly%22%3Atrue%7D%2C%2=
2compilers%22%3A%5B%7B%22source%22%3A%22%23include%20%3Ccstring%3E%5Cn%23in=
clude%20%3Ccstdlib%3E%5Cn%5Cn%5Cnint%20ffs(int%20t)%20%7B%5Cn%20%20return%2=
0__builtin_ffs(t)%3B%5Cn%7D%5Cn%5Cnint%20clz(int%20t)%20%7B%5Cn%20%20return=
%20__builtin_clz(t)%3B%5Cn%7D%5Cn%5Cnint%20ctz(int%20t)%20%7B%5Cn%20%20retu=
rn%20__builtin_ctz(t)%3B%5Cn%7D%22%2C%22compiler%22%3A%22%2Fusr%2Fbin%2Fg%2=
B%2B-4.8%22%2C%22options%22%3A%22-O3%20-march%3Dnative%20-std%3Dc%2B%2B11%2=
2%7D%5D%7D
>
> However, I'd still include both for 3 reasons:
> 1) In the future (or maybe even now), one cpu may be able to do each in o=
ne
> instruction

Optimizers also get better and can optimize sequences of operations
into a single instruction. x86 already requires this in many cases.
Any time you make this sort of argument, you should check it against
an existing optimizer.

> 2) Half of the purpose of this library is to be able to write easy to rea=
d
> bitwise expressions. So having a separate ffs() and ctz()  makes sense ev=
en
> if they are almost the same thing. I want to avoid writing a "RSIC" style
> interface.
> 3) Adding a few extra functions which just wrap the others (in this case =
its
> just ctz()-1) takes 2 seconds to implement. It costs basically nothing.

In some cases, I agree (e.g. is_pow2), but in others (parity maybe,
sh, sa, pow2_ge, set_bits_le, ffs) I worry that the names won't be
clear enough (so people reading code will have to learn lots of
obscure acronyms) and that we'll present too many ways to do the same
thing and wind up burdening users that way.

>> std::align does something like your align_up(). You should explain why
>> both are needed in your paper.
>
>
> std::align is pretty heavy weight

If you're saying it has a high runtime cost, please present
measurements. If you're saying it's syntactically heavy, fair enough.

> and has a very specific purpose. A good
> use for both align_up and align_down processing an array of bytes with si=
md
> instructions which require aligned loads and stores. I've used it for thi=
s
> before.

That looks like exactly the purpose std::align is useful for. It's
true that align_up and align_down are shorter ways to say the same
thing, but be sure to understand and address the reasons that
std::align takes as many arguments as it does.

>> saturating arithmetic is useful but seems like it belongs somewhere
>> else. Are interleave_bits and swap_nibbles general-purpose enough to
>> want to put them in the standard library?
>
> I'd like to get an embedded guy in the talk to help with this. If its
> important for them I'd like to help them out. Also if a lot of common cpu=
s
> have instructions for these things we should add them merely on the
> principle of exposing the hardware better.

What do you mean "if"? You should have a list of hardware instructions
and/or use cases before proposing a function. We try not to add things
to the C++ standard speculatively.

>> It'd be nice to avoid the constraint on the shl/shr/rotl/rotr variants
>> that their argument is non-negative. I assume that's there so the
>> compiler can directly emit machine instructions without checking?
>
>
> You mean on t or s?

The shift amount.

> I had a variant where s was signed and you could shift left or right
> depending on sign. I should add those back in. For the others, yes it sho=
uld
> be assumed unsigned so the compiler can do it without a check.

You probably shouldn't overload on signed/unsigned here, especially
since you don't need the extra bit. Another reason to use the stronger
precondition is to allow implementations to warn on incorrect
shift/rotate amounts. On the other hand, there is a clear meaning for
a negative "shift left", so it's unfortunate to add extra traps for
users just because optimizers aren't yet powerful enough to understand
the possible inputs for a particular call. Try to find some compiler
optimization authors when writing this section of your paper.

Jeffrey

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

.

------=_Part_24_17286951.1381149885087
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable



On Monday, October 7, 2013 2:57:01 AM UTC-4, Jeffrey Yasskin wrote:
>
> On Sun, Oct 6, 2013 at 6:08 AM,  <fmatth...@gmail.com <javascript:>>=20
> wrote:=20
> > On Sunday, October 6, 2013 1:02:23 AM UTC-4, Jeffrey Yasskin wrote:=20
> >> I'm nervous about using overloading for clz, since its result depends=
=20
> >> on the word size. fls() seems to avoid that problem?=20
> >>=20
> >=20
> > If we have overloads for all sizes, then will this really be a problem?=
=20
>
> Think of extended and user-defined integer types?=20
>
I've changed all of the return types to int anyway, so should not be a=20
problem.=20

>
> > Also overloading is necessary for templates.=20
> >=20
> > What we might consider is adding suffxed versions which call the=20
> template=20
> > versions:=20
> > int ctzs(unsigned short t) { return ctz(t); }=20
> > int ctzl(unsigned long t) { return ctz(t); }=20
> > int ctzll(unsigned long long t) { return ctz(t); }=20
>
> Oh, I meant that the templated version was potentially better since=20
> mismatched types will cause compile errors. A simple overload set will=20
> accept implicit conversions that might cause problems.=20
>
> Or the overload set might be fine. This is a question that'll come up=20
> during discussion, so you should try to address it in your paper, but=20
> if you think you have a convincing rationale, don't let my concern=20
> force a change.=20
>

This whole overload question is actually the most difficult part of this=20
whole proposal.
Should we use templates and make it an error to specify a signed type=20
without an ugly cast? Should we just have a set of flat function overloads=
=20
and allow it?
I really don't know what the best answer is and I get the feeling there may=
=20
be some passionate opinions on both sides.


> >> I agree with omitting signed variants.=20
> >> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3542.html=20
> >> does the same.=20
> >>=20
> >> I'd probably only include one of clz or ffs, since they look redundant=
?=20
> >=20
> >=20
> > Maybe they are:=20
> >=20
> http://gcc.godbolt.org/#%7B%22version%22%3A3%2C%22filterAsm%22%3A%7B%22la=
bels%22%3Atrue%2C%22directives%22%3Atrue%2C%22commentOnly%22%3Atrue%7D%2C%2=
2compilers%22%3A%5B%7B%22source%22%3A%22%23include%20%3Ccstring%3E%5Cn%23in=
clude%20%3Ccstdlib%3E%5Cn%5Cn%5Cnint%20ffs(int%20t)%20%7B%5Cn%20%20return%2=
0__builtin_ffs(t)%3B%5Cn%7D%5Cn%5Cnint%20clz(int%20t)%20%7B%5Cn%20%20return=
%20__builtin_clz(t)%3B%5Cn%7D%5Cn%5Cnint%20ctz(int%20t)%20%7B%5Cn%20%20retu=
rn%20__builtin_ctz(t)%3B%5Cn%7D%22%2C%22compiler%22%3A%22%2Fusr%2Fbin%2Fg%2=
B%2B-4.8%22%2C%22options%22%3A%22-O3%20-march%3Dnative%20-std%3Dc%2B%2B11%2=
2%7D%5D%7D=20
> >=20
> > However, I'd still include both for 3 reasons:=20
> > 1) In the future (or maybe even now), one cpu may be able to do each in=
=20
> one=20
> > instruction=20
>
> Optimizers also get better and can optimize sequences of operations=20
> into a single instruction. x86 already requires this in many cases.=20
> Any time you make this sort of argument, you should check it against=20
> an existing optimizer.=20
>
> > 2) Half of the purpose of this library is to be able to write easy to=
=20
> read=20
> > bitwise expressions. So having a separate ffs() and ctz()  makes sense=
=20
> even=20
> > if they are almost the same thing. I want to avoid writing a "RSIC"=20
> style=20
> > interface.=20
> > 3) Adding a few extra functions which just wrap the others (in this cas=
e=20
> its=20
> > just ctz()-1) takes 2 seconds to implement. It costs basically nothing.=
=20
>
> In some cases, I agree (e.g. is_pow2), but in others (parity maybe,=20
> sh, sa, pow2_ge, set_bits_le, ffs) I worry that the names won't be=20
> clear enough (so people reading code will have to learn lots of=20
> obscure acronyms) and that we'll present too many ways to do the same=20
> thing and wind up burdening users that way.

=20
Indeed. I also don't like the names sh and sa at all. Perhaps we should=20
think of acronyms that are a bit longer for these shifts.
=20

>
>
> >> std::align does something like your align_up(). You should explain why=
=20
> >> both are needed in your paper.=20
> >=20
> >=20
> > std::align is pretty heavy weight=20
>
> If you're saying it has a high runtime cost, please present=20
> measurements. If you're saying it's syntactically heavy, fair enough.=20
>
=20
I mean syntactically. std::align is extremely specialized. It does a lot of=
=20
things and has a very specific use case. Its amazing for one=20
thing and clumsy (possibly inefficient) for others. It kind of reminds me=
=20
of realloc().=20


> > and has a very specific purpose. A good=20
> > use for both align_up and align_down processing an array of bytes with=
=20
> simd=20
> > instructions which require aligned loads and stores. I've used it for=
=20
> this=20
> > before.=20
>
> That looks like exactly the purpose std::align is useful for. It's=20
> true that align_up and align_down are shorter ways to say the same=20
> thing, but be sure to understand and address the reasons that=20
> std::align takes as many arguments as it does.=20
>
=20
Consider we want to use simd for this:
void process_bytes(char*b, char*e ) {
  while(b !=3D e) {
    process1(*(b++));
  }
}=20

//ignoring casts for clarity
void process_bytes(char* b, char* e) {
  char* sb =3D align_up(b, sizeof(simd16));
  char* se =3D align_down(e, sizeof(simd16)):
  for(char* p =3D b; p < sb; ++p) {
    process1(*p);
  }
  for(char* p =3D sb; p < se; p+=3Dsizeof(simd16) {
    simd16 s =3D load_aligned_16(p);
    process16(s);
  }
  for(char* p =3D se; p < e; ++p) {
    process1(*p);
  }
}

std::align requires the size of the aligned portion of this buffer to work=
=20
correctly. In order to compute that, we would need to use=20
align_up/align_down!
Its a square function trying to fit into a round problem.


> >> saturating arithmetic is useful but seems like it belongs somewhere=20
> >> else. Are interleave_bits and swap_nibbles general-purpose enough to=
=20
> >> want to put them in the standard library?=20
> >=20
> > I'd like to get an embedded guy in the talk to help with this. If its=
=20
> > important for them I'd like to help them out. Also if a lot of common=
=20
> cpus=20
> > have instructions for these things we should add them merely on the=20
> > principle of exposing the hardware better.=20
>
> What do you mean "if"? You should have a list of hardware instructions=20
> and/or use cases before proposing a function. We try not to add things=20
> to the C++ standard speculatively.=20
>
> >> It'd be nice to avoid the constraint on the shl/shr/rotl/rotr variants=
=20
> >> that their argument is non-negative. I assume that's there so the=20
> >> compiler can directly emit machine instructions without checking?=20
> >=20
> >=20
> > You mean on t or s?=20
>
> The shift amount.=20
>

This is another tough question. There are 2 arguments I can see:
1) Use signed because the shift amount is a number, not a bit field. Also=
=20
this is compatible with << and >>.
2) Use unsigned because the shift amount cannot be negative.=20

Will (2) really catch a lot of bugs? I'm somewhat skeptical here.
=20

>
> > I had a variant where s was signed and you could shift left or right=20
> > depending on sign. I should add those back in. For the others, yes it=
=20
> should=20
> > be assumed unsigned so the compiler can do it without a check.=20
>
> You probably shouldn't overload on signed/unsigned here, especially=20
> since you don't need the extra bit. Another reason to use the stronger=20
> precondition is to allow implementations to warn on incorrect=20
> shift/rotate amounts. On the other hand, there is a clear meaning for=20
> a negative "shift left", so it's unfortunate to add extra traps for=20
> users just because optimizers aren't yet powerful enough to understand=20
> the possible inputs for a particular call. Try to find some compiler=20
> optimization authors when writing this section of your paper.=20
>

I'm rather skeptical that optimizers could optimize the branch of a signed=
=20
shift in *all* possible=20
cases to avoid the branch, but you're right it would be nice to have a=20
compiler writers perspective to confirm.
This is the kind of thing which would often be right in the middle of a hot=
=20
loop so it is important.

Having both variants also means we can support both signed and unsigned=20
shifts if they are directly supported by hardware in one instrruction
I'll need to check if this ever happens in practice though.

>
> Jeffrey=20
>

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

------=_Part_24_17286951.1381149885087
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Monday, October 7, 2013 2:57:01 AM UTC-4, Jeffr=
ey Yasskin wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On Sun, Oct 6=
, 2013 at 6:08 AM, &nbsp;&lt;<a href=3D"javascript:" target=3D"_blank" gdf-=
obfuscated-mailto=3D"TMwLnRdddtAJ">fmatth...@gmail.com</a>&gt; wrote:
<br>&gt; On Sunday, October 6, 2013 1:02:23 AM UTC-4, Jeffrey Yasskin wrote=
:
<br>&gt;&gt; I'm nervous about using overloading for clz, since its result =
depends
<br>&gt;&gt; on the word size. fls() seems to avoid that problem?
<br>&gt;&gt;
<br>&gt;
<br>&gt; If we have overloads for all sizes, then will this really be a pro=
blem?
<br>
<br>Think of extended and user-defined integer types?
<br></blockquote><div>I've changed all of the return types to int anyway, s=
o should not be a problem.&nbsp;</div><blockquote class=3D"gmail_quote" sty=
le=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left=
: 1ex;">
<br>&gt; Also overloading is necessary for templates.
<br>&gt;
<br>&gt; What we might consider is adding suffxed versions which call the t=
emplate
<br>&gt; versions:
<br>&gt; int ctzs(unsigned short t) { return ctz(t); }
<br>&gt; int ctzl(unsigned long t) { return ctz(t); }
<br>&gt; int ctzll(unsigned long long t) { return ctz(t); }
<br>
<br>Oh, I meant that the templated version was potentially better since
<br>mismatched types will cause compile errors. A simple overload set will
<br>accept implicit conversions that might cause problems.
<br>
<br>Or the overload set might be fine. This is a question that'll come up
<br>during discussion, so you should try to address it in your paper, but
<br>if you think you have a convincing rationale, don't let my concern
<br>force a change.
<br></blockquote><div><br></div><div>This whole overload question is actual=
ly the most difficult part of this whole proposal.</div><div>Should we use =
templates and make it an error to specify a signed type without an ugly cas=
t? Should we just have a set of flat function overloads and allow it?</div>=
<div>I really don't know what the best answer is and I get the feeling ther=
e may be some passionate opinions on both sides.</div><div><br></div><block=
quote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-le=
ft: 1px #ccc solid;padding-left: 1ex;">
<br>&gt;&gt; I agree with omitting signed variants.
<br>&gt;&gt; <a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/=
2013/n3542.html" target=3D"_blank">http://www.open-std.org/jtc1/<wbr>sc22/w=
g21/docs/papers/2013/<wbr>n3542.html</a>
<br>&gt;&gt; does the same.
<br>&gt;&gt;
<br>&gt;&gt; I'd probably only include one of clz or ffs, since they look r=
edundant?
<br>&gt;
<br>&gt;
<br>&gt; Maybe they are:
<br>&gt; <a href=3D"http://gcc.godbolt.org/#%7B%22version%22%3A3%2C%22filte=
rAsm%22%3A%7B%22labels%22%3Atrue%2C%22directives%22%3Atrue%2C%22commentOnly=
%22%3Atrue%7D%2C%22compilers%22%3A%5B%7B%22source%22%3A%22%23include%20%3Cc=
string%3E%5Cn%23include%20%3Ccstdlib%3E%5Cn%5Cn%5Cnint%20ffs(int%20t)%20%7B=
%5Cn%20%20return%20__builtin_ffs(t)%3B%5Cn%7D%5Cn%5Cnint%20clz(int%20t)%20%=
7B%5Cn%20%20return%20__builtin_clz(t)%3B%5Cn%7D%5Cn%5Cnint%20ctz(int%20t)%2=
0%7B%5Cn%20%20return%20__builtin_ctz(t)%3B%5Cn%7D%22%2C%22compiler%22%3A%22=
%2Fusr%2Fbin%2Fg%2B%2B-4.8%22%2C%22options%22%3A%22-O3%20-march%3Dnative%20=
-std%3Dc%2B%2B11%22%7D%5D%7D" target=3D"_blank">http://gcc.godbolt.org/#%7B=
%<wbr>22version%22%3A3%2C%<wbr>22filterAsm%22%3A%7B%22labels%<wbr>22%3Atrue=
%2C%22directives%22%<wbr>3Atrue%2C%22commentOnly%22%<wbr>3Atrue%7D%2C%22com=
pilers%22%<wbr>3A%5B%7B%22source%22%3A%22%<wbr>23include%20%3Ccstring%3E%5C=
n%<wbr>23include%20%3Ccstdlib%3E%5Cn%<wbr>5Cn%5Cnint%20ffs(int%20t)%20%<wbr=
>7B%5Cn%20%20return%20__<wbr>builtin_ffs(t)%3B%5Cn%7D%5Cn%<wbr>5Cnint%20clz=
(int%20t)%20%7B%<wbr>5Cn%20%20return%20__builtin_<wbr>clz(t)%3B%5Cn%7D%5Cn%=
5Cnint%<wbr>20ctz(int%20t)%20%7B%5Cn%20%<wbr>20return%20__builtin_ctz(t)%<w=
br>3B%5Cn%7D%22%2C%22compiler%22%<wbr>3A%22%2Fusr%2Fbin%2Fg%2B%2B-4.<wbr>8%=
22%2C%22options%22%3A%22-O3%<wbr>20-march%3Dnative%20-std%3Dc%<wbr>2B%2B11%=
22%7D%5D%7D</a>
<br>&gt;
<br>&gt; However, I'd still include both for 3 reasons:
<br>&gt; 1) In the future (or maybe even now), one cpu may be able to do ea=
ch in one
<br>&gt; instruction
<br>
<br>Optimizers also get better and can optimize sequences of operations
<br>into a single instruction. x86 already requires this in many cases.
<br>Any time you make this sort of argument, you should check it against
<br>an existing optimizer.
<br>
<br>&gt; 2) Half of the purpose of this library is to be able to write easy=
 to read
<br>&gt; bitwise expressions. So having a separate ffs() and ctz() &nbsp;ma=
kes sense even
<br>&gt; if they are almost the same thing. I want to avoid writing a "RSIC=
" style
<br>&gt; interface.
<br>&gt; 3) Adding a few extra functions which just wrap the others (in thi=
s case its
<br>&gt; just ctz()-1) takes 2 seconds to implement. It costs basically not=
hing.
<br>
<br>In some cases, I agree (e.g. is_pow2), but in others (parity maybe,
<br>sh, sa, pow2_ge, set_bits_le, ffs) I worry that the names won't be
<br>clear enough (so people reading code will have to learn lots of
<br>obscure acronyms) and that we'll present too many ways to do the same
<br>thing and wind up burdening users that way.</blockquote><div>&nbsp;</di=
v><div>Indeed. I also don't like the names sh and sa at all. Perhaps we sho=
uld think of acronyms that are a bit longer for these shifts.</div><div>&nb=
sp;</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: =
0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br>
<br>&gt;&gt; std::align does something like your align_up(). You should exp=
lain why
<br>&gt;&gt; both are needed in your paper.
<br>&gt;
<br>&gt;
<br>&gt; std::align is pretty heavy weight
<br>
<br>If you're saying it has a high runtime cost, please present
<br>measurements. If you're saying it's syntactically heavy, fair enough.
<br></blockquote><div>&nbsp;</div><div>I mean syntactically. std::align is =
extremely specialized. It does a lot of things and has a very specific use =
case. Its amazing for one&nbsp;</div><div>thing and clumsy (possibly ineffi=
cient) for others. It kind of reminds me of realloc().&nbsp;</div><div><br>=
</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8=
ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br>&gt; and has a very specific purpose. A good
<br>&gt; use for both align_up and align_down processing an array of bytes =
with simd
<br>&gt; instructions which require aligned loads and stores. I've used it =
for this
<br>&gt; before.
<br>
<br>That looks like exactly the purpose std::align is useful for. It's
<br>true that align_up and align_down are shorter ways to say the same
<br>thing, but be sure to understand and address the reasons that
<br>std::align takes as many arguments as it does.
<br></blockquote><div>&nbsp;</div><div>Consider we want to use simd for thi=
s:</div><div>void process_bytes(char*b, char*e ) {</div><div>&nbsp; while(b=
 !=3D e) {</div><div>&nbsp; &nbsp; process1(*(b++));<br>&nbsp; }<br>}&nbsp;=
</div><div><br></div><div>//ignoring casts for clarity</div><div>void proce=
ss_bytes(char* b, char* e) {</div><div>&nbsp; char* sb =3D align_up(b, size=
of(simd16));</div><div>&nbsp; char* se =3D align_down(e, sizeof(simd16)):</=
div><div>&nbsp; for(char* p =3D b; p &lt; sb; ++p) {</div><div>&nbsp; &nbsp=
; process1(*p);<br>&nbsp; }</div><div>&nbsp; for(char* p =3D sb; p &lt; se;=
 p+=3Dsizeof(simd16) {</div><div>&nbsp; &nbsp; simd16 s =3D load_aligned_16=
(p);</div><div>&nbsp; &nbsp; process16(s);<br>&nbsp; }</div><div>&nbsp; for=
(char* p =3D se; p &lt; e; ++p) {</div><div>&nbsp; &nbsp; process1(*p);<br>=
&nbsp; }<br>}</div><div><br></div><div>std::align requires the size of the =
aligned portion of this buffer to work correctly. In order to compute that,=
 we would need to use align_up/align_down!</div><div>Its a square function =
trying to fit into a round problem.</div><div><br></div><blockquote class=
=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #cc=
c solid;padding-left: 1ex;">
<br>&gt;&gt; saturating arithmetic is useful but seems like it belongs some=
where
<br>&gt;&gt; else. Are interleave_bits and swap_nibbles general-purpose eno=
ugh to
<br>&gt;&gt; want to put them in the standard library?
<br>&gt;
<br>&gt; I'd like to get an embedded guy in the talk to help with this. If =
its
<br>&gt; important for them I'd like to help them out. Also if a lot of com=
mon cpus
<br>&gt; have instructions for these things we should add them merely on th=
e
<br>&gt; principle of exposing the hardware better.
<br>
<br>What do you mean "if"? You should have a list of hardware instructions
<br>and/or use cases before proposing a function. We try not to add things
<br>to the C++ standard speculatively.
<br>
<br>&gt;&gt; It'd be nice to avoid the constraint on the shl/shr/rotl/rotr =
variants
<br>&gt;&gt; that their argument is non-negative. I assume that's there so =
the
<br>&gt;&gt; compiler can directly emit machine instructions without checki=
ng?
<br>&gt;
<br>&gt;
<br>&gt; You mean on t or s?
<br>
<br>The shift amount.
<br></blockquote><div><br></div><div>This is another tough question. There =
are 2 arguments I can see:</div><div>1) Use signed because the shift amount=
 is a number, not a bit field. Also this is compatible with &lt;&lt; and &g=
t;&gt;.</div><div>2) Use unsigned because the shift amount cannot be negati=
ve.&nbsp;</div><div><br></div><div>Will (2) really catch a lot of bugs? I'm=
 somewhat skeptical here.</div><div>&nbsp;</div><blockquote class=3D"gmail_=
quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;pa=
dding-left: 1ex;">
<br>&gt; I had a variant where s was signed and you could shift left or rig=
ht
<br>&gt; depending on sign. I should add those back in. For the others, yes=
 it should
<br>&gt; be assumed unsigned so the compiler can do it without a check.
<br>
<br>You probably shouldn't overload on signed/unsigned here, especially
<br>since you don't need the extra bit. Another reason to use the stronger
<br>precondition is to allow implementations to warn on incorrect
<br>shift/rotate amounts. On the other hand, there is a clear meaning for
<br>a negative "shift left", so it's unfortunate to add extra traps for
<br>users just because optimizers aren't yet powerful enough to understand
<br>the possible inputs for a particular call. Try to find some compiler
<br>optimization authors when writing this section of your paper.
<br></blockquote><div><br></div><div>I'm rather skeptical that optimizers c=
ould optimize the branch of a signed shift in *all* possible&nbsp;</div><di=
v>cases to avoid the branch, but you're right it would be nice to have a co=
mpiler writers perspective to confirm.</div><div>This is the kind of thing =
which would often be right in the middle of a hot loop so it is important.<=
/div><div><br></div><div>Having both variants also means we can support bot=
h signed and unsigned shifts if they are directly supported by hardware in =
one instrruction</div><div>I'll need to check if this ever happens in pract=
ice though.</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br>Jeffrey
<br></blockquote></div>

<p></p>

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

------=_Part_24_17286951.1381149885087--

.

On Mon, Oct 7, 2013 at 2:57 AM, Jeffrey Yasskin <jyasskin@google.com> wrote:
>> I had a variant where s was signed and you could shift left or right
>> depending on sign. I should add those back in. For the others, yes it should
>> be assumed unsigned so the compiler can do it without a check.
>
> You probably shouldn't overload on signed/unsigned here, especially
> since you don't need the extra bit. Another reason to use the stronger
> precondition is to allow implementations to warn on incorrect
> shift/rotate amounts. On the other hand, there is a clear meaning for
> a negative "shift left", so it's unfortunate to add extra traps for
> users just because optimizers aren't yet powerful enough to understand
> the possible inputs for a particular call. Try to find some compiler
> optimization authors when writing this section of your paper.

The only purpose of using unsigned integers should be getting
representation; whenever you need the value, use signed ones.
Numerics working group is standardizing generic rounding
facilities, and they used `int` for shifting no matter whether the
operations support negative value or not.

On negative shifting, I'm not sure whether there is an instruction
support it.  If it has to be done with a branching, then bitwise
proposal had better leave this as a narrow contract, IMHO.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--

---
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_275_31779460.1381180491554
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Le samedi 5 octobre 2013 19:46:40 UTC+2, fmatth...@gmail.com a =E9crit :
>
> Often we need to do bitwise manipulations such as finding the next power=
=20
> of 2, counting trailing zeros, and so on.
>
> I'd like to propose a new <bitops> header which will contain a set of=20
> constexpr bit manipulation functions.
>

I don't see any mention of std::bitset in this discussion, which seems=20
weird because bitset::count already provides popcount, and there are=20
longstanding requests to add find-like functions (never mind if they are=20
called ctz() or find_last(true)) to it. If you want to add free functions=
=20
that work on the builtin types, I don't mind, but please enhance bitset as=
=20
well.

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

------=_Part_275_31779460.1381180491554
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Le samedi 5 octobre 2013 19:46:40 UTC+2, fmatth...@gmail.c=
om a =E9crit&nbsp;:<blockquote class=3D"gmail_quote" style=3D"margin: 0;mar=
gin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D=
"ltr">Often we need to do bitwise manipulations such as finding the next po=
wer of 2, counting trailing zeros, and so on.<div><br></div><div>I'd like t=
o propose a new &lt;bitops&gt; header which will contain a set of constexpr=
 bit manipulation functions.</div></div></blockquote><div><br>I don't see a=
ny mention of std::bitset in this discussion, which seems weird because bit=
set::count already provides popcount, and there are longstanding requests t=
o add find-like functions (never mind if they are called ctz() or find_last=
(true)) to it. If you want to add free functions that work on the builtin t=
ypes, I don't mind, but please enhance bitset as well.<br></div></div>

<p></p>

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

------=_Part_275_31779460.1381180491554--

.

------=_Part_437_33375638.1381191654691
Content-Type: text/plain; charset=ISO-8859-1



On Monday, October 7, 2013 9:59:25 AM UTC-4, Zhihao Yuan wrote:
>
> On Mon, Oct 7, 2013 at 2:57 AM, Jeffrey Yasskin <jyas...@google.com<javascript:>>
> wrote:
> >> I had a variant where s was signed and you could shift left or right
> >> depending on sign. I should add those back in. For the others, yes it
> should
> >> be assumed unsigned so the compiler can do it without a check.
> >
> > You probably shouldn't overload on signed/unsigned here, especially
> > since you don't need the extra bit. Another reason to use the stronger
> > precondition is to allow implementations to warn on incorrect
> > shift/rotate amounts. On the other hand, there is a clear meaning for
> > a negative "shift left", so it's unfortunate to add extra traps for
> > users just because optimizers aren't yet powerful enough to understand
> > the possible inputs for a particular call. Try to find some compiler
> > optimization authors when writing this section of your paper.
>
> The only purpose of using unsigned integers should be getting
> representation; whenever you need the value, use signed ones.
> Numerics working group is standardizing generic rounding
> facilities, and they used `int` for shifting no matter whether the
> operations support negative value or not.
>

This issue helped me clarify the question or signed vs unsigned ints. I
think I finally understand it now.
Numbers are signed ints and signed arthmetic is math.
Unsigned numbers are bit fields and unsigned arithmetic is just another
logical operation.

Given that, the shift amount is a number, namely the number of bits to
shift by. Therefore it should be an int.
Using an unsigned int to enforce the "must be positive" run time constraint
for a numerical quantity should be considered an anti-pattern and banned.


> On negative shifting, I'm not sure whether there is an instruction
> support it.  If it has to be done with a branching, then bitwise
> proposal had better leave this as a narrow contract, IMHO.
>

I need to do some research to find out. Even if there is on some
architectures, it certainly is not on others. A extra unnecessary branch is
completely unacceptable for a low level interface like this.


>
> --
> Zhihao Yuan, ID lichray
> The best way to predict the future is to invent it.
> ___________________________________________________
> 4BSD -- http://4bsd.biz/
>

--

---
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_437_33375638.1381191654691
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Monday, October 7, 2013 9:59:25 AM UTC-4, Zhiha=
o Yuan wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-le=
ft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On Mon, Oct 7, 20=
13 at 2:57 AM, Jeffrey Yasskin &lt;<a href=3D"javascript:" target=3D"_blank=
" gdf-obfuscated-mailto=3D"VT3tQe4HcDkJ">jyas...@google.com</a>&gt; wrote:
<br>&gt;&gt; I had a variant where s was signed and you could shift left or=
 right
<br>&gt;&gt; depending on sign. I should add those back in. For the others,=
 yes it should
<br>&gt;&gt; be assumed unsigned so the compiler can do it without a check.
<br>&gt;
<br>&gt; You probably shouldn't overload on signed/unsigned here, especiall=
y
<br>&gt; since you don't need the extra bit. Another reason to use the stro=
nger
<br>&gt; precondition is to allow implementations to warn on incorrect
<br>&gt; shift/rotate amounts. On the other hand, there is a clear meaning =
for
<br>&gt; a negative "shift left", so it's unfortunate to add extra traps fo=
r
<br>&gt; users just because optimizers aren't yet powerful enough to unders=
tand
<br>&gt; the possible inputs for a particular call. Try to find some compil=
er
<br>&gt; optimization authors when writing this section of your paper.
<br>
<br>The only purpose of using unsigned integers should be getting
<br>representation; whenever you need the value, use signed ones.
<br>Numerics working group is standardizing generic rounding
<br>facilities, and they used `int` for shifting no matter whether the
<br>operations support negative value or not.
<br></blockquote><div><br></div><div>This issue helped me clarify the quest=
ion or signed vs unsigned ints. I think I finally understand it now.</div><=
div>Numbers are signed ints and signed arthmetic is math.</div><div>Unsigne=
d numbers are bit fields and unsigned arithmetic is just another logical op=
eration.</div><div><br></div><div>Given that, the shift amount is a number,=
 namely the number of bits to shift by. Therefore it should be an int.</div=
><div>Using an unsigned int to enforce the "must be positive" run time cons=
traint for a numerical quantity should be considered an anti-pattern and ba=
nned.</div><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin=
: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br>On negative shifting, I'm not sure whether there is an instruction
<br>support it. &nbsp;If it has to be done with a branching, then bitwise
<br>proposal had better leave this as a narrow contract, IMHO.
<br></blockquote><div><br></div><div>I need to do some research to find out=
.. Even if there is on some architectures, it certainly is not on others. A =
extra unnecessary branch is completely unacceptable for a low level interfa=
ce like this.</div><div>&nbsp;</div><blockquote class=3D"gmail_quote" style=
=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: =
1ex;">
<br>--=20
<br>Zhihao Yuan, ID lichray
<br>The best way to predict the future is to invent it.
<br>______________________________<wbr>_____________________
<br>4BSD -- <a href=3D"http://4bsd.biz/" target=3D"_blank">http://4bsd.biz/=
</a>
<br></blockquote></div>

<p></p>

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

------=_Part_437_33375638.1381191654691--

.

On Mon, Oct 7, 2013 at 8:20 PM,  <fmatthew5876@gmail.com> wrote:
> Using an unsigned int to enforce the "must be positive" run time constraint
> for a numerical quantity should be considered an anti-pattern and banned.

Quote from Herb on GoingNative2013:

  "And, yes (agree with Bjarne), it's unfortunately a mistake that
   the STL and the standard library is we use unsigned indices. "

> I need to do some research to find out. Even if there is on some
> architectures, it certainly is not on others. A extra unnecessary branch is
> completely unacceptable for a low level interface like this.

Thanks for doing these :)

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

--

---
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_444_31668126.1381193775417
Content-Type: text/plain; charset=ISO-8859-1



On Monday, October 7, 2013 8:49:09 PM UTC-4, Zhihao Yuan wrote:
>
> On Mon, Oct 7, 2013 at 8:20 PM,  <fmatth...@gmail.com <javascript:>>
> wrote:
> > Using an unsigned int to enforce the "must be positive" run time
> constraint
> > for a numerical quantity should be considered an anti-pattern and
> banned.
>
> Quote from Herb on GoingNative2013:
>
>   "And, yes (agree with Bjarne), it's unfortunately a mistake that
>    the STL and the standard library is we use unsigned indices. "
>

I saw that and I agree. However, I have an idea for a proposal there too.


>
> > I need to do some research to find out. Even if there is on some
> > architectures, it certainly is not on others. A extra unnecessary branch
> is
> > completely unacceptable for a low level interface like this.
>
> Thanks for doing these :)
>
> --
> Zhihao Yuan, ID lichray
> The best way to predict the future is to invent it.
> ___________________________________________________
> 4BSD -- http://4bsd.biz/
>

--

---
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_444_31668126.1381193775417
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Monday, October 7, 2013 8:49:09 PM UTC-4, Zhiha=
o Yuan wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-le=
ft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On Mon, Oct 7, 20=
13 at 8:20 PM, &nbsp;&lt;<a href=3D"javascript:" target=3D"_blank" gdf-obfu=
scated-mailto=3D"IyOR1YzGDEAJ">fmatth...@gmail.com</a>&gt; wrote:
<br>&gt; Using an unsigned int to enforce the "must be positive" run time c=
onstraint
<br>&gt; for a numerical quantity should be considered an anti-pattern and =
banned.
<br>
<br>Quote from Herb on GoingNative2013:
<br>
<br>&nbsp; "And, yes (agree with Bjarne), it's unfortunately a mistake that
<br>&nbsp; &nbsp;the STL and the standard library is we use unsigned indice=
s. "
<br></blockquote><div>&nbsp;</div><div>I saw that and I agree. However, I h=
ave an idea for a proposal there too.</div><div>&nbsp;</div><blockquote cla=
ss=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #=
ccc solid;padding-left: 1ex;">
<br>&gt; I need to do some research to find out. Even if there is on some
<br>&gt; architectures, it certainly is not on others. A extra unnecessary =
branch is
<br>&gt; completely unacceptable for a low level interface like this.
<br>
<br>Thanks for doing these :)
<br>
<br>--=20
<br>Zhihao Yuan, ID lichray
<br>The best way to predict the future is to invent it.
<br>______________________________<wbr>_____________________
<br>4BSD -- <a href=3D"http://4bsd.biz/" target=3D"_blank">http://4bsd.biz/=
</a>
<br></blockquote></div>

<p></p>

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

------=_Part_444_31668126.1381193775417--

.

------=_Part_944_3986219.1381280774781
Content-Type: text/plain; charset=ISO-8859-1


>
> The only purpose of using unsigned integers should be getting
>> representation; whenever you need the value, use signed ones.
>> Numerics working group is standardizing generic rounding
>> facilities, and they used `int` for shifting no matter whether the
>> operations support negative value or not.
>>
>
> This issue helped me clarify the question or signed vs unsigned ints. I
> think I finally understand it now.
> Numbers are signed ints and signed arthmetic is math.
> Unsigned numbers are bit fields and unsigned arithmetic is just another
> logical operation.
>
> Given that, the shift amount is a number, namely the number of bits to
> shift by. Therefore it should be an int.
> Using an unsigned int to enforce the "must be positive" run time
> constraint for a numerical quantity should be considered an anti-pattern
> and banned.
>

I've never really understood this position. I've always felt that signed
and unsigned integers are both numbers, and std::bitset is a bitfield. I
hold this belief strongly enough that I feel these functions should
probably *only* be defined for std::bitset rather than integer types. It is
the much better abstraction (with no run-time overhead).

--

---
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_944_3986219.1381280774781
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><blockquote class=3D"gmail_quote" style=3D"margin: 0;margi=
n-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"l=
tr"><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;b=
order-left:1px #ccc solid;padding-left:1ex">
The only purpose of using unsigned integers should be getting
<br>representation; whenever you need the value, use signed ones.
<br>Numerics working group is standardizing generic rounding
<br>facilities, and they used `int` for shifting no matter whether the
<br>operations support negative value or not.
<br></blockquote><div><br></div><div>This issue helped me clarify the quest=
ion or signed vs unsigned ints. I think I finally understand it now.</div><=
div>Numbers are signed ints and signed arthmetic is math.</div><div>Unsigne=
d numbers are bit fields and unsigned arithmetic is just another logical op=
eration.</div><div><br></div><div>Given that, the shift amount is a number,=
 namely the number of bits to shift by. Therefore it should be an int.</div=
><div>Using an unsigned int to enforce the "must be positive" run time cons=
traint for a numerical quantity should be considered an anti-pattern and ba=
nned.</div></div></blockquote><div><br>I've never really understood this po=
sition. I've always felt that signed and unsigned integers are both numbers=
, and std::bitset is a bitfield. I hold this belief strongly enough that I =
feel these functions should probably *only* be defined for std::bitset rath=
er than integer types. It is the much better abstraction (with no run-time =
overhead).<br></div></div>

<p></p>

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

------=_Part_944_3986219.1381280774781--

.

------=_Part_1011_6124559.1381285791294
Content-Type: text/plain; charset=ISO-8859-1



On Tuesday, October 8, 2013 9:06:14 PM UTC-4, David Stone wrote:
>
> The only purpose of using unsigned integers should be getting
>>> representation; whenever you need the value, use signed ones.
>>> Numerics working group is standardizing generic rounding
>>> facilities, and they used `int` for shifting no matter whether the
>>> operations support negative value or not.
>>>
>>
>> This issue helped me clarify the question or signed vs unsigned ints. I
>> think I finally understand it now.
>> Numbers are signed ints and signed arthmetic is math.
>> Unsigned numbers are bit fields and unsigned arithmetic is just another
>> logical operation.
>>
>> Given that, the shift amount is a number, namely the number of bits to
>> shift by. Therefore it should be an int.
>> Using an unsigned int to enforce the "must be positive" run time
>> constraint for a numerical quantity should be considered an anti-pattern
>> and banned.
>>
>
> I've never really understood this position. I've always felt that signed
> and unsigned integers are both numbers,
>

The problem is that combining signed and unsigned numbers results in very
subtle and nasty bugs.
The canonical examples being reverse loops and 0xFFFFFFFFU == -1; The
promotion rules are very archaic
and even change depending on the size of the ints on different platform,
resulting in all kinds of fun bugs you
didn't think about.

What benefits does an unsigned number really provide over a signed integer?
An extra bit? If you really need that bit you're probably either doing
bitwise operations (use unsigned, thats what its for) or need really large
numeric values (use a bigger int).
They should be kept separate. Defining their use cases allows one to do
that.


> and std::bitset is a bitfield. I hold this belief strongly enough that I
> feel these functions should probably *only* be defined for std::bitset
> rather than integer types.
>

While supporting bitset is certainly a fine idea, supporting only bitset
doesn't make sense to me at all. Unsigned integers are native types.
Furthermore, the cpu instructions that
implement ctz() and friends are based on registers of specific sizes. I
have no idea how bitset is implemented and it can change anytime I change
platform or compiler.


> It is the much better abstraction
>

Its certainly more general, but I'm not convinced its the end all be all
for for doing bitwise operations.


> (with no run-time overhead).
>

Are you sure about that? Aren't you depending a little too much on the
implementation?


--

---
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_1011_6124559.1381285791294
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Tuesday, October 8, 2013 9:06:14 PM UTC-4, Davi=
d Stone wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-l=
eft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"=
><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;bord=
er-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><blockquote class=
=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc s=
olid;padding-left:1ex">
The only purpose of using unsigned integers should be getting
<br>representation; whenever you need the value, use signed ones.
<br>Numerics working group is standardizing generic rounding
<br>facilities, and they used `int` for shifting no matter whether the
<br>operations support negative value or not.
<br></blockquote><div><br></div><div>This issue helped me clarify the quest=
ion or signed vs unsigned ints. I think I finally understand it now.</div><=
div>Numbers are signed ints and signed arthmetic is math.</div><div>Unsigne=
d numbers are bit fields and unsigned arithmetic is just another logical op=
eration.</div><div><br></div><div>Given that, the shift amount is a number,=
 namely the number of bits to shift by. Therefore it should be an int.</div=
><div>Using an unsigned int to enforce the "must be positive" run time cons=
traint for a numerical quantity should be considered an anti-pattern and ba=
nned.</div></div></blockquote><div><br>I've never really understood this po=
sition. I've always felt that signed and unsigned integers are both numbers=
, </div></div></blockquote><div><br></div><div>The problem is that combinin=
g signed and unsigned numbers results in very subtle and nasty bugs.&nbsp;<=
/div><div>The canonical examples being reverse loops and 0xFFFFFFFFU =3D=3D=
 -1; The promotion rules are very archaic</div><div>and even change dependi=
ng on the size of the ints on different platform, resulting in all kinds of=
 fun bugs you</div><div>didn't think about.</div><div><br></div><div>What b=
enefits does an unsigned number really provide over a signed integer? An ex=
tra bit? If you really need that bit you're probably either doing bitwise o=
perations (use unsigned, thats what its for) or need really large numeric v=
alues (use a bigger int).</div><div>They should be kept separate. Defining =
their use cases allows one to do that.</div><div>&nbsp;<br></div><blockquot=
e class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: =
1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div>and std::bitset is=
 a bitfield. I hold this belief strongly enough that I feel these functions=
 should probably *only* be defined for std::bitset rather than integer type=
s. </div></div></blockquote><div><br></div><div>While supporting bitset is =
certainly a fine idea, supporting only bitset doesn't make sense to me at a=
ll. Unsigned integers are native types. Furthermore, the cpu instructions t=
hat</div><div>implement ctz() and friends are based on registers of specifi=
c sizes. I have no idea how bitset is implemented and it can change anytime=
 I change platform or compiler.</div><div>&nbsp;</div><blockquote class=3D"=
gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc so=
lid;padding-left: 1ex;"><div dir=3D"ltr"><div>It is the much better abstrac=
tion </div></div></blockquote><div><br></div><div>Its certainly more genera=
l, but I'm not convinced its the end all be all for for doing bitwise opera=
tions.</div><div>&nbsp;</div><blockquote class=3D"gmail_quote" style=3D"mar=
gin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><=
div dir=3D"ltr"><div>(with no run-time overhead).<br></div></div></blockquo=
te><div><br></div><div>Are you sure about that? Aren't you depending a litt=
le too much on the implementation?</div><div><br></div><div><br></div></div=
>

<p></p>

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

------=_Part_1011_6124559.1381285791294--

.

------=_Part_873_2447960.1381286914396
Content-Type: text/plain; charset=ISO-8859-1

If I cannot rely on my implementation of std::bitset having no run-time
overhead compared to an unsigned value, I would consider that a serious
missed-optimization opportunity and either change compilers or file it as a
bug, as this is a fairly simple class to get correct in terms of
performance.

I understand that signed / unsigned combinations can lead to tricky
situations, which is why I always turn on the compiler warning for signed /
unsigned mismatch (and why I am writing an integer class that avoids that
unfortunate rule).

I often do need to use unsigned because I do need that extra bit for
numeric storage. This is not when my numbers are very large, but rather,
when they are fairly small. I have some classes that need to hold a value
between (for example) 0 and 200. If I limit myself to signed values the
size requirements for this number just doubled to 2 bytes (assuming
CHAR_BIT == 8). This single byte increase could lead to padding bytes being
added and either way has a measurable impact on the performance of my
application.

--

---
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_873_2447960.1381286914396
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">If I cannot rely on my implementation of std::bitset havin=
g no run-time=20
overhead compared to an unsigned value, I would consider that a serious mis=
sed-optimization=20
opportunity and either change compilers or file it as a bug, as this is a
 fairly simple class to get correct in terms of performance.<br><br>I under=
stand that signed / unsigned combinations can lead to tricky situations, wh=
ich is why I always turn on the compiler warning for signed / unsigned mism=
atch (and why I am writing an integer class that avoids that unfortunate ru=
le).<br><br>I often do need to use unsigned because I do need that extra bi=
t for numeric storage. This is not when my numbers are very large, but rath=
er, when they are fairly small. I have some classes that need to hold a val=
ue between (for example) 0 and 200. If I limit myself to signed values the =
size requirements for this number just doubled to 2 bytes (assuming CHAR_BI=
T =3D=3D 8). This single byte increase could lead to padding bytes being ad=
ded and either way has a measurable impact on the performance of my applica=
tion.<br></div>

<p></p>

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

------=_Part_873_2447960.1381286914396--

.

------=_Part_3220_28679288.1382315139596
Content-Type: text/plain; charset=ISO-8859-1

I put up a new version of the header.

I downloaded a bunch of CPU architecture manuals and took a look at whats
out there in a the wild. (Some notes also in git, intstructions.txt)
I think one of the major goals of this proposal should be to expose more
instructions commonly found in modern hardware.

First for ctz, it looks like we need ctz() and ctznz(). Many processors can
do ctz(), but on intel the bsf instruction has undefined behavior if the
value is 0. Every other processor just returns sizeof(x) * CHAR_BIT.
Therefore we have 2 versions of ctz(), one that is defined for 0, and one
that is not.
Similarly for clz().

I'm playing with the idea of a generic templated binary_reverse which can
do all manner of bit and byte reversal. There are also helpers for
reversing bits, nibbles, bytes, and words.
There are many different kinds of instructions available for different
variations of these on different machines. ARMv8 has a interesting set of
byte reversal instructions.

Also, I prefer to call it reverse bytes instead of byte swap. The name byte
swap makes sense for a 16 bit value, and I believe this is where the term
came from (SWAB instruction from PDP-11 maybe). it doesn't make much sense
for N > 2 byte values.

Saturated add/subtract is directly supported on ARMv8 and useful for DSP
work. So I'm going to keep that in.

I couldn't find any architecture which supports a signed shift, where the
direction of the shift depends on the sign of the value. I've decided to
forego the sh() and sa() examples from the last revision.
I've also renamed them to shll(), shlr(), shal(), shar() which I think is
more descriptive.

Finally, I took out all of the template =delete/enable_if cruft for
constraining conversions. That can be discussed later in the actual paper.
I think it just clutters the header.
I'm actually not sure if its worth disabling conversions for ctz() and some
of the others. Will it really cause problems to call ctz() or popcount() on
a signed value?
Can anyone think of a concrete example where this will make too it easy to
write incorrect code?

Interestingly this set of operations has very good support for ARMv8
instructions, which I think is a pretty cool selling point to the proposal.
Intel also has the new BMI1 and BMI2 instructions which I'm still looking
at.

I'm also thinking maybe all of this should be just added to <cmath>, but I
suppose thats more a discussion point for the numerics group when the
actual proposal is written.

--

---
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_3220_28679288.1382315139596
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I put up a new version of the header.<div><br></div><div>I=
 downloaded a bunch of CPU architecture manuals and took a look at whats ou=
t there in a the wild. (Some notes also in git, intstructions.txt)</div><di=
v>I think one of the major goals of this proposal should be to expose more =
instructions commonly found in modern hardware.</div><div><br></div><div>Fi=
rst for ctz, it looks like we need ctz() and ctznz(). Many processors can d=
o ctz(), but on intel the bsf instruction has undefined behavior if the val=
ue is 0. Every other processor just returns sizeof(x) * CHAR_BIT.</div><div=
>Therefore we have 2 versions of ctz(), one that is defined for 0, and one =
that is not.</div><div>Similarly for clz().</div><div><br></div><div>I'm pl=
aying with the idea of a generic templated binary_reverse which can do all =
manner of bit and byte reversal. There are also helpers for reversing bits,=
 nibbles, bytes, and words.</div><div>There are many different kinds of ins=
tructions available for different variations of these on different machines=
.. ARMv8 has a interesting set of byte reversal instructions.</div><div><br>=
Also, I prefer to call it reverse bytes instead of byte swap. The name byte=
 swap makes sense for a 16 bit value, and I believe this is where the term =
came from (SWAB instruction from PDP-11 maybe). it doesn't make much sense =
for N &gt; 2 byte values.</div><div><br></div><div>Saturated add/subtract i=
s directly supported on ARMv8 and useful for DSP work. So I'm going to keep=
 that in.</div><div><br></div><div>I couldn't find any architecture which s=
upports a signed shift, where the direction of the shift depends on the sig=
n of the value. I've decided to forego the sh() and sa() examples from the =
last revision.</div><div>I've also renamed them to shll(), shlr(), shal(), =
shar() which I think is more descriptive.</div><div><br></div><div>Finally,=
 I took out all of the template =3Ddelete/enable_if cruft for constraining =
conversions. That can be discussed later in the actual paper. I think it ju=
st clutters the header.</div><div>I'm actually not sure if its worth disabl=
ing conversions for ctz() and some of the others. Will it really cause prob=
lems to call ctz() or popcount() on a signed value?</div><div>Can anyone th=
ink of a concrete example where this will make too it easy to write incorre=
ct code?</div><div><br></div><div>Interestingly this set of operations has =
very good support for ARMv8 instructions, which I think is a pretty cool se=
lling point to the proposal. Intel also has the new BMI1 and BMI2 instructi=
ons which I'm still looking at.</div><div><br></div><div>I'm also thinking =
maybe all of this should be just added to &lt;cmath&gt;, but I suppose that=
s more a discussion point for the numerics group when the actual proposal i=
s written.</div><div><br></div></div>

<p></p>

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

------=_Part_3220_28679288.1382315139596--

.

------=_Part_1524_14179087.1382316123004
Content-Type: text/plain; charset=ISO-8859-1

Also with regards to ffs() and fls().

I'm not sure I see the point of ffs(). Maybe it was just invented because
of the undefined if x == 0 problem traditionally associated with ctz()?
A variant of fls() might be a useful helper to include since its kind of
clumsy writing sizeof(x) * CHAR_BIT - clz(x).

On Sunday, October 20, 2013 8:25:39 PM UTC-4, fmatth...@gmail.com wrote:
>
> I put up a new version of the header.
>
> I downloaded a bunch of CPU architecture manuals and took a look at whats
> out there in a the wild. (Some notes also in git, intstructions.txt)
> I think one of the major goals of this proposal should be to expose more
> instructions commonly found in modern hardware.
>
> First for ctz, it looks like we need ctz() and ctznz(). Many processors
> can do ctz(), but on intel the bsf instruction has undefined behavior if
> the value is 0. Every other processor just returns sizeof(x) * CHAR_BIT.
> Therefore we have 2 versions of ctz(), one that is defined for 0, and one
> that is not.
> Similarly for clz().
>
> I'm playing with the idea of a generic templated binary_reverse which can
> do all manner of bit and byte reversal. There are also helpers for
> reversing bits, nibbles, bytes, and words.
> There are many different kinds of instructions available for different
> variations of these on different machines. ARMv8 has a interesting set of
> byte reversal instructions.
>
> Also, I prefer to call it reverse bytes instead of byte swap. The name
> byte swap makes sense for a 16 bit value, and I believe this is where the
> term came from (SWAB instruction from PDP-11 maybe). it doesn't make much
> sense for N > 2 byte values.
>
> Saturated add/subtract is directly supported on ARMv8 and useful for DSP
> work. So I'm going to keep that in.
>
> I couldn't find any architecture which supports a signed shift, where the
> direction of the shift depends on the sign of the value. I've decided to
> forego the sh() and sa() examples from the last revision.
> I've also renamed them to shll(), shlr(), shal(), shar() which I think is
> more descriptive.
>
> Finally, I took out all of the template =delete/enable_if cruft for
> constraining conversions. That can be discussed later in the actual paper.
> I think it just clutters the header.
> I'm actually not sure if its worth disabling conversions for ctz() and
> some of the others. Will it really cause problems to call ctz() or
> popcount() on a signed value?
> Can anyone think of a concrete example where this will make too it easy to
> write incorrect code?
>
> Interestingly this set of operations has very good support for ARMv8
> instructions, which I think is a pretty cool selling point to the proposal.
> Intel also has the new BMI1 and BMI2 instructions which I'm still looking
> at.
>
> I'm also thinking maybe all of this should be just added to <cmath>, but I
> suppose thats more a discussion point for the numerics group when the
> actual proposal is written.
>
>

--

---
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_1524_14179087.1382316123004
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Also with regards to ffs() and fls().<div><br></div><div>I=
'm not sure I see the point of ffs(). Maybe it was just invented because of=
 the undefined if x =3D=3D 0 problem traditionally associated with ctz()?</=
div><div>A variant of fls() might be a useful helper to include since its k=
ind of clumsy writing sizeof(x) * CHAR_BIT - clz(x).<br><br>On Sunday, Octo=
ber 20, 2013 8:25:39 PM UTC-4, fmatth...@gmail.com wrote:<blockquote class=
=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #cc=
c solid;padding-left: 1ex;"><div dir=3D"ltr">I put up a new version of the =
header.<div><br></div><div>I downloaded a bunch of CPU architecture manuals=
 and took a look at whats out there in a the wild. (Some notes also in git,=
 intstructions.txt)</div><div>I think one of the major goals of this propos=
al should be to expose more instructions commonly found in modern hardware.=
</div><div><br></div><div>First for ctz, it looks like we need ctz() and ct=
znz(). Many processors can do ctz(), but on intel the bsf instruction has u=
ndefined behavior if the value is 0. Every other processor just returns siz=
eof(x) * CHAR_BIT.</div><div>Therefore we have 2 versions of ctz(), one tha=
t is defined for 0, and one that is not.</div><div>Similarly for clz().</di=
v><div><br></div><div>I'm playing with the idea of a generic templated bina=
ry_reverse which can do all manner of bit and byte reversal. There are also=
 helpers for reversing bits, nibbles, bytes, and words.</div><div>There are=
 many different kinds of instructions available for different variations of=
 these on different machines. ARMv8 has a interesting set of byte reversal =
instructions.</div><div><br>Also, I prefer to call it reverse bytes instead=
 of byte swap. The name byte swap makes sense for a 16 bit value, and I bel=
ieve this is where the term came from (SWAB instruction from PDP-11 maybe).=
 it doesn't make much sense for N &gt; 2 byte values.</div><div><br></div><=
div>Saturated add/subtract is directly supported on ARMv8 and useful for DS=
P work. So I'm going to keep that in.</div><div><br></div><div>I couldn't f=
ind any architecture which supports a signed shift, where the direction of =
the shift depends on the sign of the value. I've decided to forego the sh()=
 and sa() examples from the last revision.</div><div>I've also renamed them=
 to shll(), shlr(), shal(), shar() which I think is more descriptive.</div>=
<div><br></div><div>Finally, I took out all of the template =3Ddelete/enabl=
e_if cruft for constraining conversions. That can be discussed later in the=
 actual paper. I think it just clutters the header.</div><div>I'm actually =
not sure if its worth disabling conversions for ctz() and some of the other=
s. Will it really cause problems to call ctz() or popcount() on a signed va=
lue?</div><div>Can anyone think of a concrete example where this will make =
too it easy to write incorrect code?</div><div><br></div><div>Interestingly=
 this set of operations has very good support for ARMv8 instructions, which=
 I think is a pretty cool selling point to the proposal. Intel also has the=
 new BMI1 and BMI2 instructions which I'm still looking at.</div><div><br><=
/div><div>I'm also thinking maybe all of this should be just added to &lt;c=
math&gt;, but I suppose thats more a discussion point for the numerics grou=
p when the actual proposal is written.</div><div><br></div></div></blockquo=
te></div></div>

<p></p>

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

------=_Part_1524_14179087.1382316123004--

.

--nextPart4938258.Bk2cS6oWG2
Content-Transfer-Encoding: 7Bit
Content-Type: text/plain; charset="us-ascii"

On domingo, 20 de outubro de 2013 17:25:39, fmatthew5876@gmail.com wrote:
> First for ctz, it looks like we need ctz() and ctznz(). Many processors can
> do ctz(), but on intel the bsf instruction has undefined behavior if the
> value is 0. Every other processor just returns sizeof(x) * CHAR_BIT.
> Therefore we have 2 versions of ctz(), one that is defined for 0, and one
> that is not.

I think you're misreading the manual. It says the register has an undefined
value at the end, not that the instruction has undefined behaviour. The
instruction has a defined behaviour: it sets the zero flag and may or may not
touch the input register.

It's just that you're going to need two instructions instead of just one:
asm("bsf %1, %0\n"
 "cmovz %2, %0" :
 "=r" (result) :
 "r" (input), "r" (sizeof(input) * CHAR_BIT));

Besides, if this is implemented as a compiler built-in (which we'd recommend),
the compiler may know that the value is non-zero from prior optimisations and
remove the conditional move.

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

--nextPart4938258.Bk2cS6oWG2
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: This is a digitally signed message part.
Content-Transfer-Encoding: 7Bit

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.19 (GNU/Linux)

iD8DBQBSZK8SM/XwBW70U1gRAneYAJ4pUgl0h2XVYhEoksNUwXpvydVCdQCgtutn
hrsstz/nntDGZ6p2CA6Ezpg=
=jBYb
-----END PGP SIGNATURE-----

--nextPart4938258.Bk2cS6oWG2--


.

------=_Part_3518_10189936.1382361430769
Content-Type: text/plain; charset=ISO-8859-1

Should we rely on compiler optimizations

On Monday, October 21, 2013 12:35:22 AM UTC-4, Thiago Macieira wrote:
>
> On domingo, 20 de outubro de 2013 17:25:39, fmatth...@gmail.com<javascript:>wrote:
> > First for ctz, it looks like we need ctz() and ctznz(). Many processors
> can
> > do ctz(), but on intel the bsf instruction has undefined behavior if the
> > value is 0. Every other processor just returns sizeof(x) * CHAR_BIT.
> > Therefore we have 2 versions of ctz(), one that is defined for 0, and
> one
> > that is not.
>
> I think you're misreading the manual. It says the register has an
> undefined
> value at the end, not that the instruction has undefined behaviour. The


That is what I meant to say, used the wrong words.


>
> instruction has a defined behaviour: it sets the zero flag and may or may
> not
> touch the input register.
>
> It's just that you're going to need two instructions instead of just one:
> asm("bsf %1, %0\n"
>         "cmovz %2, %0" :
>         "=r" (result) :
>         "r" (input), "r" (sizeof(input) * CHAR_BIT));
>
> Besides, if this is implemented as a compiler built-in (which we'd
> recommend),


I'd hope that all of these are implemented as compiler instrinsics /
built-ins. I will be recommending that in the paper.


>
> the compiler may know that the value is non-zero from prior optimisations
> and
> remove the conditional move.
>

on gcc, __builtin_ctz() is only defined for non-zero inputs while
__builtin_ffs() is defined for all inputs. That's their implementation of
ctz() and ctznz() I suppose.

If we want to rely on compiler optimizations and forego ctznz(), I'd want
to be absolutely sure there is never a case where a gcc
user would reach for the __builin_ctz() instead of the standard std::ctz()
because the optimizer is unable to determine the != 0 precondition.


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

--

---
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_3518_10189936.1382361430769
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Should we rely on compiler optimizations<br><br>On Monday,=
 October 21, 2013 12:35:22 AM UTC-4, Thiago Macieira wrote:<blockquote clas=
s=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #c=
cc solid;padding-left: 1ex;">On domingo, 20 de outubro de 2013 17:25:39, <a=
 href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"ycMNTEcMsP=
cJ">fmatth...@gmail.com</a> wrote:
<br>&gt; First for ctz, it looks like we need ctz() and ctznz(). Many proce=
ssors can=20
<br>&gt; do ctz(), but on intel the bsf instruction has undefined behavior =
if the
<br>&gt; value is 0. Every other processor just returns sizeof(x) * CHAR_BI=
T.
<br>&gt; Therefore we have 2 versions of ctz(), one that is defined for 0, =
and one
<br>&gt; that is not.
<br>
<br>I think you're misreading the manual. It says the register has an undef=
ined=20
<br>value at the end, not that the instruction has undefined behaviour. The=
 </blockquote><div><br></div><div>That is what I meant to say, used the wro=
ng words.</div><div>&nbsp;</div><blockquote class=3D"gmail_quote" style=3D"=
margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;=
">
<br>instruction has a defined behaviour: it sets the zero flag and may or m=
ay not=20
<br>touch the input register.
<br>
<br>It's just that you're going to need two instructions instead of just on=
e:
<br>asm("bsf %1, %0\n"
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"cmovz %2, %0" :
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"=3Dr" (result) :
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"r" (input), "r" (sizeo=
f(input) * CHAR_BIT));
<br>
<br>Besides, if this is implemented as a compiler built-in (which we'd reco=
mmend), </blockquote><div><br></div><div>I'd hope that all of these are imp=
lemented as compiler instrinsics / built-ins. I will be recommending that i=
n the paper.</div><div>&nbsp;</div><blockquote class=3D"gmail_quote" style=
=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: =
1ex;">
<br>the compiler may know that the value is non-zero from prior optimisatio=
ns and=20
<br>remove the conditional move.
<br></blockquote><div><br></div><div>on gcc, __builtin_ctz() is only define=
d for non-zero inputs while __builtin_ffs() is defined for all inputs. That=
's their implementation of ctz() and ctznz() I suppose.</div><div><br></div=
><div>If we want to rely on compiler optimizations and forego ctznz(), I'd =
want to be absolutely sure there is never a case where a gcc&nbsp;</div><di=
v>user would reach for the __builin_ctz() instead of the standard std::ctz(=
) because the optimizer is unable to determine the !=3D 0 precondition.</di=
v><div>&nbsp;</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;mar=
gin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<br>--=20
<br>Thiago Macieira - thiago (AT) <a href=3D"http://macieira.info" target=
=3D"_blank">macieira.info</a> - thiago (AT) <a href=3D"http://kde.org" targ=
et=3D"_blank">kde.org</a>
<br>&nbsp; &nbsp;Software Architect - Intel Open Source Technology Center
<br>&nbsp; &nbsp; &nbsp; PGP/GPG: 0x6EF45358; fingerprint:
<br>&nbsp; &nbsp; &nbsp; E067 918B B660 DBD1 105C &nbsp;966C 33F5 F005 6EF4=
 5358
<br></blockquote></div>

<p></p>

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

------=_Part_3518_10189936.1382361430769--

.

On segunda-feira, 21 de outubro de 2013 06:17:10, fmatthew5876@gmail.com
wrote:
> If we want to rely on compiler optimizations and forego ctznz(), I'd want to
> be absolutely sure there is never a case where a gcc  user would reach for
> the __builin_ctz() instead of the standard std::ctz() because the optimizer
> is unable to determine the != 0 precondition.

We don't want to rely on optimisations.

We simply declare what the behaviour should be and that's all. The compiler
writers will develop their compiler so that they produce the best code to
match the behaviour we define.

I don't think we need both ctz and ctznz.

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

--

---
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_4825_20187002.1383624284703
Content-Type: text/plain; charset=ISO-8859-1

Another big update to the header in git.

https://github.com/fmatthew5876/stdcxx/blob/master/bitops/include/bitops.hh

I've settled on a naming scheme that is still short but hopefully not as
cryptic.

At this point I'm ready to start writing the actual proposal. I think it's
going to be a rather large one.

I think I'd like to enable these for signed and unsigned types. I don't see
anything dangerous about counting the 1 bits of a signed integer. I'm
willing to be persuaded otherwise but I think I will wait until the paper
is written and being debated by the numerics working group to revisit that
point again.

I'm leaving out bitset. This might be a disappointment many people but I
want to focus on selecting the right collection of bit manipulation
primitives for standardization with their semantics and names. Once that
hard work is done, a simple followup proposal for bitset can be written.

Some specifics on the different groups of methods:

Explicit Shifts:
lshr - this is actually useful for signed types. If you want to logically
right shift a signed number this is much nicer than an ugly cast combined
with operator>>. Also symmetry.
lshl, lsha - Only here for symmetry
rsha - Required, since signed >> is implementation defined there is no
portable arithmetic right shift.
lrotl, lrotr - Excited about these, they have been around as native
instructions forever and have never been directly exposed to the programmer.

Zero and One Counting:
count_tzb / count_lzb - Need for these is well known and has already been
discussed.
I decided to drop ctznz(), I think it just pollutes the library and its
really only an artifact from intel's bsf instruction. Every other machine I
surveyed has defined semantics for zero (and the same semantics, namely
return the number of bits). Even newer intel cpus have the much better
tzcnt and lzcnt instructions. Finally, many use cases with ctz() also
involve a zero test, making it very easy for the compiler to optimize out
the cmov for the bsf/bsr case.
count_l1b - Counting sign bits, native instruction for many machines and
also available on gcc.
count_t1b - Included for symmetry. I don't know of any applications of this.
popcount - Already discussed, everyone wants this
parity - Optimal implementation depends on if popcount is a native
instruction or not.

Rightmost bit manipulation:
There is a lot here and I'm not going to go though all of them.
I took most of these from hacker's delight. Several of them have native
instructions in AMD's TBM (trailing bit manipulation) extensions.
This is the set I am most unsure about. I have used some before like
reset_ls1b() but I'm not sure of the usefulness of all of the others.
Also, while many of these have native instructions on AMD, a simple test
with gcc 4.8 with -mbmi -mtbm (you can do it yourself,
http://gcc.godbolt.org) shows that the compiler can
detect all of these and substitute the right TBM instruction when you write
their logical equivalents. Also I can't find anything on the motivation or
use cases behind the AMD TBM instructions from google.
Many of these have non-obvious implementations, so having them in the
standard library makes it easy to grab one when you need it without having
to google or rediscover it on your own.

Bit/Byte Reversal:
I like these 2 a lot and I think its a good generic interface which can
cover all cases (including rare things like nibble swapping and pdp endian
conversion). There are many native instructions for different permutations
of revbits/revbytes.
Question for compiler devs: Can we effectively substitute native
instructions when bits_per_block and blocks_per_group are normal function
arguments instead of template arguments?

Saturated Math:
Native support on ARM gives this more credibility. Also its generally a
useful thing to have a costs almost nothing to implement. Probably belongs
in <cmath>.

Single Bit Manipuation:
These are just usability wrappers for simple operations. I put them in for
now but I am not attached to them.

Range of bits manipulation:
These are useful in some situations. I couldn't get gcc 4.8 to emit a BZHI
instruction, but I can't imagine reset_bitsge() implementation == BZHI is
hard for an optimizer to solve.

Power of 2:
ispow2/ispow2oz - As mentioned before, optimal implementation depends on
the implementation of popcount(). Also, power of 2 testing is so useful and
general it belongs in the standard just for that reason alone.
ceilp2/floorp2 - One application I've used many times is for growable
containers whose size must be a power of 2. For example a circular queue.
If the queue size is a power of 2, you can compute the circular offset with
a cheap & instead of an expensive %.

Alignment:
I've mentioned these already. I'm tired of writing these functions in every
one of my own code libraries. They are very important for memory allocators
and aligned simd loads. std::align is too specifc, it kind of reminds me of
realloc().

Others:
pbits_deposit/pbits_extract: I took these because they are implemented as
single instructions intel BMI2 and also mentioned as being useful here:
http://chessprogramming.wikispaces.com/BMI2
snoob: This was from hackers delight. This one I don't know if its actually
really useful to a lot of people. Will not be surprised if this gets axed.


So to summarize, there is a lot here. For the first draft I've opted to be
more inclusive than exclusive. That way we can discuss each of these and we
can remove the ones that don't seem worth standardizing.

Feedback and criticism is most welcome.

If anyone is interested in contributing, I could use help in the following
(in order in terms for importance):
* Come up with at least one application for each proposed function.
* Double check the reference implementation in git for bugs. I'm sure there
are plenty as I haven't even had time to test them yet.
* Write unit tests for the reference implementation. I plan to do this
myself eventually. The tests should ensure that all sizes (8, 16, 32, 64)
and signed vs unsigned work correctly. Google test framework is preferred.
I'l write a unit test in a day or 2 to setup the testing framework.
* Propose more bitwise functions if you think I missed one that is really
important
* Debate or propose new names for any of the functions
* List native instructions for any of these for any machine that I've
missed. I think I've got all the most important ones already so this is low
priority, but more won't hurt.

Contributors of course will get their name in the credits of the paper :)


On Monday, October 21, 2013 11:09:50 AM UTC-4, Thiago Macieira wrote:
>
> On segunda-feira, 21 de outubro de 2013 06:17:10, fmatth...@gmail.com<javascript:>
> wrote:
> > If we want to rely on compiler optimizations and forego ctznz(), I'd
> want to
> > be absolutely sure there is never a case where a gcc  user would reach
> for
> > the __builin_ctz() instead of the standard std::ctz() because the
> optimizer
> > is unable to determine the != 0 precondition.
>
> We don't want to rely on optimisations.
>
> We simply declare what the behaviour should be and that's all. The
> compiler
> writers will develop their compiler so that they produce the best code to
> match the behaviour we define.
>
> I don't think we need both ctz and ctznz.
>
> --
> 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
>
>

--

---
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_4825_20187002.1383624284703
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Another big update to the header in git.<div><br></div><di=
v><a href=3D"https://github.com/fmatthew5876/stdcxx/blob/master/bitops/incl=
ude/bitops.hh">https://github.com/fmatthew5876/stdcxx/blob/master/bitops/in=
clude/bitops.hh</a></div><div><br></div><div>I've settled on a naming schem=
e that is still short but hopefully not as cryptic.</div><div><br></div><di=
v>At this point I'm ready to start writing the actual proposal. I think it'=
s going to be a rather large one.</div><div><br></div><div>I think I'd like=
 to enable these for signed and unsigned types. I don't see anything danger=
ous about counting the 1 bits of a signed integer. I'm willing to be persua=
ded otherwise but I think I will wait until the paper is written and being =
debated by the numerics working group to revisit that point again.</div><di=
v><br></div><div>I'm leaving out bitset. This might be a disappointment man=
y people but I want to focus on selecting the right collection of bit manip=
ulation primitives for standardization with their semantics and names. Once=
 that hard work is done, a simple followup proposal for bitset can be writt=
en.</div><div><br></div><div>Some specifics on the different groups of meth=
ods:</div><div><br></div><div>Explicit Shifts:</div><div>lshr - this is act=
ually useful for signed types. If you want to logically right shift a signe=
d number this is much nicer than an ugly cast combined with operator&gt;&gt=
;. Also symmetry.</div><div>lshl, lsha - Only here for symmetry</div><div>r=
sha - Required, since signed &gt;&gt; is implementation defined there is no=
 portable arithmetic right shift.</div><div>lrotl, lrotr - Excited about th=
ese, they have been around as native instructions forever and have never be=
en directly exposed to the programmer.</div><div><br></div><div>Zero and On=
e Counting:</div><div>count_tzb / count_lzb - Need for these is well known =
and has already been discussed.</div><div>I decided to drop ctznz(), I thin=
k it just pollutes the library and its really only an artifact from intel's=
 bsf instruction. Every other machine I surveyed has defined semantics for =
zero (and the same semantics, namely return the number of bits). Even newer=
 intel cpus have the much better tzcnt and lzcnt instructions. Finally, man=
y use cases with ctz() also involve a zero test, making it very easy for th=
e compiler to optimize out the cmov for the bsf/bsr case.</div><div>count_l=
1b - Counting sign bits, native instruction for many machines and also avai=
lable on gcc.</div><div>count_t1b - Included for symmetry. I don't know of =
any applications of this.</div><div>popcount - Already discussed, everyone =
wants this</div><div>parity - Optimal implementation depends on if popcount=
 is a native instruction or not.</div><div><br></div><div>Rightmost bit man=
ipulation:</div><div>There is a lot here and I'm not going to go though all=
 of them.</div><div>I took most of these from hacker's delight. Several of =
them have native instructions in AMD's TBM (trailing bit manipulation) exte=
nsions.</div><div>This is the set I am most unsure about. I have used some =
before like reset_ls1b() but I'm not sure of the usefulness of all of the o=
thers.</div><div>Also, while many of these have native instructions on AMD,=
 a simple test with gcc 4.8 with -mbmi -mtbm (you can do it yourself, http:=
//gcc.godbolt.org) shows that the compiler can&nbsp;</div><div>detect all o=
f these and substitute the right TBM instruction when you write their logic=
al equivalents. Also I can't find anything on the motivation or use cases b=
ehind the AMD TBM instructions from google.</div><div>Many of these have no=
n-obvious implementations, so having them in the standard library makes it =
easy to grab one when you need it without having to google or rediscover it=
 on your own.</div><div><br></div><div>Bit/Byte Reversal:<br>I like these 2=
 a lot and I think its a good generic interface which can cover all cases (=
including rare things like nibble swapping and pdp endian conversion). Ther=
e are many native instructions for different permutations of revbits/revbyt=
es.</div><div>Question for compiler devs: Can we effectively substitute nat=
ive instructions when bits_per_block and blocks_per_group are normal functi=
on arguments instead of template arguments?</div><div><br></div><div>Satura=
ted Math:<br>Native support on ARM gives this more credibility. Also its ge=
nerally a useful thing to have a costs almost nothing to implement. Probabl=
y belongs in &lt;cmath&gt;.</div><div><br></div><div>Single Bit Manipuation=
:<br>These are just usability wrappers for simple operations. I put them in=
 for now but I am not attached to them.</div><div><br></div><div>Range of b=
its manipulation:</div><div>These are useful in some situations. I couldn't=
 get gcc 4.8 to emit a BZHI instruction, but I can't imagine reset_bitsge()=
 implementation =3D=3D BZHI is hard for an optimizer to solve.</div><div><b=
r></div><div>Power of 2:</div><div>ispow2/ispow2oz - As mentioned before, o=
ptimal implementation depends on the implementation of popcount(). Also, po=
wer of 2 testing is so useful and general it belongs in the standard just f=
or that reason alone.</div><div>ceilp2/floorp2 - One application I've used =
many times is for growable containers whose size must be a power of 2. For =
example a circular queue. If the queue size is a power of 2, you can comput=
e the circular offset with a cheap &amp; instead of an expensive %.</div><d=
iv><br></div><div>Alignment:</div><div>I've mentioned these already. I'm ti=
red of writing these functions in every one of my own code libraries. They =
are very important for memory allocators and aligned simd loads. std::align=
 is too specifc, it kind of reminds me of realloc().</div><div><br></div><d=
iv>Others:</div><div>pbits_deposit/pbits_extract: I took these because they=
 are implemented as single instructions intel BMI2 and also mentioned as be=
ing useful here:&nbsp;<a href=3D"http://chessprogramming.wikispaces.com/BMI=
2">http://chessprogramming.wikispaces.com/BMI2</a></div><div>snoob: This wa=
s from hackers delight. This one I don't know if its actually really useful=
 to a lot of people. Will not be surprised if this gets axed.</div><div><br=
></div><div><br></div><div>So to summarize, there is a lot here. For the fi=
rst draft I've opted to be more inclusive than exclusive. That way we can d=
iscuss each of these and we can remove the ones that don't seem worth stand=
ardizing.</div><div><br></div><div>Feedback and criticism is most welcome.<=
/div><div><br></div><div>If anyone is interested in contributing, I could u=
se help in the following (in order in terms for importance):</div><div>* Co=
me up with at least one application for each proposed function.</div><div><=
div>* Double check the reference implementation in git for bugs. I'm sure t=
here are plenty as I haven't even had time to test them yet.</div><div>* Wr=
ite unit tests for the reference implementation. I plan to do this myself e=
ventually. The tests should ensure that all sizes (8, 16, 32, 64) and signe=
d vs unsigned work correctly. Google test framework is preferred. I'l write=
 a unit test in a day or 2 to setup the testing framework.</div></div><div>=
* Propose more bitwise functions if you think I missed one that is really i=
mportant</div><div>* Debate or propose new names for any of the functions</=
div><div>* List native instructions for any of these for any machine that I=
've missed. I think I've got all the most important ones already so this is=
 low priority, but more won't hurt.<br></div><div><br></div><div>Contributo=
rs of course will get their name in the credits of the paper :)</div><div><=
br><br>On Monday, October 21, 2013 11:09:50 AM UTC-4, Thiago Macieira wrote=
:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;bo=
rder-left: 1px #ccc solid;padding-left: 1ex;">On segunda-feira, 21 de outub=
ro de 2013 06:17:10, <a href=3D"javascript:" target=3D"_blank" gdf-obfuscat=
ed-mailto=3D"LE66hoUvwhUJ">fmatth...@gmail.com</a>=20
<br>wrote:
<br>&gt; If we want to rely on compiler optimizations and forego ctznz(), I=
'd want to
<br>&gt; be absolutely sure there is never a case where a gcc &nbsp;user wo=
uld reach for
<br>&gt; the __builin_ctz() instead of the standard std::ctz() because the =
optimizer
<br>&gt; is unable to determine the !=3D 0 precondition.=20
<br>
<br>We don't want to rely on optimisations.
<br>
<br>We simply declare what the behaviour should be and that's all. The comp=
iler=20
<br>writers will develop their compiler so that they produce the best code =
to=20
<br>match the behaviour we define.
<br>
<br>I don't think we need both ctz and ctznz.
<br>
<br>--=20
<br>Thiago Macieira - thiago (AT) <a href=3D"http://macieira.info" target=
=3D"_blank">macieira.info</a> - thiago (AT) <a href=3D"http://kde.org" targ=
et=3D"_blank">kde.org</a>
<br>&nbsp; &nbsp;Software Architect - Intel Open Source Technology Center
<br>&nbsp; &nbsp; &nbsp; PGP/GPG: 0x6EF45358; fingerprint:
<br>&nbsp; &nbsp; &nbsp; E067 918B B660 DBD1 105C &nbsp;966C 33F5 F005 6EF4=
 5358
<br>
<br></blockquote></div></div>

<p></p>

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

------=_Part_4825_20187002.1383624284703--

.

------=_Part_161_13099228.1384027092292
Content-Type: text/plain; charset=ISO-8859-1

I wonder whether we could include something like bit streams or bit queues,
which the following functionality:
add(int n_bits, Integral x)
pop(int n_bits, Integral& x)

They are convenient for handling various compression algorithms and the
like.
s.add(4, 0x1011)
s.pop(2, x); // x => 0x10
s.pop(1, x1); // x1 => 1
s.pop(1,x2); // x2 => 1




--

---
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_161_13099228.1384027092292
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>I wonder whether we could include something like bit =
streams or bit queues, which the following functionality:</div><div>add(int=
 n_bits, Integral x)</div><div>pop(int n_bits, Integral&amp; x)</div><div>&=
nbsp;</div><div>They are convenient for handling various compression algori=
thms and the like.</div><div>s.add(4, 0x1011)</div><div>s.pop(2, x); // x =
=3D&gt; 0x10</div><div>s.pop(1, x1); // x1 =3D&gt; 1</div><div>s.pop(1,x2);=
 // x2 =3D&gt; 1</div><div><br><br>&nbsp;</div></div>

<p></p>

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

------=_Part_161_13099228.1384027092292--

.

------=_Part_308_8040612.1384029313809
Content-Type: text/plain; charset=ISO-8859-1

I wonder whether we could include something like bit streams or bit queues,
which the following functionality:
add(int n_bits, Integral x)
pop(int n_bits, Integral& x)

They are convenient for handling various compression algorithms and the
like.
s.add(4, 0xB)
s.pop(2, x); // x => 2
s.pop(1, x1); // x1 => 1
s.pop(1,x2); // x2 => 1




>
>
>

--

---
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_308_8040612.1384029313809
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><div>I wonder whether we could include so=
mething like bit streams or bit queues, which the following functionality:<=
/div><div>add(int n_bits, Integral x)</div><div>pop(int n_bits, Integral&am=
p; x)</div><div>&nbsp;</div><div>They are convenient for handling various c=
ompression algorithms and the like.</div><div>s.add(4, 0xB)</div><div>s.pop=
(2, x); // x =3D&gt; 2</div><div>s.pop(1, x1); // x1 =3D&gt; 1</div><div>s.=
pop(1,x2); // x2 =3D&gt; 1</div><div><br><br>&nbsp;</div></div><blockquote =
class=3D"gmail_quote" style=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex=
; border-left-color: rgb(204, 204, 204); border-left-width: 1px; border-lef=
t-style: solid;"><div dir=3D"ltr"><div><blockquote class=3D"gmail_quote" st=
yle=3D"margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left-color: rgb=
(204, 204, 204); border-left-width: 1px; border-left-style: solid;">&nbsp;<=
/blockquote></div></div></blockquote></div>

<p></p>

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

------=_Part_308_8040612.1384029313809--

.

------=_Part_1279_10914741.1384029440154
Content-Type: text/plain; charset=ISO-8859-1

That looks interesting, however I don't think it belongs in this proposal.
It sounds like a new class which would be suggested by a proposal of its
own.

On Saturday, November 9, 2013 3:35:13 PM UTC-5, Mikhail Semenov wrote:
>
> I wonder whether we could include something like bit streams or bit
> queues, which the following functionality:
> add(int n_bits, Integral x)
> pop(int n_bits, Integral& x)
>
> They are convenient for handling various compression algorithms and the
> like.
> s.add(4, 0xB)
> s.pop(2, x); // x => 2
> s.pop(1, x1); // x1 => 1
> s.pop(1,x2); // x2 => 1
>
>
>
>
>>
>>
>>

--

---
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_1279_10914741.1384029440154
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">That looks interesting, however I don't think it belongs i=
n this proposal. It sounds like a new class which would be suggested by a p=
roposal of its own.<br><br>On Saturday, November 9, 2013 3:35:13 PM UTC-5, =
Mikhail Semenov wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;=
margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr"><div dir=3D"ltr"><div>I wonder whether we could include something =
like bit streams or bit queues, which the following functionality:</div><di=
v>add(int n_bits, Integral x)</div><div>pop(int n_bits, Integral&amp; x)</d=
iv><div>&nbsp;</div><div>They are convenient for handling various compressi=
on algorithms and the like.</div><div>s.add(4, 0xB)</div><div>s.pop(2, x); =
// x =3D&gt; 2</div><div>s.pop(1, x1); // x1 =3D&gt; 1</div><div>s.pop(1,x2=
); // x2 =3D&gt; 1</div><div><br><br>&nbsp;</div></div><blockquote class=3D=
"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;padding-left:1ex;border-lef=
t-color:rgb(204,204,204);border-left-width:1px;border-left-style:solid"><di=
v dir=3D"ltr"><div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0p=
x 0px 0.8ex;padding-left:1ex;border-left-color:rgb(204,204,204);border-left=
-width:1px;border-left-style:solid">&nbsp;</blockquote></div></div></blockq=
uote></div></blockquote></div>

<p></p>

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

------=_Part_1279_10914741.1384029440154--

.

------=_Part_2091_12109875.1384149267000
Content-Type: text/plain; charset=ISO-8859-1

Everyone, please migrate to this new thread and discontinue posting here.
Thanks!

https://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/lE5-kecjJTc


On Saturday, November 9, 2013 3:37:20 PM UTC-5, fmatth...@gmail.com wrote:
>
> That looks interesting, however I don't think it belongs in this proposal.
> It sounds like a new class which would be suggested by a proposal of its
> own.
>
> On Saturday, November 9, 2013 3:35:13 PM UTC-5, Mikhail Semenov wrote:
>>
>> I wonder whether we could include something like bit streams or bit
>> queues, which the following functionality:
>> add(int n_bits, Integral x)
>> pop(int n_bits, Integral& x)
>>
>> They are convenient for handling various compression algorithms and the
>> like.
>> s.add(4, 0xB)
>> s.pop(2, x); // x => 2
>> s.pop(1, x1); // x1 => 1
>> s.pop(1,x2); // x2 => 1
>>
>>
>>
>>
>>>
>>>
>>>

--

---
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_2091_12109875.1384149267000
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Everyone, please migrate to this new thread and discontinu=
e posting here. Thanks!<br><br>https://groups.google.com/a/isocpp.org/forum=
/#!topic/std-proposals/lE5-kecjJTc<br><br><br>On Saturday, November 9, 2013=
 3:37:20 PM UTC-5, fmatth...@gmail.com wrote:<blockquote class=3D"gmail_quo=
te" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;paddi=
ng-left: 1ex;"><div dir=3D"ltr">That looks interesting, however I don't thi=
nk it belongs in this proposal. It sounds like a new class which would be s=
uggested by a proposal of its own.<br><br>On Saturday, November 9, 2013 3:3=
5:13 PM UTC-5, Mikhail Semenov wrote:<blockquote class=3D"gmail_quote" styl=
e=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex=
"><div dir=3D"ltr"><div dir=3D"ltr"><div>I wonder whether we could include =
something like bit streams or bit queues, which the following functionality=
:</div><div>add(int n_bits, Integral x)</div><div>pop(int n_bits, Integral&=
amp; x)</div><div>&nbsp;</div><div>They are convenient for handling various=
 compression algorithms and the like.</div><div>s.add(4, 0xB)</div><div>s.p=
op(2, x); // x =3D&gt; 2</div><div>s.pop(1, x1); // x1 =3D&gt; 1</div><div>=
s.pop(1,x2); // x2 =3D&gt; 1</div><div><br><br>&nbsp;</div></div><blockquot=
e class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;padding-left:1ex;=
border-left-color:rgb(204,204,204);border-left-width:1px;border-left-style:=
solid"><div dir=3D"ltr"><div><blockquote class=3D"gmail_quote" style=3D"mar=
gin:0px 0px 0px 0.8ex;padding-left:1ex;border-left-color:rgb(204,204,204);b=
order-left-width:1px;border-left-style:solid">&nbsp;</blockquote></div></di=
v></blockquote></div></blockquote></div></blockquote></div>

<p></p>

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

------=_Part_2091_12109875.1384149267000--

.