BacktrackingAllocator::computeSpillWeight() is slow in UsePosition::usePolicy()

RESOLVED FIXED in Firefox 57

Status

()

defect
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: ting, Assigned: ting)

Tracking

(Blocks 2 bugs)

Trunk
mozilla57
Unspecified
All
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox57 fixed)

Details

Attachments

(1 attachment, 1 obsolete attachment)

Assignee

Description

2 years ago
I found this when profile Speedometer Ember test, BacktrackingAllocator::computeSpillWeight() is slow in usePolicy() for accessing UsePosition.use_ inside the for loop [1]:

  for (UsePositionIterator iter = range->usesBegin(); iter; iter++) {
      switch (iter->usePolicy()) {

[1] http://searchfox.org/mozilla-central/rev/ad093e98f42338effe2e2513e26c3a311dd96422/js/src/jit/BacktrackingAllocator.cpp#2550
Assignee

Updated

2 years ago
See Also: → 1384840
Assignee

Updated

2 years ago
OS: Windows → All
Assignee

Comment 1

2 years ago
In bug 709731, the uses_ was changed from a Vector to a InlineForwardList. I am not sure, but it seems the reason is for the splitAfter() call which is not used in current code base. If my understanding is correct, we should consider switch it back to a Vector.
Assignee

Updated

2 years ago
Assignee: nobody → janus926
Assignee

Comment 2

2 years ago
Posted patch experiment patch (obsolete) — Splinter Review
This experiment patch uses Vector to store UsePosition instead. The local test shows the time it spends in Vector::insert() and Vector::erase() is way more than the time it saves in computeSpillWeight(). I can tweak the initial size of the Vector, but probably still won't outperform linked list.
Assignee

Comment 3

2 years ago
Another thing I'd like to try is to prefetch next node while walking through the liked list.
Assignee

Comment 4

2 years ago
Tried following on Linux and Windows, but I don't see any noticeable improvements:

  for (UsePositionIterator iter = range->usesBegin(); iter; ) {
      LUse::Policy policy = iter++->usePolicy();
#ifdef __GNU__
      __builtin_prefetch(*iter);
#else
      _mm_prefetch(reinterpret_cast<const char*>(*iter), _MM_HINT_T0);
#endif
      switch (policy) {
Comment on attachment 8893720 [details] [diff] [review]
experiment patch

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

::: js/src/jit/BacktrackingAllocator.h
@@ +259,4 @@
>      Range range_;
>  
>      // All uses of the virtual register in this range, ordered by location.
> +    Vector<UsePosition, 1, JitAllocPolicy> uses_;

Vector and JitAllocPolicy are not working well together because the JitAllocPolicy is an append only allocator, which implies that every time the Vector is being resized we would be wasting space in in the LifoAlloc.

The best would be to use a SegmentedVector here with the JitAllocPolicy (we would have to double check)

Note, we cannot use a Vector<*, *, SystemAllocPolicy> here, because this is a member of a TempObject, and no destructors are being executed for these.  Thus using a SystemAllocPolicy as often recommended within Ion would lead to memory leaks.
Assignee

Comment 6

2 years ago
But SegmentedVector has only append function, the UsePosition instances are sorted in the linked list.
Assignee

Comment 7

2 years ago
(In reply to Ting-Yu Chou [:ting] from comment #6)
> But SegmentedVector has only append function, the UsePosition instances are
> sorted in the linked list.

It seems that only the minimal and maximal UsePosition are required, if that's the case we don't need to sort them.
Comment hidden (mozreview-request)
Assignee

Updated

2 years ago
Attachment #8893720 - Attachment is obsolete: true
Attachment #8896866 - Flags: review?(nicolas.b.pierron) → review?(bhackett1024)

Comment 9

2 years ago
mozreview-review
Comment on attachment 8896866 [details]
Bug 1385165 - Calculate spill weight of a range's uses when add to or remove from it.

https://reviewboard.mozilla.org/r/168154/#review173340

This change sounds good to me, but I am not a master of the Backtracking Allocator.
:ting, just curious, did you see any perf improvements?
Assignee

Comment 11

2 years ago
Actually I didn't see noticeable improvement from Speedometer's numbers (the numbers weren't stable and I tested just 2 runs), but I can see the CPU time that VTune reports for the signature is gone:

Before: 4.761s
  computeSpillWeight: 0.019s
  maximumSpillWeight: 3.725s
  addUse: 0.160s
  popUse: n/a
  distributeUses: 0.857s
  
After: 1.912s
  computeSpillWeight: 0.004s
  maximumSpillWeight: 0.574s
  addUse: 0.377s
  popUse: n/a
  distributeUses: 0.957s

Comment 12

2 years ago
mozreview-review
Comment on attachment 8896866 [details]
Bug 1385165 - Calculate spill weight of a range's uses when add to or remove from it.

https://reviewboard.mozilla.org/r/168154/#review173958

Thanks for looking at this.

::: js/src/jit/BacktrackingAllocator.h:262
(Diff revision 1)
>      Range range_;
>  
>      // All uses of the virtual register in this range, ordered by location.
>      InlineForwardList<UsePosition> uses_;
> +    size_t usesSpillWeight_;
> +    uint32_t numFixedUses_;

These fields need their own comments.

::: js/src/jit/BacktrackingAllocator.cpp:111
(Diff revision 1)
>          if (other->covers(use->pos)) {
>              uses_.removeAndIncrement(iter);
> +            LUse::Policy policy = use->usePolicy();
> +            usesSpillWeight_ -= BacktrackingAllocator::SpillWeightFromUsePolicy(policy);
> +            if (policy == LUse::FIXED)
> +                --numFixedUses_;

This should be commoned with the identical code in LiveRange::popUse.  How about noteNewUse and noteRemovedUse methods that manage the total spill weight and fixed uses fields, to make the symmetrical behavior here clearer.
Attachment #8896866 - Flags: review?(bhackett1024) → review+
Comment hidden (mozreview-request)
Comment hidden (mozreview-request)

Comment 15

2 years ago
Pushed by tchou@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/df79199f9f0f
Calculate spill weight of a range's uses when add to or remove from it. r=bhackett

Comment 16

2 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/df79199f9f0f
Status: NEW → RESOLVED
Last Resolved: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla57
You need to log in before you can comment on or make changes to this bug.