<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">

<head>
<meta http-equiv=Content-Type content="text/html; charset=windows-1252">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
 /* Font Definitions */
 @font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
        {font-family:Tahoma;
        panose-1:2 11 6 4 3 5 4 4 2 4;}
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0in;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
p
        {mso-style-priority:99;
        mso-margin-top-alt:auto;
        margin-right:0in;
        mso-margin-bottom-alt:auto;
        margin-left:0in;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
span.EmailStyle18
        {mso-style-type:personal-reply;
        font-family:"Calibri","sans-serif";
        color:#1F497D;}
.MsoChpDefault
        {mso-style-type:export-only;}
@page Section1
        {size:8.5in 11.0in;
        margin:1.0in 1.25in 1.0in 1.25in;}
div.Section1
        {page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
 <o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
 <o:shapelayout v:ext="edit">
  <o:idmap v:ext="edit" data="1" />
 </o:shapelayout></xml><![endif]-->
</head>

<body lang=EN-US link=blue vlink=purple>

<div class=Section1>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Hello,<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>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.<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>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.<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>I think that we must run many different tests/scenarios before
we go with index datastructure redesign.<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#1F497D'>Regards,</span><span style='color:#1F497D'><o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif";
color:#1F497D'>Konstantin Triger</span><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'><o:p></o:p></span></p>

<div style='border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt'>

<div>

<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0in 0in 0in'>

<p class=MsoNormal><b><span style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span></b><span
style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'> senganal
thirunavakarasu [mailto:senganal@gmail.com] <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;
mono-devel-list@lists.ximian.com<br>
<b>Subject:</b> Re: [Mono-dev] Performance problem with System.Data<o:p></o:p></span></p>

</div>

</div>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

<p class=MsoNormal style='margin-bottom:12.0pt'>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<o:p></o:p></p>

<div>

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

<p class=MsoNormal>Hi Kosta,<br>
<br>
I haven't executed / compiled any of the programs :) FYI.<br>
<br>
Attaching what ever with me.<br>
<br>
Thanks<br>
<span style='color:#888888'>Nagappan</span><o:p></o:p></p>

<div>

<div>

<p class=MsoNormal style='margin-bottom:12.0pt'><o:p>&nbsp;</o:p></p>

<div>

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

<div>

<div>

<p><span style='font-size:11.0pt;color:#1F497D'>Hi Nagappan,</span><o:p></o:p></p>

<p><span style='font-size:11.0pt;color:#1F497D'>&nbsp;</span><o:p></o:p></p>

<p><span style='font-size:11.0pt;color:#1F497D'>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><o:p></o:p></p>

<p><span style='font-size:11.0pt;color:#1F497D'>&nbsp;</span><o:p></o:p></p>

<p><span style='font-size:11.0pt;color:#1F497D'>Can you please post the
Senganal's test code?</span><o:p></o:p></p>

<p><span style='font-size:11.0pt;color:#1F497D'>&nbsp;</span><o:p></o:p></p>

<p><span style='font-size:10.0pt;color:#1F497D'>Regards,</span><o:p></o:p></p>

<p><span style='font-size:10.0pt;color:#1F497D'>Konstantin Triger</span><o:p></o:p></p>

<div style='border:none;border-left:solid windowtext 1.5pt;padding:0in 0in 0in 4.0pt;
border-color:-moz-use-text-color -moz-use-text-color -moz-use-text-color blue'>

<div>

<div style='border:none;border-top:solid windowtext 1.0pt;padding:3.0pt 0in 0in 0in;
border-color:-moz-use-text-color -moz-use-text-color'>

<p><b><span style='font-size:10.0pt'>From:</span></b><span style='font-size:
10.0pt'> 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><o:p></o:p></p>

</div>

</div>

<p>&nbsp;<o:p></o:p></p>

<p style='margin-bottom:12.0pt'>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'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<o:p></o:p></p>

<div>

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

<div>

<p><span style='font-size:10.0pt'>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><o:p></o:p></p>

<div>

<p><span style='font-size:10.0pt'><br>
<br>
Regards,<br>
Konstantin Triger</span><o:p></o:p></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>
<o:p></o:p></p>

</div>

</div>

</div>

</div>

<p class=MsoNormal><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>
<o:p></o:p></p>

</div>

</div>

</div>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

</div>

</div>

</body>

</html>