1 /*
2 * Hash benchmark module
3 * Part of the xxHash project
4 * Copyright (C) 2019-2020 Yann Collet
5 *
6 * GPL v2 License
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program; if not, write to the Free Software Foundation, Inc.,
20 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 *
22 * You can contact the author at:
23 * - xxHash homepage: https://www.xxhash.com
24 * - xxHash source repository: https://github.com/Cyan4973/xxHash
25 */
26
27 /* benchmark hash functions */
28
29 #include <stdlib.h> // malloc
30 #include <assert.h>
31
32 #include "benchHash.h"
33
34
initBuffer(void * buffer,size_t size)35 static void initBuffer(void* buffer, size_t size)
36 {
37 const unsigned long long k1 = 11400714785074694791ULL; /* 0b1001111000110111011110011011000110000101111010111100101010000111 */
38 const unsigned long long k2 = 14029467366897019727ULL; /* 0b1100001010110010101011100011110100100111110101001110101101001111 */
39 unsigned long long acc = k2;
40 unsigned char* const p = (unsigned char*)buffer;
41 for (size_t s = 0; s < size; s++) {
42 acc *= k1;
43 p[s] = (unsigned char)(acc >> 56);
44 }
45 }
46
47
48 #define MARGIN_FOR_LATENCY 1024
49 #define START_MASK (MARGIN_FOR_LATENCY-1)
50
51 typedef size_t (*sizeFunction_f)(size_t targetSize);
52
53 /*
54 * bench_hash_internal():
55 * Benchmarks hashfn repeateadly over single input of size `size`
56 * return: nb of hashes per second
57 */
58 static double
bench_hash_internal(BMK_benchFn_t hashfn,void * payload,size_t nbBlocks,sizeFunction_f selectSize,size_t size,unsigned total_time_ms,unsigned iter_time_ms)59 bench_hash_internal(BMK_benchFn_t hashfn, void* payload,
60 size_t nbBlocks, sizeFunction_f selectSize, size_t size,
61 unsigned total_time_ms, unsigned iter_time_ms)
62 {
63 BMK_timedFnState_shell shell;
64 BMK_timedFnState_t* const txf = BMK_initStatic_timedFnState(&shell, sizeof(shell), total_time_ms, iter_time_ms);
65 assert(txf != NULL);
66
67 size_t const srcSize = (size_t)size;
68 size_t const srcBufferSize = srcSize + MARGIN_FOR_LATENCY;
69 void* const srcBuffer = malloc(srcBufferSize);
70 assert(srcBuffer != NULL);
71 initBuffer(srcBuffer, srcBufferSize);
72 #define FAKE_DSTSIZE 32
73 size_t const dstSize = FAKE_DSTSIZE;
74 char dstBuffer_static[FAKE_DSTSIZE] = {0};
75
76 #define NB_BLOCKS_MAX 1024
77 const void* srcBuffers[NB_BLOCKS_MAX];
78 size_t srcSizes[NB_BLOCKS_MAX];
79 void* dstBuffers[NB_BLOCKS_MAX];
80 size_t dstCapacities[NB_BLOCKS_MAX];
81 assert(nbBlocks < NB_BLOCKS_MAX);
82
83 assert(size > 0);
84 for (size_t n=0; n < nbBlocks; n++) {
85 srcBuffers[n] = srcBuffer;
86 srcSizes[n] = selectSize(size);
87 dstBuffers[n] = dstBuffer_static;
88 dstCapacities[n] = dstSize;
89 }
90
91
92 BMK_benchParams_t params = {
93 .benchFn = hashfn,
94 .benchPayload = payload,
95 .initFn = NULL,
96 .initPayload = NULL,
97 .errorFn = NULL,
98 .blockCount = nbBlocks,
99 .srcBuffers = srcBuffers,
100 .srcSizes = srcSizes,
101 .dstBuffers = dstBuffers,
102 .dstCapacities = dstCapacities,
103 .blockResults = NULL
104 };
105 BMK_runOutcome_t result;
106
107 while (!BMK_isCompleted_TimedFn(txf)) {
108 result = BMK_benchTimedFn(txf, params);
109 assert(BMK_isSuccessful_runOutcome(result));
110 }
111
112 BMK_runTime_t const runTime = BMK_extract_runTime(result);
113
114 free(srcBuffer);
115 assert(runTime.nanoSecPerRun != 0);
116 return (1000000000U / runTime.nanoSecPerRun) * nbBlocks;
117
118 }
119
120
rand_1_N(size_t N)121 static size_t rand_1_N(size_t N) { return ((size_t)rand() % N) + 1; }
122
identity(size_t s)123 static size_t identity(size_t s) { return s; }
124
125 static size_t
benchLatency(const void * src,size_t srcSize,void * dst,size_t dstCapacity,void * customPayload)126 benchLatency(const void* src, size_t srcSize,
127 void* dst, size_t dstCapacity,
128 void* customPayload)
129 {
130 (void)dst; (void)dstCapacity;
131 BMK_benchFn_t benchfn = (BMK_benchFn_t)customPayload;
132 static size_t hash = 0;
133
134 const void* const start = (const char*)src + (hash & START_MASK);
135
136 return hash = benchfn(start, srcSize, dst, dstCapacity, NULL);
137 }
138
139
140
141 #ifndef SIZE_TO_HASH_PER_ROUND
142 # define SIZE_TO_HASH_PER_ROUND 200000
143 #endif
144
145 #ifndef NB_HASH_ROUNDS_MAX
146 # define NB_HASH_ROUNDS_MAX 1000
147 #endif
148
bench_hash(BMK_benchFn_t hashfn,BMK_benchMode benchMode,size_t size,BMK_sizeMode sizeMode,unsigned total_time_ms,unsigned iter_time_ms)149 double bench_hash(BMK_benchFn_t hashfn,
150 BMK_benchMode benchMode,
151 size_t size, BMK_sizeMode sizeMode,
152 unsigned total_time_ms, unsigned iter_time_ms)
153 {
154 sizeFunction_f const sizef = (sizeMode == BMK_fixedSize) ? identity : rand_1_N;
155 BMK_benchFn_t const benchfn = (benchMode == BMK_throughput) ? hashfn : benchLatency;
156 BMK_benchFn_t const payload = (benchMode == BMK_throughput) ? NULL : hashfn;
157
158 size_t nbBlocks = (SIZE_TO_HASH_PER_ROUND / size) + 1;
159 if (nbBlocks > NB_HASH_ROUNDS_MAX) nbBlocks = NB_HASH_ROUNDS_MAX;
160
161 return bench_hash_internal(benchfn, payload,
162 nbBlocks, sizef, size,
163 total_time_ms, iter_time_ms);
164 }
165