Sean Kelly wrote:

> Craig Black wrote:
>> "Sean Kelly" <sean@f4.ca> wrote in message news:fin4fl$1h7v$1@digitalmars.com...
>>> This thread inspired me to make a number of changes to the GC and such
>>> in
>>> Tango.  They should improve efficiency in terms of eliminating wasted
>>> space and avoiding collections in some situations.  They'll probably
>>> take a few days, so stay tuned.
>> 
>> Cool!  Maybe you could show some benchmarks when you get done?
> 
> Unfortunately, I think I'm not going to commit these changes.  I had some clever ideas for how to replace the "allocate an extra byte" functionality with an approach that would have resulted in less wasted space, but it's become more complicated than the added efficiency is worth.
> 
> Basically, I was hoping to keep an extra free page at the end of the allocated memory region used by the process.  This assumes that all memory used by the process is contiguous however, or at least that the intervening pages are valid.  But neither assumption is reasonable, and while some sort of fancy manual fix may have worked with some memory management APIs, it wouldn't have worked with others.
> 
> For what it's worth, my concern with the current behavior is that its worst-case scenario coincides with typical usage.  It is extremely common for a programmer to use array sizes that are powers of two, and this is the situation which results in the maximum unused space per block (because the runtime adds 1 to the size of all array allocations passed to the GC).  Totally stinks, and I'm running out of ideas.  I don't suppose someone can offer a suggestion for how to address this, other than "just always allocate exactly what they request and if they get a page fault then too bad for them?"
> 
> 
> Sean

If object sizes are a power of 2, is that because of special padding of a struct/object to make it align well?  Maybe some clever trick could be done to use wasted space, if it exists, for special tracking data... Otherwise, allocating a bit more seems the most sensible.

Marius Muja wrote:
> Sean Kelly wrote:
> 
>> For what it's worth, my concern with the current behavior is that its worst-case scenario coincides with typical usage.  It is extremely common for a programmer to use array sizes that are powers of two, and this is the situation which results in the maximum unused space per block (because the runtime adds 1 to the size of all array allocations passed to the GC).  Totally stinks, and I'm running out of ideas.  I don't suppose someone can offer a suggestion for how to address this, other than "just always allocate exactly what they request and if they get a page fault then too bad for them?"
> 
> That was my problem also. I was using array sizes that were powers of two and because of the extra 1 there were many memory pages wasted. For example in one of my tests I was allocating float arrays of size 1024 (4096 bytes) which were taking 2 pages instead of 1 because of the extra 1 added, and that's where I was observing that with D's new operator I can only allocate half as much memory than with malloc.
> Oddly the same problem occurs if I allocate much larger arrays of exactly 1024*1024 floats (4MB size). Seems that instead of 4MB, D's runtime allocated 8MB for each of these arrays. Is D's runtime using 4MB pages for large memory allocations?

Weird.  D's GC is basically a "big bag of pages" allocator, where groups of pages are divided into pools.  The maximum size a pool will be on its own is 8 megs, with very large single allocations getting their own pool that is as big as necessary.  If I had to guess, I'd say the 8MB you're seeing is an artifact of this allocation scheme, and I'd suspect that much of the 8MB is committed but marked as free pages in your program.


Sean

Jason House wrote:
> Sean Kelly wrote:
> 
>> Craig Black wrote:
>>> "Sean Kelly" <sean@f4.ca> wrote in message
>>> news:fin4fl$1h7v$1@digitalmars.com...
>>>> This thread inspired me to make a number of changes to the GC and such
>>>> in
>>>> Tango.  They should improve efficiency in terms of eliminating wasted
>>>> space and avoiding collections in some situations.  They'll probably
>>>> take a few days, so stay tuned.
>>> Cool!  Maybe you could show some benchmarks when you get done?
>> Unfortunately, I think I'm not going to commit these changes.  I had
>> some clever ideas for how to replace the "allocate an extra byte"
>> functionality with an approach that would have resulted in less wasted
>> space, but it's become more complicated than the added efficiency is
>> worth.
>>
>> Basically, I was hoping to keep an extra free page at the end of the
>> allocated memory region used by the process.  This assumes that all
>> memory used by the process is contiguous however, or at least that the
>> intervening pages are valid.  But neither assumption is reasonable, and
>> while some sort of fancy manual fix may have worked with some memory
>> management APIs, it wouldn't have worked with others.
>>
>> For what it's worth, my concern with the current behavior is that its
>> worst-case scenario coincides with typical usage.  It is extremely
>> common for a programmer to use array sizes that are powers of two, and
>> this is the situation which results in the maximum unused space per
>> block (because the runtime adds 1 to the size of all array allocations
>> passed to the GC).  Totally stinks, and I'm running out of ideas.  I
>> don't suppose someone can offer a suggestion for how to address this,
>> other than "just always allocate exactly what they request and if they
>> get a page fault then too bad for them?"
> 
> If object sizes are a power of 2, is that because of special padding of a
> struct/object to make it align well?  Maybe some clever trick could be done
> to use wasted space, if it exists, for special tracking data... Otherwise,
> allocating a bit more seems the most sensible.

Only arrays get the +1 byte added to their size during allocations.  If an object occupies 16 bytes then it will end up in a 16 byte bucket. The +1 issue for arrays exists to make the program a bit more forgiving for "past the end" errors.  Interestingly, the ANSI C standard actually requires this behavior in its allocators.  I have yet to decide whether or not this is an artifact of C using terminators to mark the end of a block, since using terminators seems more likely to result in such bugs than the length scheme D employs.


Sean

Sean Kelly wrote:
> Jason House wrote:
>>
>> If object sizes are a power of 2, is that because of special padding of a
>> struct/object to make it align well?  Maybe some clever trick could be done
>> to use wasted space, if it exists, for special tracking data... Otherwise,
>> allocating a bit more seems the most sensible.
> 
> Only arrays get the +1 byte added to their size during allocations.  If an object occupies 16 bytes then it will end up in a 16 byte bucket. The +1 issue for arrays exists to make the program a bit more forgiving for "past the end" errors.  Interestingly, the ANSI C standard actually requires this behavior in its allocators.

So I went and looked up the clause and I'm not clear whether it requires the location to be physically available or merely fore the address to be valid for pointer mathematics.  I also realized that I don't need to worry about malloc and vmalloc because they're already ANSI C complaint, so it's just potentially a matter of sorting out VirtualAlloc and mmap.  I'm going to do a bit more research and see what comes out of it.


Sean

> Weird.  D's GC is basically a "big bag of pages" allocator, where groups of pages are divided into pools.  The maximum size a pool will be on its own is 8 megs, with very large single allocations getting their own pool that is as big as necessary.  If I had to guess, I'd say the 8MB you're seeing is an artifact of this allocation scheme, and I'd suspect that much of the 8MB is committed but marked as free pages in your program.

That seems to be the case. And because in my test program I was always allocating 4MB-sized arrays, the extra pages that were committed but marked as free couldn't be used.

Marius

Sean Kelly wrote:

> Only arrays get the +1 byte added to their size during allocations.  If an object occupies 16 bytes then it will end up in a 16 byte bucket. The +1 issue for arrays exists to make the program a bit more forgiving for "past the end" errors.  Interestingly, the ANSI C standard actually requires this behavior in its allocators.  I have yet to decide whether or not this is an artifact of C using terminators to mark the end of a block, since using terminators seems more likely to result in such bugs than the length scheme D employs.

The +1 allocation for arrays is AFAIK there to make sure that it is valid to have a pointer point one past the end. You want this to a) allow efficient iterators, and b) to allow [$..$] slices.

The problems that would arise if the GC didn't allocate that extra byte are

* appending to a [$..$] slice would in some cases be confused by the gc as appending to a [0..0] slice of the following allocated array, and thereby corrupting that memory.

* all pointers past the end prevents the consecutive memory area to be reclaimed by the GC.

-- 
Oskar

Oskar Linde wrote:
> 
> The problems that would arise if the GC didn't allocate that extra byte are
> 
> * appending to a [$..$] slice would in some cases be confused by the gc as appending to a [0..0] slice of the following allocated array, and thereby corrupting that memory.
> 
> * all pointers past the end prevents the consecutive memory area to be reclaimed by the GC.

Okay that makes sense.  The Boehm GC tied the +1 byte to whether internal pointers were allowed so I was wondering if it was something along these lines.  Thanks.


Sean

Sean Kelly wrote:
> Sean Kelly wrote:
>> Jason House wrote:
>>>
>>> If object sizes are a power of 2, is that because of special padding
>>> of a
>>> struct/object to make it align well?  Maybe some clever trick could
>>> be done
>>> to use wasted space, if it exists, for special tracking data...
>>> Otherwise,
>>> allocating a bit more seems the most sensible.
>>
>> Only arrays get the +1 byte added to their size during allocations. If an object occupies 16 bytes then it will end up in a 16 byte bucket. The +1 issue for arrays exists to make the program a bit more forgiving for "past the end" errors.  Interestingly, the ANSI C standard actually requires this behavior in its allocators.
> 
> So I went and looked up the clause and I'm not clear whether it requires the location to be physically available or merely fore the address to be valid for pointer mathematics.

C and C++ only require that the address be valid for pointer arithmetic; it need not be dereferencable.

-- James

James Dennett wrote:
> Sean Kelly wrote:
>> Sean Kelly wrote:
>>> Jason House wrote:
>>>> If object sizes are a power of 2, is that because of special padding
>>>> of a
>>>> struct/object to make it align well?  Maybe some clever trick could
>>>> be done
>>>> to use wasted space, if it exists, for special tracking data...
>>>> Otherwise,
>>>> allocating a bit more seems the most sensible.
>>> Only arrays get the +1 byte added to their size during allocations. If an object occupies 16 bytes then it will end up in a 16 byte
>>> bucket. The +1 issue for arrays exists to make the program a bit more
>>> forgiving for "past the end" errors.  Interestingly, the ANSI C
>>> standard actually requires this behavior in its allocators.
>> So I went and looked up the clause and I'm not clear whether it requires
>> the location to be physically available or merely fore the address to be
>> valid for pointer mathematics. 
> 
> C and C++ only require that the address be valid for pointer
> arithmetic; it need not be dereferencable.

Thanks.  This was what I inferred, but I had heard (or misheard) that it was the stronger guarantee and got confused when I didn't see this in the spec.  Unfortunately, as others have said, the "past the end" issue can cause other problems with garbage collection, so it seems that in D the extra byte of free space should typically be reserved anyway.


Sean