Elixir Destructuring

Break it all apart

Welcome to the fourth installment of our work with Strings. As usual here's a reminder of the original problem we were trying to solve:

take_prefix.("Mr. John", "Mr. ")
# returns 'John'

We want to be able to chop off some prefix and return the suffix of a string.

So far we've come up with three implementations, each one improving upon each other. Our initial implementation:

# slow bc of multiple String.lengths
take_prefix = fn full, prefix ->
  base = String.length(prefix)
  String.slice(full, base, String.length(full) - base)
end

IO.puts take_prefix.("Mr. John", "Mr. ")

The second implementation used ranges:

# replace one of our slow length call with a range
take_prefix = fn full, prefix ->
  base = String.length(prefix)
  String.slice(full, base..-1)
end

IO.puts take_prefix.("Mr. John", "Mr. ")

The third implementation used binary functions due to their constant speed regardless of the size of the given string.

take_prefix = fn full, prefix ->
  base = byte_size(prefix)
  binary_part(full, base, byte_size(full) - base)
end

IO.puts take_prefix.("Mr. John", "Mr. ")

The final improvement is really more aesthetics. We can make this solution a bit more functional and feel more Elixir-y by using a concept known as destructuring.

Destructuring is a way of taking a complicated data structure and breaking it apart into simplier components. Quick example:

[a, b, c] = [1, 2, 3]
# a now has the value 1
# b now has the value 2
# c now has the value 3

In this example, we took the array holding three numbers and broke it apart into it's separate elements. This is destructuring in a nutshell. Taking something and breaking it apart.

Here's another example using tuples (a data structure holding elements that are contiguous in memory).

{status, status_message} = {:ok, "Success"}

Sometimes our complex object that we want to break apart has information we don't care about. You might think you could do something like this:

# this will not work!
{status, status_message} = {:ok, "Success", "Junk"}
#** (MatchError) no match of right hand side value: {:ok, "Success", "Junk"}

Elixir thinks you messed up, so you have to be very explicit in telling it that you don't care about the last match. You do this by using an underscore.

{status, status_message, _} = {:ok, "Success", "Junk"}

Now this will work. Alright, I think we have all the tools we need to understand the final solution.

take_prefix = fn full, prefix ->
  base = byte_size(prefix)
  # this is the destructuring
  <<_::binary-size(base), rest::binary>> = full
  rest
end

IO.puts take_prefix.("Mr. John", "Mr. ")

Here we are destructuring the full string into two binary components. The << and >> signify that this is a binary data structure, in this case with two elements. The first element will contain a binary string that is the binary size of the prefix and the second element is the rest of the string. Let's get into a bit more detail.

Remember what we saw last week, a String is just a binary string in disguise. So what we are doing here is figuring out the number of bytes used in the prefix (so we know how much to chop off). Then we destructure the full string into two binary parts. The first binary part is the number of bytes that we calculated before (but now represented as the size in binary due to us wanting to destructure this into a binary data structure). And the second part is the actual string that we want to return, represented as a binary data structure. But as we saw last week, a String is just a UTF-8 encoded binary so returning this is just fine.

Destructuring is a powerful technique and is very useful in producing short and concise code. Elixir is not the only language that has this feature. ECMAScript 2016 has it as well.

With that, this concludes our multi-post demonstration on a simple problem I found from the Elixir docs, and how they were able to iterate through a few solutions until the settled on their favorite implementation. I felt like their explanation didn't go into enough detail, which is why we've been looking at each a bit more closely these past few weeks. Hopefully you learned something and had fun while doing it.

Next week, we'll discover and discuss a new topic that I haven't yet decided on yet :)

Getting Faster By Going Deeper

Elixir Code Points

This week is the third installment of our look at Strings. As a quick reminder, we tried to implement a function that chops off a prefix from a string.

take_prefix.("Mr. John", "Mr. ")
# returns 'John'

So far we've come up with two implementations, the second improving on the first. Our initial implementation:

# slow bc of multiple String.lengths
take_prefix = fn full, prefix ->
  base = String.length(prefix)
  String.slice(full, base, String.length(full) - base)
end

IO.puts take_prefix.("Mr. John", "Mr. ")

The second implementation used ranges:

# replace one of our slow length call with a range
take_prefix = fn full, prefix ->
  base = String.length(prefix)
  String.slice(full, base..-1)
end

IO.puts take_prefix.("Mr. John", "Mr. ")

The next improvement is to not even use String functions at all! Wait, what? How can you do that? What would you use??

To answer this, we have to see how Strings are represented. Everything in computers essentially boil down to 0's and 1's; we call these bits. If you put 8 of these together, you get a byte. With 8 bits put together, and each digit representing 2^n, where n is the number of positions from the far right, you can represent 0 to 255. So with 255 numbers, you just represent each letter with a number. For example, we use the number 97 to represent the small letter `a`. Another way to say this is that the small letter `a` has code point 97. This mapping is called the character encoding and Elixir uses UTF-8.

Problem is we have more than 255 characters that we want to represent, like letters with accent marks, or non-latin characters like Chinese. This means we need more numbers, which means we need more bytes. Let's look at an example using iex, the interactive elixir repl.

# `?` shows us the code point
iex> ?a
97

iex> ?ł
322

The small `a` is less than 255, which means we only need one byte to represent it. But the letter `ł` is over 255, and actually will require 2 bytes to represent 322. We can check double check this to see we are right.

iex> byte_size("a") 
1

iex> byte_size("ł") 
2

We can go even further and force Elixir to spit out it's binary representation by using a trick where we concatenate a null byte `<<0>>` to the string.

iex> "a" <> <<0>>
<<97, 0>>

iex> "ł" <> <<0>>
<<197, 130, 0>>

iex> "ał" <> <<0>>
<<97, 197, 130, 0>>

We can see that the small letter `a` only needs one byte to show 97, but `ł` needs more than one byte. So Elixir splits up the 2 bytes into two different and separate bytes and then represents each byte with it's own number. This is why we get 197 and 130 to show the 322 that really is the letter `ł`.

All this that we covered is really just to say that any letter will always be between 1 to 4 COMPLETE bytes. Elixir will never use a fraction of a byte to represent a letter. We can take advantage of this and use Elixir byte functions, which are WAY faster than Elixir String functions.

There is one more caveat, we have to make absolutely sure that whatever byte functions we use, we never chop in between code points. We don't want to chop `ł` into two separate bytes because then it won't be `ł` anymore, you need both bytes to represent this letter. Let's see our new solution:

take_prefix = fn full, prefix ->
  base = byte_size(prefix)
  binary_part(full, base, byte_size(full) - base)
end

IO.puts take_prefix.("Mr. John", "Mr. ")

Instead of `String.length` we used `byte_size`. The `String.length` function as you recall gets more expensive the longer the string is, but the latter `byte_size` always runs in constant time, regardless of the input size. This is great! Similar improvements are also gained by using `binary_part` instead of `String.slice`.

This is a good example of how understanding how something works under the covers allows you to employ some neat tricks. This is a valuable bit of insight that you will see often and should employ yourself. Whenever possible, think about replacing String functions with low level byte functions, you will get nice performance gains.

Next week we will use perform our final enhancement to this solution and wrap up our series on Elixir Strings.

Home Home on the Elixir Range

Elixir Ranges

Last week we were digging around the Elixir docs and had some fun with strings. As a reminder, we tried to implement a function that chops off a prefix from a string. Something like this:

take_prefix.("Mr. John", "Mr. ")
# returns 'John'

We saw our initial implementation:

take_prefix = fn full, prefix ->
  base = String.length(prefix)
  String.slice(full, base, String.length(full) - base)
end

IO.puts take_prefix.("Mr. John", "Mr. ")

But one big problem were the multiple calls to

String.length

which as we saw last week, does a full traversal of the string. As per the Elixir docs, the first improvement they perform is replacing

String.slice(full, base, String.length(full) - base)

with

String.slice(full, base..-1)

Let's look at this a bit. What are those dots in the second argument? This is something called a range. From the docs, a range is:

A range represents a discrete number of values 
where the first and last values are integers.

Ranges can be either increasing (first <= last)
or decreasing (first > last). Ranges are also always inclusive.

Let's take an example to help illustrate this:

range = 1..5

The `range` variable holds 5 numbers (1, 2, 3, 4, 5). That's it! It's just a collection of sequential numbers. Now let's check the docs on the new slice method:

slice(string, range)

#Returns a substring from the offset given by the
#start of the range to the offset given by the end
#of the range

So our call to slice

# As we saw last week, base is 4
# base = String.length(prefix)
String.slice(full, base..-1)

really is:

String.slice("Mr. John", 4..-1)

This function takes the string starting at the 4th letter and goes to the first letter counting backwards.

To say this another way, it's saying to take the string starting from the 4th letter up to and including the last letter.

Again, the advantage of using the range is that we save having to do the `String.length` call in the Slice method that we did last week.

Ranges are fun and come in quite handy. One more quick example with Ranges

println = fn x ->
  IO.puts x
end

Enum.each 1..5, println
Enum.each [1, 2, 3, 4, 5], println

Both of the last two lines will print out the numbers 1 through 5. The first one does so using a range and the second one uses a list of numbers.

That's it this week on the second improvement to our `take_prefix` method. Next week we will look at the next improvement that we can make to this method. As a teaser, it will involve us knowing how strings are represented. Until then!

Elixir Prefix by Suffix

Elixir Strings

I was reading through the Elixir docs and found some interesting code snippets in the `String` section. The example was how we could implement a function that returns the ending of a string.

So in other words, we want a function like this:

take_prefix.("Mr. John", "Mr. ")
# returns 'John'

The docs actually show a few solutions, gradually iterating on each, improving it slowly. I really liked how they did it, but thought that each solution could use a bit more detail.

This post will take the first naive solution and talk about it. This solution is probably the most intuitive, so is a nice way to ease into Elixir strings.

Solution

take_prefix = fn full, prefix ->
  base = String.length(prefix)
  String.slice(full, base, String.length(full) - base)
end

IO.puts take_prefix.("Mr. John", "Mr. ")

Let's jump right in.

First line

take_prefix = fn full, prefix ->

The first line declares the function. We want a function that takes in two parameters, the full/entire string, and the prefix that we want chopped off.

Second line

base = String.length(prefix)

This line figures out how long the prefix string is. There is something to note here, and that this function `String.length` needs to traverse the entire string in order to figure out it's length. The reason for this is that some letters are made up of two characters, but are perceived by humans as one.

One example is this letter:

# é
iex> String.codepoints("é")
["e", "́"]

Two characters used to represent one. So the `String.length` function has no choice but to traverse the entire string to check for weird conditions like this. As a result, as the string gets longer, this function call takes longer to complete as it has more characters to check.

Third line

String.slice(full, base, String.length(full) - base)

The next line is a bit compact, but let's dig in and see if we can't unpack it.

Let's start inside and go out.

String.length(full) - base

We saw the first part before. But now we are taking the length of the full/entire string. And from that we are subtracting out the length of the prefix.

So from our example, the length of our full string is ("Mr. John") is 8, and the length of the prefix ("Mr.  ") is 4. Simple subtraction (8-4) and we have 4.

Our call really then is:

String.slice(full, 4, 4)

Looking up the docs for that:

slice(string, start, len)
Returns a substring starting at the offset start, and of length len

In plain English, this method says, "take the string Mr. John and starting at the 4th element (0 based), give me back a string 4 characters long".

Fourth line

IO.puts take_prefix.("Mr. John", "Mr. ")

And the last line shows the invocation of the method and the write to the console.

Tada. But as you may have noticed, this method is expensive, mainly due to the two length calls we have. And then we have an additional slice call that has to yet again traverse the string in order to give us the substring. For short strings, this solution is no problem. But when you get longer strings, this method will not be so great. There are ways we can improve on this, which we will take a look at next time.

Virtual Method Table

Today I'm going to blog about something called a "virtual method table".  I randomly caught a talk where the speaker was saying that teaching someone to sling code is not sufficient. The student has to also understand the theory and fundamentals behind what they are learning.  A great analogy he used was that a "plumber should know what's going on underneath the sink."  He then randomly threw out some computer science terms and concepts; and let me tell you, it was refreshing.

So often we see those "learn to code" websites where they promise to teach you how to program in XX hours.  Reminds me of a great Abstruse Goose comic:

Love this comic

It's a little dated in that it references the old "Sam's Teach Yourself C++ in 21 Days" book but for those of you who don't remember this series:

Oh the lies

I remember this well because I actually had this book.  And I remember I felt like such a failure when I'd take me multiple hours to get through a single "1 hr" lesson.  Frustrated I remember throwing the book aside.

The book that really taught me how to program was:

A Beast of a Book

I forget exactly which edition, but I won't forget the name of the book.  This particular edition is a whopping 984 pages of text and weighs 3.4 pounds.  It was a beast back then, and it's a beast now.  But it's that large b/c the examples are so thorough and the explainations so in depth (at least my particular version was, I can only assume the core of the book is still the same for the fifth edition).

I really enjoyed this book, which is why I wanted to highlight it today.  Ok enough aside, onto the content.

What is a virtual method table?  For that matter, what is a virtual method?  It's really simple.  A virtual method is just a function that can be overriden by an inheriting class.  Basic rules apply, like you need to have the same signature, but it's not much more complicated conceptually than that.  Virtual methods are a core part of object oriented programming.  They can help allow things like polymorphism to happen, a key of OOP.  (There's more to polymorphism than just this, but that discussion is out of scope right now.)

So how are virtual methods implemented?  That's where we get into virtual method tables.  A typical function is bound at compile time.  In other words, when you compile your language, you compile in the location of where your function will live.  So when your program runs, it's a simple jump instruction to the spot in memory where your function resides.  Your program keeps track of where you came from, so when your function is done, you just hop right back where you came from.

Virtual methods on the other hand cannot compile in the memory location, because, you the programmer, could have created an inherited class that overrides that method.  So the compiler cannot figure out during compile time, which exact implementation to jump to.  As a result, the compiler (or runtime, depending on the language/implementation) will create a bit of indirection, called a 'virtual method table' (one table for each class) that acts as a lookup to the proper implementation that should be invoked.  Each instance of your class will have a pointer to this special virtual method table so that when the virtual method is called, the virtual method table can be checked to see which method implementation we actually want to invoke.  Because we don't know precisely the location until runtime (when we check the table), this is called "late" binding (as opposed to compile time, or "early" binding).

Virtual method tables are awesome because it allows us to be flexible in the behavior of our program.  Nothing in life is free though.  This table takes up memory and because of the added hop to the table, then to the actual method, the performance is also slower than an early bound method.  So in C++, you have to explicitly declare which ones of your methods will be virtual by using the keyword...virtual.  Shocking name, I know.  In Java, every method is virtual by default, unless you declare that method to be final or static.

That is the basic concept.  A relatively simple solution to a simple problem.  You'll often hear these concepts refered to by a bunch of various names, but it all refers to the same thing.  A virtual method table is also called a virtual function table, or a virtual call table, or vtable.  But tomato tomato (works better when you say that part aloud).

Hopefully this teaches you something, or at the very least refreshes your memory on a topic you probably don't have to deal with daily.  Take care and happy holidays :)