Bug #7772
closed
Consider bumping stack size in ruby_qsort
Added by Conrad.Irwin (Conrad Irwin) over 9 years ago.
Updated over 8 years ago.
Description
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.
Files
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.
Sorry, I should have had a look at the patch. It makes indeed sense to apply this patch.
- 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???.
- Status changed from Open to Closed
- % Done changed from 0 to 100
This issue was solved with changeset r44195.
Conrad, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.
util.c: bump stack size in ruby_qsort()
- util.c (ruby_qsort): fix potential stack overflow on a large
machine. based on the patch by Conrad Irwin <conrad.irwin AT
gmail.com> at [ruby-core:51816]. [Bug #7772]
- Backport set to 1.9.3: REQUIRED, 2.0.0: REQUIRED
- Backport changed from 1.9.3: REQUIRED, 2.0.0: REQUIRED to 1.9.3: REQUIRED, 2.0.0: DONE
r44195 was backported to ruby_2_0_0 at r44565.
- Backport changed from 1.9.3: REQUIRED, 2.0.0: DONE to 1.9.3: DONE, 2.0.0: DONE
backported into ruby_1_9_3 at r44738.
Also available in: Atom
PDF