Slides: Stories in Open Source

Yesterday at RUG::B I tried something I’d never done before: a more personal, story driven talk. And in order to adequately illustrate it and how different Open Source feel to me I also opted paint some very special drawings.

Open Source is something I’ve been doing for longer than people pay me to do programming. I’m immensely passionate about it and it felt like it was some kind of blind spot that I never gave a talk about it so far.

If you know of a conference this talk would be a good fit for, please let me know.

Anyhow, here are the slides to enjoy: Speaker Deck, SlideShare or PDF

Abstract

What’s it like to work on Open Source projects? They’re all the same aren’t they? No, they’re not – the longer I worked on Open Source the more I realize how different the experience is for each one of them. Walk with me through some stories that happened to me in Open Source and let’s see what we can take away.

Slides: Elixir & Phoenix – Fast, Concurrent and Explicit (Øredev)

I had the great pleasure to finally speak at Øredev! I wanted to speak there for so long, not only because it’s a great conference but also because it’s in the city of Malmö. A city that I quite like and a city I’m happy to have friends in 🙂

Anyhow, all went well although I’d have loved to spread the word more.

And yes, at its basics it’s a presentation I gave a while ago but I reworked and repurposed it both for the audience and this day and age. Of course, it now also includes bunny pics 😉

Slides can be viewed here, on speaker deck, slideshare or PDF

Abstract

Key takeaways
  • What are Elixir and Phoenix? What makes them standout among programming languages and frameworks?
  • Why would I want to use Functional Programming, what are the benefits and why does it work so well for the web?
  • How capable is Erlang (Whatsapp example) performance and reliability wise and why would I consider it for a project?
  • How does explicitness help in system design?

Elixir and Phoenix are known for their speed, but that’s far from their only benefit. Elixir isn’t just a fast Ruby and Phoenix isn’t just Rails for Elixir. Through pattern matching, immutable data structures and new idioms your programs can not only become faster but more understandable and maintainable. This talk will take a look at what’s great, what you might miss and augment it with production experience and advice.

Video & Slides: Functioning Among Humans (Heart of Clojure)

Back in July I had a great time at Heart of Clojure – the first conference who finally allowed me to share my thoughts on the importance of people skills and important people skills. And they were so nice to even record it, so here it is!

Slides can be viewed here, on speaker deck, slideshare and PDF.

 

sketchnotes
sketch notes by my friend @malweene

Abstract

In the development world most people are striving for technical excellence: better code, faster run times, more convenient interfaces, better databases… But is that really what helps us create better software?

In the end software development is done by groups of people creating products together. To do that communication and collaboration are essential. You can be the best programmer ever, but if you can’t efficiently work with others what good does it do you?

This talk will introduce you to relevant, easy to grasp concepts of collaboration and communication as well as give you food for thought.

On Going Freelance

At the end of a lengthy job search I decided to become a freelancer helping companies onboard onto Elixir, helping them with their development projects and processes, some performance work, pushing Open Source and maybe even a bit of interim CTOing or other consulting. Who knows what the future will hold? Right now I’m on a project until the end of October to help a company realize their first Elixir project, so mostly mentoring and coaching.

As I think that reflection is important (hence Retrospectives are the only constant!) I wanted to write a bit about why I decided to take the freelance route:

Flexibility

I like to take (big) breaks between jobs. I’d also love to get some Open Source funding to do Open source full time. Both are hard while working full time, as you want to stay at your job for a prolonged time. It’s not exactly easy in most jobs to say “Hey can I take a 6 month leave because I got this great Open Source fund?”, especially not if you work in a leadership position. Should I discover freelancing isn’t for me it’s also easier to get back into full time employment than the other way around.

Freelancing gives me some of this flexibility. If I already earned enough money I can decide to take a month or more off (although it seems really expensive to do so). I can apply to Open Source funds – in fact I just did last Saturday and am anxiously awaiting the result as I’d love to push a vital part of the Ruby eco system to 1.0 🤞

It also gives me the flexibility to help people with smaller projects. I get approached semi frequently asking if I know of a freelancer to do X and X might be very interesting. Now I can say that I can do X myself, and in fact I’m already throwing ideas around together with a friend. Which leads me to my next point:

Network

While I engage with communities, run the Ruby User Group Berlin, do open source and give presentations because it’s fun to me and I want these things to exist it has the positive side effect of being well connected. My big hope is that I have to spend less time doing client acquisition and can get either more paid time or free time. I also have a variety of freelancer friends whom I always wanted to work with so also keeping my fingers crossed that I might get to work with some of them 💚

Special Knowledge at Use

I happen to have some relatively specialized knowledge and combination of skills that I’d like to use more. For instance, I love performance optimizations and think there’s a market for bringing in freelancers to make your application faster and teach the team how to do this (especially with big Rails applications 😉 ). Other things I love are elixir and teaching. During my interviews I also heard of so many failed elixir introduction projects that I thought: Hey, people need some help adopting elixir! I like elixir, I like coaching/teaching, I like helping people = perfect match?

In fact, that’s exactly what I’m doing right now!

A good project to kick-start things

I was lucky enough that through my network I already had a standing offer for a 3 month project to help a company build their first elixir project. That’s something I really wanted to do and the people at the company were genuinely nice and excited. So you know – I wanted to do it so let’s try it out! “Worst” case, I do this one project and then get back to full time employment.

Choices, Choices, Choices…

I had a bunch of offers and good interviews for a variety of positions. In the end it was always hard for all of the points I mentioned in my post to come together. The project was great but I had concerns about diversity or diversity was great but I had concerns about the project or things are good but the position wasn’t what I wanted or we couldn’t agree about salary & vacations… you get the picture. I know a 100% fit is hard to achieve but in the end you can’t fault me for trying to achieve it, right?

Sometimes the timing also just didn’t work out – the freelance offer had a set deadline on when the project had to start so I couldn’t even finish interviewing with some promising positions as I decided to do (at least) this project.

Don’t get me wrong – there are really good positions out there and I’m still thinking about doing a follow up blog post highlighting some of the cool companies I interviewed with. For me the prospect of freelancing and potentially doing open source work just seemed more tempting at the time. That said, I already lost a CTO position I really liked because I decided to wait for an open source fund that I didn’t get. Let’s just hope that story doesn’t repeat itself 😉

So will you be freelancing forever now?

Maybe? I don’t know. I like it for now (well, a month in..) and if I manage to get the Open Source funding I’ll be ecstatic as I’ll essentially be paid for my hobby and do something good.

However, there are several things I’ll miss about full time employment, most importantly:

  • Building and evolving a team long term & really being part of a team of people you know well
  • Building and evolving processes long term
  • Seeing the long term impact of work and decisions
  • Form a deep understanding of product, processes, market, competitors etc

Of course there are also aspects to freelancing that aren’t ideal, I don’t believe anyone really enjoys doing their taxes, invoicing etc. but that all comes with it. Plus, the risk is all yours – if you can’t find a project you won’t get paid, if you’re sick you’re not getting paid.

For now I enjoy being a freelancer and I’m looking forward to the different projects that’ll hopefully come my way. But for how long? We’ll see 😉

Of course you can help me by hiring or recommending me 🤗

Looking for a job!

NO LONGER (REALLY) LOOKING FOR A JOB

I’m no longer looking for a job, or at least not really. I decided to go freelancing for now and I have a project until the end of October if nothing fails. So if you’ve got new freelance projects or you have a really great CTO/VP/Head of position still please feel free to contact me 😉

(decision to be explained in more detail in a further post)

Original post for historical reasons:


It’s that time: I’m looking for a job! You can find my CV and all relevant links over at my website: CV Web, CV PDF

Quick links that might interest you: website, github, twitter and blog

Who am I and why would you want to hire me?

My name is Tobi, but online I’m better known as PragTob. I am a full-stack engineer & leader deeply interested in agile methodologies, web technologies, software crafting and teaching. I love creating products that help people and am fascinated with the human side of software development.

To have a look at some of the technical topics that I’m involved with you can check out this blog but the core technologies I’ve worked with are Ruby, Elixir, PostgreSQL and JavaScript. I enjoy pair programming, mentoring, TDD, naming discussions and clean code bases. I also have a passion for performance and eliminating bottlenecks. I maintain a variety of open source projects mostly in Ruby (f.ex. simplecov) and Elixir (f.ex. benchee).

While I have this technical background, I believe that the so called “soft”/people/social skills are more important for developers as we all work together in teams. That is even more vital when looking at any kind of lead or even management position, as mentoring, communicating and collaborating is at the heart of what people in these positions should do. I’m deeply interested in topics such as motivation and communication. In my last job I was responsible for a team of ~15 people (together with the CTO). We relied on constant feedback through retrospectives to adapt our processes and grow the team through introducing the concept of seasons, going remote first, enhancing our onboarding and many more improvements. I also did regular one-on-ones, interviewed candidates, facilitated retrospectives and other meetings as well as doing knowledge sharing sessions for the whole team.

Other than these I’ve been mentoring at Rails Girls Berlin/code curious for more than 7 years and am coaching my Rails Girls project group, the rubycorns, for more than 6 years. I also run the Ruby User Group Berlin, and give presentations at various conferences.

My CV goes into more detail about what I’ve done.

What am I looking for?

I’m looking for a company where we build something useful together and where I can have an impact on product, people and process. With more concrete points this amounts to:

Position: I’m primarily looking for lead positions with responsibility so CTO/VP of Engineering/Head of Engineering/Team Lead – all depending on company size and culture. In the right circumstances, I can also imagine working as a Senior Developer. I want to be in an environment where my impact goes beyond code as I love to help people and improve processes. I like to be where I can help the team & the company the most, sometimes that’s mentoring and sharing knowledge, sometimes that’s fixing critical performance bugs and sometimes that’s participating in an all day workshop at the headquarters of a potential client.

Location: Berlin or potentially remote. I’m not looking to relocate currently.

Employment/Freelance: I’m looking for full time employment (reduced hours would also be ok) but am also open to freelance work.

Field of Work: I’m looking for a company that helps people solve real problems. I want a purpose I can get behind. For me that means no crypto currencies, advertisement or fintech for the rich. In a similar vein I’m not particularly interested in consultancy/agency work as I don’t like to travel every week and really like to work at a product company where I can really dive into the domain.

Diversity: I believe that the best products and work environments are created by diverse teams. Hence, this should be a core value applied through all levels of an organization. Or at least, the problem should be recognized and active work to counter it be put forth.

Company Culture: I’m looking for a company that trusts its employees and is open. It should also support a sustainable pace. Regular overtime is nothing to be proud of. Knowledge sharing should be key and therefore asking questions should be encouraged.

Time Allocation: I love companies that trust their employees and allow them flexible working hours and locations. Meaning it’s ok to work remotely for a couple of days or from home. Historically, I did some of my best work checking out emails and pull requests at home in the morning and then biking to work afterwards. Beloved refactorings have also emerged while dog sitting.

Benefits: Giving people time and room to grow is important to me. Particularly I usually speak at a couple of conferences during a year and think going there should be work, not vacation time.

Languages: I have expert knowledge of Ruby and Elixir. Working with Elixir would be a plus, but not a must. I also like working with JavaScript and am not afraid to do CSS albeit my CSS has gotten rather rusty sadly. I’m also naturally open to other languages, while I’m certainly most effective in the mentioned language the right company with the right culture and purpose is more important. Particularly Rust would be very interesting to me, granted I’m not too good at it (yet).

Open Source: An employer that values contributing back to open source or sharing their own creations would be a big plus, even more so if it happened to be full OSS work.

I’m aware that it’s hard to tick all of these boxes, and if you did hey we might be a great match. I just wanted to communicate wishes and values clearly as a starting point.

Getting in touch

You can send me an email at pragtob@gmail.com – otherwise my Twitter direct messages are also open.

Please don’t cold call me 🙂

Released: Statistex 1.0 an Elixir Statistics calculation library

I just released statistex – a library to calculate statistics based on a given data sample. It’s an extraction from my benchmarking library benchee and part of what I’ll henceforth call the “benchee library family”. As it’s been running in benchee basically since its inception I dubbed it 1.0.

The extraction is good because it helps the benchee code base focus on benchmarking and not things around it. It removes about 800 lines from the repo and it makes that code reusable for everyone else. It also makes it easier to introduce new statistics as it’s clearer that we’ll first introduce the logic inside statistex and later on just display it in benchee and friends. It’s good design.

Do we really need another statistics library?

I struggled with this question. I don’t want to split the eco system unnecessarily. To be honest, I thought there was no other library out there. There are at least statistics and Numerix, though. Not sure how I missed them when I started incorporating more advanced statistics.

Both include more functions than just for statistics: general math and more (drawing of random values for instance). They also support more statistical values than statistex at the time of this writing. So if you’re looking for something, that statistex doesn’t provide (yet) these are some of the first places I’d look.

Why would you still want to use statistex? Well there are some things it offers that the others don’t (to the best of my knowledge):

statistics/2 – Give me everything!

As mentioned before, statistex was extracted and the way it was used in benchee is just “give me all the statistics so that formatters can display them!” – so there’s a function that does exactly this:

What’s cool about this? Well, little effort, big result! This is quite nice to explore data sets in iex for instance. Behind the scenes statistex reuses previously calculated values so that no value is calculated twice. For instance first you get the sampe_size and the total, both are then used to calculate the average. The average and sample_size are then passed on to calculate the variance and so forth. This way statistex is fast by not duplicating work if you want a bunch of statistical values (and benchee wants most of them).

But you don’t want all of these values but would still like to reuse previously calculated values? Got you covered!

Manually reuse previously calculated values

Say you want to calculate the variance but have already calculated the average and sample_size. Easy:

Like variance/2 a lot of function take an optional keyword list as arguments where you can provide previously calculated values (options are of course documented).

Raising on empty list input

Thanks to a discussion on elixir forum I made the decision to raise an ArgumentError when statistex is handed an empty list in most functions. Why? The statistics don’t make any sense at this point and it’s likely some kind of error either way/you probably want to display something other than a bunch of nils.

I know many won’t consider this a feature, I quite like the direction it pushes client code towards, though.

Is this enough for a new library?

I think so. 🙂 Especially getting all values at once and reusing previously calculated values are incredibly valuable properties. I also like that statistex is solely focussed on statistics. And the statistics it can’t compute yet? We’ll catch up on that over time. Moreover, it’s not like I spent some huge amount of work writing it as it was a simple extraction.

I’d be happy if you gave statistex a trial run and left some feedback.

 

Slides: Functioning Among Humans (RUG-B)

In a trial run for Heart of Clojure I gave my talk Functioning Among Humans yesterday at RUG::B. It covers topics very close to my heart and is a talk I wanted to give forever. It’s sort of a “best of” soft/social/people skills that I learned going back all the way to high school and that are useful to me in every day life.

If you happened to have seen the talk, please feel free to reach out to me with feedback as I still want to improve upon it for future versions.

Slides can be viewed here, on speaker deck, slideshare or PDF

Abstract

In the development world most people are striving for technical excellence: better code, faster run times, more convenient interfaces, better databases… But is that really what helps us create better software?

In the end software development is done by groups of people creating products together. To do that communication and collaboration are essential. You can be the best programmer ever, but if you can’t efficiently work with others what good does it do you?

This talk will introduce you to relevant, easy to grasp concepts of collaboration and communication as well as give you food for thought.

Finding Bugs with Property Based Testing in a Statistics Calculation

I always loved the idea of Property Based Testing, it was the most mind blowing idea I encountered while learning clojure many years back. However, I always found it hard to apply in practice. I barely encountered the “easy” case where an operation was reversible (if I encode a term and then decode it again it should be equal to the original term, for instance). And the properties I came up always seemed to loose to catch any bugs.

So, I thought well let’s give it another shot. I got all these statistics functions in benchee/statistex – data should be easy to generate for them. Let’s give it a shot, we’ll surely not find a bug… or will we?

The first property based tests

If nothing else, I wanted to make sure no matter what numbers you throw at my statistics module it won’t blow up. To implement it I used stream_data:

This is what I came up with – our samples are any non empty list of floats and there are a bunch of checks that make sure the values are somewhere between minimum and maximum or bigger than 0. No way the tests are failing…

Wait, the tests are failing?!

 Failed with generated values (after 2 successful runs):

* Clause: samples <- list_of(float(), min_length: 1) Generated: [-9.0, -1.0] Assertion with >= failed
code: assert stats.standard_deviation_ratio() >= 0
left: -1.131370849898476
right: 0

Honestly, I was shocked. On closer inspection, the standard deviation ratio was negative when I said it should always be positive. As the generated sample only contains negative numbers the average is negative as well. As the ratio is calculated by dividing the standard deviation by the average it turned out to be negative. Usually I only work with positive samples, hence it never occurred before. The ratio should still always be positive so an abs/1 call fixed it.

Another property

Thinking more I came up with another property:

It’s much like the first properties, just making sure the percentile values are in order as they should there is absolutely no possibility that this will fail, absolutely none, well tested code… no chance it will fail …

IT FAILED AGAIN?!?!?!

 Failed with generated values (after 4 successful runs):

* Clause: samples <- list_of(float(), min_length: 1)
Generated: [1.0, 33.0]

Assertion with <= failed
code: assert percies[25] <= percies[50]
left: 25.0
right: 17.0

Wait, the 25th percentile is bigger than the 50th percentile? No way that’s ok.

A lot of digging, googling and reading our original source for implementing percentile interpolation later I figured out the problem. Basically interpolation for small sample sizes is hard and also uncommon. We missed a clause/case stated in the source, that points out that for a too small percentile and sample size the value is to be set to the minimum.

Note that any p ≤ 1/(N+1) will simply be set to the minimum value.

Our p was 0.25 (25th percentile) and 0.25 <= 1/3. Implementing this clause (through guard clauses) fixed the test.

You can check out the full implementation and bug fixes in the PR.

Learnings

The generation part was super easy in the case shown. However, what’s impressive to me is that although the properties were very loosely defined they still uncovered 2 bugs. And that’s in code that both me and many of you have been running for quite a while in benchee. Sure, they are very specific edge cases but that’s what property based testing is good at: Finding edge cases!

If you have other ideas for properties to check, I’m happy to listen and learn. And give property based testing a shot yourselves even with very loose properties – you might be surprised what you find.

 

What’s the Fastest Data Structure to Implement a Game Board in Elixir?

Ever wanted to implement something board game like in Elixir? Chess? Go? Islands? Well, then you’re gonna need a board!

But what data structure would be the most efficient one to use in Elixir? Conventional wisdom for a lot of programming languages is to use some sort of array. However, most programming languages with immutable data structures don’t have a “real” array data structure (we’ll talk about erlangs array later, it’s not really like the arrays in non functional languages) . Elixir is one of those languages.

As I like board games this was one of the first questions I ever asked the community. It’s also an interesting and relatable example to see and understand the performance trade-offs of different data structures.

Complete sources can be found in my elixir_boards_benchmark repo.

Benchmark Design

For this benchmark I didn’t have a very specific board game in mind so I settled for a board size of 9×9 . It’s a bit bigger than a normal chess board (8×8), it’s exactly the size of the smallest “normal” Go-board and it’s one smaller than the board used in Islands implemented in Functional Web Development with Elixir, OTP and Phoenix, so it seemed like a good compromise. Different sizes are likely to sport different performance characteristics.

Without a concrete usage scenario in mind I settled on a couple of different benchmarks:

  • getting a value at the coordinates (0,0), (4, 4) and (8,8). This is a fairly nano/micro benchmark for data access and provides a good balance of values at the beginning/middle/end when thinking in list terms.
  • setting a value at the coordinates (0,0), (4, 4) and (8,8).
  • a still nano/micro benchmark that combines the two previous benchmarks by getting and setting all three mentioned values. I call this “mixed bag”.
  • Why stop at the previous one? The last benchmark just sets and gets every possible coordinate once (first it sets (0,0) then gets it, then it sets (0, 1), then gets it and so forth). This also simulates the board filling which can be important for some data structures. Completely filling a board is unrealistic for most board games however, as most games finish before this stage. This one is called “getting and setting full board”.

Something that is notably not benchmarked is the creation of boards. For (almost) all of the board implementations it could resolve to a constant value which should be similar in the time it takes to create. I wasn’t overly interested in that property and didn’t want to make the code less readable by inlining the constant after creation when I didn’t need to.

Also noteworthy is that these benchmark mostly treat reading and writing equally while in my experience most AIs/bots are much more read-heavy than write-heavy.

Take all these caveats of the benchmark design into consideration when looking at the results and if in doubt of course best write your own benchmark taking into account the concrete usage patterns of your domain.

Without further ado then let’s look at the different implementations I have benchmarked so far:

Contenders

All boards need to implement a simple Board behaviour:

All boards are built so that accessing a previously unset field will return nil. No assumptions about the data stored in the board have been made, which rules out String as an implementation type. In the benchmarks atoms are used as values.

In the descriptions of the data types below (x, y) is used to mark where what value is stored.

  • List2D: A 2 dimensional list representing rows and columns: [[(0, 0), (0, 1), (0, 2), ...], [(1, 0), (1, 1), ..], ..., [..., (8, 8)]]
  • List1D: Using the knowledge of a constant board size you can encode it into a one-dimensional list resolving the index as dimension * x + y: [(0, 0), (0, 1), (0, 2), ..., (1, 0), (1, 1), ..., (8, 8)]
  • Tuple2D: Basically like List2D but with tuples instead of lists: {{(0, 0), (0, 1), (0, 2), ...}, {(1, 0), (1, 1), ..}, ..., {..., (8, 8)}}
  • Tuple1D: Basically like List1D but with a tuple instead of a list: {(0, 0), (0, 1), (0, 2), ..., (1, 0), (1, 1),... (8, 8)}
  • Array2D: erlang arrays aren’t exactly a common sight, even learn you some Erlang basically skims over them and says to be cautious when using them. I even forgot about them for the first version of this post 😅. They internally map to tuple usage in an interesting way that will be discussed/illustrated further below. With that out of the way, conceptually this is much like Tuple2D.
  • Array1D: see above for the data structure in general, otherwise conceptually like Tuple1D.
  • MapTuple: A map that takes the tuple of the coordinates {x, y} as the key with the value  being whatever is on the board: %{{0, 0} => (0, 0), {0, 1} => (0, 1), ..., {8, 8} => (8, 8)}. It’s a bit unfair compared to others shown so far as it can start with an empty map which of course is a much smaller data structure that is not only smaller but usually faster to retrieve values from. As the benchmarks start with an empty board that’s a massive advantage, so I also included a full map in the benchmark, see next/
  • MapTupleFull: Basically the same as above but initialized to already hold all key value pairs initialized as nil. Serves not only the purpose to see how this performs but also to see how MapTuple performs once it has “filled up”.
  • MapTupleHalfFull: Only looking at complete full performance and empty performance didn’t seem good either, so I added another one initialized from 0 to 4 on all columns (a bit more than a board half, totalling 45 key/value pairs).
  • MapTupleQuarterFull: Another one of these, this time with 27 key/value pairs. Why? Because there is an interesting performance characteristic, read on to find out 🙂
  • Map2D: Akin to List2D etc. a map of maps: %{0 => %{0 => (0, 0), 1 => (0, 1), ...}, 1 => %{0 => (1, 0), ...}, ..., 8 => %{..., 8 => (8, 8)}}
  • ETSSet: erlang ETS storage with table type set. Storage layout wise it’s basically the same as MapTuple, with a tuple of coordinates pointing at the stored value.
  • ETSOrderedSet: Same as above but with table type ordered_set.
  • ProcessDictionary: On a special request for Michał 😉 This is probably not a great default variant as you’re practically creating (process-) global state which means you can’t have two boards within the same process without causing mayham. Also might accidentally conflict with other code using the process dictionary. Still might be worth considering if you want to always run a board in its own process.

It’s significant to point out that all mentioned data types except for ETS and the process dictionary are immutable. This means that especially for those in the benchmark a new board is created in a before_each hook (does not count towards measured time) to avoid “contamination”.

Another notable exception (save for String for the aforementioned constraints) is Record. Records are internally represented as tuples but give you the key/value access of maps, however in elixir it is more common to use Structs (which are backed by maps). As both maps and tuples are already present in the benchmark including these likely wouldn’t lead to new insights.

System Setup

Operating System Linux
CPU Information Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
Number of Available Cores 8
Available Memory 15.61 GB
Elixir Version 1.8.2
Erlang Version 22.0

Benchmarking Results

Benchmarks of course were run with benchee and the benchmarking script is here (nothing too fancy).

You can check them out in the repo as markdown (thanks to benchee_markdown) or HTML reports (benchee_html). Careful though if you’re on mobile some of the HTML reports contain the raw measurements and hence go up to 9MB in size and can take a while to load also due to the JS drawing graphs!

The results of getting and setting full board:

runtime_final.png
getting and setting full board iterations per second (higher is better)

It’s a tight race at the top when it comes to run time! Tupl1D, Tuple2D and MapTuple are all within striking range of each other and then there’s a sharp fall off.

Also there is a fair bit of variance involved as shown by the black “whiskers” (this is usual for benchmarks that finish in nanoseconds or microseconds because of garbage collection, interference etc.). Which one of these is best? To get a better picture let’s look at the whole table of results:

Name IPS Average Deviation Median Mode Minimum Maximum
Tuple1D 133.95 K 7.47 μs ±23.29% 6.93 μs 6.88 μs 6.72 μs 492.37 μs
Tuple2D 132.16 K 7.57 μs ±29.17% 7.21 μs 7.16 μs 7.03 μs 683.60 μs
MapTuple 126.54 K 7.90 μs ±25.69% 7.59 μs 7.56 μs 7.43 μs 537.56 μs
ProcessDictionary 64.68 K 15.46 μs ±14.61% 15.12 μs 15.05 μs 14.89 μs 382.73 μs
ETSSet 60.35 K 16.57 μs ±9.17% 16.04 μs 15.95 μs 15.79 μs 161.51 μs
Array2D 56.76 K 17.62 μs ±17.45% 17.15 μs 17.04 μs 16.54 μs 743.46 μs
MapTupleFull 55.44 K 18.04 μs ±11.00% 16.92 μs 16.59 μs 16.43 μs 141.19 μs
MapTupleHalfFull 53.70 K 18.62 μs ±8.36% 17.96 μs 17.87 μs 17.67 μs 160.86 μs
Array1D 50.74 K 19.71 μs ±10.60% 19.29 μs 18.99 μs 18.81 μs 469.97 μs
ETSOrderedSet 39.53 K 25.30 μs ±10.51% 24.82 μs 24.57 μs 24.34 μs 390.32 μs
Map2D 36.24 K 27.59 μs ±8.32% 27.71 μs 25.90 μs 25.12 μs 179.98 μs
List2D 29.65 K 33.73 μs ±4.12% 33.31 μs 33.04 μs 31.66 μs 218.55 μs
MapTupleQuarterFull 28.23 K 35.42 μs ±3.86% 34.96 μs 34.61 μs 34.39 μs 189.68 μs
List1D 15.41 K 64.90 μs ±2.84% 64.91 μs 64.14 μs 62.41 μs 175.26 μs

Median, and Mode are good values to look at when unsure what is usually fastest. These values are the “middle value” and the most common respectively, as such they are much less likely to be impacted by outliers (garbage collection and such).  These seem to reinforce that Tuple1D is really the fastest, if by a negligible margin.

MapTuple is very fast, but its sibling MapTupleFull, that already starts “full”, is more than 2 times slower. Whether this is significant for you depends if you start with a truly empty board (Go starts with an empty board, chess doesn’t for instance).

Somewhat expectedly List1D does worst as getting values towards to the end of the list it has to traverse the entire list which is incredibly slow.

As an aside, it’s easy to see in the box plot that the high deviation is mainly caused by some very big outliers:

boxplot_final.png
Boxplot of getting and setting full board – dots are outliers

The dots denote outliers and they are so big (but few) that the rest of the chart is practically unreadable as all that remains from the actual box is practically a thick line.

What about memory consumption?

memory_final.png
getting and setting full board memory usage (lower is better)

Here we can see the immediate drawback of Tuple1D – it’s memory consumption is many times worse than that of the others. My (educated) guess is that it’s because it has to replace/copy/update the whole tuple with it’s 9*9 = 81 values for every update operation. Tuple2D is much more economical here, as it only needs to to update the tuple holding the columns and the one holding the specific column we’re updating (2 * 9 = 18) to the best of my understanding.

Big Tuples like this are relatively uncommon in “the real world” in my experience though as their fixed size nature makes them inapplicable for a lot of cases. Luckily, our case isn’t one of them.

MapTuple does amazingly well overall as it’s probably the structure quite some people would have intuitively reached for for good constant memory access speed. It’s memory consumption is also impressively low.

ProcessDictionary is very memory efficient and also constantly in the top 4 when it comes to run time. However, at least run time wise there’s quite the margin ~15 μs to ~7 μs which doesn’t seem to make the risks worth it overall.

Other Observations

Let’s take a look at some other things that seem note worthy:

ETS isn’t the winner

This surprised me a bit (however I haven’t used ETS much). ETS was always tagged as the go to option for performance in my mind. Looking at the docs and use cases I know it makes sense though – we’re likely to see benefits for much larger data sets as ours is relatively small:

These (ETS) provide the ability to store very large quantities of data in an Erlang runtime system, and to have constant access time to the data.

81 values hardly qualifies as “very large”.

Don’t blindly follow conventional “wisdom” – always benchmark! 💪

get(0,0) vs. get(8,8)

Let’s have a look at some of the time it takes to retrieve a value – usually a much more common operation than writing:

get(0,0)

Name IPS Average Deviation Median Mode Minimum Maximum
Tuple1D 44.12 M 22.66 ns ±842.77% 20 ns 20 ns 9 ns 35101 ns
Tuple2D 42.46 M 23.55 ns ±846.67% 20 ns 19 ns 7 ns 36475 ns
Array1D 30.38 M 32.92 ns ±84.61% 32 ns 32 ns 20 ns 8945 ns
MapTuple 29.09 M 34.38 ns ±111.15% 32 ns 31 ns 19 ns 10100 ns
MapTupleQuarterFull 18.86 M 53.03 ns ±37.27% 50 ns 49 ns 38 ns 2579 ns
Array2D 18.62 M 53.70 ns ±67.02% 50 ns 49 ns 34 ns 10278 ns
List1D 18.26 M 54.75 ns ±56.06% 53 ns 52 ns 42 ns 8358 ns
ProcessDictionary 17.19 M 58.18 ns ±1393.09% 52 ns 51 ns 39 ns 403837 ns
Map2D 15.79 M 63.34 ns ±25.86% 60 ns 54 ns 41 ns 388 ns
MapTupleHalfFull 10.54 M 94.87 ns ±27.72% 91 ns 89 ns 76 ns 2088 ns
MapTupleFull 10.29 M 97.16 ns ±18.01% 93 ns 89 ns 70 ns 448 ns
ETSSet 9.74 M 102.63 ns ±26.57% 100 ns 99 ns 78 ns 2629 ns
List2D 9.04 M 110.57 ns ±69.64% 105 ns 109 ns 82 ns 4597 ns
ETSOrderedSet 6.47 M 154.65 ns ±19.27% 152 ns 149 ns 118 ns 1159 ns

get(8, 8)

Name IPS Average Deviation Median Mode Minimum Maximum
Tuple2D 42.47 M 23.55 ns ±788.60% 21 ns 20 ns 7 ns 33885 ns
Tuple1D 40.98 M 24.40 ns ±725.07% 22 ns 21 ns 10 ns 34998 ns
Array1D 29.67 M 33.70 ns ±161.51% 33 ns 32 ns 21 ns 18301 ns
MapTuple 28.54 M 35.03 ns ±986.95% 32 ns 32 ns 20 ns 230336 ns
ProcessDictionary 19.71 M 50.73 ns ±1279.45% 47 ns 47 ns 34 ns 377279 ns
Array2D 17.88 M 55.92 ns ±85.10% 52 ns 51 ns 35 ns 13720 ns
Map2D 13.28 M 75.31 ns ±32.34% 73 ns 65 ns 56 ns 2259 ns
MapTupleHalfFull 12.12 M 82.53 ns ±31.49% 80 ns 80 ns 60 ns 1959 ns
ETSSet 9.90 M 101.05 ns ±16.04% 99 ns 95 ns 78 ns 701 ns
MapTupleFull 9.85 M 101.53 ns ±19.29% 99 ns 90 ns 70 ns 487 ns
ETSOrderedSet 5.59 M 178.80 ns ±41.70% 169 ns 170 ns 135 ns 4970 ns
MapTupleQuarterFull 4.09 M 244.65 ns ±16.85% 242 ns 240 ns 226 ns 9192 ns
List2D 3.76 M 265.82 ns ±35.71% 251 ns 250 ns 231 ns 9085 ns
List1D 1.38 M 724.35 ns ±10.88% 715 ns 710 ns 699 ns 9676 ns

The top 3 remain relatively unchanged. What is very illustrative to look at is List1D and List2D though. For get(0, 0) List1D vastly outperforms its 2D sibling even being closest to the top group. That is easy to explain because it basically translates to looking at the first element of the list which is very fast for a linked list. However, looking at the last element is very slow and this is what get(8, 8) translates to. All elements have to be traversed until the end is reached. As such the whole thing is almost 16 times slower for List1D. List2D is still very slow but through it’s 2-dimenstional structure it only needs to look at 18 elements instead of 81.

MapTuple vs. MapTupleQuarterFull vs. MapTupleHalfFull vs. MapTupleFull

In most scenarios, including the biggest scenario, MapTupleQuarterFull performs worse than MapTuple (expected), MapTupleHalfFull (unexpected) and MapTupleFull (unexpected). I had expected its performance to be worse than MapTuple but better than MapTupleFull and MapTupleHalfFull. Why is that?

I had no idea but Johanna had one: it might have to do with the “magic” limit at which a map “really” becomes a map and not just a list that is linearly searched. That limit is defined as 32 entries in the erlang source code (link also provided by Johanna). Our quarter full implementation is below that limit (27 entries) and hence often performance characteristics more akin to List1D (see good get(0, 0) performance but bad get(8, 8) performance) than its “real” map cousins.

To the best of my understanding this “switch the implementation at size 32” is a performance optimization. With such a small data set a linear search often performs better than the overhead introduced by hashing, looking up etc. You can also see that the trade-off pays off as in the big benchmark where the whole board is filled incrementally MapTuple (which is initially empty and grows) still provides top performance.

What I still don’t fully understand is that sometimes MapTupleFull seems to still outperform MapTupleHalfFull – but only by a very negligible margin (most notably in the “big” getting and setting full board benchmark). The difference however is so small that it doesn’t warrant further investigation I believe, unless you have an idea of course.

Performance difference of Array vs. Tuple

In the introduction I said arrays are backed by tuples – how come their performance is way worse then? Well, let’s have a look at what an array actually looks like:

iex(3)> mine = :array.new(81, default: nil)
{:array, 81, 0, nil, 100}
iex(4)> :array.set(13, :boom, mine)
{:array, 81, 0, nil,
{10, {nil, nil, nil, :boom, nil, nil, nil, nil, nil, nil}, 10, 10, 10, 10, 10,
10, 10, 10, 10}}

It cleverly doesn’t even initialize all the fields but uses some kind of length encoding saying “the value is the default value of nil for the next 100 fields” but also saving its set size limit of 81 (fun fact: these arrays can be configured to also dynamically grow!).

Once we set a value (at index 13) the representation changes showing still some length encoding “there is nothing here for the first 10 entries” but then the indexes 10..19 are expanded as a whole tuple that’s holding our value. So, to the best of my understanding arrays work by adding “stretches” of tuples the size of 10 as they need to.

In general this is a performance optimization especially making writes/updates faster as compared to huge tuples as mainly the 10-tuple holding the concrete value needs to get updated instead of the whole thing.

However, our custom tuple implementations are perfectly sized to begin with and not too huge. Moreover, their whole size being set at compile-time probably enables some optimizations (or so I believe).  Hence the tuple implementations outperform them while arrays don’t do too shabby (especially with read access) as compared to other implementations.

Conclusion

Tuples can be very good for the use case of known at compile time sized collections that need fast access and a simple flat map performs amazingly well. All that least for the relatively small board size (9×9 = 81 fields) benchmarked against here. There is a big caveat for the map though – it is so fast if we can start with an empty map and grow it in size as new pieces are set. The completely initialized map (MapTupleFull) performs way worse, tuples are the clear winners then.

Missing a data structure? Please do a PR! There’s a behaviour to implement and then just to lists to add your module name to – more details.

Update 1 (2019-06-17): Fixed MapTupleHalfFull. Before the update it was actually just quarter full 😅 which has wildly different performance characteristics for reasons now described along with the MapTupleQuarterFull implementation. Thanks goes to Johanna for pointing that out. Also the process registry has been added as another possible implementation on a suggestion from Michał 😉 . Also added a run time box plot to show outliers clearer and visually.

Update 2 (2019-06-18): Added and investigated Arrays thanks to /u/Hauleth over on reddit. Also added a remark about records thanks to /u/friendlysock over on lobste.rs.