Fix gc_realloc to expand in place #334
Conversation
iabdalkader
commented
Mar 5, 2014
- Issue gc_realloc returns NULL after a few calls #322
Fix gc_realloc to expand in place
|
Very nice! |
|
thanks :) |
|
I tried your example, before and after fixing n_free and checking for heap end, do you think there's still a bug here ? what am I missing ? |
|
new realloc I changed the while loop to handle the case where the first HEAD block is the last one in the heap. |
|
Ok, it looks better now, and the few tests I've run have all succeeded. Do you want to do a pull request, or I can just commit your code? |
|
what do you think about defragmenting the heap ? It will be slow, but it could be used as a last resort if gc_alloc fails to find memory ? |
|
There is no way to defrag. You don't know for certain if a pointer is really a pointer.... |
|
I see, okay :) |
|
I am admittedly ignorant of the memory layout being used, but wouldn't valid object pointers always be resolvable to an instance? So you have four possibilities (I am making some general assumptions here):
This assumes that object instances include a type pointer. How else will you know what the member vtable looks like otherwise? Lots of assumptions, I know. But I'm not sure where in the codebase I might find the answers to whether those assumptions are valid. I'm just going by what I know from other GC and runtime typing implementations. |
|
All your assumptions are correct. The problem is that something which is not a pointer can still look like a pointer (eg an integer that just happens to have the right value) and then you will modify this integer to point to the relocated heap position. That's bad. |
|
if I understand correctly, the problem is you will need to scan the stack/heap? and relocate pointers at some point ? at least this is how I imagine how it's done, then how do you know the difference between a pointer and an
|
|
But if you are only relocating managed objects, wouldn't integers (if they are typeless) or the internal data fields of integers (if they are first-class object types) naturally be excluded from scanning as a matter of fact? |
|
you can't tell if it's a python object, there's been an issue about this to implement del, if you can tell python objects maybe it could work ? |
|
I see. I wasn't following that conversation on del, but now I understand the issue. The way this was solved in CLR was to cheat in this manner (well not exactly like this, but this is close enough):
This does have a downside of course. Compact arrays become problematic because an array of M elements is no longer sizeof(element)_M in size... it is now (sizeof(element)+sizeof(pointer))_M. You can get around this by making arrays themselves typed (CLR does this with generics) or by not allowing direct pointer arithmetic for array item access (access allowed only by index via accessor). Individual pointer references to objects are fine, because they still point to the start of the object and are not aware of the extra few bytes that precede it. |
|
Also, with that type of approach you can most likely OR the pointer with the signal bit for reference types since you will realistically never define that many types and can ensure that type structures are always found in the first half of allocated memory. |
|
@KeithJRome the approach you describe is good, although it can be optimised to use less RAM. Hopefully the Micro Python GC will have this "tagging" one day, so that objects can have their But it still doesn't solve the issue of garbage compacting, since any integer may look like a pointer and you don't want to rewrite any integers. |
|
To do compacting you probably need to something like the original Macs did They used double pointers. So the user had a pointer to a pointer to the This adds a performance penalty with the benefit of being able to compact You could lock objects and use the direct pointer to get the performance Dave Hylands
|
|
The biggest problem with double-pointers is not performance hit (there's already enough hit if using interpreter), but memory usage - extra pointer for each memory alloc. Intuitively, you need compaction for smaller heaps - they're likely to be more occupied and thus fragmented. But with smaller heaps, you don't have extra memory to spend on indirection pointers! I personally wanted to implemented compacting heap when I hacked on Squirrel, but after I switched to uPy, I just enjoy minimal memory overhead a GC offers. With latest @dpgeorge changes of supporting fully static module definition, uPy on pyboards starts up with less than 1Kb heap usage, woohoo! |