<html dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<style type="text/css" id="owaParaStyle"></style>
</head>
<body fpstyle="1" ocsi="0">
<div style="direction: ltr;font-family: Tahoma;color: #000000;font-size: 10pt;">Filed a bug report, <a href="https://bugzilla.xamarin.com/show_bug.cgi?id=6406," target="_blank">https://bugzilla.xamarin.com/show_bug.cgi?id=6406,</a> that contains a sample of
 one of the lists that we are sorting.
<div><br>
</div>
<div> Martin<br>
<div style="font-family: Times New Roman; color: #000000; font-size: 16px">
<hr tabindex="-1">
<div id="divRpF731237" style="direction: ltr; "><font face="Tahoma" size="2" color="#000000"><b>From:</b> Marek Safar [marek.safar@gmail.com]<br>
<b>Sent:</b> Saturday, August 04, 2012 8:03 AM<br>
<b>To:</b> Martin Potter<br>
<b>Cc:</b> mono-devel-list@lists.ximian.com<br>
<b>Subject:</b> Re: [Mono-dev] Stack overflow in Array.Sort for large arrays<br>
</font><br>
</div>
<div></div>
<div>Hi,
<div><br>
</div>
<div>I cannot reproduce the issue. Could you fill a bug report with test case how to reproduce it.</div>
<div><br>
</div>
<div>Thanks</div>
<div>Marek<br>
<br>
<div class="gmail_quote">On Thu, Aug 2, 2012 at 7:21 PM, Martin Potter <<a href="mailto:martin.potter@logos.com" target="_blank">martin.potter@logos.com</a>> wrote:<br>
<blockquote class="gmail_quote">
<div>
<div>I am currently working on testing Mono to 2.11 with the hope to ease the transition to 2.12 when it is release. When testing, I found a nasty bug when sorting a large (228,000 elements) List<int> that resulted in a stack overflow. The partial stack trace
 from the crash:</div>
<div><br>
</div>
<div>
<div>System.Collections.Generic.List`1<int>:Sort ()</div>
<div>System.Array:Sort<int> (int[],int,int)</div>
<div>System.Array:Sort<int> (int[],int,int,System.Collections.Generic.IComparer`1<int>)</div>
<div>System.Array:SortImpl<int, int> (int[],int[],int,int,System.Collections.Generic.IComparer`1<int>)</div>
<div>System.Array:qsort<int, int> (int[],int[],int,int)</div>
<div>...</div>
<div>System.Array:qsort<int, int> (int[],int[],int,int)</div>
</div>
<div><br>
</div>
<div>Upon pulling the related sorting code from System.Array into a separate project, I determined that the stack overflow was occurring for this particular List/Array due to the fact that over half of the list elements were same number. It appears that this
 occurs as a result of the change to the various qsort methods in <a href="https://github.com/mono/mono/commit/d97cdb0c124729152be551c421c4a11732e45fc9" target="_blank">https://github.com/mono/mono/commit/d97cdb0c124729152be551c421c4a11732e45fc9</a>, which
 introduced a change in the treatment of elements with equal values. Reverting this commit fixes the stack overflow in the test app. In testing, I noticed that the old qsort code was significantly faster sorting when there were lots of duplicate values, was
 there are particular reason for changing the logic for dealing with equal values?</div>
<font color="#888888">
<div><br>
</div>
<div> Martin</div>
<div><br>
</div>
<div><br>
</div>
</font></div>
<br>
_______________________________________________<br>
Mono-devel-list mailing list<br>
<a href="mailto:Mono-devel-list@lists.ximian.com" target="_blank">Mono-devel-list@lists.ximian.com</a><br>
<a href="http://lists.ximian.com/mailman/listinfo/mono-devel-list" target="_blank">http://lists.ximian.com/mailman/listinfo/mono-devel-list</a><br>
<br>
</blockquote>
</div>
<br>
</div>
</div>
</div>
</div>
</div>
</body>
</html>