bevy_ecs/entity/
hash.rs

1use core::hash::{BuildHasher, Hasher};
2
3#[cfg(feature = "bevy_reflect")]
4use bevy_reflect::{std_traits::ReflectDefault, Reflect};
5
6/// A [`BuildHasher`] that results in a [`EntityHasher`].
7#[derive(Debug, Default, Clone)]
8#[cfg_attr(feature = "bevy_reflect", derive(Reflect), reflect(Default, Clone))]
9pub struct EntityHash;
10
11impl BuildHasher for EntityHash {
12    type Hasher = EntityHasher;
13
14    #[inline]
15    fn build_hasher(&self) -> Self::Hasher {
16        Self::Hasher::default()
17    }
18}
19
20/// A very fast hash that is only designed to work on generational indices
21/// like [`Entity`](super::Entity). It will panic if attempting to hash a type containing
22/// non-u64 fields.
23///
24/// This is heavily optimized for typical cases, where you have mostly live
25/// entities, and works particularly well for contiguous indices.
26///
27/// If you have an unusual case -- say all your indices are multiples of 256
28/// or most of the entities are dead generations -- then you might want also to
29/// try [`DefaultHasher`](bevy_platform::hash::DefaultHasher) for a slower hash
30/// computation but fewer lookup conflicts.
31#[derive(Debug, Default)]
32pub struct EntityHasher {
33    hash: u64,
34}
35
36impl Hasher for EntityHasher {
37    #[inline]
38    fn finish(&self) -> u64 {
39        self.hash
40    }
41
42    fn write(&mut self, _bytes: &[u8]) {
43        panic!("EntityHasher can only hash u64 fields.");
44    }
45
46    #[inline]
47    fn write_u64(&mut self, bits: u64) {
48        // SwissTable (and thus `hashbrown`) cares about two things from the hash:
49        // - H1: low bits (masked by `2ⁿ-1`) to pick the slot in which to store the item
50        // - H2: high 7 bits are used to SIMD optimize hash collision probing
51        // For more see <https://abseil.io/about/design/swisstables#metadata-layout>
52
53        // This hash function assumes that the entity ids are still well-distributed,
54        // so for H1 leaves the entity id alone in the low bits so that id locality
55        // will also give memory locality for things spawned together.
56        // For H2, take advantage of the fact that while multiplication doesn't
57        // spread entropy to the low bits, it's incredibly good at spreading it
58        // upward, which is exactly where we need it the most.
59
60        // While this does include the generation in the output, it doesn't do so
61        // *usefully*.  H1 won't care until you have over 3 billion entities in
62        // the table, and H2 won't care until something hits generation 33 million.
63        // Thus the comment suggesting that this is best for live entities,
64        // where there won't be generation conflicts where it would matter.
65
66        // The high 32 bits of this are ⅟φ for Fibonacci hashing.  That works
67        // particularly well for hashing for the same reason as described in
68        // <https://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/>
69        // It loses no information because it has a modular inverse.
70        // (Specifically, `0x144c_bc89_u32 * 0x9e37_79b9_u32 == 1`.)
71        //
72        // The low 32 bits make that part of the just product a pass-through.
73        const UPPER_PHI: u64 = 0x9e37_79b9_0000_0001;
74
75        // This is `(MAGIC * index + generation) << 32 + index`, in a single instruction.
76        self.hash = bits.wrapping_mul(UPPER_PHI);
77    }
78}
bevy_ecs/entity/hash.rs

bevy_ecs/entity/
hash.rs
