Bug #7772

Consider bumping stack size in ruby_qsort

Added by Conrad Irwin about 1 year ago. Updated 3 months ago.

[ruby-core:51816]
Status:Closed
Priority:Normal
Assignee:Nobuyoshi Nakada
Category:core
Target version:2.1.0
ruby -v:1.9.3p362 Backport:1.9.3: DONE, 2.0.0: DONE

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.

0001-Bump-stack-size-in-ruby_qsort-for-64-bit-CPUs.patch Magnifier - Patch to bump size to 64 (1010 Bytes) Conrad Irwin, 02/03/2013 04:07 PM

Associated revisions

Revision 44195
Added by Nobuyoshi Nakada 4 months ago

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 at . [Bug #7772]

History

#1 Updated by Conrad Irwin about 1 year ago

Patch to bump size to 64

#2 Updated by Martin Dürst about 1 year 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 quicksortrecurse 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.

#3 Updated by Martin Dürst about 1 year ago

Sorry, I should have had a look at the patch. It makes indeed sense to apply this patch.

#4 Updated by Koichi Sasada about 1 year ago

  • Category set to core
  • Assignee set to 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???.

#5 Updated by Nobuyoshi Nakada 4 months 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 at . [Bug #7772]

#6 Updated by Tomoyuki Chikanaga 4 months ago

  • Backport set to 1.9.3: REQUIRED, 2.0.0: REQUIRED

#7 Updated by Tomoyuki Chikanaga 3 months 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 ruby20_0 at r44565.

#8 Updated by Usaku NAKAMURA 3 months ago

  • Backport changed from 1.9.3: REQUIRED, 2.0.0: DONE to 1.9.3: DONE, 2.0.0: DONE

backported into ruby19_3 at r44738.

Also available in: Atom PDF