Design Patterns

1. Patterns
   1. Reusable ideas for software design
      1. Popularized in 1995 book by the "Gang of Four", Gamma, Helm, Johnson, &Vlissides, "Design Patterns: Elements of Reusable Object-Oriented Software"
      2. Many follow-on (especially domain-specific) patterns
      3. Game Programming Patterns
      4. Concurrency Patterns
   2. Distrusted by some software developers due to blind (mis)use
   3. Some of global use, some workaround for C++ deficiencies
   4. May introduce unnecessary computation
      1. Many Data Oriented Programming proponents advocate performance over design religion
      2. Knuth: "Premature optimization is the root of all evil"
         • Full quote: "Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."
      3. Write once run many, so optimize for the execution time
         1. Do not treat fellow programmers as the enemy
         2. Things that prevent incorrect usage at compile time are good
         3. Things that spend execution time to prevent misuse are questionable
   5. None the less... patterns ARE useful when appropriate.
2. Classic patterns (23 from Gang of Four)
   1. Creation
      1. Abstract Factory
         1. Function to generate polymorphic object(s)
         2. Allows choice at run-time
            • Rather than

              Image image(filename);

              use

              Image *image = LoadImage(filename);

         3. Common for virtual/abstract classes
            • Decide sub-class to create, return pointer to base
         4. Works great with DOD
            1. Populate tables instead of object
            2. DOD version of constructor
      2. Builder
         1. Avoid huge number of constructors or constructor options with a builder object
            1. Builder has member functions to add construction data
            2. Builder then builds final class
         2. Example:

            TexBuilder texbuilder;
            texbuilder.size(512,512);
            texbuilder.depth(3);
            texbuilder.colormodel(TexBuilder::RGB);
            Texture tex = texbuilder.make();

         3. Vulkan API example (struct vs. member functions):

            VkDynamicDsStateCreateInfo dsInfo = { VK_STRUCTURE_TYPE_DYNAMIC_DS_STATE_CREATE_INFO };
            dsInfo.minDepth = 0.0f;
            dsInfo.maxDepth = 1.0f;
            dsInfo.stencilReadMask = dsInfo.stencilWriteMask = 0xff;
            result = vkCreateDynamicDepthStencilState(m_device, &dsInfo, &m_dynstate.ds);

         4. Builder member functions = add component table
            • Don't need explicit Builder class, or replace with component addition
      3. Factory Method
         1. Method in subclass decides what to instantiate
         2. Example:
            1. DXRenderer and GLRenderer derived from Renderer
            2. DXTexture and GLTexture derived from Texture

               Renderer *renderer = new DXRenderer;
               Texture *tex = renderer.mkTexture(512,512,RGB);

         3. Compare to abstract factory, where factory is global function
         4. DOD equivalent:
            1. Function that adds entries to tables (as with abstract factory)
            2. Or function that adds entries to a creation table
               • Then use transform to insert into component tables
            3. Avoid virtual indirection!
      4. Prototype
         1. Clone prototype to create new objects
         2. Standard implementation: pure virtual clone function

            Character *goblin = protogoblin->clone();
            // maybe modify goblin to specialize

         3. Book author doesn't like: doesn't want non-active data in tables
         4. May be possible to do similar construction with memento
         5. Can also clone by entity ID
            • Unity entity system allows this, super handy for spawning
      5. Singleton
         1. This is a global variable for people who think the word "global" is bad
         2. Guarantees one and only one instance
         3. Lazy initialization to avoid C++ problems with global constructor timing
         4. Singleton access class constructs if not there yet

            Singleton::instance() {
                if (! Singleton::ptr) Singleton::ptr = new Singleton;
                return Singleton::ptr;
            }

            or

            Singleton::instance() {
                // godbolt.org: acquire guard, check status, init, release guard
                static Singleton *ptr = new Singleton;
                return ptr;
            }

         5. DOD:
            1. Branch check on *every* access???
            2. Better to just use global
            3. Separate init from constructor to avoid construction order
            4. Plan construction, don't be lazy
   2. Structural
      1. Adapter
         1. Glue code between incompatible interfaces

            class Adapter {
                Target target;
                method() { target.method(); }
            };

            or, for run-time adaptation

            class Adapter {
                virtual method() = 0;
            };
            class Specialization : public Adapter {
                Target target;
                virtual method() { target.method(); }
            }

         2. DOD: Transform iterator
            1. If target library is one element at a time: call target library for each entity
            2. If target library takes table: transform to new tables
            3. Plan and create arrays to match
            4. E.g. graphics API takes array of vertices, so use array of vertices
               • Though graphics APIs often takes array and stride to adapt
         3. When using on object code, prefer non-virtual form
            • Which decide the same way every time. Don't do that.
      2. Bridge
         1. Decouple interface from implementation
            1. Similar to Adapter, but with interface and implementation defined together
         2. C++ pimpl
            • Only member functions need to know what implementation is

              class Interface {
              public:
                  // methods
              private:
                  class Implementation *pimpl;
              };

         3. Abstract bridge, concrete implementation
            • Virtual implementation for compile-time choice
         4. Data oriented design options
            1. Message/event subscription, don't need virtual functions
            2. Common interface & compile-time or link-time choice
            3. Shared library
      3. Composite
         1. Treat composition of objects as a object

            class Node {
                Node *left, *right;
                virtual void render() { 
                    left->render(); 
                    right->render(); 
                }
            };
            class GeoNode : public Node {
                Geometry geo;
                virtual void render() {
                    geo.render();
                }
            };

         2. Author makes it sound harder than it is
         3. Components allow polymorphism
         4. Can use table composition for grouping behavior
      4. Decorator
         1. Wrapper around class to add functionality
         2. Allows stacking, where inheritance does not
         3. Example:

            class Base {};
            class Decorator : Base {}
            class Decorator1 : Decorator {
                Base *base;
                virtual method() { addStuff(); base->method(); }
            }
            class Decorator2 : Decorator {
                Base *base;
                virtual method() { otherStuff(); base->method(); }
            }

         4. Virtual extension of decorator w/ pointer to base and extended behavior
         5. Use components
      5. Facade
         1. Simplified interface to complex code (single interface to many parts)
         2. Doesn't need to be about objects (see GLFW/GLUT)
         3. Works just as well for data oriented
      6. Flyweight
         1. Share data to reduce memory use & allow large numbers of objects
         2. Traditionally pointer to shared state
         3. Gang of four example, character glyph & font drawing
            1. One object per character in font pool
            2. Text refers to font objects from pool
            3. But pointers & not char indices???
         4. Use Components and sub-entities
      7. Proxy
         1. Interface object (similar to Facade, Bridge & Adapter)
         2. Uses for proxies
            1. Proxy to alternate library
            2. Remote proxy over network
            3. Defer accesses to object (virtual proxy)
            4. Protection proxy to limit access
         3. Proxy for level of detail
            • Covered in LOD chapter of book
              1. Transform from LOD object to finer grained objects on view
              2. Transform back with distance
   3. Behavioral
      1. Chain of responsibility
         1. Dispatcher/handler functions (e.g. return true if handled)

            int webRequest(mg_connection *conn, int event) {
                if (check conn->uri) {
                    // process
                    return MG_TRUE;
                }
                // standard file
                return MG_FALSE;
            }

         2. Common implementation for message systems
         3. Pass message to list of subscribed functions, stop if handled
         4. Parallelize better if ability to stop on handled is removed
            • Generate new message for responsibility handoff
      2. Command
         1. Command class w/ virtual execute

            class Command {
            public:
                virtual void run() = 0;
            };
            
            class DeleteCmd : public Command {
            public:
                virtual void run();
            private:
                // command data
            };

         2. Common implementation for message systems
         3. Useful for replay, undo, queue and decouple
      3. Interpreter
         1. Described as implementation of interpreter
            • Allows easy changes and run-time modification of behavior
         2. Important thing is parse & interpret code
         3. May be easier with bytecode as input (see Game Programming Patterns)
         4. Many games use Lua, Python, C#, or similar for this purpose
      4. Iterator
         1. Class encapsulating data structure traversal state
         2. This is what C++ STL does
         3. With data oriented, mostly replaced by integers and loops over dense tables
      5. Mediator
         1. Glue between classes, especially as interfaces change
            1. Client calls mediator, mediator calls colleagues
            2. Colleagues may call back into mediator
         2. Abstract mediator allows changes, concrete if just one mediator
         3. Decoupling between client and implementation classes & between implementation classes
         4. Messages serve as mediators
      6. Memento
         1. Encapsulation of enough state to restore
            1. Content of state is not exposed
            2. Only need enough state to reconstruct object
            3. Can use for undo
         2. Serialization
         3. Partial serialization to memory for later restore (LOD chapter)
      7. Observer
         1. Object keeps list of observers, notifies them of changes
         2. Notification typically by callback functions
         3. Publish and subscribe to message is instance of observer pattern
      8. State
         1. State in class to set mode, changing behavior
         2. E.g. current drawing tool
         3. Author says no with many entities, but...
         4. Data tables = state, and behavior can be determined by tables
         5. Can move to sub-table for state behavior (e.g. active)
      9. Strategy
         1. Interchangeable algorithms with common interface.
         2. Author says nothing...
         3. Though GOF offers template as an alternative to virtual functions
         4. Definitely reduces conditionals (vs. testing in code)
      10. Template method
          1. Define overall method, but allow subclasses to replace steps
          2. Virtual member functions for operations
          3. Example: varying image data types
          4. About operations more than data, so can still apply
      11. Visitor
          1. Allow extension of objects and operations on those objects
          2. Open Scene Graph example
             1. Tree of Nodes and classes derived from node, Visitor derived from NodeVisitor
             2. Node classes implement virtual accept(NodeVisitor&)
             3. Visitor implements virtual apply(Node&) and apply(other&)
             4. Node traversal calls accept(NodeVisitor)
             5. virtual resolves to myNode::accept(NodeVisitor)
             6. myNode::accept calls NodeVisitor::apply(myNode)
             7. virtual resolves to myVisitor::apply(myNode)
          3. Double dispatch results in call specific to both subclasses
             1. Only visitor class needs to know about both subclasses
             2. Visitor class can provide fallback for Node that always works
          4. Problem 1: doubled virtual
          5. Problem 2: visitor with state forces traversal order
3. Data oriented patterns
   1. A to B transform
      1. Cache friendly for A and B
         1. Stateless so order of transform doesn't matter
         2. Allows efficient decoupled parallelization
         3. Best when accessing all elements of A
            • Parallelize in chunks, not interleaved
   2. Update transform(*)
      1. Author lumps with A to B
      2. In place A to A
   3. Generative transform
      1. Code to list
      2. Should still be stateless, parallelizable
      3. Should still fill B in order for cache
   4. Action transform(*)
      1. Complete table: A to action
      2. Should still be stateless, parallelizable
      3. Should still access A in order for cache
   5. Sorted table
      1. Need table to be sorted
      2. Sort after updates
         • If many updates then several uses
      3. Sort on use
         1. If many updates to one use
         2. Especially if don't know when updates are done
      4. Sort on update
         1. Likely bubble sort
         2. If a few updates or update/use ratio is similar
      5. Sorted indices
         1. Index list for sorted order may be cheaper to keep sorted
         2. Intermediate updates can dereference through index list
         3. Apply transform to restore to true sorted order
   6. Multi-sorted table
      1. Multiple sorted representations on different keys
      2. Can sort on primary key
      3. Others will need index and indirection
      4. Like database secondary keys
   7. Gatherer
      1. AKA Reduce
      2. Run on data (or selected set, see Map Reduce)
      3. Best if possible to implement in parallel sub-chunks
      4. If output order doesn't matter, can use lockless output buffer
      5. May want output buffer per thread followed by merge (e.g. Vulkan command buffers)
   8. Tasker
      1. Parallel for operation
      2. Break table transform into independent parallel tasks
      3. Do by blocks for cache coherence and to reduce contention
   9. Dispatcher
      1. Rather than run code during transform, create table of work
      2. Later, process dense dispatch table
      3. Trading cache conflicts during initial processing for double access of dispatch table
      4. Relying somewhat on dispatch table prefetching to make efficient
      5. May be able to reduce conditionals