6
\$\begingroup\$

I have tried to write a function like memcpy. It copies sizeof(long) bytes at a time.

What surprised me is how inefficient it is. It's just 17% more efficient than the naivest implementation with -O3. With optimizations off it's a lot faster than the naivest, so perhaps the compiler is doing this automatically?

It will copy 1 byte at a time until one of the addresses is aligned, then it will copy sizeof(long) and then 1 byte at a time to avoid writing beyond the bounds.

How can I make this faster?

#include <stdlib.h>

#define THRESHOLD sizeof(long)

static size_t min(size_t a, size_t b)
{
    return (a > b) ? a : b;
}

static void big_copy(void *dest, const void *src, size_t iterations)
{
    long *d = dest;
    const long *s = src;

    size_t eight = iterations / 8;
    size_t single = iterations % 8;

    while(eight > 0){
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        *d++ = *s++;
        --eight;
    }

    while(single > 0){
        *d++ = *s++;
        --single;
    }
}

static void small_copy(void *dest, const void *src, size_t iterations)
{
    char *d = dest;
    const char *s = src;

    while(iterations > 0){
        *d++ = *s++;
        --iterations;
    }
}

void *copy_memory(void *dest, const void *src, size_t size)
{
    //Small size is handled here
    if(size < THRESHOLD){
        small_copy(dest, src, size);
        return dest;
    }

    //Start copying 8 bytes as soon as one of the pointers is aligned
    size_t bytes_to_align = min((size_t)dest % sizeof(long), (size_t)src % sizeof(long));
    void *position = dest;

    //Align
    if(bytes_to_align > 0){
        small_copy(position, src, bytes_to_align);
        position = (char *)position + bytes_to_align;
        src = (char *)src + bytes_to_align;
        size -= bytes_to_align;
    }

    //How many iterations can be done
    size_t safe_big_iterations = size / sizeof(long);
    size_t remaining_bytes = size % sizeof(long);

    //Copy most bytes here
    big_copy(position, src, safe_big_iterations);
    position = (char *)position + safe_big_iterations * sizeof(long);
    src = (char *)src + safe_big_iterations * sizeof(long);

    //Process the remaining bytes
    small_copy(position, src, remaining_bytes);

    return dest;
}
\$\endgroup\$
  • \$\begingroup\$ I think it should be noted that in the Internet, this very code has been presented as an example of a not obvious UB. See blog.regehr.org/archives/1307 , especially section Chunking Optimizations Are Broken. I’m a layman, but the concern seems to me to be either well-founded. \$\endgroup\$ – gaazkam May 23 '17 at 21:54
4
\$\begingroup\$

The last time I saw source for a C run-time-library implementation of memcpy (Microsoft's compiler in the 1990s), it used the algorithm you describe: but it was written in assembly. It might (my memory is uncertain) have used rep movsd in the inner loop.

Your code says, //Start copying 8 bytes as soon as one of the pointers is aligned. When you're performance-testing you should know (because that's when you might expect the best performance) whether both buffers are aligned.

On the subject of alignment there as an interesting (but unrelated to your question) question here on StackOverflow: Why speed of memcpy() drops dramatically every 4KB?

I vaguely understand what kind of an effect you're looking for in your code. I don't know what assembler your compiler is actually producing.

The accepted answer to this StackOverflow question demonstrates the kind of assembly that is used nowadays: Very fast memcpy for image processing?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.