Note: There are a few cases of duplicates in user autocompletion which are being worked on.

reduce BlockSize for NodePool and EdgePool in cycle collector

RESOLVED FIXED in mozilla8

Status

()

Core
XPCOM
RESOLVED FIXED
6 years ago
6 years ago

People

(Reporter: mccr8, Assigned: mccr8)

Tracking

Other Branch
mozilla8
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [MemShrink:P2])

Attachments

(3 attachments, 2 obsolete attachments)

(Assignee)

Description

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

Updated

6 years ago
Blocks: 638299, 640457
(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)

Comment 2

6 years ago
Created attachment 538718 [details] [diff] [review]
crude patch to track memory usage and fragmentation in CC
Assignee: nobody → continuation
(Assignee)

Comment 3

6 years ago
Created attachment 538721 [details]
CC mem usage log for basic browsing around (techcrunch, cnn, facebook, etc.)

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

Comment 4

6 years ago
Created attachment 540166 [details] [diff] [review]
log mem usage for nodes and edges in CC

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
(Assignee)

Comment 5

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

Comment 6

6 years ago
Created attachment 540175 [details] [diff] [review]
reduce edge and node block size by 4 to reduce fragmentation

Here's the patch.  It is extremely intricate.

I'll try server it, because you never know.
Attachment #540175 - Flags: review?(peterv)
(Assignee)

Comment 7

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

Comment 8

6 years ago
Created attachment 540513 [details] [diff] [review]
reduce edge and node block size by a factor of 4 to reduce fragmentation

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)
(Assignee)

Comment 9

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

Comment 11

6 years ago
http://hg.mozilla.org/integration/mozilla-inbound/rev/4a2758e01ea1
http://hg.mozilla.org/mozilla-central/rev/4a2758e01ea1
Status: NEW → RESOLVED
Last Resolved: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla8
You need to log in before you can comment on or make changes to this bug.