506390 - Replace avmplus GC-based containers with standalone Allocator based ones

Status: VERIFIED FIXED

(Tamarin Graveyard :: Baseline JIT (CodegenLIR), defect)

Description

[Edwin Smith]

Replace use of avmplus::BitSet, SortedMap<>, and List<>, with standalone Allocator friendly containers.

Nanojit's uses of List don't depend on random access, so a linked list setup will work better with Allocator.  (allocate list nodes as needed)

similarly a bucket-based HashMap will be an adequate replacement where we currently use SortedMap (*).  In nanojit's uses of HashMap we can even predict a good bucket size and avoid the need for any reallocation as a HashMap is populated.

(*) LabeLap currently relies on the sorting in SortedMap; it needs a findNearest operation to find the closest key that is <= the requested key.  a very simple binary tree is good enough since LabelMap is only used in debugging code.

Along with changing the containers, the things we store in the containers can be simply allocated from Allocator&, instead of GC.

Comment 1

[Edwin Smith]

Attachment: Allocator-based BitSet, Seq, SeqBuilder, HashMap, and TreeMap containers

Comment 2

[Edwin Smith]

Attachment: Replace StringList with SeqBuilder<> list, use Allocator instead of GC

Comment 3

[Edwin Smith]

Attachment: Convert live() analyzer to Allocator

Use Allocator instead of GC in liveness analyzer nanojit::live().

Comment 4

[Edwin Smith]

Attachment: Convert LabelStateMap and RegAllocMap to Allocator based containers

Comment 5

[Brent Baker]

sending to qrb for target milestone

Comment 6

[Edwin Smith]

Attachment: convert InsList from List<> to SeqBuilder<>

Comment 7

[Edwin Smith]

Attachment: convert NInsList from avmplus:: to SeqBuilder<>

Comment 8

[Edwin Smith]

Attachment: convert LabelMap to use Allocator

LabelMap uses Allocator now internally, and also can be allocated by Allocator in host code.  ~LabelMap deleted since all it did is free stuff allocated by Allocator.

Comment 9

[Edwin Smith]

Attachment: convert LirNameMap to Allocator

Comment 10

[Edwin Smith]

Attachment: don't allocate CodeAlloc with GC and dont extend GCFinalizedObject

Also since we dont allocate CodeAlloc with GC we dont need DWB and it can be a field in PageMgr, which in turn enables PageMgr to be allocated with new/delete instead of GC.

Comment 11

[Edwin Smith]

Attachment: allocate LirBuffer with Allocator instead of GC, don't extend GCFinalizedObject

Comment 12

[Edwin Smith]

Attachment: convert Fragment to Allocator, delete Fragmento._frags and FragmentMap

In addition to not being GC allocated, Fragmento is essentially gutted by this patch and can be removed as dead code in a followup patch, with some stitching in nanojit::compile().

After an IRC conversation with graydon I'm offering this patch even though jsregexp still relies on Fragmento::getAnchor() (which uses _frags).  the RegExp -> Fragment map in tracemonkey will need to be implemented separately from Fragmento, similar to how regular trace fragments already are.

Comment 13

[Edwin Smith]

Attachment: convert Fragment to Allocator, delete Fragmento._frags and FragmentMap (2nd attempt)

Fixes initialization of Fragment and deletes unnecessary "delete frag".

Comment 14

[Edwin Smith]

Attachment: convert Assembler to Allocator

Requires several more fields to be initialized before use.

Comment 15

[Rick Reitmaier]

Note that bug #507255 deals with a corrected mem mgt issue that arose.  

Most likely that fix will cause issues with TM so whatever is designed here needs to support both use cases.

Comment 16

[Tom Harwood]

Comment on attachment 390578 [details] [diff] [review]
Allocator-based BitSet, Seq, SeqBuilder, HashMap, and TreeMap containers

BitSet::setFrom() is more or an "or" than "assign," maybe call it mergeFrom()? 

class BitSet: 
- checking in a fixme.  Meh.  OTOH I don't see any way 'round it.

- The magic number 6 gets used a lot (2^6, really).  A manifest constant with a comment would be nice.
- Similarly, the expression ONE << (i & 63) could be a macro. 

class Seq
- Traditional name for hd is car, t1 is cdr, no?

- HashMap::hash(k) it'd be nice if there were a base class where this is a functor.

class Iter:
- could be a subclass of HashMap with a factory in HashMap.

class TreeMap:
- "the only user of this structure" -- for now :) 
insert() and put() could return a pair<bool,K> if anybody's interested in replacements.

Comment 17

[Steven Johnson]

(In reply to comment #16)
> (From update of attachment 390578 [details] [diff] [review])
> class Seq
> - Traditional name for hd is car, t1 is cdr, no?

Maybe in the sense that "tradition is the practice of making the same mistake twice, on purpose". In other words: no, no, no.

Comment 19

[Tom Harwood]

Comment on attachment 390809 [details] [diff] [review]
Convert live() analyzer to Allocator

LiveTable::retire() shows a use for SeqBuilder::size() to centralize the bookkeeping.

Comment 20

[Tom Harwood]

Comment on attachment 390818 [details] [diff] [review]
Convert LabelStateMap and RegAllocMap to Allocator based containers

SideExit?  Comments for the newbs would be helpful.

Comment 21

[Nicholas Nethercote [inactive]]

(In reply to comment #17)
>
> > - Traditional name for hd is car, t1 is cdr, no?
> 
> Maybe in the sense that "tradition is the practice of making the same mistake
> twice, on purpose". In other words: no, no, no.

Hear hear.  "car" and "cdr" were derived from register names on the IBM 704 (http://en.wikipedia.org/wiki/CAR_and_CDR) and so are meaningless today.  Please use "head" and "tail" or some similar variant!

Comment 22

[Jeff Walden [:Waldo]]

I agree and would further note that saving two characters hardly seems to offset the mental overhead of mentally converting "hd" to "head" and "tl" to "tail" every time this code is read.  I'd much rather see "head" and "tail".

Comment 23

[Tom Harwood]

Since I initially commented on "car" and "cdr" after trying to puzzle out what "tee-one" meant, I agree with the recommendation that we go with "head" and "tail."

Comment 24

[Tom Harwood]

re: class Iter: s/subclass/inner class/ but it already is.  some_map.iter() would still win over Iter(some_map) but it'd either need operator = or iter() would have to return a pointer, which would not be so much of a win.

Comment 25

[Tom Harwood]

Comment on attachment 391160 [details] [diff] [review]
don't allocate CodeAlloc with GC and dont extend GCFinalizedObject

Assembler::Assembler() could be declared to take a reference to the allocator, which seems more in keeping with this new usage.

PoolObject.cpp and PoolObject.h don't agree on the preprocessor definition that triggers codePages processing -- PoolObject.cpp uses VMCFG_NANOJIT, recommend 
PoolObject.h use it as well.

Comment 26

[Tom Harwood]

Comment on attachment 391175 [details] [diff] [review]
allocate LirBuffer with Allocator instead of GC, don't extend GCFinalizedObject

A virtual destructor bites the dust, the crowd goes wild.

Comment 27

[Tom Harwood]

Comment on attachment 391250 [details] [diff] [review]
 convert Fragment to Allocator, delete Fragmento._frags and FragmentMap (2nd attempt)

It'd take a bit of work, but it would be good to have a memory hook that'd freak out on any attempt to delete an object allocated inside an Allocator.

Looks like a couple more Fragmento methods are dead code:
- getMerge
- createBranch

Comment 28

[Edwin Smith]

(In reply to comment #23)
> Since I initially commented on "car" and "cdr" after trying to puzzle out what
> "tee-one" meant, I agree with the recommendation that we go with "head" and
> "tail."

Cool, I will:

  s/hd/head
  s/tl/tail

Comment 29

[Edwin Smith]

(In reply to comment #27)
> (From update of attachment 391250 [details] [diff] [review])
> It'd take a bit of work, but it would be good to have a memory hook that'd
> freak out on any attempt to delete an object allocated inside an Allocator.

I think valgrind or purify would catch problems like this.  but i'm not sure how to build a hook without also overriding global operator delete, which we want to avoid.  suggestions?

> Looks like a couple more Fragmento methods are dead code:
> - getMerge
> - createBranch

will remove.

Comment 30

[Edwin Smith]

Comment on attachment 390578 [details] [diff] [review]
Allocator-based BitSet, Seq, SeqBuilder, HashMap, and TreeMap containers

pushed http://hg.mozilla.org/tamarin-redux/rev/0b1c604182cb

Comment 31

[Edwin Smith]

(In reply to comment #25)
> (From update of attachment 391160 [details] [diff] [review])
> Assembler::Assembler() could be declared to take a reference to the allocator,
> which seems more in keeping with this new usage.

It does take an Allocator&, did you mean it should also take CodeAlloc& instead
of CodeAlloc*?  easy change, no problem.

> PoolObject.cpp and PoolObject.h don't agree on the preprocessor definition that
> triggers codePages processing -- PoolObject.cpp uses VMCFG_NANOJIT, recommend 
> PoolObject.h use it as well.

will fix.

Comment 32

[Tom Harwood]

> It does take an Allocator&, did you mean it should also take CodeAlloc&
> instead of CodeAlloc*? 

My mistake.  Passing a reference to a GC object looks funky.

Comment 33

[Edwin Smith]

Comment on attachment 390732 [details] [diff] [review]
Replace StringList with SeqBuilder<> list, use Allocator instead of GC

pushed http://hg.mozilla.org/tamarin-redux/rev/7241f5588d9a

Comment 34

[Edwin Smith]

Comment on attachment 390809 [details] [diff] [review]
Convert live() analyzer to Allocator

pushed http://hg.mozilla.org/tamarin-redux/rev/e322674e1c89

Comment 35

[Tom Harwood]

(In reply to comment #29)
> (In reply to comment #27)
> > .. memory hook ... freak out ... delete ... inside an Allocator.
> how to build a hook without also overriding global operator delete

There are platform-specific APIs, but valgrind/Purify is a better solution.

Comment 36

[Edwin Smith]

Attachment: convert NInsMap to HashMap

This patch comes after "Convert LabelStateMap..." and before "convert InsList..."

Comment 37

[Edwin Smith]

Comment on attachment 390818 [details] [diff] [review]
Convert LabelStateMap and RegAllocMap to Allocator based containers

pushed http://hg.mozilla.org/tamarin-redux/rev/7487d79f1728

Comment 38

[Edwin Smith]

Comment on attachment 392496 [details] [diff] [review]
convert NInsMap to HashMap

http://hg.mozilla.org/tamarin-redux/rev/c5361ae4b6c8

Comment 39

[Edwin Smith]

Comment on attachment 390853 [details] [diff] [review]
convert InsList from List<> to SeqBuilder<>

pushed http://hg.mozilla.org/tamarin-redux/rev/bb1b697d2cc6

Comment 40

[Edwin Smith]

Comment on attachment 390856 [details] [diff] [review]
convert NInsList from avmplus:: to SeqBuilder<>

pushed http://hg.mozilla.org/tamarin-redux/rev/9b8bb85eabd3

Comment 41

[Edwin Smith]

Comment on attachment 390871 [details] [diff] [review]
convert LabelMap to use Allocator

pushed http://hg.mozilla.org/tamarin-redux/rev/2bbdf5865e85

Comment 42

[Edwin Smith]

Comment on attachment 391159 [details] [diff] [review]
convert LirNameMap to Allocator

pushed http://hg.mozilla.org/tamarin-redux/rev/4b4d672b5d5f

Comment 43

[Edwin Smith]

(In reply to comment #32)
> > It does take an Allocator&, did you mean it should also take CodeAlloc&
> > instead of CodeAlloc*? 
> 
> My mistake.  Passing a reference to a GC object looks funky.

... until CodeAlloc is no longer a GC object, which is what codealloc.patch accomplishes.  I'll update it to use CodeAlloc& as part of that patch.

Comment 44

[Edwin Smith]

Comment on attachment 391160 [details] [diff] [review]
don't allocate CodeAlloc with GC and dont extend GCFinalizedObject

pushed http://hg.mozilla.org/tamarin-redux/rev/fa1a9e4128f3

Comment 45

[Edwin Smith]

Comment on attachment 391175 [details] [diff] [review]
allocate LirBuffer with Allocator instead of GC, don't extend GCFinalizedObject

pushed http://hg.mozilla.org/tamarin-redux/rev/17962215073d

Comment 46

[Edwin Smith]

Comment on attachment 391250 [details] [diff] [review]
 convert Fragment to Allocator, delete Fragmento._frags and FragmentMap (2nd attempt)

pushed http://hg.mozilla.org/tamarin-redux/rev/09b2071700bb

Comment 47

[Edwin Smith]

Comment on attachment 391340 [details] [diff] [review]
convert Assembler to Allocator

pushed http://hg.mozilla.org/tamarin-redux/rev/ddc29e943a73

Comment 48

[Edwin Smith]

Attachment: Convert LInsHashSet to use Allocator instead of GC

This does what it says, which is pretty simple.

However since Allocator (intentionally) doesn't support free(), each time the CSE array doubles in size, we'll waste a bit of memory.

Some cursory measurement shows that this rarely happens (most methods are small) and the resulting waste approaches the same amount as the final size of the array. (meaning, we max out at 50% overhead)

so the typical waste (for a small % of methods) is on the order of 1K to 8K of transient memory (freed at the end of LIR generation).

For tamarin this seems okay.  soliciting opinions for tracemonkey.  I beleive (hope?) sooner than later we might be making bigger changes to the CSE code which could make this even more of a non-issue.

another possible risk mitigator would be to add a free() method to allocator, and let it consume free blocks, if they're big enough, along the slow path in Allocator.fill().  simple enough for starters, but it starts us down the path of making Allocator be a "real" allocator, and I'm reluctant to go that route.

Comment 49

[Nicholas Nethercote [inactive]]

(In reply to comment #48)
>
> For tamarin this seems okay.  soliciting opinions for tracemonkey.  I beleive
> (hope?) sooner than later we might be making bigger changes to the CSE code
> which could make this even more of a non-issue.

Bug 502778 (not yet committed) splits the LInsHashSet for CseFilter into seven LInsHashSets, and quadruples the starting size of each one from 64 to 256.  So it's only resizing that causes the waste, then this will be an improvement because fewer resizes will happen.

Comment 50

[Edwin Smith]

Attachment: convert avmplus::CopyPropagation to use Allocator instead of GC

CopyPropagation uses an array the size of the stack frame to track variables, allocate it with Allocator instead of GC.

Comment 51

[Edwin Smith]

Attachment: Convert DebuggerCheck's local storage from GC to Allocator

Comment 52

[Edwin Smith]

Attachment: LirWriter no longer needs to be a GCObject, add field initializers

This is the final patch for this bug.  With it, nanojit no longer uses MMgc::GC, or even anything from MMgc.  In tamarin, LirWriters are now allocated with Allocator (one with a shorter lifetime than the one used in Assembler).

Comment 53

[Edwin Smith]

(In reply to comment #49)
> (In reply to comment #48)
> >
> > For tamarin this seems okay.  soliciting opinions for tracemonkey.  I beleive
> > (hope?) sooner than later we might be making bigger changes to the CSE code
> > which could make this even more of a non-issue.
> 
> Bug 502778 (not yet committed) splits the LInsHashSet for CseFilter into seven
> LInsHashSets, and quadruples the starting size of each one from 64 to 256.  So
> it's only resizing that causes the waste, then this will be an improvement
> because fewer resizes will happen.

Cool.  yes, its only resizing that causes the waste.

Comment 54

[Tom Harwood]

Comment on attachment 392833 [details] [diff] [review]
Convert LInsHashSet to use Allocator instead of GC

So a CfgCseFilter specialized a CseFilter by clearing all available exprs at a backwards branch.  It's a little late to entirely grok the effects of removing this, but I agree that it is goodness.
One thing about CSE in general: beware "eliminating" when the cost of keeping the common expression is greater than the cost of recomputing it.

Comment 55

[Edwin Smith]

(In reply to comment #54)
> (From update of attachment 392833 [details] [diff] [review])
> So a CfgCseFilter specialized a CseFilter by clearing all available exprs at a
> backwards branch.  It's a little late to entirely grok the effects of removing
> this, but I agree that it is goodness.

There are no effects from removing it, because CfgCseFilter::ins0() was an exact duplicate of CseFilter::ins0().  The subclass did not change any functionality so I removed it.  At a time in the past, CseFilter::ins0() didn't do any clear operation, which is why we had CfgCseFilter... but it evolved.

> One thing about CSE in general: beware "eliminating" when the cost of keeping
> the common expression is greater than the cost of recomputing it.

I understand.  A competing concern is that eliminating trivially cheap expressions also enables more complex expressions to be found and eliminated.  Doing a good job at keeping some simple CSE's and not others probably should be in a late phase and make use of some kind of cost model?  maybe even incorporated into the asm generation pass when we know register pressure.

also, be aware that instruction selection sometimes duplicates trivial expressions instead of spilling them, or instead of computing them into a register.  example:  some constants are folded into an instruction using an immediate form.  expressions involving address computations on LIR_alloc (ie FP+const) are also rematerialized instead of being spilled.  (etc... these decisions are unique to each CPU backend)

Comment 56

[Edwin Smith]

Comment on attachment 392833 [details] [diff] [review]
Convert LInsHashSet to use Allocator instead of GC

pushed http://hg.mozilla.org/tamarin-redux/rev/5d8aead674ff

Comment 57

[Edwin Smith]

Comment on attachment 392837 [details] [diff] [review]
convert avmplus::CopyPropagation to use Allocator instead of GC

pushed http://hg.mozilla.org/tamarin-redux/rev/fabc7f674979

Comment 58

[Edwin Smith]

Comment on attachment 392838 [details] [diff] [review]
Convert DebuggerCheck's local storage from GC to Allocator

pushed http://hg.mozilla.org/tamarin-redux/rev/97c40fb2ba6e

Comment 59

[Edwin Smith]

pushed final patch
http://hg.mozilla.org/tamarin-redux/rev/ff3507cf17c8

Comment 60

[Chris Peyer]

Resolved fixed engineering / work item that has been pushed.  Setting status to verified.

Comment 61

[Brent Baker]

removing QRB request, bug resolved/verified