List:Commits« Previous MessageNext Message »
From:Tor Didriksen Date:April 20 2011 11:53am
Subject:Re: bzr commit into mysql-trunk branch (tor.didriksen:3318) WL#5774
View as plain text  
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());
>> +}
>> +
>> +
>> +}
>>
>>
>>
>>
>>
>

Thread
bzr commit into mysql-trunk branch (tor.didriksen:3318) WL#5774Tor Didriksen14 Apr
  • Re: bzr commit into mysql-trunk branch (tor.didriksen:3318) WL#5774Olav Sandstaa19 Apr
    • Re: bzr commit into mysql-trunk branch (tor.didriksen:3318) WL#5774Tor Didriksen20 Apr
    • Re: bzr commit into mysql-trunk branch (tor.didriksen:3318) WL#5774Roy Lyseng28 Apr
      • Re: bzr commit into mysql-trunk branch (tor.didriksen:3318) WL#5774Tor Didriksen28 Apr
        • Re: bzr commit into mysql-trunk branch (tor.didriksen:3318) WL#5774Roy Lyseng28 Apr