596927 - GC::ContainsPointers should be as fast as possible

Status: RESOLVED FIXED

(Tamarin Graveyard :: Garbage Collection (mmGC), defect, P3)

Description

[Lars T Hansen]

Currently GC::ContainsPointers involves determining whether the object is large or small, then calling different functions for large and small objects.  All of that code is in-lined and it's probably less than a dozen instructions on x86, but in the common case it will be several loads and a couple of branches.

However, ContainsPointers will probably be a hot spot for quasi-exact tracing of generic data structures like List<>, where we know something is a GCObject* but we don't know whether it's traced or not - TraceObjectWithOrWithoutPointers leans heavily on ContainsPointers.  It would be good to see if we could make ContainsPointers faster, eg, by lifting the single bit we need into the GCBlockHeader structure, at which point the test for large or small object won't be necessary and the test will become a mask, a load, and maybe another mask.

Comment 1

[Lars T Hansen]

Using a trick, the information can be placed in the allocator that's linked from the block header.  Then the cost would be: compute the block header pointer (a mask), load the allocator pointer, load a boolean field through that pointer.  The boolean field would reside in GCAllocBase.

The trick is necessary because a single large-object allocator can allocate both pointer-containing and non-pointer containing objects, thus the field is not constant for the allocator.  The trick is to factor the (meagre) data held by the large-object allocator into some other structure, and to allocate two small allocator structures that share that data, one with the containsPointers field set to true and the other one with it set to false.  When a pointer-containing structure is allocated, one allocator pointer is installed; when a non-pointer-containing structure is allocated, the other allocator pointer is installed.

The trick depends on not comparing allocators by pointer value.  I don't think we do that, nor can I think of a reason why we would.

Comment 2

[Lars T Hansen]

Attachment: Proof of concept

There will be some knock-on effects from this, eg cleaning up direct calls to GCAlloc::ContainsPointers and GCLargeAlloc::ContainsPointers, and if we like the trick we could in principle use it for IsRCObject as well, at a small cost of two more GCLargeAlloc instances.  IsRCObject is hot in stack pinning so there may be some modest gains if we end up simplifying it.

Comment 3

[Tommy Reilly]

Could we put this information in the header by making size or bitsShift a uint16_t and use the other 16 bits as a bit field?   That bit field could also be used for a unified rcobject check

Comment 4

[Lars T Hansen]

You mean in the block header?  I thought about that, but currently we need 'size' the way it is (we could say that it would always be a multiple of 8 and that would give us three bits to play with, at the cost of masking off those flags whenever we access it).  Ditto for 'bitsShift': we could use some of that space but at the cost of masking and possibly shifting when we access it.

Comment 5

[Tommy Reilly]

bitsShift is never larger than 12 so we could use a uint8_t for it.   Is using a part of word more expensive than using a whole word or something?    I would guess accessing a word aligned byte and a word aligned word would have the same cost.

Comment 6

[Tommy Reilly]

Attachment: move rcobject and contains pointers checks to block header

thought I'd help move this along while we await updated exact marking patches, this seems like a cleaner approach to me and I went ahead and extended it to rcobject too.  patch is relative to another patch removing the FASTBITS ifdef

Comment 7

[Lars T Hansen]

Comment on attachment 479887 [details] [diff] [review]
move rcobject and contains pointers checks to block header

I like the change, but I think you changed the contract for GC::IsRCObject, and that there are clients that depend on the old contract (at least in my code the calls to IsRCObject in RCObject::IncrementRef require the old definition).  How about a slight extension where we provide IsRCObjectSafe() that checks IsPointerToGCPage and IsPointerToGCObject and which could be used in assertions?

Comment 8

[Tommy Reilly]

yeah I fudged some of that just to post something for feedback quickly, I'll clean up and post another for review with an IsRCObjectSafe DEBUG function.

Comment 9

[Tommy Reilly]

Attachment: Now not based on removing MMGC_FASTBITS and introduced IsRCObjectSafe for assertions

Comment 10

[Lars T Hansen]

Comment on attachment 480663 [details] [diff] [review]
Now not based on removing MMGC_FASTBITS and introduced IsRCObjectSafe for assertions

R- for the minor bugs, but otherwise looks good.

Bugs:

The parameter name 'anyptr' that you use in GC.h for IsRCPointerSafe has transmuted to 'anyuserptr' in GC.cpp.  This must be fixed, probably by simply using 'ptr' both places and documenting that (a) the pointer may point anywhere and (b) if IsRCPointerSafe is to return true it must be a userptr.

If the documentation is truthful about GCAlloc::IsRCObject (and it appears to be) then the function is badly misnamed, try PointsIntoRCObjectStorage or something like that, which is what it checks.

What is the API to GC::IsRCObject (and GC::ContainsPointers, for that matter)?  Right now both require only that the pointer point somewhere in a GC block.  That seems too lenient, I'd like something tighter: the argument should be required to be a userptr, and in DEBUG builds we should check that.

That means that the use of GC::IsRCObject for large objects in ZCT.cpp must change, probably GCLargeAlloc will acquire a PointsIntoRCObjectStorage function like GCAlloc has.


Nits:

Is it necessary for IsRCObjectSafe to be DEBUG-only?  I know we're only using it for assertions, but it seems like a small cost to pay to have it generally available.

The documentation for IsRCObjectSafe should make it clear that it never throws an error and always returns false if the pointer is not actually to an RCObject.  Also see bug issue above about the parameter name.

Documentation for GCAlloc::IsRCObject: it's "it's", not "its".  Also the comment here about the ZCT should go away - the function does what it does; who uses it is probably not relevant.  (See bug note above about the name of this function being wrong.)

Comment 11

[Tommy Reilly]

Attachment: Clean up Lar's concerns and some

Took the opportunity to clean up the duplication between FindBeginningGuarded and what the ZCT scan was doing.   FindBeginningGuarded was broken because it didn't reject header pointers.   Also put IsPointerToGCObject to use to greatly simplify IsRCObjectSafe.

Comment 12

[Tommy Reilly]

Attachment: Clean up Lar's concerns and some

Comment 13

[Tommy Reilly]

pulling review until I complete my testing...

Comment 14

[Tommy Reilly]

Attachment: Addressed Lars' comments and more

- Made IsPointerToGCObject take a userptr, its a public GC API and taking a userptr is the convention for those
- Made ZCT scanning use FindBeginningGuarded instead of duplicating same code
- Fixed FindBeginningGuarded to bong pointers to GC block headers
- Made IsRCObjectSafe not DEBUG only and simplified it by using IsPointerToGCObject and IsRCObject.

Comment 15

[Tommy Reilly]

Attachment: Choice B, like 481614 but doesn't change IsPointerToGCObject, inserts before exact marking more seamlessly

Comment 16

[Lars T Hansen]

Comment on attachment 482246 [details] [diff] [review]
Choice B, like 481614 but doesn't change IsPointerToGCObject, inserts before exact marking more seamlessly

Nits you might consider fixing while landing:

GCLargeAlloc::GetItem could do with a line of documentation, even if it is private - "item" is so generic.

The GCAssertMsg on line 103 of GCLargeAlloc-inlines.h could/should use GetItem rather than block+1.

The word "this" in the new comment block for FindBeginningGuarded (line 828) is ambiguous, I don't understand what it references.  Suggest cleaning that up.  (+1 on the expanded comment, though).

The comment for IsRCObject in GC.h references 'item' but there's no 'item' in the parameter list (the parameter is unnamed).

Spurious blank line inserted before GC::Mark.

Technically a bunch of "lb+1" instances in the GC code could be replaced by calls to GCLargeAlloc::GetItem; I had such a change in the pipeline a few times over the last year or so but never thought it worthwhile to land it.  I'm not sure it's worth the bother now either.

Comment 17

[Lars T Hansen]

Comment on attachment 481614 [details] [diff] [review]
Addressed Lars' comments and more

Taking myself off review, I assume this is obsolete now?

Comment 18

[Tommy Reilly]

updated to reflect comments, GetItem became GetObject and moved to LargeBlock, hey its C++ right!

http://hg.mozilla.org/tamarin-redux/rev/45a1857ac6c9

Comment 19

[Felix S. Klock II [:pnkfelix, :fklock]]

The full log for changeset from Comment 18 (just improving internal record):

  changeset:   5363:45a1857ac6c9
  user:        Tommy Reilly <[e-mail]>
  date:        Fri Oct 15 11:25:06 2010 -0700
  summary:     Optimize contains pointers test in antipation of exact marking pounding on it, rcobject test sped up as well as side affect (r=lhansen,bug=603504)

  http://hg.mozilla.org/tamarin-redux/rev/45a1857ac6c9