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