Mirror of forum.nim-lang.org

11094 :: recusion use a lot of memory, any idea why?

• IanZhang (orginal) [2024-02-27T08:04:06+01:00] view original

  Code below is solving https://adventofcode.com/2015/day/10.

  When use recursion call, It used a lot of memory. I tried use input as var, but still on effect. Have to change code to iterative to solve the memory problem.

  Any idea why recusion call use so much memory, is there some mistake in my code?

  
  import strformat, strutils, sequtils
  
  proc findDiffCharIdx(input: string):int =
      let first = input[0]
      for i, c in input:
          if c != first:
              return i
      # all the same, diff is len
      return input.len
  
  # too large mem
  # proc lookAndSay(input: string, acc:string):string =
  #     if input.len < 1:
  #         return acc
  #     let idx = findDiffCharIdx(input)
  #     let num = idx
  #     let start = fmt"{num}{input[0]}"
  #     return lookAndSay(input[idx..^1], acc & start)
  
  # same mem, tail recursion not release mem?
  # proc lookAndSay(input: var string, pos:int, acc: var seq[string]) =
  #     if pos == input.len:
  #         return
  #     let idx = findDiffCharIdx(input[pos..^1])
  #     let num = idx
  #     let start = fmt"{num}{input[pos]}"
  #     acc.add(start)
  #     lookAndSay(input, pos+num, acc)
  
  proc lookAndSay(input: var string, acc: var seq[string]) =
      var pos = 0
      while pos < input.len:
          let idx = findDiffCharIdx(input[pos..^1])
          let num = idx
          let start = fmt"{num}{input[pos]}"
          acc.add(start)
          pos += num
  
  proc main() =
      
      var input = "3113322113"
      
      for i in 0..<50:
          var acc: seq[string] = @[]
          lookAndSay(input, acc)
          input = acc.join()
          echo i , " ", input.len
      echo fmt"output {input.len}"
  
  main()
  Run

---

• nrk (orginal) [2024-02-27T11:47:31+01:00] view original

  Nim is not a functional language. You should avoid unbounded recursion, even if it's tail recursion; it's not idiomatic and you are at the mercy of your C compiler to optimize it out. So in this case you should prefer the iterative version.

  That said, if you really want to tail recurse, here's some mistakes you can correct to get it optimized out (at least on my computer...):

  • [idx..^1] does not do what you think it does. It's essentially equivalent to substr, and allocates a new string. What you really want is an openArray[char], and the toOpenArray function, which is a non-copying slice. Rule of thumb: don't use [m..n] slices unless you want to copy.
  • Making the accumulator a var is a good idea, but why not just use a string? With a string accumulator, you are just appending stuff with the occasional realloc. With a seq accumulator, you have to allocate a gazillion strings and then a final one, which is slow.
  • Put string allocations inside a separate block in the function. This way, they go out of scope before the tail call and Nim can deallocate them (therefore allowing the C compiler to turn the call into a loop.)

  Putting it all together:

  import std/[strformat, strutils]
  
  # changed input to openArray[char]
  proc findDiffCharIdx(input: openArray[char]): int =
      let first = input[0]
      for i, c in input:
          if c != first:
              return i
      # all the same, diff is len
      return input.len
  
  # gets optimized properly
  proc lookAndSay(input: openArray[char], acc: var string) =
      if input.len < 1:
          return
      let idx = findDiffCharIdx(input)
      block: # $idx allocates! so get it to deallocate before the tail call.
        acc &= $idx
      acc &= input[0] # this uses nimAddCharV1, so it's fine to put it outside
      lookAndSay(input.toOpenArray(idx, input.high), acc)
  
  proc main() =
      
      var input = "3113322113"
      
      for i in 0..<50:
          var acc = ""
          lookAndSay(input, acc)
          input = acc
          echo i , " ", input.len
      echo fmt"output {input.len}"
  
  main()
  Run

  BTW, all info about allocations is in the generated C code; please check it out yourself with your variations.

  nim c -d:release --nimcache:/tmp/myprog myprog.nim will put the C files in /tmp/myprog, so that it is easy to inspect.

---

• IanZhang (orginal) [2024-02-28T04:22:54+01:00] view original

  Thanks! this make a lot of sense.

---