Mirror of forum.nim-lang.org

10974 :: Recursive functions returns different values

• seekworser (orginal) [2024-02-10T18:45:32+01:00] view original

  Hi, I found following two codes output different values.

  import tables
  var n = 3
  var dp = initTable[int, int](0)
  proc dfs(x: int): int =
      if x < 2: return 0
      if x in dp: return dp[x]
      dp[x] = x
      dp[x] += dfs(x div 2)
      dp[x] += dfs((x+1) div 2)
      return dp[x]
  echo dfs(n)  # 3
  Run

  import tables
  var n = 3
  var dp = initTable[int, int](0)
  proc dfs(x: int): int =
      if x < 2: return 0
      if x in dp: return dp[x]
      dp[x] = x
      var y = dfs(x div 2)
      dp[x] += y
      y = dfs((x+1) div 2)
      dp[x] += y
      return dp[x]
  echo dfs(n)  # 5
  Run

  Why these codes returns different reaults?

---

• seekworser (orginal) [2024-02-11T04:56:32+01:00] view original

  After digging around a bit more, I found even weirder results. when I fix initial size of hash table, it returns different value. When I modify line 3 of my original code to

  var dp = initTable[int, int](4)
  Run

  so that resize should not be occur, and it also returns 5, which isn't the same as my first result.

  Modifying line 3 to

  var dp = newSeq[int](4)
  Run

  also returns 5, so I suspect something occured while resizing hash table.

  I'll also try gdb debugging, but post just as a quick note.

---

• janAkali (orginal) [2024-02-11T06:30:53+01:00] view original

  That's definitely seems like a bug and a wild one at that. Please report it on github. Here are my findings:

  import tables
  
  var t = initTable[int, int](0)
  proc foo(x: int): int =
    if x < 2: return 0
    t[x] = x
    t[x] = t[x] + foo(x-1)
    if x == 2: echo t.repr # this seemingly benign line affects the result
    return t[x]
  
  echo foo(3)  # 3832898853807797816
  Run

  import tables
  
  var t = initTable[int, int](0)
  proc foo(x: int): int =
    if x < 2: return 0
    t[x] = x
    t[x] = t[x] + foo(x-1)
    return t[x]
  
  echo foo(3)  # 2
  Run

  Culprit is the initTable(0), any of these fix the issue:

  var t: Table[int, int]
  var t: initTable[int, int]()
  var t: initTable[int, int](x) # where x > 0
  Run

---

• seekworser (orginal) [2024-02-11T07:35:00+01:00] view original

  Thanks a lot, I'll report.

---

• demotomohiro (orginal) [2024-02-11T10:11:09+01:00] view original

  It looks like related to this issue: https://github.com/nim-lang/Nim/issues/18683

  dp[x] += dfs(x div 2)
  Run

  1. dp[x] is evaluated first and it return the reference (pointer) to internal heap of dp
  2. dfs(x div 2) is evaluated. Inside dfs, the internal heap of dp is reallocated when the new key-value is added. Then, the reference returned in 1. points to freed memory.
  3. the reference returned in 1. is dereferenced and the result of dfs(x div 2) is added. But it is not referencing to dp[3].

  I think using temporal variable like var y = dfs(x div 2) in your code is easiest way to workaround this.

  Simpler code to reproduce this bug:

  import tables
  var dp = initTable[int, int](0)
  
  proc test(x: var int; y: int) =
    echo "In test proc, addr x     = ", cast[uint](addr x)
    echo "In test proc, addr dp[0] = ", cast[uint](addr dp[0])
    x += y
  
  dp[0] = 1
  test(dp[0], (block:
      dp[1] = 1 # Cause reallocation
      10))
  
  echo "After test, addr dp[0]   = ", cast[uint](addr dp[0])
  echo dp[0]
  echo dp[1]
  Run

  Output:

  In test proc, addr x     = 140048628686976
  In test proc, addr dp[0] = 140048628691072
  After test, addr dp[0]   = 140048628691072
  1
  1
  Run

---