And this is why OpenSource is awesome.
A Story Of realloc (And Laziness)
21–30 of 65 posts
Re: A Story Of realloc (And Laziness)
#22Earlier quoted context omitted.
Are you saying that vector with 'grow()' is substantially slower than the given C macro ? By how much ?
It always calls (the equivalent of) malloc + memcpy + free for each grow, so it can be anywhere from the exact same speed (when realloc does the same thing internally) to absurdly slower (in the given case of a large array that has to be paged in). The first case is by far the most common case, but it is something that sometimes matters.
Huh, is it really implemented like that?!
Why use realloc when growing an array you have an interface to? Just add another allocated buffer to the previous allocated areas. When there are too many small areas, consolidate with realloc/free.
Much faster (yes yes, almost always).
(Disclaimer: Last time I used C++ I had hair. :-) )
Edit: OK, thanks plorkyeran.
Re: A Story Of realloc (And Laziness)
#23Earlier quoted context omitted.
It always calls (the equivalent of) malloc + memcpy + free for each grow, so it can be anywhere from the exact same speed (when realloc does the same thing internally) to absurdly slower (in the given case of a large array that has to be paged in). The first case is by far the most common case, but it is something that sometimes matters.
Huh, is it really implemented like that?! Why use realloc when growing an array you have an interface to? Just add another allocated buffer to the previous allocated areas. When there are too many small areas, consolidate with realloc/free. Much faster (yes yes, almost always). (Disclaimer: Last time I used C++ I had hair. :-) ) Edit: OK, thanks plorkyeran.
std::vector guarantees that it stores its elements contiguously, as this is required for a lot of use-cases (such as passing the buffer to one of the millions of functions that take just a pointer and a size).
Re: A Story Of realloc (And Laziness)
#24Earlier quoted context omitted.
Serious question from a guy made soft by garbage collection: how frequent is memory allocation failure nowadays, with large memories and virtual memory? Were I to guess from my state of ignorance I'd think that if allocs began to fail, there was no recovery anyhow... so leaking in this case would be one leak right before a forced quit. Wrong? Are there lots of ways allocation can fail besides low memory conditions?
Memory allocation failures are virtually non-existent in modern desktop computers. Good practice is to not test return values from malloc, new, etc. Memory can be allocated beyond RAM size, so by the time a failure occurs your program really should crash and return its resources. Embedded systems have fewer resources and some will not have virtual memory and so the situation will be different. But unless you know bet…
I respectfully disagree with this. Ignoring return values is _not_ good practice. It is a slippery slope to bad software. By catching these memory errors, a program has the chance to properly teardown and report a message to the user instead of crashing.
Re: A Story Of realloc (And Laziness)
#25Code in the article for realloc is dangerous and wrong: void *realloc(void *ptr, size_t size) { void *nptr = malloc(size); if (nptr == NULL) { free(ptr); return NULL; } memcpy(nptr, ptr, size); // KABOOM free(ptr); return nptr; } Line marked KABOOM copies $DEST_BYTE_COUNT, rather than $SOURCE_BYTE_COUNT. Say you want to realloc a 1 byte buffer to a 4 byte buffer - you just copied 4 bytes from a 1 byte buffer which me…
"Also, this is why the ENTIRE PREMISE of implementing your own reallocator speced to just the realloc prototype doesn't make much sense."
If you're reimplementing realloc() it's pretty easy to know the size of the allocated regions - you just need to store the size somewhere when you allocate a block. One common method is to allocate N extra bytes of memory whenever you do malloc() to hold the block header and return a pointer to (block_address + N) to the user. When you then want to realloc() a block, just look in the block header (N bytes before the user's pointer) for the size.
The block header can store other useful stuff, like debugging information. I once implemented a memory manager for debugging that could generate a list of all leaked blocks at the end of the program with the file names and line numbers where they were allocated.
Re: A Story Of realloc (And Laziness)
#26Code in the article for realloc is dangerous and wrong: void *realloc(void *ptr, size_t size) { void *nptr = malloc(size); if (nptr == NULL) { free(ptr); return NULL; } memcpy(nptr, ptr, size); // KABOOM free(ptr); return nptr; } Line marked KABOOM copies $DEST_BYTE_COUNT, rather than $SOURCE_BYTE_COUNT. Say you want to realloc a 1 byte buffer to a 4 byte buffer - you just copied 4 bytes from a 1 byte buffer which me…
Yes, indeed - but the code was not meant to be an actual implementation, just a (bad) minimalistic example.
Re: A Story Of realloc (And Laziness)
#27Earlier quoted context omitted.
Serious question from a guy made soft by garbage collection: how frequent is memory allocation failure nowadays, with large memories and virtual memory? Were I to guess from my state of ignorance I'd think that if allocs began to fail, there was no recovery anyhow... so leaking in this case would be one leak right before a forced quit. Wrong? Are there lots of ways allocation can fail besides low memory conditions?
Memory allocation failures are virtually non-existent in modern desktop computers. Good practice is to not test return values from malloc, new, etc. Memory can be allocated beyond RAM size, so by the time a failure occurs your program really should crash and return its resources. Embedded systems have fewer resources and some will not have virtual memory and so the situation will be different. But unless you know bet…
Ugh. I would much rather know that the process died because of allocation failure than try to figure out why some code is trying to write to a random null pointer as these are two very different types of bugs.
Re: A Story Of realloc (And Laziness)
#28The realloc implementation in this blog is incorrect: the passed in pointer must not be freed if realloc is called with a non-zero length and returns NULL. This will cause a double free in correct callers. As someone else pointed out, the example call of realloc is also incorrect. edit: also, malloc is incorrect for three reasons: 1) sbrk doesn't return NULL on failure, 2) a large size_t length will cause a contracti…
I fixed the double free. I must admit that the code was typed as I wrote the blog entry, and is horribly wrong :)
Re: A Story Of realloc (And Laziness)
#29Code in the article for realloc is dangerous and wrong: void *realloc(void *ptr, size_t size) { void *nptr = malloc(size); if (nptr == NULL) { free(ptr); return NULL; } memcpy(nptr, ptr, size); // KABOOM free(ptr); return nptr; } Line marked KABOOM copies $DEST_BYTE_COUNT, rather than $SOURCE_BYTE_COUNT. Say you want to realloc a 1 byte buffer to a 4 byte buffer - you just copied 4 bytes from a 1 byte buffer which me…
In the context of the code presented all mallocs were returned by sbrk. Even if the previous malloc had been "allocated" with size zero, the sbrk called by this function's invocation of malloc will ensure that there are enough bytes of addressable memory to ensure that, although it will be copying data out of earlier allocations, it will not segfault. realloc makes no guarantees of zero-initializing a newly allocated extent.
Re: A Story Of realloc (And Laziness)
#30I fixed a crippling bug on another platform that was taking down whole servers, because someone was depending on a clever realloc to behave well. This is implementation coupling at its worst. Don't do it.
Yes and no. The real error here would be to realloc without any geometric progression IMHO - ie. reallocating one more byte each time, which would behave well on Linux (except the libc call cost of course) but not on other implementations (such as some Microsoft's MSVCRT versions). Assuming realloc has no catastrophic performance impact is not something too daring.