Re: [boost] interest in a stateful pointer library?

Subject: Re: [boost] interest in a stateful pointer library?
From: Hans Dembinski (hans.dembinski_at_[hidden])
Date: 2017-10-09 09:32:21

Hi Christof,

thank you for your reply and sorry for the late answer. In the meantime I had some interesting discussion on Reddit about this library.

> On 2. Oct 2017, at 12:37, Christof Donat via Boost <boost_at_[hidden]> wrote:
> 
> Am 02.10.2017 10:46, schrieb Hans Dembinski via Boost:
>> I wrote a variant of std::unique_ptr, called tagged_ptr, which allows
>> safe read/write access to a customisable number of bits in the pointer
>> variable. You can find the library on github:
>> https://github.com/HDembinski/stateful_pointer
> 
> I don't have a current use, but I think, it might be very useful in memory constraint environments.

Please have a look at the updated README on Github. tagged_ptr uses Boost.Align to get pointers with a special bit pattern which allows to perfectly predict these bits and therefore use them to hold state. I thought that this trick was platform-independent, since Boost.Align seems platform-independent, but smart people on Reddit showed me that I am relying on undefined behaviour here. It turns out that the conversion between memory address and integers may not be as trivial as it is on a x86 machine, and then this trick would fail.

This is kinda sad, because the library is much less useful if tagged_ptr is not guaranteed to work on all platforms now and in the future. Just assume you use this in a large project and rely on it, and then a new processor generation comes out where tagged_ptr does not work anymore. That being said it is probably still useful for special projects, but not something to put in Boost. :(

>> One needs little imagination to find good use for those bits. As a
>> proof of principle, I wrote an STL compatible string class which has
>> the size of const char*, but can store up to 7 ASCII characters (on a
>> 64 bit system) without allocating any memory on the heap (aka small
>> string optimisation).
> 
> I understand, that this is only an example, but...
> 
> I have not yet written a STL compatible string class, nor have I taken my time to look at existing implementations. Therefore I might be completely wrong. In my understanding, it would contain a size_t together with the const char*, so it will always be 16 bytes on a 64 Bit system and you can have up to 14 chars plus one null byte without heap allocation.

On my system (gcc stdlib), std::string has the size of 32 bytes = 256 bits. That's 64 bits for a const char* pointer, 64 bits to hold the size_t, 64 bits to hold the allocator instance, and another 64 bits that I don't know what they are good for. I haven't looked into the gcc implementation, so I don't know whether it uses small string optimisation. 

The boost::container::string has a size of 24 bytes, which is enough to hold pointer, size, and allocator. The boost::container::string does small string optimisation. It almost has the size you expected, you just forgot the space required for the allocator instance. I did not look into the implementation closely, but I guess it can use up to 15 bytes to store a small string without doing a heap allocation.

The string I wrote is only 8 bytes = 64 bits. In small string mode, it holds the (small) size in the lowest bits and uses the rest of the bits to hold up to 7 chars. In normal mode, the size is stored at the beginning in the allocated memory, so that I do not need to store it inside the string class. I do not support allocators with state, thus I can get away without holding an instance of the allocator. std::allocator is an example of a stateless allocator which would work with this class.

Anyway, since tagged_ptr is not really portable, neither is this string. That's a bummer, because it would be great to have a portable tiny string class. It just does the optimisation a bit differently than other string classes, more focused on minimal size. Being able to chose between different optimisations by replacing the string class in a project is nice.

Best regards,
Hans