Closed Bug 1385165 Opened 4 years ago Closed 4 years ago

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

Categories

(Core :: JavaScript Engine: JIT, defect)

Product:
Core
Component:
JavaScript Engine: JIT
Platform:
Unspecified
All
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla57
Tracking Flags:
Tracking Status
firefox57 --- fixed

People

(Reporter: ting, Assigned: ting)

References

(Blocks 2 open bugs)

Details

Attachments

(1 file, 1 obsolete file)

Bug 1385165 - Calculate spill weight of a range's uses when add to or remove from it.
59 bytes, text/x-review-board-request
Details 
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
See Also: → 1384840
OS: Windows → All
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: nobody → janus926
Attached 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.
Another thing I'd like to try is to prefetch next node while walking through the liked list.
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.
But SegmentedVector has only append function, the UsePosition instances are sorted in the linked list.
(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.
Attachment #8893720 - Attachment is obsolete: true
Attachment #8896866 - Flags: review?(nicolas.b.pierron) → review?(bhackett1024)
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?
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 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+
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
https://hg.mozilla.org/mozilla-central/rev/df79199f9f0f
Status: NEW → RESOLVED
Closed: 4 years ago
status-firefox57: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla57
You need to log in before you can comment on or make changes to this bug.