The Flyweight Pattern in Go

Minimizing memory usage by sharing data with other objects

Martin Kock
Jan 21 · 5 min read
Photo by Robert Kresse on Unsplash

Definition:

Flyweight is a software design pattern. A flyweight is an object that minimizes memory usage by sharing as much data as possible with other similar objects; it is a way to use objects in large numbers when a simple repeated representation would use an unacceptable amount of memory. — Wikipedia

In the following, I’ll demonstrate the flyweight pattern with two examples in Go. First, I’ll optimize two memory-based caches that rely on the same underlying data, and then I’ll optimize another cache that contains repetitive data.

Let’s get to it. All examples are written in Golang, full examples are provided in the appendix.


Preamble

For both examples, consider this type:

Player definition.

Players on a gaming platform. This is a bit contrived, but fairly straightforward for our purposes. Example:

Player One.

First Example: One Cache, Three Lookup Methods

Assume that we wish to cache every single Player in our app in memory for quick access, and we need to be able to look them up by ID, Handle, and country Code. A first (naive) implementation might look like this:

Three data structures containing the same players.

These are filled with data from the database by looping over the individual table rows and, for each one, populate an instance of Player with the fields from each row and adding it to each map.

Maps are used for the lookups because they are efficient: when you already have the key, you don’t need to loop over the entire data structure every time — an O(n) operation — but can do a direct lookup in constant time, O(1).

This is an important optimization when there are thousands or millions of players.

Let’s take a quick look at the lookup functions for each one of the above:

Lookup functions before refactoring.

Fairly straightforward.

But there’s a problem: each player exists three times, taking up three times more memory than necessary.

Let’s go back to our cache declarations and fix that by appointing one of the maps as the “base of truth”, or “point of reference” if you will.

The declaration that uses the Player ID seems appropriate for two reasons: because the ID serves as a primary key, and because an uint32 takes up much less space than the Player’s Handle, a string of arbitrary length. Let’s refactor to:

Refactored data structures.

Now, playerCountryMap and playerHandleMap both serve as references to playerIDMap. Obviously, we’ll need to refactor our lookup functions a bit:

Refactored lookup functions.

Note that the first function, FindPlayerByID, hasn’t changed. The second, FindPlayerByHandle, will now retrieve the Player ID instead of a Player and proceed to call FindPlayerByID to finalize the lookup.

Due to the two lookups, the complexity is now O(2) rather than O(1), which is still constant time, and the difference in performance between these two approaches can therefore be considered negligible.

The third function is a bit more interesting. We create a slice initialized with the size of the ID slice we get from the first lookup, and then loop over the IDs while looking them up individually and adding the Player to the slice.

We don’t need to check for the presence of the ID, because we are in control of the cache; we know it exists. Due to the loop, the complexity is O(n+1), or just O(n).

This is worse than a direct lookup, so you have two strategies here:

  1. Continue with this implementation, which is a bit slower but saves memory, or:
  2. Stick to the original implementation which takes more memory but has a faster lookup.

You can — and should — mix and match these two strategies on a case-by-case basis; always choose the strategy that fits the situation.

As a final note for this example, you could also use pointers for reference instead of uint32s. The concept would be the same, and you could stick to always using pointers that reference the original structs rather than doing several, interdependent lookups.

But keep in mind that having a cache with thousands — or millions — of pointers also increases the number of pointers that the GC has to manage correspondingly, which can negatively affect GC pause times.

Values are preferable when you don’t need to change the data.


Second Example: Data Replication

Let’s assume a scenario where we’re still caching Players, but for this particular part of the app, we can say with absolute certainty that they have all played exactly the same games.

Perhaps because one of the video game publishers, CrashyGames, Inc., has requested a locally manageable list of all the players on the platform that have played all their games — perhaps so they can apologize to them about the questionable quality of their games?

We can immediately see that we can save a lot of memory by not storing the field Games for each Player. Since we still need that field to be part of the datatype, we’ll store it separately, and then add it to an ad-hoc Player when one is requested.

For this purpose, we’ll need a second datatype, which we’ll call cachedPlayer:

Definition of cachedPlayer.

You may have noticed that the name starts with a lowercase “c”; we won’t be exporting this type, but only using it internally, in the scope of our cache.

This is our cache, and our games list:

Cache and games list.

This time, we’ll just look them up directly by ID, which is represented by the uint32. But CrashyGames has millions of players, making this optimization worthwhile.

So, let’s dive into some code. It doesn’t take much work. First, we’ll declare a convenience method on cachedPlayer that converts it into a regular Player:

Converter method for cacedPlayer.

Now we can implement the cache lookup:

Implementation of FindPlayerByID.

I’ve kept the method cachedPlayer.convertWith pure, taking extra fields as parameters, while FindPlayerByID is a closure over the variable games, which is just stored in a package-level variable, but you can implement it any way you like.

And voilà! Now we store everything exactly once. You could even take it to the next level and save the Player names in a separate data structure if there are many repetitive names.

But beware of the overhead of performing the name comparisons, and of growing the data structure with names. Do it only when there are real savings to be had.


Conclusion

The flyweight pattern is your friend, but as with most things, there’s a balance to be struck; optimize too much, and you introduce undesirable complexity — optimize too little, and your app becomes clunky and slow.

Consider the size of your data structure, and the impact on code readability and on the maintainability of your app before deciding to use the flyweight pattern. And remember the old saying by Donald Knuth:

“Premature optimization is the root of all evil.”

Now go optimize your code!


Appendix

Example one after applying the flyweight pattern.
Example two after applying the flyweight pattern.

Better Programming

Advice for programmers.

Thanks to Zack Shapiro

Martin Kock

Written by

Interested in tech

Better Programming

Advice for programmers.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade