Forum: Ruby-core [ruby-trunk - Bug #7772][Open] Consider bumping stack size in ruby_qsort

46d1ebbb28ce0f4a8f2c77b6d3d95829?d=identicon&s=25 Conrad.Irwin (Conrad Irwin) (Guest)
on 2013-02-03 08:15
(Received via mailing list)
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.
46d1ebbb28ce0f4a8f2c77b6d3d95829?d=identicon&s=25 Conrad.Irwin (Conrad Irwin) (Guest)
on 2013-02-03 08:18
(Received via mailing list)
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.
F52e87b92cafb1e8c6d155076b56ecff?d=identicon&s=25 "duerst (Martin Dürst)" <duerst@it.aoyama.ac.jp> (Guest)
on 2013-02-03 08:26
(Received via mailing list)
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.
F52e87b92cafb1e8c6d155076b56ecff?d=identicon&s=25 "duerst (Martin Dürst)" <duerst@it.aoyama.ac.jp> (Guest)
on 2013-02-03 08:29
(Received via mailing list)
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.
C4e88907313843cf07f6d85ba8162120?d=identicon&s=25 ko1 (Koichi Sasada) (Guest)
on 2013-02-17 06:25
(Received via mailing list)
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.
5cf8f058a4c094bb708174fb43e7a387?d=identicon&s=25 nagachika (Tomoyuki Chikanaga) (Guest)
on 2013-12-14 17:04
(Received via mailing list)
Issue #7772 has been updated by nagachika (Tomoyuki Chikanaga).

Backport set to 1.9.3: REQUIRED, 2.0.0: REQUIRED


----------------------------------------
Bug #7772: Consider bumping stack size in ruby_qsort
https://bugs.ruby-lang.org/issues/7772#change-43677

Author: Conrad.Irwin (Conrad Irwin)
Status: Closed
Priority: Normal
Assignee: nobu (Nobuyoshi Nakada)
Category: core
Target version: current: 2.1.0
ruby -v: 1.9.3p362
Backport: 1.9.3: REQUIRED, 2.0.0: REQUIRED


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.
2ce415b3ae77d0e0153574e01cf3e604?d=identicon&s=25 unknown (Guest)
on 2014-01-12 07:54
(Received via mailing list)
チケット #7772 が Tomoyuki Chikanaga によって更新されました。

Backport を 1.9.3: REQUIRED, 2.0.0: REQUIRED から 1.9.3: REQUIRED, 2.0.0:
DONE に変更

r44195 was backported to ruby_2_0_0 at r44565.

----------------------------------------
Bug #7772: Consider bumping stack size in ruby_qsort
https://bugs.ruby-lang.org/issues/7772#change-44219

* 作成者: Conrad Irwin
* ステータス: Closed
* 優先度: Normal
* 担当者: Nobuyoshi Nakada
* カテゴリ: core
* 対象バージョン: 2.1.0
* ruby -v: 1.9.3p362
* Backport: 1.9.3: REQUIRED, 2.0.0: DONE
8cbb39dadafaf2287a83a13ee4981ec9?d=identicon&s=25 unknown (Guest)
on 2014-01-29 05:01
(Received via mailing list)
Issue #7772 has been updated by Usaku NAKAMURA.

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.

----------------------------------------
Bug #7772: Consider bumping stack size in ruby_qsort
https://bugs.ruby-lang.org/issues/7772#change-44675

* Author: Conrad Irwin
* 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
This topic is locked and can not be replied to.