cc: Optimize the tile map key hash for 4-byte size_t.

This patch changes the hash function for the tile map key to use
16 least significant bits from each index. This makes it faster on
systems where sizeof(size_t) == 4.

The collisions would only start happening after a large enough index.

This makes the TilingSetRasterQueueConstructAndIterate test do
about 10% more iterations per second on N4.

BUG=488636
R=enne, danakj

Review URL: https://codereview.chromium.org/1133243010

Cr-Commit-Position: refs/heads/master@{#330448}

2 files changed, 46 insertions, 18 deletions

diff --git a/cc/tiles/picture_layer_tiling.cc b/cc/tiles/picture_layer_tiling.cc
index 8eb7530..8db2352 100644
--- a/cc/tiles/picture_layer_tiling.cc
+++ b/cc/tiles/picture_layer_tiling.cc
@@ -121,13 +121,13 @@ void PictureLayerTiling::CreateMissingTilesInLiveTilesRect() {
   for (TilingData::Iterator iter(&tiling_data_, live_tiles_rect_,
                                  include_borders);
        iter; ++iter) {
-    TileMapKey key = iter.index();
+    TileMapKey key(iter.index());
     TileMap::iterator find = tiles_.find(key);
     if (find != tiles_.end())
       continue;
 
-    if (ShouldCreateTileAt(key.first, key.second))
-      CreateTile(key.first, key.second);
+    if (ShouldCreateTileAt(key.index_x, key.index_y))
+      CreateTile(key.index_x, key.index_y);
   }
   VerifyLiveTilesRect(false);
 }
@@ -286,13 +286,13 @@ void PictureLayerTiling::RemoveTilesInRegion(const Region& layer_invalidation,
         iter; ++iter) {
       if (RemoveTileAt(iter.index_x(), iter.index_y())) {
         if (recreate_tiles)
-          new_tile_keys.push_back(iter.index());
+          new_tile_keys.push_back(TileMapKey(iter.index()));
       }
     }
   }
 
   for (const auto& key : new_tile_keys)
-    CreateTile(key.first, key.second);
+    CreateTile(key.index_x, key.index_y);
 }
 
 bool PictureLayerTiling::ShouldCreateTileAt(int i, int j) const {
@@ -658,8 +658,8 @@ void PictureLayerTiling::SetLiveTilesRect(
                                            live_tiles_rect_);
        iter; ++iter) {
     TileMapKey key(iter.index());
-    if (ShouldCreateTileAt(key.first, key.second))
-      CreateTile(key.first, key.second);
+    if (ShouldCreateTileAt(key.index_x, key.index_y))
+      CreateTile(key.index_x, key.index_y);
   }
 
   live_tiles_rect_ = new_live_tiles_rect;
@@ -671,19 +671,19 @@ void PictureLayerTiling::VerifyLiveTilesRect(bool is_on_recycle_tree) const {
   for (auto it = tiles_.begin(); it != tiles_.end(); ++it) {
     if (!it->second)
       continue;
-    DCHECK(it->first.first < tiling_data_.num_tiles_x())
-        << this << " " << it->first.first << "," << it->first.second
-        << " num_tiles_x " << tiling_data_.num_tiles_x() << " live_tiles_rect "
+    TileMapKey key = it->first;
+    DCHECK(key.index_x < tiling_data_.num_tiles_x())
+        << this << " " << key.index_x << "," << key.index_y << " num_tiles_x "
+        << tiling_data_.num_tiles_x() << " live_tiles_rect "
         << live_tiles_rect_.ToString();
-    DCHECK(it->first.second < tiling_data_.num_tiles_y())
-        << this << " " << it->first.first << "," << it->first.second
-        << " num_tiles_y " << tiling_data_.num_tiles_y() << " live_tiles_rect "
+    DCHECK(key.index_y < tiling_data_.num_tiles_y())
+        << this << " " << key.index_x << "," << key.index_y << " num_tiles_y "
+        << tiling_data_.num_tiles_y() << " live_tiles_rect "
         << live_tiles_rect_.ToString();
-    DCHECK(tiling_data_.TileBounds(it->first.first, it->first.second)
+    DCHECK(tiling_data_.TileBounds(key.index_x, key.index_y)
                .Intersects(live_tiles_rect_))
-        << this << " " << it->first.first << "," << it->first.second
-        << " tile bounds "
-        << tiling_data_.TileBounds(it->first.first, it->first.second).ToString()
+        << this << " " << key.index_x << "," << key.index_y << " tile bounds "
+        << tiling_data_.TileBounds(key.index_x, key.index_y).ToString()
         << " live_tiles_rect " << live_tiles_rect_.ToString();
   }
 #endif
diff --git a/cc/tiles/picture_layer_tiling.h b/cc/tiles/picture_layer_tiling.h
index 8af4c4c..2077afc 100644
--- a/cc/tiles/picture_layer_tiling.h
+++ b/cc/tiles/picture_layer_tiling.h
@@ -52,6 +52,35 @@ class CC_EXPORT PictureLayerTilingClient {
   virtual ~PictureLayerTilingClient() {}
 };
 
+struct TileMapKey {
+  TileMapKey(int x, int y) : index_x(x), index_y(y) {}
+  explicit TileMapKey(const std::pair<int, int>& index)
+      : index_x(index.first), index_y(index.second) {}
+
+  bool operator==(const TileMapKey& other) const {
+    return index_x == other.index_x && index_y == other.index_y;
+  }
+
+  int index_x;
+  int index_y;
+};
+
+}  // namespace cc
+
+namespace BASE_HASH_NAMESPACE {
+template <>
+struct hash<cc::TileMapKey> {
+  size_t operator()(const cc::TileMapKey& key) const {
+    uint16 value1 = static_cast<uint16>(key.index_x);
+    uint16 value2 = static_cast<uint16>(key.index_y);
+    uint32 value1_32 = value1;
+    return (value1_32 << 16) | value2;
+  }
+};
+}  // namespace BASE_HASH_NAMESPACE
+
+namespace cc {
+
 class CC_EXPORT PictureLayerTiling {
  public:
   static const int kBorderTexels = 1;
@@ -225,7 +254,6 @@ class CC_EXPORT PictureLayerTiling {
     EVENTUALLY_RECT
   };
 
-  using TileMapKey = std::pair<int, int>;
   using TileMap = base::ScopedPtrHashMap<TileMapKey, ScopedTilePtr>;
 
   struct FrameVisibleRect {