← Back to All Posts

Elixir Bitstring Tutorial: Saving Memory on Blork's Spaceship

June 29, 2024
tutorial
beginner

In this step-by-step Elixir tutorial, we’ll explore bitstrings - a fundamental data type in Elixir. We’ll learn how to use bitstrings to work with binary data effectively and leverage them to save memory by encoding commands into compact bitstrings. Our mission? To help Blork, an alien spaceship captain, optimize his ship’s command system!

The Problem: Blork’s Memory Crunch 🛸

Blork, our alien friend, is facing a critical issue on his spaceship. The onboard computer is running out of memory due to the inefficient storage of command sequences. Blork frequently uses these commands:

• Fly to base: FB
• Fly to Earth: FE
• Hover: H
• Tractor beam on: T
• Tractor beam off: O

Currently, each command is stored as a string, using 1 byte per character. For example, the sequence “FEHTOFB” uses 7 bytes of precious spaceship memory. Blork needs our help to optimize this system using Elixir and bitstrings!

Our Solution: Bitstring Encoding 💾

We’ll use Elixir’s bitstrings to encode these commands more efficiently. By representing each command with just 4 bits instead of 8 or 16 bits, we can nearly halve the memory usage! Let’s get started with the basics of bitstrings, then we’ll build a command encoder for Blork’s spaceship.

Step 1: Understanding Bitstrings 🧩

Bitstrings are a fundamental data type in Elixir, allowing us to work with binary data efficiently. They are denoted with double chevrons (<< >>) and represent a contiguous sequence of bits in memory.

Defining a Bitstring

In the IEx shell, we can define bitstrings like this:

iex> << 0b110 :: 3 >>
<<6::size(3)>>

This creates a bitstring with the value 110 using 3 bits.

Binary Values

Binary values are represented with a 0b prefix followed by the binary digits. Here’s how binary numbers work:

• First bit: 1
• Second bit: 2
• Third bit: 4
• Fourth bit: 8
• ...and so on

For example, the binary value 110 represents the decimal number 6 (4 + 2).

Bitstring Comparisons

We can compare bitstrings for equality:

iex> << 0b110 :: 3 >> == << 6 :: size(3) >>
true

Both bitstrings represent the decimal number 6 using 3 bits.

Step 2: Combining Bitstrings 🔗

Let’s combine bitstrings to create more complex binary values:

iex> first = << 0b110 :: 3 >>
<<6::size(3)>>
iex> second = << 0b010 :: 3 >>
<<2::size(3)>>
iex> << first :: bitstring, second :: bitstring >>
<<50::size(6)>>

The result <<50::size(6)>> represents the binary value 110010, which is 50 in decimal (32 + 16 + 2).

Step 3: Extracting Information from Bitstrings 🕵️‍♂️

We can use pattern matching to extract information from bitstrings:

iex> << "hello, ", name :: binary >> = "hello, Blork"
"hello, Blork"
iex> name
"Blork"

For more complex pattern matching:

iex> << data_size :: 40, count :: size(data_size) >> = << 8 :: 40, 3 :: 8 >>
<<0, 0, 0, 0, 8, 3>>
iex> data_size
8
iex> count
3

Step 4: Creating the Command Encoder Module 🔒

Let’s create a module in our IDE to encode commands into bitstrings. We’ll build this file step by step, explaining each function as we go. Create a new file named command_encoder.ex and add the following content:

defmodule CommandEncoder do
  # We'll add our functions here
end

Now, let’s add and explain each function:

1. Encoding Individual Instructions

Add this function to your module:

def encode_instruction(code_point) do
  case code_point do
    ?H -> 0b0000  # Hover
    ?F -> 0b0001  # Fly
    ?B -> 0b0010  # Base
    ?E -> 0b0100  # Earth
    ?T -> 0b1000  # Tractor beam on
    ?O -> 0b0011  # Off (Tractor beam)
  end
end

This function takes a single character (as its code point) and returns a 4-bit binary representation. Each command is mapped to a unique 4-bit value, allowing us to compress the information.

2. Encoding Multiple Commands

Next, add this function to encode a sequence of commands:

def encode_commands(commands) do
  Enum.reduce(commands, <<>>, fn command, acc ->
    << acc :: bitstring, encode_instruction(command) :: 4 >>
  end)
end

This function takes a string of commands and uses Enum.reduce/3 to build a bitstring. It encodes each command using encode_instruction/1 and concatenates the results into a single bitstring.

3. Decoding Individual Instructions

Now, let’s add a function to decode a single instruction:

def decode_instruction(bitstring) do
  case bitstring do
    0b0000 -> ?H
    0b0001 -> ?F
    0b0010 -> ?B
    0b0100 -> ?E
    0b1000 -> ?T
    0b0011 -> ?O
  end
end

This function is the inverse of encode_instruction/1. It takes a 4-bit value and returns the corresponding character code point.

Step 4: Creating the Command Encoder Module 🔒

Now that we understand bitstrings, let’s create a module to encode Blork’s spaceship commands. We’ll build this file step by step, explaining each function as we go. Create a new file named command_encoder.ex in your IDE and add the following content:

defmodule CommandEncoder do
  # We'll add our functions here
end

1. Encoding Individual Instructions

Add this function to your module:

def encode_instruction(code_point) do
  case code_point do
    ?H -> 0b0000  # Hover
    ?F -> 0b0001  # Fly (used for both "Fly to base" and "Fly to Earth")
    ?B -> 0b0010  # Base (used with "F" for "Fly to base")
    ?E -> 0b0100  # Earth (used with "F" for "Fly to Earth")
    ?T -> 0b1000  # Tractor beam on
    ?O -> 0b0011  # Off (Tractor beam off)
  end
end

This function takes a single character from Blork’s command set and returns a 4-bit binary representation. By using only 4 bits per command instead of 8 bits (1 byte) per character, we’re already saving 50% of the memory for single-character commands!

Step 5: Using the Command Encoder

Now that we have our CommandEncoder module complete, let’s use it in the IEx shell to encode one of Blork’s command sequences:

iex> c("command_encoder.ex")
[CommandEncoder]
iex> encoded = CommandEncoder.encode_commands("FEHTOFB")
<<65, 35::size(4)>>
iex> CommandEncoder.decode_commands(encoded)
'FEHTOFB'

Let’s break down what’s happening:

1. We compile the `command_encoder.ex` file.
2. We encode the command sequence "FEHTOFB" (Fly to Earth, Hover, Tractor beam on, Tractor beam off, Fly to Base) into a bitstring.
3. We decode the bitstring back into the original command sequence.

This encoding reduces the memory usage from 7 bytes (one for each character) to just 3.5 bytes (28 bits total). That’s a 50% reduction in memory usage for Blork’s spaceship computer!

Memory Savings Breakdown

Let’s look at how much memory we’re saving for Blork:

• Original encoding: 7 bytes (56 bits)
  • F (8 bits) + E (8 bits) + H (8 bits) + T (8 bits) + O (8 bits) + F (8 bits) + B (8 bits)
	
• New encoding: 3.5 bytes (28 bits)
  • 0001 (F) + 0100 (E) + 0000 (H) + 1000 (T) + 0011 (O) + 0001 (F) + 0010 (B)

By using our bitstring encoding, Blork can store twice as many commands in the same amount of memory!

Step 6: Writing Tests

Create a new file command_encoder_test.exs in your IDE:

ExUnit.start()

defmodule CommandEncoderTest do
  use ExUnit.Case
  import CommandEncoder

  test "encode and decode commands" do
    commands = "FEHTOFB"
    encoded = encode_commands(commands)
    assert decode_commands(encoded) == String.to_charlist(commands)
  end

  test "encode instruction" do
    assert encode_instruction(?H) == 0b0000
    assert encode_instruction(?F) == 0b0001
    assert encode_instruction(?B) == 0b0010
    assert encode_instruction(?E) == 0b0100
    assert encode_instruction(?T) == 0b1000
    assert encode_instruction(?O) == 0b0011
  end
end

Run the tests in your terminal:

$ elixir command_encoder_test.exs

Blork’s Optimized Spaceship 🚀

With this optimization, Blork will be thrilled to have almost half of his spaceship’s command memory freed up. This efficient encoding ensures better performance and resource utilization, allowing Blork to store longer command sequences and potentially add more complex commands in the future!

Conclusion

In this tutorial, we’ve learned how to work with bitstrings in Elixir and created a module to encode and decode commands efficiently. We’ve helped Blork, our alien friend, optimize his spaceship’s command system by compressing command sequences and saving valuable memory.

Key takeaways from this tutorial:

1. Understanding bitstrings and their representation in Elixir
2. Creating efficient encodings for specific use cases
3. Implementing encoding and decoding functions
4. Testing our code to ensure reliability
5. Applying our knowledge to solve real-world problems (even if they're on alien spaceships!)

Remember, you can find the complete solution on GitHub and join our Discord server for further discussion and support.

Happy coding, and may your programs be as memory-efficient as Blork’s new command system!