From: y.mazari@... Date: 2015-02-23T03:52:57+00:00 Subject: [ruby-core:68234] [Ruby trunk - Bug #10888] [Open] DFS recursive implementation aborted Issue #10888 has been reported by Yacine Mazari. ---------------------------------------- Bug #10888: DFS recursive implementation aborted https://bugs.ruby-lang.org/issues/10888 * Author: Yacine Mazari * Status: Open * Priority: Normal * Assignee: * ruby -v: ruby 2.1.2p95 (2014-05-08 revision 45877) [x86_64-linux] * Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN, 2.2: UNKNOWN ---------------------------------------- Hello, I am trying to implement DFS algorithm recursively with a graph containing more than 5million edges: `def dfs(directed_graph, vertex) self.marked[vertex] = true directed_graph.adj[vertex].each {|w| dfs(directed_graph, w) unless self.marked[w]} self.reverse_post.push(vertex) end` I got `stack level too deep (SystemStackError)` So I tried to increase the stack size as follows: `export RUBY_THREAD_VM_STACK_SIZE=4000000` `export RUBY_THREAD_VM_STACK_SIZE=8000000` and run my script Neither worked, and execution got aborted. Here are some additional information: -- Ruby level backtrace information ---------------------------------------- scc.rb:129:in `
' scc.rb:116:in `main' scc.rb:116:in `new' scc.rb:72:in `initialize' scc.rb:72:in `new' scc.rb:34:in `initialize' scc.rb:34:in `each' scc.rb:34:in `block in initialize' scc.rb:41:in `dfs' scc.rb:41:in `each' scc.rb:41:in `block in dfs' scc.rb:41:in `dfs' scc.rb:41:in `each' scc.rb:38:in `dfs' scc.rb:38:in `puts' scc.rb:38:in `puts' scc.rb:38:in `write' -- C level backtrace information ------------------------------------------- /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(+0x1c7a5c) [0x7f8fd490fa5c] vm_dump.c:685 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(+0x759a0) [0x7f8fd47bd9a0] error.c:307 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(rb_bug+0xb3) [0x7f8fd47be653] error.c:334 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(+0x14946e) [0x7f8fd489146e] signal.c:704 /lib/x86_64-linux-gnu/libpthread.so.0(+0xf0a0) [0x7f8fd453b0a0] /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(+0x9cb0a) [0x7f8fd47e4b0a] gc.c:1304 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(+0x157b39) [0x7f8fd489fb39] string.c:484 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(rb_str_new_frozen+0x169) [0x7f8fd48a30b9] string.c:530 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(+0xaf6f9) [0x7f8fd47f76f9] io.c:1389 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(+0x1bba72) [0x7f8fd4903a72] vm_eval.c:118 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(rb_funcallv+0xb1) [0x7f8fd49045d1] vm_eval.c:50 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(rb_io_write+0x1f) [0x7f8fd47f7b5f] io.c:1427 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(rb_io_puts+0x88) [0x7f8fd47f87d8] io.c:6979 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(+0x1bba72) [0x7f8fd4903a72] vm_eval.c:118 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(rb_funcallv+0xb1) [0x7f8fd49045d1] vm_eval.c:50 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(+0x1b2230) [0x7f8fd48fa230] vm_insnhelper.c:1470 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(+0x1b6d4a) [0x7f8fd48fed4a] insns.def:1028 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(+0x1bb3e9) [0x7f8fd49033e9] vm.c:1304 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(rb_yield+0x25) [0x7f8fd4908555] vm_eval.c:938 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/../lib/libruby.so.2.1(rb_ary_each+0x52) [0x7f8fd4778772] array.c:1792 -- Other runtime information ----------------------------------------------- * Loaded script: scc.rb * Loaded features: 0 enumerator.so 1 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/enc/encdb.so 2 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/enc/trans/transdb.so 3 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/rbconfig.rb 4 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/compatibility.rb 5 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/defaults.rb 6 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/deprecate.rb 7 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/errors.rb 8 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/version.rb 9 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/requirement.rb 10 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/platform.rb 11 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/basic_specification.rb 12 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/stub_specification.rb 13 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/util/stringio.rb 14 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/specification.rb 15 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/exceptions.rb 16 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/core_ext/kernel_gem.rb 17 thread.rb 18 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/thread.so 19 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/monitor.rb 20 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems/core_ext/kernel_require.rb 21 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/rubygems.rb * Process memory map: 00400000-00401000 r-xp 00000000 08:01 1191006 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/ruby 00600000-00601000 rw-p 00000000 08:01 1191006 /home/yacine/.rvm/rubies/ruby-2.1.2/bin/ruby 01b02000-280f7000 rw-p 00000000 00:00 0 [heap] 7f8fd20ee000-7f8fd2103000 r-xp 00000000 08:01 913924 /lib/x86_64-linux-gnu/libgcc_s.so.1 7f8fd2103000-7f8fd2303000 ---p 00015000 08:01 913924 /lib/x86_64-linux-gnu/libgcc_s.so.1 7f8fd2303000-7f8fd2304000 rw-p 00015000 08:01 913924 /lib/x86_64-linux-gnu/libgcc_s.so.1 7f8fd2304000-7f8fd2878000 rw-p 00000000 00:00 0 7f8fd2878000-7f8fd2a79000 rw-p 00000000 00:00 0 7f8fd2b7a000-7f8fd2d7b000 rw-p 00000000 00:00 0 7f8fd2ead000-7f8fd2efd000 rw-p 00000000 00:00 0 7f8fd2efd000-7f8fd2f00000 r-xp 00000000 08:01 1192617 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/thread.so 7f8fd2f00000-7f8fd30ff000 ---p 00003000 08:01 1192617 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/thread.so 7f8fd30ff000-7f8fd3100000 rw-p 00002000 08:01 1192617 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/thread.so 7f8fd3100000-7f8fd3102000 r-xp 00000000 08:01 1192585 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/enc/trans/transdb.so 7f8fd3102000-7f8fd3302000 ---p 00002000 08:01 1192585 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/enc/trans/transdb.so 7f8fd3302000-7f8fd3303000 rw-p 00002000 08:01 1192585 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/enc/trans/transdb.so 7f8fd3303000-7f8fd3305000 r-xp 00000000 08:01 1192557 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/enc/encdb.so 7f8fd3305000-7f8fd3504000 ---p 00002000 08:01 1192557 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/enc/encdb.so 7f8fd3504000-7f8fd3505000 rw-p 00001000 08:01 1192557 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/ruby/2.1.0/x86_64-linux/enc/encdb.so 7f8fd3505000-7f8fd3506000 ---p 00000000 00:00 0 7f8fd3506000-7f8fd38db000 rw-p 00000000 00:00 0 7f8fd38db000-7f8fd3a5d000 r-xp 00000000 08:01 934158 /lib/x86_64-linux-gnu/libc-2.13.so 7f8fd3a5d000-7f8fd3c5d000 ---p 00182000 08:01 934158 /lib/x86_64-linux-gnu/libc-2.13.so 7f8fd3c5d000-7f8fd3c61000 r--p 00182000 08:01 934158 /lib/x86_64-linux-gnu/libc-2.13.so 7f8fd3c61000-7f8fd3c62000 rw-p 00186000 08:01 934158 /lib/x86_64-linux-gnu/libc-2.13.so 7f8fd3c62000-7f8fd3c67000 rw-p 00000000 00:00 0 7f8fd3c67000-7f8fd3ce8000 r-xp 00000000 08:01 934154 /lib/x86_64-linux-gnu/libm-2.13.so 7f8fd3ce8000-7f8fd3ee7000 ---p 00081000 08:01 934154 /lib/x86_64-linux-gnu/libm-2.13.so 7f8fd3ee7000-7f8fd3ee8000 r--p 00080000 08:01 934154 /lib/x86_64-linux-gnu/libm-2.13.so 7f8fd3ee8000-7f8fd3ee9000 rw-p 00081000 08:01 934154 /lib/x86_64-linux-gnu/libm-2.13.so 7f8fd3ee9000-7f8fd3ef1000 r-xp 00000000 08:01 934164 /lib/x86_64-linux-gnu/libcrypt-2.13.so 7f8fd3ef1000-7f8fd40f0000 ---p 00008000 08:01 934164 /lib/x86_64-linux-gnu/libcrypt-2.13.so 7f8fd40f0000-7f8fd40f1000 r--p 00007000 08:01 934164 /lib/x86_64-linux-gnu/libcrypt-2.13.so 7f8fd40f1000-7f8fd40f2000 rw-p 00008000 08:01 934164 /lib/x86_64-linux-gnu/libcrypt-2.13.so 7f8fd40f2000-7f8fd4120000 rw-p 00000000 00:00 0 7f8fd4120000-7f8fd4122000 r-xp 00000000 08:01 934160 /lib/x86_64-linux-gnu/libdl-2.13.so 7f8fd4122000-7f8fd4322000 ---p 00002000 08:01 934160 /lib/x86_64-linux-gnu/libdl-2.13.so 7f8fd4322000-7f8fd4323000 r--p 00002000 08:01 934160 /lib/x86_64-linux-gnu/libdl-2.13.so 7f8fd4323000-7f8fd4324000 rw-p 00003000 08:01 934160 /lib/x86_64-linux-gnu/libdl-2.13.so 7f8fd4324000-7f8fd432b000 r-xp 00000000 08:01 934159 /lib/x86_64-linux-gnu/librt-2.13.so 7f8fd432b000-7f8fd452a000 ---p 00007000 08:01 934159 /lib/x86_64-linux-gnu/librt-2.13.so 7f8fd452a000-7f8fd452b000 r--p 00006000 08:01 934159 /lib/x86_64-linux-gnu/librt-2.13.so 7f8fd452b000-7f8fd452c000 rw-p 00007000 08:01 934159 /lib/x86_64-linux-gnu/librt-2.13.so 7f8fd452c000-7f8fd4543000 r-xp 00000000 08:01 934174 /lib/x86_64-linux-gnu/libpthread-2.13.so 7f8fd4543000-7f8fd4742000 ---p 00017000 08:01 934174 /lib/x86_64-linux-gnu/libpthread-2.13.so 7f8fd4742000-7f8fd4743000 r--p 00016000 08:01 934174 /lib/x86_64-linux-gnu/libpthread-2.13.so 7f8fd4743000-7f8fd4744000 rw-p 00017000 08:01 934174 /lib/x86_64-linux-gnu/libpthread-2.13.so 7f8fd4744000-7f8fd4748000 rw-p 00000000 00:00 0 7f8fd4748000-7f8fd49ce000 r-xp 00000000 08:01 1191040 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/libruby.so.2.1.0 7f8fd49ce000-7f8fd4bce000 ---p 00286000 08:01 1191040 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/libruby.so.2.1.0 7f8fd4bce000-7f8fd4bd6000 rw-p 00286000 08:01 1191040 /home/yacine/.rvm/rubies/ruby-2.1.2/lib/libruby.so.2.1.0 7f8fd4bd6000-7f8fd4bfc000 rw-p 00000000 00:00 0 7f8fd4bfc000-7f8fd4c1c000 r-xp 00000000 08:01 934166 /lib/x86_64-linux-gnu/ld-2.13.so 7f8fd4c80000-7f8fd4c81000 rw-p 00000000 00:00 0 7f8fd4c81000-7f8fd4c88000 r--s 00000000 08:01 420915 /usr/lib/x86_64-linux-gnu/gconv/gconv-modules.cache 7f8fd4c88000-7f8fd4dff000 r--p 00000000 08:01 396011 /usr/lib/locale/locale-archive 7f8fd4dff000-7f8fd4e04000 rw-p 00000000 00:00 0 7f8fd4e19000-7f8fd4e1b000 rw-p 00000000 00:00 0 7f8fd4e1b000-7f8fd4e1c000 r--p 0001f000 08:01 934166 /lib/x86_64-linux-gnu/ld-2.13.so 7f8fd4e1c000-7f8fd4e1d000 rw-p 00020000 08:01 934166 /lib/x86_64-linux-gnu/ld-2.13.so 7f8fd4e1d000-7f8fd4e1e000 rw-p 00000000 00:00 0 7ffffce33000-7ffffd632000 rw-p 00000000 00:00 0 [stack] 7ffffd74a000-7ffffd74b000 r-xp 00000000 00:00 0 [vdso] ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall] [NOTE] You may have encountered a bug in the Ruby interpreter or extension libraries. Bug reports are welcome. For details: http://www.ruby-lang.org/bugreport.html Aborted -- https://bugs.ruby-lang.org/