summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJan Holesovsky <kendy@suse.cz>2013-01-31 02:18:05 +0100
committerJan Holesovsky <kendy@suse.cz>2013-01-31 02:37:01 +0100
commitf9f33617b45dc927b5605baf8c07da7664ec1b83 (patch)
treed8d299b619134ed227d383be981847719ba22e3f
parente11ca8aa63172c5b0d30f68fd9c796f276c3dd26 (diff)
Dense B+ tree: A small optimization of appends.
Append (ie. Insert() at Count()) is supposedly a critical operation, so let's optimize for that a bit - cache the last leaf. And this gets us where we want to be (1000000 of operations): BigPtrArray - append: 45 msec BigPtrArray - insert at front: 6541 msec DenseBPlusTree - append: 59 msec DenseBPlusTree - insert at front: 169 msec Change-Id: Id66ad6f37b8a08416a874af6397e113aecfd6b0e
-rw-r--r--sw/inc/densebplustree.cxx13
-rw-r--r--sw/inc/densebplustree.hxx3
2 files changed, 14 insertions, 2 deletions
diff --git a/sw/inc/densebplustree.cxx b/sw/inc/densebplustree.cxx
index 62c2394a145c..c936ad8a0ee2 100644
--- a/sw/inc/densebplustree.cxx
+++ b/sw/inc/densebplustree.cxx
@@ -146,6 +146,7 @@ struct DBPTreeNode
template < class Key, class Value >
DenseBPlusTree< Key, Value >::DenseBPlusTree()
: m_pRoot( new DBPTreeNode< Key, Value > ),
+ m_pLastLeaf( m_pRoot ),
m_nCount( 0 ),
m_nDepth( 1 )
{
@@ -161,8 +162,12 @@ template < class Key, class Value >
void DenseBPlusTree< Key, Value >::Insert( const Value& rValue, Key nPos )
{
NodeWithIndex pParents[ m_nDepth ];
- int nParentsLength;
- NodeWithIndex aLeaf = findLeaf( nPos, pParents, nParentsLength );
+ int nParentsLength = 0;
+ NodeWithIndex aLeaf( m_pLastLeaf, m_pLastLeaf->m_nUsed );
+
+ // if we are lucky, we just append, otherwise do the full job
+ if ( nPos != m_nCount || m_pLastLeaf->m_nUsed == sOrder )
+ aLeaf = findLeaf( nPos, pParents, nParentsLength );
if ( aLeaf.pNode->m_nUsed < sOrder )
{
@@ -316,6 +321,10 @@ DBPTreeNode< Key, Value >* DenseBPlusTree< Key, Value >::splitNode( DBPTreeNode<
DBPTreeNode< Key, Value > *pNewNode = new DBPTreeNode< Key, Value >;
int offset = pNewNode->copyFromSplitNode( pNode );
+ // update the last leaf if necessary
+ if ( pNode == m_pLastLeaf )
+ m_pLastLeaf = pNewNode;
+
if ( nParentsLength == 0 )
{
// we have to create a new root
diff --git a/sw/inc/densebplustree.hxx b/sw/inc/densebplustree.hxx
index 26d1dfbd0ccf..027e2d857674 100644
--- a/sw/inc/densebplustree.hxx
+++ b/sw/inc/densebplustree.hxx
@@ -103,6 +103,9 @@ private:
/// Root of the tree.
DBPTreeNode< Key, Value > *m_pRoot;
+ /// The last leaf node - only a small optimization for appends.
+ DBPTreeNode< Key, Value > *m_pLastLeaf;
+
/// Amount of values that we contain.
Key m_nCount;