Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Stack Level too Deep e Tail Call Optimization: ...

Stack Level too Deep e Tail Call Optimization: É uma boa ideia fazer recursão em Ruby? (TDC POA 2016)

Com a programação funcional sendo tão discutida nos últimos tempos e Elixir ganhando força, acabamos sendo influenciados por seus conceitos e muitas vezes tentamos implementá-los em Ruby. No caso de recursão - uma estratégia clássica de linguagens funcionais - veremos que inicialmente isto pode não ser uma boa ideia. Vamos entender o que é recursão, como funciona uma "tail call", aprender a realizar modificações na Ruby VM e a compilar uma versão customizada de código Ruby com suporte à Tail Call Optimization. Veremos também o que existe de verdade por trás do clássico erro "Stack Level too Deep", o que significa Stack em Ruby e como lidar com suas questões.

Guilherme Baptista

October 08, 2016
Tweet

More Decks by Guilherme Baptista

Other Decks in Programming

Transcript

  1. ?

  2. É um erro causado por uso de memória em excesso?

    file.rb:8:in `<main>': failed to allocate memory (NoMemoryError)
  3. Bônus: Uma linha para acabar com a memória RAM em

    segundos: Obs.: Não rodar no irb do seu servidor em produção... #fikdik
  4. É uma “proteção” para não deixar um método chamar a

    si mesmo infinitamente? file.rb:2:in `me_myself_and_i': stack level too deep (SystemStackError) from file.rb:2:in `me_myself_and_i' from file.rb:2:in `me_myself_and_i' from file.rb:2:in `me_myself_and_i' from file.rb:2:in `me_myself_and_i' ... 11901 levels... from file.rb:2:in `me_myself_and_i' from file.rb:2:in `me_myself_and_i' from file.rb:2:in `me_myself_and_i' from file.rb:5:in `<main>'
  5. 5

  6. 5

  7. 1 + 1 + 1 + 1 + 1 +

    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
  8. É uma “proteção” para não deixar um método chamar a

    si mesmo infinitamente? file.rb:7:in `eval': stack level too deep (SystemStackError) from file.rb:7:in `<main>'
  9. YARB\x02\x00\x00\x00\x03\x00\x00\x00r\x02\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x02\x0 0\x00\x00\x04\x00\x00\x00\xF9\x01\x00\x00\xFD\x01\x00\x00b\x02\x00\x00x86_64- linux\x00*\x00\x00\x00\x00\x00\x00\x00\b\x00\x00\x00\x00\x00\x00\x00*\x00\x00\x00\x00\x0 0\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00Z\x00\x00\x00\x00\x00\x00\x00Z\x00\x00\x00\x00\ x00\x00\x00;\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00 \x00\x00\x00\x00Z\x00\x00\x00\x00\x00\x00\x00;\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x 00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00Z\x00\x00\x00\x00\x00\x00\x00;\x00\x00 \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00*\x0 0\x00\x00\x00\x00\x00\x00\x10\x00\x00\x00\x00\x00\x00\x001\x00\x00\x00\x00\x00\x00\x00\x 00\x00\x00\x00\v\x00\x00\x00\x02\x00\x00\x00\r\x00\x00\x00\x11\x00\x00\x00\x0F\x00\x00\x

    00\x13\x00\x00\x00\r\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x10\x00\x00\x00\x01\x00 \x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x10\x00\x00\x00\x01\x00\x00\x00\x01\x00\x00\x00 \x00\x00\x00\x00\x10\x00\x00\x00\x01\x00\x00\x00\x01\x00\x00\x00\x02\x00\x00\x00\x01\x00 \x00\x00\x14\x00\x00\x009\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x0 0\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x0 0\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x0 0\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00\x02\x00\x0 0\x00\x00\x00\x00\x00\x17\x00\x00\x00\x00\x00\x00\x00\xD9\x00\x00\x00\x00\x00\x00\x00\xF 9\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xFF\xFF\xFF\xFF\xFF\xFF\xF F\xFF\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xF9\x00\x00\x00\x0 0\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x0 0\x00\x00\x00\x00\x00\x03\x00\x00\x00\x00\x00\x00\x00\x04\x00\x00\x00\x00\x00\x00\x00)\x 01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x03\x00\x00\x00\x00\x00\x00\x00\xF1\x00\x00\x 00\b\x00\x00\x00\x00\x00\x00\x00E\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x05\x00\x0 0\x00\x00\x00\x00\x00(irb)E\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00\a\x00\x00\x00\x0 0\x00\x00\x00the_sumE\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x0 0\x00\x00+\r\x02\x00\x00\x19\x02\x00\x002\x02\x00\x00M\x02\x00\x00
  10. == disasm: #<ISeq:the_sum@(irb)>================================= 0000 trace 8 0002 trace 1 0004

    putobject_OP_INT2FIX_O_1_C_ 0005 putobject_OP_INT2FIX_O_1_C_ 0006 opt_plus <callinfo!mid:+, argc:1, ARGS_SIMPLE>, <cal 0009 putobject_OP_INT2FIX_O_1_C_ 0010 opt_plus <callinfo!mid:+, argc:1, ARGS_SIMPLE>, <cal 0013 putobject_OP_INT2FIX_O_1_C_ 0014 opt_plus <callinfo!mid:+, argc:1, ARGS_SIMPLE>, <cal 0017 trace 16 0019 leave
  11. putobject_OP_INT2FIX_O_1_C_ putobject_OP_INT2FIX_O_1_C_ opt_plus <callinfo!mid:+, argc:1… putobject_OP_INT2FIX_O_1_C_ opt_plus <callinfo!mid:+, argc:1… putobject_OP_INT2FIX_O_1_C_

    opt_plus <callinfo!mid:+, argc:1... putobject_OP_INT2FIX_O_1_C_ putobject_OP_INT2FIX_O_1_C_ putobject_OP_INT2FIX_O_1_C_ putobject_OP_INT2FIX_O_1_C_ opt_plus <callinfo!mid:+, argc:1… opt_plus <callinfo!mid:+, argc:1… opt_plus <callinfo!mid:+, argc:1...
  12. putobject_OP_INT2FIX_O_1_C_ putobject_OP_INT2FIX_O_1_C_ opt_plus <callinfo!mid:+, argc:1… putobject_OP_INT2FIX_O_1_C_ opt_plus <callinfo!mid:+, argc:1… putobject_OP_INT2FIX_O_1_C_

    opt_plus <callinfo!mid:+, argc:1... putobject_OP_INT2FIX_O_1_C_ putobject_OP_INT2FIX_O_1_C_ opt_plus <callinfo!mid:+, argc:1… putobject_OP_INT2FIX_O_1_C_ opt_plus <callinfo!mid:+, argc:1… putobject_OP_INT2FIX_O_1_C_ opt_plus <callinfo!mid:+, argc:1...
  13. 1 + count(["B", "C", "D"]) 1 + 1 + count(["D",

    "D"]) 1 + 1 + 1 + count(["D"]) 1 + 1 + 1 + 1 + count([]) 1 + 1 + 1 + 1 + 0 4
  14. 1 + sum([2, 2, 2]) 1 + 2 + sum([2,

    2]) 1 + 2 + 2 + sum([2]) 1 + 2 + 2 + 2 + sum([]) 1 + 2 + 2 + 2 + 0 7
  15. Stack Overflow 1 + count(["B", "C", "D"]) 1 + count(["C",

    "D"]) 1 + count(["D"]) 1 + count([]) 0 Tamanho do seu Stack
  16. Stack Overflow 1 + count(["B", "C", "D"]) 1 + count(["C",

    "D"]) 1 + count(["D"]) 1 + count([]) 0 Stack Overflow
  17. Stack Overflow 1 + count(["B", "C", "D"]) 1 + count(["C",

    "D"]) 1 + count(["D"]) 1 + count([]) 0 stack level too deep (SystemStackError)
  18. Stack Overflow stack level too deep (SystemStackError) s 1 +

    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 +
  19. ulimit -all core file size (blocks, -c) 0 data seg

    size (kbytes, -d) unlimited scheduling priority (-e) 0 file size (blocks, -f) unlimited pending signals (-i) 31321 max locked memory (kbytes, -l) 64 max memory size (kbytes, -m) unlimited open files (-n) 1024 pipe size (512 bytes, -p) 8 POSIX message queues (bytes, -q) 819200 real-time priority (-r) 0 stack size (kbytes, -s) 8192 cpu time (seconds, -t) unlimited max user processes (-u) 31321 virtual memory (kbytes, -v) unlimited file locks (-x) unlimited
  20. c Tail Call Optimization 1 + count(["B", "C", "D"]) 1

    + count(["C", "D"]) 1 + count(["D"]) 1 + count([]) 0 stack level too deep (SystemStackError)
  21. c

  22. Tail Call Optimization count(["A", "B", "C", "D"], 0) count(["B", "C",

    "D"], 1) count(["C", "D"], 2) count(["D"], 3) count([], 4) 4 Tamanho do seu Stack Reaproveitamento do seu Stack
  23. file.rb:11:in `count': stack level too deep (SystemStackError) from file.rb:11:in `count'

    from file.rb:11:in `count' from file.rb:11:in `count' from file.rb:11:in `count' from file.rb:11:in `count' from file.rb:11:in `count' from file.rb:11:in `count' from file.rb:11:in `count' ... 8723 levels... from file.rb:11:in `count' from file.rb:11:in `count' from file.rb:11:in `count' from file.rb:17:in `<main>'
  24. == disasm: #<ISeq:count@ppt/tco.rb>===================================== local table (size: 5, argc: 1 [opts:

    1, rest: -1, post: 0, block: -1, kw: -1@ [ 5] list<Arg> [ 4] acc<Opt=0> [ 3] head [ 2] tail 0000 putobject_OP_INT2FIX_O_0_C_ ( 4) 0001 setlocal_OP__WC__0 4 0003 trace 8 0005 trace 1 ( 6) 0007 getlocal_OP__WC__0 5 0009 opt_empty_p <callinfo!mid:empty?, argc:0, ARGS_SIMPLE>, <callcache> 0012 branchunless 21 0014 nop 0015 nop 0016 getlocal_OP__WC__0 4 0018 trace 16 0020 leave 0021 trace 1 ( 8) 0023 getlocal_OP__WC__0 5 0025 opt_send_without_block <callinfo!mid:shift, argc:0, ARGS_SIMPLE>, <callc 0028 setlocal_OP__WC__0 3 0030 trace 1 ( 9) 0032 getlocal_OP__WC__0 5 0034 setlocal_OP__WC__0 2 0036 trace 1 ( 11)
  25. == disasm: #<ISeq:count@ppt/tco.rb>===================================== local table (size: 5, argc: 1 [opts:

    1, rest: -1, post: 0, block: -1, kw: -1@ [ 5] list<Arg> [ 4] accc<Opt=0> [ 3] head [ 2] tail 0000 putobject_OP_INT2FIX_O_0_C_ ( 4) 0001 setlocal_OP__WC__0 4 0003 trace 8 0005 trace 1 ( 6) 0007 getlocal_OP__WC__0 5 0009 opt_empty_p <callinfo!mid:empty?, argc:0, ARGS_SIMPLE>, <callcache> 0012 branchunless 21 0014 nop 0015 nop 0016 getlocal_OP__WC__0 4 0018 trace 16 0020 leave 0021 trace 1 ( 8) 0023 getlocal_OP__WC__0 5 0025 opt_send_without_block <callinfo!mid:shift, argc:0, ARGS_SIMPLE>, <callc 0028 setlocal_OP__WC__0 3 0030 trace 1 ( 9) 0032 getlocal_OP__WC__0 5 0034 setlocal_OP__WC__0 2 0036 trace 1 ( 11)
  26. == disasm: #<ISeq:count@<compiled>>===================================== local table (size: 5, argc: 1 [opts:

    1, rest: -1, post: 0, block: -1, kw: -1@-1 [ 5] list<Arg> [ 4] acc<Opt=0> [ 3] head [ 2] tail 0000 putobject_OP_INT2FIX_O_0_C_ ( 2) 0001 setlocal_OP__WC__0 4 0003 getlocal_OP__WC__0 5 ( 3) 0005 opt_empty_p <callinfo!mid:empty?, argc:0, ARGS_SIMPLE>, <callcache> 0008 branchunless 15 0010 nop 0011 nop 0012 getlocal_OP__WC__0 4 0014 leave 0015 getlocal_OP__WC__0 5 ( 5) 0017 opt_send_without_block <callinfo!mid:shift, argc:0, ARGS_SIMPLE>, <callcac 0020 setlocal_OP__WC__0 3 0022 getlocal_OP__WC__0 5 ( 6) 0024 setlocal_OP__WC__0 2 0026 putself ( 8) 0027 getlocal_OP__WC__0 2 0029 getlocal_OP__WC__0 4 0031 putobject_OP_INT2FIX_O_1_C_ 0032 opt_plus <callinfo!mid:+, argc:1, ARGS_SIMPLE>, <callcache> 0035 opt_send_without_block <callinfo!mid:count, argc:2, FCALL|ARGS_SIMPLE>, <c 0038 leave
  27. 0010 nop 0011 nop 0012 getlocal_OP__WC__0 4 0014 leave 0015

    getlocal_OP__WC__0 5 ( 5) 0017 opt_send_without_block <callinfo!mid:shift, argc:0, ARGS_SIMPLE>, <callcac 0020 setlocal_OP__WC__0 3 0022 getlocal_OP__WC__0 5 ( 6) 0024 setlocal_OP__WC__0 2 0026 putself ( 8) 0027 getlocal_OP__WC__0 2 0029 getlocal_OP__WC__0 4 0031 putobject_OP_INT2FIX_O_1_C_ 0032 opt_plus <callinfo!mid:+, argc:1, ARGS_SIMPLE>, <callcache> 0035 opt_send_without_block <callinfo!mid:count, argc:2, FCALL|ARGS_SIMPLE>, <c 0038 leave
  28. 0010 nop 0011 nop 0012 getlocal_OP__WC__0 4 0014 leave 0015

    getlocal_OP__WC__0 5 ( 5) 0017 opt_send_without_block <callinfo!mid:shift, argc:0, ARGS_SIMPLE>, <callcac 0020 setlocal_OP__WC__0 3 0022 getlocal_OP__WC__0 5 ( 6) 0024 setlocal_OP__WC__0 2 0026 putself ( 8) 0027 getlocal_OP__WC__0 2 0029 getlocal_OP__WC__0 4 0031 putobject_OP_INT2FIX_O_1_C_ 0032 opt_plus <callinfo!mid:+, argc:1, ARGS_SIMPLE>, <callcache> 0035 opt_send_without_block <callinfo!mid:count, argc:2, FCALL|ARGS_SIMPLE>, <c 0038 leave
  29. == disasm: #<ISeq:count@<compiled>>===================================== local table (size: 5, argc: 1 [opts:

    1, rest: -1, post: 0, block: -1, kw: -1@-1 [ 5] list<Arg> [ 4] acc<Opt=0> [ 3] head [ 2] tail 0000 putobject_OP_INT2FIX_O_0_C_ ( 2) 0001 setlocal_OP__WC__0 4 0003 getlocal_OP__WC__0 5 ( 3) 0005 opt_empty_p <callinfo!mid:empty?, argc:0, ARGS_SIMPLE>, <callcache> 0008 branchunless 15 0010 nop 0011 nop 0012 getlocal_OP__WC__0 4 0014 leave 0015 getlocal_OP__WC__0 5 ( 5) 0017 opt_send_without_block <callinfo!mid:shift, argc:0, ARGS_SIMPLE>, <callcac 0020 setlocal_OP__WC__0 3 0022 getlocal_OP__WC__0 5 ( 6) 0024 setlocal_OP__WC__0 2 0026 putself ( 8) 0027 getlocal_OP__WC__0 2 0029 getlocal_OP__WC__0 4 0031 putobject_OP_INT2FIX_O_1_C_ 0032 opt_plus <callinfo!mid:+, argc:1, ARGS_SIMPLE>, <callcache> 0035 opt_send_without_block <callinfo!mid:count, argc:2, FCALL|TAILCALL|ARGS_SI 0038 leave
  30. _WC__0 4 _WC__0 5 ( 5) hout_block <callinfo!mid:shift, argc:0, ARGS_SIMPLE>,

    <callcache> _WC__0 3 _WC__0 5 ( 6) _WC__0 2 ( 8) _WC__0 2 _WC__0 4 _INT2FIX_O_1_C_ <callinfo!mid:+, argc:1, ARGS_SIMPLE>, <callcache> hout_block <callinfo!mid:count, argc:2, FCALL|TAILCALL|ARGS_SIMPLE>, <callcache>
  31. user system total real .each: 16.480000 0.000000 16.480000 ( 16.492415)

    recursion: 26.280000 0.380000 26.660000 ( 26.652826)
  32. Referências: - Tail Call Optimization in Ruby http://nithinbekal.com/posts/ruby-tco/ - Tailin'

    Ruby http://timelessrepo.com/tailin-ruby - Tail Call Optimization in Ruby: Deep Dive http://blog.tdg5.com/tail-call-optimization-in-ruby-deep-dive/
  33. Referências: - TCOMethod Simplifies compiling code with tail call optimization

    in MRI Ruby https://github.com/tdg5/tco_method - Hamster Efficient, Immutable, Thread-Safe Collection classes for Ruby https://github.com/hamstergem/hamster - Functional Ruby A gem for adding functional programming tools to Ruby. Inspired by Erlang, Clojure, Haskell, and Functional Java. https://github.com/jdantonio/functional-ruby