[gsoc] Pointer Plus Bits Behavior and Interface
Hello, Pointer Plus Bits: Is a data structure which points to specifically aligned object such that the value of the address is divisible by a power of two (the power of two which it is divisible by is given as a template argument). The empty bits of the pointer are then used to store extra boolean values relating to something (This is of the programmers choosing but it would seem best practice to make it related to the object being pointed at). The technique is of storing extra bits inside of pointers is some times referred to as bit stuffing. Clang uses this technique for their QualType pointer: http://clang.llvm.org/doxygen/classclang_1_1QualType.html So here are some of the questions I would like to pose to the community about the behavior and interface of the pointer_plus_bits data structure: 1) Should the pointer_plus_bits have a pre and post increment and decrement ( what about supporting other arithmetic operations such as add, minus, add assign etc...) ? One could do this if the sizeof the type is evenly divisible by 2 to the number of bits being "stuffed". The next/previous object in the array being traversed could be correctly pointed at (assuming that the item being pointed at IS an array). 1.a) If this is a behavior supported by the pointer_plus_bits should it keep the bits being stuffed or set them to zero each time? 2) Should the bits being stuffed apply during comparison? 3) Should the pointer provide compatibility between itself and pointer of the same type that is being stuffed (the behavior of this would mean masking out the pointer so the stuffed bits won't apply during the comparison)? (ie Should pointer_plus_bits<T,2> be comparable to T* ?) (in pointer_plus_bits 2 is the number of bits being stuffed). -- thanks, Brian Bartman
Brian Bartman <bbartmanboost <at> gmail.com> writes:
Hello,
Pointer Plus Bits: Is a data structure which points to specifically aligned object such that the value of the address is divisible by a power of two (the power of two which it is divisible by is given as a template argument). The empty bits of the pointer are then used to store extra boolean values relating to something [...]
FYI, there's some code at http://bannalia.blogspot.com/2008/11/optimizing-red-black-tree-color-bits.ht... that you might want to leverage for your work.
1) Should the pointer_plus_bits have a pre and post increment and decrement ( what about supporting other arithmetic operations such as add, minus, add assign etc...) ?
I'd say this is gratuituous complication: just design a lean interface providing get_pointer, set_pointer, get_bit, set_bit (or similar names) so that you don't have to replicate pointer semantics. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On 15/07/2010 16:27, Joaquin M Lopez Munoz wrote:
Brian Bartman<bbartmanboost<at> gmail.com> writes:
Hello,
Pointer Plus Bits: Is a data structure which points to specifically aligned object such that the value of the address is divisible by a power of two (the power of two which it is divisible by is given as a template argument). The empty bits of the pointer are then used to store extra boolean values relating to something [...]
FYI, there's some code at
http://bannalia.blogspot.com/2008/11/optimizing-red-black-tree-color-bits.ht...
that you might want to leverage for your work.
some more code: http://www.boost.org/doc/libs/1_43_0/doc/html/intrusive/reference.html#heade... Best, Ion
2010/7/15 Ion Gaztañaga <igaztanaga@gmail.com>
some more code:
http://www.boost.org/doc/libs/1_43_0/doc/html/intrusive/reference.html#heade...
Thanks for the link. -- thanks, Brian Bartman
On Thu, Jul 15, 2010 at 10:27 AM, Joaquin M Lopez Munoz <joaquin@tid.es>wrote:
Brian Bartman <bbartmanboost <at> gmail.com> writes:
Hello,
Pointer Plus Bits: Is a data structure which points to specifically aligned object such that the value of the address is divisible by a power of two (the power of two which it is divisible by is given as a template argument). The empty bits of the pointer are then used to store extra boolean values relating to something [...]
FYI, there's some code at
http://bannalia.blogspot.com/2008/11/optimizing-red-black-tree-color-bits.ht...
that you might want to leverage for your work.
Thank you for the link. I did have that in my original proposal as it was one of the best examples for just how much space can be saved by using this technique.
1) Should the pointer_plus_bits have a pre and post increment and decrement ( what about supporting other arithmetic operations such as add, minus, add assign etc...) ?
I'd say this is gratuituous complication: just design a lean interface providing get_pointer, set_pointer, get_bit, set_bit (or similar names) so that you don't have to replicate pointer semantics.
So you suggest that I may be going overboard. OK, I'm OK with less work it just means I have more time to spend on testing. Thanks for the quick reply.
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- thanks, Brian Bartman
Zitat von Joaquin M Lopez Munoz <joaquin@tid.es>:
1) Should the pointer_plus_bits have a pre and post increment and decrement ( what about supporting other arithmetic operations such as add, minus, add assign etc...) ?
I'd say this is gratuituous complication: just design a lean interface providing get_pointer, set_pointer, get_bit, set_bit (or similar names) so that you don't have to replicate pointer semantics.
I'd say an interface with pointer semantics is useful, but can be built upon the a interface like you're describing. for example: pointer_plus_bits<...> a; to access the pointer part: pointer_view<...> ptr(a); //++ptr; //ptr has ptr-semantics, can be used as an iterator, etc. to access the "bits" part: integral_view<...> i(a); i=3; bitset_view<...> bitset(a); bitset.set(2,true); I'm also wondering why this has to be limited to pointer plus bits? unused bits in a variable isn't something that is limited to pointers. an integer variable might always be even, or have a maximum value so that upper bits are always unused.
On Thu, Jul 15, 2010 at 11:19 AM, Stefan Strasser <strasser@uni-bremen.de>wrote:
I'd say an interface with pointer semantics is useful, but can be built upon the a interface like you're describing. for example:
pointer_plus_bits<...> a;
to access the pointer part: pointer_view<...> ptr(a); //++ptr; //ptr has ptr-semantics, can be used as an iterator, etc.
to access the "bits" part: integral_view<...> i(a); i=3;
bitset_view<...> bitset(a); bitset.set(2,true);
I'm also wondering why this has to be limited to pointer plus bits?
Some of the other portions of my work may better address your concern. Specifically, a bitfield_tuple allows you do to close to what you're suggesting. However the genericness of the data structure still needs to be expanded slightly to allow the data structure to handle custom setting and retrieval of user specified fields (such as in the above case pointer).
unused bits in a variable isn't something that is limited to pointers. an integer variable might always be even, or have a maximum value so that upper bits are always unused.
I completely agree. -- thanks, Brian Bartman
Stefan Strasser wrote:
Zitat von Joaquin M Lopez Munoz <joaquin@tid.es>:
1) Should the pointer_plus_bits have a pre and post increment and decrement ( what about supporting other arithmetic operations such as add, minus, add assign etc...) ?
I'd say this is gratuituous complication: just design a lean interface providing get_pointer, set_pointer, get_bit, set_bit (or similar names) so that you don't have to replicate pointer semantics.
I'd say an interface with pointer semantics is useful, but can be built upon the a interface like you're describing. for example:
pointer_plus_bits<...> a;
to access the pointer part: pointer_view<...> ptr(a); //++ptr; //ptr has ptr-semantics, can be used as an iterator, etc.
to access the "bits" part: integral_view<...> i(a); i=3;
bitset_view<...> bitset(a); bitset.set(2,true);
+1 _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Joaquin M Lopez Munoz wrote:
Brian Bartman <bbartmanboost <at> gmail.com> writes:
1) Should the pointer_plus_bits have a pre and post increment and decrement ( what about supporting other arithmetic operations such as add, minus, add assign etc...) ?
I'd say this is gratuituous complication: just design a lean interface providing get_pointer, set_pointer, get_bit, set_bit (or similar names) so that you don't have to replicate pointer semantics.
I was going to disagree, but I think that Stefan has the right answer: views. There are two interfaces to support in this class: the pointer and the extra bits. Trying to mix the two will complicate the interface and likely cause ambiguities and unwanted interactions. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Pointer Plus Bits: Is a data structure which points to specifically aligned object such that the value of the address is divisible by a power of two (the power of two which it is divisible by is given as a template argument). The empty bits of the pointer are then used to store extra boolean values relating to something (This is of the programmers choosing but it would seem best practice to make it related to the object being pointed at).
Hi Brian,
1) Should the pointer_plus_bits have a pre and post increment and decrement ( what about supporting other arithmetic operations such as add, minus, add assign etc...) ?
1.a) If this is a behavior supported by the pointer_plus_bits should it keep
the bits being stuffed or set them to zero each time?
I don't think this class implement arithmetic operations because the extra bits typically apply to the referenced object and not the pointer itself. Here you have a case where the pointer and value type can't be arbitrarily decoupled (the pointer is part of the value) and so these operations don't make much sense.
2) Should the bits being stuffed apply during comparison?
Contrary to what I've just said, you could implement comparisons using the pointers alone and excluding the bits. I think this would be reasonable. Consider a comparison to nullptr (or (void*)0).
3) Should the pointer provide compatibility between itself and pointer of the same type that is being stuffed (the behavior of this would mean masking out the pointer so the stuffed bits won't apply during the comparison)? (ie Should pointer_plus_bits<T,2> be comparable to T* ?) (in pointer_plus_bits 2 is the number of bits being stuffed).
In general, I would say no. I think a non-explicit constructor taking T* and a get() member should be sufficient. I think that should cover most of your interoperability concerns, but I'm just guessing here. Andrew Sutton andrew.n.sutton@gmail.com
On Thu, Jul 15, 2010 at 10:55 AM, Andrew Sutton <andrew.n.sutton@gmail.com>wrote:
2) Should the bits being stuffed apply during comparison?
Contrary to what I've just said, you could implement comparisons using the pointers alone and excluding the bits. I think this would be reasonable. Consider a comparison to nullptr (or (void*)0).
Would it be better to make the pointer_plus_bits convertible to a boolean based on the value of the pointer being stored? This would allow it to be more like to a pointer being that you could, as many people do, put it inside of an if statement to check to see if its null. -- thanks, Brian Bartman
Contrary to what I've just said, you could implement comparisons using the pointers alone and excluding the bits. I think this would be reasonable. Consider a comparison to nullptr (or (void*)0).
Would it be better to make the pointer_plus_bits convertible to a boolean based on the value of the pointer being stored? This would allow it to be more like to a pointer being that you could, as many people do, put it inside of an if statement to check to see if its null.
Actually, yes. I think that would be a better idea :) Andrew Sutton andrew.n.sutton@gmail.com
Brian Bartman <bbartmanboost <at> gmail.com> writes:
Would it be better to make the pointer_plus_bits convertible to a boolean based on the value of the pointer being stored? This would allow it to be more like to a pointer being that you could, as many people do, put it inside of an if statement to check to see if its null.
Converting to bool can be problematic, as throughly explained at http://www.informit.com/articles/article.aspx?p=31529&seqNum=8 The optimum way to do this is to convert to a pointer of a private type which is null if and only if the stored pointer is null. This is explained also at the reference above and it's the way boost::shared_ptr implements "conversion to bool semantics" (take a look at the source for inspiration). Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Thu, Jul 15, 2010 at 12:07 PM, Joaquin M Lopez Munoz <joaquin@tid.es>wrote:
Converting to bool can be problematic, as throughly explained at
http://www.informit.com/articles/article.aspx?p=31529&seqNum=8
The optimum way to do this is to convert to a pointer of a private type which is null if and only if the stored pointer is null. This is explained also at the reference above and it's the way boost::shared_ptr implements "conversion to bool semantics" (take a look at the source for inspiration).
OK I'll read it over throughly. Thank you for the link.
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- thanks, Brian Bartman
Brian Bartman wrote:
Would it be better to make the pointer_plus_bits convertible to a boolean based on the value of the pointer being stored? This would allow it to be more like to a pointer being that you could, as many people do, put it inside of an if statement to check to see if its null.
No. One could argue that the bits should be evaluated to produce the Boolean result as easily as evaluating the pointer. There are two aspects in pointer_plus_bits and they shouldn't be obscured or conflated. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
On Thu, Jul 15, 2010 at 12:08 PM, Stewart, Robert <Robert.Stewart@sig.com>wrote:
Brian Bartman wrote:
Would it be better to make the pointer_plus_bits convertible to a boolean based on the value of the pointer being stored? This would allow it to be more like to a pointer being that you could, as many people do, put it inside of an if statement to check to see if its null.
No. One could argue that the bits should be evaluated to produce the Boolean result as easily as evaluating the pointer. There are two aspects in pointer_plus_bits and they shouldn't be obscured or conflated.
So what your saying in this one in this email and the one above is that there is a distinct need for two interfaces. One for the pointer and one for the bits. Which can be done using the veiw's suggested by Zitat von Joaquin's response. I see your point that there is a definite need for multiple interfaces due to the mixing of different items within the data. It really does leave room for ambiguity in behavior if you only have one interface.
_____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com
IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- thanks, Brian Bartman
Would it be better to make the pointer_plus_bits convertible to a boolean based on the value of the pointer being stored? This would allow it to be more like to a pointer being that you could, as many people do, put it inside of an if statement to check to see if its null.
No. One could argue that the bits should be evaluated to produce the Boolean result as easily as evaluating the pointer. There are two aspects in pointer_plus_bits and they shouldn't be obscured or conflated.
I strongly disagree with using views in the design of this data structure. It's not such a complex concept that you would need to explicitly decouple its concerns via views. You end up designing a pointer+bits that can't be used natively as a pointer or bits. The data structure is pointer_(plus_bits). First and foremost, I would expect its instances to model (at least some) Pointer semantics, which includes "if(p)" and not "if(pointer_view<...>(p))". Dereferencing the pointer returns the object being pointed at--although it could also return a pair with the object and extra bits, which might be kind of neat. Otherwise, I suspect that providing a small set of member functions to interact with the bitfield would be perfectly acceptable. Andrew Sutton andrew.n.sutton@gmail.com
On Jul 15, 2010, at 1:09 PM, Andrew Sutton wrote:
One could argue that the bits should be evaluated to produce the Boolean result as easily as evaluating the pointer. There are two aspects in pointer_plus_bits and they shouldn't be obscured or conflated.
I strongly disagree with using views in the design of this data structure. It's not such a complex concept that you would need to explicitly decouple its concerns via views. You end up designing a pointer+bits that can't be used natively as a pointer or bits.
I agree with Andrew. Somebody please read http://www.artima.com/cppsource/safebool.html Thanks, -- David Abrahams BoostPro Computing http://boostpro.com
David Abrahams <dave <at> boostpro.com> writes:
On Jul 15, 2010, at 1:09 PM, Andrew Sutton wrote:
One could argue that the bits should be evaluated to produce the Boolean result as easily as evaluating the pointer. There are two aspects in pointer_plus_bits and they shouldn't be obscured or conflated.
I strongly disagree with using views in the design of this data structure. It's not such a complex concept that you would need to explicitly decouple its concerns via views. You end up designing a pointer+bits that can't be used natively as a pointer or bits.
I agree with Andrew.
I disagree with Dave and Andrew. There is no natural concept around "a pointer plus some bits". These are packed together to save space, which is an aspect completely orthogonal to whatever purspose the pointer and the bits serve (separately). To me, pointer_plus_bits should be as similar as possible to having two members, one a pointer the other the bits, so that for instance the following class X { ... pointer ptr; bool b; }; can be rewritten as class X { ... pointer_plus_bits<...> pb; }; so as to save memory, with as little change from the original situation as possible (for instance, instead of x.ptr one would say x.pb.ptr() and so forth). Overelaborating on an concept+bits concept seems to me to be missing the point. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Jul 15, 2010, at 1:43 PM, Joaquin M Lopez Munoz wrote:
I agree with Andrew.
I disagree with Dave and Andrew. There is no natural concept around "a pointer plus some bits". These are packed together to save space, which is an aspect completely orthogonal to whatever purspose the pointer and the bits serve (separately).
To me, pointer_plus_bits should be as similar as possible to having two members, one a pointer the other the bits, so that for instance the following
class X { ... pointer ptr; bool b; };
can be rewritten as
class X { ... pointer_plus_bits<...> pb; };
so as to save memory, with as little change from the original situation as possible (for instance, instead of x.ptr one would say x.pb.ptr() and so forth). Overelaborating on an concept+bits concept seems to me to be missing the point.
Joaquin's right, of course. This is a lot like compressed_pair and probably ought to follow that model. In fact, maybe this should just *be* another optimization of compressed_pair. -- David Abrahams BoostPro Computing http://boostpro.com
AMDG David Abrahams wrote:
Joaquin's right, of course. This is a lot like compressed_pair and probably ought to follow that model. In fact, maybe this should just *be* another optimization of compressed_pair.
I don't think it can be handled by compressed pair, since pointer_plus_bits requires setters and getters. There's no way to return a reference to the pointer. In Christ, Steven Watanabe
Joaquin M Lopez Munoz wrote:
David Abrahams <dave <at> boostpro.com> writes:
On Jul 15, 2010, at 1:09 PM, Andrew Sutton wrote:
Rob Stewart wrote:
One could argue that the bits should be evaluated to produce the Boolean result as easily as evaluating the pointer. There are two aspects in pointer_plus_bits and they shouldn't be obscured or conflated.
I strongly disagree with using views in the design of this data structure. It's not such a complex concept that you would need to explicitly decouple its concerns via views. You end up designing a pointer+bits that can't be used natively as a pointer or bits.
I agree with Andrew.
I disagree with Dave and Andrew. There is no natural concept around "a pointer plus some bits". These are packed together to save space, which is an aspect completely orthogonal to whatever purspose the pointer and the bits serve (separately).
I agree almost completely.
To me, pointer_plus_bits should be as similar as possible to having two members, one a pointer the other the bits, so that for instance the following
class X { ... pointer ptr; bool b; };
can be rewritten as
class X { ... pointer_plus_bits<...> pb; };
so as to save memory, with as little change from the original situation as possible (for instance, instead of x.ptr one would say x.pb.ptr() and so forth). Overelaborating on an concept+bits concept seems to me to be missing the point.
That's a nice analogy. The alternative is to declare that pointer_plus_bits is just a pointer that happens to carry some bits, which was Andrew's emphasis. When used as a pointer, it works like any good smart pointer. When the payload is required, an accessor provides some alternative view. There's some legitimacy to that view, but I think it is largely misguided because, as you point out, a pointer_plus_bits is like a struct with both a pointer and a payload and favoring one member over the other is inappropriate. Now, we could rethink the extrinsic view approach and instead provide two accessors that return a smart pointer and a payload object. That is, one calls a member function to get the equivalent of Joaquin's pb: x.pb.ptr->foo() vs x.pointer()->foo() x.pb.b vs x.bits() BTW, I've been using the general term "payload" but named the member function "bits" because the class name is, currently, "pointer_plus_bits." It might be useful, especially in light of the recent consideration of permitting the treatment of the extra bits as a small integer value, to name the class "pointer_with_payload" or something like that. ("data" and "value" are shorter than "payload" so they're probably better choices.) _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
----- Original Message ----- From: "Stewart, Robert" <Robert.Stewart@sig.com> To: <boost@lists.boost.org> Sent: Thursday, July 15, 2010 7:57 PM Subject: Re: [boost] [gsoc] Pointer Plus Bits Behavior and Interface
Joaquin M Lopez Munoz wrote:
David Abrahams <dave <at> boostpro.com> writes:
On Jul 15, 2010, at 1:09 PM, Andrew Sutton wrote:
Rob Stewart wrote:
One could argue that the bits should be evaluated to produce the Boolean result as easily as evaluating the pointer. There are two aspects in pointer_plus_bits and they shouldn't be obscured or conflated.
I strongly disagree with using views in the design of this data structure. It's not such a complex concept that you would need to explicitly decouple its concerns via views. You end up designing a pointer+bits that can't be used natively as a pointer or bits.
I agree with Andrew.
I disagree with Dave and Andrew. There is no natural concept around "a pointer plus some bits". These are packed together to save space, which is an aspect completely orthogonal to whatever purspose the pointer and the bits serve (separately).
I agree almost completely.
To me, pointer_plus_bits should be as similar as possible to having two members, one a pointer the other the bits, so that for instance the following
class X { ... pointer ptr; bool b; };
can be rewritten as
class X { ... pointer_plus_bits<...> pb; };
so as to save memory, with as little change from the original situation as possible (for instance, instead of x.ptr one would say x.pb.ptr() and so forth). Overelaborating on an concept+bits concept seems to me to be missing the point.
That's a nice analogy.
The alternative is to declare that pointer_plus_bits is just a pointer that happens to carry some bits, which was Andrew's emphasis. When used as a pointer, it works like any good smart pointer. When the payload is required, an accessor provides some alternative view. There's some legitimacy to that view, but I think it is largely misguided because, as you point out, a pointer_plus_bits is like a struct with both a pointer and a payload and favoring one member over the other is inappropriate.
Now, we could rethink the extrinsic view approach and instead provide two accessors that return a smart pointer and a payload object. That is, one calls a member function to get the equivalent of Joaquin's pb:
x.pb.ptr->foo() vs x.pointer()->foo() x.pb.b vs x.bits()
BTW, I've been using the general term "payload" but named the member function "bits" because the class name is, currently, "pointer_plus_bits." It might be useful, especially in light of the recent consideration of permitting the treatment of the extra bits as a small integer value, to name the class "pointer_with_payload" or something like that. ("data" and "value" are shorter than "payload" so they're probably better choices.)
The bitfield_tuple class will be extended so the user is able to pack a pointer and some bitfields as follows struct a; struct b; struct c; typedef bitfield_tuple< pointer<foo, a>, flag<b>, flag<c>
foo_bool_bool;
This can ge used as foo_bool_bool fbb = make_bitfield_tuple<foo_bool_bool>(new foo(), true, false); get<a>(fbb)->foo_member if (get<a>(fbb)!=0) {} This design gives the separated view of each one of the components as suggested by Joaquin, Stefan. The question was if we stop there or we provide some kind of smart pointer that stores a pointer but that allows to use the spare bits to store other info. Brian suggested me to rename pointer_plus_bits something like twiddling_ptr or stuffling_ptr (Brian could you recall the term you used). This class would have as major interface the interface of a smart pointer, but would have also the interface as it was a bitfield_tuple. We can consider that twiddling_ptr<foo, flag<b>, flag<c> > is bitfield_tuple< pointer<T, ptr_tag>, flag<b>, flag<c>
adding the smart pointer operations. After the Brian's questions and the comments of Joaquin, I think that this pointer_plus_bits (twiddling_ptr) class will introduce more problems than would solve. Between others, it will be difficult to define the operator==() without ignoring the additional bits and be coherent with the smart pointer view. As the bitfield_tuple, can not have more than a pointer (at least not for now), we could think in providing a specific accessor so no tag is needed bitfield_tuple< pointer<T>, flag<b>, flag<c>
pbb;
pbb.pointer()-> This function could be disabled (using SFINAE) if the bitfield_tuple has no pointer member. Best, Vicente
vicente.botet wrote:
From: "Stewart, Robert" <Robert.Stewart@sig.com>
Now, we could rethink the extrinsic view approach and instead provide two accessors that return a smart pointer and a payload object. That is, one calls a member function to get the equivalent of Joaquin's pb:
x.pb.ptr->foo() vs x.pointer()->foo() x.pb.b vs x.bits()
The bitfield_tuple class will be extended so the user is able to pack a pointer and some bitfields as follows
struct a; struct b; struct c; typedef bitfield_tuple< pointer<foo, a>, flag<b>, flag<c>
foo_bool_bool;
This can be used as
foo_bool_bool fbb = make_bitfield_tuple<foo_bool_bool>(new foo(), true, false);
get<a>(fbb)->foo_member
if (get<a>(fbb)!=0) {}
This design gives the separated view of each one of the components as suggested by Joaquin, Stefan.
Nice.
The question was if we stop there or we provide some kind of smart pointer that stores a pointer but that allows to use the spare bits to store other info. Brian suggested me to rename pointer_plus_bits something like twiddling_ptr or stuffling_ptr (Brian could you recall the term you used). This class would have as major interface the interface of a smart pointer, but would have also the interface as it was a bitfield_tuple. We can consider that
twiddling_ptr<foo, flag<b>, flag<c> >
is
bitfield_tuple< pointer<T, ptr_tag>, flag<b>, flag<c>
adding the smart pointer operations.
That's the wrong place to add the pointer knowledge.
As the bitfield_tuple, can not have more than a pointer (at least not for now), we could think in providing a specific accessor so no tag is needed
bitfield_tuple< pointer<T>, flag<b>, flag<c>
pbb;
pbb.pointer()->
This function could be disabled (using SFINAE) if the bitfield_tuple has no pointer member.
That's an interesting approach. However, a wrapper of bitfield_tuple could determine how (and how many of) the extra bits are used and provide an accessor or operators for pointer use. That is, one wrapper might implement the smart pointer interface with accessors for the bits, while another might provide pointer() to access the pointer. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
Zitat von Andrew Sutton <andrew.n.sutton@gmail.com>:
Would it be better to make the pointer_plus_bits convertible to a boolean based on the value of the pointer being stored? This would allow it to be more like to a pointer being that you could, as many people do, put it inside of an if statement to check to see if its null.
No. One could argue that the bits should be evaluated to produce the Boolean result as easily as evaluating the pointer. There are two aspects in pointer_plus_bits and they shouldn't be obscured or conflated.
I strongly disagree with using views in the design of this data structure. It's not such a complex concept that you would need to explicitly decouple its concerns via views. You end up designing a pointer+bits that can't be used natively as a pointer or bits.
The data structure is pointer_(plus_bits). First and foremost, I would expect its instances to model (at least some) Pointer semantics, which
I could agree with that given the name "pointer_plus_bits". but it seems to me that the underlying generic is something like "bitfield_tuple". so "pointer_plus_bits" could easily be an adapter (not: view) to this underlying and provide an interface to the pointer part by default, if you want to be able to write "if(p)". but the problem remains that a bitfield tuple or pointer plus bits are 2 separate logical variables (...the purpose of this library) and the user needs a way to differentiate between the interfaces to the two. obvious example: pointer plus an integer of 3 bits. operator++ could increment the pointer/iterator, or increment the integer. IIUC all you're saying is that you want a type that provides a view to the first part by default, and to the second on request.
includes "if(p)" and not "if(pointer_view<...>(p))". Dereferencing the
probably more like "if(p.pointer())" which would return the pointer view. (or "if(p)" if pointer_plus_bits is an adapter as described above.)
On 15 July 2010 07:17, Brian Bartman <bbartmanboost@gmail.com> wrote:
So here are some of the questions I would like to pose to the community about the behavior and interface of the pointer_plus_bits data structure:
I think it should look, where practical, like either a tuple<T*, bitset<N>> or a tuple<T*, bool, bool, ...> Then it doesn't need to provide any pointer-like operations.
Thanks for the responses. After reading the comments from the community, I believe that implementing the pointer plus bits as a pointer abstraction is not the right call, because what is actually being stored is multiple things (in this case a pointer and some extra bits). I will be implementing the "pointer plus bits" as part of the bitfield_tuple's interface, which will look similar to template interface talked about by Scott McMurray. As talked about by Stefan Strasser, the packing and storage of extra bits is not limited to only pointers, I'll be extending the bitfield_tuple to support policies which the user can provide to further extend the packing and unpacking of different types of data to meet the users needs. -- thanks, Brian Bartman
So here are some of the questions I would like to pose to the community about the behavior and interface of the pointer_plus_bits data structure:
I think it should look, where practical, like either a tuple<T*, bitset<N>> or a tuple<T*, bool, bool, ...>
Then it doesn't need to provide any pointer-like operations.
The class is called "pointer... plus bits". If the abstraction isn't at least a little bit pointer-like, then the name of the data type is duplicitous at best. I think that some of the suggestions treat lightly the attachment that programmers have to the meanings of names. I think it might be worthwhile to provide an interface that "explodes" the data type into a tuple. I actually prefer the idea of offering methods that return the pointer and bitfield as component parts. I believe these could also return proxies to allow assignment to and from the ptr type. But if you don't at least provide a boolean cast and a dereference operator, then I don't think you should be using "pointer" in the name of the class. Andrew Sutton andrew.n.sutton@gmail.com
On 07/15/2010 06:48 PM, Andrew Sutton wrote:
The class is called "pointer... plus bits". If the abstraction isn't at least a little bit pointer-like, then the name of the data type is duplicitous at best. I think that some of the suggestions treat lightly the attachment that programmers have to the meanings of names.
But if you don't at least provide a boolean cast and a dereference operator, then I don't think you should be using "pointer" in the name of the class.
Meh, you could call it pointer_int_pair, and nobody would complain about the "pointer" in the name. (PointerIntPair is LLVM's version of this.) Sebastian
But if you don't at least provide a boolean cast and a dereference operator, then I don't think you should be using "pointer" in the name of the class.
Meh, you could call it pointer_int_pair, and nobody would complain about the "pointer" in the name. (PointerIntPair is LLVM's version of this.)
You could if you were implementing a pointer/int pair, which is exactly what that data type does. This reinforces my point. I believe that you could use Brian's framework to create a typedef consisting of a compound pointer/bitfield representation and call it something similar. Regardless of its name it's still going to have a tuple-like or component-like interface to access the pointer and the bitfield. (Brian, please correct me if I'm wrong). I would think that the point of creating this particular data type (pointer_plus_bits) was to emphasize the pointer aspect and less so the "pair". If you really want a pointer/int tuple, then create one. If you want a pointer plus some bits, then I think this would be the place to look--but only if it worked more or less like a pointer. Andrew Sutton andrew.n.sutton@gmail.com
On 15 July 2010 21:00, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:
I would think that the point of creating this particular data type (pointer_plus_bits) was to emphasize the pointer aspect and less so the "pair".
I think that's a point-of-view difference. When I heard of it, I immediately thought of "compressed pair with non-empty things". But all three work. If you're implementing a red-black tree, the interesting part is the bits, not the fact that you have pointers.
Scott McMurray wrote:
On 15 July 2010 21:00, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:
I would think that the point of creating this particular data type (pointer_plus_bits) was to emphasize the pointer aspect and less so the "pair".
I think that's a point-of-view difference. When I heard of it, I immediately thought of "compressed pair with non-empty things".
Emphasizing the tuple aspect may be useful. The generalized bitfield_tuple is a reasonable building block, but if one of the elements is a pointer, it seems a name with "pointer" in it would be better. For that, just reversing the terms might do well. I also suggested, elsewhere, that "bits" be replaced with "data," "values," or something like that. Therefore, consider these combinations: data_and_pointer data_plus_pointer data_with_pointer values_and_pointer values_plus_pointer values_with_pointer "data" is shorter, so I favor it over "values." "data_and_pointer" lends itself to an acronym, "DAP," which might prove useful. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
----- Original Message ----- From: "Stewart, Robert" <Robert.Stewart@sig.com> To: <boost@lists.boost.org> Sent: Friday, July 16, 2010 1:22 PM Subject: Re: [boost] [gsoc] Pointer Plus Bits Behavior and Interface
Scott McMurray wrote:
On 15 July 2010 21:00, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:
I would think that the point of creating this particular data type (pointer_plus_bits) was to emphasize the pointer aspect and less so the "pair".
I think that's a point-of-view difference. When I heard of it, I immediately thought of "compressed pair with non-empty things".
Emphasizing the tuple aspect may be useful. The generalized bitfield_tuple is a reasonable building block, but if one of the elements is a pointer, it seems a name with "pointer" in it would be better. For that, just reversing the terms might do well. I also suggested, elsewhere, that "bits" be replaced with "data," "values," or something like that. Therefore, consider these combinations:
data_and_pointer data_plus_pointer data_with_pointer values_and_pointer values_plus_pointer values_with_pointer
"data" is shorter, so I favor it over "values." "data_and_pointer" lends itself to an acronym, "DAP," which might prove useful.
The initial goal of the bitfield_tuple was to emulate bitfields structures. Now that we will have pointers in, we can think of this class a compressed tuple, on which each member takes only the needed bits. The Brian's project concern also with the ability to work with storages that will go out of the word boundary. So maybe compressed_tuple could be a better name that allows to put in whatever data. Best, Vicente
Andrew Sutton wrote:
The class is called "pointer... plus bits". If the abstraction isn't at least a little bit pointer-like, then the name of the data type is duplicitous at best. I think that some of the suggestions treat lightly the attachment that programmers have to the meanings of names.
Rereading the above, I realized that I wasn't putting as much emphasis on "plus" as you. I was reading the name much more like "pointer_and_bits," so the pointer focus was less strong for me. I now see your problem with the current name. Just changing "plus" to "and" would probably alleviate your concern, but reversing the order, as I suggested elsewhere, may be even more satisfactory. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
participants (11)
-
Andrew Sutton -
Brian Bartman -
David Abrahams -
Ion Gaztañaga -
Joaquin M Lopez Munoz -
Scott McMurray -
Sebastian Redl -
Stefan Strasser -
Steven Watanabe -
Stewart, Robert -
vicente.botet