Shrink int array C

Question

Just started to learn C and came across the following issue:

I need to shrink an integer array in C, removing elements at the end. By removing I mean freeing. The common answer is to allocate new memory for the smaller array, after which to copy all items ( -items to remove ) of the original array into the newly allocated memory, and then free() the original array.

Because I must deal with very large arrays, I'd rather skip the copying part.

Would it be possible to create a pointer variable that points to "near the end of the original array" of size "end of array - near the end", and then free that pointer?

Thanks in advance

Elytron

You can shrink using realloc. It's not guaranteed but some implementations will actually give you back the original pointer you passed, without copying anything. – Leaseholder

Have you considered using realloc? – Grinder

Will realloc also free whatever elements are dropped at the end? I wouldn't know how to test this… thanks for the quick response by the way! – Elytron

Well it would resize the amount of allocated space to whatever you tell it to (either bigger or smaller) I will provide an example below. – Grinder

To answer part of your question, it's not possible for free() to release part of a memory block by passing a pointer "near the end". That would almost certainly cause a crash or heap corruption. – Tomfool

comment to the EDITed section: have you properly malloc'ed the data array, before passing it to this function ? – Gallaway

" Does the data (array) in question have to be allocated using malloc" -- Yes, certainly. Please read your documentation for malloc and realloc. – Riff

Answer 1

The realloc function from the C standard library might be what you want.

In your case, it is likely to NOT perform any copy operation, because the memory manager has no reason to allocate a new memory zone. Only the difference between the old and new size might be reclaimed by the system as available memory.

Copy would occur in the case you make your array bigger, because malloc and friends do not guarantee that the memory after the 'current' zone is actually free. If it is, then it's ok, the current memory allocation will be expanded. If not, a bigger available memory zone needs to be found, and it can be allocated pretty much anywhere in memory.

Gallaway

It's also likely to not actually free any memory for reuse. – Sheley

@Sheley That simply isn't so ... shrinking a buffer via realloc makes the deallocated memory available to malloc (unless it's below malloc's chunk size). It may not return the memory to the OS, but neither will malloc/copy/free. – Riff

Thanks for the clear answer. But what ddyer said is what actually worries me. – Elytron

@Jim Balter All I needed to know ;-) – Elytron

@JimBalter: The realloc routine is not defined to make the deallocated memory available for new allocation. Whether it does so or not is up to the implementation. The malloc family of routines is difficult to implement well, due to the wide variety of applications it must serve and the trade-offs between time and memory. Taking the additional space and time to track a small amount of memory released from a large allocation might not be efficient. – Underbred

@EricPostpischil I didn't say anything about how it is defined. I've written several commercial malloc/reallocs and have studied the code of others and know well how they are implemented. It is simply false that is is "likely not to" free the memory ... the vast majority of available reallocs do so. And failing to track memory released from large allocations leaks memory. Certainly its an option to to treat a realloc of a slightly smaller size as a noop, but free enough of the buffer and that space will be available for reuse. – Riff

If it doesn't make memory free then what does it do? And what would happen to the memory it's no longer using? – Grinder

@KeithMiller If you malloc a large buffer and then realloc it to a slightly smaller size, that realloc could simply be a noop, leaving the allocated size unchanged. But this is only done for small differences, not large ones. (In practice, not "by definition", of course.) – Riff

Good discussion on the behavior of realloc. I agree with all of it, especially the part about "difficult due to variety of applications". It's just as plausible that the leftover memory could be held in reserve, so that a future realloc of the same array could magically grow the array without reallocating it. My point is the user can't depend on the memory being reused, even if it seems to be being reused today on his particular platform. – Sheley

@JimBalter: The implementation would not lose track of a small amount of memory released from a large allocation. It would simply keep it with the large allocation. The memory would not be available for reuse until the entire allocation were freed or another reallocation shortened the requested space sufficiently that the implementation considered it worth splitting up the memory. Your reported experience is insufficient grounds for an unqualified claim that realloc makes deallocate memory available. It depends on the implementation. – Underbred

@EricPostpischil "It would simply keep it with the large allocation." -- I already said that, TWICE. "insufficient grounds" -- ridiculous pedantry which misses the point that ddyer's unsupported "likely to not" claim is factually false. I repeatedly referred to actual implementations. Yes, it does depend on whether one is using one of those or some imaginary one of inexplicably low quality. My last word on this. – Riff

@JimBalter: Deducing behavior from specifications is engineering, not pedantry. Assuming favorable implementations without documentation causes bugs. Trading small amounts of memory (especially net negative amounts when the accounting cost exceeds the size of the released space) for speed is not low quality; it is optimizing for performance. – Underbred

Answer 2

Have you thought about using realloc ?

int main(void)
{
    int *array = NULL, *tmp;

    if(!(array = malloc(5 * sizeof(int)))) return 1;
    if(!(tmp = realloc(array, 2*sizeof(int)))) 
    {
        free(array);
        return 1;
    }
    array = tmp;
}

You can do this without the tmp pointer and just have array = realloc(array, 2*sizeof(int)))) but that could result in problems later down the road.

Grinder

Answer 3

It's possible to design a memory manager that would make that possible, but none of the commonly used memory managers have this property. You could write your own mm and use it for these arrays.

Sheley

Answer 4

I would use realloc. Realloc may copy the memory, but this could still be more efficient than rolling your own memory management to combat the problem of copying.

Some will tell you that no well-behaved C library will copy when the resulting size is smaller. They are probably right. However, I don't use or write commercial C libraries, so as far as I'm concerned the claim is unsubstantiated.

Merylmes

Except in the special case of debugging options that prevent freeing any memory, all commercial library reallocs avoid copying if the size shrinks (or stays the same) ... why wouldn't they? – Riff

Agreed; although to my knowledge this is not guaranteed/in the specification. – Merylmes

People keep talking about guarantees from the specification in response to my comments that say nothing about that. The specification does not guarantee that malloc will ever return anything but NULL. Understanding specifications is important, but if that is all one understands, it's pedantry, not engineering. – Riff

I don't disagree with any particular point, and I promise I won't put words in your mouth if you afford me the same courtesy. – Merylmes

I'm just pointing out that, when I talk about "all commercial library reallocs", a comment about specifications is a non sequitur or strawman. Certainly there's no guarantee in the specification that realloc won't copy ... there's no guarantee that it will succeed at all ... but that simply isn't interesting to practicing programmers. – Riff

You're wrong. First, I think you misinterpreted my original comment; it was not meant to be pointed. It was simply to illustrate that one may not achieve the behavior expected when using realloc. Second, there is some debate as to whether "all commercial libraries" implement realloc in the way you describe; you've not backed up your statement in any way. Finally, you're claiming that my assertion of the specification is not interesting to practicing programmers which is also not something you can realistically claim. You criticize me on my points without backing up yours! – Merylmes