1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3 * Copyright 2017 Couchbase, Inc.
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 #include "items.h"
19 #include "assoc.h"
20
21 #include <benchmark/benchmark.h>
22 #include <platform/cb_malloc.h>
23 #include <platform/crc32c.h>
24 #include <random>
25
26 const uint32_t max_items = 100000;
27
item_get_key(const hash_item* item)28 hash_key* item_get_key(const hash_item* item) {
29 const char *ret = reinterpret_cast<const char*>(item + 1);
30 return (hash_key*)ret;
31 }
32
hash_key_create(hash_key* hkey, uint32_t ii)33 static void hash_key_create(hash_key* hkey, uint32_t ii) {
34 char key[10];
35 auto nkey = snprintf(key, sizeof(key), "%08" PRIu32, ii);
36 auto hash_key_len = sizeof(bucket_id_t) + nkey;
37
38 if (size_t(nkey) > sizeof(hkey->key_storage.client_key)) {
39 hkey->header.full_key =
40 static_cast<hash_key_data*>(cb_malloc(hash_key_len));
41 if (hkey->header.full_key == NULL) {
42 throw std::bad_alloc();
43 }
44 } else {
45 hkey->header.full_key = (hash_key_data*)&hkey->key_storage;
46 }
47 hash_key_set_len(hkey, hash_key_len);
48 hash_key_set_bucket_index(hkey, 0);
49 hash_key_set_client_key(hkey, key, nkey);
50 }
51
52 /*
53 * The item object stores a hash_key in a contiguous allocation
54 * This method ensures correct copying into a contiguous hash_key
55 */
hash_key_copy_to_item(hash_item* dst, const hash_key* src)56 static void hash_key_copy_to_item(hash_item* dst, const hash_key* src) {
57 hash_key* key = item_get_key(dst);
58 memcpy(key, src, sizeof(hash_key_header));
59 key->header.full_key = (hash_key_data*)&key->key_storage;
60 memcpy(hash_key_get_key(key), hash_key_get_key(src), hash_key_get_key_len(src));
61 }
62
do_item_alloc(const hash_key *key)63 hash_item *do_item_alloc(const hash_key *key) {
64 size_t ntotal = sizeof(hash_item) + hash_key_get_alloc_size(key);
65 auto* it = static_cast<hash_item*>(calloc(ntotal, 1));
66 if (it == nullptr) {
67 throw std::bad_alloc();
68 }
69
70 hash_key_copy_to_item(it, key);
71 return it;
72 }
73
item_alloc(uint32_t key)74 hash_item *item_alloc(uint32_t key) {
75 hash_key hkey;
76 hash_key_create(&hkey, key);
77 auto* it = do_item_alloc(&hkey);
78 return it;
79 }
80
AccessSingleItem(benchmark::State& state)81 void AccessSingleItem(benchmark::State& state) {
82 hash_key hkey;
83 hash_key_create(&hkey, 0);
84 while (state.KeepRunning()) {
85 if (assoc_find(crc32c(hash_key_get_key(&hkey),
86 hash_key_get_key_len(&hkey), 0),
87 &hkey) == nullptr) {
88 throw std::logic_error("AccessSingleItem: Expected to find key");
89 }
90 }
91 }
92
AccessRandomItems(benchmark::State& state)93 void AccessRandomItems(benchmark::State& state) {
94 std::random_device rd;
95 std::minstd_rand0 gen(rd());
96 std::uniform_int_distribution<uint32_t> dis;
97
98 while (state.KeepRunning()) {
99 uint32_t id = dis(gen) % max_items;
100 hash_key hkey;
101 hash_key_create(&hkey, id);
102 if (assoc_find(crc32c(hash_key_get_key(&hkey),
103 hash_key_get_key_len(&hkey), 0),
104 &hkey) == nullptr) {
105 throw std::logic_error("AccessRandomItems: Expected to find key");
106 }
107 }
108 }
109
110 BENCHMARK(AccessSingleItem)->ThreadRange(1, 16);
111 BENCHMARK(AccessRandomItems)->ThreadRange(1, 16);
112
main(int argc, char** argv)113 int main(int argc, char** argv) {
114 ::benchmark::Initialize(&argc, argv);
115 if (::benchmark::ReportUnrecognizedArguments(argc, argv)) {
116 return EXIT_FAILURE;
117 }
118
119 assoc_init(nullptr);
120
121 // Populate the cache
122 for (uint32_t ii = 0; ii < max_items; ++ii) {
123 auto* it = item_alloc(ii);
124 hash_key hkey;
125 hash_key_create(&hkey, ii);
126 assoc_insert(crc32c(hash_key_get_key(&hkey),
127 hash_key_get_key_len(&hkey),
128 0),
129 it);
130 }
131
132 // Wait until the assoc table is rebalanced
133 while (assoc_expanding()) {
134 usleep(250);
135 }
136
137 ::benchmark::RunSpecifiedBenchmarks();
138
139 for (uint32_t ii = 0; ii < max_items; ++ii) {
140 hash_key hkey;
141 hash_key_create(&hkey, ii);
142 auto hash = crc32c(hash_key_get_key(&hkey),
143 hash_key_get_key_len(&hkey), 0);
144
145 auto* it = assoc_find(hash, &hkey);
146 assoc_delete(hash, &hkey);
147 free(static_cast<void*>(it));
148 }
149
150 assoc_destroy();
151
152 return EXIT_SUCCESS;
153 }
154