1 use std::hash::{Hash, Hasher};
2
3 use criterion::*;
4 use fxhash::FxHasher;
5
6 use ahash::{AHasher, CallHasher};
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<T: Hasher>(hasher: impl Fn() -> T)122 fn test_hash_common_words<T: Hasher>(hasher: impl Fn() -> T) {
123 let word_pairs: Vec<_> = gen_word_pairs();
124 check_for_collisions(&hasher, &word_pairs, 32);
125 }
126
127 #[allow(unused)] // False positive
check_for_collisions<T: Hasher, H: Hash>(hasher: &impl Fn() -> T, items: &[H], bucket_count: usize)128 fn check_for_collisions<T: Hasher, H: Hash>(hasher: &impl Fn() -> T, items: &[H], bucket_count: usize) {
129 let mut buckets = vec![0; bucket_count];
130 for item in items {
131 let value = hash(item, &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<T: Hasher>(b: &impl Hash, hasher: &dyn Fn() -> T) -> u64154 fn hash<T: Hasher>(b: &impl Hash, hasher: &dyn Fn() -> T) -> u64 {
155 let hasher = hasher();
156 b.get_hash(hasher)
157 }
158
159 #[test]
test_bucket_distribution()160 fn test_bucket_distribution() {
161 let hasher = || AHasher::new_with_keys(123456789, 987654321);
162 test_hash_common_words(&hasher);
163 let sequence: Vec<_> = (0..320000).collect();
164 check_for_collisions(&hasher, &sequence, 32);
165 let sequence: Vec<_> = (0..2560000).collect();
166 check_for_collisions(&hasher, &sequence, 256);
167 let sequence: Vec<_> = (0..320000).map(|i| i * 1024).collect();
168 check_for_collisions(&hasher, &sequence, 32);
169 let sequence: Vec<_> = (0..2560000_u64).map(|i| i * 1024).collect();
170 check_for_collisions(&hasher, &sequence, 256);
171 }
172
ahash_vec<H: Hash>(b: &Vec<H>) -> u64173 fn ahash_vec<H: Hash>(b: &Vec<H>) -> u64 {
174 let mut total: u64 = 0;
175 for item in b {
176 let mut hasher = AHasher::new_with_keys(1234, 5678);
177 item.hash(&mut hasher);
178 total = total.wrapping_add(hasher.finish());
179 }
180 total
181 }
182
fxhash_vec<H: Hash>(b: &Vec<H>) -> u64183 fn fxhash_vec<H: Hash>(b: &Vec<H>) -> u64 {
184 let mut total: u64 = 0;
185 for item in b {
186 let mut hasher = FxHasher::default();
187 item.hash(&mut hasher);
188 total = total.wrapping_add(hasher.finish());
189 }
190 total
191 }
192
bench_ahash_words(c: &mut Criterion)193 fn bench_ahash_words(c: &mut Criterion) {
194 let words = gen_word_pairs();
195 c.bench_function("aes_words", |b| b.iter(|| black_box(ahash_vec(&words))));
196 }
197
bench_fx_words(c: &mut Criterion)198 fn bench_fx_words(c: &mut Criterion) {
199 let words = gen_word_pairs();
200 c.bench_function("fx_words", |b| b.iter(|| black_box(fxhash_vec(&words))));
201 }
202
203 criterion_main!(benches);
204 criterion_group!(benches, bench_ahash_words, bench_fx_words,);
205