Bug #7772
closedConsider bumping stack size in ruby_qsort
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
Updated by Conrad.Irwin (Conrad Irwin) almost 12 years ago
- File 0001-Bump-stack-size-in-ruby_qsort-for-64-bit-CPUs.patch 0001-Bump-stack-size-in-ruby_qsort-for-64-bit-CPUs.patch added
Patch to bump size to 64
Updated by duerst (Martin Dürst) almost 12 years ago
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.
Updated by duerst (Martin Dürst) almost 12 years ago
Sorry, I should have had a look at the patch. It makes indeed sense to apply this patch.
Updated by ko1 (Koichi Sasada) almost 12 years ago
- 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???.
Updated by nobu (Nobuyoshi Nakada) almost 11 years ago
- 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]
Updated by nagachika (Tomoyuki Chikanaga) almost 11 years ago
- Backport set to 1.9.3: REQUIRED, 2.0.0: REQUIRED
Updated by nagachika (Tomoyuki Chikanaga) almost 11 years ago
- 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.
Updated by usa (Usaku NAKAMURA) almost 11 years ago
- 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.