"Illegal instruction: 4" while constructing large binary tree

[charlesstaats]

I don't know whether this is a bug/segfault or just an out-of-memory issue of one kind or another, but I thought I should report it just in case. The following code results in "Illegal instruction: 4" around depth 2093 on my machine:

import stats;

struct node {
  real value;
  node left = null;
  node right = null;

  void operator init(real value) {
    this.value = value;
  }

  void add(real t, int depth=0) {
    if (t < value) {
      if (left == null) {
        left = node(t);
        write(depth);
      } else left.add(t, depth+1);
    } else {
      if (right == null) {
        right = node(t);
        write(depth);
      } else right.add(t, depth+1);
    }
  }

}

struct tree {
  node root = null;

  void add(real t) {
    if (root == null) root = node(t);
    else root.add(t);
  }

}

tree T = new tree;
for (int i = 0; i < 100000; ++i) {
  T.add(Gaussrand() * exp(-0.001 i) + 1e-4 i);
}

Here's my output for asy --version:

Asymptote version 2.87-29 [(C) 2004 Andy Hammerlindl, John C. Bowman, Tom Prince]

ENABLED OPTIONS:
V3D      3D vector graphics output
WebGL    3D HTML rendering
OpenGL   3D OpenGL rendering
FFTW3    Fast Fourier transforms
XDR      External Data Representation (portable binary file format for V3D)
CURL     URL support
Readline Interactive history and editing
Sigsegv  Distinguish stack overflows from segmentation faults
GC       Boehm garbage collector
threads  Render OpenGL in separate thread

DISABLED OPTIONS:
SSBO     GLSL shader storage buffer objects
GSL      GNU Scientific Library (special functions)
Eigen    Eigenvalue library
LSP      Language Server Protocol

[johncbowman]

It doesn't look like a bug: I compiled Asymptote 2.87-26 under x86-64 (Fedora 38) without garbage collection and this example ran up to depth 10000 under valgrind without any errors.

[johncbowman]

It might be a garbage collection issue (which version of Boehm GC are you using?), so try configuring with --disable-gc to help isolate the problem.

[charlesstaats]

I tried compiling it without garbage collection and got an error at depth 1832. Here's my asy --version:

Asymptote version 2.87-29 [(C) 2004 Andy Hammerlindl, John C. Bowman, Tom Prince]

ENABLED OPTIONS:
V3D      3D vector graphics output
WebGL    3D HTML rendering
OpenGL   3D OpenGL rendering
FFTW3    Fast Fourier transforms
XDR      External Data Representation (portable binary file format for V3D)
CURL     URL support
Readline Interactive history and editing
Sigsegv  Distinguish stack overflows from segmentation faults
threads  Render OpenGL in separate thread

DISABLED OPTIONS:
SSBO     GLSL shader storage buffer objects
GSL      GNU Scientific Library (special functions)
Eigen    Eigenvalue library
LSP      Language Server Protocol
GC       Boehm garbage collector

[user202729]

Might as well be stack overflow. Try setting stack size to very small e.g. on UNIX with ulimit -S -s 512 (i.e. 512 KiB) I get it run to ≈ 1988. The default one is 8192 which is 16 × that, so it would probably stack overflow at 31808 which is quite large.

For me the error message is

runtime: Stack overflow
Aborted (core dumped)

[johncbowman]

Yes, good point. If I set my stack size to 512K, I also get a stack overflow. So I will close this issue.

 2283
  real value;
  ^
/u/bowman/camp/test3.asy: 4.3: runtime: Stack overflow
Aborted (core dumped)
bash-5.2$ ulimit -s
512