TIL: How Elixir Handles Tuple Size
December 2nd, 2022
Recently I was digging around the topic of tail-call optimization. Somewhere along the way, as these things go, I followed a link to the elixir-lang docs on Lists or Tuples? There's nothing terribly exciting about this section but one quick aside did catch my attention:
When counting the elements in a data structure, Elixir also abides by a simple rule: the function is named size if the operation is in constant time (i.e. the value is pre-calculated) or length if the operation is linear (i.e. calculating the length gets slower as the input grows). As a mnemonic, both "length" and "linear" start with "l".
I immediately thought that was a pretty cool convention. A function
like tuple_size/1 can instantly be understood to be an
O(1) operation. Alternatively, length/1 is an O(n)
operation and thus indicates it will scale with the size of the input.
More than this, I then began to wonder how the tuple stores that
information, as to be O(1) it must be precomputed and preserved
somewhere. And now you can probably appreciate the rabbit warren I
needed to explore.
I quickly turned to check the functions documentation of IO and Kernel but couldn't quite find what I was looking for. I thought perhaps there was some utility function to closely inspect a variable. Perhaps there is, I just haven't found it yet! What I found instead, after going further down the rabbit warren, was a fantastic breakdown of data representation within Erlang.
There is lots of depth in that link, so I won't repeat it all
here. That said, from what I can gather, a tuple consists of a
pointer referencing a header which is a data descriptor. This header
is then followed by the data represented in the tuple. And the answer
to my original question is in this header. The header stores the
length of the data represented by the tuple. So, for example, a tuple
such as {:a, :b, :c} has a length of 3 which is stored
in the header. And this value stored in the header is what's read by
the tuple_size/1 function.
Now, when you use tuple_size/1 you not only know that
it's a constant operation, but you know why it's a constant
operation. That's pretty cool.