1 /* Copyright (c) 2011, 2021, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */
22
23 // First include (the generated) my_config.h, to get correct platform defines.
24 #include "my_config.h"
25 #include <gtest/gtest.h>
26
27 #include <algorithm>
28 #include <functional>
29 #include <vector>
30
31 #include "sql_select.h"
32 #include "mem_root_array.h"
33
34 /**
35 WL#5774 Decrease number of malloc's for normal DML queries.
36 One of the malloc's was due to DYNAMIC_ARRAY keyuse;
37 We replace the DYNAMIC_ARRAY with a std::vector-like class Mem_root_array.
38
39 Below are unit tests for comparing performance, and for testing
40 functionality of Mem_root_array.
41 */
42
43
44 /*
45 Rewrite of sort_keyuse() to comparison operator for use by std::less<>
46 It is a template argument, so static rather than in unnamed namespace.
47 */
operator <(const Key_use & a,const Key_use & b)48 static inline bool operator<(const Key_use &a, const Key_use &b)
49 {
50 if (a.table_ref->tableno() != b.table_ref->tableno())
51 return a.table_ref->tableno() < b.table_ref->tableno();
52 if (a.key != b.key)
53 return a.key < b.key;
54 if (a.keypart != b.keypart)
55 return a.keypart < b.keypart;
56 const bool atab = MY_TEST((a.used_tables & ~OUTER_REF_TABLE_BIT));
57 const bool btab = MY_TEST((b.used_tables & ~OUTER_REF_TABLE_BIT));
58 if (atab != btab)
59 return atab < btab;
60 return
61 ((a.optimize & KEY_OPTIMIZE_REF_OR_NULL) <
62 (b.optimize & KEY_OPTIMIZE_REF_OR_NULL));
63 }
64
65
66 /*
67 Compare for equality.
68 It is a template argument, so static rather than in unnamed namespace.
69 */
operator ==(const Key_use & lhs,const Key_use & rhs)70 static inline bool operator==(const Key_use &lhs, const Key_use &rhs)
71 {
72 return
73 lhs.table_ref->tableno() == rhs.table_ref->tableno() &&
74 lhs.key == rhs.key &&
75 lhs.keypart == rhs.keypart &&
76 MY_TEST((lhs.used_tables & ~OUTER_REF_TABLE_BIT))
77 ==
78 MY_TEST((rhs.used_tables & ~OUTER_REF_TABLE_BIT)) &&
79 (lhs.optimize & KEY_OPTIMIZE_REF_OR_NULL)
80 ==
81 (rhs.optimize & KEY_OPTIMIZE_REF_OR_NULL);
82 }
83
84
operator <<(std::ostream & s,const Key_use & v)85 static inline std::ostream &operator<<(std::ostream &s, const Key_use &v)
86 {
87 return s << "{"
88 << v.table_ref->tableno() << ", "
89 << v.key << ", "
90 << v.keypart << ", "
91 << v.used_tables << ", "
92 << v.optimize
93 << "}"
94 ;
95 }
96
97
98 namespace dynarray_unittest {
99
100 // We still want to unit-test this, to compare performance.
101
102 /*
103 Cut'n paste this function from sql_select.cc,
104 to avoid linking in the entire server for this unit test.
105 */
sort_keyuse(Key_use * a,Key_use * b)106 inline int sort_keyuse(Key_use *a, Key_use *b)
107 {
108 int res;
109 if (a->table_ref->tableno() != b->table_ref->tableno())
110 return (int) (a->table_ref->tableno() - b->table_ref->tableno());
111 if (a->key != b->key)
112 return (int) (a->key - b->key);
113 if (a->keypart != b->keypart)
114 return (int) (a->keypart - b->keypart);
115 // Place const values before other ones
116 if ((res= MY_TEST((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
117 MY_TEST((b->used_tables & ~OUTER_REF_TABLE_BIT))))
118 return res;
119 /* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
120 return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
121 (b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
122 }
123
124
125 // We generate some random data at startup, for testing of sorting.
generate_test_data(Key_use * keys,TABLE_LIST * tables,int n)126 void generate_test_data(Key_use *keys, TABLE_LIST *tables, int n)
127 {
128 int ix;
129 for (ix= 0; ix < n; ++ix)
130 {
131 tables[ix].set_tableno(ix % 3);
132 keys[ix]=
133 Key_use(&tables[ix],
134 NULL, // Item *val
135 0, // table_map used_tables
136 ix % 4, // uint key
137 ix % 2, // uint keypart
138 0, // uint optimize
139 0, // keypart_map
140 0, // ha_rows ref_table_rows
141 true, // bool null_rejecting
142 NULL, // bool *cond_guard
143 0 // uint sj_pred_no
144 );
145 }
146 std::random_shuffle(&keys[0], &keys[n]);
147 }
148
149
150 // Play around with these constants to see std::sort speedup vs. my_qsort.
151 const int num_elements= 200;
152 const int num_iterations= 1000;
153
154 /*
155 This class is used for comparing performance of
156 std::vector<> and std::sort()
157 vs
158 DYNAMIC_ARRAY and my_qsort()
159 */
160 class DynArrayTest : public ::testing::Test
161 {
162 public:
DynArrayTest()163 DynArrayTest() {}
164
SetUpTestCase()165 static void SetUpTestCase()
166 {
167 generate_test_data(test_data, table_list, num_elements);
168 }
169
SetUp()170 virtual void SetUp()
171 {
172 my_init_dynamic_array(&m_keyuse_dyn,
173 PSI_NOT_INSTRUMENTED,
174 sizeof(Key_use), NULL,
175 num_elements, 64);
176 m_keyuse_vec.reserve(num_elements);
177 }
178
TearDown()179 virtual void TearDown()
180 {
181 delete_dynamic(&m_keyuse_dyn);
182 }
183
insert_and_sort_dynamic()184 void insert_and_sort_dynamic()
185 {
186 reset_dynamic(&m_keyuse_dyn);
187 for (int ix= 0; ix < num_elements; ++ix)
188 {
189 insert_dynamic(&m_keyuse_dyn, &test_data[ix]);
190 }
191 my_qsort(m_keyuse_dyn.buffer, m_keyuse_dyn.elements, sizeof(Key_use),
192 reinterpret_cast<qsort_cmp>(sort_keyuse));
193 }
194
insert_and_sort_vector()195 void insert_and_sort_vector()
196 {
197 m_keyuse_vec.clear();
198 for (int ix= 0; ix < num_elements; ++ix)
199 {
200 m_keyuse_vec.push_back(test_data[ix]);
201 }
202 std::sort(m_keyuse_vec.begin(), m_keyuse_vec.end(), std::less<Key_use>());
203 }
204
205 DYNAMIC_ARRAY m_keyuse_dyn;
206 std::vector<Key_use> m_keyuse_vec;
207 private:
208 static Key_use test_data[num_elements];
209 static TABLE_LIST table_list[num_elements];
210
211 GTEST_DISALLOW_COPY_AND_ASSIGN_(DynArrayTest);
212 };
213
214 Key_use DynArrayTest::test_data[num_elements];
215 TABLE_LIST DynArrayTest::table_list[num_elements];
216
217
218 // Test insert_dynamic() and my_qsort().
TEST_F(DynArrayTest,DynArray)219 TEST_F(DynArrayTest, DynArray)
220 {
221 for (int ix= 0; ix < num_iterations; ++ix)
222 insert_and_sort_dynamic();
223 }
224
225
226 // Test vector::push_back() and std::sort()
TEST_F(DynArrayTest,Vector)227 TEST_F(DynArrayTest, Vector)
228 {
229 for (int ix= 0; ix < num_iterations; ++ix)
230 insert_and_sort_vector();
231 }
232
233
234 /*
235 This class is for unit testing of Mem_root_array.
236 */
237 class MemRootTest : public ::testing::Test
238 {
239 protected:
MemRootTest()240 MemRootTest()
241 : m_mem_root_p(&m_mem_root),
242 m_array_mysys(m_mem_root_p),
243 m_array_std(m_mem_root_p)
244 {}
245
SetUp()246 virtual void SetUp()
247 {
248 init_sql_alloc(PSI_NOT_INSTRUMENTED, &m_mem_root, 1024, 0);
249 ASSERT_EQ(0, my_set_thread_local(THR_MALLOC, &m_mem_root_p));
250 MEM_ROOT *root= *static_cast<MEM_ROOT**>(my_get_thread_local(THR_MALLOC));
251 ASSERT_EQ(root, m_mem_root_p);
252
253 m_array_mysys.reserve(num_elements);
254 m_array_std.reserve(num_elements);
255 destroy_counter= 0;
256 }
257
TearDown()258 virtual void TearDown()
259 {
260 free_root(&m_mem_root, MYF(0));
261 }
262
SetUpTestCase()263 static void SetUpTestCase()
264 {
265 generate_test_data(test_data, table_list, num_elements);
266 ASSERT_EQ(0, my_create_thread_local_key(&THR_THD, NULL));
267 THR_THD_initialized= true;
268 ASSERT_EQ(0, my_create_thread_local_key(&THR_MALLOC, NULL));
269 THR_MALLOC_initialized= true;
270 }
271
TearDownTestCase()272 static void TearDownTestCase()
273 {
274 my_delete_thread_local_key(THR_THD);
275 THR_THD_initialized= false;
276 my_delete_thread_local_key(THR_MALLOC);
277 THR_MALLOC_initialized= false;
278 }
279
insert_and_sort_mysys()280 void insert_and_sort_mysys()
281 {
282 m_array_mysys.clear();
283 for (int ix= 0; ix < num_elements; ++ix)
284 {
285 m_array_mysys.push_back(test_data[ix]);
286 }
287 my_qsort(m_array_mysys.begin(), m_array_mysys.size(),
288 m_array_mysys.element_size(),
289 reinterpret_cast<qsort_cmp>(sort_keyuse));
290 }
291
insert_and_sort_std()292 void insert_and_sort_std()
293 {
294 m_array_std.clear();
295 for (int ix= 0; ix < num_elements; ++ix)
296 {
297 m_array_std.push_back(test_data[ix]);
298 }
299 std::sort(m_array_std.begin(), m_array_std.end(), std::less<Key_use>());
300 }
301
302 MEM_ROOT m_mem_root;
303 MEM_ROOT *m_mem_root_p;
304 Key_use_array m_array_mysys;
305 Key_use_array m_array_std;
306 public:
307 static size_t destroy_counter;
308 private:
309 static Key_use test_data[num_elements];
310 static TABLE_LIST table_list[num_elements];
311
312 GTEST_DISALLOW_COPY_AND_ASSIGN_(MemRootTest);
313 };
314
315 size_t MemRootTest::destroy_counter;
316 Key_use MemRootTest::test_data[num_elements];
317 TABLE_LIST MemRootTest::table_list[num_elements];
318
319
320 // Test Mem_root_array::push_back() and my_qsort()
TEST_F(MemRootTest,KeyUseMysys)321 TEST_F(MemRootTest, KeyUseMysys)
322 {
323 for (int ix= 0; ix < num_iterations; ++ix)
324 insert_and_sort_mysys();
325 }
326
327
328 // Test Mem_root_array::push_back() and std::sort()
TEST_F(MemRootTest,KeyUseStd)329 TEST_F(MemRootTest, KeyUseStd)
330 {
331 for (int ix= 0; ix < num_iterations; ++ix)
332 insert_and_sort_std();
333 }
334
335
336 // Test that my_qsort() and std::sort() generate same order.
TEST_F(MemRootTest,KeyUseCompare)337 TEST_F(MemRootTest, KeyUseCompare)
338 {
339 insert_and_sort_mysys();
340 insert_and_sort_std();
341 for (int ix= 0; ix < num_elements; ++ix)
342 {
343 Key_use k1= m_array_mysys.at(ix);
344 Key_use k2= m_array_std.at(ix);
345 EXPECT_EQ(k1, k2);
346 }
347 }
348
349
350 // Test that Mem_root_array re-expanding works.
TEST_F(MemRootTest,Reserve)351 TEST_F(MemRootTest, Reserve)
352 {
353 Mem_root_array<uint, true> intarr(m_mem_root_p);
354 intarr.reserve(2);
355 const uint num_pushes= 20;
356 for (uint ix=0; ix < num_pushes; ++ix)
357 {
358 EXPECT_EQ(ix, intarr.size());
359 EXPECT_FALSE(intarr.push_back(ix));
360 EXPECT_EQ(ix, intarr.at(ix));
361 }
362 for (uint ix=0; ix < num_pushes; ++ix)
363 {
364 EXPECT_EQ(ix, intarr.at(ix));
365 }
366 EXPECT_EQ(sizeof(uint), intarr.element_size());
367 EXPECT_EQ(num_pushes, intarr.size());
368 EXPECT_LE(num_pushes, intarr.capacity());
369 }
370
371
372 // Verify that we can swap mem-root, without any leaks.
373 // Run with
374 // valgrind --leak-check=full <executable> --gtest_filter='-*DeathTest*' > foo
TEST_F(MemRootTest,CopyMemRoot)375 TEST_F(MemRootTest, CopyMemRoot)
376 {
377 Mem_root_array<uint, true> intarr(m_mem_root_p);
378 // Take a copy, we do *not* free_root(own_root)
379 MEM_ROOT own_root= *m_mem_root_p;
380 intarr.set_mem_root(&own_root);
381 intarr.push_back(42);
382 *m_mem_root_p= own_root;
383 }
384
385
386 class DestroyCounter
387 {
388 public:
DestroyCounter()389 DestroyCounter() : p_counter(&MemRootTest::destroy_counter) {};
DestroyCounter(const DestroyCounter & rhs)390 DestroyCounter(const DestroyCounter &rhs) : p_counter(rhs.p_counter) {}
DestroyCounter(size_t * p)391 explicit DestroyCounter(size_t *p) : p_counter(p) {}
~DestroyCounter()392 ~DestroyCounter() { (*p_counter)+= 1; }
393 private:
394 size_t *p_counter;
395 };
396
397
398 // Test chop() and clear() and that destructors are executed.
TEST_F(MemRootTest,ChopAndClear)399 TEST_F(MemRootTest, ChopAndClear)
400 {
401 Mem_root_array<DestroyCounter, false> array(m_mem_root_p);
402 const size_t nn= 4;
403 array.reserve(nn);
404 size_t counter= 0;
405 DestroyCounter foo(&counter);
406 for (size_t ix= 0; ix < array.capacity(); ++ix)
407 array.push_back(foo);
408
409 EXPECT_EQ(0U, counter);
410 array.chop(nn / 2);
411 EXPECT_EQ(nn / 2, counter);
412 EXPECT_EQ(nn / 2, array.size());
413
414 array.clear();
415 EXPECT_EQ(nn, counter);
416 }
417
418
419 // Test that elements are destroyed if push_back() needs to call reserve().
TEST_F(MemRootTest,ReserveDestroy)420 TEST_F(MemRootTest, ReserveDestroy)
421 {
422 Mem_root_array<DestroyCounter, false> array(m_mem_root_p);
423 const size_t nn= 4;
424 array.reserve(nn / 2);
425 size_t counter= 0;
426 DestroyCounter foo(&counter);
427 for (size_t ix= 0; ix < nn; ++ix)
428 array.push_back(foo);
429
430 EXPECT_EQ(nn / 2, counter);
431 EXPECT_EQ(nn, array.size());
432
433 counter= 0;
434 array.clear();
435 EXPECT_EQ(nn, counter);
436 }
437
TEST_F(MemRootTest,ResizeSame)438 TEST_F(MemRootTest, ResizeSame)
439 {
440 Mem_root_array<DestroyCounter, false> array(m_mem_root_p);
441 array.reserve(100);
442 size_t counter= 0;
443 DestroyCounter foo(&counter);
444 for (int ix= 0; ix < 10; ++ix)
445 array.push_back(foo);
446 EXPECT_EQ(10U, array.size());
447 array.resize(10U);
448 EXPECT_EQ(10U, array.size());
449 array.clear();
450 EXPECT_EQ(10U, counter);
451 }
452
TEST_F(MemRootTest,ResizeGrow)453 TEST_F(MemRootTest, ResizeGrow)
454 {
455 Mem_root_array<DestroyCounter, false> array(m_mem_root_p);
456 array.reserve(100);
457 size_t counter= 0;
458 DestroyCounter foo(&counter);
459 array.resize(10, foo);
460 EXPECT_EQ(0U, counter);
461 array.clear();
462 EXPECT_EQ(0U, MemRootTest::destroy_counter);
463 EXPECT_EQ(10U, counter);
464 }
465
TEST_F(MemRootTest,ResizeShrink)466 TEST_F(MemRootTest, ResizeShrink)
467 {
468 size_t counter= 0;
469 Mem_root_array<DestroyCounter, false> array(m_mem_root_p);
470 array.reserve(100);
471 DestroyCounter foo(&counter);
472 array.resize(10, foo);
473 EXPECT_EQ(0U, counter);
474 array.resize(5);
475 EXPECT_EQ(5U, counter);
476 }
477
478
479 }
480