tags:

views:

273

answers:

5

I have a notion that C++ runtime doesn't do any heap compaction which means that the address of an object created on heap never changes. I want to confirm if this is true and also if it is true for every platform (Win32, Mac, ...)?

+3  A: 

The standard does not specify it, but then the standard does not specify a heap. This is entirely dependent on your implementation. However, there is nothing stopping an implementation compacting unused memory while maintaining the same addreses for objects in use.

anon
Thanks. I guess this implementation could come from a developer doing Memory Mgmt himself or from the runtime. I just want to be sure about the runtimes on Windows and Linux. Can you advise? On Windows, I am using Visual Studio.
HS
As I indicated, there is no standard C++ runtime, so the platform you are running on is not the issue. You need to look at the documentation for the specific C++ implementation(s) you use.
anon
I don't think coalescing free blocks is generally considered the same thing as compacting a heap.
Michael Burr
@Michael Perhaps you would care to differentiate them?
anon
As I understand it, what the OP is asking is whether allocated objects might be moved around, as a garbage collector commonly does.
jalf
@Neil: I think the definitions here are decent: http://www.memorymanagement.org/glossary/c.html#coalesce and http://www.memorymanagement.org/glossary/c.html#compaction
Michael Burr
Thanks Neil, Michael and jalf for your views.
HS
+2  A: 

You are right it does not change. Pages can be moved around in physical memory but the Translation Lookaside Buffer (This is what control virtual memory) hides all that from you.

Goz
+1  A: 

Under normal circumstances when you're using the system compiler's default runtimes, you can safely assume that pointers will not be invalidated by the runtime.

If you are not using the default memory managers, but a 3rd-party memory manager instead, it completely depends on the runtime and memory manager you are using. While C++ objects do not generally get moved around in memory by the memory manager, you can write a memory manager that compacts free space and you could conceivably write one that would move allocated objects around to maximise free space as well.

Timo Geusch
"you could conceivably write one that would move allocated objects around to maximise free space as well" only if you implemented some sort of reference tracking system, such that the programs using said memory manager wasn't storing pointers, only references.
Adam Maras
Thanks. But, I want to be sure about what kind of runtime implementation exists on Windows and Linux. Is there any chance of Heap compaction because of which an address stored becomes invalidated? I am using Visual Studio on Windows.
HS
@Adam Maras - yes, that's correct. I mainly mentioned it because it's possible even if awkward.
Timo Geusch
@HS, under most circumstances, you will be fine and unless you explicitly use a runtime that makes use of memory compacting, it is highly unlikely that it will invalidate pointers. The problem is that there is no 100% precise answer to your question as there isn't a definitive, singular runtime/memory manager on these systems. You can always link a different memory manager, for starters.
Timo Geusch
@HS - just use the normal memory managements that comes with the compiler and you will be fine. Normal C++ rules don't allow pointers to go invalid randomly, so the memory manager won't do anything funny when you aren't looking.
Michael Kohne
@HS: "Is there any chance of Heap compaction because of which an address stored becomes invalidated?". Not for objects allocated through normal C++ means, absolutely not. A stored address will definitely remain valid as long as you don't free the thing it points to. If the pointer is to non-C++ memory, like something on a Java heap, then that's a completely different matter, and perhaps compaction could render the pointer invalid. JNI has rules about what native code can assume. But pointers to allocations made from C++ are reliable.
Steve Jessop
Thanks Adam, Timo, Michael and Steve. It was really good to hear your views.
HS
+1  A: 

I'm unaware of any C++ implementation that will move allocated objects around. I suppose it might be technically permitted by the standard (though I'm not 100% sure about that), but remember that the standard must allow a pointer to be cast to a large enough integral type and back again and still be a valid pointer. So an implementation that could move dynamically allocated objects around would have to be able to deal with the admittedly unlikely series of events where:

  • a pointer is cast to an intptr_t
  • that value is transformed somehow (xor'ed with some value), so the runtime can't detect that it's a pointer to a particular object
  • the object gets moved due to compaction
  • the intptr_t gets transformed back into its original value, and
  • cast back to a pointer to the object type

The implementation would need to ensure that the pointer from that last step points to the moved object's new location.

I suppose using double indirection for pointers might allow an implementation to deal with this, but I'm unaware of any implementation that does anything like this.

Michael Burr
The old Macintosh OS used to have a handle type, which was basically a double indirect pointer. That was an OS feature, not a language feature, however, and it creates all sorts of extra work for the programmer, because you have to remember to lock and unlock handles at appropriate times.
Michael Kohne
"the standard must allow a pointer to be cast to a large enough integral type and back again". If any such type exists. `intptr_t` (a) isn't in C++03, and (b) is optional in C99 anyway. But I agree with you that this is an implausibly long shot, and that any C++ implementation which wants to compact is going to have to do it with an additional indirection somewhere (perhaps in hardware - one object per virtual memory page, anyone?).
Steve Jessop
@Michael Kohne: early versions of windows also had handles to movable memory, but it was also something that a programmer had to manage manually.
Michael Burr
@Steve Jessop: I understand that `intptr_t` isn't necessarily standard, but it's a nice shorthand for 'some int type that's large enough to hold a pointer'.
Michael Burr
Sure, but since we're talking about some very strange implementation anyway, I thought I'd point out there might not be any such integer type. For instance you could have 128-bit pointers, but the largest integer type is 64 bits. Hence the implementation can wriggle out of this particular difficulty. I'm sure there are plenty of other difficulties, though.
Steve Jessop
Thanks Michael Burr, Michael Kohne and Steve. It was really good to hear your views.
HS
+6  A: 

The C++ standard says nothing about a heap, nor about compaction. However, it does require that if you take the address of an object, that address stays the same throughout the object's lifetime.

A C++ implementation could do some kind of heap compaction and move objects around behind the scenes. But then the "addresses" it return to you when you use the address-of operator, are not actually memory addresses but some other kind of mapping.

In other words, yes, it is safe to assume that addresses in C++ stay the same while the object you're taking the address of lives.

What happens behind the scenes is unknown. It is possible that the physical memory addresses change (although common C++ compilers wouldn't do this, it might be relevant for compilers targeting various forms of bytecode, such as Flash), but the addresses that your program sees are going to behave nicely.

jalf
Said very clearly.
Michael Burr
Thanks jalf for the explanation.
HS