--gc:arc doesn't detect cycle, leaks memory; {.cursor.} ineffective with seq

[timotheecour]

BUG1

--gc:arc doesn't detect cycle through a seq element, leaks memory, in -d:case3 below

BUG2

x3 {.cursor.}: seq[Foo] doesn't remove the leak through a seq element, see below

Example

import std/strutils

type Foo = ref object
  x1: string
  x2: Foo # this would remove leak: x2 {.cursor.}: Foo
  x3: seq[Foo] # this would NOT remove leak: x3 {.cursor.}: seq[Foo]

var p = 0
proc fun()=
  var x = Foo(x1: "abc")
  x.x1.setLen 1000
  when defined case1:
    x.x2 = x
  elif defined case2:
    x.x3.add x
  elif defined case3:
    x.x3.setLen 1
    x.x3[0] = x
  else:
    static: doAssert(false, "use -d:case?")
  p += cast[int](addr x) mod 100

proc main()=
  let n = 1000000
  for i in 0..<n:
    fun()
  echo p
  echo getMaxMem().formatSize

main()

Current Output

nim c -r -d:case1 main.nim
nim c -r -d:case2 main.nim
nim c -r -d:case3 main.nim
uses 6.121MiB

nim c -r --gc:arc -d:case1 main.nim # ok

Warning: 'x.x2 = x' creates an uncollectable ref cycle; annotate 'x2' with .cursor 

=> leaks 1.412GiB

nim c -r --gc:arc -d:case2 main.nim # ??
not sure whether that's what we want here:

Hint: passing 'x' to a sink parameter introduces an implicit copy; use 'move(x)' to prevent it [Performance]

=> leaks: 1.475GiB

nim c -r --gc:arc -d:case3 main.nim
BUG: compiler doesn't tell you there's a cycle, no warnings/hints shown
=> leaks: 1.475GiB

Expected Output

compiler should tell you there's a cycle (and, as enhancement: either saying "surely a cycle" or "maybe a cycle" depending on the case)

Additional Information

• devel 5e9ebe9

• for case1, using x2 {.cursor.}: Foo would remove leak and consume only 516KiB instead of 6.09MiB without --gc:arc

[Araq]

covered by other bug reports plus arc doesn't deal with cycles by design.

[timotheecour]

@Araq

arc doesn't deal with cycles by design

• it doesn't collect cycles but it should warn when it detect cycles, otherwise it's inconsistent with case1
• cursor should remove leaks but doesn't in the case mentioned: x3 {.cursor.}: seq[Foo] would not remove the leak

covered by other bug reports

not seeing which bug report it's covered by in this list:

• https://github.com/nim-lang/Nim/labels/ARC

[ghost]

@timotheecour ARC already warns when it detects cycles though

[ghost]

For

type
  Node = ref object
    next: Node

let a = Node()
a.next = a
echo a[]

/home/dian/Projects/stuff/tt.nim(6, 8) Warning: 'a.next = a' creates an uncollectable ref cycle; annotate 'next' with .cursor [CycleCreated]

[timotheecour]

ARC already warns when it detects cycles though

@Yardanico did you read this bug report?

as mentioned in the 1st sentence, --gc:arc doesn't detect cycle through a seq element, leaks memory, in -d:case3 below

nim r -d:case3 --gc:arc main.nim
24000000
1.547GiB

=> no warning

[Araq]

There are no known algorithms that can reliably detect all cycles, I only know about heuristics.

[timotheecour]

can we reopen?
there's no need to detect all cycles, either of these 2 would be improvements over status quo:

• detect when there is at least 1 cycle (DFS/BFS will work)
• detect 1 cycle per connected component (treating as undirected graph) or strongly connected component (treating as directed graph; but IIUC we only need to consider the case of undirected graphs for this problem; please correct me if that's not true)

no heuristics needed for those

[Araq]

You can always use --gc:orc which adds a cycle collector. I don't think we should spent more effort on alternatives.

[timotheecour]

I'd like to understand more;

• does orc have overhead at CT vs arc?
• does arc have overhead at RT vs arc? is there a way to quantify?
• any other drawback of orc over arc?

[Araq]

It can have significant runtime overhead (~25% for the "havlak" benchmark) but the .ayclic annotation has been revived and brings the overhead for the acyclic objects down to zero. Since the cycle collector is thread-local, you can only send acyclic graphs to a different thread.

[timotheecour]

But here the object is not acyclic so {.acyclic.} wouldn't help; and {.cursor.} also doesn't help; this is a simple example where --gc:orc is slower than regular gc (and uses 3X memory), and --gc:arc leaks and doesn't warn that there are leaks (and is therefore even slower than --gc:orc, and regular gc). Proper fix here IMO is to detect presence of at least 1 cycle, as well as make {.cursor.} work in those cases (in particular case3)

(I've retried all those examples with devel 1.5.1 338602a)