Zero-cost lists for inline functions in c++

Question

I like writing checks for a function over a list. For this I usually write a function like this:

inline bool good_strings(const std::vector<const char *> & items)
{
    for (i in items) {
        if (not is_good(i)) return false;
    }
    return true;
}

Then I can write like if (all_good({"a", "b", "c", "d", "e"})) {...} and it looks really nice. This is good to use when your check for a couple of items grows bigger like this:

if (is_good("a") and is_good("b") and /* that's too much, man */ is_good("c")) {...}

But I'm concerned with the overhead of the container I'm using, and also it's hard to choose one: std::vector, std::list, QList, QStringList or maybe even std::array or std::initializer_list - which should be used for inline functions? And which of these a has minimum or even zero overhead when creating using the {} brackets?

Alright, and update: I grabbed my friend licensed IDA Pro and checked some options.

• std::initializer_list: the function doesn't even inline, and there is overhead for creating the list and copying pointers.
• std::vector: the function does inline, however, there is an overhead for creating a vector and copying pointers there.
• std::array: not as good-looking because of template specialization, and the function doesn't inline. So calling it many times creates many similar chunks of code. However, there is no overhead for array creation, and all pointers are passed as function parameters, which is fast for x86_64 register calling a convention.

The question remains, is there an absolutely zero-cost container?

Volant

Why not template the whole function? Then it can use whatever container you happen to pass it. – Abubekr

Parameter complexity shouldn't affect inlining functions or not. You pass that parameter by reference, so that's just an address stored in a register (for most compilers). The compiler usually decides to inline something on the code which appears inside the function, branch predictions and such stuff. You shouldn't have to worry much about parameter types. – Highkeyed

Is your goal to have all of the result evaluated at compile time, or just as efficiently as possible at run time? – Exhilaration

std::all_of(items.begin(), items.end(), is_good); – Danieledaniell

@JeremyFriesner the function is_good is sideeffectful and must be evaluated at runtime, however it's parameters are always the same and can be passed at compile time. – Volant

Is this exclusively for a constexpr context? If you can perform this test at compile time overhead doesn't really matter. – Abubekr

Answer 1

None of the containers are going to be zero overhead. std::array or std::initializer_list will give you the least amount of cost though. std::array needs it's type and size specified at compile time so it is a little less user friendly then a std::initializer_list in this case. So, using a std::initializer_list<const char*> will be the smallest and easiest to use "container" you can use. It will cost the size of the array of pointers the compiler generates and possibly a little more and it won't require any dynamic memory allocation.

---

If you can use C++17 You don't even need a container. Utilizing a variadic template and a fold expression you can have all the arguments passed to the function as separate parameters and the apply the same operation to all of the arguments.

template<typename... Args>
bool good_strings(Args&&... args)
{
    return (is_good(args) && ...);
}

will turn

all_good("a", "b", "c", "d", "e")

into

return is_good("a") && is_good("b") && ... && is_good("e");

which leverages short circuiting so it will stop evaluating as soon as the first call to is_good returns false.

You can utilize the variadic template in C++11, but you would either need to use recursion, or build your own array, which really doesn't gain you anything with the extra complexity you would have.

Necrophobia

Very nice. You could also make is_good another argument so the predicate can be easily changed. – Abubekr

Yes, that is a nice solution, and that's what i would like to use, but sadly my target platform doesn't have c++14 yet. – Volant

@Volant This actually requires C++17 (for the fold expression). What version of C++ are you limited to? – Necrophobia

Well, I checked and you're wrong about initializer_list. (-; Check my answer if you're intrested, and I can send my .idb file with the test binary commented a bit. – Volant

By the way, I found a small problem with fold expressions: there is no way to write a parameter pack with concrete types. And funnily, the stackoverflow question that told me about this said that i should use std::vector for the job. (#18018043) – Volant

@Volant why do you need concrete types in your parameter pack? If you pass anything that isn't acceptable to is_good, you'll get a compile time error, and compilers are getting better and better at giving useful messages in those cases – Duckweed

@Volant Do you need concrete types? If you want to limit what Args is you can use SFINAE to constrain the types. That said, you should get an okay-ish compiler error if you use a object that is_good does not support telling you it is coming from all_good. – Necrophobia

Answer 2

Alright, thanks to the ideas in previous answers, i figured it out. If what people say about "no better containers exist", then std::array is the best. When compiled with optimisation level -O2, std::array has neither parameter copying, nor function calling, while std::initializer_list has parameter copying. When compiled with -O0 it's all as I described in the question itself.

So my solution: use std::array and cope with specifying <N> for number of arguments.

Volant

Passing the initializer list by reference (const &) might help it's performance. – Necrophobia

@Necrophobia Passing by const reference is implied, there would be no hope for any optimization without it of course. – Volant

Answer 3

If you are really concerned about using a container, you could just write N overloads, e.g. for N = 5:

inline bool good_string(const char* a)
{
    return true;
}
inline bool good_strings(const char* a, const char* b)
{
    return good_string(a) && good_string(b);
}
inline bool good_strings(const char* a, const char* b, const char* c)
{
    return good_strings(a, b) && good_string(c);
}
inline bool good_strings(const char* a, const char* b, const char* c, const char* d)
{
    return good_strings(a, b, c) && good_string(d);
}
inline bool good_strings(const char* a, const char* b, const char* c, const char* d, const char* e)
{
    return good_strings(a ,b, c, d) && good_string(e);
}

Awash

I'm sorry, but your solution is horrible: I want to avoid repetition, and repetition is what you suggest. Your solution makes a big problem from a small problem. On the other hand, one could make this work better and write this with parameter packs and recursion. However, as another stackoverflow question i just found has said, there is no way to write a parameter packs with concrete types. – Volant

I think you misunderstand the concept of repetition. With this code you are not repeating yourself, you are creating overloads where each of the overloads has its own purpose! Check out StrCat from abseil.io here. They are applying the same concept there. – Awash

Alright, I have some strong opinions on repetition, and this is not the place to vow them. But thanks, I checked the abseil source and it looks like garbage. What baffles me is that the authors know about parameter packs, but only use them after 5 arguments. Also the they really like pointer magic, reinterpret_cast and void*, which are also bad signs for a project. – Volant

As I said, what I posted has nothing to do with repetition. – Awash

Answer 4

If you template the function thus:

bool is_good(const std::string &) { return true; )
template<typename Container>
inline bool good_strings(const Container & items)
{
    for (auto const &i : items){
        if (not is_good(i)) return false;
    }
    return true;
}

then the call good_strings(std::initializer_list<std::string>{"a", "b", "c", "d", "e"}) will pass the initializer list to all_good. No container needed.

Israelitish

This fails to compile since {...} does not have a type: coliru.stacked-crooked.com/a/54814bd7767b79c7 – Necrophobia

Container is something related to concepts? OP added tag for c++11 – Illusionist

I tried this and it doesn't compile in gcc for c++11. Apparently template type can't be deduced at compile time for this kind of polymorphic list literal. Oh how i miss Haskell. – Volant