How I reduced memory usage by 70% in Binacle.Net

In this article, I’ll take you through my journey of optimizing memory in Binacle.Net, an API built in C# and .NET.

Introduction

Binacle.Net started as a hobby project aimed at solving the 3D Bin Packing Problem in real-time. The API has grown to include a range of algorithms, some fully developed and others still in progress.

At the time of writing Binacle.Net includes both Fitting and Packing functions. While these functions might use algorithms with similar names, they are distinct in purpose and output. The Fitting function assesses whether all items can fit within a bin, while the Packing function aims to maximize bin space by fitting as many items as possible and tracking their positions.

The performance and memory data in this article were derived using BenchmarkDotNet in .Net 8 and are specific to this algorithm and its application within Binacle.Net’s Fitting function.

The charts were made with chartbenchmark.net, and the memory usage is indicated by the thin purple line within the larger bar which indicates execution time.

The Problems

It’s important to take you back before the Fitting and Packing functions existed.

One of the very first problems I encountered included an optimization of over 90% in speed and memory reduction. This, as you can imagine, was false as the algorithms didn’t operate at all or exited early. Tests with scenarios crafted by hand that guaranteed, to an extent, the new algorithm operated correctly, were paramount if I was to continue down this path.

Another issue was with architecture. I based the algorithms on a common interface, which made it easy to switch between different versions and, in the future, different types of algorithms, whilst providing a fairly equal testing environment. This, however, presented a new problem, one that I have to this day.

Each time I needed to refactor the common interface, the original algorithm’s performance could potentially change as well. I could not easily maintain the original algorithm just for historical reasons, so I decided, the benefits that the common interface provides are significantly more valuable than preserving the original algorithm through refactor and test iterations.

The graph below, is the first I have records of. During that time, the algorithm accepted many bins, but only returned the smallest applicable.

The 2nd version showed improvements, but something was wrong, both versions showed a sudden drop in memory and speed on 1000 items. After more investigation I realized that somewhere between 500 and 1000 items, the bins hit their limit and the items could no longer fit into any bin, meaning the algorithms exited early.

For clarity I was using only 5 cm cubes to do the benchmarks. So I run the calculations by hand to confirm it and also gave me new test cases to run the benchmarks on.

The values were carefully chosen so I could see the performance breakpoints of each bin. There were 3 bin sizes, the smallest fits up to 192 items, while the medium fits up to 384 items and the large one fits up to 576.

Looking at the second chart carefully, I could see that the algorithm spiked dramatically from 192 to 193 items, from 384 to 385 and then it would predictably drop at 577 items.

This made me understand that the algorithm didn’t detect that the items could not fit in the smaller size bins, and still tried to fit them. Only when it had failed to do so, did it move on to the next bin size. Version 2 had that issue fixed. You can see the sudden increases with only 1 item more, are present in version 1, but not in version 2.

Furthermore, as evidenced by the chart, in the early exit scenario where no bin could accommodate all the items, version 1 of the algorithm was more performant than version 2. This was all due to how version 2 was created.

The Refactor

After a few months I began to create another algorithm, what would later be named as the Packing function. Initially, I named it Version 3, as with all that came before it. Eventually, I changed my mind, as the algorithm essentially produced a different result. It was still in lines with the First Fit Decreasing, but it had a different purpose. It kept track of the positions of the items and it would try to pack as much as possible.

Due to how the new algorithm worked, it had visibly worse performance, after all, it had more work to do.

Realizing this new algorithm function had an entirely different purpose I began refactoring the algorithms to separate the two, which gave birth to the Fitting and Packing functions.

Through this refactor iteration I had to throw out the common interface entirely and create two new ones. As such, the performance of the original algorithm changed as well.

This was also the time the algorithms stopped accepting multiple bins.

Now

After the refactoring, I began to further improve the algorithms, and after many attempts and versions, I ended up with the following.

The graph now only shows the Fitting function as this is the subject of this article. It also displays a 70% memory reduction between version 1 and version 3, as well as a little over 50% reduction in execution time.

Below is the table with the actual numbers.

How I did it

First I researched. One of the first things that stood out was LINQ, especially when it came down to closures, as it was presented in such a way that it was the most worthwhile in terms of gain for the effort put into it.

When I started rewriting the algorithms without LINQ, there were definite improvements.

In the following two examples you can see how closures increase memory allocation especially inside loops.

I’ve put the full benchmark solution in BenchmarkTests-R2CM, should you wish to test it yourself.

foreach (var author in this.Authors!)
{
  var article = author.Articles.FirstOrDefault(x => x.WordCount > wordCountMin && x.WordCount <= wordCountMax);
  // ...
}

// VS

foreach (var author in this.Authors!)
{
  foreach (var article in author.Articles)
  {
    if (article.WordCount > wordCountMin && article.WordCount <= wordCountMax)
    {
      //...
    }
  }
}

As you can see, from the table above, for 1 author, when using LINQ, we have 104 bytes of allocation more than the foreach loop. With 5 authors we have 520 bytes and with 10, we have 1,040 bytes, more than the foreach loop. If we divide 520 by 5, we get 104, which is the same result for 1,040 divided by 10. That means every loop we do, it allocates an extra 104 bytes over the foreach loop, just for the closure.

This is also a subject for further analysis; as the article is already getting too long.

Another change I made was my data structure. In Version 1 of the algorithm I only had 3 properties to hold the dimensions and I had an iterator which returned new items for each orientation.

public IEnumerable<Item> GetOrientations()
{
  yield return new Item { ID = this.ID, Length = this.Length, Width = this.Width, Height = this.Height };
  // and so on ..
}

Version 2 changed that and held a copy of the original dimensions. The rotation of the item, however, was handled internally by swapping the variables.

class Item
{
  public int Height { get; set; }
  private int originalLength;
  // ...

  private int currentOrientation = 0;  
  public void Rotate()
  {
    // perform rotation
  }
}

The first table I want to show you is the benchmarks that measure the memory allocation when creating these two items.

As you can see Version 2 allocates more memory per item, specifically 16 more bytes, which is 4 bytes per additional dimension and 4 more for keeping track of the orientation.

However, by changing how my items are structured I was able to achieve the following result.

Version 2 is orders of magnitude faster and allocates 0 memory for rotating the item.

By trading some more memory upfront I was able to make a dramatic improvement over memory and speed in the rotation of items.

There are a few issues I have yet to deal with, and do require more work, but these were benefits I achieved with minimal core changes, albeit with a lot of testing and experimentation, and what you don’t see are the failed attempts.

Lessons Learned

I could have chosen not to optimize the algorithms and waited until Binacle.Net could potentially start getting serious use, but this is still a hobby project and there was a lot I learned from this and I hope some of it may have been of some use to you.

Here’s what I learned.

1. Don’t do it.
In most scenarios you will rarely need to optimize anything, or at least wait until you really need it. Doing it early can eat up your time and a lot can go wrong during optimization.

2. Tests, and some more tests
Make sure you have proper tests in place to ensure your code produces the expected output. Doing so will allow you to refactor key parts, then run them to ensure nothing broke.

3. Aim for the low hanging fruit.
Identify what can easily be changed first, LINQ can be a good candidate. The optimization game is one of effort and output. At first, you will most likely want to aim to achieve the most you can get, with as little effort possible.

4. Interpret the results.
Your benchmark results may have an underlying meaning. Try to analyze them as they may reveal something about your code.

5. You will probably fail… a lot!
Try to materialize those ideas, but don’t be discouraged, some will fail and make the performance worse and that’s good, because now you learned something.

6. Data structures.
Sometimes you may have to consider changing your data structures to achieve better performance.

That’s all I have for you, take care!

Photo by Bernd 📷 Dittrich on Unsplash