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
}
+
_______________________________________________
LibreOffice mailing list
LibreOffice@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/libreoffice
