gfx: Perform more aggressive caching in

`FontContext::get_layout_font_group_for_style()`.

There are several optimizations here:

* We make font families atoms, to allow for quicker comparisons.

* We precalculate an FNV hash of the relevant fields of the font style
  structure.

* When obtaining a platform font group, we first check pointer equality
  for the font style. If there's no match, we go to the FNV hash. Only
  if both caches miss do we construct and cache a font group. Note that
  individual fonts are *also* cached; thus there are two layers of
  caching here.

15% improvement in total layout thread time for Facebook Timeline.

14 files changed, 142 insertions, 60 deletions

diff --git a/components/gfx/Cargo.toml b/components/gfx/Cargo.toml
index bb213624240..b012c92b6d8 100644
--- a/components/gfx/Cargo.toml
+++ b/components/gfx/Cargo.toml
@@ -66,6 +66,9 @@ branch = "upstream-2014-06-16"
 [dependencies.script_traits]
 path = "../script_traits"
 
+[dependencies.string_cache]
+git = "https://github.com/servo/string-cache"
+
 [dependencies]
 url = "0.2.16"
 time = "0.1.12"
diff --git a/components/gfx/font_cache_task.rs b/components/gfx/font_cache_task.rs
index 8a87ed9fdb0..e22fe434f85 100644
--- a/components/gfx/font_cache_task.rs
+++ b/components/gfx/font_cache_task.rs
@@ -9,16 +9,17 @@ use platform::font_list::get_last_resort_font_families;
 use platform::font_context::FontContextHandle;
 
 use collections::str::Str;
+use font_template::{FontTemplate, FontTemplateDescriptor};
+use net::resource_task::{ResourceTask, load_whole_resource};
+use platform::font_template::FontTemplateData;
 use std::borrow::ToOwned;
 use std::collections::HashMap;
 use std::sync::Arc;
 use std::sync::mpsc::{Sender, Receiver, channel};
-use font_template::{FontTemplate, FontTemplateDescriptor};
-use platform::font_template::FontTemplateData;
-use net::resource_task::{ResourceTask, load_whole_resource};
-use util::task::spawn_named;
-use util::str::LowercaseString;
+use string_cache::Atom;
 use style::font_face::Source;
+use util::str::LowercaseString;
+use util::task::spawn_named;
 
 /// A list of font templates that make up a given font family.
 struct FontFamily {
@@ -77,7 +78,7 @@ impl FontFamily {
 pub enum Command {
     GetFontTemplate(String, FontTemplateDescriptor, Sender<Reply>),
     GetLastResortFontTemplate(FontTemplateDescriptor, Sender<Reply>),
-    AddWebFont(String, Source, Sender<()>),
+    AddWebFont(Atom, Source, Sender<()>),
     Exit(Sender<()>),
 }
 
@@ -315,7 +316,7 @@ impl FontCacheTask {
         }
     }
 
-    pub fn add_web_font(&self, family: String, src: Source) {
+    pub fn add_web_font(&self, family: Atom, src: Source) {
         let (response_chan, response_port) = channel();
         self.chan.send(Command::AddWebFont(family, src, response_chan)).unwrap();
         response_port.recv().unwrap();
diff --git a/components/gfx/font_context.rs b/components/gfx/font_context.rs
index 24574676f65..fe9dbab2b12 100644
--- a/components/gfx/font_context.rs
+++ b/components/gfx/font_context.rs
@@ -7,19 +7,24 @@ use font::SpecifiedFontStyle;
 use platform::font_context::FontContextHandle;
 use style::computed_values::{font_style, font_variant};
 
+use font::FontHandleMethods;
 use font_cache_task::FontCacheTask;
 use font_template::FontTemplateDescriptor;
-use platform::font_template::FontTemplateData;
-use font::FontHandleMethods;
 use platform::font::FontHandle;
+use platform::font_template::FontTemplateData;
+use util::arc_ptr_eq;
 use util::cache::HashCache;
-use util::smallvec::{SmallVec, SmallVec8};
+use util::fnv::FnvHasher;
 use util::geometry::Au;
-use util::arc_ptr_eq;
+use util::smallvec::{SmallVec, SmallVec8};
 
-use std::borrow::ToOwned;
-use std::rc::Rc;
+use std::borrow::{self, ToOwned};
 use std::cell::RefCell;
+use std::collections::HashMap;
+use std::collections::hash_state::DefaultState;
+use std::default::Default;
+use std::hash::{Hash, Hasher};
+use std::rc::Rc;
 use std::sync::Arc;
 
 use azure::AzFloat;
@@ -76,8 +81,8 @@ pub struct FontContext {
     /// per frame. TODO: Make this weak when incremental redraw is done.
     paint_font_cache: Vec<PaintFontCacheEntry>,
 
-    last_style: Option<Arc<SpecifiedFontStyle>>,
-    last_fontgroup: Option<Rc<FontGroup>>,
+    layout_font_group_cache:
+        HashMap<LayoutFontGroupCacheKey,Rc<FontGroup>,DefaultState<FnvHasher>>,
 }
 
 impl FontContext {
@@ -89,8 +94,7 @@ impl FontContext {
             layout_font_cache: vec!(),
             fallback_font_cache: vec!(),
             paint_font_cache: vec!(),
-            last_style: None,
-            last_fontgroup: None,
+            layout_font_group_cache: HashMap::with_hash_state(Default::default()),
         }
     }
 
@@ -132,14 +136,21 @@ impl FontContext {
     /// this context.
     pub fn get_layout_font_group_for_style(&mut self, style: Arc<SpecifiedFontStyle>)
                                             -> Rc<FontGroup> {
-        let matches = match self.last_style {
-            Some(ref last_style) => arc_ptr_eq(&style, last_style),
-            None => false,
-        };
-        if matches {
-            return self.last_fontgroup.as_ref().unwrap().clone();
+        let address = &*style as *const SpecifiedFontStyle as usize;
+        if let Some(ref cached_font_group) = self.layout_font_group_cache.get(&address) {
+            return (*cached_font_group).clone()
         }
 
+        let layout_font_group_cache_key = LayoutFontGroupCacheKey {
+            pointer: style.clone(),
+            size: style.font_size,
+            address: address,
+        };
+        if let Some(ref cached_font_group) =
+            self.layout_font_group_cache.get(&layout_font_group_cache_key) {
+                return (*cached_font_group).clone()
+            }
+
         // TODO: The font context holds a strong ref to the cached fonts
         // so they will never be released. Find out a good time to drop them.
 
@@ -147,6 +158,7 @@ impl FontContext {
                                                style.font_stretch,
                                                style.font_style == font_style::T::italic ||
                                                 style.font_style == font_style::T::oblique);
+
         let mut fonts = SmallVec8::new();
 
         for family in style.font_family.iter() {
@@ -160,7 +172,7 @@ impl FontContext {
                             break;
                         }
                         Some(ref cached_font_ref) => {
-                            let cached_font = cached_font_ref.borrow();
+                            let cached_font = (*cached_font_ref).borrow();
                             if cached_font.descriptor == desc &&
                                cached_font.requested_pt_size == style.font_size &&
                                cached_font.variant == style.font_variant {
@@ -243,8 +255,7 @@ impl FontContext {
         }
 
         let font_group = Rc::new(FontGroup::new(fonts));
-        self.last_style = Some(style);
-        self.last_fontgroup = Some(font_group.clone());
+        self.layout_font_group_cache.insert(layout_font_group_cache_key, font_group.clone());
         font_group
     }
 
@@ -275,3 +286,34 @@ impl FontContext {
         self.font_cache_task.clone()
     }
 }
+
+struct LayoutFontGroupCacheKey {
+    pointer: Arc<SpecifiedFontStyle>,
+    size: Au,
+    address: usize,
+}
+
+impl PartialEq for LayoutFontGroupCacheKey {
+    fn eq(&self, other: &LayoutFontGroupCacheKey) -> bool {
+        self.pointer.font_family == other.pointer.font_family &&
+            self.pointer.font_stretch == other.pointer.font_stretch &&
+            self.pointer.font_style == other.pointer.font_style &&
+            self.pointer.font_weight as u16 == other.pointer.font_weight as u16 &&
+            self.size == other.size
+    }
+}
+
+impl Eq for LayoutFontGroupCacheKey {}
+
+impl Hash for LayoutFontGroupCacheKey {
+    fn hash<H>(&self, hasher: &mut H) where H: Hasher {
+        self.pointer.hash.hash(hasher)
+    }
+}
+
+impl borrow::Borrow<usize> for LayoutFontGroupCacheKey {
+    fn borrow(&self) -> &usize {
+        &self.address
+    }
+}
+
diff --git a/components/gfx/font_template.rs b/components/gfx/font_template.rs
index 736c8dfad41..50cf8c57fee 100644
--- a/components/gfx/font_template.rs
+++ b/components/gfx/font_template.rs
@@ -11,11 +11,11 @@ use std::borrow::ToOwned;
 use std::sync::{Arc, Weak};
 use style::computed_values::{font_stretch, font_weight};
 
-/// Describes how to select a font from a given family.
-/// This is very basic at the moment and needs to be
-/// expanded or refactored when we support more of the
-/// font styling parameters.
-#[derive(Clone, Copy)]
+/// Describes how to select a font from a given family. This is very basic at the moment and needs
+/// to be expanded or refactored when we support more of the font styling parameters.
+///
+/// NB: If you change this, you will need to update `style::properties::compute_font_hash()`.
+#[derive(Clone, Copy, Eq, Hash)]
 pub struct FontTemplateDescriptor {
     pub weight: font_weight::T,
     pub stretch: font_stretch::T,
diff --git a/components/gfx/lib.rs b/components/gfx/lib.rs
index 0be282fb8f6..e1183753d5e 100644
--- a/components/gfx/lib.rs
+++ b/components/gfx/lib.rs
@@ -35,6 +35,7 @@ extern crate net;
 #[macro_use]
 extern crate util;
 extern crate msg;
+extern crate string_cache;
 extern crate style;
 extern crate skia;
 extern crate time;
diff --git a/components/layout/layout_task.rs b/components/layout/layout_task.rs
index c61f84cf066..33bf00e837f 100644
--- a/components/layout/layout_task.rs
+++ b/components/layout/layout_task.rs
@@ -597,7 +597,7 @@ impl LayoutTask {
 
         if mq.evaluate(&rw_data.stylist.device) {
             iter_font_face_rules(&sheet, &rw_data.stylist.device, &|family, src| {
-                self.font_cache_task.add_web_font(family.to_owned(), (*src).clone());
+                self.font_cache_task.add_web_font((*family).clone(), (*src).clone());
             });
             rw_data.stylist.add_stylesheet(sheet);
         }
diff --git a/components/servo/Cargo.lock b/components/servo/Cargo.lock
index c7158c4239f..4183d8627e9 100644
--- a/components/servo/Cargo.lock
+++ b/components/servo/Cargo.lock
@@ -320,6 +320,7 @@ dependencies = [
  "script_traits 0.0.1",
  "skia 0.0.20130412 (git+https://github.com/servo/skia?branch=upstream-2014-06-16)",
  "stb_image 0.1.0 (git+https://github.com/servo/rust-stb-image)",
+ "string_cache 0.0.0 (git+https://github.com/servo/string-cache)",
  "style 0.0.1",
  "time 0.1.19 (registry+https://github.com/rust-lang/crates.io-index)",
  "url 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)",
diff --git a/components/style/font_face.rs b/components/style/font_face.rs
index f10d2a4fa95..0c661745fb5 100644
--- a/components/style/font_face.rs
+++ b/components/style/font_face.rs
@@ -2,18 +2,18 @@
  * 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/. */
 
+use computed_values::font_family::FontFamily;
 use cssparser::{Token, Parser, DeclarationListParser, AtRuleParser, DeclarationParser};
+use media_queries::Device;
+use parser::{ParserContext, log_css_error};
+use properties::longhands::font_family::parse_one_family;
 use std::ascii::AsciiExt;
+use string_cache::Atom;
 use stylesheets::CSSRule;
-use properties::longhands::font_family::parse_one_family;
-use computed_values::font_family::FontFamily;
-use media_queries::Device;
 use url::{Url, UrlParser};
-use parser::{ParserContext, log_css_error};
 
-
-pub fn iter_font_face_rules_inner<F>(rules: &[CSSRule], device: &Device,
-                                     callback: &F) where F: Fn(&str, &Source) {
+pub fn iter_font_face_rules_inner<F>(rules: &[CSSRule], device: &Device, callback: &F)
+                                     where F: Fn(&Atom, &Source) {
     for rule in rules.iter() {
         match *rule {
             CSSRule::Style(..) |
@@ -34,7 +34,7 @@ pub fn iter_font_face_rules_inner<F>(rules: &[CSSRule], device: &Device,
 #[derive(Clone, Debug, PartialEq, Eq)]
 pub enum Source {
     Url(UrlSource),
-    Local(String),
+    Local(Atom),
 }
 
 #[derive(Clone, Debug, PartialEq, Eq)]
@@ -45,11 +45,10 @@ pub struct UrlSource {
 
 #[derive(Debug, PartialEq, Eq)]
 pub struct FontFaceRule {
-    pub family: String,
+    pub family: Atom,
     pub sources: Vec<Source>,
 }
 
-
 pub fn parse_font_face_block(context: &ParserContext, input: &mut Parser)
                              -> Result<FontFaceRule, ()> {
     let mut family = None;
@@ -83,7 +82,7 @@ pub fn parse_font_face_block(context: &ParserContext, input: &mut Parser)
 }
 
 enum FontFaceDescriptorDeclaration {
-    Family(String),
+    Family(Atom),
     Src(Vec<Source>),
 }
 
@@ -106,7 +105,8 @@ impl<'a, 'b> DeclarationParser for FontFaceRuleParser<'a, 'b> {
     fn parse_value(&self, name: &str, input: &mut Parser) -> Result<FontFaceDescriptorDeclaration, ()> {
         match_ignore_ascii_case! { name,
             "font-family" => {
-                Ok(FontFaceDescriptorDeclaration::Family(try!(parse_one_non_generic_family_name(input))))
+                Ok(FontFaceDescriptorDeclaration::Family(try!(
+                            parse_one_non_generic_family_name(input))))
             },
             "src" => {
                 Ok(FontFaceDescriptorDeclaration::Src(try!(input.parse_comma_separated(|input| {
@@ -118,9 +118,9 @@ impl<'a, 'b> DeclarationParser for FontFaceRuleParser<'a, 'b> {
     }
 }
 
-fn parse_one_non_generic_family_name(input: &mut Parser) -> Result<String, ()> {
+fn parse_one_non_generic_family_name(input: &mut Parser) -> Result<Atom, ()> {
     match parse_one_family(input) {
-        Ok(FontFamily::FamilyName(name)) => Ok(name),
+        Ok(FontFamily::FamilyName(name)) => Ok(name.clone()),
         _ => Err(())
     }
 }
diff --git a/components/style/parser.rs b/components/style/parser.rs
index 6fd821f3435..c9d1891d708 100644
--- a/components/style/parser.rs
+++ b/components/style/parser.rs
@@ -10,7 +10,6 @@ use log;
 
 use stylesheets::Origin;
 
-
 pub struct ParserContext<'a> {
     pub base_url: &'a Url,
     pub selector_context: SelectorParserContext,
diff --git a/components/style/properties.mako.rs b/components/style/properties.mako.rs
index d0503a83786..fbe09ac4dd4 100644
--- a/components/style/properties.mako.rs
+++ b/components/style/properties.mako.rs
@@ -8,10 +8,13 @@
 
 use std::ascii::AsciiExt;
 use std::borrow::ToOwned;
+use std::default::Default;
 use std::fmt;
 use std::fmt::Debug;
+use std::hash::{Hash, Hasher};
 use std::sync::Arc;
 
+use util::fnv::FnvHasher;
 use util::logical_geometry::{WritingMode, LogicalMargin};
 use util::geometry::Au;
 use url::Url;
@@ -1456,18 +1459,20 @@ pub mod longhands {
     ${new_style_struct("Font", is_inherited=True)}
 
     <%self:longhand name="font-family">
-        use std::borrow::ToOwned;
         use self::computed_value::FontFamily;
+        use std::borrow::ToOwned;
+        use string_cache::Atom;
         use values::computed::ComputedValueAsSpecified;
 
         impl ComputedValueAsSpecified for SpecifiedValue {}
         pub mod computed_value {
             use cssparser::ToCss;
+            use string_cache::Atom;
             use text_writer::{self, TextWriter};
 
-            #[derive(PartialEq, Eq, Clone)]
+            #[derive(PartialEq, Eq, Clone, Hash)]
             pub enum FontFamily {
-                FamilyName(String),
+                FamilyName(Atom),
                 // Generic
 //                Serif,
 //                SansSerif,
@@ -1476,16 +1481,17 @@ pub mod longhands {
 //                Monospace,
             }
             impl FontFamily {
+                #[inline]
                 pub fn name(&self) -> &str {
                     match *self {
-                        FontFamily::FamilyName(ref name) => name,
+                        FontFamily::FamilyName(ref name) => name.as_slice(),
                     }
                 }
             }
             impl ToCss for FontFamily {
                 fn to_css<W>(&self, dest: &mut W) -> text_writer::Result where W: TextWriter {
                     match self {
-                        &FontFamily::FamilyName(ref name) => dest.write_str(&**name),
+                        &FontFamily::FamilyName(ref name) => dest.write_str(name.as_slice()),
                     }
                 }
             }
@@ -1506,7 +1512,7 @@ pub mod longhands {
 
         #[inline]
         pub fn get_initial_value() -> computed_value::T {
-            vec![FontFamily::FamilyName("serif".to_owned())]
+            vec![FontFamily::FamilyName(Atom::from_slice("serif"))]
         }
         /// <family-name>#
         /// <family-name> = <string> | [ <ident>+ ]
@@ -1516,7 +1522,7 @@ pub mod longhands {
         }
         pub fn parse_one_family(input: &mut Parser) -> Result<FontFamily, ()> {
             if let Ok(value) = input.try(|input| input.expect_string()) {
-                return Ok(FontFamily::FamilyName(value.into_owned()))
+                return Ok(FontFamily::FamilyName(Atom::from_slice(value.as_slice())))
             }
             let first_ident = try!(input.expect_ident());
 //            match_ignore_ascii_case! { first_ident,
@@ -1532,7 +1538,7 @@ pub mod longhands {
                 value.push_str(" ");
                 value.push_str(&ident);
             }
-            Ok(FontFamily::FamilyName(value))
+            Ok(FontFamily::FamilyName(Atom::from_slice(value.as_slice())))
         }
     </%self:longhand>
 
@@ -1592,10 +1598,10 @@ pub mod longhands {
         }
         pub mod computed_value {
             use std::fmt;
-            #[derive(PartialEq, Eq, Copy, Clone)]
+            #[derive(PartialEq, Eq, Copy, Clone, Hash)]
             pub enum T {
                 % for weight in range(100, 901, 100):
-                    Weight${weight},
+                    Weight${weight} = ${weight},
                 % endfor
             }
             impl fmt::Debug for T {
@@ -1608,6 +1614,7 @@ pub mod longhands {
                 }
             }
             impl T {
+                #[inline]
                 pub fn is_bold(self) -> bool {
                     match self {
                         T::Weight900 | T::Weight800 |
@@ -4663,6 +4670,9 @@ pub mod style_structs {
             % for longhand in style_struct.longhands:
                 pub ${longhand.ident}: longhands::${longhand.ident}::computed_value::T,
             % endfor
+            % if style_struct.name == "Font":
+                pub hash: u64,
+            % endif
         }
     % endfor
 }
@@ -4836,6 +4846,9 @@ lazy_static! {
                 % for longhand in style_struct.longhands:
                     ${longhand.ident}: longhands::${longhand.ident}::get_initial_value(),
                 % endfor
+                % if style_struct.name == "Font":
+                    hash: 0,
+                % endif
             }),
         % endfor
         shareable: true,
@@ -4932,6 +4945,11 @@ fn cascade_with_cached_declarations(
         }
     }
 
+    if seen.get_font_style() || seen.get_font_weight() || seen.get_font_stretch() ||
+            seen.get_font_family() {
+        compute_font_hash(&mut *style_font.make_unique())
+    }
+
     ComputedValues {
         writing_mode: get_writing_mode(&*style_inheritedbox),
         % for style_struct in STYLE_STRUCTS:
@@ -5180,6 +5198,11 @@ pub fn cascade(viewport_size: Size2D<Au>,
         context.root_font_size = context.font_size;
     }
 
+    if seen.get_font_style() || seen.get_font_weight() || seen.get_font_stretch() ||
+            seen.get_font_family() {
+        compute_font_hash(&mut *style_font.make_unique())
+    }
+
     (ComputedValues {
         writing_mode: get_writing_mode(&*style_inheritedbox),
         % for style_struct in STYLE_STRUCTS:
@@ -5297,3 +5320,13 @@ pub fn longhands_from_shorthand(shorthand: &str) -> Option<Vec<String>> {
         _ => None,
     }
 }
+
+/// Corresponds to the fields in `gfx::font_template::FontTemplateDescriptor`.
+fn compute_font_hash(font: &mut style_structs::Font) {
+    let mut hasher: FnvHasher = Default::default();
+    hasher.write_u16(font.font_weight as u16);
+    font.font_stretch.hash(&mut hasher);
+    font.font_family.hash(&mut hasher);
+    font.hash = hasher.finish()
+}
+
diff --git a/components/style/stylesheets.rs b/components/style/stylesheets.rs
index 1e7e78ac9cc..11135ac580e 100644
--- a/components/style/stylesheets.rs
+++ b/components/style/stylesheets.rs
@@ -318,8 +318,8 @@ pub fn iter_stylesheet_style_rules<F>(stylesheet: &Stylesheet, device: &media_qu
 
 
 #[inline]
-pub fn iter_font_face_rules<F>(stylesheet: &Stylesheet, device: &Device,
-                               callback: &F) where F: Fn(&str, &Source) {
+pub fn iter_font_face_rules<F>(stylesheet: &Stylesheet, device: &Device, callback: &F)
+                               where F: Fn(&Atom, &Source) {
     iter_font_face_rules_inner(&stylesheet.rules, device, callback)
 }
 
diff --git a/components/style/values.rs b/components/style/values.rs
index e26c37191a3..80801af930a 100644
--- a/components/style/values.rs
+++ b/components/style/values.rs
@@ -13,7 +13,7 @@ macro_rules! define_css_keyword_enum {
     };
     ($name: ident: $( $css: expr => $variant: ident ),+) => {
         #[allow(non_camel_case_types)]
-        #[derive(Clone, Eq, PartialEq, FromPrimitive, Copy)]
+        #[derive(Clone, Eq, PartialEq, FromPrimitive, Copy, Hash)]
         pub enum $name {
             $( $variant ),+
         }
diff --git a/ports/cef/Cargo.lock b/ports/cef/Cargo.lock
index bc0ed5a0da5..30adc00a7b4 100644
--- a/ports/cef/Cargo.lock
+++ b/ports/cef/Cargo.lock
@@ -325,6 +325,7 @@ dependencies = [
  "script_traits 0.0.1",
  "skia 0.0.20130412 (git+https://github.com/servo/skia?branch=upstream-2014-06-16)",
  "stb_image 0.1.0 (git+https://github.com/servo/rust-stb-image)",
+ "string_cache 0.0.0 (git+https://github.com/servo/string-cache)",
  "style 0.0.1",
  "time 0.1.19 (registry+https://github.com/rust-lang/crates.io-index)",
  "url 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)",
diff --git a/ports/gonk/Cargo.lock b/ports/gonk/Cargo.lock
index db31cfd8db0..0ee174dbc67 100644
--- a/ports/gonk/Cargo.lock
+++ b/ports/gonk/Cargo.lock
@@ -296,6 +296,7 @@ dependencies = [
  "script_traits 0.0.1",
  "skia 0.0.20130412 (git+https://github.com/servo/skia?branch=upstream-2014-06-16)",
  "stb_image 0.1.0 (git+https://github.com/servo/rust-stb-image)",
+ "string_cache 0.0.0 (git+https://github.com/servo/string-cache)",
  "style 0.0.1",
  "time 0.1.19 (registry+https://github.com/rust-lang/crates.io-index)",
  "url 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)",