3 ms·
Yes. Pointer chasing datastructures really want to live in a language that has a compacting and relocating garbage collector. If all your objects are doomed t
by eru 5y ago
Yes. Pointer chasing datastructures really want to live in a language that has a compacting and relocating garbage collector.
If all your objects are doomed to die where there were born, you better put them in the right place. (So an array is good for C-like languages.)
- tankenmate 5y agoOr even better yet, use a language with a sensible SSA implementation that can identify local only variables and allocate them on the stack (like golang).
- eru 5y agoThat technique is useful _and_ independent of what I suggested. Ie you can do it whether you have garbage collection or not. Though it's less important on languages with compacting garbage collectors, because there allocation can be just a pointer bump, which is pretty similar to what you do for stack allocation. See also this Scheme implementation which allocates everything on the C stack: > Previous Schemes for implementing full tail-recursion when compiling into C have required some form of "trampoline" to pop the stack. We propose solving the tail-recursion problem in the same manner as Standard ML of New Jersey, by allocating all frames in the (garbage-collected) heap. The Scheme program is translated into continuation-passing style, so the target C functions never return. The C stack pointer then becomes the allocation pointer for a Cheney-style copying garbage collection scheme. Our Scheme can use C function calls, C arguments, C variable-arity functions, and separate compilation without requiring complex block-compilation of entire programs. Introduction IEEE Scheme [IEEE90] requires that all functions be properly tail-recursive, in order that tail-recursive programs not require an unbounded amount of stack space. Several Scheme compilers have targeted the C language [Bartlett89], because C is an efficient systems programming language which is available on nearly ev... http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7143 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7... Do keep in mind that some languages like Scheme (because of call/cc) and Haskell (because of laziness) in general don't have a single stack. See eg https://en.wikipedia.org/wiki/Parent_pointer_tree https://en.wikipedia.org/wiki/Parent_pointer_tree for what Scheme needs to do. Of course, allocation of variables with hierarchically nested lifetimes (ie stack allocation) is still an important and common special case that your compiler/interpreter should probably recognize and handle well. Escape analysis is a well studied field after all. https://en.wikipedia.org/wiki/Escape_analysis https://en.wikipedia.org/wiki/Escape_analysis