Mutations Vector operation optimizations

[Mike Austin]

I've created a few more examples for Kopi, and one is a going to be a simple particle fountain. Every data structure so far in Kopi is immutable, so updating a bunch of positions and velocities is going to create a new vector every frame.

In C++, it would be something as simple as adding a += operator:

positions += velocities

Options. Others?

Just introduce (limited) mutation. Add a set! (index, value) similar to Scheme. That works, but I don't want to get in the habit of using mutation functions. Or maybe only make collections mutable an not variables themselves.

Clojure transients are great for construction and builders, but don't work outside of construction. At least you're not supposed to use them.

Introduce state via co-routines. It is possible to create state by sending messages to co-routines, the same way you can create state in Erlang. But this still doesn't solve mutating a vector.

Variable lifetime / transfer of ownership. If there was no aliasing, there would only be one vector, only shared for reading.

Copy on write for everyone except the "owner". Maybe this is the same as above, meaning data that you store in data structures is not changed from under you. If you ask for it again, it may be different, but it won't change locally.

Look more into Haskell's Data.Vector.Mutable. I'm not exactly sure how these work, but I know they use IO or similar monads to hide some of the mutation.

[Mike Austin]

Oh, Swift uses copy-on-write when there are > 1 owners. This makes sense, so you can mutate all you want if there are no aliases to the array.

“When we mutate x, it first checks whether it is the sole owner of that memory location. If it is, then no need to worry, x can safely be mutated.”

https://betterprogramming.pub/understand-copy-on-write-in-swift-5-52a4716165a3

[Raoul Duke]

blah. i know eg dependent types are bad ux by comparison but ideally i'd not like there to be a chance at runtime of arbitrarily getting screwed on performance. either statically ensure that there's only one owner or else it is going to bite somebody sooner or later. like haskell optimization flags or random one armed bandit luck of the draw with javascript jits. not appealing to me. feels like baaaaad design to me. 

--
You received this message because you are subscribed to the Google Groups "PiLuD" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pilud+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/pilud/11241fb4-aa7c-4b74-b874-65d59373f16en%40googlegroups.com.

[Mike Austin]

I think the door goes both ways. In rust, you must know about lifetimes, moves, borrowing etc. Yes, you will know statically that a value is being copied or not. On the other hand, in Swift it’s more of an optimization. If there are ways of at least verifying at runtime that a value is not copied, I’d be happy. Optimize when you need optimization. I don’t want to deal with value lifetimes explicitly.

[Raoul Duke]

yeah agreed the current ux for lifetimes seems to be more heck than most folks ever want to suffer through including me, unfortunately. 

[David Barbour]

Producing a new vector every frame is not a big deal, especially when every element will usually change. With a suitable API (e.g. zip and map functions) you can keep it down to O(N) per frame. So long as your GC is keeping up, it isn't so different from double-buffered rendering. 

I don't like the idea of introducing mutation semantics just for performance reasons. I'd prefer that in-place update is understood as an optimization of GC, while mutation is related to concurrency semantics. Mutation does not even imply in-place update, e.g. in context of mobile objects or transactional memory.

[Mike Austin]

I agree, introducing mutations just for optimizations is a slippery slope. In-place update if there are no references/aliases seems like a simple solution. I don't have access to the JS GC, but I can implement reference counting on top.

I was also contemplating double-buffering like you mention / GC recycling as a good way to not mutate current values, but also not have to allocate a JS ArrayBuffer every frame. There's a little overhead copying (O(N)) the values but no allocation.

The idea would be that this code could always do in-place update of position:

loop (position, velocity) => {

  loop (position + velocity, velocity)

}

loop (Vector [0, 0], Vector [1, 1])

Thanks for the comments! They are very helpful.

[Raoul Duke]

there's an argument i've read that says pooling in a gc is bad because
the gc still has to trace things to determine liveness all the time,
so keeping the pool around doesn't actually gain - the more things are
connected to roots, the more work the gc has to do following those
parent reference chains? but i guess the flip side is that it avoids
things like having to compact the heap?

[Mike Austin]

Good point. I'm thinking if you only allow a small pool so you can effectively do double/triple buffering, and you are not trying to pool a whole bunch of objects, it would be OK. Also, I wonder if the GC knew about pooling if it could be smarter.

[Mike Austin]

Well, that was easy. if (referenceCount === 1) use += and return this. No more Vector allocations per frame, and no change in syntax (positions + velocities).

Reference counting reminds me of my Objective-C days. I just need to add incrementReferenceCount() to assignment (no aliases), and array and dictionary additions.

[Kyle Hayes]

It depends.

Pooling can be bad with a GC that does compaction.   Those GC types are often coupled with bump pointer allocation which is extremely cheap.   By having a pool, you increase the size of the live set.  Those objects get aged out into older generations over time so the cost is not as much of an issue, but you are kind of working against the GC at that point.

With a bump pointer allocator, allocation is so cheap that the overhead of putting something back into the pool may well exceed the cost of allocating a new object.  But if you have expensive initialization or some underlying resource that is costly (i.e. open file descriptors or sockets or a thread or...), then removing the cost of the initialization might be the big win.

If you are using a costly GC or one that does not have cheap allocation then the equation may swing back over to the other side.

YMMV.  

--
You received this message because you are subscribed to the Google Groups "PiLuD" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pilud+un...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/pilud/CAJ7XQb6BHkPjXPXS5xqtZeo3scSOutQRHMJd8ijZMbMFh2ZtRg%40mail.gmail.com.