Stack overflow? Interesting behaviour during very deep recursion

Question

While I was making my assignment on BST, Linked Lists and AVL I noticed.. actually it is as in the title.

I believe it is somehow related to stack overflow, but could not find why it is happening.

Creation of the BST and Linked list

Searching for all elements in Linked list and BST

And probably most interesting...

Comparison of the height of BST and AVL

(based on array of unique random integers)

On every graph something interesting begins around 33k elements.

Optimization O2 in MS Visual Studio 2019 Community.

Search function of Linked list is not recursive.

Memory for each "link" was allocated with "new" operator.

X axis ends on 40k elements because when it is about 43k then stack overflow error happens.

Do you know why does it happen? Actually, I'm curious what is happening. Looking forward to your answers! Stay healthy.

Here is some related code although it is not exactly the same, I can assure it works the same and it could be said some code was based on it.

struct tree {
        tree() {
        info = NULL;
        left = NULL;
        right = NULL;
        }
        int info;
    struct tree *left;
    struct tree *right;
};

struct tree *insert(struct tree*& root, int x) {
    if(!root) {
        root= new tree;
        root->info = x;
        root->left = NULL;
        root->right = NULL;
        return(root);
    }
    if(root->info > x)
         root->left = insert(root->left,x); else {
        if(root->info < x)
            root->right = insert(root->right,x);
    }
    return(root);
}

struct tree *search(struct tree*& root, int x) {
    struct tree *ptr;
    ptr=root;
    while(ptr) {
        if(x>ptr->info)
             ptr=ptr->right; else if(x<ptr->info)
             ptr=ptr->left; else
             return ptr;
    }

int bstHeight(tree*& tr) {
    if (tr == NULL) {
        return -1;
    }
    int lefth = bstHeight(tr->left);
    int righth = bstHeight(tr->right);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

AVL tree is a BST read inorder and then, array of the elements is inserted into tree object through bisection.

@ChrisMM Some sources state that it is allocated on stack. Some other options I've found include free memory, "raw data", "it is just allocated, nothing more". I don't know whom should I trust hah — Perwell
– Perwell, Commented Apr 9, 2020 at 23:42
It's generally not possible for new to allocate memory from the stack, because due to the simple nature of the stack, stack allocations must always be freed in the exact opposite order that they were allocated in -- but allocations done via new may be freed in any order (or even never freed at all, if you forget to call delete on them). OTOH note that local/automatic variables and function arguments are usually allocated on the stack. — Jeremy Friesner
– Jeremy Friesner, Commented Apr 10, 2020 at 0:30
You're probably hitting the limit of some cache such as the CPU's L2 cache. — David Schwartz
– David Schwartz, Commented Apr 10, 2020 at 0:32
I think the stack overflow is a symptom, probably of a bug in how you select elements. If you're using rand()` and an implementation like Windows in which RAND_MAX is 32767, then perhaps when you hit 32768 elements something goes badly wrong with the code which selects the next element to insert. — rici
– rici, Commented Apr 10, 2020 at 1:14

Perwell · Accepted Answer · 2020-04-10 08:37:12Z

1

Spikes in time could be, and I am nearly sure they are, because of using up some cache of the CPU (L2 for example). Some leftover data was stored somewhere in slower memory.

The answer is thanks to @David_Schwartz

Spike in the height of the BST tree is actually my own fault. For the "array of unique random" integers I used array of already sorted unique items, then mixing them up by swapping elements with the rand() function. I have totally forgotten how devastating could it be if expected to random larger numbers.

Thanks @rici for pointing it out.

answered Apr 10, 2020 at 8:37

Perwell

518 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

rici Over a year ago

I'll be interested in seeing your new graphs. All of the increase in insert/search time in your graphs can be explained by the explosion of tree depth as a result of providing the binary tree builder with the worst-case input (sorted). Cache and similar effects are certainly possible but you won't see them on a logarithmic scale graph. It would have been interesting to also chart the time taken by your AVL algorithm, since it's not going to be so adversely affected by the input. But there's no visible spike in the cost of linked list ins/srch, and that too would be affected by cache misses.

Collectives™ on Stack Overflow

Stack overflow? Interesting behaviour during very deep recursion

Creation of the BST and Linked list

Searching for all elements in Linked list and BST

Comparison of the height of BST and AVL

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Creation of the BST and Linked list

Searching for all elements in Linked list and BST

Comparison of the height of BST and AVL

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related