std.allocator: false pointers

Steven Schveighoffer via Digitalmars-d digitalmars-d at puremagic.com
Fri May 2 12:05:41 PDT 2014


On Fri, 02 May 2014 14:56:00 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 5/2/14, 11:50 AM, Steven Schveighoffer wrote:
>> On Fri, 02 May 2014 14:42:52 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>
>>> On 5/2/14, 11:07 AM, Steven Schveighoffer wrote:
>>
>>>> What is the problem with keeping the bits together?
>>>
>>> More implementation (I have a BitVector type but not a KBitsVector!k
>>> type), and scanning can't be done with fast primitives. -- Andrei
>>
>> Given a bitvector type, a 2bitvector type can be implemented on top of  
>> it.
>
> If speed is no issue, sure :o). My intuition is that the TwoBitVector  
> would need certain primitives from BitVector to work well.
>
>> If one bit is "free", and another is "garbage", you just have to look
>> for any set bits for free blocks. Yes, you have to look through 2x as
>> much memory, but only until you find a free block.
>
> Hmm, so if "garbage" is 0, then to allocate we'd need to scan for a  
> "hole" of contiguous zeros (cheap) instead of a checkered pattern  
> (expensive). I'll think about it.

Well, you are looking for one bit set (free), or another bit set  
(garbage). So the pattern may not be uniform.

What you probably want to do is to store the bits close together, but  
probably not *right* together. That way you can use logic-or to search for  
bits.

-Steve


More information about the Digitalmars-d mailing list