--- a/layout/style/ServoBindings.cpp
+++ b/layout/style/ServoBindings.cpp
@@ -59,16 +59,17 @@
 #include "mozilla/Keyframe.h"
 #include "mozilla/Mutex.h"
 #include "mozilla/ServoElementSnapshot.h"
 #include "mozilla/ServoRestyleManager.h"
 #include "mozilla/SizeOfState.h"
 #include "mozilla/StyleAnimationValue.h"
 #include "mozilla/SystemGroup.h"
 #include "mozilla/ServoMediaList.h"
+#include "mozilla/Telemetry.h"
 #include "mozilla/RWLock.h"
 #include "mozilla/dom/Element.h"
 #include "mozilla/dom/ElementInlines.h"
 #include "mozilla/dom/HTMLTableCellElement.h"
 #include "mozilla/dom/HTMLBodyElement.h"
 #include "mozilla/LookAndFeel.h"
 #include "mozilla/URLExtraData.h"
 
@@ -116,16 +117,27 @@ ThreadSafeGetDefaultFontHelper(const nsP
 }
 
 void
 AssertIsMainThreadOrServoLangFontPrefsCacheLocked()
 {
   MOZ_ASSERT(NS_IsMainThread() || sServoFFILock->LockedForWritingByCurrentThread());
 }
 
+
+void
+Gecko_RecordTraversalStatistics(uint32_t total, uint32_t parallel)
+{
+  // we ignore cases where a page just didn't restyle a lot
+  if (total > 30) {
+    uint32_t percent = parallel * 100 / total;
+    Telemetry::Accumulate(Telemetry::STYLO_PARALLEL_RESTYLE_FRACTION, percent);
+  }
+}
+
 bool
 Gecko_IsInDocument(RawGeckoNodeBorrowed aNode)
 {
   return aNode->IsInComposedDoc();
 }
 
 #ifdef MOZ_DEBUG_RUST
 bool

--- a/layout/style/ServoBindings.h
+++ b/layout/style/ServoBindings.h
@@ -137,16 +137,17 @@ struct FontSizePrefs
   nscoord mDefaultSerifSize;
   nscoord mDefaultSansSerifSize;
   nscoord mDefaultMonospaceSize;
   nscoord mDefaultCursiveSize;
   nscoord mDefaultFantasySize;
 };
 
 // DOM Traversal.
+void Gecko_RecordTraversalStatistics(uint32_t total, uint32_t parallel);
 bool Gecko_IsInDocument(RawGeckoNodeBorrowed node);
 bool Gecko_FlattenedTreeParentIsParent(RawGeckoNodeBorrowed node);
 bool Gecko_IsSignificantChild(RawGeckoNodeBorrowed node,
                               bool text_is_significant,
                               bool whitespace_is_significant);
 RawGeckoNodeBorrowedOrNull Gecko_GetLastChild(RawGeckoNodeBorrowed node);
 RawGeckoNodeBorrowedOrNull Gecko_GetFlattenedTreeParentNode(RawGeckoNodeBorrowed node);
 RawGeckoElementBorrowedOrNull Gecko_GetBeforeOrAfterPseudo(RawGeckoElementBorrowed element, bool is_before);

--- a/servo/components/style/driver.rs
+++ b/servo/components/style/driver.rs
@@ -20,29 +20,32 @@ use traversal::{DomTraversal, PerLevelTr
 
 /// Do a DOM traversal for top-down and (optionally) bottom-up processing,
 /// generic over `D`.
 ///
 /// We use an adaptive traversal strategy. We start out with simple sequential
 /// processing, until we arrive at a wide enough level in the DOM that the
 /// parallel traversal would parallelize it. If a thread pool is provided, we
 /// then transfer control over to the parallel traversal.
+///
+/// Returns true if the traversal was parallel
 pub fn traverse_dom<E, D>(
     traversal: &D,
     token: PreTraverseToken<E>,
     pool: Option<&rayon::ThreadPool>
-)
+) -> bool
 where
     E: TElement,
     D: DomTraversal<E>,
 {
     let root =
         token.traversal_root().expect("Should've ensured we needed to traverse");
 
     let dump_stats = traversal.shared_context().options.dump_style_statistics;
+    let mut used_parallel = false;
     let start_time = if dump_stats { Some(time::precise_time_s()) } else { None };
 
     // Declare the main-thread context, as well as the worker-thread contexts,
     // which we may or may not instantiate. It's important to declare the worker-
     // thread contexts first, so that they get dropped second. This matters because:
     //   * ThreadLocalContexts borrow AtomicRefCells in TLS.
     //   * Dropping a ThreadLocalContext can run SequentialTasks.
     //   * Sequential tasks may call into functions like
@@ -79,16 +82,17 @@ where
         nodes_remaining_at_current_depth -= 1;
         if nodes_remaining_at_current_depth == 0 {
             depth += 1;
             // If there is enough work to parallelize over, and the caller allows
             // parallelism, switch to the parallel driver. We do this only when
             // moving to the next level in the dom so that we can pass the same
             // depth for all the children.
             if pool.is_some() && discovered.len() > WORK_UNIT_MAX {
+                used_parallel = true;
                 let pool = pool.unwrap();
                 maybe_tls = Some(ScopedTLS::<ThreadLocalStyleContext<E>>::new(pool));
                 let root_opaque = root.as_node().opaque();
                 let drain = discovered.drain(..);
                 pool.install(|| {
                     rayon::scope(|scope| {
                         parallel::traverse_nodes(
                             drain,
@@ -123,9 +127,11 @@ where
                 }
             });
         }
         aggregate.finish(traversal, parallel, start_time.unwrap());
         if aggregate.is_large_traversal() {
             println!("{}", aggregate);
         }
     }
+
+    used_parallel
 }

--- a/servo/components/style/gecko/data.rs
+++ b/servo/components/style/gecko/data.rs
@@ -11,16 +11,17 @@ use gecko_bindings::structs::{RawGeckoPr
 use gecko_bindings::structs::{StyleSheetInfo, ServoStyleSheetInner, nsIDocument, self};
 use gecko_bindings::sugar::ownership::{HasArcFFI, HasBoxFFI, HasFFI, HasSimpleFFI};
 use invalidation::media_queries::{MediaListKey, ToMediaListKey};
 use malloc_size_of::MallocSizeOfOps;
 use media_queries::{Device, MediaList};
 use properties::ComputedValues;
 use servo_arc::Arc;
 use shared_lock::{Locked, StylesheetGuards, SharedRwLockReadGuard};
+use std::sync::atomic::{AtomicUsize, Ordering};
 use stylesheets::{StylesheetContents, StylesheetInDocument};
 use stylist::Stylist;
 
 /// Little wrapper to a Gecko style sheet.
 #[derive(Debug, Eq, PartialEq)]
 pub struct GeckoStyleSheet(*const ServoStyleSheet);
 
 impl ToMediaListKey for ::gecko::data::GeckoStyleSheet {
@@ -107,16 +108,20 @@ impl StylesheetInDocument for GeckoStyle
     }
 }
 
 /// The container for data that a Servo-backed Gecko document needs to style
 /// itself.
 pub struct PerDocumentStyleDataImpl {
     /// Rule processor.
     pub stylist: Stylist,
+    /// Total number of traversals that could have been parallel, for telemetry
+    pub total_traversal_count: AtomicUsize,
+    /// Number of parallel traversals
+    pub parallel_traversal_count: AtomicUsize,
 }
 
 /// The data itself is an `AtomicRefCell`, which guarantees the proper semantics
 /// and unexpected races while trying to mutate it.
 pub struct PerDocumentStyleData(AtomicRefCell<PerDocumentStyleDataImpl>);
 
 impl PerDocumentStyleData {
     /// Create a dummy `PerDocumentStyleData`.
@@ -128,30 +133,40 @@ impl PerDocumentStyleData {
         //
         // Should we just force XBL Stylists to be NoQuirks?
         let quirks_mode = unsafe {
             (*device.pres_context().mDocument.raw::<nsIDocument>()).mCompatMode
         };
 
         PerDocumentStyleData(AtomicRefCell::new(PerDocumentStyleDataImpl {
             stylist: Stylist::new(device, quirks_mode.into()),
+            total_traversal_count: Default::default(),
+            parallel_traversal_count: Default::default(),
         }))
     }
 
     /// Get an immutable reference to this style data.
     pub fn borrow(&self) -> AtomicRef<PerDocumentStyleDataImpl> {
         self.0.borrow()
     }
 
     /// Get an mutable reference to this style data.
     pub fn borrow_mut(&self) -> AtomicRefMut<PerDocumentStyleDataImpl> {
         self.0.borrow_mut()
     }
 }
 
+impl Drop for PerDocumentStyleDataImpl {
+    fn drop(&mut self) {
+        let total = self.total_traversal_count.load(Ordering::Relaxed) as u32;
+        let parallel = self.parallel_traversal_count.load(Ordering::Relaxed) as u32;
+        unsafe { bindings::Gecko_RecordTraversalStatistics(total, parallel) }
+    }
+}
+
 impl PerDocumentStyleDataImpl {
     /// Recreate the style data if the stylesheets have changed.
     pub fn flush_stylesheets<E>(
         &mut self,
         guard: &SharedRwLockReadGuard,
         document_element: Option<E>,
     ) -> bool
     where
@@ -183,15 +198,23 @@ impl PerDocumentStyleDataImpl {
     pub fn visited_styles_enabled(&self) -> bool {
         self.visited_links_enabled() && !self.is_private_browsing_enabled()
     }
 
     /// Measure heap usage.
     pub fn add_size_of(&self, ops: &mut MallocSizeOfOps, sizes: &mut ServoStyleSetSizes) {
         self.stylist.add_size_of(ops, sizes);
     }
+
+    /// Record that a traversal happened for later collection as telemetry
+    pub fn record_traversal(&self, was_parallel: bool) {
+        self.total_traversal_count.fetch_add(1, Ordering::Relaxed);
+        if was_parallel {
+            self.parallel_traversal_count.fetch_add(1, Ordering::Relaxed);
+        }
+    }
 }
 
 unsafe impl HasFFI for PerDocumentStyleData {
     type FFIType = RawServoStyleSet;
 }
 unsafe impl HasSimpleFFI for PerDocumentStyleData {}
 unsafe impl HasBoxFFI for PerDocumentStyleData {}

--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -258,18 +258,29 @@ fn traverse_subtree(
 
     let thread_pool_holder = &*STYLE_THREAD_POOL;
     let thread_pool = if traversal_flags.contains(TraversalFlags::ParallelTraversal) {
         thread_pool_holder.style_thread_pool.as_ref()
     } else {
         None
     };
 
+    let is_restyle = element.get_data().is_some();
+
     let traversal = RecalcStyleOnly::new(shared_style_context);
-    driver::traverse_dom(&traversal, token, thread_pool);
+    let used_parallel = driver::traverse_dom(&traversal, token, thread_pool);
+
+    if traversal_flags.contains(TraversalFlags::ParallelTraversal) &&
+       !traversal_flags.contains(TraversalFlags::AnimationOnly) &&
+       is_restyle && !element.is_native_anonymous() {
+       // We turn off parallel traversal for background tabs; this
+       // shouldn't count in telemetry. We're also focusing on restyles so
+       // we ensure that it's a restyle.
+       per_doc_data.record_traversal(used_parallel);
+    }
 }
 
 /// Traverses the subtree rooted at `root` for restyling.
 ///
 /// Returns whether the root was restyled. Whether anything else was restyled or
 /// not can be inferred from the dirty bits in the rest of the tree.
 #[no_mangle]
 pub extern "C" fn Servo_TraverseSubtree(

--- a/toolkit/components/telemetry/Histograms.json
+++ b/toolkit/components/telemetry/Histograms.json
@@ -13862,10 +13862,20 @@
     "record_in_processes": ["content"],
     "alert_emails": ["gfx-telemetry-alerts@mozilla.com","danderson@mozilla.com"],
     "expires_in_version": "61",
     "kind": "exponential",
     "high": 200,
     "n_buckets": 50,
     "description": "Amount of time in milliseconds the main thread spends waiting for the paint thread to complete, if the time was greater than 200us.",
     "bug_numbers": [1386968]
+  },
+  "STYLO_PARALLEL_RESTYLE_FRACTION": {
+    "record_in_processes": ["content"],
+    "alert_emails": ["manish@mozilla.com"],
+    "expires_in_version": "60",
+    "kind": "linear",
+    "high": 100,
+    "n_buckets": 50,
+    "description": "Fraction of restyles on a single page that were parallel",
+    "bug_numbers": [1421195]
   }
 }