Comments on Daniel's Software Blog: Fast memcpy in c

Thanks for finding the bug. I've updated the z...

2012-01-15T10:08:44.771-08:00

Thanks for finding the bug. I've updated the zip to reflect the change.

There is a (mostly benign) bug in the code. #if T...

2011-12-28T13:50:17.058-08:00

There is a (mostly benign) bug in the code.

#if TYPE_WIDTH >= 4

The code in the #if block will always be included. That should be ">", not ">=".

I talked with my c standard guru friends and the b...

2011-01-28T12:20:47.070-08:00

I talked with my c standard guru friends and the behavior is indeed undefined, but most architectures and compilers does behave as the snipplet intends to work.

From a portability point of view, its not a concern though. The full memcpy implementation contain three different implementations:

1. Post increment
2. Pre increment
3. Indexed copy

The undefined behavior only applies to option 2, and the others should be fine to use on architecture that doesn't have the more common implementation of the undefined behavior.

Thanks for pointing it out.

No, it does not state that Q-1==P when Q is outsid...

2011-01-27T20:34:28.912-08:00

No, it does not state that Q-1==P when Q is outside the boundary of the array. It states: "If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined."

There is a provision for t+n, but none for t-1 (t being an array of size n).

I gave the number of the paragraph earlier. Look it up: http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf

Adding an integer to a pointer does I believe not ...

2011-01-27T12:31:26.351-08:00

Adding an integer to a pointer does I believe not cause undefined behavior if there are no overflows in the operation. The rule states that if Q=P+1, then Q-1==P, also if Q is outside the boundary of the array.
However an indirection of Q (e.g. v = *Q) will cause memory access violation if the memory is not accessible.

Technically, --src8; and --dst8; invoke undefined ...

2011-01-27T10:26:48.474-08:00

Technically, --src8; and --dst8; invoke undefined behavior when src and dest point to the beginning of their respective blocks. See 6.5.6.8 in the C99 standard. And indeed some segmented architectures will trap on these instructions.

So it's not portable in the sense that it works when compiled by compliant compilers on these architectures.

Indeed. Typically memcmp doesn't. The standard...

2011-01-12T09:37:27.141-08:00

Indeed. Typically memcmp doesn't. The standard function that do is memmove. Its probably easy to add a test to check whether the overlap cause problems with the algorithm. Since the algorithm uses 32/64 bit blocks, the special cases are dependent on alignment, but shouldn't be hard to add in order to get the characteristics of memmove

Your code does not account for cases when the memo...

2011-01-10T21:38:18.718-08:00

Your code does not account for cases when the memory region pointed by the source overlap the memory region pointed by the destination.

its my understanding that things like the glibc an...

2010-12-29T18:18:31.112-08:00

its my understanding that things like the glibc and related libs are not using any worthwhile SIMD optimised instructions at this time for several routines, perhaps you should investigate and try some options.

see:
http://www.freevec.org/content/commentsconclusions

"... Finally, with regard to glibc performance, even if we take into account that some common routines are optimised (like strlen(), memcpy(), memcmp() plus some more), most string functions are NOT optimised. Not only that, glibc only includes reference implementations that perform the operations one-byte-at-a-time! How's that for inefficient? We're not talking about dummy unused joke functions here like memfrob(), but really important string and memory functions that are used pretty much everywhere, like strcmp(), strncmp(), strncpy(), etc.
In times where power consumption has become so much important, I would think that the first thing to do to save power is optimise the software, and what better place to start than the core parts of an operating system? I can't speak for the kernel -though I'm sure it's very optimised actually- but having looked at the glibc code extensively the past years, I can say that it's grossly unoptimised, so much it hurts."

I am a beginner who has not quite understand with ...

2010-12-11T21:17:30.380-08:00

I am a beginner who has not quite understand with this. just greetings from tyang @ codeprogram.blogspot.com just a beginner programer's blog

Sorry I don't understand . Isn't it true t...

2010-12-03T18:00:28.623-08:00

Sorry I don't understand . Isn't it true that "memcmp" and "memcpy" are implemented using only 1 x86 instruction? (Only one x86 machine language is executed to perform the whole copy in one shot)
In that case, how these functions can be optimized by any algorithm using For Loops?

Its probably more common with data being aligned a...

2010-08-13T22:25:12.384-07:00

Its probably more common with data being aligned and nowadays built-in memcpy implementations are usually faster for these cases. If you have a mix of unaligned and aligned copies and speed is important, you can always use the built-in memcpy for aligned copies and this one for unaligned. Otherwise I would stick with the built-in. Processors nowadays are so fast so time spent in memcpy isn't a big issue, but there are cases when it matters and then its good with options...

I've been testing your memcpy() on an embedded...

2010-08-12T18:40:26.274-07:00

I've been testing your memcpy() on an embedded system, Arm7 under the iar compiler.

I tried several configurations of the memcpy(), with or without indexes and pre incremented pointers and I'm only getting about 65% of the performance of the compiler built-in version. The performance of copying aligned to unaligned or unaligned to aligned buffers is much quicker with your memcpy() however, about 2x faster.

Chris

Just wanted to let you know that I'm seeing co...

2010-08-12T18:29:59.408-07:00

Just wanted to let you know that I'm seeing compiler warnings about unreachable statements from the 'break;' statements after the COPY_XXX() macros because the macro is returning.

I think you are using it correct. Not sure what op...

2010-07-05T21:49:19.693-07:00

I think you are using it correct. Not sure what optimization you turned on, but I don't think you'll beat the standard memcpy when copying aligned data on a standard processor. Nowadays, most standard library memcpy's are pretty good, especially on established processors.

This implementation is mainly beneficial if you are running a new embedded processor and sometimes on other systems (like initial versions of clib for PSP).

Occasionally this implementation works better than standard implementations on unaligned data, even on more established processors, but I wouldn't bother testing it on e.g. x86-64 unless speed is really a big problem.

I tried this as-is in a c++ project compiled with ...

2010-06-16T17:30:08.694-07:00

I tried this as-is in a c++ project compiled with Xcode for x86_64 on a Mac Mini with the following code:

int copy1[50];
int copy2[50];
for (int i = 0; i < 500000000; ++i)
{
memcpy(copy1, copy2, 50 * sizeof(int));
}

The standard memcpy took about 7 seconds, the new memcpy took about 14 seconds. Am I using it in the wrong environment, or with the wrong data set to take advantage of its speed?

I actually used early on, but Duff's device on...

2010-04-23T23:12:00.946-07:00

I actually used early on, but Duff's device only works well for pre and post increment. Most targets seem to work best with indexed copy, and then you can't use Duff's device like presented on the wiki. It is easy though to replace the while (length & 7) in COPY_SHIFT with a switch statement, but iirc, it didn't really give a performance boost. But such switch statement isn't a DUff's device since it doesn't have the while loop, but the idea is similar.

I'm amazed that you haven't mentioned Duff...

2010-03-20T01:21:21.536-07:00

I'm amazed that you haven't mentioned Duff's device anywhere. Am I missing something? http://en.wikipedia.org/wiki/Duff%27s_device