WT-1977 Improve the performance of getting snapshots with many sessions.

6 files changed, 71 insertions, 16 deletions

diff --git a/dist/s_string.ok b/dist/s_string.ok
index 31392df1d93..1e430efe403 100644
--- a/dist/s_string.ok
+++ b/dist/s_string.ok
@@ -607,6 +607,7 @@ icount
 idx
 ifdef's
 ikey
+impl
 incr
 incrementing
 indices
@@ -855,6 +856,7 @@ skiplists
 slotsp
 slvg
 snaplen
+snapsort
 snprintf
 sp
 spinlock
diff --git a/src/include/extern.h b/src/include/extern.h
index 93efcd6a84d..aafbc80e57e 100644
--- a/src/include/extern.h
+++ b/src/include/extern.h
@@ -659,7 +659,6 @@ extern void __wt_stat_refresh_dsrc_stats(void *stats_arg);
 extern void __wt_stat_aggregate_dsrc_stats(const void *child, const void *parent);
 extern void __wt_stat_init_connection_stats(WT_CONNECTION_STATS *stats);
 extern void __wt_stat_refresh_connection_stats(void *stats_arg);
-extern int WT_CDECL __wt_txnid_cmp(const void *v1, const void *v2);
 extern void __wt_txn_release_snapshot(WT_SESSION_IMPL *session);
 extern void __wt_txn_get_snapshot(WT_SESSION_IMPL *session);
 extern void __wt_txn_update_oldest(WT_SESSION_IMPL *session, int force);
diff --git a/src/include/misc.h b/src/include/misc.h
index 2808a64796a..1f3051e7f4d 100644
--- a/src/include/misc.h
+++ b/src/include/misc.h
@@ -159,6 +159,24 @@
 	}								\
 } while (0)
 
+/*
+ * Binary search for a key.
+ *
+ * The "compare_lt" argument is a function or macro that returns true when
+ * its first argument is less than its second argument.
+ */
+#define	WT_BINARY_SEARCH(key, arrayp, n, compare_lt, found) do {	\
+	uint32_t __base = 0, __indx = 0, __limit = (n) - 1;		\
+	for (; __limit != 0; __limit >>= 1) {				\
+		__indx = __base + (__limit >> 1);			\
+		if (compare_lt((arrayp)[__indx], key)) {		\
+			__base = __indx + 1;				\
+			--__limit;					\
+		}							\
+	}								\
+	found = ((n) > 0 && key == (arrayp)[__indx]);			\
+} while (0)
+
 /* Verbose messages. */
 #ifdef HAVE_VERBOSE
 #define	WT_VERBOSE_ISSET(session, f)					\
diff --git a/src/include/txn.h b/src/include/txn.h
index f44a02cc332..5f56ba4b03c 100644
--- a/src/include/txn.h
+++ b/src/include/txn.h
@@ -21,7 +21,7 @@
 	((t1) <= (t2))
 
 #define	WT_TXNID_LT(t1, t2)						\
-	((t1) != (t2) && WT_TXNID_LE(t1, t2))
+	((t1) < (t2))
 
 #define	WT_SESSION_TXN_STATE(s) (&S2C(s)->txn_global.states[(s)->id])
 
diff --git a/src/include/txn.i b/src/include/txn.i
index 7de93afc70c..56e0cdce66b 100644
--- a/src/include/txn.i
+++ b/src/include/txn.i
@@ -158,6 +158,7 @@ static inline int
 __wt_txn_visible(WT_SESSION_IMPL *session, uint64_t id)
 {
 	WT_TXN *txn;
+	int found;
 
 	txn = &session->txn;
 
@@ -208,8 +209,9 @@ __wt_txn_visible(WT_SESSION_IMPL *session, uint64_t id)
 	if (txn->snapshot_count == 0 || WT_TXNID_LT(id, txn->snap_min))
 		return (1);
 
-	return (bsearch(&id, txn->snapshot, txn->snapshot_count,
-	    sizeof(uint64_t), __wt_txnid_cmp) == NULL);
+	WT_BINARY_SEARCH(
+	    id, txn->snapshot, txn->snapshot_count, WT_TXNID_LT, found);
+	return (!found);
 }
 
 /*
diff --git a/src/txn/txn.c b/src/txn/txn.c
index 5bf7920f6da..329f7deb59d 100644
--- a/src/txn/txn.c
+++ b/src/txn/txn.c
@@ -9,18 +9,54 @@
 #include "wt_internal.h"
 
 /*
- * __wt_txnid_cmp --
- *	Compare transaction IDs for sorting / searching.
+ * __snapsort_partition --
+ *	Custom quick sort partitioning for snapshots.
  */
-int WT_CDECL
-__wt_txnid_cmp(const void *v1, const void *v2)
+static uint32_t
+__snapsort_partition(uint64_t *array, uint32_t f, uint32_t l, uint64_t pivot)
 {
-	uint64_t id1, id2;
+	uint32_t i = f - 1, j = l + 1;
+
+	for (;;) {
+		while (pivot < array[--j])
+			;
+		while (array[++i] < pivot)
+			;
+		if (i<j) {
+			uint64_t tmp = array[i];
+			array[i] = array[j];
+			array[j] = tmp;
+		} else
+			return (j);
+	}
+}
 
-	id1 = *(uint64_t *)v1;
-	id2 = *(uint64_t *)v2;
+/*
+ * __snapsort_impl --
+ *	Custom quick sort implementation for snapshots.
+ */
+static void
+__snapsort_impl(uint64_t *array, uint32_t f, uint32_t l)
+{
+	while (f + 16 < l) {
+		uint64_t v1 = array[f], v2 = array[l], v3 = array[(f + l)/2];
+		uint64_t median = v1 < v2 ?
+		    (v3 < v1 ? v1 : WT_MIN(v2, v3)) :
+		    (v3 < v2 ? v2 : WT_MIN(v1, v3));
+		uint32_t m = __snapsort_partition(array, f, l, median);
+		__snapsort_impl(array, f, m);
+		f = m + 1;
+	}
+}
 
-	return ((id1 == id2) ? 0 : WT_TXNID_LT(id1, id2) ? -1 : 1);
+/*
+ * __snapsort --
+ *	Sort an array of transaction IDs.
+ */
+void __snapsort(uint64_t *array, uint32_t size)
+{
+	__snapsort_impl(array, 0, size - 1);
+	WT_INSERTION_SORT(array, size, uint64_t, WT_TXNID_LT);
 }
 
 /*
@@ -34,10 +70,8 @@ __txn_sort_snapshot(WT_SESSION_IMPL *session, uint32_t n, uint64_t snap_max)
 
 	txn = &session->txn;
 
-	if (n <= 10)
-		WT_INSERTION_SORT(txn->snapshot, n, uint64_t, WT_TXNID_LT);
-	else
-		qsort(txn->snapshot, n, sizeof(uint64_t), __wt_txnid_cmp);
+	if (n > 1)
+		__snapsort(txn->snapshot, n);
 
 	txn->snapshot_count = n;
 	txn->snap_max = snap_max;