Like the state of a Cowboy Req object and nearly every GenServer.
Changing deeply nested values in tuples is more expensive, I think, than in maps. That’s the only performance benefit maps have over tuples that I know of.
If you only build a tuple once (like it could be done with cowboy req), and then use it just to read values from it, it should be more efficient than a map.
You can benchmark your own use case with benchee both using maps and tuples and see for yourself.
According to José (in 2015 anyway)
defrecord Student, [:first_name, :last_name]
def name(record) do
"#{record.first_name} #{record.last_name}"
end
The function above would also work on any record that contains the fields first_name and last_name. Its implementation relies on the fact we can call a function on a tuple like {Student, “josé”, “valim”}. So when you defined a record, we automatically defined functions for all of its fields. This added runtime behaviour to records but, because this relies on a tuple dispatch, it was actually slower than accessing or matching fields in a map!
This added runtime behaviour to records but, because this relies on a tuple dispatch, it was actually slower than accessing or matching fields in a map!
I don’t think it works like this anymore. You can extract the values you need in a single pattern match.
def name(student(first_name: first_name, last_name: last_name)) do
# ...
end
unless elixir does something funny, it should be the same as
def name({:student, first_name, last_name}) do
# ...
end
This kind of pattern matching (first element is an atom) is somewhat optimized (since records are used quite often in erlang) and, at least in my experience, much faster than pattern matching maps.
That is why we should get different syntax for accesses, like what about using the OCaml’y # as struct access (not literally proposing # as it is a comment, but just as an example of why not use different syntax for different type, or if Elixir was actually typed then you could use the same syntax as there is no ambiguity then). 
OCaml uses M.f to access a module namespace (capitalized initial character like Elixir), and it uses s.f to access a struct (when the left start does not start with a capitalized initial character, also like elixir). It uses a.[0] for array access. It uses o#m for object access. Among a few others. You can easily tell the type of something by the operators used even without typing declarations.
Ah yes, entirely true.
Would be nice. Though I did testing not long ago about iterating over a charlist and over a binary and it was faster for me to :erlang.string_to_binary and operate over the list then it was to iterate over the binary at the time (it was not super-long stuff, like 30 chars or so).
Ah yep, your results is about on par with the differences that I saw too.
Hmm, I wouldn’t think that would be true but would need to benchmark… A record is nothing but a tuple, so a RecordName(blah, blee, blorp) literally is just {RecordName, blah, blee, blorp}, the 4-tuple, and tuple access and matching is FAST, like nothing faster kind of fast. However rebuilding it and updating it I could see as slower than updating maps on larger sized records/tuples (though not smaller).
Not deeply nested, but rather larger tuples in general.
Yep, Tuples are O(1) access, Maps are O(N).
That was purely because Elixir used a really really bad access pattern for Records. If instead it copied the OCaml way (which requires types) or the Haskell way (which, interestingly, does not require types), then it would be perfectly efficient. But putting it as a . access was really really bad and I don’t know why that would have ever been chosen for records, it is just really really bad.
Those would be identical I’d think, that is how erlang compiles it anyway.
Very.
Is there official Elixir documentation that enumerates the time complexity for Elixir’s container types? I was going through the docs for both Record and Map and neither seems to state the time complexity of their various functions.
Also, does function head matching have the same performance? The info on reddit seems to imply that matches are always O(1).
def hello(%{name: name}), do: IO.puts "Hi #{name}"
Is matching and extracting on the :name key here O(1) or O(n)?
Even if you were just matching and not extracting I’d expect things to be the same.
def hello(%{name: "Jim"}), do: IO.puts "Love long and prosper."
If not slightly worse, since I’d expect there’s an additional comparison check.
Maps have actually two representations depending on the size. Small maps (less than 32 keys) are represented as two sorted arrays - one for keys and one for values. Accessing a key in such a map involves a linear search (and a linear search is much faster than a binary search since the size is so small). Depending on how you look at it, you might say that’s O(n) since it depends on the map size, or O(1) since the worst case is O(32), which is O(1) - the big O notation is not very helpful when talking about small data structures, especially with cache locality and branch prediction effects, you can get significantly different results from what you’d expect by a simple complexity analysis.
Large maps are represented as HAMT and the access is O(log n) - the “forking” factor of the maps is 32, so even very big maps are rather shallow and rarely involve more than 3 levels (32k items).
Anyway, maps are superior to me because of one simple thing - I can read them. Records are terrible in that regard - you get a tagged tuple and you have no idea what the fields mean. Debugging with records is a significantly worse experience and takes much longer. I would reach for records in the tightest loops of the program, where I need some “lolspeed”, but for everything else, maps and structs are plenty fast.
Thank you for clarifying Michal - I a s getting a mild heat attack reading that map access was O(N).
Comparing the speed of deeply nested tuples/records and flat maps/structs seems a bit strange. However you look at it with records you access a specific field in the tuple while with maps you have to search for the right field. Check @michalmuskala description of the internals.
Yes, using for records/tuples for small sizes, currently less than 32, is faster than maps but maps are definitely faster for large sizes. It all depends on how big your records/structs are. Maps/structs do use more memory than tuples/records as they include the names of the keys though that definitely does make them more readable at runtime.
I was comparing nested tuples with nested maps.
AFAIK in maps only the path to changed pair needs to be rebuilt, and with tuples all tuples in its path need to be copied.