Issue #7772 has been reported by Conrad.Irwin (Conrad Irwin). ---------------------------------------- Bug #7772: Consider bumping stack size in ruby_qsort https://bugs.ruby-lang.org/issues/7772 Author: Conrad.Irwin (Conrad Irwin) Status: Open Priority: Normal Assignee: Category: Target version: ruby -v: 1.9.3p362 At the moment the maximum size of the stack is 32. The comment implies this should be enough for arrays with up to 2**32 elements, but it's possible to create larger arrays on some big systems. I was not able to trigger a bug with: ([0, 1] * (2**32 + 10000)).sort! so it may actually never be a problem in practice, but it seems unsafe.
on 2013-02-03 08:15
on 2013-02-03 08:18
Issue #7772 has been updated by Conrad.Irwin (Conrad Irwin). File 0001-Bump-stack-size-in-ruby_qsort-for-64-bit-CPUs.patch added Patch to bump size to 64 ---------------------------------------- Bug #7772: Consider bumping stack size in ruby_qsort https://bugs.ruby-lang.org/issues/7772#change-35795 Author: Conrad.Irwin (Conrad Irwin) Status: Open Priority: Normal Assignee: Category: Target version: ruby -v: 1.9.3p362 At the moment the maximum size of the stack is 32. The comment implies this should be enough for arrays with up to 2**32 elements, but it's possible to create larger arrays on some big systems. I was not able to trigger a bug with: ([0, 1] * (2**32 + 10000)).sort! so it may actually never be a problem in practice, but it seems unsafe.
on 2013-02-03 08:26
Issue #7772 has been updated by duerst (Martin Dürst). 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 http://www.sw.it.aoyama.ac.jp/2012/DA/programs/6qsort.rb. 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. ---------------------------------------- Bug #7772: Consider bumping stack size in ruby_qsort https://bugs.ruby-lang.org/issues/7772#change-35796 Author: Conrad.Irwin (Conrad Irwin) Status: Open Priority: Normal Assignee: Category: Target version: ruby -v: 1.9.3p362 At the moment the maximum size of the stack is 32. The comment implies this should be enough for arrays with up to 2**32 elements, but it's possible to create larger arrays on some big systems. I was not able to trigger a bug with: ([0, 1] * (2**32 + 10000)).sort! so it may actually never be a problem in practice, but it seems unsafe.
on 2013-02-03 08:29
Issue #7772 has been updated by duerst (Martin Dürst). Sorry, I should have had a look at the patch. It makes indeed sense to apply this patch. ---------------------------------------- Bug #7772: Consider bumping stack size in ruby_qsort https://bugs.ruby-lang.org/issues/7772#change-35797 Author: Conrad.Irwin (Conrad Irwin) Status: Open Priority: Normal Assignee: Category: Target version: ruby -v: 1.9.3p362 At the moment the maximum size of the stack is 32. The comment implies this should be enough for arrays with up to 2**32 elements, but it's possible to create larger arrays on some big systems. I was not able to trigger a bug with: ([0, 1] * (2**32 + 10000)).sort! so it may actually never be a problem in practice, but it seems unsafe.
on 2013-02-17 06:25
Issue #7772 has been updated by ko1 (Koichi Sasada). Category set to core Assignee set to nobu (Nobuyoshi Nakada) Target version set to 2.1.0 Nobu, could you check, and introduce it? I think it should be included with 2.0.0-p???. ---------------------------------------- Bug #7772: Consider bumping stack size in ruby_qsort https://bugs.ruby-lang.org/issues/7772#change-36380 Author: Conrad.Irwin (Conrad Irwin) Status: Open Priority: Normal Assignee: nobu (Nobuyoshi Nakada) Category: core Target version: 2.1.0 ruby -v: 1.9.3p362 At the moment the maximum size of the stack is 32. The comment implies this should be enough for arrays with up to 2**32 elements, but it's possible to create larger arrays on some big systems. I was not able to trigger a bug with: ([0, 1] * (2**32 + 10000)).sort! so it may actually never be a problem in practice, but it seems unsafe.
Enable email notification
Enable multi-page viewPlease log in before posting. Registration is free and takes only a minute.
Existing account
(Switch to SSL-encrypted connection)
NEW: Do you have a Google/GoogleMail or Yahoo account? No registration required!
Log in with Google account | Log in with Yahoo account
Log in with Google account | Log in with Yahoo account
No account? Register here.