Exponentially increasing compilation time

[luk-f-a]

Hi, I have a case where a function that has a mistake takes an exponentially increasing amount of time to return that error.

This is an example showing what happens when looking for a field that exists ('a') and one that does not exist ('c'). In both cases I measure the running time. When successful the function is very fast (including compilation time), but when it fails, the time it takes to return the error is exponentially related to the amount of functions in the chainer object. For those wondering where this chainer object comes from, please look at #3405
Every function that is added to the chain multiplies the wait time by 2!!!

import numba as nb
import numpy as np
from numba import njit
from datetime import datetime

arr = np.arange(200).reshape(100,2)
arr_view = arr.ravel().view(dtype=[('a', 'int64'), ('b', 'int64')])

for field in ('a', 'c'):
    for k in (1,2,3,4,5,6,7,8,9,10):
        now_ = datetime.now()
        try:
            @nb.njit
            def ident(out, x, arr):
                pass

            def chain_assign(fs, inner=ident):
                tab_head, tab_tail = fs[-1], fs[:-1]

                @nb.njit
                def assign(out, x, arr):
                    inner(out, x, arr)
                    out[0] += tab_head(x, arr)

                if tab_tail:
                    return chain_assign(tab_tail, assign)
                else:
                    return assign

            @njit
            def get_a(x, arr):
                return arr[2][field]

            chain = chain_assign((get_a,)*k)
            out = np.ones(2)
            chain(out, 1, arr_view)
            print(k, 'success', datetime.now()-now_)
        except:
            print(k, 'fail', datetime.now()-now_)

EDIT, forgot to paste the output

1 success 0:00:00.093610
2 success 0:00:00.148076
3 success 0:00:00.173753
4 success 0:00:00.214892
5 success 0:00:00.280657
6 success 0:00:00.303661
7 success 0:00:00.344757
8 success 0:00:00.405511
9 success 0:00:00.430810
10 success 0:00:00.490330
1 fail 0:00:00.039574
2 fail 0:00:00.057562
3 fail 0:00:00.094420
4 fail 0:00:00.174050
5 fail 0:00:00.352585
6 fail 0:00:00.643998
7 fail 0:00:01.297872
8 fail 0:00:02.543795
9 fail 0:00:05.133452
10 fail 0:00:10.170493

[stuartarchibald]

Closing #3691 fixes.