My understanding is that classes can have scanning data in their type info, but everything else (structs, etc) need to have scan info stored with the object. It would be interesting if the dynamic allocations were segmented into scan and no scan memory areas similar to what was suggested for static data.

Sent from my iPhone

On Aug 23, 2010, at 7:19 AM, Steve Schveighoffer <schveiguy at yahoo.com> wrote:

> From what I understand, that was what the original precise scanning patch did. Since the tables are static, having the compiler do it is a better idea.
> 
> But I think the "large footprint" might be somewhat of a strawman.  Yes, it will increase space, but I don't think it will be that much.  Consider that the precise scanning bits are static, and will be stored statically.  Have we run any tests to see how much space it actually adds?
> 
> -Steve
> 
> 
> 
> ----- Original Message ----
>> From: Andrei Alexandrescu <andrei at erdani.com>
>> To: Discuss the internals of DMD <dmd-internals at puremagic.com>
>> Sent: Mon, August 23, 2010 6:51:48 AM
>> Subject: Re: [dmd-internals] Giving better static data limits to the GC
>> 
>> I see, thanks. Could that or at least the bulk of it be done through a reflection mechanism? That would have the compiler generate a modicum of info, leaving the library to generate the costly  tables.
>> 
>> Andrei
>> 
>> On 08/22/2010 11:11 PM, Walter Bright  wrote:
>>> Having a precise collector requires the compiler to emit the  tables for it.
>>> 
>>> Andrei Alexandrescu wrote:
>>>> I'm  thinking - it's been the hallmark of druntime (vs. Phobos1) for the  longest time that it has a configurable GC. How about this - let's make the precise GC a custom collector. This would allow us to (a) compare the existing GC with the proposed GC and (b) tune druntime's details with a real-world alternate GC.
>>>> 
>>>> Is that all  possible?
>>>> 
>>>> Andrei
>>>> 
>>> _______________________________________________
>>> dmd-internals mailing  list
>>> dmd-internals at puremagic.com
>>> http://lists.puremagic.com/mailman/listinfo/dmd-internals
>> _______________________________________________
>> dmd-internals s mailing list
>> dmd-internals at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/dmd-internals
>> 
> 
> 
> 
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals

Andrei Alexandrescu, el 22 de agosto a las 22:59 me escribiste:
> I'm thinking - it's been the hallmark of druntime (vs. Phobos1) for the longest time that it has a configurable GC. How about this - let's make the precise GC a custom collector. This would allow us to (a) compare the existing GC with the proposed GC and (b) tune druntime's details with a real-world alternate GC.
> 
> Is that all possible?

Absolutely, the GC I'm working on is as configurable as possible, at startup-time via environment variables [1].

And since last night, a new configuration option was added, you can choose between stop-the-world and concurrent mark phase 8-) [2].

That's why I think the pointer bitmasks generation should be added to DMD, it doesn't affect the runtime, unless you explicitly use that information, it doesn't mean you have to provide a precise scanning GC by default.

[1] http://llucax.com.ar/blog/blog/post/-2c067531
[2] http://llucax.com.ar/blog/blog/post/-4c9dd5b5

-- 
Leandro Lucarella (AKA luca)                     http://llucax.com.ar/
----------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------
No es malo que en la condici?n humana exista la mentira. Miente el p?ber
si quiere ponerla.
	-- Ricardo Vaporeso. Madrid, 1921.

There is TypeInfo generated for structs too.  Why couldn't you store the bits for that type in that typeinfo?

The only issue I see is the overhead in storing a pointer to typeinfo for a small block (i.e. a 16-byte block adds 4 bytes of overhead to store at most 4 bits of pointer info).  For small blocks, you could store the bitmask with the block instead of a pointer to the bitmask.

-Steve



----- Original Message ----
> From: Jason House <jason.james.house at gmail.com>
> 
> My understanding is that classes can have scanning data in their type info, but
>everything else (structs, etc) need to have scan info stored with the object. It would be interesting if the dynamic allocations were segmented into scan and no scan memory areas similar to what was suggested for static data.
> 
> Sent  from my iPhone
> 
> On Aug 23, 2010, at 7:19 AM, Steve Schveighoffer <schveiguy at yahoo.com> wrote:
> 
> >  From what I understand, that was what the original precise scanning patch
>did.
>
> > Since the tables are static, having the compiler do it is a  better idea.
> > 
> > But I think the "large footprint" might be  somewhat of a strawman.  Yes, it
>will
>
> > increase space, but I don't  think it will be that much.  Consider that the precise scanning  bits are static, and will be stored statically.  Have we
>run
>
> > any  tests to see how much space it actually adds?
> > 
> > -Steve

Steve Schveighoffer, el 23 de agosto a las 05:40 me escribiste:
> There is TypeInfo generated for structs too.  Why couldn't you store the bits for that type in that typeinfo?

Yes, that's what the patch in bug 3463 do. The extra needed space is
proportional to the number of types created (and the size of the types),
but since TypeInfo and ClassInfo are so huge, the overhead wouldn't be
too much. Each type as an image of an instance for the .init property,
the pointer mask needs only type_size/word_size*2 **bits** (well
+ 1 word for the lengtt of the type), that is type_size/word_size/8*2
+ word_size bytes.

If the type infos with their bitmasks are grouped together in the binary, they might not even use real memory if nobody use them, as the pages they are in can be swapped out and nobody will notice.

> The only issue I see is the overhead in storing a pointer to typeinfo for a small block (i.e. a 16-byte block adds 4 bytes of overhead to store at most 4 bits of pointer info).  For small blocks, you could store the bitmask with the block instead of a pointer to the bitmask.

Please, take a look to the bug report, all that have been discussed.

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

Anyway, this is getting a little off-topic, I was asking for another thing (separating static data that should be scanned from the one that shouldn't, I don't know how hard could it be, that that has absolutely no overhead :).

-- 
Leandro Lucarella (AKA luca)                     http://llucax.com.ar/
----------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------
Every day 21 new born babies will be given to the wrong parents

Last time I read about the GC work, I had the impression that each allocation would store an extra int/pointer regardless of how small it was. I remember something like a 20% increase in memory footprint.

You raise a good point though. There's no need to use pointers to typeinfo or object-specific bit masks. An allocated block has a deterministic scanning pattern until it is collected. The memory footprint could be as efficient as the free memory block bits that are already in the GC.

Sent from my iPhone

On Aug 23, 2010, at 8:40 AM, Steve Schveighoffer <schveiguy at yahoo.com> wrote:

> There is TypeInfo generated for structs too.  Why couldn't you store the bits for that type in that typeinfo?
> 
> The only issue I see is the overhead in storing a pointer to typeinfo for a small block (i.e. a 16-byte block adds 4 bytes of overhead to store at most 4 bits of pointer info).  For small blocks, you could store the bitmask with the block instead of a pointer to the bitmask.
> 
> -Steve
> 
> 
> 
> ----- Original Message ----
>> From: Jason House <jason.james.house at gmail.com>
>> 
>> My understanding is that classes can have scanning data in their type info, but everything else (structs, etc) need to have scan info stored with the object. It would be interesting if the dynamic allocations were segmented into scan and no scan memory areas similar to what was suggested for static data.
>> 
>> Sent  from my iPhone
>> 
>> On Aug 23, 2010, at 7:19 AM, Steve Schveighoffer <schveiguy at yahoo.com> wrote:
>> 
>>> From what I understand, that was what the original precise scanning patch
>> did.
>> 
>>> Since the tables are static, having the compiler do it is a  better idea.
>>> 
>>> But I think the "large footprint" might be  somewhat of a strawman.  Yes, it
>> will
>> 
>>> increase space, but I don't  think it will be that much.  Consider that the precise scanning  bits are static, and will be stored statically.  Have we
>> run
>> 
>>> any  tests to see how much space it actually adds?
>>> 
>>> -Steve
> 
> 
> 
> 
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals

On 8/23/2010 5:32 AM, Leandro Lucarella wrote:
> That's why I think the pointer bitmasks generation should be added to DMD, it doesn't affect the runtime, unless you explicitly use that information, it doesn't mean you have to provide a precise scanning GC by default.
>

1. I think your idea of grouping static data that doesn't need to be scanned separately from static data that does is a good one. It means putting them into a different 'segment' in the object file, analogously to the way moduleinfo and eh tables are emitted into different segments.

2. Adding simple bitmasks to the typeinfo doesn't work that well - what to do about:

     struct S { ... }
     struct T { S[1000] s; }

It would generate a giant bitmap.

3. An idea (I think it was Andrei's) was for the TypeInfo for each type to have a virtual function that gets called by the GC to "scan this object". The advantage of this is it is completely flexible, and for many types custom marking code is going to be far faster than table driven, especially if that table is compressed.

4. Eventually, I'd like to add to TypeInfo's an array of [offset,TypeInfo] pairs for the fields. While awesome in power, that's going to be slow for the GC to use, hence the idea (3) for that.

On Wed, 01 Feb 2012 22:37:50 +0100, Walter Bright <walter at digitalmars.com> wrote:

>
>
> On 8/23/2010 5:32 AM, Leandro Lucarella wrote:
>> That's why I think the pointer bitmasks generation should be added to DMD, it doesn't affect the runtime, unless you explicitly use that information, it doesn't mean you have to provide a precise scanning GC by default.
>>
>
> 1. I think your idea of grouping static data that doesn't need to be scanned separately from static data that does is a good one. It means putting them into a different 'segment' in the object file, analogously to the way moduleinfo and eh tables are emitted into different segments.
>
You can't obtain sections for ELF files (only whole segments), so we'd have to use that clamping trick again. For shared libraries if used all writeable/allocated segments (there is usually only one). So the best way to save here is to move things into .rodata where possible.

The heap is usually orders of magnitude bigger than the static data, so it probably won't matter that much.

Walter Bright, el  1 de febrero a las 13:37 me escribiste:
> On 8/23/2010 5:32 AM, Leandro Lucarella wrote:
> >That's why I think the pointer bitmasks generation should be added to DMD, it doesn't affect the runtime, unless you explicitly use that information, it doesn't mean you have to provide a precise scanning GC by default.
> 
> 1. I think your idea of grouping static data that doesn't need to be scanned separately from static data that does is a good one. It means putting them into a different 'segment' in the object file, analogously to the way moduleinfo and eh tables are emitted into different segments.

Good to know that it's even possible. I remember having a huge impact in some cases (where there is a big static data segment with words that looked like pointers to chunks in the GC made garbage immortal).

> 2. Adding simple bitmasks to the typeinfo doesn't work that well - what to do about:
> 
>     struct S { ... }
>     struct T { S[1000] s; }
> 
> It would generate a giant bitmap.

Yes, I know that increasing the size of the executable is always bad, but having a program eating up all your memory is way worse. Also this can be made an option, so people caring about the size of the binary which don't have problems with the GC don't have to pay that price.

Also maybe some repetition pattern can be done (just thinking out loud
now).

> 3. An idea (I think it was Andrei's) was for the TypeInfo for each type to have a virtual function that gets called by the GC to "scan this object". The advantage of this is it is completely flexible, and for many types custom marking code is going to be far faster than table driven, especially if that table is compressed.

What I don't like about this is part of the GC implementation is done by the compiler. Having a function to scan the object might be flexible in one way, but it would be completely inflexible in others (you remove freedom to the GC implementation).

And supposing you go this way, how would be the signature of this method? How would this pass information to the GC on how to follow pointers? Maybe I don't understand it completely, but when I try to think about the details I can't get my head around it that easily.

Also I don't know how this goes with moving collectors. How would you be able to overwrite a pointer and how would you know when something must be scanned but not overwritten (union { size_t x; int* p; })?

> 4. Eventually, I'd like to add to TypeInfo's an array of [offset,TypeInfo] pairs for the fields. While awesome in power, that's going to be slow for the GC to use, hence the idea (3) for that.

I think this would be awesome, even if slow, because it would allow the GC implementation to have a lot of information to experiment. I.e. it would be good for research.

Also the GC could pre-process that information and store it in an internal format that's fast to process while scanning, so the only overhead would be at allocation time, which I think is not that bad.

Maybe this should be the first thing done. This way you enable people to use a GC that uses that information without needing to be the default "official" GC. Maybe this is fast enough and you don't even need to generate the virtual function to scan stuff. If you planned to do this eventually, I really think it would be a good idea to do it sooner than later.

-- 
Leandro Lucarella (AKA luca)                     http://llucax.com.ar/
----------------------------------------------------------------------
GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145  104C 949E BFB6 5F5A 8D05)
----------------------------------------------------------------------
You are the very reason why everything happens to you