List:Commits« Previous MessageNext Message »
From:Tor Didriksen Date:October 14 2010 3:35pm
Subject:bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3227)
View as plain text  
#At file:///export/home/didrik/repo/next-mr-opt-team-wl1393-merge/ based on revid:tor.didriksen@stripped

 3227 Tor Didriksen	2010-10-14
      testing how to templatize Bounded_queue

    modified:
      sql/bounded_queue.cc
      sql/bounded_queue.h
      sql/filesort.cc
      unittest/gunit/bounded_queue-t.cc
=== modified file 'sql/bounded_queue.cc'
--- a/sql/bounded_queue.cc	2010-10-12 11:39:45 +0000
+++ b/sql/bounded_queue.cc	2010-10-14 15:35:25 +0000
@@ -13,64 +13,10 @@
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
-#include <string.h>
 #include "bounded_queue.h"
 #include "sql_const.h"
 #include "sql_sort.h"
 
-Bounded_queue::Bounded_queue()
-{
-  memset(&m_queue, 0, sizeof(m_queue));
-}
-
-
-Bounded_queue::~Bounded_queue()
-{
-  delete_queue(&m_queue);
-}
-
-
-int Bounded_queue::init(ha_rows max_elements, uint offset_to_key,
-                        pbool max_at_top,
-                        queue_compare compare, size_t compare_length,
-                        keymaker_function keymaker, Sort_param *sort_param,
-                        uchar **sort_keys)
-{
-  DBUG_ASSERT(sort_keys != NULL);
-
-  m_sort_keys=      sort_keys;
-  m_compare_length= compare_length;
-  m_keymaker=       keymaker;
-  m_sort_param=     sort_param;
-  // init_queue() takes an uint, and also does (max_elements + 1)
-  if (max_elements >= (UINT_MAX - 1))
-    return 1;
-  // We allocate space for one extra element, for replace when queue is full.
-  return init_queue(&m_queue, (uint) max_elements + 1, offset_to_key, max_at_top,
-                    compare, &m_compare_length);
-}
-
-
-void Bounded_queue::push(uchar *element)
-{
-  DBUG_ASSERT(is_initialized());
-  if (queue_is_full((&m_queue)))
-  {
-    uchar **pq_top= (uchar **) queue_top(&m_queue);
-    (*m_keymaker)(m_sort_param, *pq_top, element);
-    queue_replaced(&m_queue);
-  } else {
-    (*m_keymaker)(m_sort_param, m_sort_keys[m_queue.elements], element);
-    queue_insert(&m_queue, (uchar*)&m_sort_keys[m_queue.elements]);
-  }
-}
-
-
-uchar* Bounded_queue::pop()
-{
-  return queue_remove(&m_queue, 0);
-}
-
 
 double get_merge_many_buffs_cost_fast(ha_rows num_buffers, ha_rows max_n_elems,
                                       ha_rows last_n_elems, uint elem_size)

=== modified file 'sql/bounded_queue.h'
--- a/sql/bounded_queue.h	2010-10-12 11:39:45 +0000
+++ b/sql/bounded_queue.h	2010-10-14 15:35:25 +0000
@@ -16,6 +16,7 @@
 #ifndef BOUNDED_QUEUE_INCLUDED
 #define BOUNDED_QUEUE_INCLUDED
 
+#include <string.h>
 #include "my_global.h"
 #include "my_base.h"
 #include "queues.h"
@@ -36,11 +37,19 @@ typedef void (*keymaker_function)(Sort_p
   This is a wrapper on top of QUEUE and the queue_xxx() functions.
   It keeps the top N elements which are inserted.
  */
+template<typename Element_type, typename Key_type>
 class Bounded_queue
 {
 public:
-  Bounded_queue();
-  ~Bounded_queue();
+  Bounded_queue()
+  {
+    memset(&m_queue, 0, sizeof(m_queue));
+  }
+
+  ~Bounded_queue()
+  {
+    delete_queue(&m_queue);
+  }
 
   /**
     Initialize the queue.
@@ -61,7 +70,7 @@ public:
   int init(ha_rows max_elements, uint offset_to_key, pbool max_at_top,
            queue_compare compare, size_t compare_length,
            keymaker_function keymaker, Sort_param *sort_param,
-           uchar **sort_keys);
+           Key_type **sort_keys);
 
   /**
     Pushes an element on the queue.
@@ -69,14 +78,17 @@ public:
 
     @param element        The element to be pushed.
    */
-  void push(uchar *element);
+  void push(Element_type *element);
 
   /**
     Removes an element from the queue.
 
     @retval Pointer to the removed element.
    */
-  uchar *pop();
+  Key_type **pop()
+  {
+    return (Key_type**) queue_remove(&m_queue, 0);
+  }
 
   /**
     The number of elements in the queue.
@@ -89,13 +101,57 @@ public:
   bool is_initialized() const { return m_queue.max_elements > 0; }
 
 private:
-  uchar            **m_sort_keys;
+  Key_type         **m_sort_keys;
   size_t             m_compare_length;
   keymaker_function  m_keymaker;
   Sort_param        *m_sort_param;
   st_queue           m_queue;
 };
 
+
+template<typename Element_type, typename Key_type>
+int Bounded_queue<Element_type, Key_type>::init(ha_rows max_elements,
+                                                uint offset_to_key,
+                                                pbool max_at_top,
+                                                queue_compare compare,
+                                                size_t compare_length,
+                                                keymaker_function keymaker,
+                                                Sort_param *sort_param,
+                                                Key_type **sort_keys)
+{
+  DBUG_ASSERT(sort_keys != NULL);
+
+  m_sort_keys=      sort_keys;
+  m_compare_length= compare_length;
+  m_keymaker=       keymaker;
+  m_sort_param=     sort_param;
+  // init_queue() takes an uint, and also does (max_elements + 1)
+  if (max_elements >= (UINT_MAX - 1))
+    return 1;
+  // We allocate space for one extra element, for replace when queue is full.
+  return init_queue(&m_queue, (uint) max_elements + 1, offset_to_key, max_at_top,
+                    compare, &m_compare_length);
+}
+
+
+template<typename Element_type, typename Key_type>
+void Bounded_queue<Element_type, Key_type>::push(Element_type *element)
+{
+  DBUG_ASSERT(is_initialized());
+  if (queue_is_full((&m_queue)))
+  {
+    uchar **pq_top= (uchar **) queue_top(&m_queue);
+    (*m_keymaker)(m_sort_param, *pq_top, (uchar*) element);
+    queue_replaced(&m_queue);
+  } else {
+    (*m_keymaker)(m_sort_param,
+                  (uchar*) m_sort_keys[m_queue.elements],
+                  (uchar*) element);
+    queue_insert(&m_queue, (uchar*)&m_sort_keys[m_queue.elements]);
+  }
+}
+
+
 /*
   Calculate cost of merge sort
 

=== modified file 'sql/filesort.cc'
--- a/sql/filesort.cc	2010-10-12 11:39:45 +0000
+++ b/sql/filesort.cc	2010-10-14 15:35:25 +0000
@@ -47,6 +47,10 @@
  */
 static double PQ_slowness= 2.0;
 
+#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
+template class Bounded_queue<uchar, uchar>;
+#endif
+
 /// How to write record_ref.
 #define WRITE_REF(file,from) \
 if (my_b_write((file),(uchar*) (from),param->ref_length)) \
@@ -60,7 +64,7 @@ static uchar *read_buffpek_from_file(IO_
 static ha_rows find_all_keys(Sort_param *param,SQL_SELECT *select,
                              uchar **sort_keys, IO_CACHE *buffer_file,
                              IO_CACHE *tempfile,
-                             Bounded_queue *pq,
+                             Bounded_queue<uchar, uchar> *pq,
                              ha_rows *found_rows);
 static int write_keys(Sort_param *param,uchar * *sort_keys,
                       uint count, IO_CACHE *buffer_file, IO_CACHE *tempfile);
@@ -162,7 +166,7 @@ ha_rows filesort(THD *thd, TABLE *table,
   Sort_param param;
   bool multi_byte_charset;
   ha_rows found_rows;
-  Bounded_queue pq;
+  Bounded_queue<uchar, uchar> pq;
 
   DBUG_ENTER("filesort");
   DBUG_EXECUTE("info",TEST_filesort(sortorder,s_length););
@@ -543,7 +547,7 @@ static ha_rows find_all_keys(Sort_param 
                              uchar **sort_keys,
                              IO_CACHE *buffpek_pointers,
                              IO_CACHE *tempfile,
-                             Bounded_queue *pq,
+                             Bounded_queue<uchar, uchar> *pq,
                              ha_rows *found_rows)
 {
   int error,flag,quick_select;

=== modified file 'unittest/gunit/bounded_queue-t.cc'
--- a/unittest/gunit/bounded_queue-t.cc	2010-10-12 11:39:45 +0000
+++ b/unittest/gunit/bounded_queue-t.cc	2010-10-14 15:35:25 +0000
@@ -18,10 +18,13 @@
 #include "my_config.h"
 #include <gtest/gtest.h>
 #include <algorithm>
+#include <stddef.h>
 
 #include "bounded_queue.h"
 #include "my_sys.h"
 
+void break_here() {}
+
 namespace {
 
 const int num_elements= 14;
@@ -35,14 +38,45 @@ int array_size(const T (&)[size])
 }
 
 
+struct Test_element
+{
+  Test_element()      { *this= -1; }
+  Test_element(int i) { *this= i; }
+
+  Test_element &operator=(int i)
+  {
+    val= i;
+    snprintf(text, array_size(text), "%4d", i);
+    return *this;
+  }
+
+  char text[8];
+  int  val;
+};
+
+
+struct Test_key
+{
+  Test_element *element;
+  int           key;
+};
+
+
 extern "C"
-int int_ptr_compare(void *cmp_arg, uchar *a, uchar *b)
+int test_key_compare(void *cmp_arg, uchar *a, uchar *b)
 {
   size_t first_arg= *(size_t*) cmp_arg;
   EXPECT_EQ(first_arg, sizeof(int));
 
-  int a_num= (**(int**)a);
-  int b_num= (**(int**)b);
+  Test_key **a_ptr= (Test_key**) a;
+  Test_key **b_ptr= (Test_key**) b;
+
+  int a_num= (*a_ptr)->key;
+  int b_num= (*b_ptr)->key;
+
+  //printf("compare (%p %p %d)   (%p %p %d)\n",
+  //a_ptr, *a_ptr, a_num, b_ptr, *b_ptr, b_num);
+
   if (a_num > b_num)
     return +1;
   if (a_num < b_num)
@@ -51,17 +85,23 @@ int int_ptr_compare(void *cmp_arg, uchar
 }
 
 
-// We use the data value itself as key.
+// We use the data value as key.
 void mock_keymaker(Sort_param *sp, uchar *to, uchar *ref_pos)
 {
-  memcpy(to, ref_pos, sizeof(int));
+  Test_element *element= (Test_element*) ref_pos;
+  int key_val= element->val;
+
+  Test_key *key= (Test_key*) to;
+  key->element= element;
+  key->key= key_val;
+  //printf("element %p key %p %d\n", element, key, key_val);
 }
 
 
 class Bounded_queue_test : public ::testing::Test
 {
 protected:
-  Bounded_queue_test() : m_element_size(sizeof(int))
+  Bounded_queue_test() : m_key_size(sizeof(int))
   {
   }
 
@@ -73,17 +113,26 @@ protected:
     std::random_shuffle(&m_test_data[0], &m_test_data[array_size(m_test_data)]);
 
     for (ix=0; ix < array_size(m_key_ptrs); ++ix)
-      m_key_ptrs[ix]= (uchar*) &m_key_data[ix];
+      m_key_ptrs[ix]= &m_key_data[ix];
+
+    for (ix=0; ix < array_size(m_key_data); ++ix)
+    {
+      m_key_data[ix].element= NULL;
+      m_key_data[ix].key= -1;
+    }
   }
 
   // Key pointers and data, used by the queue_xxx() functions.
-  uchar*        m_key_ptrs[num_keys];
-  int           m_key_data[num_keys];
+  Test_key *m_key_ptrs[num_keys+1];
+  int foo1[1024*16];
+  Test_key  m_key_data[num_keys+1];
+  int foo2[1024*16];
+
   // Some random intput data, to be sorted.
-  int           m_test_data[num_elements];
+  Test_element  m_test_data[num_elements];
 
-  size_t        m_element_size;
-  Bounded_queue m_queue;
+  size_t m_key_size;
+  Bounded_queue<Test_element, Test_key> m_queue;
 private:
   GTEST_DISALLOW_COPY_AND_ASSIGN_(Bounded_queue_test);
 };
@@ -99,8 +148,8 @@ typedef Bounded_queue_test Bounded_queue
 TEST_F(Bounded_queue_DeathTest, die_if_not_initialized)
 {
   ::testing::FLAGS_gtest_death_test_style = "threadsafe";
-  int foo= 1;
-  EXPECT_DEATH_IF_SUPPORTED(m_queue.push((uchar*) &foo),
+  Test_element foo= 1;
+  EXPECT_DEATH_IF_SUPPORTED(m_queue.push(&foo),
                             ".*Assertion .*is_initialized.*");
 }
 #endif  // !defined(DBUG_OFF)
@@ -112,8 +161,8 @@ TEST_F(Bounded_queue_DeathTest, die_if_n
 TEST_F(Bounded_queue_test, construct_and_destruct)
 {
   EXPECT_EQ(0, m_queue.init(num_elements/2, 0, TRUE,
-                            (queue_compare) (get_ptr_compare(m_element_size)),
-                            m_element_size,
+                            (queue_compare) (get_ptr_compare(m_key_size)),
+                            m_key_size,
                             &mock_keymaker, NULL, m_key_ptrs));
 }
 
@@ -124,12 +173,12 @@ TEST_F(Bounded_queue_test, construct_and
 TEST_F(Bounded_queue_test, too_many_elements)
 {
   EXPECT_EQ(1, m_queue.init(UINT_MAX, 0, TRUE,
-                            (queue_compare) (get_ptr_compare(m_element_size)),
-                            m_element_size,
+                            (queue_compare) (get_ptr_compare(m_key_size)),
+                            m_key_size,
                             &mock_keymaker, NULL, m_key_ptrs));
   EXPECT_EQ(1, m_queue.init(UINT_MAX - 1, 0, TRUE,
-                            (queue_compare) (get_ptr_compare(m_element_size)),
-                            m_element_size,
+                            (queue_compare) (get_ptr_compare(m_key_size)),
+                            m_key_size,
                             &mock_keymaker, NULL, m_key_ptrs));
 }
 
@@ -139,22 +188,22 @@ TEST_F(Bounded_queue_test, too_many_elem
  */
 TEST_F(Bounded_queue_test, push_and_pop)
 {
-  EXPECT_EQ(0, m_queue.init(num_elements/2, 0, TRUE, int_ptr_compare,
-                            m_element_size,
+  EXPECT_EQ(0, m_queue.init(num_elements/2, 0, TRUE, test_key_compare,
+                            m_key_size,
                             &mock_keymaker, NULL, m_key_ptrs));
   for (int ix= 0; ix < array_size(m_test_data); ++ix)
   {
-    m_queue.push((uchar*) &m_test_data[ix]);
+    m_queue.push(&m_test_data[ix]);
   }
-  int prev_element= num_elements;
-  int expected_value= num_elements / 2;
-  while (!m_queue.num_elements())
-  {
-    uchar *top_p= m_queue.pop();
-    int *top= *(int**) top_p;
-    EXPECT_GT(prev_element, *top);
-    EXPECT_EQ(expected_value--, *top);
-    prev_element= *top;
+  int expected_key_val= num_elements/2;
+  while (m_queue.num_elements() > 0)
+  {
+    Test_key **top= m_queue.pop();
+    int key_val= (*top)->key;
+    EXPECT_EQ(expected_key_val, key_val);
+    Test_element *element= (*top)->element;
+    EXPECT_EQ(expected_key_val, element->val);
+    --expected_key_val;
   }
 }
 
@@ -164,22 +213,26 @@ TEST_F(Bounded_queue_test, push_and_pop)
  */
 TEST_F(Bounded_queue_test, insert_and_sort)
 {
-  EXPECT_EQ(0, m_queue.init(num_elements/2, 0, TRUE, int_ptr_compare,
-                            m_element_size,
+  EXPECT_EQ(0, m_queue.init(num_elements/2, 0, TRUE, test_key_compare,
+                            m_key_size,
                             &mock_keymaker, NULL, m_key_ptrs));
   for (int ix= 0; ix < array_size(m_test_data); ++ix)
   {
-    m_queue.push((uchar*) &m_test_data[ix]);
+    m_queue.push(&m_test_data[ix]);
   }
-  uchar *base=  (uchar*) m_key_ptrs;
+
+  // Sort our keys as strings, so erase all the element pointers first.
+  uchar *base=  (uchar*) &m_key_ptrs[0];
   uint   items= m_queue.num_elements();
-  size_t size=  m_element_size;
+  size_t size=  sizeof(Test_key);
+  for (int ii= 0; ii < array_size(m_key_data); ++ii)
+    m_key_data[ii].element= NULL;
+
   my_string_ptr_sort(base, items, size);
   for (int ii= 0; ii < num_elements/2; ++ii)
   {
-    uchar *uchar_ptr= m_key_ptrs[ii];
-    int sorted_val= *(int*) uchar_ptr;
-    EXPECT_EQ(ii, sorted_val);
+    Test_key *sorted_key= m_key_ptrs[ii];
+    EXPECT_EQ(ii, sorted_key->key);
   }
 }
 
@@ -213,31 +266,31 @@ TEST(Cost_estimation_test, merge_many_bu
   Run the with 'bounded_queue-t --disable-tap-output' to see the
   millisecond output from Google Test.
  */
-const int num_rows= 100000;
+const int num_rows= 1000;
 const int limit= 100;
-const int num_iterations= 100;
+const int num_iterations= 10000;
 /*
   Test with Bounded_queue size == limit.
  */
 TEST(Bounded_queue_performance, with_small_queue)
 {
-  uchar* key_ptrs[limit+1];
-  int    key_data[limit+1];
+  int *key_ptrs[limit+1];
+  int  key_data[limit+1];
   for (int it= 0; it < num_iterations; ++it)
   {
     int    ix;
     for (ix=0; ix < array_size(key_ptrs); ++ix)
-      key_ptrs[ix]= (uchar*) &key_data[ix];
+      key_ptrs[ix]= &key_data[ix];
     srand(0);
-    Bounded_queue queue;
-    EXPECT_EQ(0, queue.init(limit, 0, TRUE, int_ptr_compare,
+    Bounded_queue<int, int> queue;
+    EXPECT_EQ(0, queue.init(limit, 0, TRUE, test_key_compare,
                             sizeof(int), &mock_keymaker, NULL, key_ptrs));
     for (ix= 0; ix < num_rows; ++ix)
     {
       int data= rand();
-      queue.push((uchar*) &data);
+      queue.push(&data);
     }
-    my_string_ptr_sort((uchar*) key_ptrs, queue.num_elements(), sizeof(int));
+    my_string_ptr_sort((uchar*) &key_ptrs[0], queue.num_elements(), sizeof(int));
   }
 }
 
@@ -245,25 +298,25 @@ TEST(Bounded_queue_performance, with_sma
 /*
   Test with Bounded_queue size == <number of rows>
  */
-uchar *key_ptrs[num_rows];
-int    key_data[num_rows];
+int *key_ptrs[num_rows];
+int  key_data[num_rows];
 TEST(Bounded_queue_performance, with_large_queue)
 {
   for (int it= 0; it < num_iterations; ++it)
   {
     int ix;
     for (ix=0; ix < array_size(key_ptrs); ++ix)
-      key_ptrs[ix]= (uchar*) &key_data[ix];
+      key_ptrs[ix]= &key_data[ix];
     srand(0);
-    Bounded_queue queue;
-    EXPECT_EQ(0, queue.init(num_rows, 0, TRUE, int_ptr_compare,
+    Bounded_queue<int, int> queue;
+    EXPECT_EQ(0, queue.init(num_rows, 0, TRUE, test_key_compare,
                             sizeof(int), &mock_keymaker, NULL, key_ptrs));
     for (ix= 0; ix < num_rows; ++ix)
     {
       int data= rand();
-      queue.push((uchar*) &data);
+      queue.push(&data);
     }
-    my_string_ptr_sort((uchar*) key_ptrs, queue.num_elements(), sizeof(int));
+    my_string_ptr_sort((uchar*) &key_ptrs[0], queue.num_elements(), sizeof(int));
   }
 }
 
@@ -277,14 +330,14 @@ TEST(Bounded_queue_performance, without_
   {
     int ix;
     for (ix=0; ix < array_size(key_ptrs); ++ix)
-      key_ptrs[ix]= (uchar*) &key_data[ix];
+      key_ptrs[ix]= &key_data[ix];
     srand(0);
     for (ix= 0; ix < num_rows; ++ix)
     {
       int data= rand();
       key_data[ix]= data;
     }
-    my_string_ptr_sort((uchar*) key_ptrs, num_rows, sizeof(int));
+    my_string_ptr_sort((uchar*) &key_ptrs[0], num_rows, sizeof(int));
   }
 }
 
@@ -298,7 +351,7 @@ TEST(Bounded_queue_performance, no_sorti
   {
     int ix;
     for (ix=0; ix < array_size(key_ptrs); ++ix)
-      key_ptrs[ix]= (uchar*) &key_data[ix];
+      key_ptrs[ix]= &key_data[ix];
     srand(0);
     for (ix= 0; ix < num_rows; ++ix)
     {


Attachment: [text/bzr-bundle] bzr/tor.didriksen@oracle.com-20101014153525-ebynhbs9p1icjgcr.bundle
Thread
bzr commit into mysql-next-mr-bugfixing branch (tor.didriksen:3227) Tor Didriksen14 Oct