Closed Bug 658672 Opened 13 years ago Closed 13 years ago

reduce BlockSize for NodePool and EdgePool in cycle collector

Categories

(Core :: XPCOM, defect)

Other Branch
defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla8

People

(Reporter: mccr8, Assigned: mccr8)

References

Details

(Whiteboard: [MemShrink:P2])

Attachments

(3 files, 2 obsolete files)

In the cycle collector, edges and nodes are each allocated in giant blocks.  Currently, the node blocks contain 32768 nodes and the edge blocks contain 65536.  At some point this may have made sense, but currently this seems way too large, and we're probably wasting a lot of space on internal fragmentation.  I suspect that pruning out marked JS objects has drastically reduced the number of objects in the CC graph.

With a few tabs open, there are around 14k-44k nodes and 25k-135k edges.  Even with the Membuster benchmark, I am only seeing around 129k-300k nodes and 360k-580 edges.  Nodes are about 5 pointers large, and edges are a single pointer.  If the number of nodes is randomly distributed, we're getting 16k nodes worth of internal fragmentation on average, which is more than the number of nodes we allocate in some cases.  That's about half a meg on a 64 bit system.

Drawbacks of smaller blocks:
- worsened locality: scanning across nodes and edges may jump around more
- more calls to malloc and free (but maybe faster due to smaller blocks?)
- increased space: a couple of pointers per block (not too much)

I'm not sure what a good block size would be.  Half the current size?  A quarter?  Even smaller?  I suppose there are diminishing returns on shrinking the block size.  Seems worth investigating, at least.
(In reply to comment #0)
> 
> I'm not sure what a good block size would be.  Half the current size?  A
> quarter?  Even smaller?  I suppose there are diminishing returns on
> shrinking the block size.  Seems worth investigating, at least.

My suggestion: come up with a half-plausible metric, and then try a range of sizes.
Whiteboard: [MemShrink:P2]
Assignee: nobody → continuation
This is a log of memory usage for edges and nodes in the cycle collector.  The other major usage is the purple buffer, but that only allocates blocks of size 128, so fragmentation probably isn't too bad there.

In this run, fragmentation (edge frag + node frag) is around 800k-1.4m in a cycle collection.

Fragmentation is usually, but not always, worse for nodes than edges.

The number of blocks allocated for edges might be an interesting stat to look at with telemetry (# of node blocks can be inferred from # of nodes).
My previous patch calculated used memory incorrectly (for the final block, it was counting unused memory, not used memory!).
Attachment #538718 - Attachment is obsolete: true
I think dividing the block sizes by 4 might be a reasonable compromise between block size and fragmentation.  We'll only get about 38 blocks for membuster-sized graphs, which doesn't seem too bad, and they are still pretty huge, so cache effects hopefully won't be too bad.

In terms of fragmentation, we can consider the worst case to basically be the size of a block (if we just barely kick over into a new block).

nodes:  32 bytes each
(current) 32768 per block * 32 = 1024k of fragmentation in worst case
(div 4)    8192 per block * 32 =  256k in worst case

edges:  8 bytes each
(current) 65536 per block * 8 = 524k of fragmentation in worst case
(div 4)   16384 per block * 8 = 131k of fragmentation in worst case

So we'd go from 1.5megs of fragmentation to 387k total, in the worst case.  The block size is also around the size of the smallest graphs (ignoring mostly empty shutdown CCs), so fragmentation will "only" be around 100%, instead of 300% or whatever.
Here's the patch.  It is extremely intricate.

I'll try server it, because you never know.
Attachment #540175 - Flags: review?(peterv)
It passed a try server run.  It doesn't show it on the page for some reason, but I retriggered the Android Mochitest 2 and it passed.

http://tbpl.mozilla.org/?tree=Try&rev=faa1ae6fed84
Minor update: I changed the comment that talks about "millions" of PtrInfo to instead refer to "hundreds of thousands" of PtrInfo, to reflect the current state of affairs that I have observed, and that drove this change.
Attachment #540175 - Attachment is obsolete: true
Attachment #540175 - Flags: review?(peterv)
Attachment #540513 - Flags: review?(peterv)
Review ping.  This is a pretty simple patch.
Comment on attachment 540513 [details] [diff] [review]
reduce edge and node block size by a factor of 4 to reduce fragmentation

Review of attachment 540513 [details] [diff] [review]:
-----------------------------------------------------------------

Sure, let's try this.
Attachment #540513 - Flags: review?(peterv) → review+
http://hg.mozilla.org/mozilla-central/rev/4a2758e01ea1
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla8
You need to log in before you can comment on or make changes to this bug.