On Tue, Apr 19, 2011 at 1:02 PM, Olav Sandstaa <olav.sandstaa@stripped>wrote:
> Hi Tor,
>
> Thanks for a very good patch. In addition the the performance improvement
> you get by get rid of calls to malloc I think this is also a good
> improvement to our code. Great example of a detailed unit test.
>
> I have only minor comments, see inline. Most you should feel free to ignore
> if you do not agree with my comments.
>
> OK to push when you have looked at the comments.
>
> Olav
>
>
>
thanks Olav, comments on comments below.
-- didrik
>
> On 04/14/11 03:37 PM, Tor Didriksen wrote:
>
>> #At file:///export/home/didrik/repo/trunk-dynarray/ based on
>> revid:olav.sandstaa@stripped
>>
>> 3318 Tor Didriksen 2011-04-14
>> WL#5774 Decrease number of malloc's for normal DML queries
>> One of the malloc's was due to DYNAMIC_ARRAY keyuse;
>> Replace it with an array in MEM_ROOT instead.
>>
>> This fix yields a 1-2% performance gain with sysbench if you have
>> lots of cpus/threads.
>> @ sql/mem_root_array.h
>> A typesafe replacement for DYNAMIC_ARRAY.
>> We use MEM_ROOT for allocating storage, rather than the C++ heap.
>> The interface is chosen to be similar to std::vector.
>> @ sql/sql_select.cc
>> Use Key_use_array rather than DYNAMIC_ARRAY.
>> @ sql/sql_select.h
>> Use Key_use_array rather than DYNAMIC_ARRAY.
>> @ unittest/gunit/dynarray-t.cc
>> Unit tests for Mem_root_array.
>> Also performance testing comparing DYNAMIC_ARRAY with std::vector
>> and Mem_root_array.
>>
>> added:
>> sql/mem_root_array.h
>> unittest/gunit/dynarray-t.cc
>> modified:
>> sql/sql_select.cc
>> sql/sql_select.h
>> sql/sql_test.cc
>> sql/sql_test.h
>> unittest/gunit/CMakeLists.txt
>> === added file 'sql/mem_root_array.h'
>> --- a/sql/mem_root_array.h 1970-01-01 00:00:00 +0000
>> +++ b/sql/mem_root_array.h 2011-04-14 13:37:15 +0000
>> @@ -0,0 +1,172 @@
>> +/* Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
>> +
>> + This program is free software; you can redistribute it and/or modify
>> + it under the terms of the GNU General Public License as published by
>> + the Free Software Foundation; version 2 of the License.
>> +
>> + This program is distributed in the hope that it will be useful,
>> + but WITHOUT ANY WARRANTY; without even the implied warranty of
>> + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
>> + GNU General Public License for more details.
>> +
>> + You should have received a copy of the GNU General Public License
>> + along with this program; if not, write to the Free Software
>> + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
>> USA */
>> +
>> +
>> +#ifndef MEM_ROOT_ARRAY_INCLUDED
>> +#define MEM_ROOT_ARRAY_INCLUDED
>> +
>> +#include<my_alloc.h>
>> +
>> +/**
>> + A typesafe replacement for DYNAMIC_ARRAY.
>> + We use MEM_ROOT for allocating storage, rather than the C++ heap.
>> + The interface is chosen to be similar to std::vector.
>> +
>> + Note that MEM_ROOT has no facility for reusing free space,
>> + so don't use this if multiple re-expansions are likely to happen.
>> +
>> + @param Element_type The type of the elements of the container.
>> + @param has_trivial_destructor If true, we don't destroy elements.
>> + We could have used type traits to determine this.
>> + __has_trivial_destructor is supported by some (but not all)
>> + compilers we use.
>> + Maybe we should *require* that Element_type has_trivial_destructor?
>> + (since we do not guarantee destruction of objects in a MEM_ROOT
>> anyways)
>> +*/
>> +template<typename Element_type, bool has_trivial_destructor>
>> +class Mem_root_array
>> +{
>> +public:
>> + Mem_root_array()
>> + : m_root(NULL), m_array(NULL), m_size(0), m_capacity(0)
>> + {
>> + }
>> +
>> + Mem_root_array(MEM_ROOT *root)
>> + : m_root(root), m_array(NULL), m_size(0), m_capacity(0)
>> + {
>> + }
>> +
>> + ~Mem_root_array()
>> + {
>> + clear();
>> + }
>> +
>> + void set_mem_root(MEM_ROOT *root) { m_root= root; }
>> +
>> + Element_type&at(size_t n)
>> + {
>> + DBUG_ASSERT(n< size());
>> + return m_array[n];
>> + }
>> +
>> + const Element_type&at(size_t n) const
>> + {
>> + DBUG_ASSERT(n< size());
>> + return m_array[n];
>> + }
>> +
>> + // Returns a pointer to the first element in the array.
>> + Element_type *begin() { return&m_array[0]; }
>> +
>> + // Returns an pointer to the past-the-end element in the array.
>> + Element_type *end() { return&m_array[size()]; }
>> +
>> + // Erases all of the elements.
>> + void clear()
>> + {
>> + chop(0);
>> + }
>> +
>> + /*
>> + Chops the tail off the array, erasing all tail elements.
>> + @param pos Index of first element to erase.
>> + */
>> + void chop(size_t pos)
>> + {
>>
>
> Even though the code handles it and that it is a legal operation: Would it
> be good to add the following assert?
>
> DBUG_ASSERT(pos <= m_size)
>
> I think that in most situations where this would hit it would unintended by
> the user? If this assert would be a problem then we could remove it later?
added:
DBUG_ASSERT(pos < m_size);
>
>
> + if (pos>= m_size)
>> + return;
>> + if (!has_trivial_destructor)
>> + {
>> + for (size_t ix= pos; pos< m_size; ++pos)
>> + {
>> + Element_type *p=&m_array[ix];
>> + p->~Element_type(); // Destroy discarded element.
>> + }
>> + }
>> + m_size= pos;
>> + }
>>
>
> To consider: I think it would be good to add a small unit test for chop().
>
>
>
yep
> +
>> + /*
>> + Reserves space for array elements.
>> + Copies over existing elements, in case we are re-expanding the array.
>> +
>> + @param n number of elements.
>> + @retval true if out-of-memory, false otherwise.
>> + */
>> + bool reserve(size_t n)
>> + {
>>
>
> What happens if reserve() is called on an object created by the default
> constructor? (where m_root is set to NULL)
> Since it is possible to create Mem_root_arrays with m_root == NULL I think
> it would be good to add the following assert:
>
> DBUG_ASSERT(m_root != NULL);
>
>
yep
>
> + if (n<= m_capacity)
>> + return false;
>> +
>> + void *mem= alloc_root(m_root, n * element_size());
>> + if (!mem)
>> + return true;
>> + Element_type *array= static_cast<Element_type*>(mem);
>> +
>> + // Copy all the existing elements into the new array.
>> + for (size_t ix= 0; ix< m_size; ++ix)
>> + {
>> + Element_type *new_p=&array[ix];
>> + Element_type *old_p=&m_array[ix];
>> + new (new_p) Element_type(*old_p); // Copy into new
>> location.
>> + if (!has_trivial_destructor)
>> + old_p->~Element_type(); // Destroy the old
>> element.
>> + }
>> +
>> + // Forget the old array.
>> + m_array= array;
>> + m_capacity= n;
>> + return false;
>> + }
>> +
>> + /*
>> + Adds a new element at the end of the array, after its current last
>> + element. The content of this new element is initialized to a copy of
>> + the input argument.
>> +
>> + @param element Object to copy.
>> + @retval true if out-of-memory, false otherwise.
>> + */
>> + bool push_back(const Element_type&element)
>> + {
>> + const size_t min_capacity= 10;
>> + const size_t expansion_factor= 2;
>> + if (0 == m_capacity&& reserve(min_capacity))
>> + return true;
>> + if (m_size == m_capacity&& reserve(m_capacity * expansion_factor))
>> + return true;
>> + Element_type *p=&m_array[m_size++];
>> + new (p) Element_type(element);
>> + return false;
>> + }
>> +
>> + size_t element_size() const { return sizeof(Element_type); }
>> + size_t size() const { return m_size; }
>> + size_t capacity() const { return m_capacity; }
>> +
>> +private:
>> + MEM_ROOT *m_root;
>> + Element_type *m_array;
>> + size_t m_size;
>> + size_t m_capacity;
>> +
>> + // Not (yet) implemented.
>> + Mem_root_array(const Mem_root_array&);
>> + Mem_root_array&operator=(const Mem_root_array&);
>> +};
>> +
>> +
>> +#endif // MEM_ROOT_ARRAY_INCLUDED
>>
>> === modified file 'sql/sql_select.cc'
>> --- a/sql/sql_select.cc 2011-04-14 09:32:17 +0000
>> +++ b/sql/sql_select.cc 2011-04-14 13:37:15 +0000
>> @@ -59,11 +59,11 @@ const char *join_type_str[]={ "UNKNOWN",
>>
>> struct st_sargable_param;
>>
>> -static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
>> +static void optimize_keyuse(JOIN *join, Key_use_array *keyuse_array);
>> static bool make_join_statistics(JOIN *join, TABLE_LIST *leaves, Item
>> *conds,
>> - DYNAMIC_ARRAY *keyuse);
>> + Key_use_array *keyuse);
>> static bool optimize_semijoin_nests(JOIN *join, table_map all_table_map);
>> -static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,
>> +static bool update_ref_and_keys(THD *thd, Key_use_array *keyuse,
>> JOIN_TAB *join_tab,
>> uint tables, Item *conds,
>> COND_EQUAL *cond_equal,
>> @@ -3466,7 +3466,7 @@ bool JOIN::destroy()
>> while ((sj_nest= sj_list_it++))
>> sj_nest->sj_mat_exec= NULL;
>>
>> - delete_dynamic(&keyuse);
>> + keyuse.clear();
>> delete procedure;
>> DBUG_RETURN(test(error));
>> }
>> @@ -4629,7 +4629,7 @@ static uint get_tmp_table_rec_length(Lis
>>
>> static bool
>> make_join_statistics(JOIN *join, TABLE_LIST *tables_arg, Item *conds,
>> - DYNAMIC_ARRAY *keyuse_array)
>> + Key_use_array *keyuse_array)
>> {
>> int error;
>> TABLE *table;
>> @@ -6016,7 +6016,7 @@ max_part_bit(key_part_map bits)
>> */
>>
>> static bool
>> -add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
>> +add_key_part(Key_use_array *keyuse_array,KEY_FIELD *key_field)
>>
>
> Not introduced by your patch but since you anyway change this line:
> consider adding an extra space after the comma in the argument list.
yep
>
>
> {
>> Field *field=key_field->field;
>> TABLE *form= field->table;
>> @@ -6046,7 +6046,7 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array
>> key_field->null_rejecting,
>> key_field->cond_guard,
>> key_field->sj_pred_no);
>> - if (insert_dynamic(keyuse_array,&keyuse))
>> + if (keyuse_array->push_back(keyuse))
>> return TRUE;
>> }
>> }
>> @@ -6059,7 +6059,7 @@ add_key_part(DYNAMIC_ARRAY *keyuse_array
>> #define FT_KEYPART (MAX_REF_PARTS+10)
>>
>> static bool
>> -add_ft_keys(DYNAMIC_ARRAY *keyuse_array,
>> +add_ft_keys(Key_use_array *keyuse_array,
>> JOIN_TAB *stat,Item *cond,table_map usable_tables)
>> {
>> Item_func_match *cond_func=NULL;
>> @@ -6121,7 +6121,7 @@ add_ft_keys(DYNAMIC_ARRAY *keyuse_array,
>> false, // null_rejecting
>> NULL, // cond_guard
>> UINT_MAX); // sj_pred_no
>> - return insert_dynamic(keyuse_array,&keyuse);
>> + return keyuse_array->push_back(keyuse);
>> }
>>
>>
>> @@ -6237,7 +6237,7 @@ static void add_key_fields_for_nj(JOIN *
>> */
>>
>> static bool
>> -update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse,JOIN_TAB *join_tab,
>> +update_ref_and_keys(THD *thd, Key_use_array *keyuse,JOIN_TAB *join_tab,
>> uint tables, Item *cond, COND_EQUAL *cond_equal,
>> table_map normal_tables, SELECT_LEX *select_lex,
>> SARGABLE_PARAM **sargables)
>> @@ -6280,7 +6280,8 @@ update_ref_and_keys(THD *thd, DYNAMIC_AR
>> /* set a barrier for the array of SARGABLE_PARAM */
>> (*sargables)[0].field= 0;
>>
>> - if (my_init_dynamic_array(keyuse, sizeof(Key_use), 20, 64))
>> + keyuse->set_mem_root(thd->mem_root);
>>
>
> Question: would it change which mem_root being used if you moved the
> setting of keyuse's mem_root to the JOIN constructor (or JOIN::init)?
Moved it to init() (and removed a bzero() there!!)
>
>
> + if (keyuse->reserve(20))
>> return TRUE;
>>
>
> Comment: I think for this part of the code it would be just as good not to
> reserve anything in the key use array and instead relay on that the
> implementer of the Key array has selected a sensible default value? (and we
> could save two lines of code...)
>
>
I didn't want to change any semantics (assuming that the number 20 is not
random....)
I also wanted Mem_root_array to be general-purpose, rather than tailored to
Keyuse.
>
> if (cond)
>> {
>> @@ -6355,21 +6356,21 @@ update_ref_and_keys(THD *thd, DYNAMIC_AR
>> used in the query, we drop the partial key parts from
>> consideration).
>> Special treatment for ft-keys.
>> */
>> - if (keyuse->elements)
>> + if (keyuse->size())
>>
>
> Minor comment (feel free to ignore): I think this test would be more
> readable by testing explicitly:
>
> if (keyuse->size() > 0)
>
> or maybe consider implementing a Mem_root_array::empty() for this?
empty() is better (both here, and in general)
>
>
> {
>> Key_use *save_pos, *use;
>>
>> - my_qsort(keyuse->buffer, keyuse->elements, sizeof(Key_use),
>> + my_qsort(keyuse->begin(), keyuse->size(), keyuse->element_size(),
>> reinterpret_cast<qsort_cmp>(sort_keyuse));
>>
>> const Key_use key_end(NULL, NULL, 0, 0, 0, 0, 0, 0, false, NULL, 0);
>> - if (insert_dynamic(keyuse,&key_end)) // added for easy testing
>> + if (keyuse->push_back(key_end)) // added for easy testing
>> return TRUE;
>>
>> - use= save_pos= dynamic_element(keyuse, 0, Key_use *);
>> + use= save_pos= keyuse->begin();
>> const Key_use *prev=&key_end;
>> found_eq_constant=0;
>> - for (i=0 ; i< keyuse->elements-1 ; i++,use++)
>> + for (i=0 ; i< keyuse->size()-1 ; i++,use++)
>> {
>> if (!use->used_tables&& use->optimize !=
> KEY_OPTIMIZE_REF_OR_NULL)
>> use->table->const_key_parts[use->key]|= use->keypart_map;
>> @@ -6402,9 +6403,9 @@ update_ref_and_keys(THD *thd, DYNAMIC_AR
>> use->table->reginfo.join_tab->checked_keys.set_bit(use->key);
>> save_pos++;
>> }
>> - i= (uint) (save_pos - (Key_use *)keyuse->buffer);
>> - (void) set_dynamic(keyuse,&key_end, i);
>> - keyuse->elements=i;
>> + i= (uint) (save_pos - keyuse->begin());
>> + keyuse->at(i) = key_end;
>> + keyuse->chop(i);
>>
>
> Comment: I think it would be useful to add a short comments for these three
> last lines to make it easier to understand what they do.
That comment would be 'chop off everything after save_pos' which I think is
too trivial.
Frankly, I didn't make any effort to understand the logic above....
>
>
> }
>> DBUG_EXECUTE("opt", print_keyuse_array(keyuse););
>> return FALSE;
>> @@ -6414,12 +6415,11 @@ update_ref_and_keys(THD *thd, DYNAMIC_AR
>> Update some values in keyuse for faster choose_plan() loop.
>> */
>>
>> -static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array)
>> +static void optimize_keyuse(JOIN *join, Key_use_array *keyuse_array)
>> {
>> - Key_use *end, *keyuse= dynamic_element(keyuse_array, 0, Key_use *);
>> -
>> - for (end= keyuse+ keyuse_array->elements ; keyuse< end ; keyuse++)
>> + for (size_t ix= 0; ix< keyuse_array->size(); ++ix)
>> {
>> + Key_use *keyuse=&keyuse_array->at(ix);
>> table_map map;
>> /*
>> If we find a ref, assume this table matches a proportional
>>
>> === modified file 'sql/sql_select.h'
>> --- a/sql/sql_select.h 2011-04-06 11:13:33 +0000
>> +++ b/sql/sql_select.h 2011-04-14 13:37:15 +0000
>> @@ -30,6 +30,7 @@
>> #include "records.h" /* READ_RECORD */
>> #include "opt_range.h" /* SQL_SELECT, QUICK_SELECT_I */
>>
>> +#include "mem_root_array.h"
>>
>> /* Values in optimize */
>> #define KEY_OPTIMIZE_EXISTS 1
>> @@ -37,12 +38,12 @@
>>
>> /**
>> Information about usage of an index to satisfy an equality condition.
>> -
>> - @note such objects are stored in DYNAMIC_ARRAY which uses sizeof(), so
>> keep
>> - this class as POD as possible.
>> */
>> class Key_use {
>> public:
>> + // We need the default constructor for unit testing.
>> + Key_use() { memset(this, 0, sizeof(*this)); }
>> +
>> Key_use(TABLE *table_arg, Item *val_arg, table_map used_tables_arg,
>> uint key_arg, uint keypart_arg, uint optimize_arg,
>> key_part_map keypart_map_arg, ha_rows ref_table_rows_arg,
>> @@ -93,6 +94,12 @@ public:
>> uint sj_pred_no;
>> };
>>
>> +
>> +typedef Mem_root_array<Key_use, true> Key_use_array;
>>
>
> Comment: it would be nice to have a short comments added to this typedef
> explaining what this is to be used for and the "true" argument.
>
>
Of course.
>
> +#ifndef DBUG_OFF
>> +void print_keyuse_array(Key_use_array *keyuse_array);
>> +#endif
>>
>
> Comment: as commented elsewhere: I think it would have been better if this
> declaration was in sql_test.h (but understand why you have moved it here).
>
>
>
Moved it to sql_test.h
> +
>> class store_key;
>>
>> typedef struct st_table_ref : public Sql_alloc
>> @@ -1807,7 +1814,9 @@ public:
>> bool skip_sort_order;
>>
>> bool need_tmp, hidden_group_fields;
>> - DYNAMIC_ARRAY keyuse;
>> +
>> + Key_use_array keyuse;
>> +
>> List<Item> all_fields; ///< to store all fields that used in query
>> ///Above list changed to use temporary table
>> List<Item> tmp_all_fields1, tmp_all_fields2, tmp_all_fields3;
>>
>
> TODO: I think you should do something with the following line in
> JOIN::init():
>
> bzero((char*) &keyuse,sizeof(keyuse));
>
I hadn't seen that one!
>
> Alternatives:
>
> a. just remove it
> b. replace it with the following:
>
> keyuse.clear()
> keyuse.set_mem_root(.....)
b.
>
>
>
>
> === modified file 'sql/sql_test.cc'
>> --- a/sql/sql_test.cc 2010-11-05 22:19:41 +0000
>> +++ b/sql/sql_test.cc 2011-04-14 13:37:15 +0000
>> @@ -239,7 +239,7 @@ TEST_join(JOIN *join)
>>
>> #define FT_KEYPART (MAX_REF_PARTS+10)
>>
>> -void print_keyuse(Key_use *keyuse)
>> +void print_keyuse(const Key_use *keyuse)
>> {
>> char buff[256];
>> char buf2[64];
>> @@ -266,14 +266,14 @@ void print_keyuse(Key_use *keyuse)
>>
>>
>> /* purecov: begin inspected */
>> -void print_keyuse_array(DYNAMIC_ARRAY *keyuse_array)
>> +void print_keyuse_array(Key_use_array *keyuse_array)
>>
>
> Suggestion: add const to the the argument?
done
>
>
> {
>> DBUG_LOCK_FILE;
>> - fprintf(DBUG_FILE, "Key_use array (%d elements)\n",
>> keyuse_array->elements);
>> + fprintf(DBUG_FILE, "Key_use array (%d elements)\n",
>> + (int) keyuse_array->size());
>>
>
> Since keyuse_array->size() returns an unsigned type (size_t) would it be
> better to change the %d to %u and either drop the casting to int or cast to
> (unsigned int) instead?
>
>
I don't like unsigned/size_t, but used it anyway, since std::vector<> does.
Some kind of casting is necessary, I simply picked int.
I don't think MySQL will support more than 2147483647 indexes anytime
soon...
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#64-bit_Portability
>
> DBUG_UNLOCK_FILE;
>> - for(uint i=0; i< keyuse_array->elements; i++)
>> - print_keyuse(reinterpret_cast<Key_use *>
>> - (dynamic_array_ptr(keyuse_array, i)));
>> + for(uint i=0; i< keyuse_array->size(); i++)
>> + print_keyuse(&keyuse_array->at(i));
>> }
>>
>>
>>
>> === modified file 'sql/sql_test.h'
>> --- a/sql/sql_test.h 2010-08-19 07:10:58 +0000
>> +++ b/sql/sql_test.h 2011-04-14 13:37:15 +0000
>> @@ -31,7 +31,6 @@ void print_plan(JOIN* join,uint idx, dou
>> double current_read_time, const char *info);
>> void dump_TABLE_LIST_graph(SELECT_LEX *select_lex, TABLE_LIST* tl);
>> void print_sjm(TABLE_LIST *emb_sj_nest);
>> -void print_keyuse_array(DYNAMIC_ARRAY *keyuse_array);
>>
>
> My preference would be to keep this declaration in sql_test.h instead of
> having to declare it in sql_select.h. I see why you have moved it. Would it
> be possible to keep the declaration sql_test.h?
>
> TODO: if you decides to keep it like it is, then you should update the
> following comment in sql_select.cc:
>
> #include "sql_test.h" // print_where, print_keyuse_array,
> // print_sjm, print_plan, TEST_join
done
>
>
>
> #endif
>> void mysql_print_status();
>>
>>
>> === modified file 'unittest/gunit/CMakeLists.txt'
>> --- a/unittest/gunit/CMakeLists.txt 2011-04-13 11:31:44 +0000
>> +++ b/unittest/gunit/CMakeLists.txt 2011-04-14 13:37:15 +0000
>> @@ -206,6 +206,7 @@ ENDIF()
>> SET(TESTS
>> bounded_queue
>> dbug
>> + dynarray
>> mdl
>> mdl_mytap
>> my_bitmap
>>
>> === added file 'unittest/gunit/dynarray-t.cc'
>> --- a/unittest/gunit/dynarray-t.cc 1970-01-01 00:00:00 +0000
>> +++ b/unittest/gunit/dynarray-t.cc 2011-04-14 13:37:15 +0000
>> @@ -0,0 +1,357 @@
>> +/* Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
>> +
>> + This program is free software; you can redistribute it and/or modify
>> + it under the terms of the GNU General Public License as published by
>> + the Free Software Foundation; version 2 of the License.
>> +
>> + This program is distributed in the hope that it will be useful,
>> + but WITHOUT ANY WARRANTY; without even the implied warranty of
>> + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
>> + GNU General Public License for more details.
>> +
>> + You should have received a copy of the GNU General Public License
>> + along with this program; if not, write to the Free Software
>> + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
>> USA */
>> +
>> +// First include (the generated) my_config.h, to get correct platform
>> defines,
>> +// then gtest.h (before any other MySQL headers), to avoid min() macros
>> etc ...
>> +#include "my_config.h"
>> +#include<gtest/gtest.h>
>> +
>> +#include<algorithm>
>> +#include<functional>
>> +#include<vector>
>> +
>> +#include "sql_select.h"
>> +#include "mem_root_array.h"
>> +
>> +/**
>> + WL#5774 Decrease number of malloc's for normal DML queries.
>> + One of the malloc's was due to DYNAMIC_ARRAY keyuse;
>> + We replace the DYNAMIC_ARRAY with a std::vector-like class
>> Mem_root_array.
>> +
>> + Below are unit tests for comparing performance, and for testing
>> + functionality of Mem_root_array.
>> +*/
>> +
>> +pthread_key(MEM_ROOT**, THR_MALLOC);
>> +pthread_key(THD*, THR_THD);
>> +
>> +extern "C" void sql_alloc_error_handler(void)
>> +{
>> + ADD_FAILURE();
>> +}
>> +
>> +
>> +/*
>> + Rewrite of sort_keyuse() to comparison operator for use by std::less<>
>> + It is a template argument, so static rather than in unnamed namespace.
>> +*/
>> +static inline bool operator<(const Key_use&a, const Key_use&b)
>> +{
>> + if (a.table->tablenr != b.table->tablenr)
>> + return a.table->tablenr< b.table->tablenr;
>> + if (a.key != b.key)
>> + return a.key< b.key;
>> + if (a.keypart != b.keypart)
>> + return a.keypart< b.keypart;
>> + const bool atab = test((a.used_tables& ~OUTER_REF_TABLE_BIT));
>> + const bool btab = test((b.used_tables& ~OUTER_REF_TABLE_BIT));
>> + if (atab != btab)
>> + return atab< btab;
>> + return
>> + ((a.optimize& KEY_OPTIMIZE_REF_OR_NULL)<
>> + (b.optimize& KEY_OPTIMIZE_REF_OR_NULL));
>> +}
>> +
>> +
>> +/*
>> + Compare for equality.
>> + It is a template argument, so static rather than in unnamed namespace.
>> +*/
>> +static inline bool operator==(const Key_use&lhs, const Key_use&rhs)
>> +{
>> + return
>> + lhs.table->tablenr == rhs.table->tablenr&&
>> + lhs.key == rhs.key&&
>> + lhs.keypart == rhs.keypart&&
>> + test((lhs.used_tables& ~OUTER_REF_TABLE_BIT))
>> + ==
>> + test((rhs.used_tables& ~OUTER_REF_TABLE_BIT))&&
>> + (lhs.optimize& KEY_OPTIMIZE_REF_OR_NULL)
>> + ==
>> + (rhs.optimize& KEY_OPTIMIZE_REF_OR_NULL);
>> +}
>> +
>> +
>> +namespace {
>> +
>> +/*
>> + Cut'n paste this function from sql_select.cc,
>> + to avoid linking in the entire server for this unit test.
>> +*/
>> +inline int sort_keyuse(Key_use *a, Key_use *b)
>> +{
>> + int res;
>> + if (a->table->tablenr != b->table->tablenr)
>> + return (int) (a->table->tablenr - b->table->tablenr);
>> + if (a->key != b->key)
>> + return (int) (a->key - b->key);
>> + if (a->keypart != b->keypart)
>> + return (int) (a->keypart - b->keypart);
>> + // Place const values before other ones
>> + if ((res= test((a->used_tables& ~OUTER_REF_TABLE_BIT)) -
>> + test((b->used_tables& ~OUTER_REF_TABLE_BIT))))
>> + return res;
>> + /* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
>> + return (int) ((a->optimize& KEY_OPTIMIZE_REF_OR_NULL) -
>> + (b->optimize& KEY_OPTIMIZE_REF_OR_NULL));
>> +}
>> +
>> +
>> +std::ostream&operator<<(std::ostream&s, const Key_use&v)
>> +{
>> + return s<< "{"
>> +<< v.table->tablenr<< ","
>> +<< v.key<< ","
>> +<< v.keypart<< ","
>> +<< v.used_tables<< ","
>> +<< v.optimize
>> +<< "}"
>> + ;
>> +}
>> +
>> +
>> +// We generate some random data at startup, for testing of sorting.
>> +void generate_test_data(Key_use *keys, TABLE *tables, int n)
>> +{
>> + int ix;
>> + for (ix= 0; ix< n; ++ix)
>> + {
>> + tables[ix].tablenr= ix % 3;
>> + keys[ix]=
>> + Key_use(&tables[ix],
>> + NULL, // Item *val
>> + 0, // table_map used_tables
>> + ix % 4, // uint key
>> + ix % 2, // uint keypart
>> + 0, // uint optimize
>> + 0, // keypart_map
>> + 0, // ha_rows
>> ref_table_rows
>> + true, // bool
>> null_rejecting
>> + NULL, // bool *cond_guard
>> + 0 // uint sj_pred_no
>> + );
>> + }
>> + std::random_shuffle(&keys[0],&keys[n]);
>> +}
>> +
>> +
>> +// Play around with these constants to see std::sort speedup vs.
>> my_qsort.
>> +const int num_elements= 200;
>> +const int num_iterations= 1000;
>> +
>> +/*
>> + This class is used for comparing performance of
>> + std::vector<> and std::sort()
>> + vs
>> + DYNAMIC_ARRAY and my_qsort()
>> + */
>> +class DynArrayTest : public ::testing::Test
>> +{
>> +public:
>> + DynArrayTest() {}
>> +
>> + static void SetUpTestCase()
>> + {
>> + generate_test_data(test_data, table_list, num_elements);
>> + }
>> +
>> + virtual void SetUp()
>> + {
>> + my_init_dynamic_array(&m_keyuse_dyn, sizeof(Key_use), num_elements,
>> 64);
>> + m_keyuse_vec.reserve(num_elements);
>> + }
>> +
>> + void insert_and_sort_dynamic()
>> + {
>> + reset_dynamic(&m_keyuse_dyn);
>> + for (int ix= 0; ix< num_elements; ++ix)
>> + {
>> + insert_dynamic(&m_keyuse_dyn,&test_data[ix]);
>> + }
>> + my_qsort(m_keyuse_dyn.buffer, m_keyuse_dyn.elements, sizeof(Key_use),
>> + reinterpret_cast<qsort_cmp>(sort_keyuse));
>> + }
>> +
>> + void insert_and_sort_vector()
>> + {
>> + m_keyuse_vec.clear();
>> + for (int ix= 0; ix< num_elements; ++ix)
>> + {
>> + m_keyuse_vec.push_back(test_data[ix]);
>> + }
>> + std::sort(m_keyuse_vec.begin(), m_keyuse_vec.end(),
>> std::less<Key_use>());
>> + }
>> +
>> + DYNAMIC_ARRAY m_keyuse_dyn;
>> + std::vector<Key_use> m_keyuse_vec;
>> +private:
>> + static Key_use test_data[num_elements];
>> + static TABLE table_list[num_elements];
>> +
>> + GTEST_DISALLOW_COPY_AND_ASSIGN_(DynArrayTest);
>> +};
>> +
>> +Key_use DynArrayTest::test_data[num_elements];
>> +TABLE DynArrayTest::table_list[num_elements];
>> +
>> +
>> +// Test insert_dynamic() and my_qsort().
>> +TEST_F(DynArrayTest, DynArray)
>> +{
>> + for (int ix= 0; ix< num_iterations; ++ix)
>> + insert_and_sort_dynamic();
>> +}
>> +
>> +
>> +// Test vector::push_back() and std::sort()
>> +TEST_F(DynArrayTest, Vector)
>> +{
>> + for (int ix= 0; ix< num_iterations; ++ix)
>> + insert_and_sort_vector();
>> +}
>> +
>> +
>> +/*
>> + This class is for unit testing of Mem_root_array.
>> + */
>> +class MemRootTest : public ::testing::Test
>> +{
>> +protected:
>> + MemRootTest()
>> + : m_mem_root_p(&m_mem_root),
>> + m_array_mysys(m_mem_root_p),
>> + m_array_std(m_mem_root_p)
>> + {}
>> +
>> + virtual void SetUp()
>> + {
>> + init_sql_alloc(&m_mem_root, 1024, 0);
>> + ASSERT_EQ(0, my_pthread_setspecific_ptr(THR_MALLOC,&m_mem_root_p));
>> + MEM_ROOT *root= *my_pthread_getspecific_ptr(MEM_ROOT**, THR_MALLOC);
>> + ASSERT_EQ(root, m_mem_root_p);
>> +
>> + m_array_mysys.reserve(num_elements);
>> + m_array_std.reserve(num_elements);
>> + }
>> +
>> + virtual void TearDown()
>> + {
>> + free_root(&m_mem_root, MYF(0));
>> + }
>> +
>> + static void SetUpTestCase()
>> + {
>> + generate_test_data(test_data, table_list, num_elements);
>> + ASSERT_EQ(0, pthread_key_create(&THR_THD, NULL));
>> + ASSERT_EQ(0, pthread_key_create(&THR_MALLOC, NULL));
>> + }
>> +
>> + static void TearDownTestCase()
>> + {
>> + pthread_key_delete(THR_THD);
>> + pthread_key_delete(THR_MALLOC);
>> + }
>> +
>> + void insert_and_sort_mysys()
>> + {
>> + m_array_mysys.clear();
>> + for (int ix= 0; ix< num_elements; ++ix)
>> + {
>> + m_array_mysys.push_back(test_data[ix]);
>> + }
>> + my_qsort(m_array_mysys.begin(), m_array_mysys.size(),
>> + m_array_mysys.element_size(),
>> + reinterpret_cast<qsort_cmp>(sort_keyuse));
>> + }
>> +
>> + void insert_and_sort_std()
>> + {
>> + m_array_std.clear();
>> + for (int ix= 0; ix< num_elements; ++ix)
>> + {
>> + m_array_std.push_back(test_data[ix]);
>> + }
>> + std::sort(m_array_std.begin(), m_array_std.end(),
>> std::less<Key_use>());
>> + }
>> +
>> + MEM_ROOT m_mem_root;
>> + MEM_ROOT *m_mem_root_p;
>> + Key_use_array m_array_mysys;
>> + Key_use_array m_array_std;
>> +private:
>> + static Key_use test_data[num_elements];
>> + static TABLE table_list[num_elements];
>> +
>> + GTEST_DISALLOW_COPY_AND_ASSIGN_(MemRootTest);
>> +};
>> +
>> +Key_use MemRootTest::test_data[num_elements];
>> +TABLE MemRootTest::table_list[num_elements];
>> +
>> +
>> +// Test Mem_root_array::push_back() and my_qsort()
>> +TEST_F(MemRootTest, KeyUseMysys)
>> +{
>> + for (int ix= 0; ix< num_iterations; ++ix)
>> + insert_and_sort_mysys();
>> +}
>> +
>> +
>> +// Test Mem_root_array::push_back() and std::sort()
>> +TEST_F(MemRootTest, KeyUseStd)
>> +{
>> + for (int ix= 0; ix< num_iterations; ++ix)
>> + insert_and_sort_std();
>> +}
>> +
>> +
>> +// Test that my_qsort() and std::sort() generate same order.
>> +TEST_F(MemRootTest, KeyUseCompare)
>> +{
>> + insert_and_sort_mysys();
>> + insert_and_sort_std();
>> + for (int ix= 0; ix< num_elements; ++ix)
>> + {
>> + Key_use k1= m_array_mysys.at(ix);
>> + Key_use k2= m_array_std.at(ix);
>> + EXPECT_EQ(k1, k2);
>> + }
>> +}
>> +
>> +
>> +// Test that Mem_root_array re-expanding works.
>> +TEST_F(MemRootTest, Reserve)
>> +{
>> + Mem_root_array<uint, true> intarr;
>> + intarr.set_mem_root(m_mem_root_p);
>> + intarr.reserve(2);
>> + const uint num_pushes= 20;
>> + for (uint ix=0; ix< num_pushes; ++ix)
>> + {
>> + EXPECT_EQ(ix, intarr.size());
>> + EXPECT_FALSE(intarr.push_back(ix));
>> + EXPECT_EQ(ix, intarr.at(ix));
>> + }
>> + for (uint ix=0; ix< num_pushes; ++ix)
>> + {
>> + EXPECT_EQ(ix, intarr.at(ix));
>> + }
>> + EXPECT_EQ(sizeof(uint), intarr.element_size());
>> + EXPECT_EQ(num_pushes, intarr.size());
>> + EXPECT_LE(num_pushes, intarr.capacity());
>> +}
>> +
>> +
>> +}
>>
>>
>>
>>
>>
>
