Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
Do not understand how to deal with the 2nd parameter: size_t alignment. Can anyone explain?
It's got to do with pointer's memory value. A pointer points to any byte value in memory. 64 bit alignment means the pointer should be pointing to a value that is divisible by 8. You get 8 by dividing 64/8. 64 is bits, you have to convert that to bytes. Read up more about C++ memory alignment. For example it helps pack member data in classes.
void * aligned_alloc(size_t size, int alignment_bits) {
//reserve requested size plus: space for allocating a pointer plus spac$
size_t sz=size+sizeof(void*)+(1<<alignment_bits);
char *p0=(char*)malloc(sz);
if (p0==0) return 0;
//advance p to its maximum value
char* p=p0+sizeof(void*)+(1<<alignment_bits);
//cut less significant bits to achieve alignment
p=(char*)((uintptr_t)p&(uintptr_t)~((1<<alignment_bits)-1));
//store real addresss in the previous address
*(void**)(p-sizeof(void*))=p0;
return (void*)p;
}
void alignned_free(void* p) {
free((char*)p-sizeof(void*));
}
void* does not support arithmetic, maybe you mean this code:
void *alignAllocate(size_t size, size_t align) {
int offset = sizeof(void*) + align - 1;
void *rawPtr = malloc(size + offset);
if (rawPtr == nullptr)
return nullptr;
char *ans = (char*)rawPtr + sizeof(void*);
ans = (char*)(long(ans + align - 1) & ~(align - 1));
*((void**)ans - 1) = rawPtr;
return ans;
}
void alignFree(void *ptr) {
void *rawPtr = *((void**)ptr - 1);
free(rawPtr);
}
you're right malinbupt, thank you.
here is my correction:
void * aligned_alloc(size_t size, int alignment_bits) {
//reserve requested size plus: space for allocating a pointer plus spac$
size_t sz=size+sizeof(void*)+(1<<alignment_bits);
char *p0=(char*)malloc(sz);
if (p0==0) return 0;
//advance p to its maximum value
char* p=p0+sizeof(void*)+(1<<alignment_bits);
//cut less significant bits to achieve alignment
p=(char*)((uintptr_t)p&(uintptr_t)~((1<<alignment_bits)-1));
//store real addresss in the previous address
*(void**)(p-sizeof(void*))=p0;
return (void*)p;
}
void alignned_free(void* p) {
free((char*)p-sizeof(void*));
}
Should work for 32/64 bit env.
struct H { void *op; };
typedef void* voidptr;
typedef unsigned char* byteptr;
void* aAlloc(size_t l, size_t a)
{
auto a0 = a >> 3;
voidptr p0 = std::malloc(sizeof(H) + l + a0);
byteptr p = (byteptr)(p0) + sizeof(H);
p += (uintptr_t)p & (a0 - 1);
((H*)p - 1)->op = p0;
return (void*)p;
}
void afree(void *p)
{
std::free(((H*)p - 1)->op);
}
#include <list>
#include <unordered_map>
#include <cstdlib>
std::unordered_map<void*, void*> _alignedToUnaligned;
void * alignedAllocate(size_t sizeInBytes, size_t alignment)
{
if(sizeInBytes == 0)
return nullptr;
if(alignment == 0)
alignment = 1;
void* unaligned = malloc(sizeInBytes + alignment - 1);
void* aligned = unaligned;
auto offset = (size_t) unaligned % alignment;
if(offset != 0)
{
aligned = (void*) ((size_t)aligned + alignment - offset);
}
_alignedToUnaligned[aligned] = unaligned;
return aligned;
}
int alignedDeallocate(void* alignedPtr)
{
auto iter = _alignedToUnaligned.find(alignedPtr);
if(iter == _alignedToUnaligned.end())
{
return -1;
}
auto unaligned = iter->second;
_alignedToUnaligned.erase(iter);
free(unaligned);
return 0;
}
void alignedDeallocate(std::list<void*> alignedPtrs)
{
for(auto ptr : alignedPtrs)
{
alignedDeallocate(ptr);
}
}
I wrote similar code except I used new instead of malloc. I did a new with char* and cast to void* but apparently I did something wrong cause I didn't get selected.
1. you do not handle the situation when malloc returns NULL pointer
2. allocating (sizeInBytes + alignment) bytes right at the beginning could be inefficient if alignment is large. Suppose, sizeInBytes = 1024 and alignment = 1024. Then you'll waste 1024 bytes! While, it's quite likely that malloc already allocates an 1024-byte aligned chunk in this case.
Therefore, it probably makes sense:
- use some memory pool for allocations (to save on fragmentation)
- first issue 'malloc' with original size. Then if it's not properly aligned (or if the alignment is non-standard, e.g., like 127 bytes), use realloc with 'bytes + alignment' size
1. you do not handle the situation when malloc returns NULL pointer
2. allocating (sizeInBytes + alignment) bytes right at the beginning could be inefficient if alignment is large. Suppose, sizeInBytes = 1024 and alignment = 1024. Then you'll waste 1024 bytes! While, it's quite likely that malloc already allocates an 1024-byte aligned chunk in this case.
Therefore, it probably makes sense:
- use some memory pool for allocations (to save on fragmentation)
- first issue 'malloc' with original size. Then if it's not properly aligned (or if the alignment is non-standard, e.g., like 127 bytes), use realloc with 'bytes + alignment' size
1. you do not handle the situation when malloc returns NULL pointer
2. allocating (sizeInBytes + alignment) bytes right at the beginning could be inefficient if alignment is large. Suppose, sizeInBytes = 1024 and alignment = 1024. Then you'll waste 1024 bytes! While, it's quite likely that malloc already allocates an 1024-byte aligned chunk in this case.
Therefore, it probably makes sense:
- use some memory pool for allocations (to save on fragmentation)
- first issue 'malloc' with original size. Then if it's not properly aligned (or if the alignment is non-standard, e.g., like 127 bytes), use realloc with 'bytes + alignment' size
void * alignedMalloc(size_t size, size_t alignment)
{
size_t bytes = alignment / 8;
return malloc(size + (size % bytes) / bytes);
}
void alignedFree(void **p)
{
std::free(*p);
*p = nullptr;
}
do malloc of size (sizeInBytes+sizeAlignment), then from the starting pointer, find the first address that %sizeAlignment gives you 0.
- SK September 05, 2015if size is 1000 and alignment is 64, and malloc gives you a pointer at location 129 for example, it will extend from address 129 to 1093. From 129, we need to find the first pointer that %64 is 0, so we do (129/64 + 1)*64 = 192. From 192, we mark this as the beginning of the allocated space, and we mark 192 + 1000 -> 1192 as the end of the block.
Not sure how to stop memory from being used though.
To delete, Keep track of this distance from the new pointer to the original malloc pointer address.