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?

Why not template the whole function? Then it can use whatever container you happen to pass it. — François Andrieux, Feb 04 '19 at 19:03
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. — πάντα ῥεῖ, Feb 04 '19 at 19:07
Is your goal to have all of the result evaluated at compile time, or just as efficiently as possible at run time? — Jeremy Friesner, Feb 04 '19 at 19:11
@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. — MorJ, Feb 04 '19 at 19:17
Is this exclusively for a `constexpr` context? If you can perform this test at compile time overhead doesn't really matter. — François Andrieux, Feb 04 '19 at 19:39

NathanOliver · Answer 1 · 2019-02-04T19:25:22.180

12

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.

edited Feb 04 '19 at 19:25

answered Feb 04 '19 at 19:10

NathanOliver

171,901
28
288
402

Very nice. You could also make `is_good` another argument so the predicate can be easily changed. – François Andrieux Feb 04 '19 at 19:12
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. – MorJ Feb 04 '19 at 19:12
2

@MorJ This actually requires C++17 (for the fold expression). What version of C++ are you limited to? – NathanOliver Feb 04 '19 at 19:13
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. – MorJ Feb 04 '19 at 19:55
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. (https://stackoverflow.com/questions/18017543/c11-variable-number-of-arguments-same-specific-type) – MorJ Feb 05 '19 at 08:22
@MorJ 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 – Caleth Feb 05 '19 at 09:12
@MorJ 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`. – NathanOliver Feb 05 '19 at 13:28

MorJ · Answer 2 · 2019-02-05T08:19:59.193

0

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.

edited Feb 05 '19 at 08:19

answered Feb 04 '19 at 19:52

MorJ

566
4
14

Passing the initializer list by reference (`const &`) might help it's performance. – NathanOliver Feb 04 '19 at 19:54
@NathanOliver Passing by const reference is implied, there would be no hope for any optimization without it of course. – MorJ Feb 04 '19 at 21:28

score -1 · Answer 3 · answered Feb 05 '19 at 06:44

-1

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);
}

answered Feb 05 '19 at 06:44

serkan.tuerker

1,681
10
20

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. – MorJ Feb 05 '19 at 08:19
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](https://github.com/abseil/abseil-cpp/blob/master/absl/strings/str_cat.h#L318). They are applying the same concept there. – serkan.tuerker Feb 05 '19 at 19:44
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. – MorJ Feb 05 '19 at 20:11
As I said, what I posted has nothing to do with repetition. – serkan.tuerker Feb 05 '19 at 20:53

Marshall Clow · Answer 4 · 2019-02-05T05:04:17.547

-2

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.

edited Feb 05 '19 at 05:04

answered Feb 04 '19 at 19:17

Marshall Clow

15,972
2
29
45

2

This fails to compile since `{...}` does not have a type: http://coliru.stacked-crooked.com/a/54814bd7767b79c7 – NathanOliver Feb 04 '19 at 19:18
`Container` is something related to concepts? OP added tag for c++11 – 463035818_is_not_an_ai Feb 04 '19 at 19:19
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. – MorJ Feb 04 '19 at 19:27

Zero-cost lists for inline functions in c++

4 Answers4