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.
> 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.
Yes, 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.
public class Node<T>{
Node prev, next;
//stuff comes here
....
}
Then extend and have the overall code that deals with modifying the datastructure, but it's overall ugly. Personally I have written enough datastructures where linking nodes is useful. For example: red/black tree + insert order 'next' makes for a decent implementation of a moving median.
Yet, that's not what almost any developer would do normally.
Perhaps, most of the time I have not created a general use data structure - just highly specialized ones. Extending would allow no references/indirection but it's rather ugly and it has to provide another function to instantiate (I'd consider reflection, i.e. Class.newInstance() not to be a good way to handle the case).
> 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?
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.
> C++ templates cannot be implemented purely by text replacement as most of it is type driven.
The static types (and constant values in some cases) are the context. That's the "context-sensitive" part of "context-sensitive expansion".
> 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).
Yes. That's my point. I was replying to someone saying that they could remove a layer of indirection from a linked list by writing a custom data structure that had the next and previous references, and I was pointing out that they're essentially running C++ template expansion by hand. There's nothing surprising there.
> You would perform manual static context-sensitive text expansion, just like the C++ template expander does.
Sure, if you move all your code into your new language that transpiles to C, but that was my point, the lack of language integration means there's plenty it can't do that C++ templates can do.
An example from [0]:
std::is_same_v<int, std::int64_t>
In C, I don't know that there's any way to determine whether int and int64_t are the same type.
> 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.
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.