Hacker News Reader

Comment by TheFuntastic | Hacker News Reader

As a game developer working in managed languages (aka Unity/C#) this problem is one of my biggest headaches. I was hoping the article would provide divine insight, unfortunately the recommend solution doesn't really solve the problem (as I see it).

Whilst 2n array alloc is better than 3n, both are creating short lived memory objects. Do that in a hot code path and suddenly you've got tremendous garbage pressure your garbage collector is going to choke on.

One can optimise this by calculating results into a cached array, but that creates opportunities for bugs (results of previous caches persisting). I would dearly love to see a solution that allows me to code in a functional style without sacrificing performance.

View on HN

Arena style allocation helps. You still get the allocations, but GC is cheap. IMO both Java and the CLR are in desperate need of multiple heaps with separate GCs to solve these problems. One big heap simply doesn't scale well. Erlang is the only example I know of that does this right. I know that the golang GC is low-latency, but I'm not familiar with if it can sustain high allocation rates.

Nope.

Golang still uses one global heap; it just allows for stack based allocation in situations it can do it (avoiding putting stuff on the global heap), so copies _can_ be cheap re: GC.

The CLR also allows stack allocation, and many of the newer .NET Core libraries have been built with a focus on eliminating unnecessary allocations.

Some of the biggest of .NET Core's advances in stack allocation (and resulting performance boosts) likely won't make it into Unity until around the release of .NET 5, though. It should be interesting to see how Unity adapts when the tools show up.

Ponylang does as well. I always wonder about why we can't have multiple heaps. The primary argument against GCs is the stop the world pause. Unrelated high throughput code can interfere with latency critical code and therefore you have to write the whole program as if it were latency critical.

>results of previous caches persisting

You clear the buffer or capture it inside an optional type. When you're done with the buffer you can reset it to the default state to be used again.

Most of the issues are logical bugs though, not flaws with the pattern. You just need to reason about the computation that you're doing to preallocate exactly how much data you need outside your hot loops.

You can read some audio source code if you want, this is an extremely common pattern. Preallocate for your computation up front by exactly how much you need (and often with cache-friendly data structures) and don't get crafty reusing buffers where you don't need to.

Are you familiar with data-oriented design? The game-developer equivalent of the array-processing scientific programmers do.

I suspect if you look at how they do things you'd find some domain-specific design patterns.

https://en.wikipedia.org/wiki/Data-oriented_design

Is there any further reading on this in the scientific programming space?

https://en.wikipedia.org/wiki/Array_programming might be starting point.

On certain use cases, you can use a pool of objects, creating long lived objects drawn and return to a pool, reusing the memory efficiently with minimal overhead. Of course, you need to be able to size such a pool to begin with.

Disclaimer : I have no experience with game development whatsoever !

The only language I know that solved this is Rust. The borrow checker assures that you don't give away a mutable reference to your array and then use it somewhere else.

E.g. you have a function that mutates and one that doesn't, you can't accidentally use the mutated array since the borrow checker won't allow you to use it afterwards.

But if you still want to use the mutated version you have to explicitly return the mutable reference to the caller, making it immediately obvious what you're dealing with.

Lua coder here, I'm also used to the problem of constructing GCed objects in hot loops. In my experience, many problems have solutions that are really hard to generalize.

In the example of the blog post, you can reduce the resulting data to the following: - The original array (already exists) - The minimum (Integer, not GCed)¹ - The maximum (Integer, not GCed)¹ - A normalize(int, int, int):int function (can be re-used)²

None of the above give the GC any additional work, but passing them around is way more annoying than just making a normalized copy of the array; and abstraction into a class that encapsulates all of them would mean you have at least one GCed object again, which you don't want.

¹ I don't know how exactly this works in C#, but in Lua integer values aren't garbage-collected, as copying them around directly is no more expensive than copying a reference, and they're immutable anyway. I assume it's the same or at least very similar in C#.

² Instinctively, I want to turn this into a closure that just takes one value and closes the min and max values, but that'd be another GCed object, which we don't want in hot loops.

Imo you have to allocate something else if you are going with an immutable paradigm. You can do clever sharing of data structures, but ultimately if you're modifying the whole thing, you're modifying the whole thing and sharing can only go so far. It seems like further advances in this space either require giving the compiler a better understanding of what is "actually" shared and in what way (i.e. Rust and knowing when mutations are externally visible), or making copying cheaper.

Mutability is always (at least as current computer architectures are concerned) going to be faster in a general sense.

> It seems like further advances in this space either require giving the compiler a better understanding of what is "actually" shared

In the context of arrays, it helps when programmers use higher-order combinators/functions, e.g. maps.

There is a mutable way to do a map, and an immutable way, and which should be used in the compiled program depends on analysis of where the variable is used.

You may be interested in the `im` crate for Rust, which implements efficient copy-on-write structural sharing, falling back to in-place mutation when there are no other outstanding references.

https://docs.rs/im/14.1.0/im/

> both are creating short lived memory objects

Might also cause some other weird side effects. Some older versions of C# (or more specifically the .net CLR) had some issues with the heap space for large objects when it got used by external code. I believe the reason was that data allocated by external libraries had to be placed sequencially on the heap due to some marshalling constraints (or maybe the LOH always allocates sequentially?). After a while the heap got fragmented and you could get into a situation where all memory checks told you that you can still allocate another large chunk but the subsequent allocation crashed in a not so graceful manner since the memory wasn't available in sequence.

Took quite a time to even understand what was happening. I didn't really follow up to how the CLR-developers solved this issue. This was ages ago and has now been fixed. Certainly an interesting problem.

C# has this awesome using statement so you can at least indirectly influence when garbage collection occurs and ensures objects are as short lived as possible.

I don't think there is a golden way to Rome. Personally I think keeping the life-time of any object as short as possible is still the way to go and it helped with our problem. The GC of C# is aggressive towards young object that it assumes to be short lived. But I would never recommend to write code with the GC in mind until it starts to be an issue. Which might be right at the start for game developing, but otherwise I don't really care too muchabout keeping temporary copies.

`using` is for resource management scopes (disposal), not garbage collection.

Some disposal actions will dereference objects (this.thing = null) and thus add garbage and therefore garbage pressure for a GC run to clean up, so it is an indirect influence, but it is very indirect, and not what `using` and `IDisposable` are meant to do.

You shouldn't rely on `using` for GC management, and making things that don't manage resources (such as file handles, sockets, etc) `IDisposable` isn't a good way to ensure they are short-lived (and doesn't add any additional signal to the GC that the objects are short-lived; some `IDisposable` objects are incredibly long-lived).

Better tips to managing short-lived objects are to keep them as small as possible, avoid unnecessary references to/from other objects, avoid accidental captures into lambda closures, and consider if stack allocation makes sense for your scenario.

> I would dearly love to see a solution that allows me to code in a functional style without sacrificing performance.

Uniqueness types would make mutation easier to track: you'd still need to write an imperative style, but less to worry about.

I think the "functional-style" stuff in this area uses compilers (i.e. accelerate or futhark) that can analyze whether copying is necessary because the programmer uses various high-level functional combinators. I think J does something like this as well (?)

If you have precise reference counts (which is often achievable in array languages because they don't have cycles), then you can dynamically do efficient in-place updates if the array you are updating has a count of 1.

Uniqueness types are only necessary if you want to make the in-place update a static guarantee (which can be crucial if the code is going to run in an environment where allocation is not possible).

Linear typing is obviously ideal, but you can also version expensive to clone objects, and use a struct to reference them with a pointer and version number.

That way if you mess up your algorithm and attempt to access the old version of an object from a stale reference, you at least get an exception.

If you use a struct it makes the pointers fat but there's no allocation.

If you need the highest performance, you're probably always going to be stuck with some ugliness.

If the code is isolated to some specific logical module, like the game AI, you can bury it in a private helper method that at least hides the details from callers.

Just use a bool parameter `inplace` (or a reference `out`), defaulting to false, but passing it as true for the "hot path" code that needs in-place modification. You get performance, non-duplicated code, and an API style that datascience and ML people are already used too from Numpy, Pandas etc.

If you need to send a temporary array through a number of operations (normalise, then vusalise, in this case), you could also set up the stream of operations and send the elements of the array through it one at a time, or in short batches.

Streaming and lazy evaluation is definitely a solution here. But do python libraries support it well?

You can't have true lazy evaluation because you still need the maximum and minimum to normalise them. But that's just two fields that you need only once.

I have no idea whether python or any other language supports this out of the box, but I would expect there are libraries that do this, and if not, it shouldn't be too hard to write this yourself. The main thing is probably that you need to separate the normalisation parameters from the normalisation itself, and after that, you can simply do something like (in javascript):

  array.forEach(e => visualise(normalise(e, min, max)));

Of course visualisation is probably going to involve a new datastructure that's going to hold this data in some way, so there's still going to be another copy of that array living somewhere. That's unavoidable.

Do game devs write custom allocators ?

Almost always (for big budget ones).

The simplest allocation/deallocation pattern is to delete everything after the unit of work [0] has finished. The downside is that the "unit of work" has to be defined by your program.

[0] HTTP requests, video frames, etc

If you can't find a good implementation for an interface perhaps the problem is the interface. Inline the function, refactor, then express the result via re-usable components. Ultimately it is a problem of code re-use vs performance. If you want divine insight it is probably to use lazy evaluation, so for the example in the article express normalize as a generator.

Reply on news.ycombinator.com