Description
First the good news, problem seems to be not (only) the complicated bulkloading, but a plain recursive search operation. So I did the investigations with the initial rtree release without bulk loading support located at ~/Nim/tests/generics/trtree.nim
First observation by manual inspection is that for a few procs nodes are passed in an unnecessary fashion as var parameters like in
proc rstarSplit[M, D: Dim; RT, LT](t: RStarTree[M, D, RT, LT]; n: var Node[M, D, RT, LT] |
That is an unnecessary indirection, but removing var does unfortunately not help.
After manual inspection the Nim code for a few hours, I decide this morning to activate valgrind, which involves recompilation of glibc on my gentoo box, see https://wiki.gentoo.org/wiki/Debugging. Result seems to be, that first error already occurs in search() function by invalid freeing nodes. I renamed the inner search proc initially called s() to salewski() for better location. I think that it is an inner function is not really important here, I moved it already to outer scope yesterday, but it made no difference.
Here is the valgrind result:
$ nim -v
Nim Compiler Version 1.1.1 [Linux: amd64]
Compiled at 2020-01-11
Copyright (c) 2006-2019 by Andreas Rumpf
git hash: 767592a3c350fca6fc6f01f519a814c0498167f9
active boot switches: -d:release
$ nim c --gc:arc -d:useMalloc trtree.nim
$ valgrind ./trtree
==127918== Memcheck, a memory error detector
==127918== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==127918== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==127918== Command: ./trtree
==127918==
1 [2, 3, 4, 7]
[0, 0]
==127918== Invalid read of size 8
==127918== at 0x128C98: salewski__RCeHJQqbRiDVJlx7vXKl5w (in /tmp/hhh/trtree)
==127918== by 0x12926E: search__4H1fvdp4RpiGyerTSeIC2w (in /tmp/hhh/trtree)
==127918== by 0x12A170: test__aiaH86GmasxSCxE29b4wR5g (in /tmp/hhh/trtree)
==127918== by 0x12AAB1: NimMainModule (in /tmp/hhh/trtree)
==127918== by 0x12A72D: NimMainInner (in /tmp/hhh/trtree)
==127918== by 0x12A769: NimMain (in /tmp/hhh/trtree)
==127918== by 0x12A7B7: main (in /tmp/hhh/trtree)
==127918== Address 0x4c95568 is 8 bytes inside a block of size 360 free'd
==127918== at 0x48369CB: free (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==127918== by 0x10FDEE: nimRawDispose (in /tmp/hhh/trtree)
==127918== by 0x10FF5E: nimDestroyAndDispose (in /tmp/hhh/trtree)
==127918== by 0x116F74: eqdestroy___9bni1mQ3m6sVDSY3q4lFpkQ (in /tmp/hhh/trtree)
==127918== by 0x129197: salewski__RCeHJQqbRiDVJlx7vXKl5w (in /tmp/hhh/trtree)
==127918== by 0x12926E: search__4H1fvdp4RpiGyerTSeIC2w (in /tmp/hhh/trtree)
==127918== by 0x12A170: test__aiaH86GmasxSCxE29b4wR5g (in /tmp/hhh/trtree)
==127918== by 0x12AAB1: NimMainModule (in /tmp/hhh/trtree)
==127918== by 0x12A72D: NimMainInner (in /tmp/hhh/trtree)
==127918== by 0x12A769: NimMain (in /tmp/hhh/trtree)
==127918== by 0x12A7B7: main (in /tmp/hhh/trtree)
==127918== Block was alloc'd at
==127918== at 0x483579F: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==127918== by 0x11001E: nimNewObj (in /tmp/hhh/trtree)
==127918== by 0x117FD0: newNode__U3NFuiwWaqt3YXb9bgpykDA (in /tmp/hhh/trtree)
==127918== by 0x11E8D8: adjustTree__1BnzcqRjnbVp2CYX4iUiWA (in /tmp/hhh/trtree)
==127918== by 0x119054: rsinsert__Q2Q1MCAcGKTqj9a8lSfn9cMw (in /tmp/hhh/trtree)
==127918== by 0x119D52: reInsert__L0ISDUMw7u9aeGMOqY9cDaQQ (in /tmp/hhh/trtree)
==127918== by 0x11BF6C: overflowTreatment__ub9acO24XNTKqdP0kPvGGWQ (in /tmp/hhh/trtree)
==127918== by 0x11FA87: adjustTree__1BnzcqRjnbVp2CYX4iUiWA (in /tmp/hhh/trtree)
==127918== by 0x119054: rsinsert__Q2Q1MCAcGKTqj9a8lSfn9cMw (in /tmp/hhh/trtree)
==127918== by 0x119D52: reInsert__L0ISDUMw7u9aeGMOqY9cDaQQ (in /tmp/hhh/trtree)
==127918== by 0x11BF6C: overflowTreatment__ub9acO24XNTKqdP0kPvGGWQ (in /tmp/hhh/trtree)
==127918== by 0x11FA87: adjustTree__1BnzcqRjnbVp2CYX4iUiWA (in /tmp/hhh/trtree)
==127918==
==127918== Invalid read of size 8
==127918== at 0x128CE3: salewski__RCeHJQqbRiDVJlx7vXKl5w (in /tmp/hhh/trtree)
proc search*[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; b: Box[D, RT]): seq[LT] =
proc salewski[M, D: Dim; RT, LT](n: H[M, D, RT, LT]; b: Box[D, RT]; res: var seq[LT]) =
if n of Node[M, D, RT, LT]:
let h = Node[M, D, RT, LT](n)
for i in 0 ..< n.numEntries:
if intersect(h.a[i].b, b):
salewski(h.a[i].n, b, res)
elif n of Leaf[M, D, RT, LT]:
let h = Leaf[M, D, RT, LT](n)
for i in 0 ..< n.numEntries:
if intersect(h.a[i].b, b):
res.add(h.a[i].l)
else: assert false
result = newSeqOfCap[LT](1024)
salewski(t.root, b, result)In C code salewski function is calling
LA1_: ;
nimln_(51, "/tmp/hhh/trtree.nim");
eqdestroy___Y6NozN0iHtEJdDL3UA14Wg(&h_2);
nimln_(140, "/tmp/hhh/trtree.nim");
eqdestroy___9bni1mQ3m6sVDSY3q4lFpkQ(&h);
popFrame();
}