Hi ----- Original Message ----- From: "Edouard A." <edouard@fausse.info> To: <boost@lists.boost.org> Sent: Monday, September 07, 2009 7:33 PM Subject: Re: [boost] Interest request for pointer+bit compressionoptimization
I was wondering if it would be interesting to provide some generic template classes making >easier this kind of optimization.
Yes, at least for me.
You actually have more than one bit available as the OS generally reserves a huge area of virtual memory for the kernel. Typical example, Windows 32, maximum user pointer value is 0x80000000. Don't remember the values by heart for the other oses.
The trick is not because the OS don't use the whole addresable memory but on the fact memory is aligned.
From the blog "Alignment considerations dictate that many types must lie in memory addresses that are multiple of some small integer greater than 1; in particular, it is extremely usual that the alignment of a type T is even (i.e. a multiple of 2), in which case the least significant bit of the representation of pointers to T is always zero. And this is precisely the situation in which we can reuse this bit to embed the color information:"
On 64-bit OSes you really can use the large pointers to store data and therefore have very compact structures in memory. Correct me if I'm wrong but currently most OSes only allow several gigabytes of virtual memory for any given user process (something like 100-200 GB), that means there's room for expression! :D
In addition, embedding a tag within a pointer is a technique to reduce the ABA problem occurrence on lockfree containers.
It would be a nice to have IMHO, but there is a huge work of testing to make it safe and reliable.
Well there is already the fact that boost::aligned_of is not portable, but with the new C++1x we will have this is a portable way. Other than that there is not too much to do. Thanks, Vicente