Moving arrays with a c library

i'm writing small library that moves elements inside overlapping arrays and for efficiency's sake, it is important if it is being moved from left to right or right to left. this may seem like a basic question, but please hear me out....

if it is being compiled with the option of a loop doing it:
left to right:

for ( i = 0; i < n; )
dest[i] = src[i];
will not suffice, as the highest members of src MIGHT get overwritten by the TO-BE lower members of dest, so it has to be done this:

for ( i = n; i--; )
dest[i] = src[i];

same could be said if you're doing a right to left move:
for ( i = n; i--; )
dest[i] = src[i];

won't do so:
for ( i = 0; i < n; )
dest[i] = src[i];


THIS IS THE QUESTION:
now, this is all well and settled, but i want to include the option of it being compiled with optimized moving instructions such as those found in SSE, possibly made available by libraries, such as, the string.h library. i've looked through it and other libraries out there, but i can't find one that explicitly does the moving/copying in a right-to-left or left-to-right fashion.

This should actually be pretty simple. If the "head pointer" is less than the "tail pointer" you need to move one way, if the tail is leas than the head you need to move the other. If they're equal you can do nothing.

One of the great parts about C is that functions like memcpy() etc. are basically the same loops you will get from for() loops. It's very close to assembler in efficiency.

Quote:

---

Originally Posted by CommonTater

This should actually be pretty simple. If the "head pointer" is less than the "tail pointer" you need to move one way, if the tail is leas than the head you need to move the other. If they're equal you can do nothing.

One of the great parts about C is that functions like memcpy() etc. are basically the same loops you will get from for() loops. It's very close to assembler in efficiency.

---

#&%*$!*()&!!!
("oh, i think he's just having a bit of confusion! funny how the difficult questions done by some people but they get stuck on the very basic ones!" you must think...)


i don't think you understood.... i'm sorry for snapping... but like i said, you DIDN'T understand.

it's not an issue on WHEN on deciding to do a left-to-right or a right-to-left, but an assurance that the function OR CPU instruction will do it like so (left-to-right or a right-to-left). ok, let's forget about standard libraries or APIs and do it in an assembler fashion. in the standard x86 instruction listing, the MOVSB instruction is done, as far as i know in the regular manuals, as UNDEFINED to be moved right-to-left or left-to-right.

that, i believe is the distinction between memcpy and memmove for OVERLAPPING arrays. in an architecture like x86 whose MOVSB is undefined in such a way (LEFT-TO-RIGHT, RIGHT-TO-LEFT) and memcpy is used, it doesn't matter, as it is undefined when they overlap. on memmove, since it is undefined and MOST LIKELY, it does it by looping ... MOST LIKELY LOOPING. like i said, most likely.... but i don't know for sure.



-- see, it's annoying when somebody passes a quick look at the subject to get to a conclusion most desirable to them and then condescend a completely honest question... or maybe i'm just artificially looking fo ran anemy to get myself fired up again, i dunno

anyways, that being said, i might as well just stick to memmove for every overlapping situations, but i just like more assurance.

Doesn't matter if it's all in CPU cache. Otherwise moving from lower address to higher address may be faster because, as far as I know, on a cache miss, the cache line the CPU fetches will start on the address you request, so moving from higher address to lower address may generate many more cache misses.

But why are you doing this? Isn't this exactly what memmove does? What more "assurance" do you get by writing your own exact same likely inferior version?

Quote:

---

Originally Posted by cyberfish

Doesn't matter if it's all in CPU cache. Otherwise moving from lower address to higher address may be faster because, as far as I know, on a cache miss, the cache line the CPU fetches will start on the address you request, so moving from higher address to lower address may generate many more cache misses.

But why are you doing this? Isn't this exactly what memmove does? What more "assurance" do you get by writing your own exact same likely inferior version?

---

no, i'm not writing my own moving (sorry, copying, i'm trying to stick on cpu terminology for now) function, i'm looking for a function that will do it r2l or l2r assured. and it won't stay in the cache. unless when transfering/copying an array from memory directly to cache, moving it in higher address in cache, then moving it back to the memory (without any modifications) is faster than moving it directly within the memory.

Quote:

---

i'm looking for a function that will do it r2l or l2r assured

---

And why do you need that? Isn't the end result exactly the same?

It's like saying when you do "a = Add(1, 2)" you want a version that adds 2 to 1 and another that adds 1 to 2.

You can't move anything directly within memory. Everything has to go through the CPU cache, at least on an architecture like x86. CPU cache also doesn't have an addressing space. It's divided into "cache lines" (little blocks) that mirror the blocks in memory that you recently accessed. When you ask for that address again, the memory management unit remembers it's in cache, and feed you that data without going to memory.

alright, i don't think you understood the subtlety of l2r and r2l

Code:

---

src[] = {1,2,3,4,5, pad.....}
dest= src + 3;
l2r:
for ( i = 0; i < 5; )
    dest[i] = src[i];

result:
dest[] = {1,2,3,1,2,3,1,2, pad if any}

r2l:
for ( i = n; i--; )
  dest[i] = src[i];

result:
dest[] = {1,2,3,1,2,3,4,5, pad if any}

---

see? one just does not suffice for the other. i want to effect of the second loop. the inverse applies to the other r2l. does memmove do this? how i can i be sure? i know it's too hardware specific. so if there's any library that brings this feature higher-up to the surface it would be very nice.

Yes, memmove does this. By definition.

If you look at memmove's description

Quote:

---

void * memmove ( void * destination, const void * source, size_t num );
Move block of memory

Copies the values of num bytes from the location pointed by source to the memory block pointed by destination. Copying takes place as if an intermediate buffer was used, allowing the destination and source to overlap.

The underlying type of the objects pointed by both the source and destination pointers are irrelevant for this function; The result is a binary copy of the data.

The function does not check for any terminating null character in source - it always copies exactly num bytes.

To avoid overflows, the size of the arrays pointed by both the destination and source parameters, shall be at least num bytes.

---

If an intermediate is used, it would be something like

temp = src[0...4] = { 1, 2, 3, 4, 5 }
dest = temp = { 1, 2, 3, 4, 5 }
so
src = { 1, 2, 3, 1, 2, 3, 4, 5 }

This is guaranteed by the C standard. Yes, there may be differences on the hardware level. But you don't need to care. The C standard promises that memmove will always give you the same result AS IF a temporary buffer is used. How it does that is their problem.

more like functions should have been provided:

tohigheraddr(dest, src, size)
toloweraddr(dest, src, size)

mov(dest, src, size)
/* ^ implicitly does a comparison of which of the 2 functions to call */

Quote:

---

it's not an issue on WHEN on deciding to do a left-to-right or a right-to-left, but an assurance that the function OR CPU instruction will do it like so (left-to-right or a right-to-left). ok, let's forget about standard libraries or APIs and do it in an assembler fashion. in the standard x86 instruction listing, the MOVSB instruction is done, as far as i know in the regular manuals, as UNDEFINED to be moved right-to-left or left-to-right

---

Oh I understood you well enough.
C libraries contain many function calls that are beneficial to programmers. But they are largely unknowns provided simply for convenience. Nothing forces us to use them. My point is that if you want some function to behave in a known and guaranteed way, your best bet is to write the thing yourself.