Hello,


I'm currently doing a nice optimization in the tracing code: I use the same bit (per block) to indicate "this memory is allocated" and "this memory is marked as used during tracing".

The way the trick works is, at the beginning of a collection the GC marks all of its memory as deallocated (sic!). Then, it traces through pointers and marks BACK as allocated the memory that's actually used. At the end of tracing, there's no need to do anything - what's used stays used, the rest is free by default.

This is unlike more traditional GCs, which use a SEPARATE bit to mean "mark during tracing". At the beginning of the collection, these "mark" bits are set to 0. Then collection proceeds and marks with 1 all blocks that are actually used. As the last step, collection deallocates all blocks that were marked with 0 and were previously allocated.

So the optimization consumes less memory and saves one pass. It does have a disadvantage, however.

Consider a false pointer. It will claim that a block that's free is actually occupied, and the implementation can't distinguish because it conflates the "mark" and the "allocated" bit together. So it's possible that at the end of collection there are blocks allocated that previously weren't. The optimization is therefore sensitive to false pointers.

Thoughts? How bad are false pointers (assuming we fix globals, which only leaves the stack and registers)?


Andrei

On Friday, 2 May 2014 at 15:55:06 UTC, Andrei Alexandrescu wrote:
> Hello,
>
>
> I'm currently doing a nice optimization in the tracing code: I use the same bit (per block) to indicate "this memory is allocated" and "this memory is marked as used during tracing".
>
> The way the trick works is, at the beginning of a collection the GC marks all of its memory as deallocated (sic!). Then, it traces through pointers and marks BACK as allocated the memory that's actually used. At the end of tracing, there's no need to do anything - what's used stays used, the rest is free by default.
>
> This is unlike more traditional GCs, which use a SEPARATE bit to mean "mark during tracing". At the beginning of the collection, these "mark" bits are set to 0. Then collection proceeds and marks with 1 all blocks that are actually used. As the last step, collection deallocates all blocks that were marked with 0 and were previously allocated.
>
> So the optimization consumes less memory and saves one pass. It does have a disadvantage, however.
>
> Consider a false pointer. It will claim that a block that's free is actually occupied, and the implementation can't distinguish because it conflates the "mark" and the "allocated" bit together. So it's possible that at the end of collection there are blocks allocated that previously weren't. The optimization is therefore sensitive to false pointers.
>
> Thoughts? How bad are false pointers (assuming we fix globals, which only leaves the stack and registers)?

If destructors are still going to be called (see other thread), this trick is dangerous, because the resurrected objects might later on be destroyed again (double free).

I'm aware that this is still about untyped allocators, but if they are going to be used as a basis for typed allocators, things like this need to be considered already at this stage.

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?

Another thing to consider is that this makes it impossible to pre-allocate blocks of varying sizes for absurdly fast allocations via atomic linked lists, in most cases literally a single `lock cmpxchg`.

On 5/2/14, Andrei Alexandrescu via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
> Hello,
>
>
> I'm currently doing a nice optimization in the tracing code: I use the same bit (per block) to indicate "this memory is allocated" and "this memory is marked as used during tracing".
>
> The way the trick works is, at the beginning of a collection the GC marks all of its memory as deallocated (sic!). Then, it traces through pointers and marks BACK as allocated the memory that's actually used. At the end of tracing, there's no need to do anything - what's used stays used, the rest is free by default.
>
> This is unlike more traditional GCs, which use a SEPARATE bit to mean "mark during tracing". At the beginning of the collection, these "mark" bits are set to 0. Then collection proceeds and marks with 1 all blocks that are actually used. As the last step, collection deallocates all blocks that were marked with 0 and were previously allocated.
>
> So the optimization consumes less memory and saves one pass. It does have a disadvantage, however.
>
> Consider a false pointer. It will claim that a block that's free is actually occupied, and the implementation can't distinguish because it conflates the "mark" and the "allocated" bit together. So it's possible that at the end of collection there are blocks allocated that previously weren't. The optimization is therefore sensitive to false pointers.
>
> Thoughts? How bad are false pointers (assuming we fix globals, which only leaves the stack and registers)?
>
>
> Andrei
>

On Fri, 02 May 2014 11:55:11 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> Hello,
>
>
> I'm currently doing a nice optimization in the tracing code: I use the same bit (per block) to indicate "this memory is allocated" and "this memory is marked as used during tracing".
>
> The way the trick works is, at the beginning of a collection the GC marks all of its memory as deallocated (sic!). Then, it traces through pointers and marks BACK as allocated the memory that's actually used. At the end of tracing, there's no need to do anything - what's used stays used, the rest is free by default.
>
> This is unlike more traditional GCs, which use a SEPARATE bit to mean "mark during tracing". At the beginning of the collection, these "mark" bits are set to 0. Then collection proceeds and marks with 1 all blocks that are actually used. As the last step, collection deallocates all blocks that were marked with 0 and were previously allocated.
>
> So the optimization consumes less memory and saves one pass. It does have a disadvantage, however.
>
> Consider a false pointer. It will claim that a block that's free is actually occupied, and the implementation can't distinguish because it conflates the "mark" and the "allocated" bit together. So it's possible that at the end of collection there are blocks allocated that previously weren't. The optimization is therefore sensitive to false pointers.
>
> Thoughts? How bad are false pointers (assuming we fix globals, which only leaves the stack and registers)?

False pointers are less of a problem in 64-bit code, but you can run into worse issues. If you are not zeroing the memory when deallocating, then if it mysteriously comes alive again, it has the ghost of what could be a pointer to other code. Your blocks are more likely to resurrect once one of them resurrects.

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.

This doesn't save on the bit space, but I think the savings there is minimal anyway. However, it does allow the final pass to be saved.

-Steve

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).

essentially:

enum GCState {free, allocated, garbage}

GCState memoryBlocks[];

fullCollect()
{
   foreach(ref st; memoryBlocks)
   {
      final switch(st)
      {
      case GCState.free:
         break;
      case GCState.allocated:
         st = GCState.garbage;
         break;
      case GCState.garbage:
         st = GCState.free;
         break;
      }
   }
   ... // run mark/sweep setting garbage to allocated for reachable blocks
}

On 5/2/14, 10:12 AM, "Marc Schütz" <schuetzm@gmx.net>" wrote:
>
> If destructors are still going to be called (see other thread), this
> trick is dangerous, because the resurrected objects might later on be
> destroyed again (double free).

Yah, forgot to mention this trick is only applicable to what I call "the passive heap". Thanks! -- Andrei

On 5/2/14, 10:15 AM, 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?

It's the time savings that are most important.

> Another thing to consider is that this makes it impossible to
> pre-allocate blocks of varying sizes for absurdly fast allocations via
> atomic linked lists, in most cases literally a single `lock cmpxchg`.

Those can be accommodated I think.


Andrei

On 5/2/14, 10:26 AM, Steven Schveighoffer wrote:
> False pointers are less of a problem in 64-bit code, but you can run
> into worse issues. If you are not zeroing the memory when deallocating,
> then if it mysteriously comes alive again, it has the ghost of what
> could be a pointer to other code. Your blocks are more likely to
> resurrect once one of them resurrects.

Good point.

> 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.
>
> This doesn't save on the bit space, but I think the savings there is
> minimal anyway. However, it does allow the final pass to be saved.

That's a great idea. Thanks!


Andrei

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

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?

-Steve