List:Commits« Previous MessageNext Message »
From:Sunny Bains Date:June 10 2010 2:46am
Subject:bzr commit into mysql-next-mr-innodb branch (Sunny.Bains:3229)
View as plain text  
#At file:///Users/sunny/innodb/bzr-new/next-mr/ based on revid:vasil.dimov@stripped

 3229 Sunny Bains	2010-06-10
      Use a binary search to check whether a transaction sees another transaction's
      updates. Previously we used a linear search and at higher threads it had
      become a bottleneck.
      
      rb://375, Reviewed by Jimmy Yang.

    modified:
      storage/innobase/include/read0read.h
      storage/innobase/include/read0read.ic
      storage/innobase/include/ut0byte.h
      storage/innobase/include/ut0byte.ic
      storage/innobase/read/read0read.c
=== modified file 'storage/innobase/include/read0read.h'
--- a/storage/innobase/include/read0read.h	revid:vasil.dimov@stripped
+++ b/storage/innobase/include/read0read.h	revid:sunny.bains@stripped
@@ -146,7 +146,7 @@ struct read_view_struct{
 				this is the "low water mark". */
 	ulint		n_trx_ids;
 				/*!< Number of cells in the trx_ids array */
-	trx_id_t*	trx_ids;/*!< Additional trx ids which the read should
+	ib_int64_t*	trx_ids;/*!< Additional trx ids which the read should
 				not see: typically, these are the active
 				transactions at the time when the read is
 				serialized, except the reading transaction

=== modified file 'storage/innobase/include/read0read.ic'
--- a/storage/innobase/include/read0read.ic	revid:vasil.dimov@stripped
+++ b/storage/innobase/include/read0read.ic	revid:sunny.bains@stripped
@@ -27,7 +27,7 @@ Created 2/16/1997 Heikki Tuuri
 Gets the nth trx id in a read view.
 @return	trx id */
 UNIV_INLINE
-trx_id_t
+ib_int64_t
 read_view_get_nth_trx_id(
 /*=====================*/
 	const read_view_t*	view,	/*!< in: read view */
@@ -46,7 +46,7 @@ read_view_set_nth_trx_id(
 /*=====================*/
 	read_view_t*	view,	/*!< in: read view */
 	ulint		n,	/*!< in: position */
-	trx_id_t	trx_id)	/*!< in: trx id to set */
+	ib_int64_t	trx_id)	/*!< in: trx id to set */
 {
 	ut_ad(n < view->n_trx_ids);
 
@@ -60,38 +60,39 @@ UNIV_INLINE
 ibool
 read_view_sees_trx_id(
 /*==================*/
-	const read_view_t*	view,	/*!< in: read view */
-	trx_id_t		trx_id)	/*!< in: trx id */
+	const read_view_t*	view,		/*!< in: read view */
+	trx_id_t		in_trx_id)	/*!< in: trx id */
 {
-	ulint	n_ids;
-	int	cmp;
-	ulint	i;
-
-	if (ut_dulint_cmp(trx_id, view->up_limit_id) < 0) {
-
+	/* This value is the same as view->trx_ids[view->n_trx_ids-1]. */
+	if (ut_dulint_cmp(in_trx_id, view->up_limit_id) < 0) {
 		return(TRUE);
-	}
-
-	if (ut_dulint_cmp(trx_id, view->low_limit_id) >= 0) {
-
+	} else if (ut_dulint_cmp(in_trx_id, view->low_limit_id) >= 0) {
 		return(FALSE);
-	}
-
-	/* We go through the trx ids in the array smallest first: this order
-	may save CPU time, because if there was a very long running
-	transaction in the trx id array, its trx id is looked at first, and
-	the first two comparisons may well decide the visibility of trx_id. */
-
-	n_ids = view->n_trx_ids;
-
-	for (i = 0; i < n_ids; i++) {
-
-		cmp = ut_dulint_cmp(
-			trx_id,
-			read_view_get_nth_trx_id(view, n_ids - i - 1));
-		if (cmp <= 0) {
-			return(cmp < 0);
-		}
+	} else {
+		ulint		lower = 0;
+		ulint		upper = view->n_trx_ids - 1;
+		ib_int64_t	trx_id = ut_conv_dulint_to_longlong(in_trx_id);
+
+		ut_a(view->n_trx_ids > 0);
+
+		do {
+			ib_int64_t	cmp;
+			ulint		mid = (lower + upper) >> 1;
+
+			cmp = view->trx_ids[mid] - trx_id;
+
+			if (cmp == 0) {
+				return(FALSE);
+			} else if (cmp < 0) {
+				if (mid > 0) {
+					upper = mid - 1;
+				} else {
+					break;
+				}
+			} else {
+				lower = mid + 1;
+			}
+		} while (lower <= upper);
 	}
 
 	return(TRUE);

=== modified file 'storage/innobase/include/ut0byte.h'
--- a/storage/innobase/include/ut0byte.h	revid:vasil.dimov@stripped
+++ b/storage/innobase/include/ut0byte.h	revid:sunny.bains@stripped
@@ -81,6 +81,14 @@ ut_conv_dulint_to_longlong(
 /*=======================*/
 	dulint	d);	/*!< in: dulint */
 /*******************************************************//**
+Converts a ib_int64_t to a dulint (a struct of 2 ulints).
+@return	value in dulint type */
+UNIV_INLINE
+dulint
+ut_conv_longlong_to_dulint(
+/*=======================*/
+	ib_int64_t	v);	/*!< in: ib_int64_t*/
+/*******************************************************//**
 Tests if a dulint is zero.
 @return	TRUE if zero */
 UNIV_INLINE

=== modified file 'storage/innobase/include/ut0byte.ic'
--- a/storage/innobase/include/ut0byte.ic	revid:vasil.dimov@stripped
+++ b/storage/innobase/include/ut0byte.ic	revid:sunny.bains@stripped
@@ -83,6 +83,23 @@ ut_conv_dulint_to_longlong(
 }
 
 /*******************************************************//**
+Converts a ib_int64_t to a dulint (a struct of 2 ulints).
+@return	value in dulint type */
+UNIV_INLINE
+dulint
+ut_conv_longlong_to_dulint(
+/*=======================*/
+	ib_int64_t	v)	/*!< in: ib_int64_t*/
+{
+	dulint          d;
+
+	d.high = v >> 32;
+	d.low  = v & 0xFFFFFFFF;
+
+	return(d);
+}
+
+/*******************************************************//**
 Tests if a dulint is zero.
 @return	TRUE if zero */
 UNIV_INLINE

=== modified file 'storage/innobase/read/read0read.c'
--- a/storage/innobase/read/read0read.c	revid:vasil.dimov@stripped
+++ b/storage/innobase/read/read0read.c	revid:sunny.bains@stripped
@@ -152,7 +152,7 @@ read_view_create_low(
 	view = mem_heap_alloc(heap, sizeof(read_view_t));
 
 	view->n_trx_ids = n;
-	view->trx_ids = mem_heap_alloc(heap, n * sizeof *view->trx_ids);
+	view->trx_ids = mem_heap_alloc(heap, n * sizeof(*view->trx_ids));
 
 	return(view);
 }
@@ -179,6 +179,7 @@ read_view_oldest_copy_or_open_new(
 	ulint		insert_done	= 0;
 	ulint		n;
 	ulint		i;
+	ib_int64_t	trx_id;
 
 	ut_ad(mutex_own(&kernel_mutex));
 
@@ -189,9 +190,11 @@ read_view_oldest_copy_or_open_new(
 		return(read_view_open_now(cr_trx_id, heap));
 	}
 
+	trx_id = ut_conv_dulint_to_longlong(old_view->creator_trx_id);
+
 	n = old_view->n_trx_ids;
 
-	if (!ut_dulint_is_zero(old_view->creator_trx_id)) {
+	if (trx_id != 0) {
 		n++;
 	} else {
 		needs_insert = FALSE;
@@ -206,12 +209,9 @@ read_view_oldest_copy_or_open_new(
 	while (i < n) {
 		if (needs_insert
 		    && (i >= old_view->n_trx_ids
-			|| ut_dulint_cmp(old_view->creator_trx_id,
-					 read_view_get_nth_trx_id(old_view, i))
-			> 0)) {
+			|| trx_id > read_view_get_nth_trx_id(old_view, i))) {
 
-			read_view_set_nth_trx_id(view_copy, i,
-						 old_view->creator_trx_id);
+			read_view_set_nth_trx_id(view_copy, i, trx_id);
 			needs_insert = FALSE;
 			insert_done = 1;
 		} else {
@@ -232,8 +232,8 @@ read_view_oldest_copy_or_open_new(
 
 	if (n > 0) {
 		/* The last active transaction has the smallest id: */
-		view_copy->up_limit_id = read_view_get_nth_trx_id(
-			view_copy, n - 1);
+		view_copy->up_limit_id = ut_conv_longlong_to_dulint(
+			read_view_get_nth_trx_id(view_copy, n - 1));
 	} else {
 		view_copy->up_limit_id = old_view->up_limit_id;
 	}
@@ -284,7 +284,9 @@ read_view_open_now(
 		    && (trx->conc_state == TRX_ACTIVE
 			|| trx->conc_state == TRX_PREPARED)) {
 
-			read_view_set_nth_trx_id(view, n, trx->id);
+			read_view_set_nth_trx_id(
+				view, n,
+				ut_conv_dulint_to_longlong(trx->id));
 
 			n++;
 
@@ -307,7 +309,8 @@ read_view_open_now(
 
 	if (n > 0) {
 		/* The last active transaction has the smallest id: */
-		view->up_limit_id = read_view_get_nth_trx_id(view, n - 1);
+		view->up_limit_id = ut_conv_longlong_to_dulint(
+			read_view_get_nth_trx_id(view, n - 1));
 	} else {
 		view->up_limit_id = view->low_limit_id;
 	}
@@ -390,8 +393,7 @@ read_view_print(
 
 	for (i = 0; i < n_ids; i++) {
 		fprintf(stderr, "Read view trx id " TRX_ID_FMT "\n",
-			TRX_ID_PREP_PRINTF(
-				read_view_get_nth_trx_id(view, i)));
+				read_view_get_nth_trx_id(view, i));
 	}
 }
 
@@ -404,7 +406,7 @@ UNIV_INTERN
 cursor_view_t*
 read_cursor_view_create_for_mysql(
 /*==============================*/
-	trx_t*	cr_trx)	/*!< in: trx where cursor view is created */
+	trx_t*		cr_trx)	/*!< in: trx where cursor view is created */
 {
 	cursor_view_t*	curview;
 	read_view_t*	view;
@@ -452,7 +454,9 @@ read_cursor_view_create_for_mysql(
 		if (trx->conc_state == TRX_ACTIVE
 		    || trx->conc_state == TRX_PREPARED) {
 
-			read_view_set_nth_trx_id(view, n, trx->id);
+			read_view_set_nth_trx_id(
+				view, n,
+				ut_conv_dulint_to_longlong(trx->id));
 
 			n++;
 
@@ -475,7 +479,8 @@ read_cursor_view_create_for_mysql(
 
 	if (n > 0) {
 		/* The last active transaction has the smallest id: */
-		view->up_limit_id = read_view_get_nth_trx_id(view, n - 1);
+		view->up_limit_id = ut_conv_longlong_to_dulint(
+			read_view_get_nth_trx_id(view, n - 1));
 	} else {
 		view->up_limit_id = view->low_limit_id;
 	}


Attachment: [text/bzr-bundle] bzr/sunny.bains@oracle.com-20100610024504-2n0m468awzr1xmeq.bundle
Thread
bzr commit into mysql-next-mr-innodb branch (Sunny.Bains:3229) Sunny Bains10 Jun