1 #![cfg_attr(feature = "specialize", feature(build_hasher_simple_hash_one))]
2
3 use std::hash::{BuildHasher, Hash, Hasher};
4
5 use ahash::RandomState;
6 use criterion::*;
7 use fxhash::FxHasher;
8
gen_word_pairs() -> Vec<String>9 fn gen_word_pairs() -> Vec<String> {
10 let words: Vec<_> = r#"
11 a, ability, able, about, above, accept, according, account, across, act, action,
12 activity, actually, add, address, administration, admit, adult, affect, after,
13 again, against, age, agency, agent, ago, agree, agreement, ahead, air, all,
14 allow, almost, alone, along, already, also, although, always, American, among,
15 amount, analysis, and, animal, another, answer, any, anyone, anything, appear,
16 apply, approach, area, argue, arm, around, arrive, art, article, artist, as,
17 ask, assume, at, attack, attention, attorney, audience, author, authority,
18 available, avoid, away, baby, back, bad, bag, ball, bank, bar, base, be, beat,
19 beautiful, because, become, bed, before, begin, behavior, behind, believe,
20 benefit, best, better, between, beyond, big, bill, billion, bit, black, blood,
21 blue, board, body, book, born, both, box, boy, break, bring, brother, budget,
22 build, building, business, but, buy, by, call, camera, campaign, can, cancer,
23 candidate, capital, car, card, care, career, carry, case, catch, cause, cell,
24 center, central, century, certain, certainly, chair, challenge, chance, change,
25 character, charge, check, child, choice, choose, church, citizen, city, civil,
26 claim, class, clear, clearly, close, coach, cold, collection, college, color,
27 come, commercial, common, community, company, compare, computer, concern,
28 condition, conference, Congress, consider, consumer, contain, continue, control,
29 cost, could, country, couple, course, court, cover, create, crime, cultural,
30 culture, cup, current, customer, cut, dark, data, daughter, day, dead, deal,
31 death, debate, decade, decide, decision, deep, defense, degree, Democrat,
32 democratic, describe, design, despite, detail, determine, develop, development,
33 die, difference, different, difficult, dinner, direction, director, discover,
34 discuss, discussion, disease, do, doctor, dog, door, down, draw, dream, drive,
35 drop, drug, during, each, early, east, easy, eat, economic, economy, edge,
36 education, effect, effort, eight, either, election, else, employee, end, energy,
37 enjoy, enough, enter, entire, environment, environmental, especially, establish,
38 even, evening, event, ever, every, everybody, everyone, everything, evidence,
39 exactly, example, executive, exist, expect, experience, expert, explain, eye,
40 face, fact, factor, fail, fall, family, far, fast, father, fear, federal, feel,
41 feeling, few, field, fight, figure, fill, film, final, finally, financial, find,
42 fine, finger, finish, fire, firm, first, fish, five, floor, fly, focus, follow,
43 food, foot, for, force, foreign, forget, form, former, forward, four, free,
44 friend, from, front, full, fund, future, game, garden, gas, general, generation,
45 get, girl, give, glass, go, goal, good, government, great, green, ground, group,
46 grow, growth, guess, gun, guy, hair, half, hand, hang, happen, happy, hard,
47 have, he, head, health, hear, heart, heat, heavy, help, her, here, herself,
48 high, him, himself, his, history, hit, hold, home, hope, hospital, hot, hotel,
49 hour, house, how, however, huge, human, hundred, husband, I, idea, identify, if,
50 image, imagine, impact, important, improve, in, include, including, increase,
51 indeed, indicate, individual, industry, information, inside, instead,
52 institution, interest, interesting, international, interview, into, investment,
53 involve, issue, it, item, its, itself, job, join, just, keep, key, kid, kill,
54 kind, kitchen, know, knowledge, land, language, large, last, late, later, laugh,
55 law, lawyer, lay, lead, leader, learn, least, leave, left, leg, legal, less,
56 let, letter, level, lie, life, light, like, likely, line, list, listen, little,
57 live, local, long, look, lose, loss, lot, love, low, machine, magazine, main,
58 maintain, major, majority, make, man, manage, management, manager, many, market,
59 marriage, material, matter, may, maybe, me, mean, measure, media, medical, meet,
60 meeting, member, memory, mention, message, method, middle, might, military,
61 million, mind, minute, miss, mission, model, modern, moment, money, month, more,
62 morning, most, mother, mouth, move, movement, movie, Mr, Mrs, much, music, must,
63 my, myself, name, nation, national, natural, nature, near, nearly, necessary,
64 need, network, never, new, news, newspaper, next, nice, night, no, none, nor,
65 north, not, note, nothing, notice, now, n't, number, occur, of, off, offer,
66 office, officer, official, often, oh, oil, ok, old, on, once, one, only, onto,
67 open, operation, opportunity, option, or, order, organization, other, others,
68 our, out, outside, over, own, owner, page, pain, painting, paper, parent, part,
69 participant, particular, particularly, partner, party, pass, past, patient,
70 pattern, pay, peace, people, per, perform, performance, perhaps, period, person,
71 personal, phone, physical, pick, picture, piece, place, plan, plant, play,
72 player, PM, point, police, policy, political, politics, poor, popular,
73 population, position, positive, possible, power, practice, prepare, present,
74 president, pressure, pretty, prevent, price, private, probably, problem,
75 process, produce, product, production, professional, professor, program,
76 project, property, protect, prove, provide, public, pull, purpose, push, put,
77 quality, question, quickly, quite, race, radio, raise, range, rate, rather,
78 reach, read, ready, real, reality, realize, really, reason, receive, recent,
79 recently, recognize, record, red, reduce, reflect, region, relate, relationship,
80 religious, remain, remember, remove, report, represent, Republican, require,
81 research, resource, respond, response, responsibility, rest, result, return,
82 reveal, rich, right, rise, risk, road, rock, role, room, rule, run, safe, same,
83 save, say, scene, school, science, scientist, score, sea, season, seat, second,
84 section, security, see, seek, seem, sell, send, senior, sense, series, serious,
85 serve, service, set, seven, several, sex, sexual, shake, share, she, shoot,
86 short, shot, should, shoulder, show, side, sign, significant, similar, simple,
87 simply, since, sing, single, sister, sit, site, situation, six, size, skill,
88 skin, small, smile, so, social, society, soldier, some, somebody, someone,
89 something, sometimes, son, song, soon, sort, sound, source, south, southern,
90 space, speak, special, specific, speech, spend, sport, spring, staff, stage,
91 stand, standard, star, start, state, statement, station, stay, step, still,
92 stock, stop, store, story, strategy, street, strong, structure, student, study,
93 stuff, style, subject, success, successful, such, suddenly, suffer, suggest,
94 summer, support, sure, surface, system, table, take, talk, task, tax, teach,
95 teacher, team, technology, television, tell, ten, tend, term, test, than, thank,
96 that, the, their, them, themselves, then, theory, there, these, they, thing,
97 think, third, this, those, though, thought, thousand, threat, three, through,
98 throughout, throw, thus, time, to, today, together, tonight, too, top, total,
99 tough, toward, town, trade, traditional, training, travel, treat, treatment,
100 tree, trial, trip, trouble, true, truth, try, turn, TV, two, type, under,
101 understand, unit, until, up, upon, us, use, usually, value, various, very,
102 victim, view, violence, visit, voice, vote, wait, walk, wall, want, war, watch,
103 water, way, we, weapon, wear, week, weight, well, west, western, what, whatever,
104 when, where, whether, which, while, white, who, whole, whom, whose, why, wide,
105 wife, will, win, wind, window, wish, with, within, without, woman, wonder, word,
106 work, worker, world, worry, would, write, writer, wrong, yard, yeah, year, yes,
107 yet, you, young, your, yourself"#
108 .split(',')
109 .map(|word| word.trim())
110 .collect();
111
112 let mut word_pairs: Vec<_> = Vec::new();
113 for word in &words {
114 for other_word in &words {
115 word_pairs.push(word.to_string() + " " + other_word);
116 }
117 }
118 assert_eq!(1_000_000, word_pairs.len());
119 word_pairs
120 }
121
122 #[allow(unused)] // False positive
test_hash_common_words<B: BuildHasher>(build_hasher: &B)123 fn test_hash_common_words<B: BuildHasher>(build_hasher: &B) {
124 let word_pairs: Vec<_> = gen_word_pairs();
125 check_for_collisions(build_hasher, &word_pairs, 32);
126 }
127
128 #[allow(unused)] // False positive
check_for_collisions<H: Hash, B: BuildHasher>(build_hasher: &B, items: &[H], bucket_count: usize)129 fn check_for_collisions<H: Hash, B: BuildHasher>(build_hasher: &B, items: &[H], bucket_count: usize) {
130 let mut buckets = vec![0; bucket_count];
131 for item in items {
132 let value = hash(item, build_hasher) as usize;
133 buckets[value % bucket_count] += 1;
134 }
135 let mean = items.len() / bucket_count;
136 let max = *buckets.iter().max().unwrap();
137 let min = *buckets.iter().min().unwrap();
138 assert!(
139 (min as f64) > (mean as f64) * 0.95,
140 "min: {}, max:{}, {:?}",
141 min,
142 max,
143 buckets
144 );
145 assert!(
146 (max as f64) < (mean as f64) * 1.05,
147 "min: {}, max:{}, {:?}",
148 min,
149 max,
150 buckets
151 );
152 }
153
154 #[cfg(feature = "specialize")]
155 #[allow(unused)] // False positive
hash<H: Hash, B: BuildHasher>(b: &H, build_hasher: &B) -> u64156 fn hash<H: Hash, B: BuildHasher>(b: &H, build_hasher: &B) -> u64 {
157 build_hasher.hash_one(b)
158 }
159
160 #[cfg(not(feature = "specialize"))]
161 #[allow(unused)] // False positive
hash<H: Hash, B: BuildHasher>(b: &H, build_hasher: &B) -> u64162 fn hash<H: Hash, B: BuildHasher>(b: &H, build_hasher: &B) -> u64 {
163 let mut hasher = build_hasher.build_hasher();
164 b.hash(&mut hasher);
165 hasher.finish()
166 }
167
168 #[test]
test_bucket_distribution()169 fn test_bucket_distribution() {
170 let build_hasher = RandomState::with_seeds(1, 2, 3, 4);
171 test_hash_common_words(&build_hasher);
172 let sequence: Vec<_> = (0..320000).collect();
173 check_for_collisions(&build_hasher, &sequence, 32);
174 let sequence: Vec<_> = (0..2560000).collect();
175 check_for_collisions(&build_hasher, &sequence, 256);
176 let sequence: Vec<_> = (0..320000).map(|i| i * 1024).collect();
177 check_for_collisions(&build_hasher, &sequence, 32);
178 let sequence: Vec<_> = (0..2560000_u64).map(|i| i * 1024).collect();
179 check_for_collisions(&build_hasher, &sequence, 256);
180 }
181
182 #[cfg(feature = "std")]
183 #[test]
test_ahash_alias_map_construction()184 fn test_ahash_alias_map_construction() {
185 let mut map = ahash::HashMap::default();
186 map.insert(1, "test");
187 use ahash::HashMapExt;
188 let mut map = ahash::HashMap::with_capacity(1234);
189 map.insert(1, "test");
190 }
191
192 #[cfg(feature = "std")]
193 #[test]
test_ahash_alias_set_construction()194 fn test_ahash_alias_set_construction() {
195 let mut set = ahash::HashSet::default();
196 set.insert(1);
197
198 use ahash::HashSetExt;
199 let mut set = ahash::HashSet::with_capacity(1235);
200 set.insert(1);
201 }
202
203
204 #[cfg(feature = "std")]
205 #[test]
test_key_ref()206 fn test_key_ref() {
207 let mut map = ahash::HashMap::default();
208 map.insert(1, "test");
209 assert_eq!(Some((1, "test")), map.remove_entry(&1));
210
211 let mut map = ahash::HashMap::default();
212 map.insert(&1, "test");
213 assert_eq!(Some((&1, "test")), map.remove_entry(&&1));
214
215 let mut m = ahash::HashSet::<Box<String>>::default();
216 m.insert(Box::from("hello".to_string()));
217 assert!(m.contains(&"hello".to_string()));
218
219 let mut m = ahash::HashSet::<String>::default();
220 m.insert("hello".to_string());
221 assert!(m.contains("hello"));
222
223 let mut m = ahash::HashSet::<Box<[u8]>>::default();
224 m.insert(Box::from(&b"hello"[..]));
225 assert!(m.contains(&b"hello"[..]));
226 }
227
228 #[cfg(feature = "std")]
229 #[test]
test_byte_dist()230 fn test_byte_dist() {
231 use rand::{SeedableRng, Rng, RngCore};
232 use pcg_mwc::Mwc256XXA64;
233
234 let mut r = Mwc256XXA64::seed_from_u64(0xe786_c22b_119c_1479);
235 let mut lowest = 2.541;
236 let mut highest = 2.541;
237 for _round in 0..100 {
238 let mut table: [bool; 256 * 8] = [false; 256 * 8];
239 let hasher = RandomState::with_seeds(r.gen(), r.gen(), r.gen(), r.gen());
240 for i in 0..128 {
241 let mut keys: [u8; 8] = hasher.hash_one((i as u64) << 30).to_ne_bytes();
242 //let mut keys = r.next_u64().to_ne_bytes(); //This is a control to test assert sensitivity.
243 for idx in 0..8 {
244 while table[idx * 256 + keys[idx] as usize] {
245 keys[idx] = keys[idx].wrapping_add(1);
246 }
247 table[idx * 256 + keys[idx] as usize] = true;
248 }
249 }
250
251 for idx in 0..8 {
252 let mut len = 0;
253 let mut total_len = 0;
254 let mut num_seq = 0;
255 for i in 0..256 {
256 if table[idx * 256 + i] {
257 len += 1;
258 } else if len != 0 {
259 num_seq += 1;
260 total_len += len;
261 len = 0;
262 }
263 }
264 let mean = total_len as f32 / num_seq as f32;
265 println!("Mean sequence length = {}", mean);
266 if mean > highest {
267 highest = mean;
268 }
269 if mean < lowest {
270 lowest = mean;
271 }
272 }
273 }
274 assert!(lowest > 1.9, "Lowest = {}", lowest);
275 assert!(highest < 3.9, "Highest = {}", highest);
276 }
277
278
ahash_vec<H: Hash>(b: &Vec<H>) -> u64279 fn ahash_vec<H: Hash>(b: &Vec<H>) -> u64 {
280 let mut total: u64 = 0;
281 for item in b {
282 let mut hasher = RandomState::with_seeds(12, 34, 56, 78).build_hasher();
283 item.hash(&mut hasher);
284 total = total.wrapping_add(hasher.finish());
285 }
286 total
287 }
288
fxhash_vec<H: Hash>(b: &Vec<H>) -> u64289 fn fxhash_vec<H: Hash>(b: &Vec<H>) -> u64 {
290 let mut total: u64 = 0;
291 for item in b {
292 let mut hasher = FxHasher::default();
293 item.hash(&mut hasher);
294 total = total.wrapping_add(hasher.finish());
295 }
296 total
297 }
298
bench_ahash_words(c: &mut Criterion)299 fn bench_ahash_words(c: &mut Criterion) {
300 let words = gen_word_pairs();
301 c.bench_function("aes_words", |b| b.iter(|| black_box(ahash_vec(&words))));
302 }
303
bench_fx_words(c: &mut Criterion)304 fn bench_fx_words(c: &mut Criterion) {
305 let words = gen_word_pairs();
306 c.bench_function("fx_words", |b| b.iter(|| black_box(fxhash_vec(&words))));
307 }
308
309 criterion_main!(benches);
310 criterion_group!(benches, bench_ahash_words, bench_fx_words,);
311