Hi all, I recently learned about tagged pointers, https://en.m.wikipedia.org/wiki/Tagged_pointer. Over the weekend, I was working on a tiny_string implementation which has a width of only one pointer. Essentially it's a null-terminated char* array managed by std::unique_ptr. On my system, std::string is four times larger (probably 8 byte for the pointer, 8 byte for the length, 8 byte for the allocator and 8 byte for … good measure?). With a tagged pointer, I could even implement a small-string optimisation in that tiny_string, by storing small strings with up to 7 bytes in the memory that otherwise holds the address to the char* array. The tag then allows you to discriminate between the two uses of the memory. You may rightfully question whether it is really practical to do this, but it is certainly one possible application of a tagged pointer. Looking into boost, I found that the lockfree library has a tagged pointer implementation in its "detail" namespace. The implementation is nice, because it falls back to a safe version with a separate tag field on systems which do not follow the required alignment conventions. Wouldn't it make sense to make the tagged pointer accessible by users, i.e. place it in a separate library (or in the existing smart_ptr library)? Best regards, Hans
On Mon, Jan 9, 2017 at 10:54 AM, Hans Dembinski <hans.dembinski@gmail.com> wrote:
I recently learned about tagged pointers, https://en.m.wikipedia.org/ wiki/Tagged_pointer. [...] Looking into boost, I found that the lockfree library has a tagged pointer implementation in its "detail" namespace. The implementation is nice, because it falls back to a safe version with a separate tag field on systems which do not follow the required alignment conventions.
Wouldn't it make sense to make the tagged pointer accessible by users, i.e. place it in a separate library (or in the existing smart_ptr library)?
FWIW, Facebook Folly has two 64-bit-only pointers using this: https://github.com/facebook/folly/blob/master/folly/DiscriminatedPtr.h https://github.com/facebook/folly/blob/master/folly/PackedSyncPtr.h I'd welcome an official one in Boost as well. Wasn't aware of the Boost.Lockfree one. Thanks for the pointer :). --DD
Hans Dembinski wrote:
Looking into boost, I found that the lockfree library has a tagged pointer implementation in its "detail" namespace.
Wouldn't it make sense to make the tagged pointer accessible by users, i.e. place it in a separate library (or in the existing smart_ptr library)?
One issue with tagged pointers is that you need to get it right on every architecture that you care about. An advantage of Boost offering it, rather than everyone implementing their own version, would be that the architecture-specific research would only need to be done once. For example, Facebook's implementation assumes that the top 16 bits of a 64-bit pointer are free. On arm64, as I understand it only the top 8 bits are guaranteed to be free; see e.g. https://www.kernel.org/doc/Documentation/arm64/tagged-pointers.txt . Boost.Lockfree also uses 16 bits, but it does check for x86_64 first. There is also the question of what happens when you dereference a tagged pointer. Arm64 Linux promises to ignore the tag bits when dereferencing, so no masking is needed (*); on other arm64 operating systems this might not happen so you would need to mask. (*) You can't pass a pointer with tag bits to a system call though. Anyway, yes, it would be great to have this as a public part of Boost. Cheers, Phil.
On 10 Jan 2017, at 19:28, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:
One issue with tagged pointers is that you need to get it right on every architecture that you care about. An advantage of Boost offering it, rather than everyone implementing their own version, would be that the architecture-specific research would only need to be done once.
Yes, exactly my thoughts. :) Once a platform-independent implementation exists, it could serve to optimise countless other boost and user libraries. This is a potential class with high adoption value. Perhaps boost.align could be used on non-conforming platforms to ensure correct alignment of the pointer, so that the always trick works. If tagged_ptr is a smart pointer, it can use aligned_alloc and aligned_free behind the scenes.
participants (3)
-
Dominique Devienne -
Hans Dembinski -
Phil Endecott