Hi<br><br>as i said before, my whole reason for trying out the RBTree implementation was to be compare with .net performance for the<br>usecases mentioned (some kind of sorted order for the data) before.. i was trying to see if using a balanced tree would give me<br>


comparable results. on the other-hand,&nbsp; there is always a tradeoff with memory .. i dont remember seeing any major difference in memory<br>consumption between the basic implementation and .net (i mean in orders) for large datasets.. infact, if mem consumption is a big issue, then u could have a mixed implementation (messy to maintain ofcourse) and use the tree based storage purely for sorted data and the basic array implementation for others..<br>
<br>i guess this is something that needs to tested and figured out for different usecases and compared with .net..<br><br>cheers<br>senganal<br> <br><div class="gmail_quote">On Feb 5, 2008 5:19 AM, Konstantin Triger &lt;<a href="mailto:kostat@mainsoft.com">kostat@mainsoft.com</a>&gt; wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">








<div link="blue" vlink="purple" lang="EN-US">

<div>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">Hello,</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">&nbsp;</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">My major concern with an RBTree implementation is memory
consumption. Since you must create a node for each record, for a DataTable with
several hundreds thousands records memory size of RBTree may reach several MB.
Since it's common that DataTable has several constraints/views, memory
consumption may easily reach hundred MB or more... In addition, this will pose
an additional pressure on GC.</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">&nbsp;</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">Note that one of design goals behind array based architecture of
both DataContainers and indices was to minimize memory consumption due to the
calculations above.</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">&nbsp;</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">I think that we must run many different tests/scenarios before
we go with index datastructure redesign.</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">&nbsp;</span></p>

<p><span style="font-size: 10pt; color: rgb(31, 73, 125);">Regards,</span><span style="color: rgb(31, 73, 125);"></span></p>

<p><span style="font-size: 10pt; color: rgb(31, 73, 125);">Konstantin Triger</span><span style="font-size: 11pt; color: rgb(31, 73, 125);"></span></p>

<div style="border-style: none none none solid; border-color: -moz-use-text-color -moz-use-text-color -moz-use-text-color blue; border-width: medium medium medium 1.5pt; padding: 0in 0in 0in 4pt;">

<div>

<div style="border-style: solid none none; border-color: rgb(181, 196, 223) -moz-use-text-color -moz-use-text-color; border-width: 1pt medium medium; padding: 3pt 0in 0in;">

<p><b><span style="font-size: 10pt;">From:</span></b><span style="font-size: 10pt;"> senganal
thirunavakarasu [mailto:<a href="mailto:senganal@gmail.com" target="_blank">senganal@gmail.com</a>] <br>
<b>Sent:</b> Sunday, February 03, 2008 6:29 PM<br>
<b>To:</b> Nagappan A<br>
<b>Cc:</b> Konstantin Triger; Hubert FONGARNAND;
<a href="mailto:mono-devel-list@lists.ximian.com" target="_blank">mono-devel-list@lists.ximian.com</a><div><div></div><div class="Wj3C7c"><br>
<b>Subject:</b> Re: [Mono-dev] Performance problem with System.Data</div></div></span></p>

</div>

</div><div><div></div><div class="Wj3C7c">

<p>&nbsp;</p>

<p style="margin-bottom: 12pt;">Hi<br>
<br>
Its been quite a while (~1.5yrs) and i dont remember all the details , but will
try and explain whatever i remember..<br>
<br>
Well, the difference is when u have constraints on the datatable.. loading lots
of data is inherently slower in an array based storage as adding new data would
mean inserting data and not just appending it to the end.. ofcourse, if u
disable all constraints and load all the data and then enable the constraints,
things should be fine .. but on testing .net implementation, both the usecases
(with and without the constraints) were fast as compared the mono
implementation.. <br>
<br>
using a RBTree, inserting/searching are not expensive operations and hence
perform reasonably well in both the cases.. infact, its prob a lil bit slower
than the array implementation when the constraints are not enforced but thats
negligibly small ..<br>
<br>
the RBTree implementation that i had was pretty much a basic implementation
straight out of cormen book..&nbsp; the idea was to check if there will be any
significant effect.. It definitely could be better implemented, which is why i
had not checked it in at that time.. anyways, an RBTree or any balanced tree
based implementation would definitely be faster than the array based
implementation when it comes to loading/modifying the data in dataTable.. <br>
<br>
hope that helps.. <br>
<br>
cheers<br>
senganal</p>

<div>

<p>On Feb 3, 2008 4:03 AM, Nagappan A &lt;<a href="mailto:nagappan@gmail.com" target="_blank">nagappan@gmail.com</a>&gt;
wrote:</p>

<p>Hi Kosta,<br>
<br>
I haven&#39;t executed / compiled any of the programs :) FYI.<br>
<br>
Attaching what ever with me.<br>
<br>
Thanks<br>
<span style="color: rgb(136, 136, 136);">Nagappan</span></p>

<div>

<div>

<p style="margin-bottom: 12pt;">&nbsp;</p>

<div>

<p>On Feb 3, 2008 12:02 AM, Konstantin Triger &lt;<a href="mailto:kostat@mainsoft.com" target="_blank">kostat@mainsoft.com</a>&gt;
wrote:</p>

<div>

<div>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">Hi Nagappan,</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">&nbsp;</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">As far as I know, when adding
many records, the suggested usage of DataTable is [BeginLoadData -&gt; add
records -&gt; EndLoadData]. In this case the performance of both implementation
should be roughly similar, but the memory footprint of RBTree will be much
higher.</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">&nbsp;</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">Can you please post the
Senganal&#39;s test code?</span></p>

<p><span style="font-size: 11pt; color: rgb(31, 73, 125);">&nbsp;</span></p>

<p><span style="font-size: 10pt; color: rgb(31, 73, 125);">Regards,</span></p>

<p><span style="font-size: 10pt; color: rgb(31, 73, 125);">Konstantin Triger</span></p>

<div style="border-style: none none none solid; border-color: -moz-use-text-color -moz-use-text-color -moz-use-text-color blue; border-width: medium medium medium 1.5pt; padding: 0in 0in 0in 4pt;">

<div>

<div style="border-style: solid none none; border-color: -moz-use-text-color; border-width: 1pt medium medium; padding: 3pt 0in 0in;">

<p><b><span style="font-size: 10pt;">From:</span></b><span style="font-size: 10pt;"> Nagappan A [mailto:<a href="mailto:nagappan@gmail.com" target="_blank">nagappan@gmail.com</a>]
<br>
<b>Sent:</b> Saturday, February 02, 2008 11:39 PM<br>
<b>To:</b> Konstantin Triger<br>
<b>Cc:</b> Hubert FONGARNAND; <a href="mailto:mono-devel-list@lists.ximian.com" target="_blank">mono-devel-list@lists.ximian.com</a>; <a href="mailto:senganal@gmail.com" target="_blank">senganal@gmail.com</a><br>
<b>Subject:</b> Re: [Mono-dev] Performance problem with System.Data</span></p>

</div>

</div>

<p>&nbsp;</p>

<p style="margin-bottom: 12pt;">Hi Kosta,<br>
<br>
RBTree implementation is not directly related to this bug, but I was trying to
say, in general about the performance of System.Data.<br>
<br>
In general RBTree performance is much better than Array based. As per
Senganal&#39;s test result, for adding 1 million records, it took 40 minutes. With
RBTree implementation, he was able to do them in seconds.<br>
<br>
Adding senganal in CC.<br>
<br>
Thanks<br>
Nagappan</p>

<div>

<p>2008/2/2 Konstantin Triger &lt;<a href="mailto:kostat@mainsoft.com" target="_blank">kostat@mainsoft.com</a>&gt;:</p>

<div>

<p><span style="font-size: 10pt;">Hey Nagappan,<br>
<br>
Can you please explain<br>
1. How RBTree implementation will solve the issue in the bug?<br>
2. Why do you think RBTree implementation will be superior over Array in
performance?</span></p>

<div>

<p><span style="font-size: 10pt;"><br>
<br>
Regards,<br>
Konstantin Triger</span></p>

</div>

</div>

</div>

<p><br>
-- <br>
Linux Desktop Testing Project - <a href="http://ldtp.freedesktop.org" target="_blank">http://ldtp.freedesktop.org</a><br>
<a href="http://nagappanal.blogspot.com" target="_blank">http://nagappanal.blogspot.com</a>
</p>

</div>

</div>

</div>

</div>

<p><br>
<br clear="all">
<br>
-- <br>
Linux Desktop Testing Project - <a href="http://ldtp.freedesktop.org" target="_blank">http://ldtp.freedesktop.org</a><br>
<a href="http://nagappanal.blogspot.com" target="_blank">http://nagappanal.blogspot.com</a>
</p>

</div>

</div>

</div>

<p>&nbsp;</p>

</div></div></div>

</div>

</div>


</blockquote></div><br>