Bug #10888
closed
DFS recursive implementation aborted
Description
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 <main>' 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
Updated by