Bug 1588431 - Optimize storage of ApplicableDeclaration again. r=heycam
authorEmilio Cobos Álvarez <emilio@crisal.io>
Wed, 13 Nov 2019 09:59:10 +0000
changeset 501907 06945900e072481a3ecacf3f75a1ea66fc422176
parent 501906 15ba6d5159446877cac2dee1ffa17cf53aba8d7a
child 501908 1f6cd5814db95dda18ac4aeaffe2dffcd2b887d9
push id114172
push userdluca@mozilla.com
push dateTue, 19 Nov 2019 11:31:10 +0000
treeherdermozilla-inbound@b5c5ba07d3db [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersheycam
bugs1588431
milestone72.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1588431 - Optimize storage of ApplicableDeclaration again. r=heycam So that we don't regress perf. Differential Revision: https://phabricator.services.mozilla.com/D52576
servo/components/style/applicable_declarations.rs
servo/components/style/rule_tree/mod.rs
--- a/servo/components/style/applicable_declarations.rs
+++ b/servo/components/style/applicable_declarations.rs
@@ -14,37 +14,47 @@ use smallvec::SmallVec;
 /// declarations between selector matching and inserting into the rule tree, and
 /// therefore we want to avoid heap-allocation where possible.
 ///
 /// In measurements on wikipedia, we pretty much never have more than 8 applicable
 /// declarations, so we could consider making this 8 entries instead of 16.
 /// However, it may depend a lot on workload, and stack space is cheap.
 pub type ApplicableDeclarationList = SmallVec<[ApplicableDeclarationBlock; 16]>;
 
+/// Blink uses 18 bits to store source order, and does not check overflow [1].
+/// That's a limit that could be reached in realistic webpages, so we use
+/// 24 bits and enforce defined behavior in the overflow case.
+///
+/// [1] https://cs.chromium.org/chromium/src/third_party/WebKit/Source/core/css/
+///     RuleSet.h?l=128&rcl=90140ab80b84d0f889abc253410f44ed54ae04f3
+const SOURCE_ORDER_SHIFT: usize = 0;
+const SOURCE_ORDER_BITS: usize = 24;
+const SOURCE_ORDER_MAX: u32 = (1 << SOURCE_ORDER_BITS) - 1;
+const SOURCE_ORDER_MASK: u32 = SOURCE_ORDER_MAX << SOURCE_ORDER_SHIFT;
+
+/// We pack the cascade level in a single byte, see CascadeLevel::to_byte_lossy
+/// for the different trade-offs there.
+const CASCADE_LEVEL_SHIFT: usize = SOURCE_ORDER_BITS;
+
 /// Stores the source order of a block, the cascade level it belongs to, and the
 /// counter needed to handle Shadow DOM cascade order properly.
-///
-/// FIXME(emilio): Optimize storage.
 #[derive(Clone, Copy, Eq, MallocSizeOf, PartialEq, Debug)]
-struct ApplicableDeclarationBits {
-    source_order: u32,
-    cascade_level: CascadeLevel,
-}
+struct ApplicableDeclarationBits(u32);
 
 impl ApplicableDeclarationBits {
     fn new(source_order: u32, cascade_level: CascadeLevel) -> Self {
-        Self { source_order, cascade_level }
+        Self((source_order & SOURCE_ORDER_MASK) | ((cascade_level.to_byte_lossy() as u32) << CASCADE_LEVEL_SHIFT))
     }
 
     fn source_order(&self) -> u32 {
-        self.source_order
+        self.0 & SOURCE_ORDER_MASK
     }
 
     fn level(&self) -> CascadeLevel {
-        self.cascade_level
+        CascadeLevel::from_byte((self.0 >> CASCADE_LEVEL_SHIFT) as u8)
     }
 }
 
 /// A property declaration together with its precedence among rules of equal
 /// specificity so that we can sort them.
 ///
 /// This represents the declarations in a given declaration block for a given
 /// importance.
--- a/servo/components/style/rule_tree/mod.rs
+++ b/servo/components/style/rule_tree/mod.rs
@@ -676,22 +676,86 @@ pub enum CascadeLevel {
         /// does the right thing.
         shadow_cascade_order: ShadowCascadeOrder,
     },
     /// User important rules.
     UserImportant,
     /// User-agent important rules.
     UAImportant,
     /// Transitions
-    ///
-    /// NB: If this changes from being last, change from_byte below.
     Transitions,
 }
 
 impl CascadeLevel {
+    /// Pack this cascade level in a single byte.
+    ///
+    /// We have 10 levels, which we can represent with 4 bits, and then a
+    /// cascade order optionally, which we can clamp to three bits max, and
+    /// represent with a fourth bit for the sign.
+    ///
+    /// So this creates: SOOODDDD
+    ///
+    /// Where `S` is the sign of the order (one if negative, 0 otherwise), `O`
+    /// is the absolute value of the order, and `D`s are the discriminant.
+    #[inline]
+    pub fn to_byte_lossy(&self) -> u8 {
+        let (discriminant, order) = match *self {
+            Self::UANormal => (0, 0),
+            Self::UserNormal => (1, 0),
+            Self::PresHints => (2, 0),
+            Self::AuthorNormal { shadow_cascade_order } => (3, shadow_cascade_order.0),
+            Self::SMILOverride => (4, 0),
+            Self::Animations => (5, 0),
+            Self::AuthorImportant { shadow_cascade_order } => (6, shadow_cascade_order.0),
+            Self::UserImportant => (7, 0),
+            Self::UAImportant => (8, 0),
+            Self::Transitions => (9, 0),
+        };
+
+        debug_assert_eq!(discriminant & 0xf, discriminant);
+        if order == 0 {
+            return discriminant;
+        }
+
+        let negative = order < 0;
+        let value = std::cmp::min(order.abs() as u8, 0b111);
+        (negative as u8) << 7 | value << 4 | discriminant
+    }
+
+    /// Convert back from the single-byte representation of the cascade level
+    /// explained above.
+    #[inline]
+    pub fn from_byte(b: u8) -> Self {
+        let order = {
+            let abs = ((b & 0b01110000) >> 4) as i8;
+            let negative = b & 0b10000000 != 0;
+            if negative { -abs } else { abs }
+        };
+        let discriminant = b & 0xf;
+        let level = match discriminant {
+            0 => Self::UANormal,
+            1 => Self::UserNormal,
+            2 => Self::PresHints,
+            3 => return Self::AuthorNormal {
+                shadow_cascade_order: ShadowCascadeOrder(order),
+            },
+            4 => Self::SMILOverride,
+            5 => Self::Animations,
+            6 => return Self::AuthorImportant {
+                shadow_cascade_order: ShadowCascadeOrder(order),
+            },
+            7 => Self::UserImportant,
+            8 => Self::UAImportant,
+            9 => Self::Transitions,
+            _ => unreachable!("Didn't expect {} as a discriminant", discriminant),
+        };
+        debug_assert_eq!(order, 0, "Didn't expect an order value for {:?}", level);
+        level
+    }
+
     /// Select a lock guard for this level
     pub fn guard<'a>(&self, guards: &'a StylesheetGuards<'a>) -> &'a SharedRwLockReadGuard<'a> {
         match *self {
             CascadeLevel::UANormal |
             CascadeLevel::UserNormal |
             CascadeLevel::UserImportant |
             CascadeLevel::UAImportant => guards.ua_or_user,
             _ => guards.author,