Flyweight pattern

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 flyweight 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.

History[edit]

According to the textbook Design Patterns: Elements of Reusable Object-Oriented Software,[1] 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,[2] although similar techniques were already used in other systems, e.g., an application framework by Weinand et al. (1988).[3]

Immutability and equality[edit]

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 {
    private readonly string _flavour;

    public CoffeeFlavour(string flavour) {
        _flavour = flavour;
    }

    public string Flavour {
        get { return _flavour; }
    }

    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(_flavour, other._flavour);
    }

    public override int GetHashCode() {
        return (_flavour != null ? _flavour.GetHashCode() : 0);
    }

    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[edit]

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:

  1. Make Flyweight instantiation single threaded thus introducing contention and ensuring one instance per value.
  2. 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#[edit]

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.ContainsKey(flavour)) return _cache[flavour];
        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) {
                if (!_cache.ContainsKey(coffeeFlavour.Flavour)) _cache.Add(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[edit]

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[edit]

import java.util.List;
import java.util.Map;
import java.util.Vector;
import java.util.concurrent.ConcurrentHashMap;

// Instances of CoffeeFlavour will be the Flyweights
class CoffeeFlavour {
  private final String name;

  CoffeeFlavour(final String newFlavor) {
    this.name = newFlavor;
  }

  @Override
  public String toString() {
    return name;
  }
}

// Menu acts as a factory and cache for CoffeeFlavour flyweight objects
class Menu {
  private Map<String, CoffeeFlavour> flavours = new ConcurrentHashMap<String, CoffeeFlavour>();

  synchronized CoffeeFlavour lookup(final String flavorName) {
    if (!flavours.containsKey(flavorName))
      flavours.put(flavorName, new CoffeeFlavour(flavorName));
    return flavours.get(flavorName);
  }

  int totalCoffeeFlavoursMade() {
    return flavours.size();
  }
}

// Order is the context of the CoffeeFlavour flyweight.
class Order {
  private final int tableNumber;
  private final CoffeeFlavour flavour;

  Order(final int tableNumber, final CoffeeFlavour flavor) {
    this.tableNumber = tableNumber;
    this.flavour = flavor;
  }

  void serve() {
    System.out.println("Serving " + flavour + " to table " + tableNumber);
  }
}

public class CoffeeShop {
  private final List<Order> orders = new Vector<Order>();
  private final Menu menu = new Menu();

  void takeOrder(final String flavourName, final int table) {
    CoffeeFlavour flavour = menu.lookup(flavourName);
    Order order = new Order(table, flavour);
    orders.add(order);
  }

  void service() {
    for (Order order : orders)
      order.serve();
  }

  String report() {
    return "\ntotal CoffeeFlavour objects made: "
        + menu.totalCoffeeFlavoursMade();
  }

  public static void main(final 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(shop.report());
  }
}

Example in Scala[edit]

/*
https://gist.github.com/pkinsky/111aee2f129c03ff1d0d
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
*/

class CoffeeFlavour(val name: String){
    override def toString = s"CoffeeFlavour($name)"
}

object CoffeeFlavour {
  import scala.collection.mutable.Map
  private val cache = Map.empty[String, CoffeeFlavour]

  def apply(name: String): CoffeeFlavour =
    cache.getOrElseUpdate(name, new CoffeeFlavour(name))

  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[edit]

# 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[edit]

Attributes can be defined for a Class instead of a Instance, in Python's. New-style classes instances store instances data on a dictionary self.__dict__. By default, accessing attributes do lookup this per-instance __dict__ and fallback to the Class attributes next. This way, a class is a kind of Flyweight container for its instances.

Although Python have no immutability, it can be emulated overwriting __setattr__ to disallow changes on the Flyweight attributes.

# Instances of CheeseBrand will be the Flyweights
class CheeseBrand(object):
    def __init__(self, brand, cost):
        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(CheeseBrand, self).__setattr__(name, value)
    

class CheeseShop(object):
    menu = {}  # Shared container to access the Flyweights
    
    def __init__(self):
        self.orders = {}  # per-instance container with private attributes

    def stock_cheese(self, brand, cost):
        cheese = CheeseBrand(brand, cost)
        self.menu[brand] = cheese   # Shared Flyweight

    def sell_cheese(self, brand, units):
        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[edit]

import Foundation

// Instances of CoffeeFlavour will be the Flyweights
struct CoffeeFlavor : CustomStringConvertible {
    var flavor: String
    var description: String { return 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 f = flavors[flavor] { return f }
        else {
            let cFlavor = CoffeeFlavor(flavor: flavor)
            flavors[flavor] = cFlavor
            return cFlavor
        }
    }
}

struct CoffeeShop {
    private var orders = [Int: CoffeeFlavor]()
    private var menu = Menu()

    mutating func takeOrder(flavor flavor: String, table: Int) {
        orders[table] = menu.lookup(flavor)
    }

    func serve() {
        for (table, flavor) in orders {
            print("Serving \(flavor) to table \(table)")
        }
    }
}

let 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[edit]

# 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

See also[edit]

References[edit]

  1. ^ Gamma, Erich; Richard Helm; Ralph Johnson; John Vlissides (1995). Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley. pp. 205–206. ISBN 0-201-63361-2. 
  2. ^ 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. 
  3. ^ 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. doi:10.1145/62083.62089. ISBN 0-89791-284-5.