List:Commits« Previous MessageNext Message »
From:Tor Didriksen Date:April 20 2011 2:12pm
Subject:bzr commit into mysql-trunk branch (tor.didriksen:3328) WL#5774
View as plain text  
#At file:///export/home/didrik/repo/trunk-dynarray/ based on revid:sergey.glukhov@stripped

 3328 Tor Didriksen	2011-04-20
      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-20 14:12:25 +0000
@@ -0,0 +1,175 @@
+/* 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.
+          Elements must be copyable.
+   @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.
+*/
+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; }
+  MEM_ROOT *mem_root() const { return m_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()
+  {
+    if (!empty())
+      chop(0);
+  }
+
+  /*
+    Chops the tail off the array, erasing all tail elements.
+    @param pos Index of first element to erase.
+  */
+  void chop(const size_t pos)
+  {
+    DBUG_ASSERT(pos < m_size);
+    if (pos >= m_size)
+      return;
+    if (!has_trivial_destructor)
+    {
+      for (size_t ix= pos; ix < m_size; ++ix)
+      {
+        Element_type *p= &m_array[ix];
+        p->~Element_type();              // Destroy discarded element.
+      }
+    }
+    m_size= pos;
+  }
+
+  /*
+    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)
+  {
+    if (n <= m_capacity)
+      return false;
+
+    DBUG_ASSERT(m_root != NULL);
+
+    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 capacity()     const { return m_capacity; }
+  size_t element_size() const { return sizeof(Element_type); }
+  bool   empty()        const { return size() == 0; }
+  size_t size()         const { return m_size; }
+
+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-15 08:11:49 +0000
+++ b/sql/sql_select.cc	2011-04-20 14:12:25 +0000
@@ -38,8 +38,7 @@
 #include "sql_parse.h"                          // check_stack_overrun
 #include "sql_partition.h"       // make_used_partitions_str
 #include "sql_acl.h"             // *_ACL
-#include "sql_test.h"            // print_where, print_keyuse_array,
-                                 // print_sjm, print_plan, TEST_join
+#include "sql_test.h"            // misc. debug printing utilities
 #include "records.h"             // init_read_record, end_read_record
 #include "filesort.h"            // filesort_free_buffers
 #include "sql_union.h"           // mysql_union
@@ -59,11 +58,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 +3465,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 +4628,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 +6015,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)
 {
   Field *field=key_field->field;
   TABLE *form= field->table;
@@ -6046,7 +6045,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 +6058,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 +6120,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 +6236,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 +6279,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))
+  DBUG_ASSERT(thd->mem_root == keyuse->mem_root());
+  if (keyuse->reserve(20))
     return TRUE;
   if (cond)
   {
@@ -6355,21 +6355,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->empty())
   {
     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 +6402,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);
   }
   DBUG_EXECUTE("opt", print_keyuse_array(keyuse););
   return FALSE;
@@ -6414,12 +6414,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-15 08:11:49 +0000
+++ b/sql/sql_select.h	2011-04-20 14:12:25 +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,10 @@ public:
   uint         sj_pred_no;
 };
 
+
+// Key_use has a trivial destructor, no need to run it from Mem_root_array.
+typedef Mem_root_array<Key_use, true> Key_use_array;
+
 class store_key;
 
 typedef struct st_table_ref : public Sql_alloc
@@ -1807,7 +1812,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;
@@ -1937,7 +1944,7 @@ public:
     all_fields= fields_arg;
     if (&fields_list != &fields_arg)      /* Avoid valgrind-warning */
       fields_list= fields_arg;
-    bzero((char*) &keyuse,sizeof(keyuse));
+    keyuse.set_mem_root(thd_arg->mem_root);
     tmp_table_param.init();
     tmp_table_param.end_write_records= HA_POS_ERROR;
     rollup.state= ROLLUP::STATE_NONE;

=== 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-20 14:12:25 +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(const Key_use_array *keyuse_array)
 {
   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());
   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-20 14:12:25 +0000
@@ -17,6 +17,7 @@
 #define SQL_TEST_INCLUDED
 
 #include "mysqld.h"
+#include "sql_select.h"
 
 class JOIN;
 struct TABLE_LIST;
@@ -31,7 +32,7 @@ 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);
+void print_keyuse_array(const Key_use_array *keyuse_array);
 #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-20 14:12:25 +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-20 14:12:25 +0000
@@ -0,0 +1,411 @@
+/* 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= 10;
+
+/*
+  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());
+}
+
+
+class DestroyCounter
+{
+public:
+  DestroyCounter(const DestroyCounter &rhs) : p_counter(rhs.p_counter) {}
+  DestroyCounter(size_t *p) : p_counter(p) {}
+  ~DestroyCounter() { (*p_counter)+= 1; }
+private:
+  size_t *p_counter;
+};
+
+
+// Test chop() and clear() and that destructors are executed.
+TEST_F(MemRootTest, ChopAndClear)
+{
+  Mem_root_array<DestroyCounter, false> array;
+  array.set_mem_root(m_mem_root_p);
+  const size_t nn= 4;
+  array.reserve(nn);
+  size_t counter= 0;
+  DestroyCounter foo(&counter);
+  for (size_t ix= 0; ix < array.capacity(); ++ix)
+    array.push_back(foo);
+
+  EXPECT_EQ(0U, counter);
+  array.chop(nn / 2);
+  EXPECT_EQ(nn / 2, counter);
+  EXPECT_EQ(nn / 2, array.size());
+
+  array.clear();
+  EXPECT_EQ(nn, counter);
+}
+
+
+// Test that elements are destroyed if push_back() needs to call reserve().
+TEST_F(MemRootTest, ReserveDestroy)
+{
+  Mem_root_array<DestroyCounter, false> array;
+  array.set_mem_root(m_mem_root_p);
+  const size_t nn= 4;
+  array.reserve(nn / 2);
+  size_t counter= 0;
+  DestroyCounter foo(&counter);
+  for (size_t ix= 0; ix < nn; ++ix)
+    array.push_back(foo);
+  
+  EXPECT_EQ(nn / 2, counter);
+  EXPECT_EQ(nn, array.size());
+
+  counter= 0;
+  array.clear();
+  EXPECT_EQ(nn, counter);
+}
+
+
+}


Attachment: [text/bzr-bundle] bzr/tor.didriksen@oracle.com-20110420141225-epjcxbh0on2vuaj2.bundle
Thread
bzr commit into mysql-trunk branch (tor.didriksen:3328) WL#5774Tor Didriksen20 Apr