Flyweight pattern
In computer programming, 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. Often some parts of the object state can be shared, and it is common practice to hold them in external data structures and pass them to the objects temporarily when they are used.
A classic example usage of the flyweight pattern is the data structures for graphical representation of characters in a word processor. It might be desirable to have, for each character in a document, a glyph object containing its font outline, font metrics, and other formatting data, but this would amount to hundreds or thousands of bytes for each character. Instead, for every character there might be a reference to a flyweight glyph object shared by every instance of the same character in the document; only the position of each character (in the document and/or the page) would need to be stored internally.
Another example is string interning.
In other contexts the idea of sharing identical data structures is called hash consing.
Overview
The Flyweight [1] design pattern is one of the twenty-three well-known GoF design patterns that describe how to solve recurring design problems to design flexible and reusable object-oriented software, that is, objects that are easier to implement, change, test, and reuse.
What problems can the Flyweight design pattern solve? [2]
- Large numbers of objects should be supported efficiently.
- Creating large numbers of objects should be avoided.
When representing large text documents, for example, creating an object for each character in the document would result in a huge number of objects that could not be processed efficiently.
What solution does the Flyweight design pattern describe?
Define Flyweight objects that
- store intrinsic (invariant) state that can be shared and
- provide an interface through which extrinsic (variant) state can be passed in.
This enables clients to (1) reuse (share) Flyweight objects
(instead of creating a new object each time) and (2) pass in extrinsic state when they invoke a Flyweight operation.
This greatly reduces the number of physically created objects.
Intrinsic state is invariant (context independent) and therefore can be shared
(for example, the code of character 'A' in a given character set).
Extrinsic state is variant (context dependent) and therefore can not be shared and must be passed in
(for example, the position of character 'A' in a text document).
See also the UML class and sequence diagram below.
History
According to the textbook Design Patterns: Elements of Reusable Object-Oriented Software,[3] the flyweight pattern was first coined and extensively explored by Paul Calder and Mark Linton in 1990 to efficiently handle glyph information in a WYSIWYG document editor,[4] although similar techniques were already used in other systems, e.g., an application framework by Weinand et al. (1988).[5]
Structure
UML class and sequence diagram
In the above UML class diagram,
the Client class refers (1) to the FlyweightFactory class to create/share Flyweight objects and (2) to the Flyweight interface to perform an operation by passing in extrinsic (variant) state
(flyweight.operation(extrinsicState)). The Flyweight1 class
implements the Flyweight interface and stores intrinsic (invariant) state that can be shared.
The sequence diagram shows the run-time interactions:
The Client object
calls getFlyweight(key) on the
FlyweightFactory that creates and returns a Flyweight1 object.
After calling operation(extrinsicState)
on the returned Flyweight1 object,
the Client again calls getFlyweight(key)
on the FlyweightFactory, which now shares and returns
the already existing Flyweight1 object.
Immutability and equality
To enable safe sharing, between clients and threads, Flyweight objects must be immutable. Flyweight objects are by definition value objects. The identity of the object instance is of no consequence therefore two Flyweight instances of the same value are considered equal.
Example in C# (note Equals and GetHashCode overrides as well as == and != operator overloads):
public class CoffeeFlavour {
public CoffeeFlavour(string flavour) {
this.Flavour = flavour;
}
public string Flavour { get; }
public override bool Equals(object obj) {
if (ReferenceEquals(null, obj)) return false;
return obj is CoffeeFlavour && Equals((CoffeeFlavour)obj);
}
public bool Equals(CoffeeFlavour other) {
return string.Equals(this.Flavour, other.Flavour);
}
public override int GetHashCode() {
return this.Flavour.GetHashCode();
}
public static bool operator ==(CoffeeFlavour a, CoffeeFlavour b) {
return Equals(a, b);
}
public static bool operator !=(CoffeeFlavour a, CoffeeFlavour b) {
return !Equals(a, b);
}
}
Concurrency
Special consideration must be made in scenarios where Flyweight objects are created on multiple threads. If the list of values is finite and known in advance the Flyweights can be instantiated ahead of time and retrieved from a container on multiple threads with no contention. If Flyweights are instantiated on multiple threads there are two options:
- Make Flyweight instantiation single threaded thus introducing contention and ensuring one instance per value.
- Allow concurrent threads to create multiple Flyweight instances thus eliminating contention and allowing multiple instances per value. This option is only viable if the equality criterion is met.
Example in C#
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Threading;
public interface ICoffeeFlavourFactory {
CoffeeFlavour GetFlavour(string flavour);
}
public class ReducedMemoryFootprint : ICoffeeFlavourFactory {
private readonly object _cacheLock = new object();
private readonly IDictionary<string, CoffeeFlavour> _cache = new Dictionary<string, CoffeeFlavour>();
public CoffeeFlavour GetFlavour(string flavour) {
if (_cache.TryGetValue(flavour, out CoffeeFlavour cachedCoffeeFlavour))
return cachedCoffeeFlavour;
var coffeeFlavour = new CoffeeFlavour(flavour);
ThreadPool.QueueUserWorkItem(AddFlavourToCache, coffeeFlavour);
return coffeeFlavour;
}
private void AddFlavourToCache(object state) {
var coffeeFlavour = (CoffeeFlavour)state;
if (!_cache.ContainsKey(coffeeFlavour.Flavour)) {
lock (_cacheLock) {
_cache[coffeeFlavour.Flavour] = coffeeFlavour;
}
}
}
}
public class MinimumMemoryFootprint : ICoffeeFlavourFactory {
private readonly ConcurrentDictionary<string, CoffeeFlavour> _cache = new ConcurrentDictionary<string, CoffeeFlavour>();
public CoffeeFlavour GetFlavour(string flavour) {
return _cache.GetOrAdd(flavour, flv => new CoffeeFlavour(flv));
}
}
Simple implementation
Flyweight allows you to share bulky data that are common to each object. In other words, if you think that same data is repeating for every object, you can use this pattern to point to the single object and hence can easily save space. Here the FlyweightPointer creates a static member Company, which is used for every object of MyObject.
// Defines Flyweight object that repeats itself.
public class FlyWeight
{
public string CompanyName { get; set; }
public string CompanyLocation { get; set; }
public string CompanyWebSite { get; set; }
//Bulky Data
public byte[] CompanyLogo { get; set; }
}
public static class FlyWeightPointer
{
public static readonly FlyWeight Company = new FlyWeight
{
CompanyName = "Abc",
CompanyLocation = "XYZ",
CompanyWebSite = "www.abc.com"
// Load CompanyLogo here
};
}
public class MyObject
{
public string Name { get; set; }
public string Company
{
get
{
return FlyWeightPointer.Company.CompanyName;
}
}
}
Example in Java
import java.util.ArrayList;
import java.util.WeakHashMap;
class CoffeeFlavour {
private final String name;
private static final WeakHashMap<String, CoffeeFlavour> CACHE = new WeakHashMap<>();
// only intern() can call this constructor
private CoffeeFlavour(String name) {
this.name = name;
}
@Override
public String toString() {
return name;
}
public static CoffeeFlavour intern(String name) {
synchronized (CACHE) {
return CACHE.computeIfAbsent(name, CoffeeFlavour::new);
}
}
public static int flavoursInCache() {
synchronized (CACHE) {
return CACHE.size();
}
}
}
@FunctionalInterface
interface Order {
void serve();
static Order of(String flavourName, int tableNumber) {
CoffeeFlavour flavour = CoffeeFlavour.intern(flavourName);
return () -> System.out.println("Serving " + flavour + " to table " + tableNumber);
}
}
class CoffeeShop {
private final ArrayList<Order> orders = new ArrayList<>();
public void takeOrder(String flavour, int tableNumber) {
orders.add(Order.of(flavour, tableNumber));
}
public void service() {
orders.forEach(Order::serve);
}
}
public class FlyweightExample {
public static void main(String[] args) {
CoffeeShop shop = new CoffeeShop();
shop.takeOrder("Cappuccino", 2);
shop.takeOrder("Frappe", 1);
shop.takeOrder("Espresso", 1);
shop.takeOrder("Frappe", 897);
shop.takeOrder("Cappuccino", 97);
shop.takeOrder("Frappe", 3);
shop.takeOrder("Espresso", 3);
shop.takeOrder("Cappuccino", 3);
shop.takeOrder("Espresso", 96);
shop.takeOrder("Frappe", 552);
shop.takeOrder("Cappuccino", 121);
shop.takeOrder("Espresso", 121);
shop.service();
System.out.println("CoffeeFlavor objects in cache: " + CoffeeFlavour.flavoursInCache());
}
}
The execution of this code will give the following :
Serving Cappuccino to table 2
Serving Frappe to table 1
Serving Espresso to table 1
Serving Frappe to table 897
Serving Cappuccino to table 97
Serving Frappe to table 3
Serving Espresso to table 3
Serving Cappuccino to table 3
Serving Espresso to table 96
Serving Frappe to table 552
Serving Cappuccino to table 121
Serving Espresso to table 121
CoffeeFlavor objects in cache: 3
Example in Scala
/*
run as a script using `scala flyweight.scala`
expected output:
Serving CoffeeFlavour(Espresso) to table 121
Serving CoffeeFlavour(Cappuccino) to table 121
Serving CoffeeFlavour(Frappe) to table 552
Serving CoffeeFlavour(Espresso) to table 96
Serving CoffeeFlavour(Cappuccino) to table 3
Serving CoffeeFlavour(Espresso) to table 3
Serving CoffeeFlavour(Frappe) to table 3
Serving CoffeeFlavour(Cappuccino) to table 97
Serving CoffeeFlavour(Frappe) to table 897
Serving CoffeeFlavour(Espresso) to table 1
Serving CoffeeFlavour(Frappe) to table 1
Serving CoffeeFlavour(Cappuccino) to table 2
total CoffeeFlavour objects made: 3
*/
/* the `private` constructor ensures that only interned
* values of type `CoffeeFlavour` can be obtained. */
class CoffeeFlavour private (val name: String){
override def toString = s"CoffeeFlavour($name)"
}
object CoffeeFlavour {
import scala.collection.mutable
import scala.ref.WeakReference
private val cache = mutable.Map.empty[String, ref.WeakReference[CoffeeFlavour]]
def apply(name: String): CoffeeFlavour = synchronized {
cache.get(name) match {
case Some(WeakReference(flavour)) => flavour
case _ =>
val newFlavour = new CoffeeFlavour(name)
cache.put(name, WeakReference(newFlavour))
newFlavour
}
}
def totalCoffeeFlavoursMade = cache.size
}
case class Order(tableNumber: Int, flavour: CoffeeFlavour){
def serve: Unit =
println(s"Serving $flavour to table $tableNumber")
}
object CoffeeShop {
var orders = List.empty[Order]
def takeOrder(flavourName: String, table: Int) {
val flavour = CoffeeFlavour(flavourName)
val order = Order(table, flavour)
orders = order :: orders
}
def service: Unit = orders.foreach(_.serve)
def report =
s"total CoffeeFlavour objects made: ${CoffeeFlavour.totalCoffeeFlavoursMade}"
}
CoffeeShop.takeOrder("Cappuccino", 2)
CoffeeShop.takeOrder("Frappe", 1)
CoffeeShop.takeOrder("Espresso", 1)
CoffeeShop.takeOrder("Frappe", 897)
CoffeeShop.takeOrder("Cappuccino", 97)
CoffeeShop.takeOrder("Frappe", 3)
CoffeeShop.takeOrder("Espresso", 3)
CoffeeShop.takeOrder("Cappuccino", 3)
CoffeeShop.takeOrder("Espresso", 96)
CoffeeShop.takeOrder("Frappe", 552)
CoffeeShop.takeOrder("Cappuccino", 121)
CoffeeShop.takeOrder("Espresso", 121)
CoffeeShop.service
println(CoffeeShop.report)
Example in Ruby
# Flyweight Object
class Lamp
attr_reader :color
#attr_reader makes color attribute available outside
#of the class by calling .color on a Lamp instance
def initialize(color)
@color = color
end
end
class TreeBranch
def initialize(branch_number)
@branch_number = branch_number
end
def hang(lamp)
puts "Hang #{lamp.color} lamp on branch #{@branch_number}"
end
end
# Flyweight Factory
class LampFactory
def initialize
@lamps = {}
end
def find_lamp(color)
if @lamps.has_key?(color)
# if the lamp already exists, reference it instead of creating a new one
lamp = @lamps[color]
else
lamp = Lamp.new(color)
@lamps[color] = lamp
end
lamp
end
def total_number_of_lamps_made
@lamps.size
end
end
class ChristmasTree
def initialize
@lamp_factory = LampFactory.new
@lamps_hung = 0
dress_up_the_tree
end
def hang_lamp(color, branch_number)
TreeBranch.new(branch_number).hang(@lamp_factory.find_lamp(color))
@lamps_hung += 1
end
def dress_up_the_tree
hang_lamp('red', 1)
hang_lamp('blue', 1)
hang_lamp('yellow', 1)
hang_lamp('red', 2)
hang_lamp('blue', 2)
hang_lamp('yellow', 2)
hang_lamp('red', 3)
hang_lamp('blue', 3)
hang_lamp('yellow', 3)
hang_lamp('red', 4)
hang_lamp('blue', 4)
hang_lamp('yellow', 4)
hang_lamp('red', 5)
hang_lamp('blue', 5)
hang_lamp('yellow', 5)
hang_lamp('red', 6)
hang_lamp('blue', 6)
hang_lamp('yellow', 6)
hang_lamp('red', 7)
hang_lamp('blue', 7)
hang_lamp('yellow', 7)
puts "Made #{@lamp_factory.total_number_of_lamps_made} total lamps"
puts "Hung #{@lamps_hung} total lamps"
end
end
Example in Python
Attributes can be defined at the class-level instead of only for instances in Python because classes are first-class objects in the language—meaning there are no restrictions on their use as they are the same as any other object. New-style class instances store instance data in a special attribute dictionary instance.__dict__. By default, accessed attributes are first looked up in this __dict__, and then fall back to the instance's class attributes next. [7] In this way, a class can effectively be a kind of Flyweight container for its instances.
Although Python classes are mutable by default, immutability can be emulated by overriding the class's __setattr__ method so that it disallows changes to any Flyweight attributes.
# Instances of CheeseBrand will be the Flyweights
class CheeseBrand(object):
def __init__(self, brand: str, cost: float) -> None:
self.brand = brand
self.cost = cost
self._immutable = True # Disables future attributions
def __setattr__(self, name, value):
if getattr(self, '_immutable', False): # Allow initial attribution
raise RuntimeError('This object is immutable')
else:
super().__setattr__(name, value)
class CheeseShop(object):
menu = {} # Shared container to access the Flyweights
def __init__(self) -> None:
self.orders = {} # per-instance container with private attributes
def stock_cheese(self, brand: str, cost: float) -> None:
cheese = CheeseBrand(brand, cost)
self.menu[brand] = cheese # Shared Flyweight
def sell_cheese(self, brand: str, units: int) -> None:
self.orders.setdefault(brand, 0)
self.orders[brand] += units # Instance attribute
def total_units_sold(self):
return sum(self.orders.values())
def total_income(self):
income = 0
for brand, units in self.orders.items():
income += self.menu[brand].cost * units
return income
shop1 = CheeseShop()
shop2 = CheeseShop()
shop1.stock_cheese('white', 1.25)
shop1.stock_cheese('blue', 3.75)
# Now every CheeseShop have 'white' and 'blue' on the inventory
# The SAME 'white' and 'blue' CheeseBrand
shop1.sell_cheese('blue', 3) # Both can sell
shop2.sell_cheese('blue', 8) # But the units sold are stored per-instance
assert shop1.total_units_sold() == 3
assert shop1.total_income() == 3.75 * 3
assert shop2.total_units_sold() == 8
assert shop2.total_income() == 3.75 * 8
Example in Swift
// Instances of CoffeeFlavour will be the Flyweights
struct CoffeeFlavor : CustomStringConvertible {
var flavor: String
var description: String { flavor }
}
// Menu acts as a factory and cache for CoffeeFlavour flyweight objects
struct Menu {
private var flavors: [String: CoffeeFlavor] = [:]
mutating func lookUp(flavor: String) -> CoffeeFlavor {
if let existing = flavors[flavor] { return existing }
let newFlavor = CoffeeFlavor(flavor: flavor)
flavors[flavor] = newFlavor
return newFlavor
}
}
struct CoffeeShop {
private var orders: [Int: CoffeeFlavor] = [:]
private var menu = Menu()
mutating func takeOrder(flavor: String, table: Int) {
orders[table] = menu.lookUp(flavor: flavor)
}
func serve() {
for (table, flavor) in orders {
print("Serving \(flavor) to table \(table)")
}
}
}
var coffeeShop = CoffeeShop()
coffeeShop.takeOrder(flavor: "Cappuccino", table: 1)
coffeeShop.takeOrder(flavor: "Frappe", table: 3)
coffeeShop.takeOrder(flavor: "Espresso", table: 2)
coffeeShop.takeOrder(flavor: "Frappe", table: 15)
coffeeShop.takeOrder(flavor: "Cappuccino", table: 10)
coffeeShop.takeOrder(flavor: "Frappe", table: 8)
coffeeShop.takeOrder(flavor: "Espresso", table: 7)
coffeeShop.takeOrder(flavor: "Cappuccino", table: 4)
coffeeShop.takeOrder(flavor: "Espresso", table: 9)
coffeeShop.takeOrder(flavor: "Frappe", table: 12)
coffeeShop.takeOrder(flavor: "Cappuccino", table: 13)
coffeeShop.takeOrder(flavor: "Espresso", table: 5)
coffeeShop.serve()
Example in Crystal
# Instances of CoffeeFlavor will be the Flyweights
class CoffeeFlavor
def initialize(new_flavor : String)
@name = new_flavor
end
def to_s(io)
io << @name
end
end
# Menu acts as a factory and cache for CoffeeFlavor flyweight objects
class Menu
def initialize
@flavors = {} of String => CoffeeFlavor
end
def lookup(flavor_name : String)
@flavors[flavor_name] ||= CoffeeFlavor.new(flavor_name)
end
def total_flavors_made
@flavors.size
end
end
# Order is the context of the CoffeeFlavor flyweight.
class Order
private getter table_number : Int32, flavor : CoffeeFlavor
def initialize(@table_number, @flavor)
end
def serve
puts "Serving #{flavor} to table #{table_number}"
end
end
class CoffeeShop
private getter orders
private getter menu
def initialize
@orders = [] of Order
@menu = Menu.new
end
def take_order(flavor_name : String, table : Int32)
flavor = menu.lookup(flavor_name)
order = Order.new(table, flavor)
@orders << order
end
def service
orders.each do |order|
order.serve
end
end
def report
"Total CoffeeFlavor made: #{menu.total_flavors_made}"
end
end
# Program
shop = CoffeeShop.new
shop.take_order("Cappuchino", 2)
shop.take_order("Frappe", 1)
shop.take_order("Espresso", 1)
shop.take_order("Frappe", 897)
shop.take_order("Cappuccino", 97)
shop.take_order("Frappe", 3)
shop.take_order("Espresso", 3)
shop.take_order("Cappuccino", 3)
shop.take_order("Espresso", 96)
shop.take_order("Frappe", 552)
shop.take_order("Cappuccino", 121)
shop.take_order("Espresso", 121)
shop.service
puts shop.report
Output
Serving Cappuchino to table 2 Serving Frappe to table 1 Serving Espresso to table 1 Serving Frappe to table 897 Serving Cappuccino to table 97 Serving Frappe to table 3 Serving Espresso to table 3 Serving Cappuccino to table 3 Serving Espresso to table 96 Serving Frappe to table 552 Serving Cappuccino to table 121 Serving Espresso to table 121 Total CoffeeFlavor made: 4
Example in C++
The C++ Standard Template Library provides several containers that allow unique objects to be mapped to a key. The use of containers helps further reduce memory usage by removing the need for temporary objects to be created.
#include <iostream>
#include <map>
#include <string>
// Instances of Tenant will be the Flyweights
class Tenant {
public:
Tenant(const std::string& name = "") : m_name(name) {}
std::string name() const {
return m_name;
}
private:
std::string m_name;
};
// Registry acts as a factory and cache for Tenant flyweight objects
class Registry {
public:
Registry() : tenants() {}
Tenant findByName(const std::string& name) {
if (tenants.count(name) != 0) return tenants[name];
auto newTenant = Tenant(name);
tenants[name] = newTenant;
return newTenant;
}
private:
std::map<std::string,Tenant> tenants;
};
// Apartment maps a unique tenant to their room number.
class Apartment {
public:
Apartment() : m_occupants(), m_registry() {}
void addOccupant(const std::string& name, int room) {
m_occupants[room] = m_registry.findByName(name);
}
void tenants() {
for (auto i : m_occupants) {
const int room = i.first;
const Tenant tenant = i.second;
std::cout << tenant.name() << " occupies room " << room << std::endl;
}
}
private:
std::map<int,Tenant> m_occupants;
Registry m_registry;
};
int main() {
Apartment apartment;
apartment.addOccupant("David", 1);
apartment.addOccupant("Sarah", 3);
apartment.addOccupant("George", 2);
apartment.addOccupant("Lisa", 12);
apartment.addOccupant("Michael", 10);
apartment.tenants();
return 0;
}
See also
- Copy-on-write
- Memoization
- Multiton
References
- Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (1994). Design Patterns: Elements of Reusable Object-Oriented Software. Addison Wesley. pp. 195ff. ISBN 978-0-201-63361-0.CS1 maint: multiple names: authors list (link)
- "The Flyweight design pattern - Problem, Solution, and Applicability". w3sDesign.com. Retrieved 2017-08-12.
- Gamma, Erich; Richard Helm; Ralph Johnson; John Vlissides (1995). Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley. pp. 205–206. ISBN 978-0-201-63361-0.
- Calder, Paul R.; Linton, Mark A. (October 1990). Glyphs: Flyweight Objects for User Interfaces. The 3rd Annual ACM SIGGRAPH Symposium on User Interface Software and Technology. Snowbird, Utah, United States. pp. 92–101. doi:10.1145/97924.97935. ISBN 0-89791-410-4.
- Weinand, Andre; Gamma, Erich; Marty, Rudolf (1988). ET++—an object oriented application framework in C++. OOPSLA (Object-Oriented Programming Systems, Languages and Applications). San Diego, California, United States. pp. 46–57. CiteSeerX 10.1.1.471.8796. doi:10.1145/62083.62089. ISBN 0-89791-284-5.
- "The Flyweight design pattern - Structure and Collaboration". w3sDesign.com. Retrieved 2017-08-12.
- "Data Model §". The (online) Python Language Reference. Python Software Foundation. Retrieved 7 March 2017.