Re: Patch to huge memory consumption in LO Calc

Hello Kohei,

Thanks for your feedback. I'll do my best to be C++03 compliant for my 
next patches . So far i haven't found an equivalent to shrink_to_fit, 
but i think i have another to do it... i'll given it a look during this 
week end.

Meanwhile, i think we can improve things a little with the patch i 
attached to this email.

I had a look to the insert_empty_impl and set_new_block_to_middle method 
and i noticed that the way element_block_func::assign_values_from_block 
is called can be optimized. Especially when working with very large 
documents.

What is currently done after the new block is created is (in short) :

1/ "copy right part of the old block to the new one"
2/ "shrink left part"

When working with huge document (mine is ~100 000 rows and 100 columns), 
it happends very often to insert at a position at the very beginning. In 
such case, we will have to copy something like ~100 000 items to the new 
block and resize the old one to something like less than 10.

What i suggest is to add a test on left vs right block size, and then 
copy the smallest one instead of the right one.

Now the smaller block content is copyied to the new block, and the 
bigger on is either resized or items are poped from front. If needed 
pointer are swapped. This save some cycles when you work with huge sheets :)

I made some timing measurements, still using my 100 000 x 100 sheet and 
subtotal, average execution time of the ScTable::InsertRow method goes 
from 0.607 second down to 0.289 seconds (Phenom II box quad core and 
8gigs of ram).

If you agree with the solution i proposed, i'll check if other method 
need the same kind of optimization and i will submit a patch.

Cheers,

--
William BONNET
Directeur Technique / CTO LINAGORA
Linagora 80 rue Roque de Fillol / Puteaux 92800 F
Tél. +33 (0)810 251 251
GSM +33 (0)689 376 977
Twitter @wbonnet

http://www.linagora.com/ | http://www.08000linux.com/

Découvrez OBM, La messagerie Libre : http://www.obm.org/

La présente transmission contient des informations confidentielles appartenant à Linagora, 
exclusivement destinées au(x) destinataire(s) identifié(s) ci-dessus. Si vous n'en faites pas 
partie, toute reproduction, distribution ou divulgation de tout ou partie des informations de cette 
transmission, ou toute action effectuée sur la base de celles-ci vous sont formellement interdites. 
Si vous avez reçu cette transmission par erreur, nous vous remercions de nous en avertir et de la 
détruire de votre système d'information.

The present transmission contains privileged and confidential information belonging to Linagora, 
exclusively intended for the recipient(s) thereabove identified. If you are not one of these 
aforementioned recipients, any reproduction, distribution, disclosure of said information in whole 
or in part, as well as any action undertaken on the basis of said information are strictly 
prohibited. If you received the present transmission by mistake, please inform us and destroy it 
from your messenging and information systems.

--- multi_type_vector_def.inl.without.copy.modified     2014-05-29 10:19:05.515577222 +0200
+++ multi_type_vector_def.inl   2014-05-29 11:11:07.809888018 +0200
@@ -2523,12 +2523,42 @@
     m_blocks[block_index+1] = new block(length);
     m_blocks[block_index+2] = new block(size_blk_next);
 
-    block* blk_next = m_blocks[block_index+2];
-    blk_next->mp_data = 
element_block_func::create_new_block(mdds::mtv::get_block_type(*blk->mp_data), 0);
-    element_block_func::assign_values_from_block(*blk_next->mp_data, *blk->mp_data, size_blk_prev, 
size_blk_next);
-
-    element_block_func::resize_block(*blk->mp_data, size_blk_prev);
-    blk->m_size = size_blk_prev;
+    // If the block at block_ index keeps most of the data then we need then
+    // We need to allocate a new block, copy to the block the data then resize
+    // first block
+    //
+    // Otherwise, if the new block will contain most of the data, we need to 
+    // Create a new block, copy the data at begining to this one, then remove
+    // data from block at block_index and swap blocks
+    //
+    // This will really reduce the amount of data to be copied in some case
+    if (size_blk_prev > size_blk_next) {
+        block* blk_next = m_blocks[block_index+2];
+        blk_next->mp_data = 
element_block_func::create_new_block(mdds::mtv::get_block_type(*blk->mp_data), 0);
+        element_block_func::assign_values_from_block(*blk_next->mp_data, *blk->mp_data, 
size_blk_prev, size_blk_next);
+        element_block_func::resize_block(*blk->mp_data, size_blk_prev);
+        blk->m_size = size_blk_prev;
+    } else {
+        block* blk_keep = m_blocks[block_index];
+        block* blk_next = m_blocks[block_index+2];
+
+        // Create the block data for block at index + 2
+        blk_next->mp_data = 
element_block_func::create_new_block(mdds::mtv::get_block_type(*blk->mp_data), 0);
+
+        // Copy the data from "head" to the new block
+        element_block_func::assign_values_from_block(*blk_next->mp_data, *blk->mp_data, 0, 
size_blk_prev);
+        blk_next->m_size = size_blk_prev;
+
+        // Remove the size_blk_prev element from the current block
+        element_block_func::erase(*blk->mp_data, 0, size_blk_prev);
+
+        // Set the size of the current block to its new size ( what is after the new block )
+        blk->m_size = size_blk_next;
+
+        // And now let's swap the blocks...
+        m_blocks[block_index] = blk_next;
+        m_blocks[block_index+2] = blk_keep;
+    }
 
     m_cur_size += length;
 
@@ -2727,19 +2757,55 @@
         block* blk_lower = m_blocks[block_index+2];
         assert(blk_lower->m_size == lower_block_size);
         element_category_type cat = mtv::get_block_type(*blk->mp_data);
-        blk_lower->mp_data = element_block_func::create_new_block(cat, 0);
-        element_block_func::assign_values_from_block(
-            *blk_lower->mp_data, *blk->mp_data, lower_data_start, lower_block_size);
 
-        if (overwrite)
-        {
-            // Overwrite cells that will become empty.
-            element_block_func::overwrite_values(
-                *blk->mp_data, offset, new_block_size);
-        }
+        // If the block at block_ index keeps most of the data then we need then
+        // We need to allocate a new block, copy to the block the data then resize
+        // first block
+        //
+        // Otherwise, if the new block will contain most of the data, we need to 
+        // Create a new block, copy the data at begining to this one, then remove
+        // data from block at block_index and swap blocks
+        //
+        // This will really reduce the amount of data to be copied in some case
+        if (blk->m_size > lower_block_size) {
+            blk_lower->mp_data = element_block_func::create_new_block(cat, 0);
+            element_block_func::assign_values_from_block(*blk_lower->mp_data, *blk->mp_data, 
lower_data_start, lower_block_size);
+
+            if (overwrite)
+            {
+                // Overwrite cells that will become empty.
+                element_block_func::overwrite_values(*blk->mp_data, offset, new_block_size);
+            }
+
+            // Shrink the current data block.
+            element_block_func::resize_block(*blk->mp_data, offset); 
+
+        } else {
+            block* blk_keep = m_blocks[block_index];
 
-        // Shrink the current data block.
-        element_block_func::resize_block(*blk->mp_data, offset);
+            // Create the block data for block at index + 2
+            blk_lower->mp_data = 
element_block_func::create_new_block(mdds::mtv::get_block_type(*blk->mp_data), 0);
+
+            // Copy the data from "head" to the new block
+            element_block_func::assign_values_from_block(*blk_lower->mp_data, *blk->mp_data, 0, 
offset);
+            blk_lower->m_size = offset;
+
+            if (overwrite)
+            {
+                // Overwrite cells that will become empty.
+                element_block_func::overwrite_values(*blk->mp_data, offset, new_block_size);
+            }
+
+            // Remove the size_blk_prev element from the current block
+            element_block_func::erase(*blk->mp_data, 0, offset + new_block_size);
+
+            // Set the size of the current block to its new size ( what is after the new block )
+            blk->m_size = lower_block_size;
+
+            // And now let's swap the blocks...
+            m_blocks[block_index] = blk_lower;
+            m_blocks[block_index+2] = blk_keep;         
+        }
     }
 
     blk->m_size = offset;
@@ -4092,3 +4158,4 @@
 #endif
 
 }
+