30 ms·
Copying data is wasteful, mutating data is dangerous
- TheFuntastic 7y agoAs 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.
- itamarst 7y agoAre 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 https://en.wikipedia.org/wiki/Data-oriented_design
- hderms 7y agoImo 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.
- vmchale 7y ago> 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.
- tene 7y agoYou 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/ https://docs.rs/im/14.1.0/im/
- strictfp 7y agoArena 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.
- lostcolony 7y agoNope. 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.
- jen20 7y agoThe CLR also allows stack allocation, and many of the newer .NET Core libraries have been built with a focus on eliminating unnecessary allocations.
- WorldMaker 7y agoSome 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.
- imtringued 7y agoPonylang 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.
- C4stor 7y agoOn 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 !
- unlinked_dll 7y ago>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.
- vmchale 7y ago> 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 (?)
- Athas 7y agoIf 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).
- agumonkey 7y agoDo game devs write custom allocators ?
- danielscrubs 7y agoAlmost always (for big budget ones).
- imtringued 7y agoThe 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
- twiceaday 7y agoIf 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.
- nitwit005 7y agoIf 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.
- mcv 7y agoIf 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.
- davedx 7y agoStreaming and lazy evaluation is definitely a solution here. But do python libraries support it well?
- mcv 7y agoYou 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.
- reitzensteinm 7y agoLinear 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.
- DarkWiiPlayer 7y agoLua 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.
- nnq 7y agoJust 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.
- carlmr 7y agoThe 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.
- raxxorrax 7y ago> 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.
- WorldMaker 7y ago`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.
- xg15 7y agoThis seems like a problem that would be suited for an optimizing compiler. You could imagine some hypothetical language in which all objects are immutable, as far as the programmer is concerned - however the compiler is allowed to reuse objects behind the scenes if there is provably no way that a side-effect could be introduced. E.g., in such a language, the first variant would be the only legal form to write the normalizing function: low = array1.min() high = array1.max() array2 = array1 - low array3 = array2 / (high - low) return array3 However, this could be safely turned into the following during compilation: low = array1.min() high = array1.max() array2 = array1 - low array2 /= (high - low) return array2 ... because array2 is not visible outside the function and therefore could not cause side-effects.
- deleted 7y ago[deleted]
- oefrha 7y agoAlas, CPython isn’t an optimizing compiler, it faithfully compiles code into bytecode which is then faithfully executed. I don’t know the state of NumPy on PyPy since I don’t use PyPy.
- masklinn 7y agonumba.jit might be able to optimise the extra copies away though, I'm reasonably sure working with numpy arrays is a pretty significant use case.
- ben509 7y agoThere's another project, Pythran, that does that. I'm not sure if it's doing inlining before the laziness analysis, which would be ideal. [1]: https://pythran.readthedocs.io/en/latest/INTERNAL.html#lazyness https://pythran.readthedocs.io/en/latest/INTERNAL.html#lazyn...
- anoncake 7y agoIt does have a peephole optimizer.
- DecoPerson 7y agoI'm not super familiar with interior mutablility, but I don't think this is the same "interior mutablility" as used in Rust. Interior mutablility: A, immutable, points to B. B, immutable, points to C. C, mutable, points to D. D, immutable, points to E. Even though A and B are immutable -- B points to C mutably, so you can modify its contents. Some "interior" part of A (and of B) is mutable. You can't change which C is pointed to by B (because B is immutable, or rather we only have an immutable reference to it), but it's open season on the contents of C. What this article describes: We have 2 operations. We are passed in Array A. We can either: - Apply both operations to A, modifying it even though the "owner" may not want this. - Copy before each operation (or as part of them), which leaves A untouched, but requires triple the memory usage. - Cooy before (or as part of) the first operation only. The second operation can be applied in-place on the copy. This leaves A untouched and only requires double the memory. They're totally different concepts. I don't know what you'd call the second concept -- I think the important part is that A remains untouched, so... "Avoiding side effects while reducing memory usage", or "How to make performant pure functions" ?
- chewbacha 7y ago> B points to C mutably I think you mean that B points to D mutably because C is mutable. The pointing from B to C is locked in place because of the immutability of B. However, C is free to change it's pointers to some other D.
- shpongled 7y agoI think the easier way to think about Rust's interior mutability is via an example: (Cell is a mechanism for interior mutability) struct S { a: Cell<u64> } struct T { b: u64 } To mutate field `b` on `T`, we need a mutable object or reference. However, we can mutate field `a` on `S` via an immutable reference. Typically this is used to encapsulate some kind of interior state that isn't visible outside of the struct's methods, and helps in certain situations where using a mutable reference might cause some hair pulling due to the borrow checker
- edflsafoiewq 7y agoYeah, this is just "don't create large temporaries unnecessarily". I'm not sure it warrants a name.
- nayuki 7y agoHow I would summarize the article is that mutation should be confined to internal objects that have not been published yet or are temporaries that are thrown away. Theoretically, you can make every API mutate data. If the user didn't want to mutate data, they can explicitly make a copy first. Whereas if there only exists an immutable API to return new objects, then it's hard or impossible to get the benefits of mutating in place. As far as I know, only Rust, C++, and C give support at the type-checking level to denote which functions will modify the interior of their arguments. This way, you can distinguish behaviors easily - for example in Rust: impl Vector { // The method reads this current vector and returns a new one. pub fn normalize(&self) -> Vector { ... } // The method reads and modifies this current vector in place. pub fn normalize(&mut self) { ... } } The article gave this subtly flawed example in Python: def normalize_in_place(array: numpy.ndarray): low = array.min() high = array.max() array -= low array /= high - low def visualize(array: numpy.ndarray): normalize_in_place(array) plot_graph(array) data = generate_data() if DEBUG_MODE: visualize(data) do_something(data) In Rust, it would be a type error because visualize() takes a reference but normalize_in_place() takes a mutable reference: fn normalize_in_place(array: &mut numpy::ndarray) { let low = array.min(); let high = array.max(); array -= low; array /= high - low; } fn visualize(array: &numpy::ndarray) { normalize_in_place(array); // ERROR plot_graph(array); } let data: numpy::ndarray = generate_data(); if DEBUG_MODE { visualize(&data); } do_something(&data);
- masklinn 7y ago> As far as I know, only Rust, C++, and C give support at the type-checking level to denote which functions will modify the interior of their arguments. 1. C and C++ allow casting away constness, which may or may not be UB depending how the parameter is defined 2. Swift also provides this ability to an extent: struct parameters have to be flagged `inout` to be mutable I'm sure there are others.
- gdxhyrd 7y agoCasting away constness in C++ is something it is virtually never done, and has to be done very explicitly.
- benibela 7y agoThat is how strings work in Delphi/Pascal. All strings have a reference count. When you change a string, and the ref count is not one, it is copied before the change. If the ref count is one, it is not copied
- wlib 7y agoIsn't this solved perfectly with an affine or linear type-aware optimizing compiler? Where all data is immutable unless the types prove to the compiler that there are no mutation conflicts. I believe Rust implements this and Idris 2 does so as well with quantitative type theory.
- roywiggins 7y agoThis seems more like "defensive copying" than "interior mutability" to me. Ideally you'd have a compiler that could perform optimizing magic to detect when the copy isn't needed, but that's not going to happen in CPython.
- vmchale 7y agoI think Futhark approaches this with uniqueness types. A bit strange (maybe that's just me?) but it works well with arrays. Also it compiles to Python nicely.
- 333c 7y agoWhy does this blog post have a recaptcha? In addition, I just finished reading the Rust book last night, and I don't believe this is what interior mutability is (at least as used in Rust).
- nhumrich 7y agoI see no recaptcha.
- 333c 7y agoHere's a screenshot: https://i.imgur.com/a/84Hb9Jq.png https://i.imgur.com/a/84Hb9Jq.png
- itamarst 7y agoI'm using ConvertKit for newsletter signups, and choices are either: 1. Validate emails with recaptcha (which is why you see that thing in the corner.) 2. no email validation at all, so random people get spammed with confirma-you-want-to-subscribe emails. I am not super-happy with having to make this choice :(
- true_religion 7y agoFor the email box, presumably he doesn’t want bots entering emails.
- zackmorris 7y agoAnother option is for the language's runtime to use copy-on-write (COW): https://en.wikipedia.org/wiki/Copy-on-write https://en.wikipedia.org/wiki/Copy-on-write So basically every buffer can be made immutable and then only copied when written to, using something like refcounts and diff trees to internally track mutations from an immutable parent buffer. Languages like Clojure due this to manage state. I believe the Redux also does this internally, although I've only studied it and haven't had a chance to use it professionally. In practice, this looks like a language where everything is value-based instead of reference-based. So like, in C# where you pass objects by reference, a COW language passes everything by const value. Then an imperative language statically analyzes the code to detect mutation (my own theory is that this can never be accomplished with 100% certainty, at least not with a simple implementation). So basically buffers act like Git instead of byte arrays, creating a new snapshot with every mutation. Or functional languages can disallow mutation altogether, or reduce the code into its most minimal representation and handle mutation at special breaks in execution (like monads). I'm grossly oversimplifying all of this and probably using the wrong terminology, but am more than 50% confident that I can derive what I'm talking about, so will just go with it hah. I think that the complex imperative implementation I'm talking about is probably Rust. The simple functional implementation would look like a pure immutable Lisp running within the Actor model, handling state only through IO, and dropping monads altogether. The catch being that complex functional code might have so many breaks in execution that it would practically be happening on every single line and begin to look like an imperative language with all its flaws. This is the primary reason why I shy away from impure functional languages like Haskell, because I don't think they have solved this core issue of mutation clearly enough (not to mention, I think functional language syntax is generally write-only and not readable by others or yourself in 6 months hahah). As far as I'm concerned, this is still an open problem. In another life, I want to make an imperative language that's primarily immutable, that uses higher order functions (or better yet, statically analyzes code for side effects and converts foreach loops into higher order functions automagically), and transpiles to a purely immutable Lisp. It would be associative array-based and look like Javascript. The idea being that we could write code in the human-readable imperative style and let the computer distill it down to its pure functional equivalent.
- acemarke 7y ago
- perfunctory 7y ago> To reduce memory usage, you can use in-place operations like += btw, I think it's a design flaw in python that `a += b` is not always equivalent to `a = a + b`.
- notduncansmith 7y agoAs someone who has never used Python seriously I have to ask... why not?
- falkaer 7y agoPython defines += as the __iadd__ method which is sometimes mutating, i.e. if the object being assigned to is mutable or not.
- perfunctory 7y agoBecause I once learned that `a += b` is just a shortcut for `a = a + b`, just a syntax sugar. Now I have to constantly remind myself that it's not the case in python. edit: I might have misunderstood your question. If you meant "why it's not equivalent" please see the falkaer's answer.
- im3w1l 7y agoThey aren't equivalent in C++ either.
- perfunctory 7y agoMy C++ is a bit rusty. Does it manifest itself in the standard library as well? The problem with python (in my view) is that this behaviour is implemented in the standard library and therefor propagates to the 3rd-party libraries by convention.
- zabzonk 7y ago> Does it manifest itself in the standard library as well? Yes. For example for std::string `a = a + b;` will (at least notionally) create a temporary string and then use the assignment operator. `a += b;` will not do this.
- capableweb 7y agoSeems like "both libraries make copies of the data, which means you’re using even more RAM." is a assumption (that copy data leads to more RAM usage) and I'm guessing the libraries (haven't used them myself, nor python, so not sure how feasible this is) can be implemented like a persistent data structure (https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure) and therefore get both immutability (which leads to less bugs, no mutability) and not that high RAM usage. Clojure is a famous example of something that implements persistent data structures.
- perfunctory 7y ago> can be implemented like a persistent data structure you don't get much benefit from persistent structures if every element of an array is modified, like in the examples in the post.
- capableweb 7y agoI missed that, sorry. Thanks for clarifying!
- pipeep 7y agoIf the data structure has a reference count of one, you can safely mutate the data structure instead. Many persistent immutable data structure libraries use this as an additional optimization.
- perfunctory 7y ago> But mutation is a cognitive burden: you need to think much harder about what your code is doing. One way to alleviate the problem is to use naming convention. normalize(a) # mutates in place. note: no return value. b = normalized(a) # no mutation. returns a new instance. note the adjective. Python does this in the standard library a.sort() b = sorted(a)
- jszymborski 7y agoin-place operations give me the heebie-jeebies. I think this is something that is a slightly less obvious when dealing with classes. I see stuff like this in academic code all the time: class SomeDataObj: def __init__(self, data): self.data = data def normalize(self): self.data = normalize(self.data) I'd much prefer for there to be variable `self.data_normalized` which is initialized to None or even better a getter `getNormalizedData()` that computes/caches a normalized variable.
- UncleEntity 7y agoThe pythonic way would be to have sort() and sorted() which either sort in place or return a sorted copy. Best of both worlds.
- ajuc 7y agoCommand Query Separation is a very good general idea in programming that should be followed more often. Sadly it went out of fashion in 90s when everybody got hyped about OOP.
- kburman 7y agoI like how ruby way of declaration if a method does mutate object or not but a exclamation mark at end to tell it modifies the object a = a.sort or a.sort!
- jonnycomputer 7y agoI like the idea of adding an exclamation or some other mark to the individual parameters in the method declaration since a method might mutate some but not all parameters.
- DrFell 7y agoI have been mutating data for decades without any unexpected behavior gremlins.
- mrkeen 7y agoI'm surprised no-one has mentioned Haskell's ST library yet. It hits this exact use-case, and comes with some pretty sweet safeguards from the type system. https://wiki.haskell.org/Monad/ST https://wiki.haskell.org/Monad/ST It allows you mutate arrays and other stuff "on the inside" like this article suggests, but it's also able to wrap up the operation so it appears pure from the outside, so the caller doesn't have to guess or rely on naming conventions to figure out the mutability. It's your choice on whether you want to do the copy on the way in ('thawing'), on the way out ('freezing'), or both, by using the 'in-place' variants of thaw and freeze.
- bfield 7y agoSpecifically on the point about Pandas, last time I checked the inplace flag did not save any memory. Under the hood, it creates a temporary copy which is copied back to the original dataframe, and then the temporary gets removed next garbage collection cycle. If that is no longer the case I would love to know about it though!
- lsb 7y agoDoes the Numba JIT do this? This definitely seems like a compiler optimization that I want to mechanically run on my code
- IshKebab 7y agoThis is just a straightforward memory optimisation; nothing to do with interior mutability.
- alexhutcheson 7y agoIn other languages this is less of an issue, because function signatures can include information about whether the argument can be modified or not. For example, in C++: // Definitely doesn't modify 'array', because 'array' is copied. vector<int> Normalize(vector<int> array); // Almost certainly doesn't modify 'array'. vector<int> Normalize(const vector<int>& array); // Probably *does* modify 'array' (otherwise author would have used // const reference instead of pointer.) void Normalize(vector<int>* array); In Python every function uses the 3rd approach, so you have to signal to the user in some other way whether the argument will be modified or not. In Ruby and some other languages the convention is to append "!" to the function name, but in Python most people seem to just mention it in the docstring.
- pansa 7y agoThere is some convention in Python - for example `reverse` and `sort` are mutating, whereas `reversed` and `sorted` are not. However, I don’t know if there is a good reason why the mutating versions are methods and the non-mutating ones are standalone functions.
- ed_balls 7y agoAnother option is to have a data structure that you have frozen and then you unfroze it for the hot path and then freeze it again when you exit it.
- anaphor 7y agoThere are also data structures such as zippers which are immutable but minimize the amount of data you need to copy, at the cost of potentially using more space overall. Zippers are cool because they can be generalized to many different types of data structures as long as they can be expressed as algebraic data types.
- ajuc 7y agoThere's a 3rd option - keeping a modifications' log and applying them all destructively on just 1 temporary copy only when the result is needed. A = normalized(X*b - M*N*k); //creates a pipeline A.calculate(); //calculates all the stages destructively on the new copy
- wbillingsley 7y agoScala's collections API also uses some mutable internal data structures locally (and temporarily) within some functions that present a pure API. List[T] is one of the classic immutable data structures, and a List[T] cannot have its contents modified. But within the prependAll method, it can create a mutable List factory (ListBuffer) to do its work building the new list that it will return. So, if you follow this (contrived) example in your IDE, calling this: val f = List(4, 5, 6).prependedAll[Int](Array(1, 2, 3)) will take you inside StrictOptimizedSeqOps, which does this: override def prependedAll[B >: A](prefix: IterableOnce[B]): CC[B] = { val b = iterableFactory.newBuilder[B] b ++= prefix b ++= this b.result() } The mutable data structure doesn't escape the function, so to the caller it remains referentially transparent.
- pmarreck 7y agoDon’t functional data structures basically “diff” data, which is a reasonable compromise?
- hannofcart 7y agoI think one way numerical computation APIs can offer optimizations of this sort is to expose a chaining API. For eg: chain(my_large_array).op1().op2().op3().result() Using this, the chain() start could copy the input data once, but thereafter do a series of in place mutations in op1, op2 and op3 to improve performance. Do numpy APIs provide such facilities?
- pornel 7y agoRust iterators combine like that if the operations are per-element (iter + map + collect). For optimizing complex access patterns you'd need a language like Halide.
- DarkWiiPlayer 7y agoWhat about lazy evaluation though? That could get the functions 2*A memory down to just A while still keeping the time O(n)¹ Of course, maybe the author just chose to limit this blog post to this one solution, but it wouldn't have hurt to at least mention some further optimizations :) ¹ And some O(1) data like the min and max values of the Array
- blt 7y agoMatlab gives you these semantics by default. IMO, it's a big reason why it has been so successful with non-CS programmers. Mutation is often more intuitive, but as long as you break your code into functions, you automatically limit the scope of mutability bugs that can occur.
- drej 7y agoThe problem and solution are broadly fine, but having done a bit of performance critical work, I usually dislike when a function allocates without a) me asking, b) me having the option to tell it not to. I like passing in pre-allocated containers to house the results of my computation. That way I have not only predictable memory consumption, but I can also avoid costly allocation (and de-allocation) in tight loops. Having worked with Go a bit, there were times when I used this (like passing in byte slices to readers), but oftentimes you couldn't just tell a function not to allocate (which it did for safety), because you and only you knew it'd be safe to modify the structure in place. The bottom line is that people should not be "always copy/always use pure functions" or "always use mutable structures, because performance!!!", but be aware of what the upsides and downsides of each are.
- londons_explore 7y agoCopy on write?
- kstenerud 7y agoThis is why you want a two-tiered API: High level and low level. The high level API chooses a static trade-off in performance, size, etc for the 80% case, and the low level API gives more explicit control over what's going on. In this case, you could create the function normalized() for the 80% case, and normalize_in_place() for users who need to optimize this path (choosing to take on the extra responsibilities that come with it).
- nnq 7y agoBetter pattern is to follow the style of Numpy or Pandas and other libs (that OP also mentioned, but then failed to apply it in his own examples), letting the caller/user of your functions choose, if/when they want better performance, to opt-in for in-place modification, like have either: def normalize(data, inplace=False): if not inplace: data = data.copy() ... or: def normalize(data, out=None): if out is None: out = data.copy() ... Please, do follow this pattern for any libraries you release, having value-semantics-by-default to prevent shooting yourself in the foot + opt-in in-place mutation option for better memory performance is the right thing, and it's quite easy too with Python, Numpy and Pandas!
- ourlordcaffeine 7y agoJulia has this as well, functions with a '!' at the end mutate the data, functions without make a copy. So you have the functions 'filter' and 'filter!', 'sort' and 'sort!' etc.
- itamarst 7y agoEven if your API provides both choices, you can use the pattern described in the article to make the copying variation more memory efficient.
- cultureswitch 7y agoThis is rather dumb. The only reason there is an intermediate array in the original copy-based code is because the normalization is badly written. After you obtain max and min, normalization is a single map() function, not two. As for the overall problem: always choose immutability and then make it faster by first taking advantage of optimization patterns that immutability allows you to use safely. In a case like this, doing the normalization lazily is what springs to mind. If memory allocation and de-allocation is an issue, use more explicit memory management. Though by experience it is rarely the actual problem. There's basically no chance that it is an issue here, Python interpreters aren't stupid enough to give back memory to the OS immediately after a variable falls out of scope.
- markus92 7y agoDo you have any links to some examples or help on how to do this exactly? Reason being that in our group we have a ton of normalization code that looks exactly like the 'bad' example from this post. As we use relatively large datasets (4D MRI images), memory is a bit scarce...
- naveen99 7y agoPytorch has a built in normalize function: https://pytorch.org/docs/master/_modules/torchvision/transforms/functional.html#normalize https://pytorch.org/docs/master/_modules/torchvision/transfo... It just subtracts the mean and divides by standard deviation, both in place.
- jackcviers3 7y agoIf your language allows mutation: 1. Immutable first. 2. Data structures should use partial copying [1]. 3. Data structures should be lazy by default. 4. When you've profiled a bottleneck, and identified memory allocation and copying as the bottleneck culprit, then use a mutable data structure internal to the operation (copy your lazy immutable data structure once into the mutable one, taking only the portion of your lazy structure that you need, operate on the mutable structure in place, then return an immutable, lazy copy of that structure out of your operation. This will isolate the need for mutation reasoning to performance critical parts of your application/library, and let you still reason about the rest of your program with referential integrity, while avoiding performance bottlenecks. Never use a mutable structure in a mutable reference at the same time. You don't need both. 1. https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki-ebook/dp/B00AKE1V04&ved=2ahUKEwjb9YfGk_nmAhXULc0KHYaRAw0QFjAXegQIBBAH&usg=AOvVaw2G1ZviAl6c7fVGecHERvwq https://www.google.com/url?sa=t&source=web&rct=j&url=https:/...
- namelosw 7y agoOr just use an immutable language or library and you'll have the best of both worlds. Unless you're writing an operating system. But the example was given in Python so I guess it's perfectly fine. The idea of immutable data structure is just like strings in Java or other modern languages: it seems like a reference type but works like a value/primitive type. It maintains a constant pool that all "foo"s in the same virtual machine points to the same reference. For immutable data structures, they work in the same way. On top of that, there's more underlying sharing mechanism. For List(1,2,3), it's actually might sharing the same List(1,2) with List(1,2,4) to minimize the waste.