[Patch] bitmap_allocator.

[Paolo Carlini]

Dhruv Matani wrote:

>Now, IMO, the problem might be starting at the place when I start
>accessing bit-maps! That's because half of them will have only 4-byte
>alignment! If this in fact is the problem, then how does the compiler
>arrays of unsigned ints for 64-bit machines? We can then adopt the same
>strategy!
>  
>
Is it clear that the alignment requirements depend on the type? If you 
align 8
on 32-bit and 16 on 64-bit you are *always* safe, if you align less, you 
are safe
sometimes, not safe other times, depending on the type. For instance 
when the
allocator is called by standard containers, such as std::list, std::map, 
std::set, and
so on, you need space for relatively big structs, that in general have 
higher
alignment requirements...

Another thing: it looks like in your allocator, all the various 
quantities are
unsigned ints. Besides alignment issues, this is *not* ok on 64-bit machines
because everything becomes severely limited!! Do you know that linux on 
x86_64,
an archs becoming rather popular, already supports 512 G of virtual address
space per process and is being extended very soon to 47 bits (128TB)? 
Doesn't
make sense to use unsigned ints on modern 64-bit machines.

>Yes, currently I use the __builting_ctz instruction, which is working
>for 32-bit types. Now, I need to change that to __builtin_ctzl. But is
>it guaranteed that it will work for 8-byte types, and also will
>sizeof(long) == 8-bytes on 32-bit and 64-bit machines?
>  
>
Of course sizeof(long) is 4 on 32-bit machines and that's ok, because, 
as I already
wrote, 2 * sizeof(long) gives you the optimal alignment everywhere. And 
of course
a builtin for long works for long, whatever size it has on that target.

>Should I assume that 8-byte alignment is sufficient?
>  
>
As I already told you 8 is the bare minimum you should aim to, but that must
be configurable. Please try to follow my suggestion: use *everywhere* longs
for the memory and the bookeeping quantities, and possibly pairs of them for
the memory in case the user wants that.

Paolo.