https://redmine.ruby-lang.org/https://redmine.ruby-lang.org/favicon.ico?17113305112013-02-03T16:07:52ZRuby Issue Tracking SystemRuby master - Bug #7772: Consider bumping stack size in ruby_qsorthttps://redmine.ruby-lang.org/issues/7772?journal_id=357952013-02-03T16:07:52ZConrad.Irwin (Conrad Irwin)conrad.irwin@gmail.com
<ul><li><strong>File</strong> <a href="/attachments/3463">0001-Bump-stack-size-in-ruby_qsort-for-64-bit-CPUs.patch</a> <a class="icon-only icon-download" title="Download" href="/attachments/download/3463/0001-Bump-stack-size-in-ruby_qsort-for-64-bit-CPUs.patch">0001-Bump-stack-size-in-ruby_qsort-for-64-bit-CPUs.patch</a> added</li></ul><p>Patch to bump size to 64</p> Ruby master - Bug #7772: Consider bumping stack size in ruby_qsorthttps://redmine.ruby-lang.org/issues/7772?journal_id=357962013-02-03T16:26:26Zduerst (Martin Dürst)duerst@it.aoyama.ac.jp
<ul></ul><p>It's very well known that Quicksort may create stack overflows. But it's also very well known how to deal with them: Check which of the remaining divisions is longer, and user recursion for the sorter part, and tail recursion simulated with a loop for the longer one. For a (conceptual, written using Ruby as executable pseudocode) example, please see quick_sort_recurse at <a href="http://www.sw.it.aoyama.ac.jp/2012/DA/programs/6qsort.rb" class="external">http://www.sw.it.aoyama.ac.jp/2012/DA/programs/6qsort.rb</a>. I haven't checked the C code, but I would be extremely surprised if this and other optimizations would not have been used in Ruby's sort implementation.</p> Ruby master - Bug #7772: Consider bumping stack size in ruby_qsorthttps://redmine.ruby-lang.org/issues/7772?journal_id=357972013-02-03T16:28:32Zduerst (Martin Dürst)duerst@it.aoyama.ac.jp
<ul></ul><p>Sorry, I should have had a look at the patch. It makes indeed sense to apply this patch.</p> Ruby master - Bug #7772: Consider bumping stack size in ruby_qsorthttps://redmine.ruby-lang.org/issues/7772?journal_id=363802013-02-17T14:24:45Zko1 (Koichi Sasada)
<ul><li><strong>Category</strong> set to <i>core</i></li><li><strong>Assignee</strong> set to <i>nobu (Nobuyoshi Nakada)</i></li><li><strong>Target version</strong> set to <i>2.1.0</i></li></ul><p>Nobu, could you check, and introduce it?</p>
<p>I think it should be included with 2.0.0-p???.</p> Ruby master - Bug #7772: Consider bumping stack size in ruby_qsorthttps://redmine.ruby-lang.org/issues/7772?journal_id=436612013-12-14T11:45:09Znobu (Nobuyoshi Nakada)nobu@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Closed</i></li><li><strong>% Done</strong> changed from <i>0</i> to <i>100</i></li></ul><p>This issue was solved with changeset r44195.<br>
Conrad, thank you for reporting this issue.<br>
Your contribution to Ruby is greatly appreciated.<br>
May Ruby be with you.</p>
<hr>
<p>util.c: bump stack size in ruby_qsort()</p>
<ul>
<li>util.c (ruby_qsort): fix potential stack overflow on a large<br>
machine. based on the patch by Conrad Irwin <conrad.irwin AT<br>
gmail.com> at <a href="/issues/7772">[ruby-core:51816]</a>. [Bug <a class="issue tracker-1 status-5 priority-4 priority-default closed" title="Bug: Consider bumping stack size in ruby_qsort (Closed)" href="https://redmine.ruby-lang.org/issues/7772">#7772</a>]</li>
</ul> Ruby master - Bug #7772: Consider bumping stack size in ruby_qsorthttps://redmine.ruby-lang.org/issues/7772?journal_id=436772013-12-15T01:04:09Znagachika (Tomoyuki Chikanaga)nagachika00@gmail.com
<ul><li><strong>Backport</strong> set to <i>1.9.3: REQUIRED, 2.0.0: REQUIRED</i></li></ul> Ruby master - Bug #7772: Consider bumping stack size in ruby_qsorthttps://redmine.ruby-lang.org/issues/7772?journal_id=442192014-01-12T06:54:31Znagachika (Tomoyuki Chikanaga)nagachika00@gmail.com
<ul><li><strong>Backport</strong> changed from <i>1.9.3: REQUIRED, 2.0.0: REQUIRED</i> to <i>1.9.3: REQUIRED, 2.0.0: DONE</i></li></ul><p>r44195 was backported to ruby_2_0_0 at r44565.</p> Ruby master - Bug #7772: Consider bumping stack size in ruby_qsorthttps://redmine.ruby-lang.org/issues/7772?journal_id=446752014-01-29T04:01:14Zusa (Usaku NAKAMURA)usa@garbagecollect.jp
<ul><li><strong>Backport</strong> changed from <i>1.9.3: REQUIRED, 2.0.0: DONE</i> to <i>1.9.3: DONE, 2.0.0: DONE</i></li></ul><p>backported into ruby_1_9_3 at r44738.</p>