What does memcmp do if you pass two identical pointers as inputs?

Question

I am comparing two byte arrays with memcmp (or rather a library function does that). The arrays can become relatively large, and they can actually be the same array in many cases.

Would it make sense to write something like this, or will memcmp already do that internally?

int memcmp_wrapper(const void* lhs, const void* rhs, std::size_t count) {
    if (lhs == rhs)
        return 0;
    return std::memcmp(lhs, rhs, count);
}

Did you profile it, by comparing the same large buffer with itself? — Jeffrey, Oct 09 '19 at 13:27
That's up the your standard library implementation. Maybe you can look at the assembly to find out. — François Andrieux, Oct 09 '19 at 13:27
I tried to look up the source for gcc, but it is an internal function that does not have an implementation. I also did not profile it, as I am looking for a general answer for all compilers — SteakOverflow, Oct 09 '19 at 13:29
While agreeing with @FrançoisAndrieux I became curious and had a look into [memcmp.c on github](https://github.com/lattera/glibc/blob/master/string/memcmp.c). According to this, your comparison can make sense. However, isn't this a bit exotic? — Scheff's Cat, Oct 09 '19 at 13:29
I'm not a fan of this check. it looks like it will hide bugs. Why would you check if an array equals itself. Seems like this is a symptom of a bigger issue. — NathanOliver, Oct 09 '19 at 13:31
@NathanOliver I am comparing two arrays, but due to the COW implementation of `QByteArray`, they can sometimes point to the same memory, so I was wondering if I could take a shortcut — SteakOverflow, Oct 09 '19 at 13:35
@SteakOverflow No, you often can't find source code for those kinds of functions. They are often implemented in highly optimized assembly. This is why I mention you will likely need to inspect the assembly to determine what optimizations it contains. — François Andrieux, Oct 09 '19 at 13:37

score 6 · Accepted Answer · edited Oct 09 '19 at 14:09

What does memcmp do if you pass two identical pointers as inputs?

It will return 0.

will memcmp already [return early if pointers are equal]?

It is not specified by the standard. A version of glibc that I checked for example does not.

Would it make sense to write something like this

Potentially, if the array is large enough.

What would you consider large enough,

I would consider the array to be large enough when you have measured memcmp_wrapper to be faster than memcmp by a factor that statistically significant compared to the variance of the measurements.

Some considerations, among many, for measuring are:

the size threshold can be different across different systems depending on CPU, cache and memory etc. See What is a "cache-friendly" code? for an in-depth discussion.
Also note that if the optimiser can prove the equality of the pointers at compile time, then it may be smart enough to optimise the memcmp away entirely, and you may end up measuring two programs that do nothing so design your test harness with care.

and why does it only make sense for that size?

The branch is not free. The time that you may save by not comparing the array must overcome the expense of the added check.

Since the cost of comparing the array increases (linear asymptotic complexity) with the size of the array, there must be some length after which any comparison will be slower than the branch.

What would you consider large enough, and why does it only make sense for that size? — SteakOverflow, Oct 09 '19 at 13:39
@SteakOverflow For one thing, a branch (such as `if`) is [not free](https://stackoverflow.com/a/11227902/7359094). — François Andrieux, Oct 09 '19 at 13:40
@SteakOverflow If the array is only 8 bytes then checking for pointer equality before checking for byte-wise equality would roughly double the amount of work. That's without considering branch mispredictions. — Max Langhof, Oct 09 '19 at 13:40
After some benchmarking, it appears that gcc and clang both do use that shortcut, as they are extremely fast when comparing two identical pointers. The only measurable difference between `memcmp_wrapper` and `std::memcmp` is therefore when `count<=1`. — SteakOverflow, Oct 09 '19 at 14:42

Nathanael Demacon · Answer 2 · 2019-10-09T13:37:00.000

1

If by "same array" you mean same pointer then yes, it makes sense. But if you want to compare the content (what a memcmp implementation should do), the equality doesn't make sense.

Also the implementation of memcmp you're using could do this verification.

edited Oct 09 '19 at 13:37

answered Oct 09 '19 at 13:28

Nathanael Demacon

1,169
7
19

What I am trying to do is compare two chunks of memory. The chunks might or might not actually be the same single chunk – SteakOverflow Oct 09 '19 at 13:32
Well, then it makes sense to do the comparison. – Nathanael Demacon Oct 09 '19 at 13:33
1

One could test whether the compiler’s memcmp() implementation already does this by creating a few enormous (eg 100MB) arrays of identical data and then measuring the time it takes to memcmp() two different arrays vs the time it takes to memcmp() one against itself. (Note that would only tell you about one implementation of memcmp(); other compilers’ implementations might work differently) – Jeremy Friesner Oct 09 '19 at 13:42

What does memcmp do if you pass two identical pointers as inputs?

2 Answers2