Flyweight pattern

Last updated
Text editors, such as LibreOffice Writer, often use the flyweight pattern. Linux-Mint-20-MATE-writer.png
Text editors, such as LibreOffice Writer, often use the flyweight pattern.

In computer programming, the flyweight software design pattern refers to an object that minimizes memory usage by sharing some of its data with other similar objects. The flyweight pattern is one of twenty-three well-known GoF design patterns . [1] These patterns promote flexible object-oriented software design, which is easier to implement, change, test, and reuse.

Contents

In other contexts, the idea of sharing data structures is called hash consing.

The term was first coined, and the idea extensively explored, by Paul Calder and Mark Linton in 1990 [2] to efficiently handle glyph information in a WYSIWYG document editor. [3] Similar techniques were already used in other systems, however, as early as 1988. [4]

Overview

The flyweight pattern is useful when dealing with a large number of objects that share simple repeated elements that would use a large amount of memory if individually embedded. It is common to hold shared data in external data structures and pass it to the objects temporarily when they are used.

A classic example are the data structures used representing characters in a word processor. Naively, each character in a document might have a glyph object containing its font outline, font metrics, and other formatting data. However, this would use hundreds or thousands of bytes of memory for each character. Instead, each character can have a reference to a glyph object shared by every instance of the same character in the document. This way, only the position of each character needs to be stored internally.

As a result, flyweight objects can: [5]

Clients can reuse Flyweight objects and pass in extrinsic state as necessary, reducing the number of physically created objects.

Structure

A sample UML class and sequence diagram for the Flyweight design pattern. W3sDesign Flyweight Design Pattern UML.jpg
A sample UML class and sequence diagram for the Flyweight design pattern.

The above UML class diagram shows:

The sequence diagram shows the following run-time interactions:

  1. The Client object calls getFlyweight(key) on the FlyweightFactory, which returns a Flyweight1 object.
  2. After calling operation(extrinsicState) on the returned Flyweight1 object, the Client again calls getFlyweight(key) on the FlyweightFactory.
  3. The FlyweightFactory returns the already-existing Flyweight1 object.

Implementation details

There are multiple ways to implement the flyweight pattern. One example is mutability: whether the objects storing extrinsic flyweight state can change.

Immutable objects are easily shared, but require creating new extrinsic objects whenever a change in state occurs. In contrast, mutable objects can share state. Mutability allows better object reuse via the caching and re-initialization of old, unused objects. Sharing is usually nonviable when state is highly variable.

Other primary concerns include retrieval (how the end-client accesses the flyweight), caching and concurrency.

Retrieval

The factory interface for creating or reusing flyweight objects is often a facade for a complex underlying system. For example, the factory interface is commonly implemented as a singleton to provide global access for creating flyweights.

Generally speaking, the retrieval algorithm begins with a request for a new object via the factory interface.

The request is typically forwarded to an appropriate cache based on what kind of object it is. If the request is fulfilled by an object in the cache, it may be reinitialized and returned. Otherwise, a new object is instantiated. If the object is partitioned into multiple extrinsic sub-components, they will be pieced together before the object is returned.

Caching

There are two ways to cache flyweight objects: maintained and unmaintained caches.

Objects with highly variable state can be cached with a FIFO structure. This structure maintains unused objects in the cache, with no need to search the cache.

In contrast, unmaintained caches have less upfront overhead: objects for the caches are initialized in bulk at compile time or startup. Once objects populate the cache, the object retrieval algorithm might have more overhead associated than the push/pop operations of a maintained cache.

When retrieving extrinsic objects with immutable state one must simply search the cache for an object with the state one desires. If no such object is found, one with that state must be initialized. When retrieving extrinsic objects with mutable state, the cache must be searched for an unused object to reinitialize if no used object is found. If there is no unused object available, a new object must be instantiated and added to the cache.

Separate caches can be used for each unique subclass of extrinsic object. Multiple caches can be optimized separately, associating a unique search algorithm with each cache. This object caching system can be encapsulated with the chain of responsibility pattern, which promotes loose coupling between components.

Concurrency

Special consideration must be taken into account 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.

To enable safe sharing between clients and threads, flyweight objects can be made into immutable value objects, where two instances are considered equal if their values are equal.

This example from C# 9 uses records [7] to create a value object representing flavours of coffee:

publicrecordCoffeeFlavours(stringflavour);

Example in C#

In this example every instance of the MyObject class uses a Pointer class to provide data.

// Defines Flyweight object that repeats itself.publicclassFlyweight{publicstringName{get;set;}publicstringLocation{get;set;}publicstringWebsite{get;set;}publicbyte[]Logo{get;set;}}publicstaticclassPointer{publicstaticreadonlyFlyweightCompany=newFlyweight{"Abc","XYZ","www.example.com"};}publicclassMyObject{publicstringName{get;set;}publicstringCompany=>Pointer.Company.Name;}

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 FlyweightsclassTenant{public:Tenant(conststd::string&name=""):m_name(name){}std::stringname()const{returnm_name;}private:std::stringm_name;};// Registry acts as a factory and cache for Tenant flyweight objectsclassRegistry{public:Registry():tenants(){}Tenant&findByName(conststd::string&name){if(!tenants.contains(name)){tenants[name]=Tenant{name};}returntenants[name];}private:std::map<std::string,Tenant>tenants;};// Apartment maps a unique tenant to their room number.classApartment{public:Apartment():m_occupants(),m_registry(){}voidaddOccupant(conststd::string&name,introom){m_occupants[room]=&m_registry.findByName(name);}voidtenants(){for(constauto&i:m_occupants){constint&room=i.first;constauto&tenant=i.second;std::cout<<tenant->name()<<" occupies room "<<room<<std::endl;}}private:std::map<int,Tenant*>m_occupants;Registrym_registry;};intmain(){Apartmentapartment;apartment.addOccupant("David",1);apartment.addOccupant("Sarah",3);apartment.addOccupant("George",2);apartment.addOccupant("Lisa",12);apartment.addOccupant("Michael",10);apartment.tenants();return0;}

Example in PHP

<?phpclassCoffeeFlavour{privatestaticarray$CACHE=[];privatefunction__construct(privatestring$name){}publicstaticfunctionintern(string$name):self{self::$CACHE[$name]??=newself($name);returnself::$CACHE[$name];}publicstaticfunctionflavoursInCache():int{returncount(self::$CACHE);}publicfunction__toString():string{return$this->name;}}classOrder{privatefunction__construct(privateCoffeeFlavour$flavour,privateint$tableNumber){}publicstaticfunctioncreate(string$flavourName,int$tableNumber):self{$flavour=CoffeeFlavour::intern($flavourName);returnnewself($flavour,$tableNumber);}publicfunction__toString():string{return"Serving {$this->flavour} to table {$this->tableNumber}";}}classCoffeeShop{privatearray$orders=[];publicfunctiontakeOrder(string$flavour,int$tableNumber){$this->orders[]=Order::create($flavour,$tableNumber);}publicfunctionservice(){print(implode(PHP_EOL,$this->orders).PHP_EOL);}}$shop=newCoffeeShop();$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();print("CoffeeFlavor objects in cache: ".CoffeeFlavour::flavoursInCache().PHP_EOL);

See also

Related Research Articles

<span class="mw-page-title-main">Abstract factory pattern</span> Software design pattern

The abstract factory pattern in software engineering is a design pattern that provides a way to create families of related objects without imposing their concrete classes, by encapsulating a group of individual factories that have a common theme without specifying their concrete classes. According to this pattern, a client software component creates a concrete implementation of the abstract factory and then uses the generic interface of the factory to create the concrete objects that are part of the family. The client does not know which concrete objects it receives from each of these internal factories, as it uses only the generic interfaces of their products. This pattern separates the details of implementation of a set of objects from their general usage and relies on object composition, as object creation is implemented in methods exposed in the factory interface.

The bridge pattern is a design pattern used in software engineering that is meant to "decouple an abstraction from its implementation so that the two can vary independently", introduced by the Gang of Four. The bridge uses encapsulation, aggregation, and can use inheritance to separate responsibilities into different classes.

In computer programming, lazy initialization is the tactic of delaying the creation of an object, the calculation of a value, or some other expensive process until the first time it is needed. It is a kind of lazy evaluation that refers specifically to the instantiation of objects or other resources.

In object oriented programming, the factory method pattern is a creational pattern that uses factory methods to deal with the problem of creating objects without having to specify the exact class of the object that will be created. This is done by creating objects by calling a factory method—either specified in an interface and implemented by child classes, or implemented in a base class and optionally overridden by derived classes—rather than by calling a constructor.

In software engineering, the composite pattern is a partitioning design pattern. The composite pattern describes a group of objects that are treated the same way as a single instance of the same type of object. The intent of a composite is to "compose" objects into tree structures to represent part-whole hierarchies. Implementing the composite pattern lets clients treat individual objects and compositions uniformly.

In object-oriented programming, the decorator pattern is a design pattern that allows behavior to be added to an individual object, dynamically, without affecting the behavior of other instances of the same class. The decorator pattern is often useful for adhering to the Single Responsibility Principle, as it allows functionality to be divided between classes with unique areas of concern as well as to the Open-Closed Principle, by allowing the functionality of a class to be extended without being modified. Decorator use can be more efficient than subclassing, because an object's behavior can be augmented without defining an entirely new object.

In object-oriented programming, the iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container's elements. The iterator pattern decouples algorithms from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled.

In software design and engineering, the observer pattern is a software design pattern in which an object, named the subject, maintains a list of its dependents, called observers, and notifies them automatically of any state changes, usually by calling one of their methods.

In object-oriented (OO) and functional programming, an immutable object is an object whose state cannot be modified after it is created. This is in contrast to a mutable object, which can be modified after it is created. In some cases, an object is considered immutable even if some internally used attributes change, but the object's state appears unchanging from an external point of view. For example, an object that uses memoization to cache the results of expensive computations could still be considered an immutable object.

A method in object-oriented programming (OOP) is a procedure associated with an object, and generally also a message. An object consists of state data and behavior; these compose an interface, which specifies how the object may be used. A method is a behavior of an object parametrized by a user.

In computer programming, a function object is a construct allowing an object to be invoked or called as if it were an ordinary function, usually with the same syntax. In some languages, particularly C++, function objects are often called functors.

In computer science, a mutator method is a method used to control changes to a variable. They are also widely known as setter methods. Often a setter is accompanied by a getter, which returns the value of the private member variable. They are also known collectively as accessors.

In computer science, object composition and object aggregation are closely related ways to combine objects or data types into more complex ones. In conversation the distinction between composition and aggregation is often ignored. Common kinds of compositions are objects used in object-oriented programming, tagged unions, sets, sequences, and various graph structures. Object compositions relate to, but are not the same as, data structures.

In computer programming, an opaque pointer is a special case of an opaque data type, a data type declared to be a pointer to a record or data structure of some unspecified type.

A class in C++ is a user-defined type or data structure declared with any of the keywords class, struct or union that has data and functions as its members whose access is governed by the three access specifiers private, protected or public. By default access to members of a C++ class declared with the keyword class is private. The private members are not accessible outside the class; they can be accessed only through member functions of the class. The public members form an interface to the class and are accessible outside the class.

The curiously recurring template pattern (CRTP) is an idiom, originally in C++, in which a class X derives from a class template instantiation using X itself as a template argument. More generally it is known as F-bound polymorphism, and it is a form of F-bounded quantification.

C++11 is a version of the ISO/IEC 14882 standard for the C++ programming language. C++11 replaced the prior version of the C++ standard, called C++03, and was later replaced by C++14. The name follows the tradition of naming language versions by the publication year of the specification, though it was formerly named C++0x because it was expected to be published before 2010.

In computer programming, variadic templates are templates that take a variable number of arguments.

In object-oriented design, the chain-of-responsibility pattern is a behavioral design pattern consisting of a source of command objects and a series of processing objects. Each processing object contains logic that defines the types of command objects that it can handle; the rest are passed to the next processing object in the chain. A mechanism also exists for adding new processing objects to the end of this chain.

This article compares the syntax for defining and instantiating an algebraic data type (ADT), sometimes also referred to as a tagged union, in various programming languages.

References

  1. ↑ 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.{{cite book}}: CS1 maint: multiple names: authors list (link)
  2. ↑ 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.
  3. ↑ Calder, Paul R.; Linton, Mark A. (October 1990). "Glyphs: Flyweight Objects for User Interfaces". Proceedings of the 3rd annual ACM SIGGRAPH symposium on User interface software and technology - UIST '90. 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.
  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.
  5. ↑ "Implementing Flyweight Patterns in Java". Developer.com. 2019-01-28. Retrieved 2021-06-12.
  6. ↑ "The Flyweight design pattern - Structure and Collaboration". w3sDesign.com. Retrieved 2017-08-12.
  7. ↑ BillWagner. "Records - C# reference". docs.microsoft.com. Retrieved 2021-06-12.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.