On 5/2/14, 11:07 AM, Steven Schveighoffer wrote:
> On Fri, 02 May 2014 14:00:18 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>
>> On 5/2/14, 10:33 AM, Steven Schveighoffer wrote:
>>> On Fri, 02 May 2014 13:26:41 -0400, Steven Schveighoffer
>>> <schveiguy@yahoo.com> wrote:
>>>
>>>> Why not keep the 3 states, but just treat unmarked blocks as free?
>>>> Then the next time you go through tracing, change the bit to free if
>>>> it was already marked.
>>>
>>> Sorry, if it was already *unmarked* (or marked as garbage).
>>
>> Yah, understood. Unfortunately I just realized that would require
>> either to keep the bits together or to scan two memory areas when
>> trying to allocate, both of which have disadvantages. Well, I guess
>> I'll go with the post-tracing pass. -- Andrei
>
> 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

On Fri, 02 May 2014 14:42:52 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@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 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.

-Steve

On 5/2/14, 11:50 AM, Steven Schveighoffer wrote:
> On Fri, 02 May 2014 14:42:52 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@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.


Andrei

On Fri, 02 May 2014 14:56:00 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@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@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

On 5/2/14, 11:56 AM, Andrei Alexandrescu wrote:
> If speed is no issue, sure :o). My intuition is that the TwoBitVector
> would need certain primitives from BitVector to work well.

Heh, however it's implemented, TwoBitVector's very name implies that it's cheap to use ;)

On Friday, 2 May 2014 at 17:15:20 UTC, Orvid King via Digitalmars-d wrote:
> Well, in a 64-bit address space, the false pointer issue is almost
> mute, the issue comes in when you try to apply this design to 32-bit,
> where the false pointer issue is more prevelent. Is the volume of
> memory saved by this really worth it?

False pointers don't only cause memory consumption, you're forgetting that the GC will repeatedly scan memory held by false pointers at each collection*. This adds time to each collection and further increases the risk of other false pointers.

False pointers can make many reasonable looking D programs behave unexpectedly when run in a 32-bit environment (to the point that I consider that they can "break" programs.)

I think false pointers must be addressed to make claims that D is well-behaved on 32-bit systems.

* Unless it is marked NO_SCAN of course, but this is not likely the common case.

On Saturday, 3 May 2014 at 23:41:02 UTC, safety0ff wrote:
>> Well, in a 64-bit address space, the false pointer issue is almost
>> mute, the issue comes in when you try to apply this design to 32-bit,

That assumes that the heap is located at a high address.

> I think false pointers must be addressed to make claims that D is well-behaved on 32-bit systems.

Which means a precise collector, which means faster stack meta info access, which means faster exception handling? Then use a single pass mark-and-don't-sweep collector/allocator? (invert the meaning of the bit for every other full collection cycle)

A conservative collector will never be acceptable in a language which is primarily GC based. It is something you can bolt on to a RC system to collrct cycles, IMHO.