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