Closed Bug 570608 Opened 14 years ago Closed 14 years ago

AtomArray should be rolled into List<>

Categories

(Tamarin Graveyard :: Virtual Machine, enhancement, P3)

enhancement

Tracking

(Not tracked)

RESOLVED FIXED
Q3 11 - Serrano

People

(Reporter: stejohns, Assigned: stejohns)

References

Details

Attachments

(4 files, 20 obsolete files)

55.73 KB, patch
lhansen
: review+
edwsmith
: superreview+
Details | Diff | Splinter Review
58.67 KB, patch
lhansen
: review+
edwsmith
: superreview+
Details | Diff | Splinter Review
1.85 KB, patch
lhansen
: review+
Details | Diff | Splinter Review
4.15 KB, patch
lhansen
: review+
Details | Diff | Splinter Review
List doesn't handle Atom, but could do so trivially; adding this would allow us to eliminate AtomArray. 

Note 1: we'd have to transplant a few methods that live on AtomArray (eg, splice).
Note 2: sizeof(List) > sizeof(AtomArray); the former includes an extra int32 and a GC* -- we would need to audit usage to see if the extra size matters and/or can be pruned.
Reworks List<> (in the style of Hashtable from bug 568664) to simplify and clean in preparation for expansion. Among other things, this removes the weird ListBase wart (a legacy from when some versions zeroed themselves in dtor and some didn't; now all do) and unifies allocation on GC always, never MMFX.
Assignee: nobody → stejohns
Attachment #450786 - Flags: feedback?(edwsmith)
Attached patch Add LIST_Atom (obsolete) — Splinter Review
Add a handler for Atom types, as well as a few methods that AtomArray supports but List doesn't.
Attachment #450787 - Flags: feedback?(edwsmith)
Attachment #450788 - Flags: feedback?(edwsmith)
Attached patch Remove AtomArray (obsolete) — Splinter Review
On MacTel, avmshell is ~25k smaller with this series of patches applied.
Attachment #450789 - Flags: feedback?(edwsmith)
Attachment #450786 - Flags: feedback?(lhansen)
Attachment #450787 - Flags: feedback?(lhansen)
Attachment #450788 - Flags: feedback?(lhansen)
Attachment #450789 - Flags: feedback?(lhansen)
Comment on attachment 450786 [details] [diff] [review]
Refactor list in preparation for augmentation

Seems like always using GC to allocate the list regardless of element type is a significant loss in functionality.  For example, PoolObject's int/uint cpools were fixed alloc, no pointers, and freed in ~PoolObject.  now they are gc alloc'd un-necessarily.

The classes in avmplusList.h need comments; each one should at least explain "whats it for".

ListData - why not make ListHelper be a friend?  too much template cruft to specify?
Attachment #450786 - Flags: feedback?(stan)
Attachment #450786 - Flags: feedback?(edwsmith) → feedback-
Comment on attachment 450787 [details] [diff] [review]
Add LIST_Atom

insert(), splice(), reverse() all seem bad to inline.   see (eg) eval/eval-util.cpp for examples of template methods not being inlined.  Explicit instantiation may be required;  is this feasible here, or for Hashtable?
Attachment #450787 - Flags: feedback?(edwsmith) → feedback-
Comment on attachment 450788 [details] [diff] [review]
Replace AtomArray with List<Atom>

seems like a straightforward application of the new data structures.

Stan recently was reviewing lots of avmplus code from a what-could-be-a-good-library point of view, I suggest pinging him for feedback.
Attachment #450788 - Flags: feedback?(edwsmith) → feedback+
Attachment #450789 - Flags: feedback?(edwsmith) → feedback+
(In reply to comment #5)
> (From update of attachment 450786 [details] [diff] [review])
> Seems like always using GC to allocate the list regardless of element type is a
> significant loss in functionality.  For example, PoolObject's int/uint cpools
> were fixed alloc, no pointers, and freed in ~PoolObject.  now they are gc
> alloc'd un-necessarily.

NonGCObject lists are still no-pointers, and still explicitly freed in ~PoolObject. It's true that GC allocation is unnecessary in these cases, but having everything gc allocated simplifies the allocation path, and also eliminates a potential memory leak: Stack-allocated List<> instance before could leak permanently if an exception skipped over their dtor. Using GC eliminates this possibility. IMHO it's a tradeoff worth considering; I'd like to hear Lars' opinion on whether the added GC pressure is likely to be significant or not. 

(Side note: it sure would be handy to be able to have mmfx memory with a "contains pointers" flag...)
 
> The classes in avmplusList.h need comments; each one should at least explain
> "whats it for".

Yep.
 
> ListData - why not make ListHelper be a friend?  too much template cruft to
> specify?

Yep, pretty much. I can go back and try to find the right incantation if you think it's worthwhile.

(In reply to comment #6)
> (From update of attachment 450787 [details] [diff] [review])
> insert(), splice(), reverse() all seem bad to inline.   see (eg)
> eval/eval-util.cpp for examples of template methods not being inlined. 

I guess I need to brush up on my template-fu, because I didn't think that all template methods are automatically inlined simply by virtue of being in a header file -- ie, I though "modern" (cough) compilers were smarter about this. That said, I'll review eval-util.cpp and see if moving it is practical.
Attachment #450786 - Attachment is obsolete: true
Attachment #450786 - Flags: feedback?(stan)
Attachment #450786 - Flags: feedback?(lhansen)
Attachment #450787 - Attachment is obsolete: true
Attachment #450787 - Flags: feedback?(lhansen)
Attachment #450788 - Attachment is obsolete: true
Attachment #450788 - Flags: feedback?(lhansen)
Attachment #450789 - Attachment is obsolete: true
Attachment #450789 - Flags: feedback?(lhansen)
Attached patch Refactor List (obsolete) — Splinter Review
Reworked version of the first two patches (refactoring List and adding a LIST_Atoms variant), incorporating various suggestions and cleanup. Two major notes:

-- restored the ability to have a non-GC based list (but only for LIST_NonGCObjects). Rather than have two distinct ctors as we used to, we now use gc==NULL as the distinguishing flag. 

-- split non-inlined methods into another header file, avmplusList-impl.h ... this is included by avmplusList.cpp, with specific instantiations, but the methods live in a header file so that other instantiations in embedders (eg Flash) can be added by simple inclusion. (see AbcGen.cpp for an example of this.)

Stan, I'd very much like your feedback on this general approach.
Attachment #456970 - Flags: review?(edwsmith)
Attachment #456970 - Flags: feedback?(stan)
Attachment #456971 - Flags: review?(edwsmith)
Attachment #456971 - Flags: feedback?(stan)
Attached patch Remove AtomArray (obsolete) — Splinter Review
Attachment #456972 - Flags: review?(edwsmith)
Attachment #456972 - Flags: feedback?(stan)
Comment on attachment 456971 [details] [diff] [review]
Replace AtomArray with List<Atom>

AtomArray had a (recently added) optimized ctor that used the efficient _ctor write barriers.  This change nukes that and will slow down AS code that uses a lot of Array literals.
(In reply to comment #12)
> AtomArray had a (recently added) optimized ctor that used the efficient _ctor
> write barriers.  This change nukes that and will slow down AS code that uses a
> lot of Array literals.

Oooh, nice tip. I'll investigate.
(In reply to comment #5)
> Seems like always using GC to allocate the list regardless of element type is a
> significant loss in functionality.  For example, PoolObject's int/uint cpools
> were fixed alloc, no pointers, and freed in ~PoolObject.  now they are gc
> alloc'd un-necessarily.

I'd like to (once again) challenge this assertion, as having a uniform always-gc allocation significantly streamlines the code; also, keep in mind that using fixed memory is only an option for LIST_NonGCObjects in the first place, and for those, we allocate without kContainsPointers (so the memory is never scanned anyway) and free explicitly. 

I see only two reasons to support non-gc allocation here:

(1) we have a need to use List<> when GC isn't available (which might be a factor for some Flash/AIR usage but is a nonfactor for all VM usage)

(2) switching LIST_NonGCObjects to use GC memory always (instead of "sometimes" as the code is now) would increase GC pressure enough to make a measurable impact on performance. No evidence of this, but I can do some quick benchmarking and see if any of the performance tests move the needle either way.
I agree about not supporting a runtime gc-or-not decision in the code.  I'd still like to see it be part of the template design, though.  there's a general desire to reduce GC pressure by not using GC to allocate objects that can easily be managed explicitly.  (yes, i'm aware of the exception throwing situation).  The only way its "okay" in my book to use GC mem when not required, is when its rare (and thus hardly any benefit of reducing gc pressure).  But I have no data supporting the idea that non-gc hashtables are rare.  do you?
> (2) switching LIST_NonGCObjects to use GC memory always (instead of "sometimes"
> as the code is now) would increase GC pressure enough to make a measurable
> impact on performance. No evidence of this, but I can do some quick
> benchmarking and see if any of the performance tests move the needle either
> way.

on (2) I would be looking at objection population data, not performance data.  Performance data will be noisy, and inconclusive, at best.
(In reply to comment #15)
> But I have no data supporting the idea that non-gc hashtables are
> rare.  do you?

We're actually talking List<> here, not Hashtable. No, I have no data offhand, but in the VM itself, the only place we use such lists are for a few constant pools (int, uint, multiname-offsets), as a component of SortedMap (used by the Verifier) and in AbcGen (which is going away soon). Flash/AIR likely have uses too. Of these, only SortedMap seems likely to matter -- I'll gather some usage numbers and see,

(In reply to comment #16)
> on (2) I would be looking at objection population data, not performance data. 
> Performance data will be noisy, and inconclusive, at best.

Yeah, that's what I found running tests overnight. 

(In reply to comment #15)
> I agree about not supporting a runtime gc-or-not decision in the code.  I'd
> still like to see it be part of the template design, though.  

Sure, the question is whether it's worth the time and code-complication to do so -- i.e., if non-gc-allocated lists aren't really making a difference, are they worth it?
In the case of PoolObject's cpool lists, we should just make them flat, fixed, array-of-int, etc.  the LIst class is really unjustified for what we use them for.  And we already know the lifetime of PoolObjects and explicitly free other things.
Turns out that Flash uses LIST_NonGCObjects in quite a few places, but the total memory usage and element count isn't that high -- see below.

Gathering a few numbers from hastily instrumented Flash builds, which track all LIST_NonGC usage (*except* for the ones in PoolObject, which, as noted above, don't need to be List in the first place):

-- running the Flex checkinapp, average list length is around  4; we never get above 300 or so Lists in existence at any time; including capacity overhead, peak list memory usage is around 8k

-- running ATS9AS3, average list length is around  5; including capacity overhead, peak list memory usage hovers around 76k.
(In reply to comment #19)
> -- running ATS9AS3, average list length is around  5; including capacity
> overhead, peak list memory usage hovers around 76k.

On that note: our default List capacity (if you omit the arg in the ctor, which much code does) is 128. Seems like it may be a bit high...?
Status: NEW → ASSIGNED
Flags: flashplayer-qrb+
Priority: -- → P3
Target Milestone: --- → flash10.2
Attachment #456970 - Attachment is obsolete: true
Attachment #456970 - Flags: review?(edwsmith)
Attachment #456970 - Flags: feedback?(stan)
Attachment #456971 - Attachment is obsolete: true
Attachment #456971 - Flags: review?(edwsmith)
Attachment #456971 - Flags: feedback?(stan)
Attachment #456972 - Attachment is obsolete: true
Attachment #456972 - Flags: review?(edwsmith)
Attachment #456972 - Flags: feedback?(stan)
The experiments so far have shown a number of a number of subtle but IMHO important issues (especially in defacto usage in Flash/AIR code), leading me to believe that a generic rewrite would be useful... so here it is. (Yes this is the Mother Of All Scope Creep, since this bug was was originally "make List<Atom> possible"...)

(1) We attempt to sniff the right type, but can sometimes get it wrong

There's clever code contributed by ChrisB that can usually infer the right type... except that there are some cases it can't guess correctly (mostly, forward-declared classes). This means we end up with explicitly-specified types, which can get copy-and-pasted incorrectly.

(2) It's possible to specify the wrong kind of memory handling

If you explicitly specify a memory handling type, there is little or no checking (compiletime or runtime) to verify that you made a reasonable choice. In particular, you can make a list of GCObject/RCObject that is handled via LIST_NonGCObjects, which can result in the list contents going stale in a dangerous way.

(3) there's a need for a Weak version, but none exists

See the previous item; most of these use cases appear to really "want" a WeakRef list, but didn't do so; having a first-class strongly-typed WeakList would make such use cases easy.

(4) default capacity seems dubiously large

If you omit the "initialCapacity" argument, we use 128. For many use cases this seems dubiously large.

(5) non-GC version can leak memory if stack-allocated and an exception is throw over dtor, or if dynamically allocated

LIST_NonGCObjects can be allocated using GC memory or FixedMalloc memory. In the latter case, we can easily leak memory if we do something like:

	List<int, LIST_NonGCObjects> foo;
	...
	core->throwException(); // foo is now leaked forever....

(6) RC version can leak memory if dynamically allocated due to missing DRC

Flash frequently allocates List dynamically, eg

	foo = new(gc) List<SomeObject*, LIST_RCObjects>(gc);

but there's a latent bug here, in that List<> isn't a finalized object; so while the underlying memory storage of the List is GC memory (and will eventually be reclaimed), the necessary DecrementRef calls to the objects stored in the lists won't happen when the List is reclaimed, causing potential suboptimal reclaiming of the contents.

(7) massive code bloat in XCode due to inling and code replication

All the methods in avmplusList.h are defined in the header file, resulting in implicit inlining of almost every method, appropriate or not. Also, while MSVC does a credible job of combining functions that have identical binary forms, XCode does not, so you end up with major code bloat

(8) it's wordy

Many declarations have a big "LIST_SomeDamnType" wart on the end.

Individually, this may be nits, but added up, they make my spidey-sense tingle: we have a lot of ways to do modestly-dangerous things, but compound interest adds up to something that will bite us. This patch introduces a suite of List classes (all based on one underlying template implementation):
	
	DataList<T> -- T must be a plain old data type, like int, float, etc. Will not hold any type of pointer.
	UnmanagedPointerList<T> -- T must be a pointer, and the pointer must not be managed by GC (no GCObjects or RCObjects allowed)
	GCList<T> -- T must be a subclass of GCObject/GCFinalizedObject (but not a subclass RCObject)
	RCList<T> -- T must be a subclass of RCObjects.
	WeakRefList<T> -- T must be a subclass of GCObject/GCFinalizedObject/RCObject, but is held by a weak reference.
				Accessing a no-longer-valid (ie, collected) entry simply returns NULL.

For all of the above, trying to use an incompatible type will cause COMPILE-time errors.

All of the above are legal to use either on the stack, or as a member of a GCObject, or as member of a GCRoot. What you can't do with them is dynamically allocate them via operator new; for that use, you will need to use a wrapper:

	HeapList< DataList<T> >, HeapList< GCList<T> >, ... etc.

This is unfortunate but the most reasonable away around the issue (namely, dynamically-allocated instances need a C++ vtable and finalization, others don't).

How does this address the issues above? 

(1) We attempt to sniff the right type, but can sometimes get it wrong
(2) It's possible to specify the wrong kind of memory handling

Type sniffing is gone; you now have to explicitly specify that handling you want (ouch), but, you can no longer get it wrong (as we'll generate compile-time errors if you try to use an inappropriate combination

(3) there's a need for a Weak version, but none exists

One exists, and is strongly typed, so you would be able to easily do

	WeakRefList<ScriptPlayer*> playersThatAreAlive;

(4) default capacity seems dubiously large

Stop offering a default value for the argument, and require an explicit capacity in the ctor call. (Existing code that omits it would probably get the existing value of "128" specified until/unless we can prove that a smaller value won't cause issues, so this is more an improvement for new code.)

(5) non-GC version can leak memory if stack-allocated and an exception is throw over dtor, or if dynamically allocated

I don't have a good solution for this; the simplest solution would be to remove the option for non-GC memory allocation, but there are legitimate use cases that prevent it. It may be possible to hook such list implementations into the exception stack so that have a built-in unwind as necessary, but I think that's a task for a followup bug; so for now, this one remains unaddressed.

(6) RC version can leak memory if dynamically allocated due to missing DRC

See the Heap variants above.

(7) massive code bloat in XCode due to inling and code replication

Here's the good part: the prototype I have makes *one* concrete instantiation for the underlying implementation RCList (and GCList, etc), then makes RCList as a purely inline wrapper around that. My quick test on Friday (MacTel Release Standalone x86-32 only, with code dead-stripping enabled) *decreased* code size by 200k. 

(8) it's wordy

	List<SomeObject*, LIST_RCObjects> -> RCList<SomeObject*>
Attachment #458499 - Flags: review?(edwsmith)
Attachment #458499 - Flags: feedback?(stan)
Attachment #458500 - Flags: review?(edwsmith)
Attachment #458500 - Flags: feedback?(stan)
Attached patch Replace AtomArray with AtomList (obsolete) — Splinter Review
Attachment #458501 - Flags: review?(edwsmith)
Attachment #458501 - Flags: feedback?(stan)
Attached patch Remove AtomArray (obsolete) — Splinter Review
Attachment #458502 - Flags: review?(edwsmith)
Attachment #458502 - Flags: feedback?(stan)
Attached patch Remove old List<> class (obsolete) — Splinter Review
Attachment #458503 - Flags: review?(edwsmith)
Attachment #458503 - Flags: feedback?(stan)
review ping...
Attachment #458499 - Flags: review?(edwsmith)
Attachment #458500 - Flags: review?(edwsmith)
Attachment #458501 - Flags: review?(edwsmith)
Attachment #458502 - Flags: review?(edwsmith)
Attachment #458503 - Flags: review?(edwsmith)
Blocks: 590693
Tweaked and vetted against performance tests; I think these are ready for a final review.
Attachment #458499 - Attachment is obsolete: true
Attachment #476102 - Flags: superreview?(edwsmith)
Attachment #476102 - Flags: review?(lhansen)
Attachment #458499 - Flags: feedback?(stan)
Attachment #458500 - Attachment is obsolete: true
Attachment #476103 - Flags: superreview?(edwsmith)
Attachment #476103 - Flags: review?(lhansen)
Attachment #458500 - Flags: feedback?(stan)
(note that I've omitted patches that remove the old List<> and AtomArray classes, but that would naturally follow after all Flash/AIR code was migrated)
Attachment #458501 - Attachment is obsolete: true
Attachment #458502 - Attachment is obsolete: true
Attachment #458503 - Attachment is obsolete: true
Attachment #476104 - Flags: superreview?(edwsmith)
Attachment #476104 - Flags: review?(lhansen)
Attachment #458501 - Flags: feedback?(stan)
Attachment #458502 - Flags: feedback?(stan)
Attachment #458503 - Flags: feedback?(stan)
Gentle review ping reminder...
NB: Although not part of this patchset, we can (and should) revise Vector to use this for storage as well, as most of the logic is essentially replicated. If/when this lands I'll make a followup patch for that.
(In reply to comment #15)
> I agree about not supporting a runtime gc-or-not decision in the code.
> I'd still like to see it be part of the template design, though.  there's a
> general desire to reduce GC pressure by not using GC to allocate objects 
> that can easily be managed explicitly.

I now believe that's an antipattern.  It removes the memory from view of the GC and that may significantly affect GC policy, both by increasing the rate of collections (increasing the amount of GC work) and decreasing it (letting the heap grow too large).  We've seen both bugs in practice and I recently changed the Vector code to maintain its pointerfree storage storage as GC storage.  On the flip side, GCHeap provides API to allow external allocations to be registered with it so that it can have a reasonable view of memory pressure, this was essential for the OOM work for 10.1 / mobile.
Comment on attachment 476102 [details] [diff] [review]
New suite of List<> replacement classes, v2

R- for bugs, but the code is very pretty.  I believe, based on no deep analysis, that exact tracing can be added without a lot of pain, but since exact tracing adds another base class (wohoo!) there will be more code, presumably.


GC.h/GC.cpp:

Naming bug: 'movePointers1' is not an acceptable name.  'movePointersWithinBlock' might be.

avmplusList.h:

In block comment at top, "However, they CANNOT be allocated dynamically ..." is incorrect.  They cannot be allocated using GC allocation, but standard mmfx_new should not be an issue, should it?

I don't really object to eg "move_range" but throughout much of the rest of the code we're more or less consistently using the style "moveRange" or "MoveRange".  In ListImpl you use ensureCapacity, indexOf.

Curious that there's no need for a GCFinalizedObject list.

Again I wish that the abbreviation "LH" would not be used in ListImpl since it's only used a tiny number of times, ListHelper would be clearer.

In the case of indexOf, lastIndexOf, what are the assumptions about equality?  Are we using '=='?  Will an overloaded '==' be used if provided?  Are there guarantees about calling patterns?  Etc.

In this comment (appears multiple times):

"// hackery that is necessary due to the fact that GCFinalizedObject
 // doesn't extend GCObject, for some unknown reason..."

It should be capitalized, and the editorializing is not useful.

I'm not sure this very public name is a good idea:

    MMgc::FixedMalloc* mmfx()


avmplusList-impl.h:

In ListImpl<T,LH>::add, is the index of the added element used so often that it's worth returning that value?  (Yeah, minor issue.)

Bug?  Uses of ensureCapacity are possibly unsafe (security issue): The use of ensureCapacity(x, n+m) is an anti-pattern, better is ensureCapacity(x, n, m) where ensureCapacity implements overflow-safe addition once.  I'm not sure if this is a big deal at present as we have a sub-4GB object size limit, but in principle: If I had two List<uint8_t> (byte lists) that each had more than 2G elements and appended one to the other then the size computation would overflow and the resulting successfully allocated structure would have a smallish array that we would try to store 4G elements into.  On 64-bit systems this might actually sort of work, opening up a security hole.  Drill down from GC::Calloc to see other code that handles the problem.  If you believe it's not a problem we probably want copious comments explaining why not.

Bug: lastIndexOf uses an int32_t for the length value, fetching it out of a uint32_t.

Generally there seems to be some schizophrenia in the code regarding how long a list can be, with length fields being uint but assertions and tests scattered throughout the code disproving that.  This strikes me as not-ideal.  ensureCapacity does not check whether the list is growing too long, making the field susceptible to overflows.

Bug: ListImpl::reverse is incorrect because it omits the write barrier.  Consider a large object that has been split by the marker: the pointers in the prefix of the object have been marked, but the pointers in the suffix of the object have not.  The object suffix is still on the mark stack.  Now we swap the pointers: the prefix is made to point to the objects from the suffix.  But those objects have not been marked, nor will they be marked because the prefix is no longer on the mark stack.


avmplusList-inlines.h:

Nothing to remark at this time.


avmplusList.cpp:

Capitalization, twice, at least:

    // force explicit instantiations for various non-inlined ListImpl methods... 
    // some compilers don't need this, but some do (I'm looking at you, XCode)
Attachment #476102 - Flags: review?(lhansen) → review-
Comment on attachment 476103 [details] [diff] [review]
Replace all usage of List<> in the VM with new List suite, v2

PoolObject.h:

Capitalize, punctuate:

+    // this is intended to be exactly the size of a double in memory
+    // (and is backed up by compiletime assertions)

SortedMap.h:

Incorrect, same comment as for the previous patch:

+     * However, it CANNOT be allocated dynamically
Attachment #476103 - Flags: review?(lhansen) → review+
Comment on attachment 476104 [details] [diff] [review]
Replace AtomArray with AtomList, v2

I mostly skimmed this but it seems straightforward.  I'm going to be in a lot of pain in the exact marking code when this lands but it mirrors some of the changes I've made anyway and it's clearly the right thing to move in this direction.
Attachment #476104 - Flags: review?(lhansen) → review+
Attachment #476102 - Flags: superreview?(edwsmith)
Comment on attachment 476103 [details] [diff] [review]
Replace all usage of List<> in the VM with new List suite, v2

Will this be a problem with exact marking, if GCObject sprouts a C++ vtable?

  MMGC_STATIC_ASSERT(sizeof(GCDouble) == sizeof(double));

Will all the new methods be covered by the acceptance tests? If not, we probably want some selftests dedicated to this library.  Especially considering the ensureCapacity comments from Lars.
Attachment #476103 - Flags: superreview?(edwsmith) → superreview+
GCObject cannot sprout a vtable, the world would come to an end.  There is a new base class for exact marking that has a vtable.
Attachment #476104 - Flags: superreview?(edwsmith) → superreview+
(In reply to comment #32)
> I now believe that's an antipattern.  It removes the memory from view of the GC

That brings up a nice meaty issue, then: if it's an antipattern, should we remove the option to use MMFX memory? 

(Related note: as followup work, I've been specifically requested to add a variant that allows using system allocators, so that the class suite can be used for platform-specific work before/after GC is inited. Obviously this would be limited to DataList/UnmanagedPointerList...)

(In reply to comment #33)
> Naming bug: 'movePointers1' is not an acceptable name. 
> 'movePointersWithinBlock' might be.

Deal.
 
> avmplusList.h:
> 
> In block comment at top, "However, they CANNOT be allocated dynamically ..." is
> incorrect.  They cannot be allocated using GC allocation, but standard mmfx_new
> should not be an issue, should it?

Not as written, since they have a private, unimplemented operator new. The idea is to force people to use the HeapList wrapper, which wraps it in a GCFinalizedObject to ensure the dtor is run. 

> I don't really object to eg "move_range" but throughout much of the rest of the
> code we're more or less consistently using the style "moveRange" or
> "MoveRange".  In ListImpl you use ensureCapacity, indexOf.

Yeah, not sure why I settled on that for the helpers. I can change 'em if you like.
 
> Curious that there's no need for a GCFinalizedObject list.

Er, there is, see HeapList.
 
> Again I wish that the abbreviation "LH" would not be used in ListImpl since
> it's only used a tiny number of times, ListHelper would be clearer.

I'll fix that.
 
> In the case of indexOf, lastIndexOf, what are the assumptions about equality? 
> Are we using '=='?  Will an overloaded '==' be used if provided?  Are there
> guarantees about calling patterns?  Etc.

We are using ==, and thus overloaded == should be used (but this has not been tested). I'll add some explicit comments.

> It should be capitalized, and the editorializing is not useful.

Stale comment, my confusion about lack of extension was answered but the comment wasn't updated.
 
> I'm not sure this very public name is a good idea:
> 
>     MMgc::FixedMalloc* mmfx()

Yeah, I'm of two minds on that -- I ended up adding it so that non-gc lists could have a terse creation syntax, ie

	DataList foo(mmfx(), 0); // terse
	DataList foo(MMgc::FixedMalloc::GetFixedMalloc(), 0); // yuck

But exposing the name public might be problematic. 

> In ListImpl<T,LH>::add, is the index of the added element used so often that
> it's worth returning that value?  (Yeah, minor issue.)

I don't really like it either; I left it that way to avoid changing a handful of existing glue-code usages that rely on it. But maybe we're better off having it return void and changing the users.
 
> Bug?  Uses of ensureCapacity are possibly unsafe (security issue): The use of
> ensureCapacity(x, n+m) is an anti-pattern, better is ensureCapacity(x, n, m)
> where ensureCapacity implements overflow-safe addition once. 

Nice catch, hadn't thought of that. I'll make the change.

> Bug: lastIndexOf uses an int32_t for the length value, fetching it out of a
> uint32_t.

Will fix.
 
> Generally there seems to be some schizophrenia in the code regarding how long a
> list can be, with length fields being uint but assertions and tests scattered
> throughout the code disproving that.  This strikes me as not-ideal. 
> ensureCapacity does not check whether the list is growing too long, making the
> field susceptible to overflows.

Will investigate and improve.
 
> Bug: ListImpl::reverse is incorrect because it omits the write barrier. 

Nice catch, I forgot about the splitting of large bits. Will add WB.

> (various capitalization comments)

Will fix.

> I'm going to be in a lot
> of pain in the exact marking code when this lands but it mirrors some of the
> changes I've made anyway and it's clearly the right thing to move in this
> direction.

Anything we can do to lessen the future pain? 

(In reply to comment #36)
> Will all the new methods be covered by the acceptance tests?

Yes -- everything here is replacing existing code, which (we believe) is fully tested by existing acceptance tests.
Patch with the corrections detailed in Comment 34.
Attachment #476102 - Attachment is obsolete: true
Attachment #478936 - Flags: review?(lhansen)
The "v3" set of patches omitted the newly-added files (-inlines.h, etc)... ooops
Attachment #478936 - Attachment is obsolete: true
Attachment #479183 - Flags: review?(lhansen)
Attachment #478936 - Flags: review?(lhansen)
Blocks: 597577
gentle review ping...
One note on this: I've tried to maintain the same (or very similar) API to the previous List<> structure doing this, but I'm thinking that one deviation is worth doing: rename size() to length(). IMHO size() has always been a dodgy name, since it's returning length, not size-in-byte, so length() is probably a more reasonable choice. Will require more churn, but some of that will be necessary anyway. (Also, it lends itself much more readily to adding a set_length() method in the future, which will probably be necessary if we rewrite VectorObject to use these classes...)
Attached patch change size() to length() (obsolete) — Splinter Review
followup patch to rename the size() method and related constants. More churn than I expected, but IMHO worth it.
Attachment #480671 - Flags: review?(lhansen)
Comment on attachment 479183 [details] [diff] [review]
New suite of List<> replacement classes, v4

Bugs:

It is wrong if a HeapList (which is GC-managed storage) points to FixedAlloc-allocated storage, because this hides actual memory pressure from the GC.  Don't know what to do about it except GC storage uniformly for all the lists.

One bug in removeAt noted below.

(Fix what you think is appropriate; no re-review needed.)


Nits:

avmplusList.h.:

This comment:

  "(Note, since MMgc currently doesn't allow allocations over 4GB, this 
   won't cause any problems with existing code.)"

is of dubous value, since it's "current" MMgc and "existing" code, ie, the comment is potentially stale the minute it lands, and thereafter misleading.  Does the comment contribute anything?  I think not.  If you choose to keep it you /must/ qualify it with a date, I usually insert something like "now=2010-10-06" in my comments when I talk about time.

It probably wouldn't kill us to have documentation for ListImpl::ListImpl so that we can document the meaning of capacity and args.

Should "Ensure the ListImpl can hold ..." really be "Ensure that the ListImpl can hold ..."?  (My ear says yes but then it's a foreign ear.)

In the comment for ListImpl::bytesUsed() you are using the word "itself", which suggests to me that it is the ListImpl object only.  Presumably that's not what you're trying to say, but rather "the ListImpl instance and its private data".

As a general style comment the parameter lists for all of the constructors in this file (with one parameter per line) are poorly indented.


avmplusList-impl.h:

indexOf uses (int32_t)i, while lastIndexOf uses int32_t(i).  No worse than the variable pointerhugging I do, but still would be good to be consistent.

Again, poorly indented constructors.

In reverse(), "(len >> 1)" is really not pretty.  Why not "len/2"?  The variable is unsigned and any compiler worth its salt will get this right.  (Arguably the same in ensureCapacityImpl where it could be "cap/4" and not "cap >> 2".)

Bug? In removeAt the removed element is not cleared if it is the last element.  

(On the whole I find removeAt to be confusing, probably because moveRange is relied on to clear storage but is a no-op if zero elements are moved.  That problem causes (I'm guessing) the early decrementation of len, from which follows the surprising "len-index" last argument to moveRange where "len-index-1" would have been more natural.  If it were me I would move the decrementation of len to the last moment and restructure around that, but I don't know how much it would help.)


avmplusList-inlines.h:

This comment around allocData is dodgy:

"Since almost all List usage has sizeof(T) <= (sizeof(LISTDATA) - sizeof(T)),  waste is not really a concern."

It's just stating that sizeof(LISTDATA) >= 2*sizeof(T) in almost all cases.  Actually sizeof(LISTDATA) == sizeof(T)+8 in all cases, which is possibly more informative, but apart from all that I don't understand what the statement has to do with anything.  Maybe the problem is that the comment says "Simplify overflow checking", not "Delegate overflow checking to Calloc" - the latter would express the intent more clearly.  I think the comment block needs to be cleaned up to better express what's going on.

Generally the moveRange bodies are poorly indented.
Attachment #479183 - Flags: review?(lhansen) → review+
BTW I would really appreciate it if you could hold off on replacing AtomArray with List<> until I've converted the exact GC infrastructure to use the new List<> class, after you land that - I expect turbulence and will need to recover from that.
Comment on attachment 480671 [details] [diff] [review]
change size() to length()

(Skimmed it.)

I'm indifferent, seems like a lot of churn for little gain if you ask me, but also does not seem to be a big problem with landing it.
Attachment #480671 - Flags: review?(lhansen) → review+
(In reply to comment #44)
> It is wrong if a HeapList (which is GC-managed storage) points to
> FixedAlloc-allocated storage, because this hides actual memory pressure from
> the GC.  Don't know what to do about it except GC storage uniformly for all the
> lists.

I'd actually prefer to use GC storage uniformly; it is not the case right now mainly because Edwin pushed back hard against it (see Comment 5)... if you think there's no downside to using GC for all allocations, I'd be happy to change it.

That said, there is a way to mitigate this, by calling SignalDependentAllocation()/SignalDependentDeallocation() [which is what the Player's version of ByteArray does, see Bug 564248]... but using GC memory directly is a simpler approach, assuming Edwin's concerns aren't critical.
 
> One bug in removeAt noted below.
> 
> Does the comment contribute anything?  I think not.  If you choose to keep it
> you /must/ qualify it with a date, I usually insert something like
> "now=2010-10-06" in my comments when I talk about time.

Probably correct. I'll just nuke it.
 
> It probably wouldn't kill us to have documentation for ListImpl::ListImpl so
> that we can document the meaning of capacity and args.

Agreed.
 
> Should "Ensure the ListImpl can hold ..." really be "Ensure that the ListImpl
> can hold ..."?  (My ear says yes but then it's a foreign ear.)

Both sound valid to me, but then, I am just a caveman programmer, not an English major.
 
> In the comment for ListImpl::bytesUsed() you are using the word "itself", which
> suggests to me that it is the ListImpl object only.  Presumably that's not what
> you're trying to say, but rather "the ListImpl instance and its private data".

Will clarify.
 
> As a general style comment the parameter lists for all of the constructors in
> this file (with one parameter per line) are poorly indented.

Willfix.

> avmplusList-impl.h:
> 
> indexOf uses (int32_t)i, while lastIndexOf uses int32_t(i).  No worse than the
> variable pointerhugging I do, but still would be good to be consistent.

Yup.
 
> Again, poorly indented constructors.

I love review comments like this, it means the reviewer can't find meaty things to complain about :-)

> In reverse(), "(len >> 1)" is really not pretty.  Why not "len/2"?  The
> variable is unsigned and any compiler worth its salt will get this right. 
> (Arguably the same in ensureCapacityImpl where it could be "cap/4" and not "cap
> >> 2".)

Old habits die hard, I guess; I'm still bitten by early-90's MPW C...
 
> Bug? In removeAt the removed element is not cleared if it is the last element.  

Oooh, think you're right. Will address. (Odd that no acceptance test found this, will investigate.)

> overflow checking", not "Delegate overflow checking to Calloc" - the latter
> would express the intent more clearly.  I think the comment block needs to be
> cleaned up to better express what's going on.

Yeah, that's basically the intent. Will cleanup.

(In reply to comment #45)
> BTW I would really appreciate it if you could hold off on replacing AtomArray
> with List<> until I've converted the exact GC infrastructure to use the new
> List<> class

Okey dokey.

(In reply to comment #46)
> change size() to length()

Main issue will be churn in Player code, but that's going to have to be done a bit at a time anyway (I have most of it in a sandbox, it will just have to trickle in), but IMHO is a win in the long term.
FYI, the corrected version of removeAt():


    template<class T, class ListHelper>
    T ListImpl<T,ListHelper>::removeAt(uint32_t index)
    {
        AvmAssert(index < m_data->len);
        T const old = ListHelper::load(m_data, index);
        if (index < m_data->len-1)
        {
            typename ListHelper::ALLOCATOR* const allocator = ListHelper::getAllocator(m_data);
            ListHelper::moveRange(allocator, m_data, index+1, index, m_data->len-index-1);
        }
        else
        {
            ListHelper::clearRange(m_data, index, 1);
        }
        m_data->len--;
        return old;
    }
Comment on attachment 476103 [details] [diff] [review]
Replace all usage of List<> in the VM with new List suite, v2

pushed as 5330:8f85f445cee7
Attachment #476103 - Attachment is obsolete: true
Comment on attachment 479183 [details] [diff] [review]
New suite of List<> replacement classes, v4

5330:8f85f445cee7
Attachment #479183 - Attachment is obsolete: true
Comment on attachment 480671 [details] [diff] [review]
change size() to length()

5330:8f85f445cee7
Attachment #480671 - Attachment is obsolete: true
Pushed the new List classes (with nits fixed), and removed the old List class.

Per Lars' request, AtomArray is still present and in use until Lars can get AtomList happy with exact marking.

The one remaining work item is to decide whether to switch all Lists to use GC memory, rather than having some use MMFX; if Lars feels we're better suited to use GC memory everywhere, I'm inclined to do so, but since Edwin expressed serious concerns, let's hear him and Lars duke it out... (in the meantime, I left that as-is)
I think his latest thinking (channelling Lars can be hazardous) is that using fixedmem is nice and all, but it can get in the way of GC policy since its per-process instead of per-gc.  The pattern of a GCFinalizedObject having some non-pointer-containing Lists, could be converted to use GC (nonpointer) memory - this makes the list mem visible to gc policy without increasing the mark workload or adding false retention.

I don't know if I'd blindly convert all List<> to use GC mem, because now you've got GC objects where you didn't before, introducing a new problem of tracking that list, etc.  If there are fixmem Lists that aren't tied to a GC object in any way, they probably need to be thought about.  Hopefully that's not the common case.
Attached patch Minor optimizations (obsolete) — Splinter Review
Some minor optimizations I noticed while working on updating other code to use DataList:

-- we don't need to pass an allocator to ensureCapcity() calls, since most of the calls won't need it, so pre-emptively loading the allocator is wasted effort. (This shows up in perf tests that call set() repeatedly.) Instead, have ensureCapacityImpl load it when necessary.

-- don't check for kListMaxLength in the inlined methods, do it in ensureCapacityImpl stead

-- use a little trickery in ensureCapacityExtra() to do the overflow checking without having to resort to 64-bit math.
Attachment #481399 - Flags: review?(lhansen)
Yet another minor tweak based on using these classes for more work...

This corrects a longstanding defect in the old List<>::set() method: using set() to set a specific entry would not grow the capacity as necessary (it would merely assert if you tried to set a too-high index). This was the one method that required to caller to explicitly manage capacity ahead of time, and as such, was weird and painful (not to mention error prone).

This patch corrects that, at essentially zero cost: we don't need to check to see if we need to grow unless we are setting beyond the current length, and we already were checking for that.

All code that worked previously should still work -- only code that asserted before would be affected, and AFAIK there isn't any. This is just a going-forward-make-it-less-stupid patch.
Attachment #481404 - Flags: review?(lhansen)
(In reply to comment #53)
> I think his latest thinking (channelling Lars can be hazardous) is that using
> fixedmem is nice and all, but it can get in the way of GC policy since its
> per-process instead of per-gc.  The pattern of a GCFinalizedObject having some
> non-pointer-containing Lists, could be converted to use GC (nonpointer) memory
> - this makes the list mem visible to gc policy without increasing the mark
> workload or adding false retention.
> 
> I don't know if I'd blindly convert all List<> to use GC mem, because now
> you've got GC objects where you didn't before, introducing a new problem of
> tracking that list, etc.  If there are fixmem Lists that aren't tied to a GC
> object in any way, they probably need to be thought about.  Hopefully that's
> not the common case.

I'm only concerned about the case where a GC object is holding onto fixed memory - in that particular case I'd like the GC to be aware of the memory pressure inflicted by the fixed memory.  It can be through using GC memory or through signaling the allocation/deallocation.  (The former is better going forward because we want to get rid of finalizable GC objects as much as possible, but the latter is OK at this time.)

I don't want to imply that we should be using GC memory everywhere for every list.

(On a general note, OOM accounting and handling does not require that we use GC memory, but timely GC requires it - if GC is not timely we can end up in a soft OOM situation, and then we punt and run som of the GCs synchronously, and that incurs pauses, and that's visible & ugly & reduces the edge an incremental GC gives us.  It may be that using GC memory more broadly would further reduce the chance of soft OOM situations but I think further research would be good before we start converting things.)
Comment on attachment 481399 [details] [diff] [review]
Minor optimizations

The ensureCapacity(a,b) optimization is way obscure and I'm skeptical that it really matters, but I'm game...  The comment should say "... will definitely fail in ensureCapacityImpl."
Attachment #481399 - Flags: review?(lhansen) → review+
Attachment #481404 - Flags: review?(lhansen) → review+
Attached patch Tidy up allocation (obsolete) — Splinter Review
This has three small interlocking changes to how allocation of list storage is performed.

The first is that clear() delegates to allocData, it does not muck around with allocating by itself.  Thus all allocation now goes through allocData, I think (I hope).

The second is that allocdata uses placement ::new so that the constructor of LISTDATA can be invoked, if there is one.  That doesn't matter for the code as you've written it but it matters for me, because an exactly traced container object will have a vtable at least.

The third is that since all allocation goes through allocData, and allocData calls Calloc, all allocation uses Calloc.  So I updated a comment to that effect.
Attachment #481519 - Flags: review?(stejohns)
Blocks: 588364
Comment on attachment 481399 [details] [diff] [review]
Minor optimizations

http://hg.mozilla.org/tamarin-redux/rev/cd95b7adb613
Attachment #481399 - Attachment is obsolete: true
Comment on attachment 481404 [details] [diff] [review]
List::set() should expand capacity as necessary

http://hg.mozilla.org/tamarin-redux/rev/cd95b7adb613
Attachment #481404 - Attachment is obsolete: true
Attachment #481519 - Flags: review?(stejohns) → review+
(In reply to comment #56)
> I'm only concerned about the case where a GC object is holding onto fixed
> memory - in that particular case I'd like the GC to be aware of the memory
> pressure inflicted by the fixed memory.  It can be through using GC memory or
> through signaling the allocation/deallocation.  (The former is better going
> forward because we want to get rid of finalizable GC objects as much as
> possible, but the latter is OK at this time.)

Well, the only thing I'm really concerned about here, going forward, is the external-facing API for List, to minimize future churn if we change the policy. Currently, DataList takes a FixedMalloc as a ctor argument, and others take a GC; perhaps we should unify on everything taking a GC, whether or not it is using GC memory for allocation. (Especially since it seems like that the doesn't-use-gc-memory variety will want access to a GC to notify it of allocation/deallocation, anyway). This is the remaining gating factor for landing this in Flash proper; I don't want to start changing their glue code if our API might mutate.

I'll post a sample patch for this change later for comment.
(Additive to patch 481519)

More sweeping than I thought it would be, but I like it: the idea is that all List variants take a GC* in their ctor, even if the underlying storage isn't GC memory. (DataList still uses FixedMalloc, but now it calls SignalDependant(De)Allocation as appropriate)

It does add a new GC* field to ListData, which probably isn't significant... we could possibly finesse things such that only DataList needs to store it (allowing other variants to call GetGC() but I'm not sure it's worth the effort. Opinions?

Running a quick perf comparison, seems to be a wash, no red flags there. 

Assuming the extra gc-pointer field isn't a stopping point, the regularization of the ctor api is IMHO a good reason to land this (it lets us defer decisions about allocation strategies without affecting integration plans).

(Note, if you R+ this and need to land it to continue your work, feel free to land it for me, as I'm out Friday-Sunday, back Monday)
Attachment #481694 - Flags: review?(lhansen)
Comment on attachment 481519 [details] [diff] [review]
Tidy up allocation

tamarin-redux changeset:   5343:9879fff9e705
Attachment #481519 - Attachment is obsolete: true
Comment on attachment 481694 [details] [diff] [review]
Use GC in all ctors

review ping...
Attachment #481694 - Flags: superreview?(edwsmith)
Blocks: 605324
Adding the GC field (attachment 481694 [details] [diff] [review]) uncovered a latent bug in allocData: it didn't calculate "extra" correctly if the field and base weren't even multiples. Need to round up when doing the division to handle this case. (Shows up on 32-bit systems if sizeof(T) == 8, for instance).
Attachment #484155 - Flags: review?(lhansen)
Blocks: 601817
No longer blocks: 588364
Comment on attachment 476104 [details] [diff] [review]
Replace AtomArray with AtomList, v2

Some benchmarking shows that Array.reverse() is slower with this patch; investigation shows that the old AtomArray::reverse() method simply shifted the values around without WB/WBRC usage, whereas the new AtomList::reverse() does WBATOM and such on store. Before I try to "optimize" this, though... was the old code correct? I thought that moving pointers around in this way could cause issues with partial marking? Was the old AtomArray code latently buggy?
I believe the old code was buggy but need to investigate deeply.
A little ham-handed, but gets the job done: basically an optimization in the same vein as movePointersWithinBlock.
Attachment #485171 - Flags: review?(lhansen)
Comment on attachment 485171 [details] [diff] [review]
Speed up reverse()

On reflection I'm confident that the old code is buggy and that we never saw this reported because reversing large arrays is rare, and doing so while the object is split on the mark stack is even rarer; additionally I belive object splitting was implemented after 10.0, so there's been little scope for the bug to be discovered.
Attachment #485171 - Flags: review?(lhansen) → review+
Comment on attachment 484155 [details] [diff] [review]
Fix rounding in allocData()

The comment is now starting to look ironic, seeing as it starts with "Simplify".
Attachment #484155 - Flags: review?(lhansen) → review+
Comment on attachment 481694 [details] [diff] [review]
Use GC in all ctors

I've run my eyes over this and not spotted any issues.

+1 on avoiding exposing implementation details by requiring the gc to be passed for DataList, I think this is the argument that sways me.

Also, GC::GetGC() is cheap now but I suspect it will become more expensive in the future if we start removing size-segregated allocation, and avoiding it is good.  So keep the data field.

Since we no longer pass an allocator I believe embedding hosts that do not use FixedMalloc uniformly (AIR?) no longer has the option of passing a custom / system allocator to a DataList, though.  Is that OK?

Longer term we should move the List templates into our base library probably.

(Memo to self: the use of 'IncrementalMarking' or 'marking' for what is really 'BarrierActive' is an accident waiting to happen, need to clean this up by exposing an appropriate API.)
Attachment #481694 - Flags: review?(lhansen) → review+
Comment on attachment 476104 [details] [diff] [review]
Replace AtomArray with AtomList, v2

You should push this; I will deal with the consequences, which I believe to be modest.
(In reply to comment #71)
> Since we no longer pass an allocator I believe embedding hosts that do not use
> FixedMalloc uniformly (AIR?) no longer has the option of passing a custom /
> system allocator to a DataList, though.  Is that OK?

I think it's OK.
pushed to TR as http://hg.mozilla.org/tamarin-redux/rev/8f85c4e15098
Status: ASSIGNED → RESOLVED
Closed: 14 years ago
Resolution: --- → FIXED
Attachment #481694 - Flags: superreview?(edwsmith) → superreview+
Flags: flashplayer-bug-
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: