Replace avmplus GC-based containers with standalone Allocator based ones

VERIFIED FIXED

Status

Tamarin
Baseline JIT (CodegenLIR)
VERIFIED FIXED
9 years ago
8 years ago

People

(Reporter: Edwin Smith, Assigned: Edwin Smith)

Tracking

unspecified
x86
Mac OS X
Bug Flags:
flashplayer-triage +

Details

Attachments

(2 attachments, 16 obsolete attachments)

4.48 KB, patch
graydon
: review+
Tom Harwood
: review+
Details | Diff | Splinter Review
5.39 KB, patch
Tom Harwood
: review+
graydon
: review+
Details | Diff | Splinter Review
(Assignee)

Description

9 years ago
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.
(Assignee)

Comment 1

9 years ago
Created attachment 390578 [details] [diff] [review]
Allocator-based BitSet, Seq, SeqBuilder, HashMap, and TreeMap containers
Assignee: nobody → edwsmith
(Assignee)

Comment 2

9 years ago
Created attachment 390732 [details] [diff] [review]
Replace StringList with SeqBuilder<> list, use Allocator instead of GC
(Assignee)

Comment 3

9 years ago
Created attachment 390809 [details] [diff] [review]
Convert live() analyzer to Allocator

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

Comment 4

9 years ago
Created attachment 390818 [details] [diff] [review]
Convert LabelStateMap and RegAllocMap to Allocator based containers

Comment 5

9 years ago
sending to qrb for target milestone
Flags: flashplayer-triage+
Flags: flashplayer-qrb?
(Assignee)

Comment 6

9 years ago
Created attachment 390853 [details] [diff] [review]
convert InsList from List<> to SeqBuilder<>
(Assignee)

Comment 7

9 years ago
Created attachment 390856 [details] [diff] [review]
convert NInsList from avmplus:: to SeqBuilder<>
(Assignee)

Comment 8

9 years ago
Created attachment 390871 [details] [diff] [review]
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.
(Assignee)

Comment 9

9 years ago
Created attachment 391159 [details] [diff] [review]
convert LirNameMap to Allocator
(Assignee)

Comment 10

9 years ago
Created attachment 391160 [details] [diff] [review]
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.
(Assignee)

Comment 11

9 years ago
Created attachment 391175 [details] [diff] [review]
allocate LirBuffer with Allocator instead of GC, don't extend GCFinalizedObject
(Assignee)

Comment 12

9 years ago
Created attachment 391239 [details] [diff] [review]
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.
(Assignee)

Comment 13

9 years ago
Created attachment 391250 [details] [diff] [review]
 convert Fragment to Allocator, delete Fragmento._frags and FragmentMap (2nd attempt)

Fixes initialization of Fragment and deletes unnecessary "delete frag".
Attachment #391239 - Attachment is obsolete: true
(Assignee)

Comment 14

9 years ago
Created attachment 391340 [details] [diff] [review]
convert Assembler to Allocator

Requires several more fields to be initialized before use.
(Assignee)

Updated

9 years ago
Attachment #391250 - Attachment is patch: true
Attachment #391250 - Attachment mime type: application/octet-stream → text/plain

Comment 15

9 years ago
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.
(Assignee)

Updated

9 years ago
Attachment #390578 - Flags: review?(nnethercote)
Attachment #390578 - Flags: review?(graydon)
(Assignee)

Updated

9 years ago
Attachment #390578 - Flags: review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #390732 - Flags: review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #390809 - Flags: review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #390818 - Flags: review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #390853 - Flags: review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #390856 - Flags: review?
(Assignee)

Updated

9 years ago
Attachment #390856 - Flags: review? → review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #390871 - Flags: review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #391159 - Flags: review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #391160 - Flags: review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #391175 - Flags: review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #391250 - Flags: review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #391340 - Flags: review?(tharwood)

Comment 16

9 years ago
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.
Attachment #390578 - Flags: review?(tharwood) → review+

Comment 17

9 years ago
(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 18

9 years ago
Comment on attachment 390732 [details] [diff] [review]
Replace StringList with SeqBuilder<> list, use Allocator instead of GC
Attachment #390732 - Flags: review?(tharwood) → review+

Comment 19

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

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

Updated

9 years ago
Attachment #390809 - Flags: review?(tharwood) → review+

Comment 20

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

SideExit?  Comments for the newbs would be helpful.
Attachment #390818 - Flags: review?(tharwood) → review+

Updated

9 years ago
Attachment #390853 - Flags: review?(tharwood) → review+
(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!
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

9 years ago
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

9 years ago
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.

Updated

9 years ago
Attachment #390856 - Flags: review?(tharwood) → review+

Updated

9 years ago
Attachment #390871 - Flags: review?(tharwood) → review+

Updated

9 years ago
Attachment #391159 - Flags: review?(tharwood) → review+

Updated

9 years ago
Attachment #391160 - Flags: review?(tharwood) → review+

Comment 25

9 years ago
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

9 years ago
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.
Attachment #391175 - Flags: review?(tharwood) → review+

Comment 27

9 years ago
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
Attachment #391250 - Flags: review?(tharwood) → review+

Updated

9 years ago
Attachment #391340 - Flags: review?(tharwood) → review+
(Assignee)

Comment 28

9 years ago
(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
(Assignee)

Comment 29

9 years ago
(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.
(Assignee)

Comment 30

9 years ago
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
(Assignee)

Comment 31

9 years ago
(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

9 years ago
> 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.
(Assignee)

Updated

9 years ago
Attachment #390578 - Attachment is obsolete: true
Attachment #390578 - Flags: review?(nnethercote)
Attachment #390578 - Flags: review?(graydon)
(Assignee)

Comment 33

9 years ago
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
Attachment #390732 - Attachment is obsolete: true
(Assignee)

Comment 34

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

pushed http://hg.mozilla.org/tamarin-redux/rev/e322674e1c89
Attachment #390809 - Attachment is obsolete: true

Comment 35

9 years ago
(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.
(Assignee)

Comment 36

9 years ago
Created attachment 392496 [details] [diff] [review]
convert NInsMap to HashMap

This patch comes after "Convert LabelStateMap..." and before "convert InsList..."
Attachment #392496 - Flags: review?(tharwood)

Updated

9 years ago
Attachment #392496 - Flags: review?(tharwood) → review+
(Assignee)

Comment 37

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

pushed http://hg.mozilla.org/tamarin-redux/rev/7487d79f1728
Attachment #390818 - Attachment is obsolete: true
(Assignee)

Comment 38

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

http://hg.mozilla.org/tamarin-redux/rev/c5361ae4b6c8
Attachment #392496 - Attachment is obsolete: true
(Assignee)

Comment 39

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

pushed http://hg.mozilla.org/tamarin-redux/rev/bb1b697d2cc6
Attachment #390853 - Attachment is obsolete: true
(Assignee)

Comment 40

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

pushed http://hg.mozilla.org/tamarin-redux/rev/9b8bb85eabd3
Attachment #390856 - Attachment is obsolete: true
(Assignee)

Comment 41

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

pushed http://hg.mozilla.org/tamarin-redux/rev/2bbdf5865e85
Attachment #390871 - Attachment is obsolete: true
(Assignee)

Comment 42

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

pushed http://hg.mozilla.org/tamarin-redux/rev/4b4d672b5d5f
Attachment #391159 - Attachment is obsolete: true
(Assignee)

Comment 43

9 years ago
(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.
(Assignee)

Comment 44

9 years ago
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
Attachment #391160 - Attachment is obsolete: true
(Assignee)

Updated

9 years ago
Attachment #391175 - Attachment is obsolete: true
(Assignee)

Comment 45

9 years ago
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
(Assignee)

Comment 46

9 years ago
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
Attachment #391250 - Attachment is obsolete: true
(Assignee)

Comment 47

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

pushed http://hg.mozilla.org/tamarin-redux/rev/ddc29e943a73
Attachment #391340 - Attachment is obsolete: true
(Assignee)

Comment 48

9 years ago
Created attachment 392833 [details] [diff] [review]
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.
Attachment #392833 - Flags: review?(graydon)
(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.
(Assignee)

Updated

9 years ago
Attachment #392833 - Flags: review?(tharwood)
(Assignee)

Comment 50

9 years ago
Created attachment 392837 [details] [diff] [review]
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.
Attachment #392837 - Flags: review?(tharwood)
(Assignee)

Comment 51

9 years ago
Created attachment 392838 [details] [diff] [review]
Convert DebuggerCheck's local storage from GC to Allocator
Attachment #392838 - Flags: review?(tharwood)
(Assignee)

Comment 52

9 years ago
Created attachment 392840 [details] [diff] [review]
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).
Attachment #392840 - Flags: review?(tharwood)
(Assignee)

Updated

9 years ago
Attachment #392840 - Flags: review?(graydon)
(Assignee)

Comment 53

9 years ago
(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

9 years ago
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.
Attachment #392833 - Flags: review?(tharwood) → review+

Updated

9 years ago
Attachment #392837 - Flags: review?(tharwood) → review+

Updated

9 years ago
Attachment #392838 - Flags: review?(tharwood) → review+

Updated

9 years ago
Attachment #392840 - Flags: review?(tharwood) → review+
(Assignee)

Comment 55

9 years ago
(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)
(Assignee)

Comment 56

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

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

Comment 57

9 years ago
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
Attachment #392837 - Attachment is obsolete: true
(Assignee)

Updated

9 years ago
Attachment #392838 - Attachment is obsolete: true
(Assignee)

Comment 58

9 years ago
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
(Assignee)

Comment 59

9 years ago
pushed final patch
http://hg.mozilla.org/tamarin-redux/rev/ff3507cf17c8
Status: NEW → RESOLVED
Last Resolved: 9 years ago
Resolution: --- → FIXED

Updated

9 years ago
Attachment #392833 - Flags: review?(graydon) → review+

Updated

9 years ago
Attachment #392840 - Flags: review?(graydon) → review+

Comment 60

8 years ago
Resolved fixed engineering / work item that has been pushed.  Setting status to verified.
Status: RESOLVED → VERIFIED

Comment 61

8 years ago
removing QRB request, bug resolved/verified
Flags: flashplayer-qrb?
You need to log in before you can comment on or make changes to this bug.