func not fucn

There's just something about this that doesn't sit right with me. Here's what I am seeing:

1. I get that when we do sliding_dot_product = make_sliding_dot_product() (let's refer to this left side as sdp1), you are setting sliding_dot_product to the sliding_dot_product function that is being returned from inside of the closure (let's refer to this inside-of-the-closure-function as sdp2)
2. However, the contents of the sliding_dot_product function inside of the closure (sdp2) are never executed until you call sdp1.
3. This means that if you have many Q and T pairs, it is performing boundary comparisons every time rather than performing an O(1) lookup
4. Similarly, if you have many boundaries to check, then this would be slow

So, while the logic is sound, this point:

Doesn't this mean that every time somebody passes in the boundaries then the sets of bounds get loaded every time you call this function?

is still relevant. Yes, the sets of boundaries are supplied/embedded once into sdp2 BUT each call to sdp2 triggers a slow iterative search. Is there a cheap time AND space efficient way to create an O(1) function lookup given m and n? This for loop isn't the right approach. If we have an O(1) function lookup then it's really lightweight and I wouldn't mind going the config route because 99.9% of users will use our default.

Having said that, are we going to have a way for users to run a function and come up with boundaries and functions that are best suited for their hardware?

So, while the logic is sound, this point:

Doesn't this mean that every time somebody passes in the boundaries then the sets of bounds get loaded every time you call this function?

is still relevant. Yes, the sets of boundaries are supplied/embedded once into sdp2 BUT each call to sdp2 triggers a slow iterative search.

Right, I misunderstood your point before.

Is there a cheap time AND space efficient way to create an O(1) function lookup given m and n? This for loop isn't the right approach. If we have an O(1) function lookup then it's really lightweight

Let's replace that for-loop with choose_sdp_func, a function that gets m and n as inputs and return a sdp function as output, and also let's get rid of closure. So, we can have a regular function like this:

def sliding_dot_product(Q, T, choose_sdp_func=None):
    m = len(Q)
    n = len(T)
    if m == n:
        return np.array([np.dot(Q, T)])
 
    if choose_sdp_func is None: 
        # STUMPY DEFAULT
    
    sdp_func = choose_sdp_func(m, n)  # branching logic
    return sdp_func(Q, T)

Is it a bad design? This allows [advanced] users to use different ways to implement branching logic for their choose_sdp_func function:

• A dictionary, keyed by (m,n), and the values are sdp functions. It is O(1)
• Or, if-else logic
• Or, boundaries.
• etc

We can always add a caching mechanism on top of the function choose_sdp_func to make sure it returns output in O(1) for a repeated input (m, n). Regarding STUMPY DEFAULT for choose_sdp_func, we can go with a simple if-else logic.

As a side, regarding the following question you raised before in another comment:

the question remains, how do we allow the flexibility to swap out or modify the if/else logic in that case as well? We should think about this..

I think the proposal should address that

Having said that, are we going to have a way for users to run a function and come up with boundaries and functions that are best suited for their hardware?

Finding "boundaries" is tricky. I have a narrower scope (and, tbh, simpler solution 😅) in mind... a function that gets (m, n) and a list of sdp functions as input, and returns the best one for the provided (m, n).

Finding "boundaries" is tricky

Okay, I think it might be tricky for most users too! So, maybe they appreciate if we just come up with a function that helps them identify boundaries approximately. For instance, we just explore cases where m and n are exact power of two.

I am mostly interested in what the STUMPY_DEFAULT choose_sdp_func would look like and how efficient it would be?

I wanted to say a simple if-else... but I think it can get ugly later. I think we should do what you proposed before in stumpy-dev/sliding_dot_product#18 (comment), a 2D lookup table. And, I think there is no longer a need for choose_sdp_func !!

def make_sliding_dot_product(
    lengths=None, sdp_lookup=None, sdp_functions=None, sdp_default=None
):
    if sdp_default is None:
        sdp_default = sdp._convolve_sliding_dot_product

    if sdp_functions is None:
        sdp_functions = [
            sdp._njit_sliding_dot_product,
            sdp._pocketfft_sliding_dot_product,
            sdp._convolve_sliding_dot_product,
        ]

        # append if pyfftw is available.
        # len(sdp_functions) can change here but it will be 
        # taken care of later in the code
        if sdp.PYFFTW_IS_AVAILABLE:  # pragma: no cover
            sdp_functions.append(sdp._pyfftw_sliding_dot_product)
      

    if lengths  is None or sdp_lookup is None:
        lengths = set()
        for i in range(3, 2**28 + 1):
            lengths.add(next_fast_len(i, real=True))
        lengths = np.sort(list(lengths), dtype=np.uint32) 
        sdp_lookup = np.empty((len(lengths), len(lengths)), dtype=np.uint8)

        # Filling sdp_lookup
        idx_m = np.searchsorted(lengths, config.STUMPY_NJIT_SDP_Q_LENGTH, side='right')
        sdp_lookup[:idx_m, :] = 0
        sdp_lookup[idx_m:, :] = 4  
    
    # when sdp_lookup contains values that are not in the range of indices of `sdp_functions`
    mask = sdp_lookup >= len(sdp_functions)
    if np.any(mask):
        # raise warning
        sdp_lookup[mask] = -1  # fallback indicator

The # Filling sdp_lookup part has similar issue to what we raised for if-else. I mean... we need to revise it every time as we find better functions for different (len(Q), len(T)) pairs.

So, I feel I need to think about...

are we going to have a way for users to run a function and come up with boundaries and functions that are best suited for their hardware?

In this PR.

I think we should do what you proposed before in stumpy-dev/sliding_dot_product#18 (comment), a 2D lookup table

Even using np.searchsorted is O(nlogn), which is undesirable. It would be best to find something that is O(1) if possible.

Filling sdp_lookup

I wouldn't do this inside of make_sliding_dot_product. Instead, I would move the filling code outside of make_sliding_dot_product and this filling code would rarely be used (i.e., a human would manually call it every so often to generate the lookup). Then, the generated lookup table would/should be hardcoded somewhere in a .py file (maybe as a function?). In make_sliding_dot_product, it would simply import the lookup-table-function (but not the "generation" function).