Nested Template Functions as Parameters

Question

In Python, there is a very simply way of decorating a function such that you can add additional functionality before and/or after a function. In its most simple form, it looks like this:

from random import SystemRandom
from time import time
import functools

rdev = SystemRandom()

def time_function(func):
    @functools.wraps(func)
    def run(*args, **kwargs):
        start = time()
        ret = func(*args, **kwargs)
        print("Took {:0.5f}s".format(time()-start))
        return ret
    return run

@time_function
def foo():
    x = [rdev.randint(1, 1000) for _ in range(10000)]
    sorted(x)

foo()  # prints "Took 0.04239s"

I wanted to write something with similar functionality in C++. I would like to pass a function with arbitrary parameters and return types into a function and have it perform some action. This is what I came up with:

#ifndef TIMEIT_H
#define TIMEIT_H
#include <string>
#include <functional>
#include <iostream>
#if defined(_WIN32)
#include <Windows.h>
namespace timeit {
    unsigned long gettime(void) {
        return GetTickCount();
    }
}
#elif defined(__linux__)
namespace timeit{
    unsigned long gettime(void) {
        return 0; // implement later
    }
}
#endif

namespace timeit {
    template <typename> struct timer_s;

    template<typename... Args> // this is required for any void function
    struct timer_s<void(Args ...)> {
        std::function<void(Args ...)> func;
        timer_s(std::function<void(Args ...)> f) : func{ f } {}
        void operator()(unsigned long &time, Args ... args) {
            unsigned long start = gettime();
            func(args ...);
            time = gettime() - start;
            return;
        }
    };

    template <typename T, typename... Args> // this is for any other return type
    struct timer_s<T(Args ...)> {
        std::function<T(Args ...)> func;
        timer_s(std::function<T(Args ...)> f) : func{ f } { }
        T operator()(unsigned long &time, Args ... args) {
            unsigned long start = gettime();
            T ret = func(args ...);
            time = gettime() - start;
            return ret;
        }
    };

    template<typename T, typename... Args>
    timer_s<T(Args...)> timer(T(*func)(Args ...)) {
        return timer_s<T(Args ...)>(std::function<T(Args ...)>(func));
    }
}
#endif//TIMEIT_H

This is working rather well. For example, I can time mostly any function with the following:

static std::random_device rdev;

unsigned int foo(size_t size){
    std::vector<unsigned int> nums(size);
    std::mt19937 rand(rdev());
    std::generate(nums.begin(), nums.end(), rand);
    std::sort(nums.begin(), nums.end());
    return nums.back(); // return largest number
}

int main(){
    //foo(0xffff); // normal call
    unsigned long foo_time = 0;
    auto t_foo = timeit::timer(foo);
    unsigned int largest = t_foo(foo_time, 0xffff); // stores time
    std::cout << "Took " << foo_time << "ms\nLargest number: " << largest << "\n";
    return 0;
}

The trouble arises when I try to time a templated function such as std::sort directly. I can only do it if I specify the exact type. I supposed I am wondering if C++ is capable of doing nested template deduction. I want it to deduce which form of std::sort I am using and change the implementation of t_sort dynamically:

What I am currently doing:

static std::random_device rdev;

int main(){
    std::vector<unsigned int> nums(size);
    std::mt19937 rand(rdev());
    std::generate(nums.begin(), nums.end(), rand);
    auto t_sort = timeit::timer(std::sort<std::vector<unsigned int>::iterator>);
    unsigned long sort_time = 0;
    t_sort(sort_time, nums.begin(), nums.end());
}

What I would like:

static std::random_device rdev;

int main(){
    std::vector<unsigned int> nums(size);
    std::mt19937 rand(rdev());
    std::generate(nums.begin(), nums.end(), rand);
    auto t_sort = timeit::timer(std::sort); // this line is different
    unsigned long sort_time = 0;
    t_sort(sort_time, nums.begin(), nums.end());
}

Is this possible? My initial reaction is probably not, but if not, why?

Answer 1

It seems like you've found your answer that something doesn't exist in c++ quite like what python provides, but I'd like to address your question of 'why?' in the context of variadic templates.

The error message you're probably getting is "cannot determine which instance of overloaded function "std::sort" is intended" and that's because you aren't actually passing a specific function pointer to timer. Sort only becomes a specific function when you declare its type, as an un-specialized template it's just the idea of a function. The compiler will deduce the types for T and Args in timer based only on the specific function and arguments you use, so a specific function is necessary. You've got this nice dynamic-typing idea of delaying that specification until later when you actually pass the arguments to t_sort. The compiler needs to know what specialized timer should be used when you initialize it with the constructor.

A way to get the types infered for sort could be to pass everything to the timer constructor (delaying execution execute of the timer for later). Surely the types for sort can be inferred from something like this:

auto t_sort = timeit::timer(std::sort, nums.begin(), nums.end());

where the factory looks like

template<typename T, typename... Args>
timer_s<T(Args...)> timer(T(*func)(Args ...), Args...)
{
    return timer_s<T(Args ...)>(std::function<T(Args ...)>(func), Args...);
}

We'd like the compiler to look inside the timer method and see that the Args... are of type std::vector<unsigned int>::iterator so clearly that is what should be used for the inputs to the function pointer which means that sort should be specialized on std::vector<unsigned int>::iterator. When the compiler looks at the method signature, it associates the Args... parameter to the iterator types and sees that the function needs to take those same types. And this works!

template<typename ... Args> // this is required for any void function
struct timer_s<void(Args... )> {

    std::function<void(Args ...)> func;
    std::tuple<Args...> m_args;


    timer_s(std::function<void(Args ...)> f, Args... args)
        : func{ f }, m_args(std::forward<Args>(args)...)
    {
    }


    void operator()(unsigned long &time) {

        unsigned long start = gettime();

// func(std::get(m_args)...); //more on this later time = gettime() - start;

        return;
    }
};


template<typename... Args>
timer_s<void(Args...)> timerJBS(void(*func)(Args ...), Args... args)
{
    return timer_s<void(Args ...)>(std::function<void(Args ...)>(func), std::forward<Args>(args)...);
}

and then you could totally use

auto t_sort = timeit::timer(std::sort, nums.begin(), nums.end());

Okay, so this compiles with MSVC (VS2015) and the goal of using std::sort without specifying parameters is achieved. There is a catch though and that's the evaluation of func (which I commented out). For some reason I get error C3546: '...': there are no parameter packs available to expand which seems to have been due to a bug in earlier version of the compiler. Some sources seem to say it's been fixed others say it's only on the roadmap. I think figuring this out is outside the scope of the question, which was essentially about passing std::sort to a factory function that produced a lazy evaluating wrapper. I hope this is okay for now, if you can't figure out how to get around the compiler error maybe try posting another question. Also, maybe try using some other compilers, I didn't do that.

A final thought, there might be another way to do what I've outlined by binding the parameters to the function within the template, making sort explicitly specialized. I think the pattern would more-or-less follow what I've written though, with the only differences being within the timer_s struct.

Answer 2

std::sort is not a function but a function template,

One solution is to any accept Functor instead:

namespace timeit {

    template <typename Functor>
    struct timer_s {
        Functor func;
        double time = 0;
        timer_s(Functor  f) : func{ f } {}

        template <typename ... Ts>
        auto operator()(Ts ... args) {
            struct Finally {
                ~Finally() {
                    time = std::chrono::duration_cast<std::chrono::milliseconds>
                              (std::chrono::system_clock::now() - start).count();
                }
                double& time;
                std::chrono::time_point<std::chrono::system_clock> start;
            } finally{time, std::chrono::system_clock::now()};
            return func(std::forward<Ts>(args)...);
        }
    };

    template<typename F>
    timer_s<F> timer(F f) {
        return timer_s<F>(f);
    }
}

And then call it:

// Generic lambda to wrap std::sort and call the correct one.
auto t_sort = timeit::timer([](auto b, auto e){ return std::sort(b, e); });

std::vector<int> v {4, 8, 23, 42, 15, 16};

t_sort(v.begin(), v.end());

Demo