Consider bumping stack size in ruby_qsort
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.
Updated by Conrad.Irwin (Conrad Irwin) almost 10 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 10 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 nobu (Nobuyoshi Nakada) almost 9 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()