Non dynalloc framework roots
Hi PyPyr's This is mainly for Carl or Michael as it concerns the framework gc, but I was just interested how easy it would be to track the roots without doing any dynamic memory allocation. I came up with the following code, which I am interested to see how easily it could be translated to llpython or whatever the lowest level is called. If someone can give me some hints, I may even have a go at implementing it myself! Cheers, Ben #include "assert.h" // Code typedef struct _GCFuncNode { int count; void*** pointers; struct _GCFuncNode* prev; } GCFuncNode; GCFuncNode* GC_top_node; void GC_push_func_node(GCFuncNode* node, int count, void*** pointers) { GCFuncNode* old_top; node->count = count; node->pointers = pointers; old_top = GC_top_node; GC_top_node = node; node->prev = old_top; } void GC_pop_func_node(void) { GC_top_node = GC_top_node->prev; } typedef struct _GCRootItr { GCFuncNode* cur_node; int cur_ptr; } GCRootItr; void GC_init_root_itr(GCRootItr* itr) { itr->cur_node = GC_top_node; itr->cur_ptr = 0; } void** GC_itr_cur(GCRootItr* itr) { if(itr->cur_node) { return itr->cur_node->pointers[itr->cur_ptr]; } else { return (void**)0; } } void GC_itr_next(GCRootItr* itr) { assert(itr->cur_ptr < itr->cur_node->count); // Find next non-null pointer while(1) { itr->cur_ptr++; if(itr->cur_ptr == itr->cur_node->count) { itr->cur_node = itr->cur_node->prev; itr->cur_ptr = 0; return; } if(*itr->cur_node->pointers[itr->cur_ptr] != (void*)0) { return; } } } // Example typedef void* PyObjPtr; void example_func_2(PyObjPtr a, PyObjPtr b, int x, int y); void example_func_1(int x, int y) { PyObjPtr a = 0, b = 0, c = 0; // GC code GCFuncNode node; void** GC_local_vars[] = {&a, &b, &c}; GC_push_func_node(&node, sizeof(GC_local_vars)/sizeof(void*), GC_local_vars); // end GC code // Do stuff with a, b, c example_func_2(a, b, 3, y); // GC code GC_pop_func_node(); // end GC code } void example_func_2(PyObjPtr a, PyObjPtr b, int x, int y) { PyObjPtr i = 0, j = 0; // GC code GCFuncNode node; void** GC_local_vars[] = {&i, &j}; GC_push_func_node(&node, sizeof(GC_local_vars)/sizeof(void*), GC_local_vars); // end GC code // GC code GC_pop_func_node(); // end GC code } int main(int argc, char* argv[]) { return 0; }
On Mon, Sep 04, 2006 at 11:59:48AM +0100, Ben.Young@risk.sungard.com wrote:
This is mainly for Carl or Michael as it concerns the framework gc, but I was just interested how easy it would be to track the roots without doing any dynamic memory allocation. I came up with the following code, which I am interested to see how easily it could be translated to llpython or whatever the lowest level is called.
// GC code GCFuncNode node; void** GC_local_vars[] = {&a, &b, &c}; GC_push_func_node(&node, sizeof(GC_local_vars)/sizeof(void*), GC_local_vars); // end GC code
Yes, it makes sense. As usual it's not completely clear if it is better or worse than our current approach. One thing I fear is that taking the address of all the local variables is going to kill all gcc optimizations on them. A more annoying problem is that - anyway - we cannot take addresses of local variables in our flow graphs, so far. There is not even a notion of "all the local variables" of a graph; only of a block. It would require quite some tweaking. If would be nice to try out... An intermediate solution between what you suggest and what we do now would be to still use purely-local variables (i.e. no taking pointers to them) and save them around calls instead of around the whole function, but instead of saving to a global stack, save in a precomputed graph-local Array type with enough items for the maximum number of variables that need to be saved. Then, instead of saving/restoring the roots in the global root stack, they would be saved/restored into the local Array. I guess the node and GC_local_vars could both be packed in a single local var-sized Struct, with a 'prev' pointer, and an Array at the end. In term of flow graphs, to obtain local variables of Struct type, we use a 'stack' flavor of malloc: v = flavored_malloc(S, 'stack') It gives you a pointer to an otherwise-invisible local variable of type S. In other words in the C code it becomes: struct S invisible; struct S* v = &invisible; /* constant pointer used for all accesses */ I'm not sure any more if we support 'stack'-flavored mallocs of var-sized structures and arrays, but that should be easy to fix. The meat of the work is to extend the class FrameworkGCTransformer in pypy.rpython.memory.gctransform. See StacklessFrameworkGCTransformer for an example of providing an alternate StackRootIterator. Its push_root/pop_root static methods should save/restore a local variable into/from some place where the StackRootIterator instance can find them later. (For now, pop_root can be a no-op as long as we can't support moving GCs... but hopefully that is going to change soon, thanks to mwh). A bientot, Armin
Hi Armin, Thanks for the reply! pypy-dev-bounces@codespeak.net wrote on 09/09/2006 10:56:27:
On Mon, Sep 04, 2006 at 11:59:48AM +0100, Ben.Young@risk.sungard.com wrote:
This is mainly for Carl or Michael as it concerns the framework gc, but I was just interested how easy it would be to track the roots without doing any dynamic memory allocation. I came up with the following code, which I am interested to see how easily it could be translated to llpython or
whatever the lowest level is called.
// GC code GCFuncNode node; void** GC_local_vars[] = {&a, &b, &c}; GC_push_func_node(&node, sizeof(GC_local_vars)/sizeof(void*), GC_local_vars); // end GC code
Yes, it makes sense. As usual it's not completely clear if it is better or worse than our current approach. One thing I fear is that taking the address of all the local variables is going to kill all gcc optimizations on them. A more annoying problem is that - anyway - we cannot take addresses of local variables in our flow graphs, so far. There is not even a notion of "all the local variables" of a graph; only of a block. It would require quite some tweaking. If would be nice to try out...
Hmm, I hadn't thought about killing GC optimizations. I guess the only way to find out it do it and see what happens!
An intermediate solution between what you suggest and what we do now would be to still use purely-local variables (i.e. no taking pointers to them) and save them around calls instead of around the whole function, but instead of saving to a global stack, save in a precomputed graph-local Array type with enough items for the maximum number of variables that need to be saved. Then, instead of saving/restoring the roots in the global root stack, they would be saved/restored into the local Array.
I guess the node and GC_local_vars could both be packed in a single local var-sized Struct, with a 'prev' pointer, and an Array at the end. In term of flow graphs, to obtain local variables of Struct type, we use a 'stack' flavor of malloc:
v = flavored_malloc(S, 'stack')
It gives you a pointer to an otherwise-invisible local variable of type S. In other words in the C code it becomes:
struct S invisible; struct S* v = &invisible; /* constant pointer used for all accesses */
I'm not sure any more if we support 'stack'-flavored mallocs of var-sized structures and arrays, but that should be easy to fix.
The meat of the work is to extend the class FrameworkGCTransformer in pypy.rpython.memory.gctransform. See StacklessFrameworkGCTransformer for an example of providing an alternate StackRootIterator. Its push_root/pop_root static methods should save/restore a local variable into/from some place where the StackRootIterator instance can find them later. (For now, pop_root can be a no-op as long as we can't support moving GCs... but hopefully that is going to change soon, thanks to mwh).
I think I understand. If I get some time I'll have a play with some code. I'm currently looking at how annotation works to see how easy it would be to get generator support in rpython aswell. It would allow me to fix all the iter... methods in the multidict code easily. Cheers, Ben
A bientot,
Armin _______________________________________________ pypy-dev@codespeak.net http://codespeak.net/mailman/listinfo/pypy-dev
participants (2)
-
Armin Rigo -
Ben.Young＠risk.sungard.com