Discussion:
Bit utilities proposal, last revision before submission
(too old to reply)
Vincent Reverdy
2016-01-20 20:58:07 UTC
Permalink
Hello again everyone.

I've finally implemented a lot of changes in that proposal.
This time, it looks good to me in the sense that it discuss a lot of
different possible approaches.
Critics, comments and code reviews (for the classes synopsis) are very
welcome.

Best,
Vincent
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Jens Maurer
2016-01-20 23:12:00 UTC
Permalink
Post by Vincent Reverdy
Hello again everyone.
I've finally implemented a lot of changes in that proposal.
This time, it looks good to me in the sense that it discuss a lot of different possible approaches.
Critics, comments and code reviews (for the classes synopsis) are very welcome.
This seems a bit ... large to me.

I disagree that bits should have arithmetic operations (in particular
compound assignment and increment/decrement) going with them.
I understand the mathematical motivation, but that seems to be quite
a stretch to me.

I would appreciate not having implicit conversion to bool for any
of these types; explicit conversion to bool is fine.

For the set / reset / flip operations, I wonder whether we'd be better
off with a non-member approach:

bit_whatever my_bit;
set(my_bit); // uh, conflicts with std::set
reset(my_bit);
flip(my_bit);

This would allow to remove bit_value and replace it with "bool",
my natural choice for a single bit rvalue.

You seem to use size_t throughout to indicate the position of a bit
in an unsigned integer. That seems a bit over-the-top, and might
be larger-than-efficient on some platforms such as x86 real mode,
where size_t is probably 32-bit, but there aren't any 32-bit
arithmetic instructions.

A bit more explanation on the semantics of the individual operations
would be appreciated. For example, what's comparison and difference
on bit_pointer supposed to do when the two bit_pointers refer to
distinct UIntType objects?

Jens
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vincent Reverdy
2016-01-20 23:55:38 UTC
Permalink
Thanks for the comments!

The approach you describe (no arithmetic operations), is the one I was
using in the previous versions.
I prefered to opt for the most exhaustive approach, because it is easier to
remove arithmetic operators later than to introduce them.
I would advocate for one of the two options:
1) no arithmetic behaviour at all (and consequently no implicit conversion
to bool, but only an explicit one)
2) an exhaustive arithmetic behaviour (like the one I present in this
version)
Having an overloaded ~, no compound assignment but binary arithmetic
operators through an implicit conversion seems very error-prone to me.

For non-members, I will list the idea in the last part of the document.
But maybe set and reset are far too common names to be dedicated to bit
manipulation? (and there is also the problem of the conflicting name).
And if we make the bool conversion operator explicit, for me, it means that
we consider that a bit and a boolean are two different concepts, and in
that case, I find it far more elegant to have a dedicated bit_value class.
But that is just my opinion.

Thanks for the size_t remark, that's a very good point!

For the comparison and difference operators, I explain it in the
"additional remark" subsection of the "design decisions part" (as far as I
remember).
It is to deal with cv-qualified template types, and is inspired by the
design of std::reverse_iterator.
So can compare a bit_pointer<unsigned int> with a bit_pointer<const
unsigned int>,but you cannot compare a bit_pointer<unsigned int> to a bit_pointer<unsigned
long long int>.

Vincent
Post by Vincent Reverdy
Post by Vincent Reverdy
Hello again everyone.
I've finally implemented a lot of changes in that proposal.
This time, it looks good to me in the sense that it discuss a lot of
different possible approaches.
Post by Vincent Reverdy
Critics, comments and code reviews (for the classes synopsis) are very
welcome.
This seems a bit ... large to me.
I disagree that bits should have arithmetic operations (in particular
compound assignment and increment/decrement) going with them.
I understand the mathematical motivation, but that seems to be quite
a stretch to me.
I would appreciate not having implicit conversion to bool for any
of these types; explicit conversion to bool is fine.
For the set / reset / flip operations, I wonder whether we'd be better
bit_whatever my_bit;
set(my_bit); // uh, conflicts with std::set
reset(my_bit);
flip(my_bit);
This would allow to remove bit_value and replace it with "bool",
my natural choice for a single bit rvalue.
You seem to use size_t throughout to indicate the position of a bit
in an unsigned integer. That seems a bit over-the-top, and might
be larger-than-efficient on some platforms such as x86 real mode,
where size_t is probably 32-bit, but there aren't any 32-bit
arithmetic instructions.
A bit more explanation on the semantics of the individual operations
would be appreciated. For example, what's comparison and difference
on bit_pointer supposed to do when the two bit_pointers refer to
distinct UIntType objects?
Jens
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Jens Maurer
2016-01-21 08:33:35 UTC
Permalink
Post by Vincent Reverdy
Thanks for the comments!
The approach you describe (no arithmetic operations), is the one I was using in the previous versions.
I prefered to opt for the most exhaustive approach, because it is easier to remove arithmetic operators later than to introduce them.
1) no arithmetic behaviour at all (and consequently no implicit conversion to bool, but only an explicit one)
2) an exhaustive arithmetic behaviour (like the one I present in this version)
I can't follow "exhaustive"; I didn't see free functions such as + - * /.
Post by Vincent Reverdy
Having an overloaded ~, no compound assignment but binary arithmetic operators through an implicit conversion seems very error-prone to me.
No implicit conversions out of a bit_* class, please.
Post by Vincent Reverdy
For non-members, I will list the idea in the last part of the document.
But maybe set and reset are far too common names to be dedicated to bit manipulation? (and there is also the problem of the conflicting name).
And if we make the bool conversion operator explicit, for me, it means that we consider that a bit and a boolean are two different concepts, and in that case, I find it far more elegant to have a dedicated bit_value class. But that is just my opinion.
Frankly, and I understand this is a large item, I'd like to see more
use-cases for this. That is, specific problems that are addressed
by these classes. I'm particularly interested in specific use-cases
(as in: problems to be solved, not conceived snippets of code) for
the arithmetic operations. Note that "bool" does NOT have the
arithmetic properties you ascribe to bit_value here.
Post by Vincent Reverdy
For the comparison and difference operators, I explain it in the "additional remark" subsection of the "design decisions part" (as far as I remember).
No, I'm not talking about const vs. non-const. I'm talking about

unsigned int i = 0;
unsinged int j = 0;
bit_pointer(i, 0) - bit_pointer(j, 1) // what's the result?

(I don't think we want the argument of bit_pointer to ever be
NULL, so using a reference instead of a pointer parameter seems
the better approach.)

Thanks,
Jens
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vincent Reverdy
2016-01-21 16:13:24 UTC
Permalink
Post by Vincent Reverdy
Post by Vincent Reverdy
Thanks for the comments!
The approach you describe (no arithmetic operations), is the one I was
using in the previous versions.
Post by Vincent Reverdy
I prefered to opt for the most exhaustive approach, because it is easier
to remove arithmetic operators later than to introduce them.
Post by Vincent Reverdy
1) no arithmetic behaviour at all (and consequently no implicit
conversion to bool, but only an explicit one)
Post by Vincent Reverdy
2) an exhaustive arithmetic behaviour (like the one I present in this
version)
I can't follow "exhaustive"; I didn't see free functions such as + - * /.
Most operators are obtained through an implicit conversion to bool (which
is then likely to be promoted to int, but that's ok because if a bit is
mathematically defined as a one-bit long unsigned integer, then, this
behaviour is consistent with what would be expected if a bit was a
fundamental type). With the current std::bitset::reference, you can write x
= x + 3, but you cannot write x += 3. For me, this is a significant
conceptual problem.
Post by Vincent Reverdy
Post by Vincent Reverdy
Having an overloaded ~, no compound assignment but binary arithmetic
operators through an implicit conversion seems very error-prone to me.
No implicit conversions out of a bit_* class, please.
This design choice is directly related to the question of arithmetic
behaviour, because implicit conversions provide most operators without
having to write all the possible combinations of binary operators with
integer types. Maybe there is another "simple" way to provide all the
binary arithmetic operators that I don't have considered, and in that case
it would make the two questions separate (which would be good). But if the
two question are linked, then I would like the question of the arithmetic
behaviour to be discussed with this proposal, because I think it is
important. It boils down to the fundamental question of "what is a bit?".
In this version of the proposal, I have considered that a bit is
mathematically a one-digit long unsigned integer. I discuss the other
options that came to my mind in the "What is the arithmetic definition of a
bit?" subsection. In my view, the first question to anwer is "what is,
mathematically speaking, a bit?". This question have strong design
consequences, including, implicit conversions (at least as long as the two
questions are linked).
Post by Vincent Reverdy
Post by Vincent Reverdy
For non-members, I will list the idea in the last part of the document.
But maybe set and reset are far too common names to be dedicated to bit
manipulation? (and there is also the problem of the conflicting name).
Post by Vincent Reverdy
And if we make the bool conversion operator explicit, for me, it means
that we consider that a bit and a boolean are two different concepts, and
in that case, I find it far more elegant to have a dedicated bit_value
class. But that is just my opinion.
Frankly, and I understand this is a large item, I'd like to see more
use-cases for this. That is, specific problems that are addressed
by these classes. I'm particularly interested in specific use-cases
(as in: problems to be solved, not conceived snippets of code) for
the arithmetic operations. Note that "bool" does NOT have the
arithmetic properties you ascribe to bit_value here.
You mean, more use-cases for bit utilities, in general, or more use cases
for bit_value? If we are speaking of bit_value, for me, the simple fact
that a reference and a value of an object would have a different arithmetic
behaviour, is both error-prone and conceptually very strange And this would
be the case if we consider that the value type associated with a
bit_reference is a bool. That is one of the reason behind bit_value. The
arithmetic behaviour I provide for bit_value and bit_reference, here, is
the arithmetic behaviour of a hypothetical one-digit long integer (in the
sense of unsigned char, unsigned short int, unsigned int, unsigned long
int, unsigned long long int), which is NOT a bool.
Post by Vincent Reverdy
Post by Vincent Reverdy
For the comparison and difference operators, I explain it in the
"additional remark" subsection of the "design decisions part" (as far as I
remember).
No, I'm not talking about const vs. non-const. I'm talking about
unsigned int i = 0;
unsinged int j = 0;
bit_pointer(i, 0) - bit_pointer(j, 1) // what's the result?
The result should be the distance, in iterable bits, between the pointed
bits (as an extension of a classical difference of pointers).
Something like :
(&j - &i)*std::numeric_limits<unsigned int>::digits + (pos_j - pos-i)
Post by Vincent Reverdy
(I don't think we want the argument of bit_pointer to ever be
NULL, so using a reference instead of a pointer parameter seems
the better approach.)
Thanks,
Jens
Note: keep in mind that, this is a first draft with a "suggestion of
design" only.
Actually, the main questions I would really like to be answered after a
first face-to-face meeting are:
- Do we want a bit_iterator in the standard library to be able to write
algorithms on bits (if the answer by the community, and especially the low
latency application domains, is yes, then the other classes are a
consequence of that)?
- How to define the position of a bit (it put constaints on the template
parameter type, and on the way we iterate on bits)?
- What is, conceptually and mathematically, a bit? (a pure digit with no
mathematical meaning, a pure bool, a one-digit long unsigned integer => it
will put strong constraints on the design (including arithmetic operators
and implicit conversions))
Given the answers to these "fundamental" questions, the whole document will
be updated to propose something that fit these requirements.

@Tomasz
Thanks for the very interesting suggestion. I did not think of that.

=================
Plus, I have an additional question: what would be the most suited part of
the committee to discuss this proposal? Library evolution, Ranges (SG9) or
Low Latency (SG14)? Or a mix of all of them?
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Patrice Roy
2016-01-21 16:32:01 UTC
Permalink
It can go to SG14 for an early discussion / exchange of ideas, but will
probably go to LEWG eventually (or so it seems to me).
Post by Vincent Reverdy
Post by Vincent Reverdy
Post by Vincent Reverdy
Thanks for the comments!
The approach you describe (no arithmetic operations), is the one I was
using in the previous versions.
Post by Vincent Reverdy
I prefered to opt for the most exhaustive approach, because it is
easier to remove arithmetic operators later than to introduce them.
Post by Vincent Reverdy
1) no arithmetic behaviour at all (and consequently no implicit
conversion to bool, but only an explicit one)
Post by Vincent Reverdy
2) an exhaustive arithmetic behaviour (like the one I present in this
version)
I can't follow "exhaustive"; I didn't see free functions such as + - * /.
Most operators are obtained through an implicit conversion to bool (which
is then likely to be promoted to int, but that's ok because if a bit is
mathematically defined as a one-bit long unsigned integer, then, this
behaviour is consistent with what would be expected if a bit was a
fundamental type). With the current std::bitset::reference, you can write
x = x + 3, but you cannot write x += 3. For me, this is a significant
conceptual problem.
Post by Vincent Reverdy
Post by Vincent Reverdy
Having an overloaded ~, no compound assignment but binary arithmetic
operators through an implicit conversion seems very error-prone to me.
No implicit conversions out of a bit_* class, please.
This design choice is directly related to the question of arithmetic
behaviour, because implicit conversions provide most operators without
having to write all the possible combinations of binary operators with
integer types. Maybe there is another "simple" way to provide all the
binary arithmetic operators that I don't have considered, and in that case
it would make the two questions separate (which would be good). But if the
two question are linked, then I would like the question of the arithmetic
behaviour to be discussed with this proposal, because I think it is
important. It boils down to the fundamental question of "what is a bit?".
In this version of the proposal, I have considered that a bit is
mathematically a one-digit long unsigned integer. I discuss the other
options that came to my mind in the "What is the arithmetic definition of a
bit?" subsection. In my view, the first question to anwer is "what is,
mathematically speaking, a bit?". This question have strong design
consequences, including, implicit conversions (at least as long as the two
questions are linked).
Post by Vincent Reverdy
Post by Vincent Reverdy
For non-members, I will list the idea in the last part of the document.
But maybe set and reset are far too common names to be dedicated to bit
manipulation? (and there is also the problem of the conflicting name).
Post by Vincent Reverdy
And if we make the bool conversion operator explicit, for me, it means
that we consider that a bit and a boolean are two different concepts, and
in that case, I find it far more elegant to have a dedicated bit_value
class. But that is just my opinion.
Frankly, and I understand this is a large item, I'd like to see more
use-cases for this. That is, specific problems that are addressed
by these classes. I'm particularly interested in specific use-cases
(as in: problems to be solved, not conceived snippets of code) for
the arithmetic operations. Note that "bool" does NOT have the
arithmetic properties you ascribe to bit_value here.
You mean, more use-cases for bit utilities, in general, or more use cases
for bit_value? If we are speaking of bit_value, for me, the simple fact
that a reference and a value of an object would have a different arithmetic
behaviour, is both error-prone and conceptually very strange And this would
be the case if we consider that the value type associated with a
bit_reference is a bool. That is one of the reason behind bit_value. The
arithmetic behaviour I provide for bit_value and bit_reference, here, is
the arithmetic behaviour of a hypothetical one-digit long integer (in the
sense of unsigned char, unsigned short int, unsigned int, unsigned long
int, unsigned long long int), which is NOT a bool.
Post by Vincent Reverdy
Post by Vincent Reverdy
For the comparison and difference operators, I explain it in the
"additional remark" subsection of the "design decisions part" (as far as I
remember).
No, I'm not talking about const vs. non-const. I'm talking about
unsigned int i = 0;
unsinged int j = 0;
bit_pointer(i, 0) - bit_pointer(j, 1) // what's the result?
The result should be the distance, in iterable bits, between the pointed
bits (as an extension of a classical difference of pointers).
(&j - &i)*std::numeric_limits<unsigned int>::digits + (pos_j - pos-i)
Post by Vincent Reverdy
(I don't think we want the argument of bit_pointer to ever be
NULL, so using a reference instead of a pointer parameter seems
the better approach.)
Thanks,
Jens
Note: keep in mind that, this is a first draft with a "suggestion of
design" only.
Actually, the main questions I would really like to be answered after a
- Do we want a bit_iterator in the standard library to be able to write
algorithms on bits (if the answer by the community, and especially the low
latency application domains, is yes, then the other classes are a
consequence of that)?
- How to define the position of a bit (it put constaints on the template
parameter type, and on the way we iterate on bits)?
- What is, conceptually and mathematically, a bit? (a pure digit with no
mathematical meaning, a pure bool, a one-digit long unsigned integer => it
will put strong constraints on the design (including arithmetic operators
and implicit conversions))
Given the answers to these "fundamental" questions, the whole document
will be updated to propose something that fit these requirements.
@Tomasz
Thanks for the very interesting suggestion. I did not think of that.
=================
Plus, I have an additional question: what would be the most suited part of
the committee to discuss this proposal? Library evolution, Ranges (SG9) or
Low Latency (SG14)? Or a mix of all of them?
--
---
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
Visit this group at
https://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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Tony V E
2016-01-21 16:34:13 UTC
Permalink
<html><head></head><body lang="en-US" style="background-color: rgb(255, 255, 255); line-height: initial;"> <div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);">&gt; <span style="line-height: initial;">Something like :</span></div>&gt; (&amp;j - &amp;i)*std::numeric_limits&lt;unsigned int&gt;::digits + (pos_j - pos-i)<div><br></div><div>?Since i and j are not part of the same array, the above is actually undefined behaviour.&nbsp;</div><div><br></div><div>&gt; ?What is, conceptually and mathematically, a bit? (a pure digit with no mathematical meaning, a pure bool, a one-digit long unsigned integer =&gt; it will put strong constraints on the design (including arithmetic operators and implicit conversions))</div><div><br></div><div>A bit is a bool. Now, you can argue about what a bool is (conceptually, mathematically) and you might get a different answer than what C++ has decided a bool is. ? But the closest thing we have to a bit is a bool, so you should align with that, and not step past it to arithmetic types.&nbsp;</div><div><br></div><div>?&gt; Plus, I have an additional question: what would be the most suited part of the committee to discuss this proposal? Library evolution, Ranges (SG9) or Low Latency (SG14)? Or a mix of all of them?<br><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);"><br></div><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);">LEWG.&nbsp;</div><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);"><br></div><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);">IMO,</div><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);">Tony</div><div style="width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);"><br></div> <div style="display:none"></div> <div style="font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, 255);">Sent&nbsp;from&nbsp;my&nbsp;BlackBerry&nbsp;portable&nbsp;Babbage&nbsp;Device</div> <div style="display:none"></div><div style="font-size: initial; text-align: initial; background-color: rgb(255, 255, 255);"><table width="100%" style="background-color:white; border-spacing:0px;"> <tbody><tr><td></td><td id="_separatorInternal" rowspan="2" style="text-align: center; font-size: initial; background-color: rgb(255, 255, 255);"> <span id="_bb10TempSeparatorText" style="background-color:white; color:#0073BC;font-size:smaller;font-family:&quot;Slate Pro&quot;">&nbsp; Original Message &nbsp;</span> </td></tr> <tr> <td colspan="2"><div style="border:none;border-top:solid #0073BC 1.0pt;"></div> </td></tr></tbody></table></div> <table width="100%" style="background-color:white;border-spacing:0px;"> <tbody><tr><td colspan="2" style="font-size: initial; text-align: initial; background-color: rgb(255, 255, 255);"> <div style="font-size: smaller;font-family:&quot;Tahoma&quot;,&quot;BB Alpha Sans&quot;,&quot;Slate Pro&quot;,sans-serif,&quot;sans-serif&quot;;"> <div><b>From: </b>Vincent Reverdy</div><div><b>Sent: </b>Thursday, January 21, 2016 11:13 AM</div><div><b>To: </b>ISO C++ Standard - Future Proposals</div><div><b>Reply To: </b>std-***@isocpp.org</div><div><b>Subject: </b>Re: [std-proposals] Bit utilities proposal, last revision before submission</div></div></td></tr></tbody></table><div style="border-style: solid none none; border-top-color: rgb(186, 188, 209); border-top-width: 1pt; font-size: initial; text-align: initial; background-color: rgb(255, 255, 255);"></div><br><div id="_originalContent" style=""><div dir="ltr">Le jeudi 21 janvier 2016 02:33:38 UTC-6, Jens Maurer a ?crit&nbsp;:<blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On 01/21/2016 12:55 AM, Vincent Reverdy wrote: <br>&gt; Thanks for the comments! <br>&gt; <br>&gt; The approach you describe (no arithmetic operations), is the one I was using in the previous versions. <br>&gt; I prefered to opt for the most exhaustive approach, because it is easier to remove arithmetic operators later than to introduce them. <br>&gt; I would advocate for one of the two options: <br>&gt; 1) no arithmetic behaviour at all (and consequently no implicit conversion to bool, but only an explicit one) <br>&gt; 2) an exhaustive arithmetic behaviour (like the one I present in this version) <br> <br>I can't follow "exhaustive"; I didn't see free functions such as + - * /. <br></blockquote><div><br>Most operators are obtained through an implicit conversion to <span style="font-family: courier new,monospace;">bool</span> (which is then likely to be promoted to int, but that's ok because if a bit is mathematically defined as a one-bit long unsigned integer, then, this behaviour is consistent with what would be expected if a bit was a fundamental type). With the current <span style="font-family: courier new,monospace;">std::bitset::reference</span>, you can write x = x + 3, but you cannot write x += 3. For me, this is a significant conceptual problem.<br>&nbsp;</div><blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">&gt; Having an overloaded ~, no compound assignment but binary arithmetic operators through an implicit conversion seems very error-prone to me. <br> <br>No implicit conversions out of a bit_* class, please. <br></blockquote><div><br>This design choice is directly related to the question of arithmetic behaviour, because implicit conversions provide most operators without having to write all the possible combinations of binary operators with integer types. Maybe there is another "simple" way to provide all the binary arithmetic operators that I don't have considered, and in that case it would make the two questions separate (which would be good). But if the two question are linked, then I would like the question of the arithmetic behaviour to be discussed with this proposal, because I think it is important. It boils down to the fundamental question of "what is a bit?". In this version of the proposal, I have considered that a bit is mathematically a one-digit long unsigned integer. I discuss the other options that came to my mind in the "What is the arithmetic definition of a bit?" subsection. In my view, the first question to anwer is "what is, mathematically speaking, a bit?". This question have strong design consequences, including, implicit conversions (at least as long as the two questions are linked).<br>&nbsp;</div><blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"> <br>&gt; For non-members, I will list the idea in the last part of the document. <br>&gt; But maybe set and reset are far too common names to be dedicated to bit manipulation? (and there is also the problem of the conflicting name). <br>&gt; And if we make the bool conversion operator explicit, for me, it means that we consider that a bit and a boolean are two different concepts, and in that case, I find it far more elegant to have a dedicated bit_value class. But that is just my opinion. <br> <br>Frankly, and I understand this is a large item, I'd like to see more <br>use-cases for this. &nbsp;That is, specific problems that are addressed <br>by these classes. &nbsp;I'm particularly interested in specific use-cases <br>(as in: problems to be solved, not conceived snippets of code) for <br>the arithmetic operations. &nbsp;Note that "bool" does NOT have the <br>arithmetic properties you ascribe to bit_value here. <br></blockquote><div><br>You mean, more use-cases for bit utilities, in general, or more use cases for bit_value? If we are speaking of bit_value, for me, the simple fact that a reference and a value of an object would have a different arithmetic behaviour, is both error-prone and conceptually very strange And this would be the case if we consider that the value type associated with a bit_reference is a bool. That is one of the reason behind bit_value. The arithmetic behaviour I provide for bit_value and bit_reference, here, is the arithmetic behaviour of a hypothetical one-digit long integer (in the sense of unsigned char, unsigned short int, unsigned int, unsigned long int, unsigned long long int), which is NOT a bool. <br>&nbsp;<br></div><blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"> <br>&gt; For the comparison and difference operators, I explain it in the "additional remark" subsection of the "design decisions part" (as far as I remember). <br> <br>No, I'm not talking about const vs. non-const. &nbsp;I'm talking about <br> <br>&nbsp; &nbsp;unsigned int i = 0; <br>&nbsp; &nbsp;unsinged int j = 0; <br>&nbsp; &nbsp;bit_pointer(i, 0) - bit_pointer(j, 1) &nbsp;// what's the result? <br> <br></blockquote><div><br>The result should be the distance, in iterable bits, between the pointed bits (as an extension of a classical difference of pointers). <br>Something like :<br>(&amp;j - &amp;i)*std::numeric_limits&lt;unsigned int&gt;::digits + (pos_j - pos-i)<br>&nbsp;</div><blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">(I don't think we want the argument of bit_pointer to ever be <br>NULL, so using a reference instead of a pointer parameter seems <br>the better approach.) <br> <br>Thanks, <br>Jens <br></blockquote><div><br>Note: keep in mind that, this is a first draft with a "suggestion of design" only.<br>Actually, the main questions I would really like to be answered after a first face-to-face meeting are:<br>- Do we want a bit_iterator in the standard library to be able to write algorithms on bits (if the answer by the community, and especially the low latency application domains, is yes, then the other classes are a consequence of that)?<br>- How to define the position of a bit (it put constaints on the template parameter type, and on the way we iterate on bits)?<br>- What is, conceptually and mathematically, a bit? (a pure digit with no mathematical meaning, a pure bool, a one-digit long unsigned integer =&gt; it will put strong constraints on the design (including arithmetic operators and implicit conversions))<br>Given the answers to these "fundamental" questions, the whole document will be updated to propose something that fit these requirements.<br><br>@Tomasz<br>Thanks for the very interesting suggestion. I did not think of that.<br><br>=================<br>Plus, I have an additional question: what would be the most suited part of the committee to discuss this proposal? Library evolution, Ranges (SG9) or Low Latency (SG14)? Or a mix of all of them?<br></div></div>

<p></p>

-- <br>
<br>
--- <br>
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:std-proposals+***@isocpp.org">std-proposals+***@isocpp.org</a>.<br>
To post to this group, send email to <a href="mailto:std-***@isocpp.org">std-***@isocpp.org</a>.<br>
Visit this group at <a href="https://groups.google.com/a/isocpp.org/group/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals/</a>.<br>
<br><!--end of _originalContent --></div></div></body></html>

<p></p>

-- <br />
<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 email to <a href="mailto:std-proposals+***@isocpp.org">std-proposals+***@isocpp.org</a>.<br />
To post to this group, send email to <a href="mailto:std-***@isocpp.org">std-***@isocpp.org</a>.<br />
Visit this group at <a href="https://groups.google.com/a/isocpp.org/group/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals/</a>.<br />
Vincent Reverdy
2016-01-21 17:05:51 UTC
Permalink
Post by Vincent Reverdy
(&j - &i)*std::numeric_limits<unsigned int>::digits + (pos_j - pos-i)
‎Since i and j are not part of the same array, the above is actually
undefined behaviour.
Post by Vincent Reverdy
‎What is, conceptually and mathematically, a bit? (a pure digit with no
mathematical meaning, a pure bool, a one-digit long unsigned integer => it
will put strong constraints on the design (including arithmetic operators
and implicit conversions))
A bit is a bool. Now, you can argue about what a bool is (conceptually,
mathematically) and you might get a different answer than what C++ has
decided a bool is. ‎ But the closest thing we have to a bit is a bool, so
you should align with that, and not step past it to arithmetic types.
I don't want to argue about what C++ has decided a bool is. I am perfectly
ok with what a bool is ;)
However, I don't see anything in the current standard that explicitly
requires a bit to be a bool, but maybe I am wrong.
Even std::bitset::reference and std::vector<bool>::reference are not bool:
bool don't have set/reset/flip functions, bool have a different behaviour
of operator~ (see lines 3 and 4 of the example listing on the page 3 of the
proposal), and bool have compound assignment operators. That is already
quite strong differences.
Personnally, I would be very happy with one of the two options to motivate
the assertion "a bit is a bool":
1) The standards REQUIRES a bit to be a bool, because of the following
reasons: A, B, and C (including potential problems if this rule is not
strictly followed)
2) People are happy with a bit and a bool being conceptually the same thing
Either one of these is for me an excellent motivation, and in that case,
the most "logical" design I can think of, is no bit_value, a bit_reference
implicitly convertible to bool, no overloaded operator~, a set of non
member functions set/reset/flip as suggested by Jens, and compound
arithmetic operators.
But if neither of this is true, then we can wonder what the alternatives
are (and I discuss five of them in the proposal).
‎> Plus, I have an additional question: what would be the most suited part
of the committee to discuss this proposal? Library evolution, Ranges (SG9)
or Low Latency (SG14)? Or a mix of all of them?
LEWG.
IMO,
Tony
Sent from my BlackBerry portable Babbage Device
Original Message
*From: *Vincent Reverdy
*Sent: *Thursday, January 21, 2016 11:13 AM
*To: *ISO C++ Standard - Future Proposals
*Subject: *Re: [std-proposals] Bit utilities proposal, last revision
before submission
Post by Vincent Reverdy
Post by Vincent Reverdy
Thanks for the comments!
The approach you describe (no arithmetic operations), is the one I was
using in the previous versions.
Post by Vincent Reverdy
I prefered to opt for the most exhaustive approach, because it is
easier to remove arithmetic operators later than to introduce them.
Post by Vincent Reverdy
1) no arithmetic behaviour at all (and consequently no implicit
conversion to bool, but only an explicit one)
Post by Vincent Reverdy
2) an exhaustive arithmetic behaviour (like the one I present in this
version)
I can't follow "exhaustive"; I didn't see free functions such as + - * /.
Most operators are obtained through an implicit conversion to bool (which
is then likely to be promoted to int, but that's ok because if a bit is
mathematically defined as a one-bit long unsigned integer, then, this
behaviour is consistent with what would be expected if a bit was a
fundamental type). With the current std::bitset::reference, you can write
x = x + 3, but you cannot write x += 3. For me, this is a significant
conceptual problem.
Post by Vincent Reverdy
Post by Vincent Reverdy
Having an overloaded ~, no compound assignment but binary arithmetic
operators through an implicit conversion seems very error-prone to me.
No implicit conversions out of a bit_* class, please.
This design choice is directly related to the question of arithmetic
behaviour, because implicit conversions provide most operators without
having to write all the possible combinations of binary operators with
integer types. Maybe there is another "simple" way to provide all the
binary arithmetic operators that I don't have considered, and in that case
it would make the two questions separate (which would be good). But if the
two question are linked, then I would like the question of the arithmetic
behaviour to be discussed with this proposal, because I think it is
important. It boils down to the fundamental question of "what is a bit?".
In this version of the proposal, I have considered that a bit is
mathematically a one-digit long unsigned integer. I discuss the other
options that came to my mind in the "What is the arithmetic definition of a
bit?" subsection. In my view, the first question to anwer is "what is,
mathematically speaking, a bit?". This question have strong design
consequences, including, implicit conversions (at least as long as the two
questions are linked).
Post by Vincent Reverdy
Post by Vincent Reverdy
For non-members, I will list the idea in the last part of the document.
But maybe set and reset are far too common names to be dedicated to bit
manipulation? (and there is also the problem of the conflicting name).
Post by Vincent Reverdy
And if we make the bool conversion operator explicit, for me, it means
that we consider that a bit and a boolean are two different concepts, and
in that case, I find it far more elegant to have a dedicated bit_value
class. But that is just my opinion.
Frankly, and I understand this is a large item, I'd like to see more
use-cases for this. That is, specific problems that are addressed
by these classes. I'm particularly interested in specific use-cases
(as in: problems to be solved, not conceived snippets of code) for
the arithmetic operations. Note that "bool" does NOT have the
arithmetic properties you ascribe to bit_value here.
You mean, more use-cases for bit utilities, in general, or more use cases
for bit_value? If we are speaking of bit_value, for me, the simple fact
that a reference and a value of an object would have a different arithmetic
behaviour, is both error-prone and conceptually very strange And this would
be the case if we consider that the value type associated with a
bit_reference is a bool. That is one of the reason behind bit_value. The
arithmetic behaviour I provide for bit_value and bit_reference, here, is
the arithmetic behaviour of a hypothetical one-digit long integer (in the
sense of unsigned char, unsigned short int, unsigned int, unsigned long
int, unsigned long long int), which is NOT a bool.
Post by Vincent Reverdy
Post by Vincent Reverdy
For the comparison and difference operators, I explain it in the
"additional remark" subsection of the "design decisions part" (as far as I
remember).
No, I'm not talking about const vs. non-const. I'm talking about
unsigned int i = 0;
unsinged int j = 0;
bit_pointer(i, 0) - bit_pointer(j, 1) // what's the result?
The result should be the distance, in iterable bits, between the pointed
bits (as an extension of a classical difference of pointers).
(&j - &i)*std::numeric_limits<unsigned int>::digits + (pos_j - pos-i)
Post by Vincent Reverdy
(I don't think we want the argument of bit_pointer to ever be
NULL, so using a reference instead of a pointer parameter seems
the better approach.)
Thanks,
Jens
Note: keep in mind that, this is a first draft with a "suggestion of
design" only.
Actually, the main questions I would really like to be answered after a
- Do we want a bit_iterator in the standard library to be able to write
algorithms on bits (if the answer by the community, and especially the low
latency application domains, is yes, then the other classes are a
consequence of that)?
- How to define the position of a bit (it put constaints on the template
parameter type, and on the way we iterate on bits)?
- What is, conceptually and mathematically, a bit? (a pure digit with no
mathematical meaning, a pure bool, a one-digit long unsigned integer => it
will put strong constraints on the design (including arithmetic operators
and implicit conversions))
Given the answers to these "fundamental" questions, the whole document
will be updated to propose something that fit these requirements.
@Tomasz
Thanks for the very interesting suggestion. I did not think of that.
=================
Plus, I have an additional question: what would be the most suited part of
the committee to discuss this proposal? Library evolution, Ranges (SG9) or
Low Latency (SG14)? Or a mix of all of them?
--
---
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
Visit this group at
https://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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Jens Maurer
2016-01-21 19:58:21 UTC
Permalink
Post by Jens Maurer
Post by Vincent Reverdy
Thanks for the comments!
The approach you describe (no arithmetic operations), is the one I was using in the previous versions.
I prefered to opt for the most exhaustive approach, because it is easier to remove arithmetic operators later than to introduce them.
1) no arithmetic behaviour at all (and consequently no implicit conversion to bool, but only an explicit one)
2) an exhaustive arithmetic behaviour (like the one I present in this version)
I can't follow "exhaustive"; I didn't see free functions such as + - * /.
Most operators are obtained through an implicit conversion to bool
(which is then likely to be promoted to int, but that's ok because if
a bit is mathematically defined as a one-bit long unsigned integer,
then, this behaviour is consistent with what would be expected if a
bit was a fundamental type). With the current std::bitset::reference,
you can write x = x + 3, but you cannot write x += 3. For me, this is
a significant conceptual problem.
In my opinion, the conceptual problem is that you can
write x = x + 1 where x is a bool.
And that probably yields x == true and not !x.

Put bluntly, I can't see the real-world value of a "mod 2"
arithmetic type. Yes, it's mathematically well-defined and
it's even a field, but whom does it help in practice?
Post by Jens Maurer
You mean, more use-cases for bit utilities, in general, or more use
cases for bit_value?
Use-cases for bit_value that require it to be different from "bool".
Post by Jens Maurer
If we are speaking of bit_value, for me, the
simple fact that a reference and a value of an object would have a
different arithmetic behaviour, is both error-prone and conceptually
very strange And this would be the case if we consider that the value
type associated with a bit_reference is a bool. That is one of the
reason behind bit_value. The arithmetic behaviour I provide for
bit_value and bit_reference, here, is the arithmetic behaviour of a
hypothetical one-digit long integer (in the sense of unsigned char,
unsigned short int, unsigned int, unsigned long int, unsigned long
long int), which is NOT a bool.
Everybody knows that arithmetic on bools essentially doesn't work;
unfortunately, it's not ill-formed due to the promotion to int.
Post by Jens Maurer
unsigned int i = 0;
unsinged int j = 0;
bit_pointer(i, 0) - bit_pointer(j, 1) // what's the result?
The result should be the distance, in iterable bits, between the pointed bits (as an extension of a classical difference of pointers).
(&j - &i)*std::numeric_limits<unsigned int>::digits + (pos_j - pos-i)
That's undefined behavior because i and j are not part of the
same array.
Post by Jens Maurer
Plus, I have an additional question: what would be the most suited part of the committee to discuss this proposal? Library evolution, Ranges (SG9) or Low Latency (SG14)? Or a mix of all of them?
LEWG. SG14 might not have quorum at WG21 meetings.
Please call me into the room so that I can vote against
the proposal in its current form.

Jens
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vincent Reverdy
2016-01-21 20:39:52 UTC
Permalink
Use-cases for bit_value that require it to be different from "bool".

Everybody knows that arithmetic on bools essentially doesn't work;
unfortunately, it's not ill-formed due to the promotion to int.

Again, my two prefered options are
[1) No arithmetic behaviour at all]
[2) An arithmetic behaviour of a one-digit long unsigned integer].
But I really don't like the grey zone in the middle.
So, if we opt for the first option, as you say, it's currently unfortunate
that arithmetic on bool is not ill formed.
For me that's an excellent motivation for bit_value in that case: I don't
want the value associated to a bit reference (which can be seen as the type
of std::bit_iterator::value_type) to have an arithmetic behaviour, and I
want the program to be ill-formed in that case (and in that case bit_value
would only be explicitly convertible to bool, not implicitly).

LEWG. SG14 might not have quorum at WG21 meetings.
Please call me into the room so that I can vote against
the proposal in its current form.

Of course, I would like you to be there.
My goal with this proposal is not to ask "Look, this design is awesome, do
you want it?" Of course not, because I don't think it is :)
The important word in your sentence is "in its current form". I would
myself also vote against in its current form.
It will need several revisions.

My goal is to say:
1) Is there an interest into providing a standard way to iterate on bits,
particularly for the low latency community? (this could lead later, to the
conception of bit ranges)
2) Here are some questions that need to be answered before proposing a
relevant design: How to define the position of a bit? What is,
mathematically speaking, a bit?
3) Here are some possible answers that seem to be very consistent to me (ie
the 1) and 2) listed before), but I personnally don't like the grey zone
between these two approaches.

Vincent
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Jens Maurer
2016-01-21 21:50:21 UTC
Permalink
1) Is there an interest into providing a standard way to iterate on bits, particularly for the low latency community? (this could lead later, to the conception of bit ranges)
This is a question you should ask SG14.
Personally, I haven't come across bit-strings often.
2) Here are some questions that need to be answered before proposing a relevant design: How to define the position of a bit? What is, mathematically speaking, a bit?
I think the only portable answer here is that the n-th bit in an
unsigned integer value x (which is guaranteed to have mod 2^m arithmetic)
is the one you get with x & (1 << n).
3) Here are some possible answers that seem to be very consistent to
me (ie the 1) and 2) listed before), but I personnally don't like the
grey zone between these two approaches.
Agreed, but people have come to live with "bool" for 15+ years.
Is the "bool" situation bad enough to spend time + effort of
lots of people to standardize bit_value? As I said, I'm looking
for use-cases (what practical higher-level problems are solved
with bit_value), and not "preferred options" at this time.

Jens
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Howard Hinnant
2016-01-21 21:56:12 UTC
Permalink
Post by Jens Maurer
Agreed, but people have come to live with "bool" for 15+ years.
Is the "bool" situation bad enough to spend time + effort of
lots of people to standardize bit_value? As I said, I'm looking
for use-cases (what practical higher-level problems are solved
with bit_value), and not "preferred options" at this time.
Here are performance numbers that show when algorithms are modified to take advantage of the bit-string data structure, significant performance optimizations (order of magnitude) over an array of bools can be had. find, count, copy, fill, rotate are examples of such algorithms and not a complete list.

This proposal may be the first stepping stone towards realizing such portable high-performance algorithms.

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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Jens Maurer
2016-01-21 22:54:13 UTC
Permalink
Post by Howard Hinnant
Post by Jens Maurer
Agreed, but people have come to live with "bool" for 15+ years.
Is the "bool" situation bad enough to spend time + effort of
lots of people to standardize bit_value? As I said, I'm looking
for use-cases (what practical higher-level problems are solved
with bit_value), and not "preferred options" at this time.
Here are performance numbers that show when algorithms are modified to take advantage of the bit-string data structure, significant performance optimizations (order of magnitude) over an array of bools can be had. find, count, copy, fill, rotate are examples of such algorithms and not a complete list.
This proposal may be the first stepping stone towards realizing such portable high-performance algorithms.
Yes, agreed.

Do those algorithms need bit_value as an rvalue representation
of a bit, or would they work with plain bool for this purpose, too?

(The algorithms you mentioned might need to be specialized
for bit_iterator, and/or bit_iterator needs a wider
interface to expose the underlying unsigned integer.)

Jens
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Howard Hinnant
2016-01-21 23:21:26 UTC
Permalink
Post by Jens Maurer
Post by Howard Hinnant
Post by Jens Maurer
Agreed, but people have come to live with "bool" for 15+ years.
Is the "bool" situation bad enough to spend time + effort of
lots of people to standardize bit_value? As I said, I'm looking
for use-cases (what practical higher-level problems are solved
with bit_value), and not "preferred options" at this time.
Here are performance numbers that show when algorithms are modified to take advantage of the bit-string data structure, significant performance optimizations (order of magnitude) over an array of bools can be had. find, count, copy, fill, rotate are examples of such algorithms and not a complete list.
This proposal may be the first stepping stone towards realizing such portable high-performance algorithms.
Yes, agreed.
Do those algorithms need bit_value as an rvalue representation
of a bit, or would they work with plain bool for this purpose, too?
(The algorithms you mentioned might need to be specialized
for bit_iterator, and/or bit_iterator needs a wider
interface to expose the underlying unsigned integer.)
To be perfectly transparent, I’m only tangentially following this thread/proposal (because of time constraints).

The algorithms definitely need to be specialized for bit_iterator, and bit_iterator must expose a wider interface than a normal iterator. If the algorithms see bools, they are too slow. That fact is addressed in http://howardhinnant.github.io/onvectorbool.html, backed up by performance measurements.

The paper compares the algorithms for 3 cases:

A. A hypothetical non-specialized vector<bool> // an array of bools
B. A hypothetical bit_vector<> // algorithms specialized on bit_iterator
C. A hypothetical bit_vector<> using the unoptimized generic algorithms // what is common today for vector<bool>

Case B is the one with screaming performance. Case A and C are both relatively slow and for completely different reasons. A is slow because it caches in too much data (a byte instead of a bit). C is slow because it reads/writes one bit at a time.

B is fast is because it operates on a word of bits at a time.

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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vincent Reverdy
2016-01-22 22:24:12 UTC
Permalink
Hello everyone and thanks again for all the useful points that were
discussed.

I updated the proposal accordingly, with an alternative technical
specifications (no arithmetic behaviour).
However, I maintain my position concerning the fact that a bit and a bool
are two different things, mixing them up have led to the design of
std::vector<bool>, the same approach was not applied for std::array (if a
bit were a bool, then std::bitset and std::array should be the same class,
and I am glad we have both), and the arithmetic of bools are particularly
error-prone. Introducing a std::bit_value (or std::bit, if we want to name
it that way) allow to avoid this confusion, and I think it is particularly
important.

Vincent
Post by Howard Hinnant
Post by Jens Maurer
Post by Howard Hinnant
Post by Jens Maurer
Agreed, but people have come to live with "bool" for 15+ years.
Is the "bool" situation bad enough to spend time + effort of
lots of people to standardize bit_value? As I said, I'm looking
for use-cases (what practical higher-level problems are solved
with bit_value), and not "preferred options" at this time.
Here are performance numbers that show when algorithms are modified to
take advantage of the bit-string data structure, significant performance
optimizations (order of magnitude) over an array of bools can be had.
find, count, copy, fill, rotate are examples of such algorithms and not a
complete list.
Post by Jens Maurer
Post by Howard Hinnant
This proposal may be the first stepping stone towards realizing such
portable high-performance algorithms.
Post by Jens Maurer
Yes, agreed.
Do those algorithms need bit_value as an rvalue representation
of a bit, or would they work with plain bool for this purpose, too?
(The algorithms you mentioned might need to be specialized
for bit_iterator, and/or bit_iterator needs a wider
interface to expose the underlying unsigned integer.)
To be perfectly transparent, I’m only tangentially following this
thread/proposal (because of time constraints).
The algorithms definitely need to be specialized for bit_iterator, and
bit_iterator must expose a wider interface than a normal iterator. If the
algorithms see bools, they are too slow. That fact is addressed in
http://howardhinnant.github.io/onvectorbool.html, backed up by
performance measurements.
A. A hypothetical non-specialized vector<bool> // an array of bools
B. A hypothetical bit_vector<> // algorithms specialized on bit_iterator
C. A hypothetical bit_vector<> using the unoptimized generic algorithms //
what is common today for vector<bool>
Case B is the one with screaming performance. Case A and C are both
relatively slow and for completely different reasons. A is slow because it
caches in too much data (a byte instead of a bit). C is slow because it
reads/writes one bit at a time.
B is fast is because it operates on a word of bits at a time.
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
David Krauss
2016-01-27 04:55:38 UTC
Permalink
Hello everyone and thanks again for all the useful points that were discussed.
I updated the proposal accordingly, with an alternative technical specifications (no arithmetic behaviour).
However, I maintain my position concerning the fact that a bit and a bool are two different things, mixing them up have led to the design of std::vector<bool>, the same approach was not applied for std::array (if a bit were a bool, then std::bitset and std::array should be the same class, and I am glad we have both),
Are you proposing that std::vector<bit_value> and std::array<bit_value> will have packed representation? If not, bit_value and bool will be doing the same thing.
and the arithmetic of bools are particularly error-prone. Introducing a std::bit_value (or std::bit, if we want to name it that way) allow to avoid this confusion, and I think it is particularly important.
As mentioned, bool is broken by integer promotion, which equally harms all narrow integer types. Why not address short too?

Before looking at this thread, I tried to find the motivation for bit_value in the proposal. It repeatedly says that it “implements arithmetic behavior” and mentions “non-referenced,” and it goes into technical implementation details. But there’s no mention of what goes wrong if bool is used instead. The phrase “arithmetic behaviour of a one-digit long unsigned integer” is very unclear. C++ unfortunately doesn’t currently have classes that implement values but not persistent objects.

The proposal goes right to a synopsis which includes bit_value::operator+= and bit_value::operator-=. Even %= and /=! There’s no discussion of their semantics. I guess that %= calls clear iff the RHS equals 1. There are no binary ordinary arithmetic operators, and increment and decrement are included even though the former is already being removed and the latter never existed in ISO C++ for bool.

Since it defines an implicit conversion to bool, and no value-semantic binary operators, it fails to avoid integer promotion. (bitv[0] | bitv[3]) will still have type int. Either the synopsis doesn’t reflect what was prototyped, or the prototype wasn’t tested very well, or the problem isn’t really so severe in the first place.

bit_value needs to be either removed or redesigned. Either way, proposal should explain the design space in terms of trade-offs with examples.
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vincent Reverdy
2016-01-27 17:59:42 UTC
Permalink
Hello.
Thanks for the comments.

I started to reimplement the std::algorithms for bit_iterators and measured
the speedups compared to std::vector<bool>.
I am going to release a graph to summarize some of my tests.
On my platform, bit_iterators are about 80 faster than std::vector<bool>
for std::count, about 600x faster for std::sort, and about 450x faster for
std::rotate, about 40x faster for std::reverse, and about 150x faster for
std::fill (g++5.3 -O3 -mpopcnt)

As explained in the proposal, I can come up with two designs for
std::bit_value. One which enable “arithmetic behaviour of a one-digit long
unsigned integer”, in the same way that a byte implements the “arithmetic
behaviour of a eight-digit (most of the time) long unsigned integer”
through unsigned char. bit1 | bit2 would produce an int, in the same way
that byte1 | byte2 would produce an int. It mimics a narrow type, and as
is, follows the rule of the current C++ standard. What is different with a
bool is that bool1 += 3 sets bool1 to true, whereas bit1 += 3, flips the
bit three times (modulo 2 arithmetic, is the same way byte1 += 1025 would
use a modulo 256 arithmetic). I will try to make that clearer. The
alternative design that uses bit_value to prevent all arithmetic operations
is also an elegant alternative. At least it makes things very clear. I am
just very incomfortable with someone doing (*bit_iterator) =
~(*bit_iterator) and ending up with the same value, or (*bit_iterator) <<=
(*bit_iterator) (bit shift... of a bit) and ending up with the same value
because of the arithmetic of bool...
Hello everyone and thanks again for all the useful points that were discussed.
I updated the proposal accordingly, with an alternative technical
specifications (no arithmetic behaviour).
However, I maintain my position concerning the fact that a bit and a bool
are two different things, mixing them up have led to the design of
std::vector<bool>, the same approach was not applied for std::array (if a
bit were a bool, then std::bitset and std::array should be the same class,
and I am glad we have both),
Are you proposing that std::vector<bit_value> and std::array<bit_value>
will have packed representation? If not, bit_value and bool will be doing
the same thing.
and the arithmetic of bools are particularly error-prone. Introducing a
std::bit_value (or std::bit, if we want to name it that way) allow to avoid
this confusion, and I think it is particularly important.
As mentioned, bool is broken by integer promotion, which equally harms
all narrow integer types. Why not address short too?
Before looking at this thread, I tried to find the motivation for
bit_value in the proposal. It repeatedly says that it “implements
arithmetic behavior” and mentions “non-referenced,” and it goes into
technical implementation details. But there’s no mention of what goes wrong
if bool is used instead. The phrase “arithmetic behaviour of a one-digit
long unsigned integer” is very unclear. C++ unfortunately doesn’t currently
have classes that implement values but not persistent objects.
The proposal goes right to a synopsis which includes bit_value::operator+=
and bit_value::operator-=. Even %= and /=! There’s no discussion of their
semantics. I guess that %= calls clear iff the RHS equals 1. There are no
binary ordinary arithmetic operators, and increment and decrement are
included even though the former is already being removed and the latter
never existed in ISO C++ for bool.
Since it defines an implicit conversion to bool, and no value-semantic
binary operators, it fails to avoid integer promotion. (bitv[0] | bitv[3])
will still have type int. Either the synopsis doesn’t reflect what was
prototyped, or the prototype wasn’t tested very well, or the problem isn’t
really so severe in the first place.
bit_value needs to be either removed or redesigned. Either way, proposal
should explain the design space in terms of trade-offs with examples.
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Ville Voutilainen
2016-01-27 18:02:29 UTC
Permalink
Post by Vincent Reverdy
Hello.
Thanks for the comments.
I started to reimplement the std::algorithms for bit_iterators and measured
the speedups compared to std::vector<bool>.
I am going to release a graph to summarize some of my tests.
On my platform, bit_iterators are about 80 faster than std::vector<bool> for
std::count, about 600x faster for std::sort, and about 450x faster for
std::rotate, about 40x faster for std::reverse, and about 150x faster for
std::fill (g++5.3 -O3 -mpopcnt)
Just out of curiosity, does this vector<bool> your comparing against have
specializations for the aforementioned algorithms?
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Ville Voutilainen
2016-01-27 18:04:46 UTC
Permalink
On 27 January 2016 at 20:02, Ville Voutilainen
Post by Ville Voutilainen
Post by Vincent Reverdy
Hello.
Thanks for the comments.
I started to reimplement the std::algorithms for bit_iterators and measured
the speedups compared to std::vector<bool>.
I am going to release a graph to summarize some of my tests.
On my platform, bit_iterators are about 80 faster than std::vector<bool> for
std::count, about 600x faster for std::sort, and about 450x faster for
std::rotate, about 40x faster for std::reverse, and about 150x faster for
std::fill (g++5.3 -O3 -mpopcnt)
Just out of curiosity, does this vector<bool> your comparing against have
specializations for the aforementioned algorithms?
*you're and all that..
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vincent Reverdy
2016-01-27 18:32:56 UTC
Permalink
Given the speed-ups I have, I would say no.
The timestamp of my libstdc++ I use is: 20151204.
The goal of this proposal is not to rewrite std::vector<bool>, even if it
could be a side effect of it for standard library implementers.
The goal is to provide very basic tools to developers who need full
performance on bit manipulation... because now, using a std::vector<bool>
is probably not a good idea given the speedup we can have with with a
bit_iterator.
Post by Ville Voutilainen
On 27 January 2016 at 20:02, Ville Voutilainen
Post by Ville Voutilainen
Post by Vincent Reverdy
Hello.
Thanks for the comments.
I started to reimplement the std::algorithms for bit_iterators and
measured
Post by Ville Voutilainen
Post by Vincent Reverdy
the speedups compared to std::vector<bool>.
I am going to release a graph to summarize some of my tests.
On my platform, bit_iterators are about 80 faster than
std::vector<bool> for
Post by Ville Voutilainen
Post by Vincent Reverdy
std::count, about 600x faster for std::sort, and about 450x faster for
std::rotate, about 40x faster for std::reverse, and about 150x faster
for
Post by Ville Voutilainen
Post by Vincent Reverdy
std::fill (g++5.3 -O3 -mpopcnt)
Just out of curiosity, does this vector<bool> your comparing against
have
Post by Ville Voutilainen
specializations for the aforementioned algorithms?
*you're and all that..
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Ville Voutilainen
2016-01-27 18:39:57 UTC
Permalink
Post by Vincent Reverdy
Given the speed-ups I have, I would say no.
The timestamp of my libstdc++ I use is: 20151204.
The goal of this proposal is not to rewrite std::vector<bool>, even if it
could be a side effect of it for standard library implementers.
The goal is to provide very basic tools to developers who need full
performance on bit manipulation... because now, using a std::vector<bool> is
probably not a good idea given the speedup we can have with with a
bit_iterator.
You might want to compare against libc++ anyway, I got the impression
that Howard
did such algorithm specializations for vector<bool> with performance
as the main target.
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vincent Reverdy
2016-01-27 18:57:41 UTC
Permalink
I am not used to test with libc++.
I just compiled with: clang++-3.5 -std=c++14 -Wall -Wextra -pedantic -O3 -g
-march=native -stdlib=libc++ bit.cpp -o bit -nodefaultlibs -lc++ -lc++abi
-lm -lc -lgcc_s -lgcc
and just got a factor of 178 (instead of 150x) for std::fill.
I will release a very preliminary version of the library soon, so everyone
could test.
Post by Vincent Reverdy
Post by Vincent Reverdy
Given the speed-ups I have, I would say no.
The timestamp of my libstdc++ I use is: 20151204.
The goal of this proposal is not to rewrite std::vector<bool>, even if
it
Post by Vincent Reverdy
could be a side effect of it for standard library implementers.
The goal is to provide very basic tools to developers who need full
performance on bit manipulation... because now, using a
std::vector<bool> is
Post by Vincent Reverdy
probably not a good idea given the speedup we can have with with a
bit_iterator.
You might want to compare against libc++ anyway, I got the impression
that Howard
did such algorithm specializations for vector<bool> with performance
as the main target.
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vincent Reverdy
2016-01-29 22:45:04 UTC
Permalink
Quick question: to whom should I write to have a document number (I was
used to the ancient numbering system)?
Post by Vincent Reverdy
I am not used to test with libc++.
I just compiled with: clang++-3.5 -std=c++14 -Wall -Wextra -pedantic -O3
-g -march=native -stdlib=libc++ bit.cpp -o bit -nodefaultlibs -lc++
-lc++abi -lm -lc -lgcc_s -lgcc
and just got a factor of 178 (instead of 150x) for std::fill.
I will release a very preliminary version of the library soon, so everyone
could test.
Post by Vincent Reverdy
Post by Vincent Reverdy
Given the speed-ups I have, I would say no.
The timestamp of my libstdc++ I use is: 20151204.
The goal of this proposal is not to rewrite std::vector<bool>, even if
it
Post by Vincent Reverdy
could be a side effect of it for standard library implementers.
The goal is to provide very basic tools to developers who need full
performance on bit manipulation... because now, using a
std::vector<bool> is
Post by Vincent Reverdy
probably not a good idea given the speedup we can have with with a
bit_iterator.
You might want to compare against libc++ anyway, I got the impression
that Howard
did such algorithm specializations for vector<bool> with performance
as the main target.
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Ville Voutilainen
2016-01-29 22:47:51 UTC
Permalink
Quick question: to whom should I write to have a document number (I was used
to the ancient numbering system)?
To lwgchair, like before.
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vincent Reverdy
2016-02-07 01:15:50 UTC
Permalink
<Loading Image...>
Just as an aside note, I finished a first implementation and tested the
performances against std::vector<bool>.
Here are the results.
The speedups are in the boxes at the top of the image.
The vertical axis is logarithmic...
I will add it to the proposal.
Post by Ville Voutilainen
Post by Vincent Reverdy
Quick question: to whom should I write to have a document number (I was
used
Post by Vincent Reverdy
to the ancient numbering system)?
To lwgchair, like before.
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vicente J. Botet Escriba
2016-02-07 10:43:16 UTC
Permalink
Post by Vincent Reverdy
<https://lh3.googleusercontent.com/--3-iyp-ouy4/VraZ8DWpPcI/AAAAAAAABZQ/CoSbzky4MHU/s1600/bit_log.png>
Just as an aside note, I finished a first implementation and tested
the performances against std::vector<bool>.
Here are the results.
The speedups are in the boxes at the top of the image.
The vertical axis is logarithmic...
I will add it to the proposal.
Do you have figures for specialized algorithms for vector<bool>?

Vicente
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Nick Pelling
2016-02-07 13:44:48 UTC
Permalink
Hi everyone,

May I ask if there has already been a proposal to allow individual
array dimensions to be typed? I'm specifically thinking of enums here, e.g.:

enum Channel
{
Channel_A,
Channel_B
};

// Declare array large enough to contain all legal Channel values
(i.e. 2 elements)
uint32_t ChannelStatus[auto : Channel];

if (ChannelStatus[Channel_A]) {} // compiler happy
if (ChannelStatus[0]) {} // compiler warning or error (TBD)

Here, not only does the enum declaration drive the size of the
dimension of the array directly, but the compiler also warns the
programmer when an incorrect enum type is used to index into that
array dimension.

Naturally, the same mechanism would scale to the different dimensions
of a multi-dimensional array etc.

Thanks, Nick


---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vishal Oza
2016-02-07 16:05:02 UTC
Permalink
Post by Nick Pelling
Hi everyone,
May I ask if there has already been a proposal to allow individual
enum Channel
{
Channel_A,
Channel_B
};
// Declare array large enough to contain all legal Channel values
(i.e. 2 elements)
uint32_t ChannelStatus[auto : Channel];
if (ChannelStatus[Channel_A]) {} // compiler happy
if (ChannelStatus[0]) {} // compiler warning or
error (TBD)
Here, not only does the enum declaration drive the size of the
dimension of the array directly, but the compiler also warns the
programmer when an incorrect enum type is used to index into that
array dimension.
Naturally, the same mechanism would scale to the different dimensions
of a multi-dimensional array etc.
Thanks, Nick
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
While I like your idea and it suggestion might work in the general case
what would it do if someone assigned enum values?
For example:

enum MessageStatus
{
ErrorDetected = -1,
GoodMessage = 0,
BadMessage = 1,
WarningMessage = 2,
ProcessMessage = 17
};

uint32_t MessageReceivedCount[auto : Channel]; //what is the size of the
array 4, 5, 17 or 18

if(MessageStatus[ErrorDetected] > 20'000) // Is
"MessageStatus[ErrorDetected]" an error, valid code or undefined behavior?
{
std::cout <<"Program is unstable\n";
}
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Andrew Tomazos
2016-02-07 16:41:30 UTC
Permalink
I think what you want is unordered_map<Channel, ChannelStatus>. This has
the same asymptotic performance as an array, and will also deal with
irregular enumeration values (ie when they are spread out sparsely, and not
contiguous).

At least, I currently don't see the significant advantage of what you are
proposing over that type.
Post by Nick Pelling
Hi everyone,
May I ask if there has already been a proposal to allow individual array
enum Channel
{
Channel_A,
Channel_B
};
// Declare array large enough to contain all legal Channel values
(i.e. 2 elements)
uint32_t ChannelStatus[auto : Channel];
if (ChannelStatus[Channel_A]) {} // compiler happy
if (ChannelStatus[0]) {} // compiler warning or
error (TBD)
Here, not only does the enum declaration drive the size of the dimension
of the array directly, but the compiler also warns the programmer when an
incorrect enum type is used to index into that array dimension.
Naturally, the same mechanism would scale to the different dimensions of a
multi-dimensional array etc.
Thanks, Nick
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
--
--- 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
Visit this group at
https://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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
maurice barnum
2016-02-07 18:52:56 UTC
Permalink
I have yet to encounter a situation where an enum->thing map should be
implemented as an unordered_map<>. Most of these mappings are for
a small set of contiguous enums, where the proposal would be beneficial:
you're not going to beat a direct index with any sort of search.

Assuming that indexing isn't appropriate (maintenance cost in the
current language, or a sparse enumeration for some dumb reason), better
solutions to unordered_map<E,V> exist now:

* vector<pair<E,V>> : for small enumerations, linear search is hard
to beat. for modest sized enumerations, sort once (before
compiling) and use binary search. I don't know what N is for
"modest"; for string keys it's somewhere around 20 on x86
hardware, I expect for integers it'd be in the low hundreds.
There's no reason to guess: measure.

* gperf-generated, or similar, perfect hash for large enumerations.

map<E,V> or unordered_map<E,V> are great when you want something
"pretty good" that's easy to implement and the performance isn't
critical. Which is faster is likely a matter of cache friendliness,
not computational overhead. If you care enough to measure, I
suggest you use a something else.

note: I find the proosal problematic, and I'm not convinced
this is a problem that needs to be solved. I'm responding to your
"unordered_map" suggestion.
Post by Andrew Tomazos
I think what you want is unordered_map<Channel, ChannelStatus>. This
has the same asymptotic performance as an array, and will also deal with
irregular enumeration values (ie when they are spread out sparsely, and
not contiguous).
At least, I currently don't see the significant advantage of what you
are proposing over that type.
On Sun, Feb 7, 2016 at 2:44 PM, Nick Pelling
Hi everyone,
May I ask if there has already been a proposal to allow individual
enum Channel
{
Channel_A,
Channel_B
};
// Declare array large enough to contain all legal Channel
values (i.e. 2 elements)
uint32_t ChannelStatus[auto : Channel];
if (ChannelStatus[Channel_A]) {} // compiler happy
if (ChannelStatus[0]) {} // compiler warning
or error (TBD)
Here, not only does the enum declaration drive the size of the
dimension of the array directly, but the compiler also warns the
programmer when an incorrect enum type is used to index into that
array dimension.
Naturally, the same mechanism would scale to the different
dimensions of a multi-dimensional array etc.
Thanks, Nick
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
--
--- 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,
Visit this group at
https://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
Visit this group at
https://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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Tony V E
2016-02-07 20:59:49 UTC
Permalink
Maybe someone should wrap all of that up into a single class that just 'does the right thing' based on size etc.

Sent from my BlackBerry portable Babbage Device
  Original Message  
From: maurice barnum
Sent: Sunday, February 7, 2016 1:53 PM
To: std-***@isocpp.org
Reply To: std-***@isocpp.org
Subject: [std-proposals] Re: Typed array dimensions...?

I have yet to encounter a situation where an enum->thing map should be
implemented as an unordered_map<>. Most of these mappings are for
a small set of contiguous enums, where the proposal would be beneficial:
you're not going to beat a direct index with any sort of search.

Assuming that indexing isn't appropriate (maintenance cost in the
current language, or a sparse enumeration for some dumb reason), better
solutions to unordered_map<E,V> exist now:

* vector<pair<E,V>> : for small enumerations, linear search is hard
to beat. for modest sized enumerations, sort once (before
compiling) and use binary search. I don't know what N is for
"modest"; for string keys it's somewhere around 20 on x86
hardware, I expect for integers it'd be in the low hundreds.
There's no reason to guess: measure.

* gperf-generated, or similar, perfect hash for large enumerations.

map<E,V> or unordered_map<E,V> are great when you want something
"pretty good" that's easy to implement and the performance isn't
critical. Which is faster is likely a matter of cache friendliness,
not computational overhead. If you care enough to measure, I
suggest you use a something else.

note: I find the proosal problematic, and I'm not convinced
this is a problem that needs to be solved. I'm responding to your
"unordered_map" suggestion.
I think what you want is unordered_map<Channel, ChannelStatus>. This
has the same asymptotic performance as an array, and will also deal with
irregular enumeration values (ie when they are spread out sparsely, and
not contiguous).
At least, I currently don't see the significant advantage of what you
are proposing over that type.
On Sun, Feb 7, 2016 at 2:44 PM, Nick Pelling
Hi everyone,
May I ask if there has already been a proposal to allow individual
enum Channel
{
Channel_A,
Channel_B
};
// Declare array large enough to contain all legal Channel
values (i.e. 2 elements)
uint32_t ChannelStatus[auto : Channel];
if (ChannelStatus[Channel_A]) {} // compiler happy
if (ChannelStatus[0]) {} // compiler warning
or error (TBD)
Here, not only does the enum declaration drive the size of the
dimension of the array directly, but the compiler also warns the
programmer when an incorrect enum type is used to index into that
array dimension.
Naturally, the same mechanism would scale to the different
dimensions of a multi-dimensional array etc.
Thanks, Nick
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
--
--- 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,
Visit this group at
https://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
Visit this group at
https://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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Vincent Reverdy
2016-02-12 07:33:12 UTC
Permalink
Here is the submitted proposal (version attached).
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Tomasz
2016-01-21 12:35:52 UTC
Permalink
I have one comment regarding the bit_value class, I think that it should be
also templated for the UnderliningType with default being equal unsigned
char.

This may be very usefull in case of developing an real bit_vector class
that would use U as underlining type. In this situation if we define
ValueType of bit_vector to be bit_value<U> and its ReferenceType to be
bit_reference<U>, then single bit_reference<U> could be used to point both
to ValueType and container element. This would simplify the proxy iterator
design as proposed by Eric Niebler
(http://ericniebler.com/2015/02/13/iterators-plus-plus-part-2/). For
further details you may check my (tkamin) comment bellow post I have linked.


W dniu środa, 20 stycznia 2016 21:58:07 UTC+1 uÅŒytkownik Vincent Reverdy
Post by Vincent Reverdy
Hello again everyone.
I've finally implemented a lot of changes in that proposal.
This time, it looks good to me in the sense that it discuss a lot of
different possible approaches.
Critics, comments and code reviews (for the classes synopsis) are very
welcome.
Best,
Vincent
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Moritz Klammler
2016-02-07 02:32:05 UTC
Permalink
Post by Vincent Reverdy
<https://lh3.googleusercontent.com/--3-iyp-ouy4/VraZ8DWpPcI/AAAAAAAABZQ/CoSbzky4MHU/s1600/bit_log.png>
Just as an aside note, I finished a first implementation and tested the
performances against std::vector<bool>.
Here are the results.
The speedups are in the boxes at the top of the image.
The vertical axis is logarithmic...
I will add it to the proposal.
These numbers are really impressive. Almost hard to believe. I think
it would be very interesting if you could also add a third column for
`std::vector<unsigned>` (or maybe `unsigned char`?) if that is not too
much work. I have seen people use these types to avoid the
`std::vector<bool>` specialization so it might be interesting how they
compare.
--
OpenPGP:

Public Key: http://openpgp.klammler.eu
Fingerprint: 2732 DA32 C8D0 EEEC A081 BE9D CF6C 5166 F393 A9C0
--
---
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+***@isocpp.org.
To post to this group, send email to std-***@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
Loading...