4 ms·
This writeup is a bit unclear. It actually mentions two problems. The first is functions out-living stack-allocated arguments... this isn't a GC issue but a c
by KMag 6y ago
This writeup is a bit unclear. It actually mentions two problems. The first is functions out-living stack-allocated arguments... this isn't a GC issue but a compiler issue that could be solved by escape analysis (or more powerful variants, like Rust's lifetime analysis). I guess that maybe they're implicitly talking about using a spaghetti stack instead of doing escape/lifetime analysis, and then needing the GC for the stack frame to support interior references. In any case, as they state the first problem, it's a compiler problem, not a GC problem. As they state in the article, inheritance doesn't solve this, and Simula just forbids by-name/by-reference arguments that are allocated in the caller's call frame.
The second problem they describe is linked lists. A Java-like linked list means an extra level of indirection, where the list element holds a reference to the held object. For both performance and space reasons, they wanted to remove that layer of indirection. That meant either having their garbage collector support interior references (references to any field inside the object) or else making a reference to a linked list element be the same as a reference to the held object. They chose the second option, by way of making the element and the held object one and the same, using inheritance. A Simula linked list has as much indirection as a C++ std::list<T>, one fewer indirection than a java LinkedList<T>.
They mention reference counting, but a mark-and-sweep, copying, or tricolor tracing collector would still have this same issue if it didn't support interior references. As sophisticated as Oracle's latest JVM is, I don't believe any of its several garbage collectors support interior references. Physically in the JVM's memory, LinkedList<T> really has an extra layer of indirection as compared to C++'s std::list<T>, and the JVM uses escape/lifetime analysis in order to stack-allocate some objects that would otherwise need to be heap-allocated.
- xxs 6y ago> A Java-like linked list means an extra level of indirection I guess you mean java.util.LinkedList that has virtually no use case that's not outperformed (both space and time) by another datastructure. Writing your own linked list with prev(+next) pointers ain't hard by it's nothing like C++ templates. The removal of layer of indirection does work in Java [pretty well] as well - like extending AtomicReference (or AtomicInteger), if you need a CAS and some other data, of course it comes with false sharing.
- KMag 6y agoYes, I mean java.util.LinkedList. Obviously, one can do manual writing of Java (or even use m4 macros or hijack the C preprocessor... the preprocessor doesn't know anything about C beyond tokenization) for anything C++ templates can do. It's just tedious and potentially error-prone. Here's hoping Java eventually gets reified generics.
- MaxBarraclough 6y ago> can do manual writing of Java (or even use m4 macros or hijack the C preprocessor... the preprocessor doesn't know anything about C beyond tokenization) for anything C++ templates can do Sounds broadly true, but I'm not sure it's precisely right. How could std::is_same be implemented?
- KMag 6y ago> How could std::is_same be implemented? You would perform manual static context-sensitive text expansion, just like the C++ template expander does. In this case, you end up just manually expanding it all the way out to a true or false by hand. I'm just saying that the C++ template expander only performs static context-sensitive text replacements, ending in valid template-free C++ code. The template engine doesn't introduce any magic that can't be done more tediously in template-free C++ by hand, so you can do the same tricks in Java by hand. Now, Java doesn't have non-primitive value types, so you'd have to manually flatten some classes in order to get the same layout without the class boundary forcing an indirection. Java also doesn't allow interior references while C++ absolutely does, but that's outside the C++ template expander / template sub-language.
- gpderetta 6y agoC++ templates cannot be implemented purely by text replacement as most of it is type driven. It is true that you can do anything that templates do by hand, but that's true for any language construct (at the limit you could write asm).
- ilammy 6y ago> a compiler issue that could be solved by escape analysis It could be solved today, not in the sixties when Simula has been designed. It's fascinating how much scientific progress we're taking for granted, assuming that is has been that way forever. > A Simula linked list has as much indirection as a C++ std::list<T> Barring the same comment on the progress in generic types, intrusive lists are on a bit different scale. The difference between a T which can be a part of intrusive list and List<T> is in how T gets into a list. For intrusive list the links are already in your T. If you have an element and want to add it to the list then it's a bunch of pointer assignments. For non-intrusive list you have to allocate a new list node, and maybe even move your element there.