Hacker News Reader

Ok, then array-of-structs. Maybe obstacks (region-based allocation). All that stuff that cannot be done in Java, Smalltalk, etc. Does that invalidate the generational hypothesis or not?

> All that stuff that cannot be done in Java

Maybe not on the standard implementation, but just like C and C++, Java also enjoys some extensions.

Packed Objects in IBM J9

http://www.ibm.com/support/knowledgecenter/SSYKE2_8.0.0/com....

ObjectLayout in Azul

http://www.azulsystems.com/content/goto-conference-chicago-2...

And in some standard form in Java 10

http://openjdk.java.net/jeps/169

I guess we'll see when Java gets value types soon, but the Go people can answer that now; only problem is, I'm not sure people build as many and as-data-heavy applications in Go as they do in Java just yet. Also, realtime Java VMs do support arenas (even scoped arenas). So, I don't know the answer, but let's put it this way: I haven't heard anyone saying it isn't true -- and that would be a pretty big thing -- even though there should be enough indicators by now.

C# can do value types and arrays of structs and it has a generational collector, so presumably Microsoft felt that C# fitted the hypothesis.

Go does escape analysis and stack allocation. Presumably this would be pointless if Go allocations rarely died young.

Bear in mind that the hypothesis talks about allocations in general. That means things that get put on the stack count as "dying young".

It's common for Go programs to have millions of stacks. A million simultaneous goroutines in a Go program is pretty common. Not so much for other languages.

Not to mention that in Go you create and destroy stacks much more often (probably orders of magnitude compared to typical Java program).

Go stacks, however, are heap objects... The thing about stack memory is that it's constant size and easy to manage. Go stacks, however, are just heap data structures (I think they used to be linked-list of arrays, and now they're "growable" arrays, like ArrayList, but I'm not sure). It's true that Go uses a different GC algorithm for managing the stacks, but it's still not stack memory. Quasar fibers on the JVM use the same approach. You can have millions of fibers, each with their own stack, but the stack themselves are heap objects.

The fact that stack segments are allocated from the heap, has absolutely no consequence whatsoever. (And in fact, they are allocated from system memory, not from GCd memory.)

That's the main thing of consequence, because those stacks are managed like heap memory. For example, you could implement each and every object as a lightweight thread with a stack -- in fact, that's not too far from how Erlang does it -- but that doesn't change the behavior of that memory. What matters isn't what it's called or what programming abstraction is exposed to the programmer, but how it behaves, which in turn dictates how it's managed. If your program consists of millions of lightweight threads -- as it's done in Erlang, Java with Quasar, or Go -- the algorithms required to manage that "stack" memory are very similar to the algorithms for managing plain heap memory, and not at all like how (heavyweight thread) stacks are managed. So the answer to "how is memory be managed if more things are on stack" is "pretty much the same" if those stacks really behave like heap objects, and are themselves managed as such.

> the algorithms required to manage that "stack" memory are very similar to the algorithms for managing plain heap memory, and not at all like how (heavyweight thread) stacks are managed.

No, this makes no sense. It's managed absolutely identical to how any plain stacks in C are managed. Stacks are created and destroyed when scheduling units (threads or goroutines) are created and destroyed. Whether that memory is allocated by some user level library or the kernel (albeit with POSIX threads, you can, and in fact it's common for thread memory to be allocated by the calling process beforehand) has absolutely no relevance whatsoever. All that matters is that the lifetime of the stack is 1:1 mapped to the lifetime of the schedulable entity.

Of course in Go goroutine stacks are dynamic, which is an optimization that makes Go programs use less memory, but that has no semantic effect.

The thing that makes "plain" stacks easy to manage is that they're of constant size and long lifetime. If the the stack (and its schedulable entity) may be very short lived, and the stack itself may resize, then the stack requires the same (or very similar) dynamic memory management as a heap object. It is the precisely the semantics that make no difference here, but the actual behavior and lifetime of data in memory. It doesn't matter that the lifetime of the memory is that of the thread, if the lifetime of the thread is not at all like that of a heavyweight thread. From the perspective of the programmer it's a stack; from the perspective of the runtime -- it's a heap object (or close enough; there are some assumption you can make -- which Go makes -- that makes managing that memory a little easier, but those assumptions are, as usual, tradeoffs).

"Managing" stacks does not matter here. That's trivial. What matters is the lifetime of the data that lives on the stack. You correctly pointed out that in Java, the data on the stack represents a small percentage of all data, so escape analysis has a limited amount of effect on decreasing memory pressure.

However, in Go, this percentage is much higher because there are orders of magnitude more stacks.

But those stacks aren't stacks from a memory management perspective! They're just heap objects (that happen to be exposed to the user using a stack abstraction): The data in them is heap data, their lifetime is plain heap lifetime, and their memory management (which is what we're talking about and isn't at all trivial) is heap memory management (pretty much). It's just another way of abstracting objects via message passing. You can call your objects "stacks", but they're still the same objects.

Let me take this to the extreme: Imagine a language with no assignable variables at all, but with processes and channels. In that language, you're able to create an arbitrary mutable variable as a process with a channel, that can get `set` or `get` messages. The value of the "variable" is kept in the process's "stack". In fact, this is pretty much how the process calculi work (one of which, CSP, is one of the inspirations behind Go's design). That this is how you choose to design your programming abstractions makes no difference to the runtime implementation. Your stacks would behave just like normal variables behave in languages with different abstractions.

> But those stacks aren't stacks from a memory management perspective!

Yes they are, it doesn't matter who is allocating them, the kernel, or the program itself (which as I mentioned, also happens with POSIX threads).

> The data in them is heap data

No it isn't, not anymore than data in POSIX thread stacks is heap data. You do realise that the memory for POSIX thread stacks also comes from "the heap" (regardless of who is allocating it), and it's not from the process stack segment, right?

> their lifetime is plain heap lifetime

No, their lifetime is the lifetime of the function activation record, just like in C with POSIX threads. The lifetime of some value that lives on the stack is the lifetime of the stack frame, not the lifetime of the stack segment.

> and their memory management (which is what we're talking about and isn't at all trivial) is heap memory management (pretty much).

No, the memory management of values that live on the stack is stack memory management. Values live as long as their stack frame they belong to lives. Stack frame allocation is a pointer decrement, and stack frame deallocation is a stack frame increment (plus some amortised O(1) cost caused by copying stack mechanism).

The lifetime of the stack segments themselves does indeed resemble (or is) heap-based memory allocation, but that is true in C, Java, Go, and any other language, and doesn't matter (or, if you take the position that it matters, it matters the same in all these languages and environments). And allocating stack segments is trivial.

> It's just another way of abstracting objects via message passing.

??? Message passing!? Wat.

Edit:

> Let me take this to the extreme: [...]

If you invent new language implementations and change the normal definition of various concepts, I guess anything can be true in that particular frame of reference...

We keep talking past each other. The objects that are allocated on the stacks are managed like stack objects, but the stacks themselves are heap objects. Storing objects on the stack is, as you say O(1) (or, rather, amortized O(1) for dynamic stacks), but the same is true for using some Stack class in an OO language. It is the stack itself, the container of those objects, that behaves like a plain heap object. This is how pretty much all heap objects behave: they all primitives in fields or arrays, but what the runtime needs to manage is the container. So, yes, you can store the same heap data contained in lightweight thread stacks rather than in objects, but that won't change how that data behaves.

When you create a runtime for lightweight threads (as I have), what matters isn't what the programmer sees but what the runtime sees. POSIX threads and lightweight threads appear the same to the programmer, but behave very differently from the runtime's perspective, and require very different memory management (and very different scheduling) algorithms. What matters to the runtime is: how big each stack is, whether it's constant in size or can grow and shrink, and how often it's allocated and deallocated. It's those parameters that make the difference, not the user abstraction. The point of my example was to clarify that the stack abstraction can be used in different ways. Yes, POSIX thread stacks are also managed in some heap, but their usage parameters make them very different from lightweight thread stacks; the latter behave like a plain object would.

In Erlang, Go and Quasar, the lightweight thread stacks are managed very differently from how the OS manages heavyweight thread stacks, and this is because the two behave very differently despite exposing the same abstraction. You keep repeating that lightweight threads and heavyweight threads are the very same abstraction but what matters is the usage parameters, and that's why their implementation is so different.

BTW, this is true not only for memory management, but for scheduling as well. The scheduling algorithm for heavyweight threads simply does not work well for lightweight threads and vice versa. The reason is that the patterns of blocking and unblocking, and the number of threads -- i.e. the parameters of the behavior -- are radically different, in spite of the abstraction being exactly the same.

I would think the GC's work would correlate more closely to the number of objects than the raw heap size, and presumably most applications that operate on such large data will have relatively few, very large blobs in the heap as opposed to 100s of GBs of <1Kb objects. Am I mistaken?

That very much depends on the application, but for "ordinary" server-side business applications the answer is no, there are a lot of relatively small objects, organized in various data structures: maps (caches, lookups), tree indices (in-memory search), all concurrent.

I work on a JVM app that routinely allocates GBs, and sometimes 10s and occasionally 100s of GBs, of small objects intricately connected. (It's a static analyzer, and the applications it analyzes can get into the MLoCs.) So there's one anecdatum for you.