Chapter 35

Flyweight

Thousands of objects carry the same few values. Flyweight keeps one object per value and shares it among every use.

Some programs need fine-grained objects in enormous numbers: the characters in a document, the tiles in a game map, or the strings in a compiler’s symbol table. The uses of such objects far outnumber their distinct values. Sharing replaces the many objects with one object per distinct value, which every use references.

Two ideas make sharing work.

First, split each object’s state in two. Intrinsic state belongs to the value and is identical across every use, so it can live in the shared object. Extrinsic state varies per use, so it must live outside, where each use supplies it. Second, construct every object through a factory that returns the existing instance for a given value.

Sharing one object under many names is safe when the object stays the same for everyone, so a flyweight must be immutable.

Python Uses Flyweights

CPython creates small integers once and shares them:

# small_integer_flyweights.py
low, low2 = int("256"), int("256")
high, high2 = int("100000"), int("100000")
print(low is low2, high is high2)
#: True False

Both int("256") calls return the same cached object. Each int("100000") call builds a fresh one. The cache covers a set range of values chosen at CPython build time. The range usually quoted is -5 through 256, but each build picks its own range. The CPython build this book uses caches up to 1024, so the listing uses 100000 rather than 257 for the fresh object.

The listing parses each value from a string because the compiler pools equal constants within one code object. With literals, high, high2 = 100000, 100000 makes high is high2 print True. That sharing comes from the pooling, not from the integer cache. Parsing at runtime builds the integer after compilation, so any sharing that remains comes from the cache. Because the result of is depends on details like constant pooling, Python emits a SyntaxWarning when a literal is an operand of is, as in high is 100000.

String interning keeps one copy of each distinct string in a pool. CPython interns identifier-like string constants automatically. sys.intern() adds any string to the pool, or returns the pooled copy if one exists:

# string_interning.py
from sys import intern

joined = "".join(["fly", "weight"])
joined2 = "".join(["fly", "weight"])
print(joined == joined2, joined is joined2)
#: True False
print(intern(joined) is intern(joined2))
#: True

CPython’s == on two strings checks identity before it compares characters. For interned strings, equal means identical, so equal interned strings compare in one step.

The small-integer cache and string interning are CPython implementation details, not language guarantees. Write code that works on any Python implementation, but notice that both keep one shared object per distinct value.

Intrinsic and Extrinsic State

A map can hold millions of cells, but only a handful of tile kinds. Here, the handful is grass, water, and rock. A first design stores every attribute of a cell in the cell’s own object, its position included:

# unshared_cells.py
from record import record

@record
class Cell:
    symbol: str
    name: str
    walkable: bool
    row: int
    col: int

left = Cell(".", "grass", True, 0, 0)
right = Cell(".", "grass", True, 0, 1)
print(left == right)
#: False

The two grass cells differ in col alone, and that difference makes them different values. No factory can hand one object to both cells, because each Cell holds one position. Every cell in the grid is a distinct value, so the map needs one object per cell.

Sharing starts by moving the position out. The tile’s symbol, name, and walkability are intrinsic. Every grass cell agrees on them, so they go in a record. The tile’s position is extrinsic. It is the cell’s coordinates in the grid, so it stays out of the Tile object. An operation that needs the position takes it as an argument.

The factory is tile(), a constructor function under functools.cache. @cache stores each result under its argument, so every call with the same symbol returns the object the first call built.

Every water cell in the grid is the same Tile object

# tile_map.py
from functools import cache
from typing import Final, Literal
from record import record

type Symbol = Literal[".", "~", "#"]
type TileSpec = tuple[str, bool]

@record
class Tile:
    symbol: Symbol
    name: str
    walkable: bool

    def label(self, row: int, col: int) -> str:
        return f"{self.name} at ({row}, {col})"

SPECS: Final[dict[Symbol, TileSpec]] = {
    ".": ("grass", True),
    "~": ("water", False),
    "#": ("rock", False),
}

@cache
def tile(symbol: Symbol) -> Tile:
    name, walkable = SPECS[symbol]
    return Tile(symbol, name, walkable)

def to_symbol(char: str) -> Symbol:
    if char not in SPECS:
        raise KeyError(char)
    return char

def parse_map(text: str) -> list[list[Tile]]:
    return [[tile(to_symbol(char)) for char in line]
            for line in text.split()]

# tile_map_demo.py
from tile_map import parse_map

field = parse_map("""
    ..~~..
    ..~~.#
    ......
    ##..~~
""")
cells = [*row for row in field]
print(len(cells), len({id(t) for t in cells}))
#: 24 3
print(field[0][2] is field[3][5])
#: True
print(field[0][2].label(0, 2))
#: water at (0, 2)
print(field[3][5].label(3, 5))
#: water at (3, 5)

The twenty-four cells share three Tile objects. Because @cache returns the same Tile for the same symbol every time, the object count stays at the number of tile kinds however large the grid grows. The listing shows the object count, not the memory behind it (see exercise 2).

[*row for row in field] uses comprehension unpacking to flatten the grid into one list of cells.

The listing counts id(t) rather than len(set(cells)) on purpose. Because Tile is a record, its generated __eq__() compares field values. A set of cells therefore collapses to three with or without sharing. Only identity proves sharing.

The two label() calls in tile_map_demo.py go to one object, the shared water tile, and get two answers, because each caller passes in the position. The grid holds each cell’s position by where it stores the reference. Asking “is the cell at row 1, column 5 walkable?” is field[1][5].walkable, with the asker supplying the coordinates.

Typing the Symbol Set

Symbol lists the closed set of valid map characters, so Tile.symbol and every key of SPECS must be one of those characters. If you add a kind to SPECS and leave Symbol as it is, the type checker rejects the SPECS assignment, because the new key is not a Symbol.

tile() declares its parameter a Symbol, but callers call the wrapper that @cache returns. The wrapper’s signature keeps the return type and drops the parameter type. The decorated tile is a functools._lru_cache_wrapper, whose call accepts any hashable arguments. The type checker therefore accepts tile("?"). The call then raises a KeyError at runtime when it indexes SPECS. That leaves to_symbol() as the boundary, the one function that takes a str and returns a Symbol.

The type checker narrows on the membership guard in to_symbol(). SPECS has key type Symbol, so past the guard char is a Symbol, and return char satisfies the declared return type as written.

The narrowing proves what a cast() asserts. Prefer a guard that lets the type checker narrow. Keep cast() for the cases where no guard exists, because the type checker accepts whatever a cast() asserts.

The test file confirms that:

tile() returns one object per symbol and different objects for different symbols.
A parsed map shares one Tile among the cells of each kind.
to_symbol() raises a KeyError for a character outside SPECS.
A direct Tile(...) call builds an object equal to the pooled tile and distinct from it.

# test_tile_map.py
import pytest
from tile_map import Tile, parse_map, tile, to_symbol

def test_one_object_per_symbol() -> None:
    assert tile(".") is tile(".")
    assert tile(".") is not tile("#")

def test_map_shares_tiles() -> None:
    field = parse_map("..\n~~")
    assert field[0][0] is field[0][1]
    assert field[1][0] is field[1][1]
    assert field[0][0] is not field[1][0]

def test_to_symbol_raises_key_error() -> None:
    with pytest.raises(KeyError):
        to_symbol("?")

def test_direct_construction_bypasses_pool() -> None:
    bypassed = Tile("~", "water", False)
    assert bypassed == tile("~")
    assert bypassed is not tile("~")

Freezing the Shared Tile

Freezing Tile makes sharing it safe. A frozen tile keeps its values for its whole life, so every cell that shares it reads the same values on every visit.

If you replace @record with @dataclass, the pattern fails. Mutating the grass tile in one cell changes every grass cell in the map.

The freezing must cover what each field holds, too. A record blocks assignment to a field, not mutation inside one. A Tile holding a list hands the same mutable list to every cell that shares the tile. That is the shallow-freezing trap. Every field here is immutable, so the sharing is safe.

@cache is a caching decorator, but tile() uses it for a different job. A cache returns a stored result instead of computing that result again. Evicting an entry leaves the program’s results the same, because the next call rebuilds an equal result, a little more slowly. Building a Tile is fast, so tile() has little time to save. What tile() gets from @cache is identity. Every call for a symbol returns the same object. A flyweight’s factory exists for that sameness.

The figure follows tile() through tile_map_demo.py and through test_direct_construction_bypasses_pool() in test_tile_map.py:

Four steps of Flyweight: tile() builds a Tile on the first request for a symbol and keeps it, returns that same Tile on every later request, two cells pass their own positions to the one shared water Tile and get two answers, and a direct Tile() call builds a second, equal object

Steps 1 and 2 show the sameness as two requests arriving at one object. Step 3 shows why one object can serve every water cell. The position is an argument to label(), not a field of the tile. Step 4 shows a construction that goes around the factory. A Tile built by a direct call equals the shared tile but is a separate object.

The memory saving and every is comparison depend on that sameness. A factory that evicts an entry and builds a replacement leaves two uses of one value holding two objects, whereas a cache that evicts an entry runs slower and returns equal results.

Interning in the Constructor

A factory function like tile() has a visibly different name and call syntax, so a caller can see that construction goes through the factory rather than the class. If you want callers to construct objects with an ordinary class call such as Color(...), hide the pool inside __new__() instead.

Singleton builds and returns its one instance in __new__(). An interning __new__() stores each instance in a pool under its constructor arguments instead of a single constant key. A pool of singletons keyed this way is sometimes called Multiton. A Multiton’s objects can be mutable. A flyweight must be immutable, so Color is a record:

# interned_color.py
from typing import ClassVar
from record import record

type RGB = tuple[int, int, int]

@record
class Color:
    _pool: ClassVar[dict[RGB, Color]] = {}
    red: int
    green: int
    blue: int

    def __new__(cls, red: int, green: int,
                blue: int) -> Color:
        key: RGB = (red, green, blue)
        if key not in cls._pool:
            cls._pool[key] = super().__new__(cls)
        return cls._pool[key]

crimson = Color(220, 20, 60)
print(crimson is Color(220, 20, 60))
#: True
print(len(Color._pool))
#: 1

A caller writes an ordinary constructor call and receives a shared object, as with int("256").

You write the bookkeeping yourself. It must account for the way Python calls __init__() after __new__(). When __new__() returns an instance of the class, as it does here, Python calls __init__() on it, as Singleton notes. The record’s generated __init__() therefore runs at every construction, including the ones that return a pooled instance. On a new instance, that run fills in the fields, since __new__() builds a bare instance and leaves them to __init__(). On a pooled instance, the frozen record’s __init__() assigns the same three components again through object.__setattr__(), so the object stays as it was. If a field has a default_factory or __post_init__() has a side effect, the re-run repeats that factory call or that side effect on a finished object.

Because every caller that asks for the same components receives the same Color, an assignment to crimson.red would change every crimson in the program. The record’s frozen fields reject that assignment, which makes sharing a Color safe for the same reason sharing a Tile is safe.

_pool stays a plain dict with a membership test, not a defaultdict. A defaultdict calls its default_factory with no arguments. super().__new__(cls) needs the class that asked.

_pool stores each object under its components alone, and every subclass shares the one dict. The first request for a set of components builds the object, and every later request receives that object, whether Color or a subclass asks. Key the pool by (cls, red, green, blue) if you need to subclass.

The factory tile() and the interning Color differ in one guarantee. tile() shares one object among the calls that go through it. A direct Tile("~", "water", False) bypasses tile(), building a second object equal to the pooled water tile. Every Color(...) call looks in the pool first, so two Colors with the same components are the same object and is returns the same result as ==.

Write the __new__() bookkeeping when is must agree with == for every Color, or when callers must keep writing Color(...). When you need neither, a @cache factory like tile_map.py’s tile() shares one object per value with no __new__().

One more hazard from Singleton’s cached factory applies here. Every lazy check-then-insert pool races under threads. Two threads asking for the same new color can each build “the” shared object. The second store overwrites the first, and the two threads can end up holding distinct objects. @cache races the same way. Its C implementation runs the lookup, the call to your function, and the store as three separate steps, so threads that all miss on the same key each run the function and each keep their own result.

interned_color.py adds a second hazard. __new__() pools the object before __init__() fills in its fields. A constructor call runs __init__() before it returns, so every caller of Color(...) receives a complete object. Code that reads Color._pool from another thread can still find a Color whose components are unset, and reading a component then raises an AttributeError. When more than one thread uses a pool, populate the pool eagerly or guard the insert with a lock.

A Pool That Does Not Leak

Both pools built so far hold their objects forever. @cache keeps strong references to every argument and result, and Color._pool grows with every new color. A map has a handful of tile kinds and a program usually draws from a small palette, so holding them forever uses little memory. When the set of values keeps growing, as the symbols in a long-running parser do, the pool becomes a memory leak.

weakref.WeakValueDictionary fixes the leak. It is the class behind the live-instance registry. A WeakValueDictionary holds its values weakly, so it removes an entry the moment that value’s last other reference goes away:

# weak_pool.py
from dataclasses import dataclass
from typing import Final
from weakref import WeakValueDictionary

@dataclass(frozen=True, slots=True, weakref_slot=True)
class Name:
    text: str

_pool: Final[WeakValueDictionary[str, Name]] = (
    WeakValueDictionary())

def name(text: str) -> Name:
    found: Name | None = _pool.get(text)
    if found is None:
        found = Name(text)
        _pool[text] = found
    return found

if __name__ == "__main__":
    alpha = name("alpha")
    alias = name("alpha")
    print(alpha is alias, len(_pool))
    del alpha, alias
    print(len(_pool))
#: True 1
#: 0

While any reference to the Name survives, every call to name("alpha") returns that same object. When the last reference goes away, CPython’s reference counting frees the object, and the weak reference’s callback removes the pool entry. The pool guarantees sharing. Each object lives as long as a reference outside the pool holds it. sys.intern()’s pool works the same way. An interned string lives as long as a reference outside the pool holds it.

Flyweight cuts the number of objects, and slots=True cuts the size of each one, so the two are worth combining when memory matters. Tile combines them by being a record.

A weak reference needs a __weakref__ slot, and a slotted class has one only if it declares it. With slots=True alone, _pool[text] = found therefore raises a TypeError. weakref_slot=True adds that one slot and no __dict__. record() does not pass weakref_slot through, so Name writes the dataclass call in full.

functools.lru_cache(maxsize=n) bounds a pool a different way. When it holds n entries, each new entry evicts the least recently used one. That eviction turns the factory back into a cache. Requesting an evicted value builds a fresh object, equal to any surviving original and distinct from it. Two uses of one value can then hold two objects, and an is comparison between them answers False. Use lru_cache where a stored result saves recomputation, not as a flyweight factory. The weak pool releases entries and keeps the identity guarantee. An entry lives as long as something references its Name, so every request during that life returns the one Name.

The tests confirm that name() returns the live Name for a repeated text and a different object for a different text, and that the pool removes an entry once the last reference to its Name goes away:

# test_weak_pool.py
from weak_pool import _pool, name

def test_names_are_shared() -> None:
    keep = name("x")
    assert name("x") is keep
    assert name("y") is not keep

def test_pool_removes_unreferenced() -> None:
    temp = name("temp")
    assert "temp" in _pool
    del temp
    assert "temp" not in _pool

A Known Set: Enum

When you know the full set of shared values as you write the program, the class definition can build the pool. An Enum is a flyweight pool the language maintains. Python constructs each member once, at class creation. Every later lookup of a member returns that one object. Here is tile_map.py’s Tile recast as an enum, with the pool moved into the language and the member name replacing the name field:

# tile_enum.py
from enum import Enum

class Tile(Enum):
    GRASS = (".", True)
    WATER = ("~", False)
    ROCK = ("#", False)

    walkable: bool

    def __new__(cls, symbol: str, walkable: bool) -> Tile:
        member = object.__new__(cls)
        member._value_ = symbol
        member.walkable = walkable
        return member

walkable is a bare annotation, not a ClassVar. It declares a per-member attribute, the role a dataclass field plays. Here __new__() assigns the attribute, where a dataclass assigns it in a generated __init__(). __new__() runs during class creation, before the class statement binds the name Tile, so every member has its walkable by the time any code can read it. The bare annotation is enough.

Each member’s tuple goes to __new__(), which stores the walkability and assigns _value_, so the member’s value is its map symbol rather than the tuple. Enum reads _value_ to build the Tile(".") lookup table and the member’s repr(), so __new__() must assign that name rather than a name of its own such as _symbol_.

__new__(), not __init__(), must assign _value_. Enum reads _value_ as soon as __new__() returns. An __init__() that assigns _value_ runs too late. The lookup table behind Tile(".") then stays keyed by the tuples, so Tile(".") raises a ValueError. With _value_ set in __new__(), Tile(".") returns Tile.GRASS.

object.__new__(cls) builds a bare instance by going straight to object, past Tile.__new__(), so the call cannot recurse.

# tile_enum_demo.py
from tile_enum import Tile

print(Tile.GRASS is Tile["GRASS"] is Tile("."))
#: True
print(Tile.WATER.value, Tile.WATER.walkable)
#: ~ False
print([t.value for t in Tile])
#: ['.', '~', '#']

The enum version also brings iteration, exhaustive match, and a closed set of members. Tile("?") raises a ValueError, and Tile.DOOR raises an AttributeError.

When every member of Tile has a case, the type checker knows the match covers every value. If you leave a member out of a function that declares a return type, the type checker reports the missing case before the code runs:

# tile_enum_match.py
from tile_enum import Tile

# ty: function can implicitly return `None`,
# not assignable to return type `str`
def describe(tile: Tile) -> str:  # type: ignore
    match tile:
        case Tile.GRASS:
            return "grass"
        case Tile.WATER:
            return "water"

print(describe(Tile.GRASS))
#: grass

Without the # type: ignore, ty check reports:

error[invalid-return-type]: Function can implicitly return
`None`, which is not assignable to return type `str`
 --> tile_enum_match.py:6:29
  |
6 | def describe(tile: Tile) -> str:
  |                             ^^^

The function returns None implicitly for Tile.ROCK, the member the match leaves out. Adding that case clears the diagnostic.

The enum version cannot load its tile kinds at runtime. tile() reads SPECS, a dict that a program can fill from a file at runtime, while each Tile member is an assignment in the class statement.

Both designs in State Machines also use an Enum as a flyweight pool, with its members serving as shared, comparable states.

Choosing a Flyweight and Its Pool

Three questions decide whether a type is a candidate for Flyweight. First, do uses far outnumber distinct values? A map with millions of cells and three kinds of tile qualifies. A list of customer records, each one different, does not. Second, can all the extrinsic state move out of the object? If a position, an owner, or a count must live inside, every use needs its own object, as unshared_cells.py shows. Third, can you freeze what remains? Sharing a mutable object lets one use’s change appear in every use (see exercise 3).

When all three answers are yes, the remaining choice is among the four pools. Two things decide it: how much you know about the set of values, and whether callers must keep writing the constructor. If you know the set as you write the program, use an Enum and let the language hold the pool. If callers must keep writing C(...), intern in __new__() and write the bookkeeping. If the set keeps growing, use a WeakValueDictionary so the pool shrinks with the live set. Otherwise use a @cache factory.

These four answers read as an if/elif chain, but the questions behind them are independent. Because constructor syntax and leak-safety are separate questions, __new__() interning can hold its pool weakly too. Key the WeakValueDictionary on the constructor arguments the way interned_color.py keys _pool. Combine mechanisms when more than one requirement applies.

Flyweights in the Wild

Compilers and interpreters intern identifiers so that scope lookups compare pointers instead of characters. Dataframe libraries such as pandas and Polars offer categorical types. A column of a million country names stores small integer codes that index into a pool of distinct strings. Text systems share one glyph object per character and font, with each occurrence supplying its own position. In all three, memory grows with the number of distinct values, not with the number of uses. When every instance of a type comes from the pool, you can write its equality checks as is.

Exercises

Try each exercise before opening its solution.

Add door (+, walkable) and tree (T, not walkable) kinds to tile_map.py. Extend Symbol and SPECS to match, then write walkable_neighbors(field, row, col) returning the count of adjacent walkable cells. Confirm the tile pool size still equals the number of kinds, however large the map.
Use tracemalloc to measure the memory parse_map() uses on a large map, first with every cell sharing its Tile, then with @cache removed from tile() so each cell gets a new one. How does the ratio change as the map grows?
Replace @record on Tile with @dataclass and set field[0][0].walkable = False on a parsed map. Write a test that exposes the resulting bug, then restore @record.
Model chess: a frozen Piece (color, kind) and a board that is a dict mapping squares to pieces. A full opening position holds thirty-two piece references. How many Piece objects exist? How do you capture and promote?
Rewrite interned_color.py to hold its pool weakly, as weak_pool.py does, and show that building and dropping a palette of colors leaves the pool empty. Say what the rewrite gave up to get there.
Constrain red, green, and blue to 0-255 in interned_color.py. Raise ValueError from __new__() for an out-of-range component, and write a test for it.
Rewrite tile_map.py on top of tile_enum.py’s Tile, so parse_map() returns list[list[Tile]] of enum members and to_symbol() disappears. What does the type checker still catch that the Literal version caught, and what does it catch that the Literal version did not?
Make tile()’s body slow, with a time.sleep(0.05) before it builds the Tile, and call it from four threads with the same, previously unseen symbol. How many Tile objects does the run build, and how many distinct objects do the four threads hold? Fix it two ways: populate the pool eagerly at import, and guard the factory with a threading.Lock.