Copying data is wasteful, mutating data is dangerous

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" ?

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.

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.

  a.sort()
  b = sorted(a)

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.

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

  low = array1.min()
  high = array1.max()
  array2 = array1 - low
  array2 /= (high - low)
  return array2

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.

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) { ... }
  }

  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)

  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);

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

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:/...

    // 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 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).

btw, I think it's a design flaw in python that `a += b` is not always equivalent to `a = a + b`.

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.

    def normalize(data, inplace=False):
        if not inplace:
            data = data.copy()
        ...

    def normalize(data, out=None):
        if out is None:
            out = data.copy()
        ...

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))

  override def prependedAll[B >: A](prefix: IterableOnce[B]): CC[B] = {
    val b = iterableFactory.newBuilder[B]
    b ++= prefix
    b ++= this
    b.result()
  }

    A = normalized(X*b - M*N*k); //creates a pipeline
    A.calculate(); //calculates all the stages destructively on the new copy

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?

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.

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.

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).

Also it compiles to Python nicely.

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

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.