Google Interview Question
Country: United States
Interview Type: Phone Interview
memmove(void * dest,void * src, int len)
{
if(dest <= src)
{
for(int i=0;i<len;i++)
{
dest[i]=src[i];
}
}
else
{
for(int i=len-1;i>=0;i--)
{
dest[i]=src[i];
}
}
}
//optimisation goes in multiple directions
//1. Using natural arithmetics for 32bit you can do 4 bytes at once
//2. using movement instructions in assembly (DMA?)
//3. paralel computation, but issue is, that bottleneck is RAM acess time.
dest[i] doesn't make sense for a void pointer. Also, len should be unsigned of type size_t.
1. First see if it's 32-bit or 64-bit machine, and copy 4 or 8 bytes at a time.
2. AFAIK x86 does not support moving from and to memory?
3. Not sure Most of reads/writes will be made to cache so
as long as you copy sequentially going parallel won't help unless
you can specify which core each thread should be scheduled.
But I guess this is worth mentioning to the interviewer.
Here is the code:
void* __memmove__(void* s, const void* d, size_t size) {
if (s == d)
return d;
char* myS = (char*)s;
char* myD = (char*)d;
long long direction = 1;
if (myD < d && (myS + size) > d) {
myS = myS + size - 1;
myD = myD + size - 1;
direction = -1;
}
for (long long i = 0; i < size; i++) {
*myD = *myS;
myS += direction;
myD += direction;
}
return (void*)myD;
}
One optimization I can think of is casting void* to (long long*) and copy 8 byte at a time. After that, you have to copy the remaining data byte by byte
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void* mymemmove(void* dest, void* source, size_t num)
{
unsigned char* destc = (unsigned char*)dest;
unsigned char* sourcec = (unsigned char*)source;
for ( ; num > 0; --num )
{
destc[num-1] = sourcec[num-1];
}
return destc;
}
int main()
{
char* str = (char*)malloc(100);
memset(str, 0, 100);
strcpy(str, "memmove can be very useful......");
mymemmove(str+20, str+15, 11);
puts(str);
free(str);
return 0;
}
void * memove(void *dest, void *src, size_t n)
- siri.paddu December 06, 2012{
char *d =(char *)dest;
char *s =(char *)src;
if(s == d)
return dest;
if(s < d) {
//copy from back
s=s+n-1;
d=d+n-1;
while(n--)
{
*d-- = *s--;
}
}
else {
//copy from front
while(n--)
*d++=*s++;
}
return dest;
}
optimisation suggested to use int and float may not work all time as the address need to be exact divisible of 4 or 8 depending on machine and memory alignment.
The while loop can be optimised by using loop unrolling.
This was the answer expected by the interviewer.