summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJan Holesovsky <kendy@suse.cz>2013-01-31 20:23:20 +0100
committerJan Holesovsky <kendy@suse.cz>2013-01-31 20:23:20 +0100
commit2bcd2598ad45738079889752577fa1cb6f7e0c93 (patch)
treea8ef2189ae103001d2abfa98687434036cc5c866
parent40605ecc1faa02939e5e03abecdadbaea6afbe12 (diff)
Dense B+ tree: Use binary search when searching in the Keys inside nodes.
Also started measuring one more case - inserting in the middle. Before this change, it took about 100 msec. BigPtrArray - append: 45 msec BigPtrArray - insert at front: 6510 msec BigPtrArray - insert in the middle: 3043 msec DenseBPlusTree - append: 48 msec DenseBPlusTree - insert at front: 167 msec DenseBPlusTree - insert in the middle: 90 msec Change-Id: I2cc0a151b26931d90c8915a6ba879cf0e386b3b2
-rw-r--r--sw/inc/densebplustree.cxx25
-rw-r--r--sw/qa/core/densebplustree-test.cxx14
2 files changed, 34 insertions, 5 deletions
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index a1865462b11d..4ea38928aad8 100644
--- a/sw/inc/densebplustree.cxx
+++ b/sw/inc/densebplustree.cxx
@@ -289,13 +289,28 @@ typename DenseBPlusTree< Key, Value >::NodeWithIndex DenseBPlusTree< Key, Value
DBPTreeNode< Key, Value > *pNode = m_pRoot;
rParentsLength = 0;
- // recursion is nice for the alg. description, but for implementation, we
- // want to unwind it
+ // traverse from the root to the leaves
while ( pNode->m_bIsInternal )
{
- int i = 0;
- while ( i < pNode->m_nUsed - 1 && pNode->m_pKeys[ i ] <= nPos )
- ++i;
+ int i;
+ if ( pNode->m_nUsed < 2 || nPos < pNode->m_pKeys[ 0 ] ) // nPos too small, we continue leftmost
+ i = 0;
+ else if ( pNode->m_pKeys[ pNode->m_nUsed - 2 ] <= nPos ) // nPos is too big, continue rightmost
+ i = pNode->m_nUsed - 1;
+ else
+ {
+ // binary search, the values are ordered
+ i = 1;
+ int max = pNode->m_nUsed - 2;
+ while ( i < max )
+ {
+ int pivot = i + ( max - i ) / 2;
+ if ( pNode->m_pKeys[ pivot ] <= nPos )
+ i = pivot + 1;
+ else
+ max = pivot;
+ }
+ }
// m_pKeys in children are relative
if ( i > 0 )
diff --git a/sw/qa/core/densebplustree-test.cxx b/sw/qa/core/densebplustree-test.cxx
index 0ea0d8effd92..38e9501fbd58 100644
--- a/sw/qa/core/densebplustree-test.cxx
+++ b/sw/qa/core/densebplustree-test.cxx
@@ -70,6 +70,13 @@ int main( int, char** )
print_time( "BigPtrArray - insert at front", tv_before, tv_after );
gettimeofday( &tv_before, NULL );
+ BigPtrArray bparr3;
+ for ( int i = 0; i < 1000000; i++ )
+ bparr3.Insert( new BigPtrEntryMock(i), bparr3.Count() / 2 );
+ gettimeofday( &tv_after, NULL );
+ print_time( "BigPtrArray - insert in the middle", tv_before, tv_after );
+
+ gettimeofday( &tv_before, NULL );
DenseBPlusTree< int, BigPtrEntryMock* > aTest;
for ( int i = 0; i < 1000000; ++i )
aTest.Insert( new BigPtrEntryMock(i), aTest.Count() );
@@ -82,6 +89,13 @@ int main( int, char** )
aTest2.Insert( new BigPtrEntryMock(i), 0 );
gettimeofday( &tv_after, NULL );
print_time( "DenseBPlusTree - insert at front", tv_before, tv_after );
+
+ gettimeofday( &tv_before, NULL );
+ DenseBPlusTree< int, BigPtrEntryMock* > aTest3;
+ for ( int i = 0; i < 1000000; ++i )
+ aTest3.Insert( new BigPtrEntryMock(i), aTest3.Count() / 2 );
+ gettimeofday( &tv_after, NULL );
+ print_time( "DenseBPlusTree - insert in the middle", tv_before, tv_after );
#endif
#if 0