Optimization Patterns

This section gathers together a few general techniques for improving performance that are so useful that they deserve specific mention. The reader may recognize some of these patterns as the core of familiar data structures, C++ language features, or hardware innovations:

  • Precomputation — Remove computation from the hot part of the program by performing it before execution arrives at the hot code — earlier in the program, at link time, compile time, or design time.

  • Lazy computation — Remove computation from some code paths by performing the computation closer to the point where it is needed.

  • Batching — Perform computation on several items together rather than one item at a time.

  • Caching — Reduce computation by saving and reusing the results of an expensive computation rather than recomputing them.

  • Sepcialization — Reduce computation by removing generality that is not used.

  • Hinting — Reduce computation by providing a hint the might improve permanence.

  • Optimizing the expected path — Test for inputs or events at run time in decreasing order of expected frequency.

  • Hashing — Compute a compact numerical summary (the hash) of a larger data structure such as a variable-length character string. The hash can stand in for the data structure in comparisons to improve performance.

  • Double-checking — Reduce computation by performing an inexpensive check, followed only if necessary by an expensive check.

Read More »

Apache Thrift architecture

The Apache Thrift Framework can be organized into five layers:

* The RPC Server Library
* RPC Service Stubs
* User-Defined Type Serialization
* The Serialization Protocol Library
* The Transport Library

Applications requiring a common way to serialize data structures for storage or messaging may need nothing more than the bottom three layers of this model.

The top two layers the Apache Thrift library of RPC servers and the IDL compiler generated service stubs, adding RPC support to the stack.

Apache Thrift is conceptually an object oriented framework, though it supports object-oriented and non-object oriented languages. The Transport, Protocol, and Server libraries are often referred to as class libraries, though they may be implemented in other ways in non-object oriented languages. The classes within the Apache Thrift libraries are typically named with a leading capital T, for example, TTransport, TProtocol, and TServer.

Read More »

Microservice Patterns – Escaping Monolithic Hell

Scale cube and micro-services

The model defines three ways to scale an application: X, Y, and Z.

X-axis scaling

X-axis scaling is a commonly to scale an application. You simple run multiple instances of the application behind a load balancer.

The load balancer distributes requests amongst the N identical instances of the application.

Z-axis scaling

Z-axis scaling also runs multiple instances of the application. However, unlike X-axis scaling, each server is responsible for only a subset of the data. The router in front of the instances uses an attribute of request to route it to the appropriate instance.

The router uses the x attribute of the request to decide select one of the N identical instances of the application. A commonly used attribute is the userId. Different users are routed to different instances of the application.

Y-axis scaling

X and Z-axis scaling improve the application's capacity and availability. Neither approach, however, solves the problem of increasing development and application complexity. To solve those problems we need to apply Y-axis scaling a.k.a. functional decomposition. Y-axis scaling splits a monolithic application into a set of services.

A service, is a mini-application that implements a set of related functionality such as order management, customer management, etc. A service is called using X-axis and Z-axis when necessary. “For example, the Order Management service is deployed as a set of load balanced service instances.”

This is my high-level definition of micro-services: an architectural style that functionally decomposes an application into a set of services. Note that this definition does not say anything about size. Instead, what matters is that each service has a focussed, cohesive set of responsibilities.

Micro-services as a form of modularity

The micro-service architecture uses services as the unit of modularity. A service has an impermeable boundary that is difficult to violate. As a result, the modularity of the application is much easier to preserve over time. There are other benefits of the micro-service architecture including the ability to deploy and scale services independently.

Each service has its own database

A key characteristic of the micro-service architecture is that the services are loosely coupled. One way this loose coupling is achieved is by each service having it's own datastore.

Now that we have defined the micro-service architecture and described some of its essential characteristics, lets look how this applies to the FTGO application.

Read More »

Sequence Modeling: Recurrent and Recursive Nets

a recurrent neural network is a neural network that is specialized fro processing a sequence of values x^{(1)}, \dots, x^{(\tau)} . Just as convolutional networks can readily scale to images with large width and height, and some convolutional networks can readily sale to images with large width an height, and some convolutional networks can process images of variable size, recurrent networks can scale to much longer sequences than would be practical for networks without sequence-based specialization.

To go from multi-layer networks to recurrent networks, we need to take advantage of the early ideas found in machine learning and statical models of the 1980s: sharing parameters across different parts of a model.

  • Parameter sharing makes it possible to extend and apply the model to examples of different forms and generalize across them.
  • If we had separate parameters for each value of the time index, we could not generalize to sequence lengths not seen during training, nor share statistical strength across different sequence lengths and across different positions in time.
  • Such sharing is particular important when a specific piece of information can occur at multiple positions within the sequence.

Suppose that we trained a feedforward network that processes sentences of fixed length. A traditional fully connected feedforward network would have separate parameters for each input feature, so ti would need to learn all of the rules of the language separately at each position in the sentence. By comparison, a recurrent neural network shares the same weights across several time steps.

A related idea is the use of convolution across a 1-D temporal sequence. This convolutional approach is the basis for time-delay neural networks.

  • The convolution operation allows a network to share parameters across time, but is shallow. The output of convolution is a sequence where each member of the output is a function fo a small number of neighboring members of the input. The idea of parameter sharing manifests in the application of the same convolution kernel at each time step.

Recurrent networks share parameters in a different way.

  • Each member of the output is produced using the same update rule applied to the previous outputs. This recurrent formulation results in the sharing of parameters through a very deep computational graph.

This chapter extends the idea of a computational graph to include cycles. These cycles represent the influence of the present value of a variable on its own value at a future time step. Such computational graphs allow us to define recurrent neural networks. We then describe many different ways to construct, train, and use recurrent neural networks.

Read More »

Autonomous Driving: Modeling and Learning Behaviors

Motion planning for dynamic environments is clearly one of the main problems that needs to be solved for effective autonomous navigation. As shown by Ref and Sharir, the general problem is NP-Hard, which explains the continued efforts to find algorithms to cope with that complexity.

A much more overlooked but equally critical aspect of the problem is motion prediction. Motion planning algorithms assume the availability of previous knowledge about how every mobile object in the environment will move, an assumption which does not hold for a vast number of situations and environments. The alternative is to predict how objects will move and to use that prediction as the input of the motion planning algorithm.

Read More »

Mastering CMake — Key Concepts

Key Concepts

Main Structures

This chapter provides an introduction not CMake's key concepts. As you start working with CMake, you. Will run into a variety of concepts such as targets, generators, and commands. In CMake, these concepts are implemented as C++ classes and are referenced in many of CMake's commands. Understanding these concepts will provide you with the working knowledge you need to create effective CMakeLists files.

Before going into detail about CMake's classes, it is worth understanding their basic relationships. At the lowest level are source files; these correspond to typical C or C++ source code files. Source files are combined int targets. A target is typically an executable or library. A directory represents a directory in the source tree and typically has a CMakeLists file and one-or-more targets associated with it. Every directory has a local generator that is responsible for generating the Makefiles or project for the directory. All of the local generators share a common global generator that oversees the build process. Finally, the global generator is created and driven by the cmake class itself.

Figure 1 shows the basic structure of CMake. We will now consider CMake's concepts in a bit more detail. CMake's execution begins by creating an instance of the make class and passing command line arguments to it. This class manages the overall configuration process and holds information that is global to the build process, such as the cache values. One of the first things the cake class does is to create the correct global generator based on the user's selection of which generator to use (such as Visual Studio 10, Borland Makefiles, or UNIX Makefiles). At this point, the cmake class passes control to the global generator it read by invoking the configure and generate methods.


The global generator is responsible for managing the configuration and generation of all the Makefiles (or project files) for a project. In practice, most of the work is actually done by local generators that are created by the global generator. One local generator is created for each directory of the project that is processed. So while a project will have only one global generator, it may have many local generators. For example, under Visual Studio 7, the global generator creates a solution file for the entire project while the local generators create a project file for each target in their directory.

Read More »

Autonomous Driving: Context and the State-of-the-Art

In this section the state-of-the-art in Intelligent Vehicles will be presented from a vehicle navigation perspective as these achieve autonomous navigation capabilities. The section is structured as follows:

  1. Motivation: The motivation to this ongoing transformation of modern vehicles are presented in terms of usage, safety and external factors such as fossil-fuel constraints, pollution.
  2. Vehicle navigation functions: The state-of-the art review is formulated in terms of vehicle navigation functions to focus the section on the machine intelligence and decision-making processes that are being developed and introduced to transform modern vehicles into connected platforms with autonomous navigation capabilities. It addresses the issues of autonomy, driver needs and communications. That is, it formulates the vehicle onboard intelligence as a navigation problem and thus defines the functional needs for vehicles t demonstrate autonomous navigation capabilities.
  3. Related vehicle techniques: Current developments have been classified under three different perspectives:

    1. Driver Centric addresses systems that seek to increase the situational awareness of drivers providing different types of driving assistance systems that include the driver in the decision making process.
    2. Network Centric addresses the use of wireless networks enabling the sharing of information among vehicles and in the infrastructure creating awareness of the drivers and machines beyond what standalone vehicle systems could observe.
    3. Vehicle Centric addresses systems that seek to convert vehicles into fully autonomous vehicles, with the driver outside the control loop.

    These different perspectives will be defined, presenting current developments in academia and industry.

  4. Future developments: A perspective on future developments and how these technologies could be adopted taking account cost, legal and societal constraints will be provided.

Read More »

Creational Patterns

Creational design patterns abstract the instantiation process. They help make a system independent of how its objects are created, composed, and represented. A class creational pattern uses inheritance to vary the class that’s instantiated, whereas an object creational pattern will delegate instantiation to another object.

Creational patterns become important as systems evolve to depend more on object composition than class inheritance. As that happens, emphasis shifts away from hard-coding a fixed set of behaviors toward defining a smaller set of fundamental behaviors that can be composed into any number of more complex ones. Thus creating objects with particular behaviors requires more than simply instantiating a class.

There are two recurring themes in these patterns. First, they all encapsulate knowledge about which concrete classes the system uses. Second, they hide how instances of these classes are created and put together. All the system at large knows about the objects is their interfaces as defined by abstract classes. Consequently, the creational patterns give you a lot of flexibility in what gets created, who creates it, how it gets created, and when. They let you configure a system with “product” objects that vary widely in structure and functionality. Configuration can be static (that is, specified at compile-time) or dynamic (at run-time).

Sometimes creational patterns are competitors. For example, there are cases when either Prototype (117) or Abstract Factory (87) could be used profitably. At other times they are complementary: Builder (97) can use one of the other patterns to implement which components get built. Prototype (117) can use Singleton (127) in its implementation.

Read More »

A case study: Designing a Document Editor

This chapter presents a case study in the design of a “What-You-See-Is-What-You-Get” (or “WYSIWYG”) document editor called Lexi.[1] We’ll see how design patterns capture solutions to design problems in Lexi and applications like it. By the end of this chapter you will have gained experience with eight patterns, learning them by example.

Design Problems

  1. Document structure. The choice of internal representation for the document affects nearly aspect of Lexi's design. All editing, formatting, displaying, and textual analysis will require traversing the representation. The way we organize this information will impact the design of the rest of the application.
  2. Formatting. How does Lexi actually arrange text and graphics into lines and columns? What objects are responsible for carrying out different formatting policies? How does these polices interact with the document's internal representation?
  3. Embellishing the user interface. Lexi's user interface includes scroll bars, borders, and drop shadows that embellish the WYSIWYG document interface.

  4. Supporting multiple look-and-feel standards. Lexi should adapt easily to different look-and-feel standards such as Motif and Presentation Manager (PM) without major modification.

  5. Supporting multiple window systems. Lexi's design should be as independent of the window system as possible.

  6. User operations. Users control Lexi through various user interfaces, including buttons and pull-down menus. The functionality behind these interfaces is shattered throughout the objects in the application.

  7. Spelling checking and hyphenation. How does Lexi support analytical operations such as checking for misspelled words and determining hyphenation points?

Read More »

Effective Python (26) — Use multiple inheritance only for mix-in utility classes

Python is an object-oriented language with built-in facilities for making multiple inheritance tractable. However, it's better to avoid multiple inheritance altogether.

If you find you yourself desiring the convenience and encapsulation that comes with multiple inheritance, considering writing a mix-in instead. A mix-in is a small class that only defines a set of additional methods that a class should provide. Mix-in classes don't define their own instance attributes nor require their __init__ constructor to be called.

Writing mix-ins is easy because Python makes it trivial to inspect the current state of any object regardless of its type. Dynamic inspection lets you write generic functionality a single time, in a mix-in, that can be applied to many other classes. Mix-ins can be composed and layered to minimize repetitive code and maximize reuse.

For example, say you want the ability to convert a Python object from its in-memory representation to a dictionary that's ready for serialization. Why not write this functionality generically so you can use it with all of your classes?

class ToDictMixin(object):
    def to_dict(self):
        return self._traverse_dict(self.__dict__)

The implementation details are straightforward and rely on dynamic attribute access using hasattr, dynamic type inspection with isinstance, and accessing the instance dictionary __dict__.

def _traverse_dict(self, instance_dict):
    output = {}
    for key, value in instance_dict.items():
        output[key] = self._traverse(key, value)
    return output

def _traverse(self, key, value):
    if isinstance(value, ToDictMixMin):
        return value.to_dict()
    elif isinstance(value, dict):
        return self.__traverse_dict(value)
    elif isinstance(value, list):
        return [self._traverse(key, i) for i in value]
    elif isinstance(value, '__dict__'):
        return self._traverse_dict(value.__dict__)
        return value

Here, I define an example class that uses the mix-in to make a dictionary representation of a binary tree:

class BinaryTree(ToDictMixin):
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

Translating a large number of related Python objects into a dictionary becomes easy.

tree = BinaryTree(10,
  left=BinaryTree(7, right=BinaryTree(9)),
  right=BinaryTree(13, left=BinaryTree(11)))

{'left': {'left': None,
         'right': {'left':None, 'right':None, 'value':9},
         'value': 7},
 'right': {'left': {'left': None, 'right':None, 'value': 11},
          'right': None,
          'value': 13},
 'value': 10}

The best part about mix-ins is that you can make their generic functionality pluggable so behaviors can be overridden when required. For example, here I define a subclass of BinaryTree that holds a reference to its parent. This circular reference would cause the default implementation of ToDictMixin.to_dict to loop forever.

class BinaryTreeWithParent(BinaryTree):
    def __init__(self, value, left=None,
                right=None, parent=None):
        super().__init__(value, left=left, right=right)
        self.parent = parent

The solution is to override the ToDictMixin._traverse method in the BinaryTreeWithParent class to only process values that matter, preventing cycles encountered by the mix-in. Here, I override the _traverse method to not traverse the parent and just insert its numerical value:

def _traverse(self, key, value):
    if (isinstance(value, BinaryTreeParent) and
          key == 'parent'):
        return value.value # Prevent cycles
        return super()._traverse(key, value)

Calling BinaryTreeWithParent.to_dit will work without issue because the circular referencing properties aren't followed.

root = BinaryTreeWithParent(10)
root.left = BinaryTreeWithParent(7, parent=root)
root.left.right = BinaryWithParent(9, parent=root.left)

{'left': {'left': None,
         'parent': 10,
         'right': {'left': None,
                  'parent': 7,
                  'right': None,
                  'value': 9},
         'value': 7},
'parent': None,
'right': None,
'value': 10}

By defining BinaryTreeWithParent._traverse, I've also enabled any class that has an attribute of type BinaryTreeWithParent to automatically work with ToDictMixin.

class NamedSubTree(ToDictMixin):
    def __init__(self, name, tree_with_parent):
        self.name = name
        self.tree_with_parent = tree_with_parent
    my_tree = NamedSubTree('foobar', root.left.right)
    print(my_tree.to_dict()) # No inifinite loop
{'name': 'foobar',
'tree_with_parent': {'left': None,
                    'parent': 7,
                    'right': None,
                    'value': 9}}

Mix-ins can also be composed together. For example, say you want a mix-in provides generic JSON serialization for any class. You can do this by assuming that a class provides a to_dict method (which may or may not be provided by the ToDictMixin class).

class JsonMixin(object):
    def from_json(cls, data):
        kwargs = json.loads(data)
        return cls(**kwargs)
    def to_json(self):
        return json.dumps(self.to_dict())

Note how the JsonMixin class defines both instance methods and class methods. Mix-ins let you add either kind of behavior. In this example, the only requirements of the JsonMixin are that the class has a to_dict method and its __init__ method takes keyword arguments.

This mix-in makes it simple to create hierarchies of utility classes that can be serialized to and from JSON with little boilerplate. For example, here I have a hierarchy of data classes representing parts of a datacenter topology:

class DatacenterRack(ToDictMixin, JsonMixin):
    def __init__(self, switch=None, machines=None):
        self.switch = Switch(**switch)
        self.machines = [
          Machine(**kwargs) for kwargs in machines]

class Switch(ToDictMixin, JsonMixin):
    # ...
class Machine(ToDicMixin, JsonMixin):
    # ...

Serializing these classes to and from JSON is simple. Here, I verify that the data is able to be sent round-trip through serializing and deserializing:

serialized = """{
    "switch": {"ports": 5, "speed": 1e9},
    "machines": [
        {"cores": 8, "ram": 32e9, "disk": 5e12},
        {"cores": 4, "ram": 16e9, "disk": 1e12},
        {"cores": 2, "ram": 4e9, "disk": 500e9}

deserialized = DatacenterRack.from_json(serialized)
roundtrip = deserialized.to_json()
assert json.loads(serialized) == json.loads(roundtrip)

When you use mix-ins like this, it's also fine if the class already inherits from JsonMixin higher up in the object hierarchy. The resulting class will behave the same way.