Closed Bug 1367190 Opened 7 years ago Closed 7 years ago

nsPresArena::mFreeLists should be an array rather than a hashtable

Categories

(Core :: Layout, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla55
Tracking Status
firefox55 --- fixed

People

(Reporter: dbaron, Assigned: dbaron)

Details

(Keywords: perf)

Attachments

(3 files, 3 obsolete files)

nsPresArena::mFreeLists is currently a hashtable.  However, most of the uses of it are based on two sets of fixed entries (AllocateByFrameID uses nsQueryFrame::FrameIID and AllocateByObjectID uses mozilla::ArenaObjectID), and AllocateBySize probably uses a relatively limited set of buckets that we could perhaps more strictly limit.

mFreeLists should instead just be an array so that we don't have to deal with a hashtable.

(We could perhaps get rid of AllocateBySize entirely and avoid dealing with the size problem!)
Rank: 25
Priority: -- → P2
Assignee: nobody → dbaron
Status: NEW → ASSIGNED
Rank: 25
Priority: P2 → --
Component: Audio/Video: GMP → Layout
Attachment #8870584 - Attachment is obsolete: true
Attachment #8870584 - Flags: review?(mats)
Aargh!  Something in version-control-tools is changing the descriptions of the patches in my queue repository!
Attachment #8870590 - Attachment is obsolete: true
Attachment #8870590 - Flags: review?(mats)
Attachment #8870593 - Attachment is obsolete: true
Attachment #8870593 - Flags: review?(mats)
Also, for the record, mozilla::eArenaObjectID_COUNT is currently 215.

I've reduced FreeList from 4 (64-bit) or 5 (32-bit) words to 3 words, and PLDHashTable's entry store leaves a decent number of free entries (doubling the store size when it reaches 75%, I believe).

I'm not exactly sure what that adds up to memory-wise, but I think it's worth the tradeoff.
Attachment #8870595 - Attachment description: Bug 1367190 patch 3 - Store nsPresArena::mFreeLists as an array. → patch 3 - Store nsPresArena::mFreeLists as an array.
So the memory usage of the PLDHashTable prior to the patch should have been (counting the entry store (20 bytes (32-bit) or 32 bytes (64-bit) per entry) plus the 28-byte (32-bit) or 40-byte (64-bit) PLDHashTable itself) should be (ignoring allocator overhead for the extra allocation in the old setup!), I think:

types     entry     32-bit   64-bit
alloc'd   store     size     size
          entries
    0-6         8     188      296
   7-12        16     348      552
  13-24        32     668     1064
  25-48        64    1308     2088
  49-96       128    2588     4136
 97-192       256    5148     8232
193-384       512   10268    16424

With the new setup, we always allocate 2580 bytes on 32-bit and 5160 bytes on 64-bit.

So on 32-bit the new setup uses less space if we've allocated objects with 49 or more of the types; on 64-bit it uses less space if we've allocated 97 or more.


Loading data:text/html,<!DOCTYPE HTML><body> allocates objects of 36 of the types (with the patch to convert the last 4 types).

Loading https://www.google.com allocates objects of 61 of the types (again, with the conversion patch).


I computed those in gdb with:

set $i = 0
set $sum = 0
while $i < 215
  set $sum = $sum + ($13.mFreeLists[$i].mEntriesEverAllocated != 0)
  set $i = $i + 1
  end
p $i
p $sum
Oh, and the reason I noticed this was because I saw the hashtable operation show up in a profile (although only on one sample... but it was also a pretty small profile).
Keywords: perf
Comment on attachment 8870582 [details] [diff] [review]
patch 1 - Convert the 4 objects that use nsPresArena::AllocateBySize to use AllocateByObjectID.

> layout/generic/nsIntervalSet.cpp
>+    Interval *newInterval = static_cast<Interval*>(AllocateInterval());

I'd use 'auto' here instead of repeating the type.

>     if (!newInterval) {
>         NS_NOTREACHED("allocation failure");
>         return;
>     }

While we're here... please remove this since pres arena allocation is
infallible now.

> layout/generic/nsIntervalSet.h
> typedef void *
> (* IntervalSetAlloc)(size_t aBytes, void *aClosure);
> 
> typedef void
> (* IntervalSetFree) (size_t aBytes, void *aPtr, void *aClosure);

Can we remove those typedefs now?
Attachment #8870582 - Flags: review?(mats) → review+
Attachment #8870586 - Flags: review?(mats) → review+
Comment on attachment 8870595 [details] [diff] [review]
patch 3 - Store nsPresArena::mFreeLists as an array.

>layout/base/nsPresArena.cpp
>+  for (FreeList *entry = mFreeLists; entry != ArrayEnd(mFreeLists); ++entry) {

nit: * with the typename please

>   // If there is no free-list entry for this type already, we have
>   // to create one now, to record its size.
>-  FreeList* list = mFreeLists.PutEntry(aCode);
>+  FreeList* list = &mFreeLists[aCode];

The code comment becomes a bit confusing now since the "... we have to
create one now," part comments on the PutEntry() which we now remove.
We should probably remove it altogether.

>   nsTArray<void*>::index_type len = list->mEntries.Length();
>   if (list->mEntrySize == 0) {
>     MOZ_ASSERT(len == 0, "list with entries but no recorded size");
>     list->mEntrySize = aSize;
>   } else {
>     MOZ_ASSERT(list->mEntrySize == aSize,
>                "different sizes for same object type code");

This code can probably be simplified and avoid the branch.  Could we write
the assertion(s) upfront, and then unconditionally assign
"list->mEntrySize = aSize" afterwards?
(feel free to leave it as is though)

>+  for (FreeList *entry = mFreeLists; entry != ArrayEnd(mFreeLists); ++entry) {

nit: * with the typename please

>layout/base/nsPresArena.h
>+    FreeList()
>+      : mEntrySize(0)
>+      , mEntriesEverAllocated(0)
>+    {
>+    }

nit: I think {} is the more commonly used style

>     // Default copy constructor and destructor are ok.

This comment should be removed.
Attachment #8870595 - Flags: review?(mats) → review+
(In reply to David Baron :dbaron: ⌚️UTC-4 from comment #10)
> With the new setup, we always allocate 2580 bytes on 32-bit and 5160 bytes
> on 64-bit.

FYI, I found 3 of the frame IDs we declare are actually not used anymore,
so there will be 3 less entries in the array soon.
https://hg.mozilla.org/integration/mozilla-inbound/rev/9becc74079ff446688e59470cc38bd75dc3f5c9e
Bug 1367190 patch 1 - Convert the 4 objects that use nsPresArena::AllocateBySize to use AllocateByObjectID.  r=mats

https://hg.mozilla.org/integration/mozilla-inbound/rev/d0f672dfdeb6bbf77d204b530b0b8f22772a19f5
Bug 1367190 patch 2 - Remove nsPresArena::AllocateBySize, nsIPresShell::AllocateMisc, and nsPresContext::AllocateFromShell.  r=mats

https://hg.mozilla.org/integration/mozilla-inbound/rev/b096ffc589e36bbf87fa28beaef8edce2bd3b31a
Bug 1367190 patch 3 - Store nsPresArena::mFreeLists as an array.  r=mats
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: