<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;">
<div>Forgot to cc the list, sorry for the duplicate Marek.</div>
<div><br>
</div>
Marek,
<div><br>
</div>
<div>When running Mono from the command line, it appears that the stack limit is not reached as quickly as when running embedded or on a ThreadPool thread like we do in our application. Running from the command line, it takes a much larger array to reach stack
 overflow, but it will eventually hit that limit.</div>
<div><br>
</div>
<div>Are you able to answer the question as to why the change was made? It does not seem like an optimization as the commit states. Using the actual 228299 element list, which is just one example of the type of data we are sorting, Mono 2.10.9 takes 00.0382963
 seconds to sort, Mono 2.11.2 takes 17.293864 seconds to sort; this seems less than optimal and is a huge concern for us.</div>
<div><br>
</div>
<div>I am not at home at the moment where I have access to the actual array values, but will file a bug when I am at home again. Until then, the following code will reproduce the issue for me running Mono 2.11.2 built from source on Mac OS X:</div>
<div><br>
</div>
<div>
<div>using System;</div>
<div>using System.Collections.Generic;</div>
<div>using System.Threading;</div>
<div><br>
</div>
<div>namespace SortCrash</div>
<div>{</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>class Program</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>{</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>static ManualResetEvent s_wait;</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>static void Main (string[] args)</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>{</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>s_wait = new ManualResetEvent(false);</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>ThreadPool.QueueUserWorkItem(Sort);</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>s_wait.WaitOne();</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>}</div>
<div><br>
</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>static void Sort(object state)</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>{</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>List<int> ints = new List<int>();</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>for (int i = 0; i < 50000; i++)</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>ints.Add(1);</div>
<div><br>
</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>ints.Sort();</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>s_wait.Set();</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>}</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span>}</div>
<div>}</div>
<div><br>
</div>
<div>I have updated the various qsort methods on our fork to their state prior to the optimization commit, added back the Insertion sort optimization (along with adding it to the non-generic qsort method) and modified the algorithm to only recurse on the smaller
 partition, limiting the potential for stack overflow. These changes are available at <a href="https://github.com/LogosBible/mono/commit/d4d4d0768a39881fd8a12818be363139a37c3da3" target="_blank" title="https://github.com/LogosBible/mono/commit/d4d4d0768a39881fd8a12818be363139a37c3da3
Cmd+Click to follow link">https://github.com/LogosBible/mono/commit/d4d4d0768a39881fd8a12818be363139a37c3da3</a> if
 you are interested.</div>
<div><br>
</div>
<div>Thanks,</div>
<div>Martin</div>
</div>
<div style="font-family: Times New Roman; color: #000000; font-size: 16px">
<hr tabindex="-1">
<div id="divRpF958813" 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>
</body>
</html>