Fast Approximation to memcpy()

i wont even start to code that in asm: wasnt that just a loop, asm loop ?

like in single c++

for (int i=0; i < len; i++)

destination = source;

you anyway pass an array of addresses of the source

the less instructions you write the better

:wub:

somehow i cant imagine to just throw set of bytes, into other memory region

Since you asked for an "approximation" to memcpy:

void *src; // assumed that this is set to something valid

void *dst; // assumed that this is set to something valid

dst = src;

There you go! Approximately equivalent to memcpy!

Just map the same physical region to another virtual address. Same content, zero copy. Different addresses!

making a good memcpy or memset is excruciatingly hard (huh, did I spell that right?) mostly because you don't know in advance.

Wait, you don't know? What is it you don't know? Well... everything.

You don't know on which CPU your code will run, you don't know how large the block will be (not at the time of writing the memcpy function anyway!) and you don't know what access pattern is going to be used (nor is there a way to communicate this over that API).

On some CPUs, something like REP STOS is the fastest way up to about half a kilobyte or a kilobyte. On others, a simple 4-times unrolled loop in C copying a uint64_t at a time is faster. At some point, it turns around. On some CPUs, SSE4.1 string instructions are fastest, on some they are not, and on some they don't even exist. For blocks greater than so-and-so-many bytes, using SSE registers either way (even SSE2) is faster than registers. Depending on whether or not you are soon reading back the data (e.g. fill a buffer handed to GPU), using write-combining writes is faster and more efficient, but in every other case it's slower. On some CPUs, you must use several threads to saturate memory bandwidth. Prefetching is advantageous, sometimes. And sometimes it is only extra instructions which are slower overall. Usually, almost always, your intuition tells you the wrong thing and you would have been better not prefetching at all.

SSE optimized versions may or may not overwrite without causing a fault if you are being careless, and with no easy way of detecting the problem. Admitted, non-SSE code can do that as well, but you still have a good chance of getting a crash (which is a good thing!). SSE writes are pretty much guaranteed to hide the issue.

Why? Well, because it so happens that your SSE writes are always properly aligned, and thus always fit snugly into a page (because 4096 is a greater power-of-two than 16), so you don't get a segmentation fault if your last write accidentially garbled some bytes past the end. All you get is garbled data, and maybe a crash in a different, unrelated piece of code much later, but never a segfault when it should happen.

I would not be surprised if there even existed systems where remapping pages and thus pulling a page from the operating system's zero page pool was the fastest possible way of zeroing memory (and I wouldn't be surprised if there existed systems which abused DMA in some way (network card, graphics card? disk controller!?) to do memset or memcpy in hardware).

On almost all systems, for all "not terribly huge" sizes, the badly predictable branches necessary to find the best, optimal solution for each case are almost as expensive as the savings, so unless you are operating on a small compiletime-known size, you're kinda lost... and in that case, the compiler would replace the vanilla library call with an optimized inline version anyway. Any no-shit compiler in a release build would, at least.

So, all in all... it's a bit of a totally-no-fun endeavour. I'm just using the C standard library's function. Which, hopefully, is always good enough.

or use gpu lel

Just map the same physical region to another virtual address. Same content, zero copy. Different addresses!

Hahaha, that too! :D

This is a treacherous way of doing it, though. Unless you map the memory CoW, writing to one block of memory will (obviously) modify the other. Which is almost certainly not what the unwitty observer would expect to happen. But if you map it CoW, you have the same insidious behaviour that people writing servers experience with fork.

You fork, this took slightly under half a millisecond, and it's all fine and dandy, everything just works, life is good. And then either the parent or the child process writes to memory. Oh fuck... suddenly everything is so slow, I cannot understand why there are so many page faults. Latencies in the hundreds of milliseconds. What's going on! (This is for example a well-known "issue" with redis. Not really an issue but a technical necessity, but still... well-known enough to have its own FAQ page, and about 30k web sites writing about it.)

The nasty thing is that the reason why all these faults happen all of a sudden is not obvious (well... it is, but... not to you, at that time -- from your perspective there is no reason why they should happen). A second earlier, all was good, and now every memory access causes a fault. You didn't even touch anything! And to top it off with sugar, it's operating-system dependant...

And then, to maximize your joy, you are running on a Linux system with huge pages enabled, and you no longer understand a thing...

Don't forget about overcommiting. Enjoy processes dying out of nowhere without any warning or explanation.

As for speed, reminds me of a situation I had with memcmp. Apparently at least on some implementations it's optimized for comparing large chunks of data when I was using it to compare a few bytes instead - but not a fixed amount so the compiler can't just unroll it. And this was in a tight loop. Turns out that the overhead of preparing for a large comparison outweighted the benefit, to the point that simply adding a simple check for the first byte (since most comparisons would fail) would speed it up like crazy.

Just because the standard library is probably better optimized than what you can do doesn't necessarily mean it'll be best optimized for your actual case.

void memcpy(void* dst, void*src, size_t size)
{
                if (size >= 1 && dst != src)
                {
                                *dst = *src;
                }

                // The rest can’t be that important
}

Can't you just use a lookup table, like you do with the trigonometry functions?

Just create an array of RAM, then set the destination equal to ram[sourceAddress].

Depends on how much is good enough:

[source]

const int GOOD_ENOUGH_PERCENT = 95;

void *memapprox(void * destination, const void * source, size_t num) {

memcpy(destination, source, num * GOOD_ENOUGH_PERCENT / 100);

}

[/source]

const char GOOD_ENOUGH_MASK    = 0xF8;
const int  GOOD_ENOUGH_PERCENT = 90;

// uses less power than memcpy
void* memcpy_approx(void* dst, const void* src, size_t len) {
    char* pdst = (char*)dst;
    const char* psrc = (char*)src;
    const char* pend = psrc + (len * GOOD_ENOUGH_PERCENT / 100);

    while ( psrc < pend ) {
        *pdst++ = *psrc++ & GOOD_ENOUGH_MASK;
    }

    return dst;
};

how about:

for (a=count; a>0; a--, *(p1+count-a)=*p2+count-a));

it does a dec (sometimes faster), and pointer math to boot!

does it even compile?

Edit: Aw! Fastcall be me to the pointer math.

50% accuracy!

for (int i = 0; i < len; i += 2)
    dst[i] = src[i];

Lets not care about anything :)

template<class T>
void memcpyApproximation(void* dest, void* src, size_t size)
{
    T::memcpy(dest, src);
}

void memcpy(void *dest, void *src, size_t size)
{
  strncpy((char*)dest, (const char*)src, size);
}

This one actually works... within a given assumption :wink:

void memcpy(void *dest, void *src, size_t size)
{
  assert(dest == src);
}

I'm surprised no one came with a solution using 3 or 4 boost template classes that would magically be optimized by the intelligent compiler.

template<typename Type, size_t Num>
constexpr Type[Num] memcpy(Type[Num] src)
{
    return src;
}

Thats the modern C++11 variant. Better syntax (why pass in dest when we have return-values), and zero runtime overhead. And I'm not even sure if that even compiles and/or works, as an added bonus ;)