(This is a spinoff from bug #516156.) It should be possible to scan objects exactly, ie, for the GC's scanner routine to know exactly where pointer-containing fields are and what their types are (esp Atom vs pointer). It should be possible for some objects to remain conservatively scanned while others are exactly scanned; that way, we can concentrate on writing exact scanners for important object types without having to write scanners for all object types.

We don't need MMGC_FASTBITS but we do need more per-object bit space, as introduced in bug #575316.

Ported from bug #516156 and rebased to redux 4901 plus the two patches from bug #575316.

Fixes a few bugs.

(Copied from bug #516156, lightly edited.) How to do partly-exact tracing in MMgc: It's a standard trick: mark objects that can be traced exactly with a special flag, and look for this flag in the tracer (GC::MarkItem). If the flag is set, invoke a custom tracer on the object (based on the value of the flag). In the simplest version, assume that if the flag is set then the object is a subtype of GCFinalizedObject; so call that class's virtual GCTrace method to perform the tracing. In a more complicated version, one flag value specifies a virtual method for tracing, others specify specific object types that don't have a VTable (pure GCObject subclasses). For now we have these parts that build one upon the other: - "new mark bits structure" patch: - provide space for the flag on a per-object basis, so we don't have to segregate allocators even more. The patch could be simpler, but the consequence of going to a byte per object means a lot of complexity drops away and the patch contains the resulting cleanup. - "gc support for partly-exact tracing" patch: - a facility to set the "exact" flag during object allocation, for qualifying object types - a check for the flag in the GC, with dispatch to a virtual method - support code that the custom GCTrace methods can call to trace known and unknown pointers - some refactoring to make it all hang together - "mutator changes for partly-exact tracing" patch: - changes to the ScriptObject constructor to allow a flag to be passed and set - custom allocator for ScriptObject that makes sure to set the exact flag by passing it to the constructor; this was not strictly necessary perhaps but simplified the client code - a custom tracer for ScriptObject, slot arrays, atom arrays While a host application probably would want to implement more custom tracers to take full benefit of the facility, and while we want to provide a custom tracer for StringObject, at least, and maybe other VM objects, handling just ScriptObject should take care of every AS3 class that doesn't have a native aspect that contains pointers that must be traced.

Conversation copied from bug #516156: Lars: "A substantial number of object types in the VM are derived from GCObject. On the one hand we'd like to trace these exactly without making them any larger, because there are many of them and making them larger is not a good thing. On the other hand, absent a virtual method or a function pointer in each of them, we must have many bits available to create a type discriminator for all the important types, and we must switch on this discriminator when we trace. Suppose we go with one byte per object for the various bits; four bits are already used, at most that gives us 14 different types (plus virtual method and conservatively traced). That's not a lot, so that means moving to two bytes per object. At that point, it becomes interesting to ask whether it is not simply better to make the interesting classes derive from GCFinalizedObject, so that they have a vtable and can use the virtual trace method. If the vtable introduces some sort of alignment issue in the object we risk paying two words for it - and that could be bad. In that case a new base class, GCObjectTraced could be used, which introduces an explicit function pointer - but that too could have some alignment issues. So measurements will be important. But it seems likely that we'll have to pay some memory here to get exact tracing, given the large number of different types we have." Ed: "Since ScriptObject and all AS3 user types already derive from GCFinalizedObject->RCObject, what are the chances that 14 of the remaining (many) GCObject-derived types represent the bulk of the non-GCFO population? if its any consolation, we could save a pointer per ScriptObject by exploiting the fact that user defined ScriptObject subclasses always share a common value for __proto__ (ScriptObject.delegate) -- we could move that to VTable. only vanilla instances of Object constructed with a user defined function have varying __proto__" Lars: "I don't know yet. I observe: class VTable : public MMgc::GCObject class Traits : public MMgc::GCObject class MultinameHashtable : public MMgc::GCObject class ImtEntry: public MMgc::GCObject class NamespaceSet : public MMgc::GCObject class QCachedItem : public MMgc::GCObject class ScopeTypeChain : public MMgc::GCObject class ScopeChain : public MMgc::GCObject class ExceptionHandlerTable : public MMgc::GCObject class E4XNodeAux : public MMgc::GCObject class E4XNode : public MMgc::GCObject class LineNumberRecord : public MMgc::GCObject class CodeContext : public MMgc::GCObject as well as class TextE4XNode : public E4XNode class CommentE4XNode : public E4XNode class AttributeE4XNode : public E4XNode class CDATAE4XNode : public E4XNode class PIE4XNode : public E4XNode class ElementE4XNode : public E4XNode It's my fault for not static the case precisely previously. Observe that we derive two benefits from exact tracing, namely precision (thus less false retention) and performance (when we're exactly tracing an object that has few pointers relative to its size). Performance improves when we don't have to guess at what a field is, and if we have many objects with a significant fraction of non-pointer fields. Precision improves with the fraction of all object types that have /any/ non-pointer fields that we trace exactly, because exact tracing precludes misidentifying int/double data as pointer data. So for performance we mainly care about GCObject-derived types that have many non-pointer fields, and of which there's a significant volume. Some profiling needs to happen to find this out. But for precision we care about many more types, probably."

Though the patches are preliminary - partial solution, several FIXMEs, of which not all are benign - they pass acceptance testing and run the standard benchmarks in 32-bit and 64-bit modes (Release build, MacPro).

See comments in bug #538943 about how we can, and should, get rid of ScriptObject::~ScriptObject and String::~String, if DRC is gone and exact tracing has introduced a way of distinguishing "clean" ScriptObjects from arbitrarily subclassed ones.

This is a minor observation, but if an object is to be scanned precisely then the size field in the mark stack item is not needed for scanning. It is currently used for some statistics and policy but I'm not sure how crucial it is, or whether that information could not be synthesized in some other way. It may be that as the volume of precisely scanned storage goes up, the object size should be computed on demand as only conservative scanning will need it, and relatively few objects will be scanned conservatively. (Unfortunately the value may need to be present on the mark stack - as zero - so that we can handle roots, large object splits, and so on.)

Preparatory cleanup item. GC::MarkItem_MMX has been dead for a long time; let's remove the code. The partly-exact tracer changes the structure of GC::MarkItem and if we want to resurrect MarkItem_MMX we'll have no use for the dead code currently in the file.

This is in fairly good shape, it has no FIXMEs and I'm pleased with how the refactoring of MarkItem turned out and how size computation has been moved off the exact path. The whole design biases in favor of exact marking. It passes acceptance testing and runs the benchmarks without problems. There's a solution in place for tracing large objects exactly, but that's not yet tested by the mutator patch (following right behind this one). Given the trickiness of large object splitting we should expect a little rough sailing here. The other thing that's still missing is optimization of Traits::traceSlots and GC::TraceSlots, which still do a bit-by-bit crawl through the slot descriptor bit map. See comments around GC::TraceSlots. (We also want to trace jitted stack frames precisely but I consider that out of scope for this patch.)

Further exploration of exact tracing. More to come.

Comment on attachment 456266 [details] [diff] [review] Cleanup: Remove dead code truly dead code!

Comment on attachment 456266 [details] [diff] [review] Cleanup: Remove dead code >Remove dead MMX version of GC::MarkItem > >diff --git a/MMgc/GC.cpp b/MMgc/GC.cpp >--- a/MMgc/GC.cpp >+++ b/MMgc/GC.cpp >@@ -2750,109 +2750,6 @@ > m_markStackOverflow = true; > } > >-#if 0 >- // TODO: SSE2 version >- void GC::MarkItem_MMX(const void *ptr, size_t size) >- { >- uintptr_t *p = (uintptr_t*) ptr; >- // deleted things are removed from the queue by setting them to null >- if(!p) >- return; >- >- bytesMarked += size; >- marks++; >- >- uintptr_t *end = p + (size / sizeof(void*)); >- uintptr_t thisPage = (uintptr_t)p & GCHeap::kBlockMask; >- >- // since MarkItem recurses we have to do this before entering the loop >- if(IsPointerToGCPage(ptr)) >- { >- int b = SetMark(ptr); >-#if defined(_DEBUG) && !defined(AVMPLUS_SAMPLER) // sampler does some marking which triggers this >- // def ref validation does a Trace which can >- // cause things on the work queue to be already marked >- // in incremental GC >- if(!validateDefRef) { >- GCAssert(!b); >- } >-#endif >- } >- >- _asm { >- // load memStart and End into mm0 >- movq mm0,memStart >- } >- >- while(p < end) >- { >- _asm { >- mov ebx, [p] >- mov ecx, [count] >- sar ecx, 1 >- mov eax, dword ptr [lowerBound] >- dec eax >- movd mm1, eax >- movd mm2, dword ptr [upperBound] >- punpckldq mm1, mm1 >- punpckldq mm2, mm2 >- mov eax, 3 >- movd mm5, eax >- punpckldq mm5, mm5 >- MarkLoop: >- movq mm0, qword ptr [ebx] >- movq mm3, mm0 >- pcmpgtd mm3, mm1 >- movq mm4, mm2 >- pcmpgtd mm4, mm0 >- pand mm3, mm4 >- packssdw mm3, mm3 >- movd eax, mm3 >- or eax, eax >- jz Advance >- >- // normalize and divide by 4K to get index >- psubd mm0, mm1 >- psrld mm0, 12 >- >- // shift amount to determine position in the byte (times 2 b/c 2 bits per page) >- movq mm6, mm0 >- pand mm6, mm5 >- pslld mm6, 1 >- packssdw mm6, mm6 >- >- // index = index >> 2 for pageMap index >- psrld mm0, 2 >- packssdw mm0, mm0 >- >- // check >- push ecx >- >- >- >- push [workAddr] >- movd edx, mm6 >- push edx // packShiftAmount >- movd edx, mm0 >- push edx // packIndex4 >- push eax // packTest >- push dword ptr [ebx+4] // val2 >- push dword ptr [ebx] // val1 >- mov ecx, [this] >- call ConservativeMarkMMXHelper >- >- pop ecx >- >- Advance: >- add ebx, 8 >- loop MarkLoop >- mov dword ptr [p], ebx >- } >- } >- } >- >-#endif >- > // HandleLargeMarkItem handles work items that are too big to > // marked atomically. We split the work item into two chunks: a > // small head (which we mark now) and a large tail (which we push

Hm, the upgrade to bugzilla has changed its behavior: the patch is quoted and any comment is ignored when marking a patch as obsolete. Dead code removal pushed as tamarin-redux changeset: 4912:70b67d07045f

Comment on attachment 456269 [details] [diff] [review] Preliminary patch: GC support for partly-exact tracing (v3) style nit: all other instance methods in GCObject and friends are initial-lowercase, not initial-cap; IMHO the GCTrace/GCTraceLarge methods should follow this precedent. efficiency nit: GCTrace() (and probably GCTraceLarge) would probably benefit from being FASTCALL.

Comment on attachment 456270 [details] [diff] [review] Preliminary patch: mutator changes for tracing ScriptObject, String, Namespace, E4X objects InlineHashtable::gcTraceAtoms() probably needs to check for logCapacity==0 (aka "not yet initialized") since it can be called on an uninited HT. nit: I'm guessing that the "bool gctrace" arg to the ScriptObject ctor will usually be a compiletime constant... would be nice if we could somehow add new ctors that implicitly specify this. (Not sure how to do so without adding a phantom arg, which defeats the purpose...) general thought: there's lots of avmglue code (especially in Flash) that is going to need to override the GCTrace() methods to get maximum benefit from this, since lots of that code declares custom fields in C++... however, if we added the long-talked-about way to declare private members in AS3 via nativegen.py then most of this could be handled automagically (since AS3-declared fields would be handled by the bitset in Traits). This would be a good impetus to finally finish that work...

(In reply to comment #17) > general thought: there's lots of avmglue code (especially in Flash) that is > going to need to override the GCTrace() methods to get maximum benefit from > this, since lots of that code declares custom fields in C++... however, if we > added the long-talked-about way to declare private members in AS3 via > nativegen.py then most of this could be handled automagically (since > AS3-declared fields would be handled by the bitset in Traits). This would be a > good impetus to finally finish that work... If I understand how this is designed, the deal is that we can incrementally do that work. objects without GCTrace simply get scanned conservatively. We can easily prioritize which classes to add GCTrace methods to based on object demographics. so a high priority task is to generate those object demographics. (and to do that work...). note that the object demographics can identify non-AS3 classes too, and there are probably some of those that outnumber some AS3 native classes. (MethodEnv?).

(In reply to comment #18) > > If I understand how this is designed, the deal is that we can incrementally do > that work. objects without GCTrace simply get scanned conservatively. Indeed, that's mainly why it's structured the way it is. It's "pay as you go". After handling ScriptObject and String, and with double being pointer-free, it's probably handling the bulk of objects already - the only open issue being VM-internal objects that may have a large volume, as you point out.

(In reply to comment #19) > Indeed, that's mainly why it's structured the way it is. It's "pay as you go". OK, but I stand by my assessment: one thing we've learned from looking at outside-the-VM glue code is that it needs to be much more bulletproof. Transitioning to the AS3-generated-slot approach would probably not be much more work that adding GCTrace methods, and be much more reliable.

I would agree that we don't want the player code riddled with GCTrace functions if we can avoid it. From my (out of date) recollection of profiling results VTable/Traits should be next. Is there a bug for that AS3 slot stuff?

No argument here that autogen'd GCTrace methods will be more reliable than hand-generated ones. I see it as additive but no reason to add nodes to the dependency graph for partly-exact tracing.

(In reply to comment #21) > Is there a bug for that AS3 slot stuff? https://bugzilla.mozilla.org/show_bug.cgi?id=578405 (In reply to comment #22) > I see it as additive but no reason to add nodes to the dependency graph for partly-exact tracing. Agreed; it's not a required dependency, but rather an optimization opportunity.

(In reply to comment #16) > Comment on attachment 456269 [details] [diff] [review] > Preliminary patch: GC support for partly-exact tracing (v3) > > style nit: all other instance methods in GCObject and friends are > initial-lowercase, not initial-cap; IMHO the GCTrace/GCTraceLarge methods > should follow this precedent. Fixed, against my better judgement (all instance methods in the GC are initial-cap). > efficiency nit: GCTrace() (and probably GCTraceLarge) would probably benefit > from being FASTCALL. Good point. On that note, I thought FASTCALL only applied to non-methods, but maybe it's the other way around, it only applies to methods? I see it used both ways in the code.

(In reply to comment #24) > > ... all instance methods in the GC are initial-cap. That's a lie, of course; for example the policy manager is all initial-lowercase. So consider my objection retracted.

(In reply to comment #17) > > InlineHashtable::gcTraceAtoms() probably needs to check for logCapacity==0 > (aka "not yet initialized") since it can be called on an uninited HT. Won't getAtoms return NULL in that case?

(In reply to comment #24) > On that note, I thought FASTCALL only applied to non-methods, but maybe it's > the other way around, it only applies to methods? I see it used both ways in > the code. FASTCALL can apply just fine to methods (but not ctors), at least in GCC and MSVC; of course, it's only useful for single-arg methods (since the first arg register is always 'this'). (In reply to comment #26) > Won't getAtoms return NULL in that case? REALLY_INLINE Atom* InlineHashtable::getAtoms() { return (Atom*)(m_atomsAndFlags & ~kAtomFlags); } ...if we're guaranteed that m_atomsAndFlags is always zeroed? Maybe.

(In reply to comment #27) > > > Won't getAtoms return NULL in that case? > > REALLY_INLINE Atom* InlineHashtable::getAtoms() > { > return (Atom*)(m_atomsAndFlags & ~kAtomFlags); > } > > ...if we're guaranteed that m_atomsAndFlags is always zeroed? Maybe. It's set to 0 in the constructor and elsewhere we assume that NULL is all-bits-zero. I think I shall assume that until proven wrong, but I'll keep it in mind as I test.

(I have additional pending changes to trace AtomArray precisely, and those changes were in place for the following experiment.) The following is the edited output from a simple object population profiler that accounts for object populations based on allocation site. Here we count the number of bytes and objects /traced/ conservatively broken down by allocation site. (Major thanks to Tommy and whoever else contributed to the new symbolification work on Mac.) The data are for jsbench/FFT. About 98% of the storage is traced exactly on that program already (or is pointer-free); the top 10 allocating sites for the remaining 2% or so of the storage - 7MB of tracing work - are these: 2646000 bytes - 47250 items - avmplus::AbcParser::parseMethodInfos 1829632 bytes - 112 items - avmplus::PoolObject::initPrecomputedMultinames 1245440 bytes - 30968 items - avmplus::DebuggerMethodInfo::create 811272 bytes - 14487 items - avmplus::AbcParser::parseMethodInfos 787136 bytes - 14056 items - avmplus::MethodEnv::newfunction avmplus::interpBoxed 682752 bytes - 112 items - avmplus::MultinameHashtable::grow avmplus::MultinameHashtable::add avmplus::addScript avmplus::DomainMgrFP10::addNamedScript 474432 bytes - 15008 items - avmplus::ScopeChain::create avmplus::MethodEnv::newfunction avmplus::interpBoxed 460112 bytes - 57 items - avmplus::TraitsBindings::alloc avmplus::Traits::_buildTraitsBindings avmplus::Traits::resolveSignaturesSelf avmplus::Traits::resolveSignatures 354368 bytes - 14952 items - avmplus::ScopeTypeChain::create 341376 bytes - 14224 items - avmplus::MethodEnv::newfunction avmplus::interpBoxed Note carefully that there are not eg 112 PrecomputedMultiName instances, because we account for that object once every time there's a GC (twice if it's a root - I haven't checked yet, but I suspect it). Also note carefully that I suspect the numbers to be fairly polluted by this being a Debug-Debugger run, better numbers should be forthcoming.

Oh, and stack and root storage are not accounted for at all right now - that will be fixed obviously.

One tricky issue is what we do with objects that can't have a vtable. For example, in BaseExecMgr::init we find this: #ifndef MEMORY_INFO MMGC_STATIC_ASSERT(offsetof(MethodInfo, _implGPR) == 0); #endif No code seems to depend on that invariant, presumably it's an efficiency concern. (Disabling the assertion and running causes no problems.) Adding a vtable to MethodInfo (actually MethodInfoProcHolder) will necessarily kill the invariant with most realistic object layouts. And even if MethodInfo turns out not to be a problem, other host objects might be. The way to get around that is to allow for the tracing function to be specified not with a vtable, ie for the object to carry a typetag or function pointer. However, adding a typetag at a known offset (usually 0) will lead us back to the same problem. We can add the typetag elsewhere in the object (but where?) or outside the object - in an object header maintained by the GC, if we had that, or in the GC bits. The GC bits are currently full (again). IMO a proper object header is inevitable in the long term, as it solves a bunch of problems that we're currently having with objects not being self-identifying; the current structure of the GC bits makes sense when there's only a byte per object, but if we had to move to even as little as two bytes per object in order to accomodate self-identification for some objects then a header would be vastly more attractive.

Another long talked about change was to have all the pool MethodInfo's be lumped together in one allocation instead of allocating them separately. If we had one vtable per pool of MethodInfo's then surely no one would complain ;-) Might speed up startup a little too.

I'm all for pay as you go but can things be done so that we only conservatively scan what we don't know about? I'm not sure how it would work but if we could exactly scan all declared slots and hashtable's exactly and only conservatively scan the C++ fields that would be great. If its too hard then moving to declaring everything in AS is even more warranted.

Is it time for MMgc to become avmplus::Atom aware? It would be nice to have atom savvy scanning of Hashtables and AtomArrays.

(In reply to comment #33) > One tricky issue is what we do with objects that can't have a vtable. For > example, in BaseExecMgr::init we find this: > > #ifndef MEMORY_INFO > MMGC_STATIC_ASSERT(offsetof(MethodInfo, _implGPR) == 0); > #endif I can vouch for this being just an efficiency concern, and probably obsolete, and needing a comment either way. IIRC stejohns added it when working on IMT stubs to ensure the _implGPR pointer is <32 bytes from the start of the object, which is advantageous for Thumb addressing modes. > IMO a proper object header is inevitable in the long term, as it solves a bunch > of problems that we're currently having with objects not being > self-identifying; the current structure of the GC bits makes sense when there's > only a byte per object, but if we had to move to even as little as two bytes > per object in order to accomodate self-identification for some objects then a > header would be vastly more attractive. Moving from a vtable to a header might break ties between an object's C++ type and its required storage class. Just something I've been thinking about while attempting to write down checkable GC rules, and probably a good thing.

(In reply to comment #35) > I'm all for pay as you go but can things be done so that we only > conservatively scan what we don't know about? I've rejected that in the past on the basis of a gut feeling that says it's too much hassle and not enough gain. I think we should revisit once the numbers are in on volumes and types of conservatively traced data in the Flash Player. > I'm not sure how it would work but if we > could exactly scan all declared slots and hashtable's exactly and only > conservatively scan the C++ fields that would be great. This would appear to insert further conditions on the tracing path, I'm not sure that's such a great idea. There are a lot already. But again, let's wait for the numbers and just keep the idea warm. > If its too hard then > moving to declaring everything in AS is even more warranted. That debate is definitely coming, though AS will have to get a lot more expressive in order to handle many data types for which there is significant volume, I expect. But for ScriptObject-derived types I think we could easily go in this direction, and it would be good to do so - the sources of error are just too many with hand-written tracers.

(In reply to comment #36) > Is it time for MMgc to become avmplus::Atom aware? It would be nice to have > atom savvy scanning of Hashtables and AtomArrays. See GC::TraceAtoms in GC.cpp in the patch set here :-)

(In reply to comment #39) > See GC::TraceAtoms in GC.cpp in the patch set here :-) I (obivously) haven't read the patches carefully, I was thrown off by this: REALLY_INLINE void InlineHashtable::gcTraceAtoms(MMgc::GC* gc) 255 { 256 gc->TraceObjectWithPointers(getAtoms()); 257 } 258

Hm, yes, appears that code is not quite finished. Thanks.

(General design note.) Consider MultinameHashtable, InlineHashtable, and quite a few others: When we have a object (owning object) that contains the only reference to some other object (owned object) we have two choices. Usually the owned object is some array allocated via Calloc or Alloc, ie, it does not have a vtable and is not even derived from GCObject. Since the owning object has the only reference to the owned object, the owning object can trace the owned object when the owned object is being traced. (Two steps: set the mark and trace the slots.) However, if the owned object is large this is wrong because it kills incrementality and mark stack control. Thus the more general solution, which is to create a container type for these arrays and allocate that container type with 'new (gc,extra) CT(...)', is usually preferable, even if it creates slightly higher heap consumption.

Couldn't the API be async? I mean the array could be pushed on to the mark stack and split up no?

Oh I get it, then the mark stack would have to be extended to know how to mark this memory somehow

So if you make a container type how do you get it to be incremental? Seems like it would still require some new mark stack smarts.

(In reply to comment #45) > So if you make a container type how do you get it to be incremental? Seems > like it would still require some new mark stack smarts. It's probably not fully developed in the patch currently attached to this bug but you can do this with a cursor system, there is a gcTraceLarge that's called multiple times with increasing values of a cursor. The object and the cursor are kept on the mark stack inbetween invocations.

With the following patches, passes all acceptance & performance testing and provides the capability to profile objects that are conservatively traced.

Simple framework that can be used in ad-hoc ways to profile an object population by allocation site and volume.

In addition to ScriptObject, String, Namespace, and E4X I've added many internal types, including MethodInfo, MethodEnv, Traits, TraitsBindings. There's a long tail (likely more than 100 types) of GC-internal types still scanned conservatively, I'm attacking them in order of decreasing scanning volume. That work is resulting in the developement of various ad-hoc techniques for scanning objects of different classes (for example, some can't have vtables), and those techniques are filtering back into the GC patch.

bug 583074 is accumulating a number of Dehydra ideas and experiments. One of them is able to find gc pointer members of arbitrary C++ types, and it wouldn't be hard to have it emit "candidate" trace methods for such types. (maybe sorted by population). It occurred to me that once an object is doing exact tracing, we probably have enough type information to do some tighter sanity checking on its mark method. So, if either of these ideas might be useful, respond here or on that bug.

I've been doing some profiling of non-exact scanning volume and it's fascinating. In addition to conservative marking I look at roots and stacks. Below, "roots" comprises normal GCRoots and alloca segments; "stacks" are, to the best of my knowledge, actual segments of the CPU stack. The volumes and object counts are accumulated across all GCs, this is ESC compiling itself in one invocation (loading one ABC file per compiler module, not a single merged ABC) and there are approx 17 GCs. The roots are scanned twice per GC so we can divide by 34 to get the appropriate root volume, approximately 30KB. That's higher than I would have expected and needs some investigation. A fraction of it - don't know how much yet - is the strings tables, see bug #596207. Roots: 1004848 bytes scanned - 1673 objs scanned Class 4-7: 132 bytes scanned - 33 objs scanned Class 32-63: 30800 bytes scanned - 770 objs scanned Class 64-127: 2904 bytes scanned - 33 objs scanned Class 128-255: 32220 bytes scanned - 186 objs scanned Class 256-511: 33172 bytes scanned - 91 objs scanned Class 512-1023: 183952 bytes scanned - 217 objs scanned Class 1024-2047: 275788 bytes scanned - 186 objs scanned Class 2048-4095: 404616 bytes scanned - 156 objs scanned Class 32768-65535: 41264 bytes scanned - 1 objs scanned The general impression about the stacks is that they're pretty deep, on average. This is probably because the parser and code generator both are recursive (especially the parser goes deep when it parses expressions) and more data on more programs are needed to draw lessons from this. If ESC is typical then the performance of stack pinning and interior pointer recognition will probably matter in practice, and exact tracing of stack frames (especially for the JIT) may pay off handsomely. Stacks: 518172 bytes scanned - 79 objs scanned Class 128-255: 244 bytes scanned - 1 objs scanned Class 512-1023: 1688 bytes scanned - 2 objs scanned Class 1024-2047: 19380 bytes scanned - 13 objs scanned Class 2048-4095: 45352 bytes scanned - 14 objs scanned Class 4096-8191: 147824 bytes scanned - 24 objs scanned Class 8192-16383: 250808 bytes scanned - 22 objs scanned Class 16384-32767: 52876 bytes scanned - 3 objs scanned

Data point: on ESC compiling itself in a single invocation, above 97% of the traced storage is traced exactly. The bulk of the conservative scanning (I would say above 95% of the conservative scanning but I don't have solid numbers yet) is for GCRoots and stack. That leaves a longish tail (representing 0.15% or so of the scanning by volume, allocated from 200 unique call stacks) of sundry internal objects, ScriptObject subtypes, and a few objects that are reached by (mis)identifying pointers in the stack and roots but should be reached through other paths. Conservative scanning can thus be cut further as follows: - allow roots to be scanned exactly (easy, and desirable) - reduce the volume of roots (desirable, often easy) - implement exact scanning for JIT stack frames (harder) - implement exact scanning for interpreter stack frames (tricky) - tackle the long tail of unhandled object types (laborious)

SWAG: what you've done so far gets us %30 exact marking for a flex app. If we exactly marked ScriptObject subclasses and one or two specific C++ objects we'd get flex apps up to %90 too. Do we want exact marking code to bleed into the player or should we be thinking about a automatic way to generate C++ pointer maps? This is one approach we could look at: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.37.9897&rep=rep1&type=pdf

IMO we want exact marking code to bleed into the player. I believe it's not going to be as bad as you think. A fair amount of the code can be generated by nativegen.py and it's entirely pay-as-you-go. But we'll see - I'm not committing either way, but if we generate anything it needs to be significantly more accurate than hand-writing it. (Also 30% sounds terribly low since the code now handles all AS3 subclasses of Object, what you're saying is that 70% of the objects in the Flex heap is going to be instances of Flash builtin classes. But I'm moving on to the full Player next so we'll see.)

The exact-marking code from nativegen.py should be bulletproof and straightforward; the main issue is native objects that add data fields in C++ that nativegen.py can't know about. IMHO a more robust solution would be to go ahead and implement the long-talked-about way to declare "private native" fields in AS3 directly (with nativegen-generated accessor wrappers), which will allow us to (gradually) move ScriptObject subclass member declarations out of C++ and into AS3, which we've long ago decided is desirable in the first place; if this was in place, the "manual rewrite" for making a native class be exact-marking would simply involve moving all member fields from C++ into AS3 -- end result would likely be more flexible and less error-prone in the long run.

(In reply to comment #55) > The exact-marking code from nativegen.py should be bulletproof and > straightforward; the main issue is native objects that add data fields in C++ > that nativegen.py can't know about. Yes, and it's not (for most classes so far) a big deal, there's a good pattern for it and the hard part is programmer discipline. The style we use many places in the VM with separate delineated data sections help /a lot/ and should be encouraged. > IMHO a more robust solution would be to go ahead and implement the > long-talked-about way to declare "private native" fields in AS3 directly (with > nativegen-generated accessor wrappers), which will allow us to (gradually) > move > ScriptObject subclass member declarations out of C++ and into AS3, which we've > long ago decided is desirable in the first place; if this was in place, the > "manual rewrite" for making a native class be exact-marking would simply > involve moving all member fields from C++ into AS3 -- end result would likely > be more flexible and less error-prone in the long run. That helps if the main issue is ScriptObject derived classes and not general GC-managed storage. For the VM at least that's far from the case; the hard cases are all in ad-hoc C++ code using GCObject/GCFinalizedObject. In particular, ScriptObject-derived classes tend to have adequate type discipline, while ad-hoc objects pun wildly, store tags left and right, and have unsafe unions whose contents can only be interpreted context-sensitively. (Don't get me wrong, handling just ScriptObject would be nice, but that's not what I'm most worried about at present.)

Lars: look thru the SO-derived native glue classes in Flash/AIR and I think you'll see what I mean: either way it will be a lot of churn, but IMHO the nativegen-generated approach will be far less error prone in the long run (and probably a similar amount of coding effort).

(In reply to comment #55) > The exact-marking code from nativegen.py should be bulletproof and > straightforward; the main issue is native objects that add data fields in C++ > that nativegen.py can't know about. > > IMHO a more robust solution would be to go ahead and implement the > long-talked-about way to declare "private native" fields in AS3 directly (with > nativegen-generated accessor wrappers), which will allow us to (gradually) move > ScriptObject subclass member declarations out of C++ and into AS3, which we've > long ago decided is desirable in the first place; if this was in place, the > "manual rewrite" for making a native class be exact-marking would simply > involve moving all member fields from C++ into AS3 -- end result would likely > be more flexible and less error-prone in the long run. pile-on! A complimentary approach is to scan C++ code directly for pointer fields, using Dehydra, as prototyped in bug 592553. This could be used as a safety net to statically check mark methods, detect missing mark methods, or as a development tool to generate new mark methods.

Until Dehydra is usable on Mac + Windows (at least), we shouldn't rely on it for anything other than a safety net.

I hear ya, but it also works great as a dev tool, to find pieces of code that can be hand modified. Most cross-platform code is visible. Notice that I didn't suggest depending on it for (say) auto generation of mark methods.

More data, with better statistics (fixed some bugs in the accounting). With ESC compiling itself, Mac Release 32-bit, GC time is not a big part of overall running time. 0.3% of all objects traced, and 1% of all storage traced, is still traced conservatively. Overall heap consumption is down, and running time is slightly down, and GC time is down, with exact tracing, but not so much that it makes a real difference on this test, and I don't know yet that it isn't noise. But nothing suggests that the GC is slower with these changes, or uses more memory.

Applies cleanly to TR 5215. Builtins must be rebuilt in core/ before compiling. This now carries changes to nativegen.py to auto-generate tracers for the parts of objects that are visible in AS3: a class is annotated with clsGC="exact" or instanceGC="exact", a small amount of hand-written C++ is then necessary. That amount can be reduced if the AS3 file were to contain more information, as discussed here earlier. Currently only clsGC is properly supported. All classes in core/ have been rewritten to use the new mechanism. AS3 object instances are still traced using hand-written tracers, this will be fixed shortly. Design documentation is slowly accumulating here: https://acrobat.com/#d=UCWhgWVzJeNr7Ph3M7y1Fw Five patches in the queue; they apply in this order: allocaAbuse (optional) exactMarking objectPopulationProfiling enableConservativeProfiler (optional) mutatorChanges

nit: it's a lot more convenient (IMHO) to look at patches in-browser than to download, unzip, apply.

Initial data from the Flash Player (Mac R-D Standalone): 79% of the object volume and 77% of the byte volume is scanned precisely (or is pointerfree) on checkinapp.swf after just dropping in my patch queue and cleaning up a couple of bugs in the Player (it likes to use HeapHashtable, WeakKeyHashtable, and WeakValueHashtable as members of other objects - a no-no that it would be great to be able to use static analysis to root out, as I'm now just relying on assertions). The tail of conservatively scanned objects comprises 8294 distinct stacks. The profile of conservatively scanned objects looks flat, with the top 30 by volume making up only about 10% of the conservatively scanned storage. I don't have good debugging information yet with which to interpret the stacks but the top conservatively scanned entry is the AS2 'ScriptObject' - sort of fascinating given that this is supposed to be an AS3 benchmark.

The situation on CignaTabbing is grimmer, with only 41% of the byte volume and 66% of the object volume being traced precisely (or being pointerfree). But here the top offenders are at least AS3 classes instantiated from the JIT code via ScriptObject::slowCreateInstance().

(In reply to comment #64) > I don't have > good debugging information yet with which to interpret the stacks but the top > conservatively scanned entry is the AS2 'ScriptObject' - sort of fascinating > given that this is supposed to be an AS3 benchmark. A large chunk of AS3 is implemented on top of the AS2 implementation, an expediency to ship FP9 that was never fixed. I suspect there's two or more complete copies of the AS2 global object which can be quite large. You really need a meaty flex app to drown out the AS2 stuff (which shouldn't grow much beyond the initial global object setup hit).

(In reply to comment #65) > The situation on CignaTabbing is grimmer, with only 41% of the byte volume and > 66% of the object volume being traced precisely (or being pointerfree). But > here the top offenders are at least AS3 classes instantiated from the JIT code > via ScriptObject::slowCreateInstance(). SObject and subclasses of DisplayObject will start to move up to the top of any really interesting flex app.

CignaTabbing, conservative scanning broken down by allocation site for byte volume over 1MB (based on top 30), multiple entries per site if there were multiple stacks leading to it, sorted by decreasing volume per site: 6668328 bytes scanned - 7621 objs scanned 5820384 bytes scanned - 6013 objs scanned 3817128 bytes scanned - 4124 objs scanned 2835992 bytes scanned - 2969 objs scanned 1071768 bytes scanned - 1126 objs scanned avmplus::SpriteObject::create(avmplus::VTable*, avmplus::ScriptObject*) (SpriteGlue.h:32) 7335360 bytes scanned - 5660 objs scanned 3865968 bytes scanned - 2983 objs scanned SObject::newRichEdit() (sobject.cpp:15417) 2724288 bytes scanned - 16216 objs scanned 605808 bytes scanned - 3606 objs scanned DisplayList::PlaceObject(CorePlayer*, SObject*, PlaceInfo*) (sdisplay.cpp:3241) 3089232 bytes scanned - 21453 objs scanned 1260576 bytes scanned - 8754 objs scanned SObject::Create(MMgc::GC*) (sobject.h:941) 982384 bytes scanned - 9446 objs scanned 868032 bytes scanned - 9864 objs scanned 795144 bytes scanned - 4733 objs scanned avmplus::EventDispatcherObject::create(avmplus::VTable*, avmplus::ScriptObject*) (EventDispatcherGlue.h:250) 1468800 bytes scanned - 30600 objs scanned 656880 bytes scanned - 13685 objs scanned avmplus::WeakMethodClosureClass::create(avmplus::MethodEnv*, avmplus::ScriptObject*) (EventDispatcherGlue.cpp:4942) 1901760 bytes scanned - 8490 objs scanned avmplus::TextFieldClass::createInstance(avmplus::VTable*, avmplus::ScriptObject*) (TextFieldGlue.cpp:73) 1063040 bytes scanned - 8305 objs scanned 685312 bytes scanned - 5354 objs scanned avmplus::InteractiveObject::set_booleanProperty(int, bool) (InteractiveObjectGlue.cpp:107) 1386336 bytes scanned - 8252 objs scanned DisplayList::PlaceObject(CorePlayer*, SObject*, PlaceInfo*) (sdisplay.cpp:3017) 1175104 bytes scanned - 5246 objs scanned avmplus::ShapeClass::createInstance(avmplus::VTable*, avmplus::ScriptObject*) (ShapeGlue.cpp:37) 1129216 bytes scanned - 8822 objs scanned avmplus::TextFormatClass::createInstance(avmplus::VTable*, avmplus::ScriptObject*) (TextFieldGlue.cpp:1693)

Cool data rocks! First we need exact scanning of AS3 native classes (duh), that will account for half of these RichEdit is a big class (one for each text field), I think they are like 500 bytes, however they only contain about a half dozen GC fields. Couple options for exact marking these, should we create a watson bug and discuss there? The 3rd and 4th are both SObjects, again should probably discuss strategies in a watson bug.

RichEdit is just a GCFinalizedObject and thus has a vtable and exact-tracing facilties already; all we need to do is write a tracer and turn on exact tracing for it. (Can't autogenerate that tracer but that's true for a lot of C++ objects already. Fact of life.) I'll sit on this over the weekend but you're probably right, the FP specific work needs to move out of Bugzilla. I'll take care of it and cross-link from here.

Watson 2605504 for FP discussion / tracking. P4 CL 722195 for pending FP changes.

(In reply to comment #71) > Watson 2605504 for FP discussion / tracking. Sigh... Watson 2726355.

(In reply to comment #64) > of bugs in the Player (it likes to use HeapHashtable, WeakKeyHashtable, and > WeakValueHashtable as members of other objects - a no-no that it would be great Hashtable (mis)usage is rampant in Flash player. The improved Hashtable suite in https://bugzilla.mozilla.org/show_bug.cgi?id=568664 would allow us to dramatically improve that (assuming I ever finish it)...

Applies in the order printed by "tar tzf". I may have one or two outstanding changes to make this compile in the Flash Player; if I get around to it today I will post or circulate a separate patch. I've incorporated the code that moves 'atom' from core/ to vmbase/ in this patch set. I'm not 100% convinced that's a good idea. To use the patch set without that change, a few instances of 'vmbase' qualification in MMgc/ will have to be reverted; it should not be a big deal. This patch set still relies on tracers generated from fields moved from C++ to AS3 in some cases. As discussed in bug #578405 that approach is almost certainly not workable in practice (too many gotchas) - and I do not expect the code in this patch to work on 64-bit systems for that reason.

Comment on attachment 480051 [details] Current patch queue Forgot: this applies cleanly to TR 5295.

Comment on attachment 480051 [details] Current patch queue The patch queue (which has been factored) is now maintained at hg.mozilla.org/users/lhansen_adobe.com/redux-revolution. At this time the queue is: exactMarking objectPopulationProfiling enableConservativeProfiler nonAs3Types stringAndNamespace scriptObject nativegen as3Types Please ignore the other patches, they haven't been refreshed in a few weeks and probably won't apply cleanly any longer.

(In reply to comment #76) > Comment on attachment 480051 [details] > Current patch queue > > The patch queue (which has been factored) is now maintained at > hg.mozilla.org/users/lhansen_adobe.com/redux-revolution. > > At this time the queue is: > > exactMarking Strangely enough, it seemed like I was able to build successfully using Xcode, but not using the xplat infrastructure (targeting x86_64-darwin release). In particular, I am getting the following error from g++: Compiling shell/PosixPartialPlatform In file included from /Users/fklockii/Dev/tr-revolution/core/avmplus.h:258, from /Users/fklockii/Dev/tr-revolution/vmbase/atom.cpp:41: /Users/fklockii/Dev/tr-revolution/core/avmplusList.h: In member function 'void avmplus::ListBase<T, LIST_RCObjects, ListAllocPolicy>::arraycopy(const T*, uint32_t, T*, uint32_t, size_t)': /Users/fklockii/Dev/tr-revolution/core/avmplusList.h:217: error: no matching function for call to 'MMgc::GC::movePointers(void**&, uint32_t&, const void**&, uint32_t&, size_t&)' /Users/fklockii/Dev/tr-revolution/MMgc/GC.h:475: note: candidates are: void MMgc::GC::movePointers(void*, void**, uint32_t, const void**, uint32_t, size_t) In file included from /Users/fklockii/Dev/tr-revolution/core/avmplus.h:258, from /Users/fklockii/Dev/tr-revolution/vmbase/AvmAssert.cpp:42: /Users/fklockii/Dev/tr-revolution/core/avmplusList.h: In member function 'void avmplus::ListBase<T, LIST_RCObjects, ListAllocPolicy>::arraycopy(const T*, uint32_t, T*, uint32_t, size_t)': /Users/fklockii/Dev/tr-revolution/core/avmplusList.h:217: error: no matching function for call to 'MMgc::GC::movePointers(void**&, uint32_t&, const void**&, uint32_t&, size_t&)' /Users/fklockii/Dev/tr-revolution/MMgc/GC.h:475: note: candidates are: void MMgc::GC::movePointers(void*, void**, uint32_t, const void**, uint32_t, size_t) make: *** [vmbase/atom.o] Error 1 make: *** Waiting for unfinished jobs.... make: *** [vmbase/AvmAssert.o] Error 1 Inspecting the code, it looks like this is an oversight; Lars updated one of the calls to movePointers in avmplusList.h in that patch, but another remains. But the difference in build behavior between Xcode and the xplat worries me a little. . . Questions: 1. Lars, have you done a build bot run with each of the patches individually? 2. If not, have you done a build bot run with all of the patches applied at once? (I just tried using xplat to build with all patches up to as3Types, and got a lot of warnings (and an entirely different error.)

FYI: applying exactMarking Trailing Whitespace(s) found in MMgc/GC-inlines.h for rev 5339 (change 84108c26bb13): @@ -495,6 +528,90 @@ + else ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a Trailing Whitespace(s) found in MMgc/GC.cpp for rev 5339 (change 84108c26bb13): @@ -1928,12 +1966,20 @@ + // marked atomically by splitting the work into chunks; the ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a Trailing Whitespace(s) found in MMgc/GCObject.cpp for rev 5339 (change 84108c26bb13): @@ -54,4 +71,13 @@ + gcTrace(gc); ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a Trailing Whitespace(s) found in MMgc/GCObject.h for rev 5339 (change 84108c26bb13): @@ -80,22 +81,122 @@ + * the traceable bit in their constructor by calling setExactGC(), ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a Trailing Whitespace(s) found in MMgc/GCPolicyManager.cpp for rev 5339 (change 84108c26bb13): @@ -391,11 +399,13 @@ + return ((bytesScannedExactlyTotal + bytesScannedConservativelyTotal + bytesScannedPointerfreeTotal) + ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a applying objectPopulationProfiling Trailing Whitespace(s) found in MMgc/GCMemoryProfiler.cpp for rev 5340 (change 15f5b8fc3912): @@ -729,6 +748,165 @@ + GCLog(" Class %d-%d: %llu bytes scanned - %u objs scanned\n", ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a applying enableConservativeProfiler applying nonAs3Types Trailing Whitespace(s) found in core/AtomArray.cpp for rev 5342 (change 21477ece573a): @@ -82,6 +83,42 @@ + work = capacity - (cursor * work_increment); ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a Trailing Whitespace(s) found in core/Exception.h for rev 5342 (change 21477ece573a): @@ -117,9 +117,19 @@ + { ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a Trailing Whitespace(s) found in core/MethodInfo.cpp for rev 5342 (change 21477ece573a): @@ -1012,4 +1059,21 @@ + // Complete outlier if a MethodSignature is 2KB or larger; ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a Trailing Whitespace(s) found in core/MultinameHashtable.cpp for rev 5342 (change 21477ece573a): @@ -43,14 +43,54 @@ + * i think it has roughly the same requirements as a general hashtable would -- parametitized value ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a Trailing Whitespace(s) found in core/PoolObject.h for rev 5342 (change 21477ece573a): @@ -197,13 +204,26 @@ + class ConstantStringContainer : public MMgc::GCTraceableObjectWithTrace ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a Trailing Whitespace(s) found in core/avmplusHashtable-inlines.h for rev 5342 (change 21477ece573a): @@ -300,6 +306,7 @@ + setExactGC(); ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a applying stringAndNamespace applying scriptObject Trailing Whitespace(s) found in core/Traits.cpp for rev 5344 (change 8244b94312c0): @@ -1966,6 +1966,58 @@ + for (uint32_t bit = 1; bit <= bitsUsed; bit++) ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a Trailing Whitespace(s) found in core/Traits.h for rev 5344 (change 8244b94312c0): @@ -421,7 +421,37 @@ + // Trace slot storage from a bitmap; useful for pointer-dense objects. ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a applying nativegen Trailing Whitespace(s) found in utils/exactgc.as for rev 5345 (change 668aab6397bc): @@ -0,0 +1,508 @@ +// - The ActionScript definition must have an native attribute annotation, ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a Trailing Whitespace(s) found in utils/nativegen.py for rev 5345 (change 668aab6397bc): @@ -38,6 +38,53 @@ +# If present this is the name of the type that will be used to declare the variable ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a applying as3Types patching file core/builtin.cpp Hunk #9 FAILED at 4511 1 out of 15 hunks FAILED -- saving rejects to file core/builtin.cpp.rej patching file core/builtin.h Hunk #1 FAILED at 865 1 out of 59 hunks FAILED -- saving rejects to file core/builtin.h.rej patch failed, unable to continue (try -v) Trailing Whitespace(s) found in core/ClassClosure.h for rev 5346 (change 82b3922bc8c0): @@ -89,8 +100,11 @@ + private: ^ (n)o, (y)es, (a)llow Trailing Whitespaces for current file Are you sure you want to commit this change? [n]: a patch failed, rejects left in working dir errors during apply, please fix and refresh as3Types

Initial feedback: using as3 for generating tracer could be problematic for player dev's, python would have been a better fit I think, I could see push back on a rule that says if you touch an exact traced class you have to build an avmshell but I think the dogfood principle wins out and building tamarin ain't that hard we should just prepare for it. We could build avmshell for the common platforms and check it into tools. what to do about custom fields like: class ScriptObjectAuxiliaryData { // can be an Atom, a GC pointer or a unmanaged pointer or a non-pointer value uintptr_t m_userData; } hand write gcTrace? Hate to do that but I guess its okay if its the exception rather than the rule. Seems like a lot of code, should measure code size increase? Seems like a lot of code out the MMgc, could we generate richer info and make code outside GC go away (ie pointer maps). Seems like an allocation should be able to declare its all atoms and MMgc takes care of it completely. Like maybe gcTrace could call another virtual gcTraceType() which could return some canned things like "ALL_ATOMS", or "ALL_POINTERS"? I mean the GC already knows what an Atom is to the jump to Atom * seems easy enough. HeapHashtable not done? Why not GCFinalizedObjectWithTrace, maybe because of subclasses? Re: subclassing ScriptObject and not implementing gcLargeTrace, comments seem wrong with new code gen approach, the new approach generates gcTrace it seems. We want a gcTraceLarge for some of those mammoth Flex types. Traits::gcTrace scares me. Should we look at using the trace gen stuff on internal stuff, seems less error prone. From my too much "code outside the GC" critique I don't think generated code counts ;-) Also we can easily switch gears (ie from function calls to a pointer map) with code gen. You could almost generate gcTrace function for poco (plain old C++ objects, ie not ScriptObject)'s by scanning the DWB macros, could we combine spec and write barrier? private: DWB(Traits*) m_supertype_cache; // 1-entry cache for subtypeof=true private: GCMemberRef<Traits> m_supertype_cache; // 1-entry cache for subtypeof=true Idea is gcTrace could be gen'd by scanning for GCMemberRefs (class would opt in with header spec), ifdef's would a problem if code gen was done at build time we could scan .i files (going off deep end?) gcTracePrivateProperties?? aren't these slots in the slot area? are we scanning these twice? Overall: I think we want more code gen, less hand coding outside the GC and some guarantees about write barrier/tracer agreement/correctness. Here again I'm thinking we have DEBUG mode write barriers that build up a pointer map that can be compared to the tracers somehow.

(In reply to comment #79) > Initial feedback: > > using as3 for generating tracer could be problematic for player dev's, > python would have been a better fit I think, I could see push back on > a rule that says if you touch an exact traced class you have to build > an avmshell but I think the dogfood principle wins out and building > tamarin ain't that hard we should just prepare for it. We could build > avmshell for the common platforms and check it into tools. I don't really care, but I hate Python and it was much faster for me to write the script in AS3. It can be rewritten. > what to do about custom fields like: > > class ScriptObjectAuxiliaryData { > // can be an Atom, a GC pointer or a unmanaged pointer or a non-pointer value > uintptr_t m_userData; > } > hand write gcTrace? Hate to do that but I guess its okay if its the > exception rather > than the rule. There are a couple of options. The GC has a method, TraceConservativePointer or something like that, that takes any value and figures out if it's a pointer or not. I've had to use it a couple of places where I could not figure out what the meaning of the field was. It is the exception to the rule, though. > Seems like a lot of code, should measure code size increase? I don't care about code size, though we might measure anyway. (New smartphones will have 0.5-1GB of RAM and 100x that much Flash disk, and download size won't matter greatly because Flash/AIR will be pre-installed if it's successful. Desktop systems are increasingly broadband-connected.) > Seems like a lot of code out the MMgc, could we generate richer info > and make code outside GC go away (ie pointer maps). These are pointer maps - without the overhead of interpretation. > Seems like an > allocation should be able to declare its all atoms and MMgc takes care > of it completely. I have no idea what you mean by that - apart from maybe having a data structure that specifies how the object is laid out. > Like maybe gcTrace could call another virtual > gcTraceType() which could return some canned things like "ALL_ATOMS", > or "ALL_POINTERS"? I mean the GC already knows what an Atom is > to the jump to Atom * seems easy enough. The variability in layouts probably precludes that. Specifics would be required. > HeapHashtable not done? Why not GCFinalizedObjectWithTrace, maybe > because of subclasses? Will look, could be an oversight. > Re: subclassing ScriptObject and not implementing gcLargeTrace, > comments seem wrong with new code gen approach, the new approach > generates gcTrace it seems. We want a gcTraceLarge for some of those > mammoth Flex types. Good point, will look into that. Though 2KB is still very, very large for objects, I remember some data from Alex H where he was talking about "large" objects being around 1K and complaining about fragmentation in the allocatr. > Traits::gcTrace scares me. Should we look at using the trace gen stuff > on internal stuff, seems less error prone. From my too much "code outside the > GC" critique I don't think generated code counts ;-) Also we can easily > switch gears (ie from function calls to a pointer map) with code gen. I think that generating code for as many non-glue classes as possible would be good, and I've started to think about that too. > You could almost generate gcTrace function for poco (plain old C++ objects, ie > not ScriptObject)'s by scanning the DWB macros, could we combine spec and write > barrier? > > private: DWB(Traits*) m_supertype_cache; // 1-entry cache for > subtypeof=true > > private: GCMemberRef<Traits> m_supertype_cache; // 1-entry cache > for subtypeof=true Thought about that and decided it was just error prone, I hate approximately-parsing fields. Hence the annotation system. The annotation system could be made stronger by having it look for strings that almost match, so that we could catch mistakes where the annotation was not written correctly. > Idea is gcTrace could be gen'd by scanning for GCMemberRefs (class > would opt in with header spec), ifdef's would a problem if code gen > was done at build time we could scan .i files (going off deep end?) I'm afraid so. #ifdefs are a problem in any case, I've hacked around it with the ifdef="..." attribute but don't know if the hack will be sufficient. (Another if="..." attribute would complement it.) > gcTracePrivateProperties?? aren't these slots in the slot area? are > we scanning these twice? Yes, that should go away for exactly that reason, but because of the bug with the slotDestroyInfo discussed on email it's currently saving my bacon. > Overall: I think we want more code gen, less hand coding outside the GC and > some guarantees about write barrier/tracer agreement/correctness. Agree. > Here again > I'm > thinking we have DEBUG mode write barriers that build up a pointer map that can > be > compared to the tracers somehow. That would be a useful facility. Thanks for the comments.

(In reply to comment #80) > These are pointer maps - without the overhead of interpretation. Sure but in my mind a bunch of calls to TraceObject* even if inlined will be the same speed as tight loop over a bitmap. I cite Steven's experiment with generated destroy funcs not helping. Also a method in the GC could take the inlining further (ie TraceFromPointerMap could inline everything) whereas this method only inlines TraceObjectWithoutPointers.

(In reply to comment #81) > (In reply to comment #80) > > These are pointer maps - without the overhead of interpretation. > > Sure but in my mind a bunch of calls to TraceObject* even if inlined will be > the same speed as tight loop over a bitmap. A tight loop over a pointer map will have an extra load (bit) and branch (kind of pointer to mark), and the load will be base+variable, whereas the load in the inlined mark code will be load base+const. That extra load+branch has a cost, so you'd have to argue that we'd make up for it (and then some) with the interpretive marker.

(hashed this out with Lars earlier in the morning, but wanted to record this detail somewhere) The exactMarking patch adds a GCTracedPointerContainer template, which is using the flexible array member[1] pun in a class that also declares virtual methods. Lars convinced me that we already rely on this (non-portable for C++) idiom working; i.e. no target that we support will put the vtable after the last member, since GCTracedPointerContainer's base class has virtual methods. We definitely do have classes with flexible array members that extend other classes that have virtual methods. But, as followup, I did a review [2] of other cases where we use the trick and I could not find any instance in the source trees of AVM nor the Player of a class with both a flexible array member and a virtual method declaration at the same time. This detail might be worth documenting in this code, or avoiding if possible. [1] The flexible array member pun is the pattern of putting an array member declaration of the form Baz foo[1]; at the very end of a class specifier, but instead of denoting an array of length 1, it represents a variable length array of Baz's. [2] Here's the grep command I used to browse the instances of the pun; it works well in tandem with Emacs M-x grep. find . -name '*.h' -exec grep --with-filename --line-number '\[1\];' '{}' ';'

I need a review of this at this point. Arguably it is not completely finished but the two things that remain are: - merge gcTrace and gcTraceLarge back into a single tracing method - optimizing common cases As far as merging the two methods is concerned, since almost all tracers will be generated by a script from annotations, nobody really cares a whole lot whether there are two or one - thus we could land this in its current shape and clean it up later. (I'm as eager to get out of rebasing hell as the next person.) As far as optimizations are concerned, a lot of that has to do with implementing special cases and also making the tracer generator smarter so that it can batch operations - that's all deferred to a different bug. Thus what I need a review on here is the functionality provided, the new base classes - in other words, what's here.

This is a simple framework, built atop the memory profiler, to profile data types that are traced conservatively. It needs to be switched on at compile time (see the next patch) and is not meant for production use, only for development use. It can't quite be applied independently from the previous patch because it fits into the code at a point where there's been a lot of refactoring churn, but logically speaking it is independent.

This simple patch turns on the object population profiler; it's useful to keep this apart from the other patch.

BTW the base is TR changeset: 5509:ef8f8c9629ce.

Comment on attachment 488834 [details] [diff] [review] GC infrastructure for exact marking There be tabs in this patch! Turning off my tab detector hook for now...

(reviewing now)

Comment on attachment 488834 [details] [diff] [review] GC infrastructure for exact marking In general I didn't find any major blocking issues, responses to comments you don't agree with would be nice. Notes: Taking size out of the mark stack will be nice! surely we should log a bug for GCRoot's being GC memory, I can't think of why that would make sense Future todo: The mark stack should probably be refactored out as a separate class, possibly hiding all the work item details behind a clean API. The first sentence of the HandleLargeMarkItem novella isn't gramatical, although its not an injection. "go the way of reference counting"? Where did DRC go? ;-) > // EXACTGC FIXME - is recursive marking still a good idea? Probably until we know for sure MarkItem isn't a hot spot Should TraceConservativePointer be inlined into MarkItem until we know its not a hotspot. I'm worry about slowing down the old vm. When safegc lands we should consider having: TracePointer(GCMember<T>&) Similar to what you're thinking with TraceAtom. > // EXACTGC OPTMIZEME: Here we can fold the ContainsPointers test into > // the marked test if there's a bit in the header indicating pointerfulness. We should also re-evaluate having separate pages for pointer free data. > PushWorkItem(GCWorkItem((void*)(cursor + 4), GCWorkItem::kInertPayload)); > if (!exactlyTraced->gcTraceLarge(this, cursor>>2)) Why the +4? and shift? Needs a comment. I read the comments before gcTraceLarge and still don't completely get it Should all the tracing base classes and functionality go into a separate header? GCObject.h will be less of a churn source if we do this (safegc is doing the same, ie moving GCMember out). Why burn a bit for kLargeObject test, GCLargeAlloc::IsLargeBlock isn't fast enough? Its a shame to copy GCObject into GCTraceableObject just to avoid GCFinalizedObject being a GCObject, maybe they could share a base class? For safegc we were planning on introducing a shared base class between GCObject and GCFinalizedObject so we could have one GCMember definition. I don't like that we now expose the un-prefixed MEMORY_INFO_ARG and HEAP_GRAPH_ARG to client code.

Thanks for the very useful comments. > > // EXACTGC FIXME - is recursive marking still a good idea? > > Probably until we know for sure MarkItem isn't a hot spot Right. Probably it won't be if we manage to convert an interesting fraction of objects to exact tracing. Note that exact tracing is /not/ recursive. > Should TraceConservativePointer be inlined into MarkItem until we > know its not a hotspot. I'm worry about slowing down the old vm. I've wondered about this, but the same argument goes: we really do not want conservative tracing to hit most of the storage. So I've decided against, for now, but I think we need to examine performance over time and possibly reconsider if profiling tells us otherwise. > When safegc lands we should consider having: > > TracePointer(GCMember<T>&) > > Similar to what you're thinking with TraceAtom. Absolutely. I've actually improved this API quite a bit in the new patch queue. > > PushWorkItem(GCWorkItem((void*)(cursor + 4), GCWorkItem::kInertPayload)); > > if (!exactlyTraced->gcTraceLarge(this, cursor>>2)) > > Why the +4? and shift? Needs a comment. I read the comments > before gcTraceLarge and still don't completely get it The cursor looks like a pointer, thus the two low bits must be zero. Yet the API is that the cursor increases monotonically by '1'. > Should all the tracing base classes and functionality go into a > separate header? GCObject.h will be less of a churn source if we > do this (safegc is doing the same, ie moving GCMember out). Are you thinking about GCTraceableObject (which is like GCObject) or the utility classes for exactly traced arrays? > Why burn a bit for kLargeObject test, GCLargeAlloc::IsLargeBlock > isn't fast enough? It's to allow a very fast test for the common case in MarkItem, but the bit will be reclaimed when gcTrace and gcTraceLarge are merged. > Its a shame to copy GCObject into GCTraceableObject just to avoid > GCFinalizedObject being a GCObject, maybe they could share a base > class? They're unrelated representations (one with a vtable, the other without), though in this case there's no destructor to worry about so at least the discussion is interesting. I don't mind the code duplication much right now because some of it will fall away again with future cleanup (probably). > I don't like that we now expose the un-prefixed MEMORY_INFO_ARG > and HEAP_GRAPH_ARG to client code. That's also gone in the new patch - the APIs are now called TraceLocation and always take the location containing a pointer / uintptr_t / Atom. Thus HEAP_GRAPH_ARG is hidden in the GC again. MEMORY_INFO_ARG disappeared (arguments were not used, holdover from old code).

Comment on attachment 488834 [details] [diff] [review] GC infrastructure for exact marking R+. Comments/questions below in order of importance (but all are mostly nits). What is the newly added GCWorkItem::GetCursor() method for? It looks like the old implementation of GetSize, but is currently not invoked anywhere in this patch, and it is undocumented. nit: Consider making PushWorkItem delegate to PushWorkItem_Unsafe rather than duplicating PushWorkItem_Unsafe's body in PushWorkItem. In this code (GC::WorkItemInvariants): // Some roots are on GC pages - a little unclear why, as of yet. So for // now just require non-GCItems not to point to GC objects. GCAssert(!IsPointerToGCPage(GetRealPointer(item.ptr)) || !IsPointerToGCObject(GetRealPointer(item.ptr))); am I correct that the reason you are not just asserting the second disjunct on its own is that it is not legal to call IsPointerToGCObject unless the first disjunct fails? (That's how I interpret the doc for _DEBUG mode of FindBeginningGuarded -- I had to go there because IsPointerToGCObject does not explicitly mention such constraints) Too bad that the refactoring of TraceConservativePointer was not (could not be?) factored into separate patch. (I did not review the relatively noisy changes to the code that became the body of TraceConservativePointer carefully; it looks like the conservative marking behavior has been kept approximately the same, as expected.) RE: the FIXME above SetHasGCTrace in GC.h: I thought this was addressed in the code in GC::HandleLargeMarkItem; is FIXME still relevant? Am I misunderstanding the two-word mark state that stores the pointer in order to recover the associated vtable? Or is this another notion of "split" that is not what is being handled by the cursor? RE: this comment in GC.cpp: // This is necessary if the destructor has been run because the destructor snaps // the vtable back to GCTraceableBase, which has pure virtual functions for // gcTrace and gcTraceLarge. The alternative here is to have empty base methods three things: 1. gcTrace and gcTraceLarge are not pure virtuals in this patch. 2. You can do both; i.e. you can implement pure virtuals; sample code below (though g++ does warn about calling pure virtuals from a class's destructor). BUT: would an empty base method actually do the right thing? I assume that control is actually reaching a point where the collector is looking at the exactly traced bit on an object whose destructor has run, and subsequently invoking the gcTrace method; with your current approach, is it being conservatively traced? That sounds very different than invoking an empty base gcTrace method. 3. Anyway they aren't pure virtuals, and they aren't empty base methods either (they're assert-fail methods), so I guess the point is that the comment should be revised to just point out the code is there to stop gcTrace from being invoked on destructed objects. /** sample code start **/ #include <stdio.h> struct A { A() { printf(" A()\n"); } ~A() { printf("~A()\n"); vmeth("line 5"); } virtual void vmeth(const char *s) = 0; }; struct B : public A { B() { printf(" B()\n"); } ~B() { printf("~B()\n"); vmeth("line 11"); } virtual void vmeth(const char *s) { printf("B::vmeth(\"%s\")\n", s); } }; void A::vmeth(const char *s) { printf("A::vmeth(\"%s\")\n", s); } int main() { B b; b.vmeth("line 19"); b.A::vmeth("line 20"); return 0; } /** sample code finis **/

Comment on attachment 488836 [details] [diff] [review] Enable the object population profiler I'm assuming and my +1 is predicated on this patch being separated from the the previous patch so don't push turning it on.

Comment on attachment 488835 [details] [diff] [review] Object population profiler Looks fine, the data is hard to interpret outside the context of how many collections occurred and the volume of exactly traced data. But its very useful by itself none-the less. One thing I used to measure is the mb/s MarkItem chewed threw. I'd be curious to know the mb/s of all the exact traffic vs. conservative traffic.

> What is the newly added GCWorkItem::GetCursor() method for? It looks > like the old implementation of GetSize, but is currently not invoked > anywhere in this patch, and it is undocumented. Dead code, thanks. > nit: Consider making PushWorkItem delegate to PushWorkItem_Unsafe > rather than duplicating PushWorkItem_Unsafe's body in PushWorkItem. I will consider it :) > In this code (GC::WorkItemInvariants): > // Some roots are on GC pages - a little unclear why, as of yet. So for > // now just require non-GCItems not to point to GC objects. > GCAssert(!IsPointerToGCPage(GetRealPointer(item.ptr)) || > !IsPointerToGCObject(GetRealPointer(item.ptr))); > am I correct that the reason you are not just asserting the second > disjunct on its own is that it is not legal to call > IsPointerToGCObject unless the first disjunct fails? Yes. > Too bad that the refactoring of TraceConservativePointer was not > (could not be?) factored into separate patch. (I did not review the > relatively noisy changes to the code that became the body of > TraceConservativePointer carefully; it looks like the conservative > marking behavior has been kept approximately the same, as expected.) That's a good point, actually. I'll consider that; a thorough review of that code by itself would be helpful. It's probably a half-day job to disentangle the changes but it may still be worth it. > RE: the FIXME above SetHasGCTrace in GC.h: I thought this was > addressed in the code in GC::HandleLargeMarkItem; is FIXME still > relevant? Am I misunderstanding the two-word mark state that > stores the pointer in order to recover the associated vtable? > Or is this another notion of "split" that is not what is being handled > by the cursor? I think what worries me here is: What happens if the object is reached before the bit is set and pushed onto the mark stack for conservative tracing, and the first chunk of the object is traced, and the bit is then set while the rest of the object exists on the stack. I /think/ this is going to be handled, the FIXME is there to remind me to look into it. (Clearly the reminder could have been more explicit.) To my shame there are too many FIXMEs in this patch, I need to attend to those before posting the final patch. > RE: this comment in GC.cpp: > // This is necessary if the destructor has been run because the destructor > snaps > // the vtable back to GCTraceableBase, which has pure virtual functions for > // gcTrace and gcTraceLarge. The alternative here is to have empty base > methods > three things: > 1. gcTrace and gcTraceLarge are not pure virtuals in this patch. Right, old comment but still applies to the existing code where the base methods always call GCHeap::Abort. > 2. You can do both; i.e. you can implement pure virtuals; sample code > below (though g++ does warn about calling pure virtuals from a > class's destructor). BUT: would an empty base method actually do > the right thing? It would - it would do nothing. Since the object is dead, and is only being reached through a false pointer, there would be no fields to trace. > I assume that control is actually reaching a > point where the collector is looking at the exactly traced bit on > an object whose destructor has run, and subsequently invoking the > gcTrace method; with your current approach, is it being > conservatively traced? Yes. > That sounds very different than invoking an > empty base gcTrace method. Yes it is. The latter is more correct; the former may actually cause false retention and/or cover latent bugs. > 3. Anyway they aren't pure virtuals, and they aren't empty base > methods either (they're assert-fail methods), so I guess the point > is that the comment should be revised to just point out the code is > there to stop gcTrace from being invoked on destructed objects. Will do.

(In reply to comment #91) > Are you thinking about GCTraceableObject (which is like GCObject) or the > utility classes for exactly traced arrays? I was thinking everything tracing related.

(In reply to comment #96) > (In reply to comment #91) > > > Are you thinking about GCTraceableObject (which is like GCObject) or the > > utility classes for exactly traced arrays? > > I was thinking everything tracing related. Hm, I don't know. GCTraceableObject is as fundamental as GCObject and GCFinalizedObject and GCTraceableBase is needed by two of those. I'm working on some cleanup and as part of that GCTraceableObjectWithTrace and GCFinalizedObjectWithTrace disappeared. The container structures could usefully be moved out of GCObject.h, conceivably out of MMgc altogether I think and exported from avmplus.

> > > Are you thinking about GCTraceableObject (which is like GCObject) or the > > > utility classes for exactly traced arrays? > > > > I was thinking everything tracing related. > > Hm, I don't know. GCTraceableObject is as fundamental as GCObject and > GCFinalizedObject and GCTraceableBase is needed by two of those. > > I'm working on some cleanup and as part of that GCTraceableObjectWithTrace > and GCFinalizedObjectWithTrace disappeared. > > The container structures could usefully be moved out of GCObject.h, > conceivably > out of MMgc altogether I think and exported from avmplus. Indeed, with the latest patches GCTracedPointerContainer disappeared (supplanted by GCList) and GCTracedStructContainer moved into core/ in the guise of an ExactStructContainer<> type.

Retargeting the tracker - the exactgc work is pretty much done for Serrano, a few bugs remain open and targeted.