Why does this C++ function takes 4 time as much as a c function

Question

I am considering using c++ for a performance critical application. I thought both C and C++ will have comparable running times. However i see that the c++ function takes >4 times to run that the comparable C snippet.

When i did a disassemble i saw the end(), ++, != were all implemented as function calls. Is it possible to make them (at least some of them) inline?

Here is the C++ code:

typedef struct pfx_s {
    unsigned int start;
    unsigned int end;
    unsigned int count;
} pfx_t;

typedef std::list<pfx_t *> pfx_list_t;

int
eval_one_pkt (pfx_list_t *cfg, unsigned int ip_addr)
{
    const_list_iter_t iter;

    for (iter = cfg->begin(); iter != cfg->end(); iter++) {
        if (((*iter)->start <= ip_addr) &&
            ((*iter)->end >= ip_addr)) {
            (*iter)->count++;
            return 1;
        }
    }
    return 0;
}

And this is the equivalent C code:

int
eval_one_pkt (cfg_t *cfg, unsigned int ip_addr)
{
    pfx_t *pfx;

    TAILQ_FOREACH (pfx, &cfg->pfx_head, next) {
        if ((pfx->start <= ip_addr) &&
            (pfx->end >= ip_addr)) {
            pfx->count++;
            return 1;
        }
    }
    return 0;
}

Answer 1

It might be worth noting that the data structures you used are not entirely equivalent. Your C list is implemented as a list of immediate elements. Your C++ list is implemented as a list of pointers to actual elements. Why did you make your C++ list a list of pointers?

This alone will not, of course, cause four-fold difference in performance. However, it could affect the code's performance do to its worse memory locality.

I would guess that you timed debug version of your code, maybe even compiled with debug version of the library.

Answer 2

Do you have a really good reason to use a list here at all? At first glance, it looks like a std::vector will be a better choice. You probably also don't want a container of pointers, just a container of objects.

You can also do the job quite a bit more neatly a standard algorithm:

typedef std::vector<pfx_t> pfx_list_t;

int
eval_one_pkt(pfx_list_t const &cfg, unsigned int ip_addr) {
    auto pos = std::find_if(cfg.begin(), cfg.end(),
        [ip_addr](pfx_t const &p) {
            return ip_addr >= p.begin && ip_addr <= p.end;
        });

    if (pos != cfg.end()) {
       ++(pos->count);
       return 1;
    }
    return 0;
}

If I were doing it, however, I'd probably turn that into generic algorithm instead:

template <class InIter>
int
eval_one_pkt(InIter b, InIter e, unsigned int ip_addr) {
    auto pos = std::find_if(b, e,
        [ip_addr](pfx_t const &p) {
            return ip_addr >= p.begin && ip_addr <= p.end;
        });

    if (pos != cfg.end()) {
       ++(pos->count);
       return 1;
    }
    return 0;
}

Though unrelated to C vs. C++, for a possible slight further optimization on the range check you might want to try something like this:

return ((unsigned)(ip_addr-p.begin) <= (p.end-p.begin));

With a modern compiler with optimization enabled, I'd expect the template to be expanded inline entirely at the point of use, so there probably wouldn't be any function calls involved at all.

Answer 3

I copied your code and ran timings of 10,000 failed (thus complete) searches of 10,000 element lists:

Without optimization:

• TAILQ_FOREACH 0.717s
• std::list<pfx_t *> 2.397s
• std::list<pfx_t> 1.98s

(Note that I put a next into pfx_t for TAILQ and used the same redundant structure with std::list)

You can see that lists of pointers is worse than lists of objects. Now with optimization:

• TAILQ_FOREACH 0.467s
• std::list<pfx_t *> 0.553s
• std::list<pfx_t> 0.345s

So as everyone pointed out, optimization is the dominant term in a tight inner loop using collection types. Even the slowest variation is faster than the fastest unoptimized version. Perhaps more surprising is that the winner changes -- this is likely due to the compiler better recognizing optimization opportunities in the std code than in an OS-provided macro.