--- a/gfx/webrender_bindings/WebRenderAPI.cpp
+++ b/gfx/webrender_bindings/WebRenderAPI.cpp
@@ -609,16 +609,23 @@ DisplayListBuilder::PushBuiltDisplayList
 void
 DisplayListBuilder::PushScrollLayer(const layers::FrameMetrics::ViewID& aScrollId,
                                     const WrRect& aContentRect,
                                     const WrRect& aClipRect)
 {
   WRDL_LOG("PushScrollLayer id=%" PRIu64 " co=%s cl=%s\n",
       aScrollId, Stringify(aContentRect).c_str(), Stringify(aClipRect).c_str());
   wr_dp_push_scroll_layer(mWrState, aScrollId, aContentRect, aClipRect);
+  if (!mScrollIdStack.empty()) {
+    auto it = mScrollParents.insert({aScrollId, mScrollIdStack.back()});
+    if (!it.second) { // aScrollId was already a key in mScrollParents
+                      // so check that the parent value is the same.
+      MOZ_ASSERT(it.first->second == mScrollIdStack.back());
+    }
+  }
   mScrollIdStack.push_back(aScrollId);
 }
 
 void
 DisplayListBuilder::PopScrollLayer()
 {
   WRDL_LOG("PopScrollLayer id=%" PRIu64 "\n", mScrollIdStack.back());
   mScrollIdStack.pop_back();
@@ -899,21 +906,14 @@ DisplayListBuilder::TopmostClipId()
     return Nothing();
   }
   return Some(mClipIdStack.back());
 }
 
 Maybe<layers::FrameMetrics::ViewID>
 DisplayListBuilder::ParentScrollIdFor(layers::FrameMetrics::ViewID aScrollId)
 {
-  // Finds the scrollId in mScrollIdStack immediately before aScrollId, or
-  // returns Nothing() if it can't find one
-  for (auto it = mScrollIdStack.rbegin(); it != mScrollIdStack.rend(); it++) {
-    if (*it == aScrollId) {
-      it++;
-      return (it == mScrollIdStack.rend() ? Nothing() : Some(*it));
-    }
-  }
-  return Nothing();
+  auto it = mScrollParents.find(aScrollId);
+  return (it == mScrollParents.end() ? Nothing() : Some(it->second));
 }
 
 } // namespace wr
 } // namespace mozilla

--- a/gfx/webrender_bindings/WebRenderAPI.h
+++ b/gfx/webrender_bindings/WebRenderAPI.h
@@ -3,16 +3,17 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef MOZILLA_LAYERS_WEBRENDERAPI_H
 #define MOZILLA_LAYERS_WEBRENDERAPI_H
 
 #include <vector>
+#include <unordered_map>
 
 #include "mozilla/AlreadyAddRefed.h"
 #include "mozilla/Range.h"
 #include "mozilla/webrender/webrender_ffi.h"
 #include "mozilla/webrender/WebRenderTypes.h"
 #include "FrameMetrics.h"
 #include "GLTypes.h"
 #include "Units.h"
@@ -288,34 +289,36 @@ public:
   WrClipRegionToken PushClipRegion(const WrRect& aMain,
                                    const nsTArray<WrComplexClipRegion>& aComplex,
                                    const WrImageMask* aMask = nullptr);
 
   // Returns the clip id that was most recently pushed with PushClip and that
   // has not yet been popped with PopClip. Return Nothing() if the clip stack
   // is empty.
   Maybe<WrClipId> TopmostClipId();
-  // Returns the scroll id that was pushed just before the given scroll id.
-  // If the given scroll id is not in the stack of active scrolled layers, or if
-  // it is the rootmost scroll id (and therefore has no ancestor), this function
-  // returns Nothing().
+  // Returns the scroll id that was pushed just before the given scroll id. This
+  // function returns Nothing() if the given scrollid has not been encountered,
+  // or if it is the rootmost scroll id (and therefore has no ancestor).
   Maybe<layers::FrameMetrics::ViewID> ParentScrollIdFor(layers::FrameMetrics::ViewID aScrollId);
 
   // Try to avoid using this when possible.
   WrState* Raw() { return mWrState; }
 protected:
   WrState* mWrState;
 
   // Track the stack of clip ids and scroll layer ids that have been pushed
   // (by PushClip and PushScrollLayer, respectively) and are still active.
   // This is helpful for knowing e.g. what the ancestor scroll id of a particular
   // scroll id is, and doing other "queries" of current state.
   std::vector<WrClipId> mClipIdStack;
   std::vector<layers::FrameMetrics::ViewID> mScrollIdStack;
 
+  // Track the parent scroll id of each scroll id that we encountered.
+  std::unordered_map<layers::FrameMetrics::ViewID, layers::FrameMetrics::ViewID> mScrollParents;
+
   friend class WebRenderAPI;
 };
 
 Maybe<WrImageFormat>
 SurfaceFormatToWrImageFormat(gfx::SurfaceFormat aFormat);
 
 } // namespace wr
 } // namespace mozilla