#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 Didriksen | 14 Oct |
