robin_hood_map.h | Explore in Territory

// Copyright 2023 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/351564777): Remove this and convert code to safer constructs.
#pragma allow_unsafe_buffers
#endif

#ifndef THIRD_PARTY_BLINK_RENDERER_CORE_CSS_ROBIN_HOOD_MAP_H_
#define THIRD_PARTY_BLINK_RENDERER_CORE_CSS_ROBIN_HOOD_MAP_H_

#include <memory>
#include <type_traits>

#include "base/compiler_specific.h"
#include "third_party/blink/renderer/platform/wtf/text/atomic_string.h"

namespace blink {

// Since RuleMap is so performance-critical for us (a large part of style
// is looking up rules in RuleMaps, especially since we have one RuleSet per
// stylesheet and one RuleSet has many RuleMaps), we have implemented our own
// hash table, which gives better lookup performance than WTF::HashMap,
// especially on cache-starved CPUs. We pay for this with some extra code
// and slightly more expensive inserts (and we also don't support deletes,
// although that could be added). The key features of our implementation are:
//
//  - Partition bucketing: No divide/modulo required, only a single 32x32
//    multiplication and shift to map the hash value to a bucket.
//    (This technique was popularized by Daniel Lemire.)
//
//  - Supports any table size (not restricted to power-of-two or prime),
//    due to the above.
//
//  - Open addressing with Robin Hood hashing and a bounded number of probes
//    (based on an idea by Malte Skarupte); makes lookup always O(1),
//    accessing at most three (neighboring) cache lines (assuming 16-byte
//    buckets), typically inlined and unrolled by the compiler.
//
//  - Inline data (not node-based); few allocations, no extra cache misses
//    after finding the element.
//
//  - High density due to Robin Hood hashing; small maps have almost 100%
//    load factor, whereas larger ones tend to go towards 60% or so.
//    No rehashing based solely on load factor; only violating the maximum
//    probe length will cause one.
//
//  - Not robust towards adversary cache collisions; if someone deliberately
//    introduces lots of AtomicStrings with the exact same hash value,
//    the insert will fail. (This of course isn't ideal, but it's a direct
//    consequence of the O(1) lookup bound, and is extremely unlikely
//    to happen on non-adversary data. Based on simulations with random
//    strings and 256k inserts, which is the maximum RuleData supports,
//    we estimate the odds of a 9-collision are very roughly 1 in 2e14.
//    Of course, if you lower kPossibleBucketsPerKey to e.g. 4, you'll
//    only need a 5-collision, which is _much_ more likely.)
//
// Possible future extensions:
//
//  - Arbitrary keys (currently supports only AtomicString as key).
//
//  - Using a HeapVector instead of a regular array, allowing to store Oilpan
//    objects as values without using Persistent<> (note that WTF::HashMap
//    only supports Oilpan objects using Member<>, not directly).
//
//  - Full STL-like or WTF-like interface: Better iterators, removals, etc.
//
//  - Packed buckets, to avoid extraneous padding and save yet more cache/RAM
//    (depending, of course, on Value).
template <class Key, class Value>
struct RobinHoodMap { … };

}  // namespace blink

#endif  // THIRD_PARTY_BLINK_RENDERER_CORE_CSS_ROBIN_HOOD_MAP_H_
chromium/third_party/blink/renderer/core/css/robin_hood_map.h
