On 07.08.2013 18:18, Leandro Lucarella wrote:
> On Fri, Jun 21, 2013 at 11:37:45PM +0200, Rainer Schuetze wrote:
>> The size value itself is only a small issue, the larger one is the
>> address of the array data moves depending on the size of the
>> allocation, so the pointer info needs to be placed at some offset
>> sometimes. My first implementation actually figured this out in
>> the GC, but I think this leaks too much implementation details of
>> the array into the GC. So I changed it to use gc_emplace instead.
>
> Any reason not to use a more obvious name like setType() or similar?
>

I liked how it pairs quite well with std.emplace. But I'm open to suggestions, I'll note yours as gc_settype.
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

Le 7-août-2013 à 16:42, Rainer Schuetze <r.sagitario@gmx.de> a écrit :

> I'm also hoping for a comment on the ambiguity of TypeInfo_Class. If implementing TypeInfo_Reference, what would TypeInfo_Reference.toString return? "C ref" as in Michel Fortin's implementation of tail const references? ;-)

Funny problem. But there's no ambiguity really because you can't create using "new" a memory block that'll only contain a reference to an object. You can thus be sure that if the root type of a memory block is a TypeInfo_Class it truly is an object of that class; and if a *variable* has TypeInfo_Class then it's a reference.

Even my const(Object)ref patch did not change that. Try "new (C ref)()" or "new (const(C)ref)()" and you'll get a new object and not a pointer to a reference to the object. The "ref" part here was purely a syntactic mean to change the head-constness of the object type.

(Side note: Internally in the compiler there was a reference type created in some cases but it was mostly an implementation detail to facilitate propagating and checking for const. Most of the compiler code did not touch it, and that type was only used when the head-constness was different from the tail-constness anyway.)

-- 
Michel Fortin
michelfortin@aranatha.com

On 08.08.2013 03:05, Michel Fortin wrote:
> Le 7-août-2013 à 16:42, Rainer Schuetze<r.sagitario@gmx.de>  a écrit
> :
>
>>> I'm also hoping for a comment on the ambiguity of TypeInfo_Class.
>>> If implementing TypeInfo_Reference, what would
>>> TypeInfo_Reference.toString return? "C ref" as in Michel Fortin's
>>> implementation of tail const references?;-)
> Funny problem. But there's no ambiguity really because you can't
> create using "new" a memory block that'll only contain a reference to
> an object. You can thus be sure that if the root type of a memory
> block is a TypeInfo_Class it truly is an object of that class; and if
> a*variable*  has TypeInfo_Class then it's a reference.

That's what my code currently assumes. But that doesn't work if std.emplace is used to create a class instance into the memory of a struct instance. How can you distinguish that the memory is used as a reference or an instance of that class.

The same happens with classes generated into the data segment by the compiler, e.g. TypeInfo_Class objects. These currently don't have mutable references that could point into GC allocated memory, but a recent change also allows creating user defined class instances to be built into the data segment.
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

On Wed, Aug 07, 2013 at 10:42:25PM +0200, Rainer Schuetze wrote:
> On 07.08.2013 19:12, Leandro Lucarella wrote:
> >On Fri, Jun 21, 2013 at 09:37:51PM +0200, Leandro Lucarella wrote:
> >>>Before creating a pull request, I'd like to hear opinions on whether this should be included, if other choices would be better and where it should be improved.
> >>
> >>I'll read this e-mail in detail next week, and hopefully I'll take a look at the code too.
> >
> >Finally I had some time to do this. I made some comments in the commit themselves in GitHub.
> >
> 
> Thanks for the comments.
> 
> >Is there any reason why not to do the review with a proper pull request? For some reason you prefer to keep this somehow more private for now?
> >
> 
> It currently even fails to compile the druntime unittests because of the reported problems with the RTInfo generation. May it is better to let it fail in public ;-)

:O
I didn't even try to compile it to be honest, just looked at the code,
are you saying is not really working as it is now? I'm sorry, I'm not
familiar with all the RTInfo stuff.

> I also wanted to implement a different version for comparison, that stores the TypeInfo pointer in the allocation. I have a first attempt but it is quite a bit slower as it has to do some dynamic casting during scanning because of the way arrays are implemented. Some optimizations are needed to make an unbiased comparison, but other stuff distracted from doing this.

The old precise scanning patch I used with the concurrent collector did
that and the overhead was considerable:
http://www.llucax.com.ar/blog/blog/post/098ceae8
(and http://www.llucax.com.ar/blog/blog/post/1490c03e also analyze the
performance but is a little confusing, I'm not sure what happened there
because what I said in the text is not really reflected in the graphs
:P).

But it would be interesting to be able to compare it with the approach of storing the bits in a bitmap.

In any case, I don't think this should be a blocker, if this were the only problem it can be merged as is and improved in future pull requests.

> I'm also hoping for a comment on the ambiguity of TypeInfo_Class. If implementing TypeInfo_Reference, what would TypeInfo_Reference.toString return? "C ref" as in Michel Fortin's implementation of tail const references? ;-)

I can't really comment on this one, not very familiar with them either.

-- 
Leandro Lucarella
Senior R&D Developer
Sociomantic Labs GmbH <http://www.sociomantic.com>
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

On Wed, Aug 07, 2013 at 11:10:37PM +0200, Rainer Schuetze wrote:
> On 07.08.2013 18:18, Leandro Lucarella wrote:
> >On Fri, Jun 21, 2013 at 11:37:45PM +0200, Rainer Schuetze wrote:
> >>The size value itself is only a small issue, the larger one is the address of the array data moves depending on the size of the allocation, so the pointer info needs to be placed at some offset sometimes. My first implementation actually figured this out in the GC, but I think this leaks too much implementation details of the array into the GC. So I changed it to use gc_emplace instead.
> >
> >Any reason not to use a more obvious name like setType() or similar?
> >
> 
> I liked how it pairs quite well with std.emplace. But I'm open to suggestions, I'll note yours as gc_settype.

But emplace in that sense doesn't have a quite different meaning? One is initializing the content of the memory and the other just the "metadata". That's why I found it a bit confusing, because at first I thought it was messing with the actual memory block.

I guess is OK once you get used to it anyway though...

-- 
Leandro Lucarella
Senior R&D Developer
Sociomantic Labs GmbH <http://www.sociomantic.com>
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

Le 8-août-2013 à 0:54, Rainer Schuetze <r.sagitario@gmx.de> a écrit :

> On 08.08.2013 03:05, Michel Fortin wrote:
>> Funny problem. But there's no ambiguity really because you can't create using "new" a memory block that'll only contain a reference to an object. You can thus be sure that if the root type of a memory block is a TypeInfo_Class it truly is an object of that class; and if a*variable*  has TypeInfo_Class then it's a reference.
> 
> That's what my code currently assumes. But that doesn't work if std.emplace is used to create a class instance into the memory of a struct instance. How can you distinguish that the memory is used as a reference or an instance of that class.

More importantly, how would emplace signal the GC that it is instantiating an object of a certain type in "void[]" memory in the first place? For all you know, with emplace one could construct and destruct and reconstruct objects of different classes, or things other than classes, in the same block of memory. If emplace is calling a specific function to add a root of a certain type, you can create a special flag or separate function for "in-place objects" and make emplace call this function.

> The same happens with classes generated into the data segment by the compiler, e.g. TypeInfo_Class objects. These currently don't have mutable references that could point into GC allocated memory, but a recent change also allows creating user defined class instances to be built into the data segment.

I can't really comment on this because I have no idea how you're getting any typeinfo for the data segment.

-- 
Michel Fortin
michel.fortin@michelf.ca
http://michelf.ca

_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

On 08.08.2013 20:06, Michel Fortin wrote:
> Le 8-août-2013 à 0:54, Rainer Schuetze <r.sagitario@gmx.de> a écrit
> :
>
>> On 08.08.2013 03:05, Michel Fortin wrote:
>>> Funny problem. But there's no ambiguity really because you can't
>>> create using "new" a memory block that'll only contain a
>>> reference to an object. You can thus be sure that if the root
>>> type of a memory block is a TypeInfo_Class it truly is an object
>>> of that class; and if a*variable*  has TypeInfo_Class then it's a
>>> reference.
>>
>> That's what my code currently assumes. But that doesn't work if
>> std.emplace is used to create a class instance into the memory of a
>> struct instance. How can you distinguish that the memory is used as
>> a reference or an instance of that class.
>
> More importantly, how would emplace signal the GC that it is
> instantiating an object of a certain type in "void[]" memory in the
> first place? For all you know, with emplace one could construct and
> destruct and reconstruct objects of different classes, or things
> other than classes, in the same block of memory. If emplace is
> calling a specific function to add a root of a certain type, you can
> create a special flag or separate function for "in-place objects" and
> make emplace call this function.

That's what the new gc_emplace(void*p,size_t len,TypeInfo ti) function in the precise gc implementation is meant for.

>
>> The same happens with classes generated into the data segment by
>> the compiler, e.g. TypeInfo_Class objects. These currently don't
>> have mutable references that could point into GC allocated memory,
>> but a recent change also allows creating user defined class
>> instances to be built into the data segment.
>
> I can't really comment on this because I have no idea how you're
> getting any typeinfo for the data segment.
>

I have patched the compiler to emit this information. Without it false pointers in the data segment ruin all the efforts for the heap, because there is even no NO_SCAN flag for GUIDs, unicode encoding tables, strings, etc. (See also the dconf talk/slides) I intended to discuss it in a second step.
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

On 08.08.2013 16:06, Leandro Lucarella wrote:
> On Wed, Aug 07, 2013 at 10:42:25PM +0200, Rainer Schuetze wrote:
>> It currently even fails to compile the druntime unittests because of
>> the reported problems with the RTInfo generation. May it is better
>> to let it fail in public ;-)
>
> :O
> I didn't even try to compile it to be honest, just looked at the code,
> are you saying is not really working as it is now? I'm sorry, I'm not
> familiar with all the RTInfo stuff.

Unfortunately, for non-trivial programs it does not work out-of-the box, because you easily get link errors, mostly with respect to associative arrays. You can usually workaround these by adding aliases to the corresponding AssociativeArray(Key,Value) template somewhere. I recently managed to reduce it to something manageable:

http://d.puremagic.com/issues/show_bug.cgi?id=10786

The worse issue is silent non-generation of the RTInfo pointer, though the compiler replaces it with 0/1 that can be used for conservative scanning.

http://d.puremagic.com/issues/show_bug.cgi?id=10442

>
>> I also wanted to implement a different version for comparison, that
>> stores the TypeInfo pointer in the allocation. I have a first
>> attempt but it is quite a bit slower as it has to do some dynamic
>> casting during scanning because of the way arrays are implemented.
>> Some optimizations are needed to make an unbiased comparison, but
>> other stuff distracted from doing this.
>
> The old precise scanning patch I used with the concurrent collector did
> that and the overhead was considerable:
> http://www.llucax.com.ar/blog/blog/post/098ceae8
> (and http://www.llucax.com.ar/blog/blog/post/1490c03e also analyze the
> performance but is a little confusing, I'm not sure what happened there
> because what I said in the text is not really reflected in the graphs
> :P).

Thanks for the links, I think I already saw them long ago but reread them now. I'm not sure we can blame the precise scanning for increasing the size of an allocation dramatically by adding one pointer, causing the allocations to use the next bin of twice the size. This only happens for allocations that happen to match the bin sizes (or are designed with these GC internals in mind), for others the overhead for adding the pointer is zero.

In general we are already wasting 25% on average with these bin sizes that are a power of 2, we could mitigate the problem by adding some intermediate bin sizes.

One test I've run to test performance of the GC is testgc3 from the test suite, which just adds entries to a uint[uint] associative array.
A node in the hash list is 16 bytes for 32-bit processes, but 36 bytes due to pessimistic alignment assumptions for 64-bit processes. This causes 64 byte allocations by the GC with horrible results for both memory and performance for the 64-bit version in comparison with the 32-bit version.


_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

On Fri, Aug 09, 2013 at 10:47:33AM +0200, Rainer Schuetze wrote:
> On 08.08.2013 16:06, Leandro Lucarella wrote:
> >On Wed, Aug 07, 2013 at 10:42:25PM +0200, Rainer Schuetze wrote:
> >>It currently even fails to compile the druntime unittests because of the reported problems with the RTInfo generation. May it is better to let it fail in public ;-)
> >
> >:O
> >I didn't even try to compile it to be honest, just looked at the code,
> >are you saying is not really working as it is now? I'm sorry, I'm not
> >familiar with all the RTInfo stuff.
> 
> Unfortunately, for non-trivial programs it does not work out-of-the box, because you easily get link errors, mostly with respect to associative arrays. You can usually workaround these by adding aliases to the corresponding AssociativeArray(Key,Value) template somewhere. I recently managed to reduce it to something manageable:
> 
> http://d.puremagic.com/issues/show_bug.cgi?id=10786
> 
> The worse issue is silent non-generation of the RTInfo pointer, though the compiler replaces it with 0/1 that can be used for conservative scanning.
> 
> http://d.puremagic.com/issues/show_bug.cgi?id=10442

Oh! Bummer, I was under the impression that you had this working at some point.

> >>I also wanted to implement a different version for comparison, that stores the TypeInfo pointer in the allocation. I have a first attempt but it is quite a bit slower as it has to do some dynamic casting during scanning because of the way arrays are implemented. Some optimizations are needed to make an unbiased comparison, but other stuff distracted from doing this.
> >
> >The old precise scanning patch I used with the concurrent collector did
> >that and the overhead was considerable:
> >http://www.llucax.com.ar/blog/blog/post/098ceae8
> >(and http://www.llucax.com.ar/blog/blog/post/1490c03e also analyze the
> >performance but is a little confusing, I'm not sure what happened there
> >because what I said in the text is not really reflected in the graphs
> >:P).
> 
> Thanks for the links, I think I already saw them long ago but reread them now. I'm not sure we can blame the precise scanning for increasing the size of an allocation dramatically by adding one pointer, causing the allocations to use the next bin of twice the size. This only happens for allocations that happen to match the bin sizes (or are designed with these GC internals in mind), for others the overhead for adding the pointer is zero.

Yes, I know, but the values in the first post shows, at least for those
cases, it makes a difference. And I think for small sizes is very likely
that you have objects with the size as a bin (specially for 16 and 32).
When objects are larger, the chances of matching an exact bin size are
smaller.
Maybe an hybrid model would be the best approach.

And then, having to read the memory block could have bad cache effects, specially for object that are NO_SCAN, which otherwise would be never read from memory. Cache-wise I think bitmaps should behave better.

> In general we are already wasting 25% on average with these bin sizes that are a power of 2, we could mitigate the problem by adding some intermediate bin sizes.

True, but that's a different issue and not a justification to waste even more space :P

> One test I've run to test performance of the GC is testgc3 from the
> test suite, which just adds entries to a uint[uint] associative
> array.
> A node in the hash list is 16 bytes for 32-bit processes, but 36
> bytes due to pessimistic alignment assumptions for 64-bit processes.
> This causes 64 byte allocations by the GC with horrible results for
> both memory and performance for the 64-bit version in comparison
> with the 32-bit version.

:S

-- 
Leandro Lucarella
Senior R&D Developer
Sociomantic Labs GmbH <http://www.sociomantic.com>
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime

On Aug 9, 2013, at 2:55 AM, Leandro Lucarella <leandro.lucarella@sociomantic.com> wrote:

> On Fri, Aug 09, 2013 at 10:47:33AM +0200, Rainer Schuetze wrote:
>> 
>> 
>> Thanks for the links, I think I already saw them long ago but reread them now. I'm not sure we can blame the precise scanning for increasing the size of an allocation dramatically by adding one pointer, causing the allocations to use the next bin of twice the size. This only happens for allocations that happen to match the bin sizes (or are designed with these GC internals in mind), for others the overhead for adding the pointer is zero.
> 
> Yes, I know, but the values in the first post shows, at least for those
> cases, it makes a difference. And I think for small sizes is very likely
> that you have objects with the size as a bin (specially for 16 and 32).
> When objects are larger, the chances of matching an exact bin size are
> smaller.
> Maybe an hybrid model would be the best approach.

There's a related issue where array length is stored within the allocated space for a chunk.  And since programmers tend to allocate buffers with sizes that are powers of two, we're probably doing them a disservice here too.  But I'm not sure how best to handle this situation.

Regarding precise scanning, it seems like we really want TypeInfo present for a number of different reasons.  The bit array, a finalizer, and so on.  What if we had a TypeInfo registry inside the GC code?  Then we could limit the size to store a TypeInfo reference for a block to some number of bytes for an index value.  I can't imagine needing more than 4 bytes for this, and maybe 2 would be sufficient?

Given what I said above, I think we have 4 cases to consider anyway:

1. The block is untyped.
2. The block is a class or struct.
3. The block is an array.
4. The block is an array of structs.

Case 1 doesn't need any metadata, cases 2 needs to store precise scanning information and possibly a finalizer pointer, case 3 needs to store length information, and case 4 needs to store data from both case 2 and 3.  Assuming that array length storage is better integrated into the GC (and I think an argument could be made for expecting the GC to remember the allocation length requested by the caller), how could we store these different combinations of data most efficiently?

> And then, having to read the memory block could have bad cache effects, specially for object that are NO_SCAN, which otherwise would be never read from memory. Cache-wise I think bitmaps should behave better.

As much as the idea of a virtual function inside TypeInfo for scanning a block sounds appealing from a code perspective, I imagine that the proper approach is to have a bitmap and a few flags in TypeInfo and to let the GC implement the scanning code itself.  Reducing things further so that we could get to the bitmap with a single pointer dereference sounds like it could be tricky though, if we're trying to save space per block.  And further still, we could try and do things in a way that avoided cache misses, though at that point I imagine we'd be tweaking runtime or compiler code.
_______________________________________________
D-runtime mailing list
D-runtime@puremagic.com
http://lists.puremagic.com/mailman/listinfo/d-runtime