How Elixir Manages Memory?

Yes. map gets copied. But its keys and values are not directly encoded in the map, but stored as references. So there are only references copied which point to the same locations as they did in the old map.

The BEAM is very simple in this regard. If you change something, necessary parts will be copied. To make it a bit more efficient, containers store their content as references.

Though not answering your question directly, there can be a lot of insight into how Erlangs and Elixir memory management works when reading the article about OTP 19 new Garbage Collector:

Elixir uses persistent data structures. These data structures are meant to, first and foremost, preserve previous versions of themselves. The nice thing here is that you aren’t taking more traditional data structures and trying to glue persistence on top of them. If lists were build using arrays, or maps built using dictionaries, the cost of modification would be high (O(N) in time and memory).

Lists are built using linked lists and maps, once they grow past a certain point, are HAMTs. Both of these are able to be modified efficiently. Lists are still quite sensitive to the specific operation (a prepend is O(1) while an append is O(n)) though.

To be more specific, imagine a map as a property list (not accurate, but it will make this easy to represent), and let’s start with:

iex(27)> m = [a: 1, b: 2] # %{a: 1, b: 2}
[a: 1, b: 2]

Let’s update :b to be 42:

iex(28)> m = [b: 42]++m # Map.put(m, :b, 42)
[b: 42, a: 1, b: 2]
iex(29)> m[:b]
42

And so forth.

This is not how maps actually work (internally they are an…interesting structure that changes form based on its size) but updating a value does not necessarily get rid of the old one (at least until all references to the old structure are GC’d) but any requests on it only get the new.

Map’s are actually fairly easy to make immutable and efficient (see OCaml’s Map for a spectacular and quite readable implementation (not the ‘best’, but those are significantly more unreadable, kind of like the BEAM’s Map, which is even better but its C source is quite unreadable ^.^)), what is not is an Array, yet the BEAM has those too (implemented entirely in erlang, not C, these are fully and entirely functional):

iex(31)> a = :array.new(30)
{:array, 30, 0, :undefined, 100}

So an array is an opaque record of type :array, I’ve set this one to 30 elements (there is a dynamically sized access type as well), 0 are currently defined, with a ‘space’ of 100 allocated, yet you don’t see the space here at all, it is the :undefined, they all start as :undefined by default (unless you set a default value), however since all the values are the same it just represents that value straight. To see how it stores it internally let’s set a value:

iex(33)> a = :array.set(12, "Hello", a)
{:array, 30, 0, :undefined,
 {10,
  {:undefined, :undefined, "Hello", :undefined, :undefined, :undefined,
   :undefined, :undefined, :undefined, :undefined}, 10, 10, 10, 10, 10, 10, 10,
  10, 10}}

Well this looks interesting. What it is doing is it split the array up into a nested tuples that contains nested tuples (potentially multiple layers deep) with a tuple-size based on a heuristic they calculated long ago (which could be wrong now, but good enough regardless), but you see that the ‘storage’ size of 100 is now the tuple, split in to 10 10’s, the first 10 is just ‘10’ meaning this location represents 10 entries of the default value (of `:undefined), but since we set 12 then the indices of 10-19 have to be a 10-tuple, all of which are the default value except the single place we set.

If you allocate a huge array it will only allocate few tuples, and even if you have every single element set to something unique, like:

iex(36)> a = 0..29 |> Enum.reduce(a, &:array.set(&1, to_string(&1), &2))
{:array, 30, 0, :undefined,
 {{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"},
  {"10", "11", "12", "13", "14", "15", "16", "17", "18", "19"},
  {"20", "21", "22", "23", "24", "25", "26", "27", "28", "29"}, 10, 10, 10, 10,
  10, 10, 10, 10}}

So you see the areas we set them all, nice and easy, updating a value at this size of array (up to size 100) only involves setting 3 tuples, which on the BEAM is FAST rather than needing to copy everything.

And yes, if you make an unsized array the ‘size’ element in the tuple is 0, and if you try to set a value out of range you get an ArgumentError.

It is just changing how you think to optimize the structure for its use-case.

Maps are stored as sorted arrays when they have 32 elements or less. Above that they switch to an HAMT, similar to Clojure, Immutable.js, etc. This article explains nicely why HAMTs can be immutable yet fairly efficient: Immutable.js, persistent data structures and structural sharing.

Hi @hariharasudhan94,

You might want to watch this:

Yes it is a video about Clojure but it answers your question. The video starts at the right time.

Great pretty pictures! Better than my simplified example.