{"action":"created","comment":{"url":"https://api.github.com/repos/nengo/nengo/pulls/comments/87353120","pull_request_review_id":7967728,"id":87353120,"diff_hunk":"@@ -0,0 +1,969 @@\n+\"\"\"Operator graph optimizers.\"\"\"\n+\n+from collections import defaultdict\n+import logging\n+import time\n+import warnings\n+\n+import numpy as np\n+\n+from nengo.builder.neurons import SimNeurons\n+from nengo.builder import operator\n+from nengo.builder.operator import DotInc, ElementwiseInc, SlicedCopy\n+from nengo.builder.signal import Signal\n+from nengo.config import SupportRcDefaultsMixin\n+from nengo.params import BoolParam, IntParam, RcDefault\n+from nengo.utils.compat import zip_longest\n+from nengo.utils.graphs import toposort, transitive_closure\n+\n+logger = logging.getLogger(__name__)\n+\n+\n+class OpMergeOptimizer(SupportRcDefaultsMixin):\n+    \"\"\"Optimizes the operator graph by merging operators.\n+\n+    This reduces the number of iterators to iterate over in slow Python code\n+    (as opposed to fast C code) and due to the merging operations will be\n+    performed on larger chunks of sequential memory making better use of CPU\n+    caching and prefetching.\n+\n+    The optimization algorithm has a worst case complexity of O(n^2 + e) where\n+    n is the number of operators and e the number of edges in the dependency\n+    graph. In practice the run time will be much better because not all n^2\n+    pairwise combinations of operators will be evaluated. A grouping depending\n+    on the operator type and view bases will be done with dictionaries. This\n+    grouping can be done in amortized linear time and reduces the actual worst\n+    case runtime of the optimization algorithm to O(g*m^2 + e) where g is the\n+    number of groups and m the number of elements in a group. Moreover,\n+    information about memory alignment will be used to cut the inner loop short\n+    in many cases and gives a runtime much closer to linear in most cases.\n+\n+    Note that both `model` and `dg` will be changed by the `optimize` method.\n+\n+    Parameters\n+    ----------\n+    model : :class:`nengo.builder.builder.Model`\n+        Builder output to optimize.\n+    dg : dict\n+        Dict of the form {a: {b, c}} where b and c depend on a specifying the\n+        operator dependency graph of the model.\n+    \"\"\"\n+\n+    op_mergers = {}\n+\n+    enabled = BoolParam('enabled', default=True, optional=False)\n+    max_passes = IntParam('max_passes', default=None, optional=True)\n+\n+    def __init__(self, model, dg):\n+        self.enabled = RcDefault\n+        self.max_passes = RcDefault\n+\n+        self.model = model\n+        self.dg = dg\n+\n+        # Internal dict mapping Signals to Operators accessing those signals.\n+        self._sig2op = None\n+        # Internal set of Operators merged during the current optimization\n+        # pass.\n+        self._merged = None\n+\n+    @classmethod\n+    def supports_merge(cls, op_type):\n+        return op_type in cls.op_mergers\n+\n+    @classmethod\n+    def can_merge_ops(cls, op1, op2):\n+        return (\n+            type(op1) == type(op2) and\n+            type(op1) in cls.op_mergers and\n+            cls.op_mergers[type(op1)].can_merge(op1, op2))\n+\n+    @classmethod\n+    def merge_ops(cls, ops):\n+        return cls.op_mergers[type(ops[0])].merge(ops)\n+\n+    @classmethod\n+    def register_merger(cls, op_type):\n+        def register(merger):\n+            if op_type in cls.op_mergers:\n+                warnings.warn(\n+                    \"Merger for operator of type {} overwritten.\".format(\n+                        op_type))\n+            cls.op_mergers[op_type] = merger()\n+            return merger\n+        return register\n+\n+    def optimize(self):\n+        \"\"\"Perform the optimization.\"\"\"\n+        if not self.enabled:\n+            return\n+\n+        logger.info(\"Running %s ...\", self.__class__.__name__)\n+\n+        # We try first to merge operators with views only as these have a fixed\n+        # order for the memory alignment whereas operators without views could\n+        # be merged in a random order. Merging the views of operators will\n+        # propagate requirements in the memory ordering via the other\n+        # associated signals of the operator to other operators.\n+        #\n+        # Once no more operators with views can be merged, we try to merge\n+        # operators without views and then try again merging views (because\n+        # each operator merge might generate new views).\n+\n+        before, after = None, None\n+        i = 0\n+        only_merge_ops_with_view = True\n+        while only_merge_ops_with_view or after < before:\n+            if self.max_passes is not None and i >= self.max_passes:\n+                break\n+\n+            i += 1\n+            self._log_counts()\n+\n+            only_merge_ops_with_view = before is None or before != after\n+            before = len(self.dg)\n+            t_start = time.time()\n+\n+            self._perform_single_pass(only_merge_ops_with_view)\n+\n+            t_end = time.time()\n+            after = len(self.dg)\n+            logger.info(\n+                \"Pass %i [%s]: Reduced %i to %i operators in %fs.\",\n+                i, \"only views\" if only_merge_ops_with_view else \"all\",\n+                before, after, t_end - t_start)\n+\n+        self._reinitialize_model_ops(self.dg)\n+\n+    def _perform_single_pass(self, only_merge_ops_with_view):\n+        \"\"\"Perform a single optimization pass.\n+\n+        Parameters\n+        ----------\n+        only_merge_ops_with_view : bool\n+            Limits operator merges to operators with views.\n+        \"\"\"\n+        self._init_pass_helper_vars()\n+        op_replacements, sig_replacements = self._perform_merges(\n+            only_merge_ops_with_view)\n+        ops = list(op_replacements.values())\n+        self._replace_op_signals(ops, sig_replacements)\n+        self._update_dg(op_replacements)\n+        self._update_model_sigs(sig_replacements)\n+\n+    def _init_pass_helper_vars(self):\n+        \"\"\"Initializes the internal helper variables for an optimization pass.\n+        \"\"\"\n+        self._sig2op = defaultdict(list)\n+        for op in self.dg:\n+            for s in op.all_signals:\n+                self._sig2op[s].append(op)\n+        self._merged = set()\n+\n+    def _ops_by_type(self, ops):\n+        \"\"\"Returns `ops` as a dictionary sorted by type.\"\"\"\n+        by_type = defaultdict(list)\n+        for op in ops:\n+            by_type[type(op)].append(op)\n+        return by_type\n+\n+    def _log_counts(self):\n+        \"\"\"Logs for each operator type the count in the dependency graph.\"\"\"\n+        if logger.isEnabledFor(logging.DEBUG):\n+            for tp, ops in self._ops_by_type(self.dg).items():\n+                logger.debug(\"%s: %i\", tp, len(ops))\n+\n+    def _perform_merges(self, only_merge_ops_with_view):\n+        \"\"\"Go through all operators and merge them where possible.\n+\n+        Parameters\n+        ----------\n+        only_merge_ops_with_view : bool\n+            Limit merges to operators with views.\n+\n+        Returns\n+        -------\n+        op_replacements : dict\n+            Dictionary that maps from original operators to the newly merged\n+            operators. To be used to update the dependency graph.\n+        sig_replacements : dict\n+            Dictionary that maps from original signals to new signals resulting\n+            from the merges. To be used to update the signals referenced by\n+            the operators.\n+        \"\"\"\n+        step_order = toposort(self.dg)\n+        tc = transitive_closure(self.dg, step_order)\n+        by_type = self._ops_by_type(step_order)\n+\n+        op_replacements = {}\n+        sig_replacements = {}\n+\n+        # Note that the following loops will stop as soon as any operators\n+        # have been merged, so that merges are performed on at most one type\n+        # of operators. This function will be called again once the dependency\n+        # graph and signals have been updated with those merges to continue\n+        # merging other operator types.\n+\n+        # Heuristic order to reduce runtime and number of passes\n+        for tp in [ElementwiseInc, SlicedCopy, DotInc, SimNeurons]:\n+            opr, sigr = self._perform_merges_for_subset(\n+                by_type[tp], tc, only_merge_ops_with_view)\n+            op_replacements.update(opr)\n+            sig_replacements.update(sigr)\n+            del by_type[tp]  # no need to process tp again in the second loop\n+            if not only_merge_ops_with_view and len(opr) > 0:\n+                # If we're not only merging views, the memory layout changes\n+                # and non-views are turned into views. In that case we need\n+                # to update the signals the operators are referring to before\n+                # trying to merge a different type of operators. Thus, we break\n+                # the loop here (and have a similar condition in the second\n+                # loop). The updating of the signal references is done outside\n+                # of this function.\n+                break\n+\n+        # Process remaining operations\n+        for tp, subset in by_type.items():\n+            if self.supports_merge(tp) and (\n+                    only_merge_ops_with_view or len(opr) <= 0):\n+                opr, sigr = self._perform_merges_for_subset(\n+                    subset, tc, only_merge_ops_with_view)\n+                op_replacements.update(opr)\n+                sig_replacements.update(sigr)\n+            else:\n+                # If an operator type does not support merging we still need to\n+                # add the operators to op_replacements to not have them removed\n+                # from the dependency graph.\n+                op_replacements.update({op: op for op in subset})\n+\n+        sig_replacements.update(self._get_sig_view_replacements(\n+            op_replacements.values(), sig_replacements))\n+\n+        return op_replacements, sig_replacements\n+\n+    def _get_view_indices(self, op):\n+        \"\"\"Enumerates all signals of an operator and returns the indices that\n+        correspond to signal views.\"\"\"\n+        view_indices = []\n+        for idx, s in enumerate(op.all_signals):\n+            if s.is_view:\n+                view_indices.append(idx)\n+        return view_indices\n+\n+    def _mergeable(self, op1, op2, op1_view_indices, tc):\n+        \"\"\"Determines if `op1` can be merged with `op2` given that `op1`'s\n+        signals corresponding to `op1_view_indices` are views. `tc` needs to be\n+        the transitive closure of the dependency graph.\n+        \"\"\"\n+        # Ensure the operators don't form a dependency cycle and that op2\n+        # hasn't been merged with another operator yet. (Whether op1 has been\n+        # merged with another operator will be checked outside of this function\n+        # to reduce the number of checks inside the inner loop of the\n+        # optimizer.)\n+        independent = (\n+            (op1 not in tc[op2] and op2 not in tc[op1]) and\n+            op2 not in self._merged)\n+\n+        op1_sigs = op1.all_signals\n+        op2_sigs = op2.all_signals\n+\n+        # Ensure that the signal views are compatible, otherwise the operators\n+        # cannot be merged.\n+        views_match = op1_view_indices == self._get_view_indices(op2)\n+        for idx in op1_view_indices:\n+            s1 = op1_sigs[idx]\n+            s2 = op2_sigs[idx]\n+            views_match &= s1.dtype is s2.dtype\n+            views_match &= s1.base == s2.base\n+            views_match &= s1.strides == s2.strides\n+\n+        return independent and views_match and self.can_merge_ops(op1, op2)\n+\n+    def _is_memory_access_sequential(self, ops):\n+        \"\"\"Checks that the corresponding signals of the operators `ops` are all\n+        views onto a sequential piece of memory. If this is the case the views\n+        can be merged into a single view onto the same memory.\"\"\"\n+        for signals in zip(*[op.all_signals for op in ops]):\n+            if all(not s.is_view for s in signals):\n+                continue\n+            elif not all(s.is_view for s in signals):\n+                return False\n+\n+            end = signals[0].offset + signals[0].size * signals[0].itemsize\n+            for s in signals[1:]:\n+                if end != s.offset:\n+                    return False\n+                end = s.offset + s.size * s.itemsize\n+        return True\n+\n+    @staticmethod\n+    def _view_offset(op):\n+        \"\"\"Returns the offset of the first signal view of operator `op`.\n+\n+        Returns 0 if the operator has no signal views.\"\"\"\n+        for s in op.all_signals:\n+            if s.is_view:\n+                return s.offset\n+        return 0\n+\n+    @staticmethod\n+    def _view_size(op):\n+        \"\"\"Returns the size of the first signal view of operator `op`.\n+\n+        Returns 0 if the operator has no signal views.\"\"\"\n+        for s in op.all_signals:\n+            if s.is_view:\n+                return s.size * s.itemsize\n+        return 0\n+\n+    @staticmethod\n+    def _view_base(op):\n+        \"\"\"Returns the base of the first signal view of operator `op`.\n+\n+        Returns ``None`` if the operator has no signal views.\"\"\"\n+        for s in op.all_signals:\n+            if s.is_view:\n+                return s.base\n+        return None\n+\n+    def _check_sequential(self, op1, op2):\n+        \"\"\"Checks that the first signal views of `op1` and `op2` are\n+        non-overlapping and the view of `op2` starts after the view of `op1`.\n+\n+        This is similar to the `_is_memory_access_sequential`, but has some\n+        minute differences. In contrast to `_is_memory_access_sequential`, this\n+        function\n+\n+        * only checks the first view instead of all views\n+        * does not check that all signals are views\n+        * only checks two operators at a time instead of a whole list\n+        * only returns ``True`` if there is a gap between the end of the view\n+          of `op1` and the start of the view of `op2`\n+\n+        This function is only intended to give a quick indication whether the\n+        merge of `op1` and `op2` could potentially be possible to allow for an\n+        early break out of the inner loop given a list of sorted operators by\n+        the offset of their first signal view; whereas\n+        `_is_memory_access_sequential` is used for the final check that all\n+        the views match up in their memory alignment.\n+        \"\"\"\n+        return (\n+            self._view_offset(op1) + self._view_size(op1) <\n+            self._view_offset(op2))\n+\n+    def _perform_merges_for_subset(\n+            self, subset, tc, only_merge_ops_with_view=True):\n+        \"\"\"Performs operator merges for a subset of operators.\n+\n+        Parameters\n+        ----------\n+        subset : list\n+            Subset of operators.\n+        tc : dict\n+            Transitive closure of dependency graph.\n+        only_merge_ops_with_view : bool\n+            Limit merges to operators with views.\n+\n+        Returns\n+        -------\n+        op_replacements : dict\n+            Dictionary that maps from original operators to the newly merged\n+            operators. To be used to update the dependency graph.\n+        sig_replacements : dict\n+            Dictionary that maps from original signals to new signals resulting\n+            from the merges. To be used to update the signals referenced by\n+            the operators.\n+        \"\"\"\n+        op_replacements = {op: op for op in subset}\n+        sig_replacements = {}\n+        by_view = defaultdict(list)\n+\n+        # Sort by base of views\n+        for op in subset:\n+            by_view[self._view_base(op)].append(op)\n+\n+        if only_merge_ops_with_view and None in by_view:\n+            del by_view[None]\n+\n+        for view_subset in by_view.values():\n+            if len(view_subset) > 1:\n+                self._perform_merges_for_view_subset(\n+                    view_subset, tc, op_replacements, sig_replacements)\n+\n+        return op_replacements, sig_replacements\n+\n+    def _perform_merges_for_view_subset(\n+            self, subset, tc, op_replacements, sig_replacements):\n+        \"\"\"Perform merges for a subset of operators with the same view base.\n+\n+        Parameters\n+        ----------\n+        subset : list\n+            Subset of operators. These need to have the same view base (can be\n+            None if it is None for all) for their first signal in\n+            `all_signals`.\n+        tc : dict\n+            Transitive closure of dependency graph.\n+        only_merge_ops_with_view : bool\n+            Limit merges to operators with views.\n+        op_replacements : dict\n+            Dictionary that maps from original operators to the newly merged\n+            operators. To be used to update the dependency graph. This dict\n+            will be updated by this function.\n+        sig_replacements : dict\n+            Dictionary that maps from original signals to new signals resulting\n+            from the merges. To be used to update the signals referenced by\n+            the operators. This dict will be updated by this function.\n+        \"\"\"\n+        view_indices = []\n+        # Sort to have sequential memory.\n+        offsets = np.array([self._view_offset(op) for op in subset])\n+        sort_indices = np.argsort(offsets)\n+        offsets = offsets[sort_indices]\n+        sorted_subset = [subset[i] for i in sort_indices]\n+\n+        for i, op1 in enumerate(sorted_subset):\n+            if op1 in self._merged:\n+                # Cannot merge merged operator again until dependency graph\n+                # has been updated (happens outside of this function).\n+                continue\n+\n+            view_indices = self._get_view_indices(op1)\n+\n+            # Find operators that can be merged.\n+            merge = [op1]\n+            # For a merge to be possible the view of the next operator has to\n+            # start where the view of op1 ends. Because we have sorted the\n+            # operators by the start of their views we can do a binary search\n+            # and potentially skip a number of operators at the beginning.\n+            start = np.searchsorted(\n+                offsets, offsets[i] + self._view_size(op1), side='left')\n+            for op2 in sorted_subset[start:]:\n+                can_merge = (\n+                    op2 not in self._merged and\n+                    self._mergeable(merge[-1], op2, view_indices, tc) and\n+                    self._is_memory_access_sequential([merge[-1], op2]))\n+                if can_merge:\n+                    merge.append(op2)\n+                elif self._check_sequential(merge[-1], op2):\n+                    # If this check is true the view of op2 does not\n+                    # immediately follow the view of the operators being\n+                    # merged. Because we iterate over the operators sorted by\n+                    # view offset there will be a gap between the end of the\n+                    # operators being merged and all remaining operators to\n+                    # loop over. With such a gap a merge is never possible and\n+                    # we can cut the loop short.\n+                    break\n+\n+            if len(merge) > 1:\n+                self._merge(merge, op_replacements, sig_replacements)\n+\n+        return op_replacements, sig_replacements\n+\n+    def _merge(self, merge, op_replacements, sig_replacements):\n+        \"\"\"Merges the operators in `merge` and updates `op_replacements` and\n+        `sig_replacements` with the required replacements of operators and\n+        signals.\n+\n+        It will also update the internal list of merged operators to prevent\n+        further merges on the same operators before all required operators and\n+        signals have been replaced.\n+        \"\"\"\n+        merged_op, merged_sig = self.merge_ops(merge)\n+        self._merged.update(merge)\n+        for op in merge:\n+            op_replacements[op] = merged_op\n+            # Mark all operators referencing the same signals as merged\n+            # (even though they are not) to prevent them from getting\n+            # merged before their signals have been updated.\n+            for s in op.all_signals:\n+                self._merged.update(self._sig2op[s])\n+        sig_replacements.update(merged_sig)\n+\n+    def _update_dg(self, op_replacements):\n+        \"\"\"Updates the dependency graph.\n+\n+        This involves doing all operator replacements in `op_replacements` and\n+        ensuring that dependencies are preserved.\n+        \"\"\"\n+        dg = {}\n+        for op in op_replacements:\n+            if op_replacements[op] not in dg:\n+                dg[op_replacements[op]] = set()\n+            for x in self.dg[op]:\n+                dg[op_replacements[op]].add(op_replacements[x])\n+        self.dg.clear()\n+        self.dg.update(dg)\n+\n+    @staticmethod\n+    def _map_onto_op_signals(fn, ops):\n+        \"\"\"Maps function `fn` on all signals of all operators in the sequence\n+        `ops`.\n+        \"\"\"\n+        for op in ops:\n+            for key in dir(op):\n+                sig = getattr(op, key)\n+                if isinstance(sig, Signal):\n+                    setattr(op, key, fn(sig))\n+\n+            op.sets = [fn(s) for s in op.sets]\n+            op.incs = [fn(s) for s in op.incs]\n+            op.reads = [fn(s) for s in op.reads]\n+            op.updates = [fn(s) for s in op.updates]\n+\n+    @classmethod\n+    def _get_sig_view_replacements(cls, ops, sig_replacements):\n+        \"\"\"Given signal replacements `sig_replacements`, returns additional\n+        signal replacements required to account for views into a replaced\n+        signal.\n+\n+        Parameters\n+        ----------\n+        ops : sequence\n+            Operators to determine the additional signal replacements for.\n+        sig_replacements : dict\n+            Signal replacements.\n+\n+        Returns\n+        -------\n+        dict\n+            Additional required replacements of views into replaced bases of\n+            signals.\n+        \"\"\"\n+        view_replacements = {}\n+\n+        def get_sig_view_replacement(s):\n+            if s.is_view and s.base in sig_replacements:\n+                base_replacement = sig_replacements[s.base]\n+                offset = s.offset\n+                strides = tuple(a // b * c for a, b, c in zip_longest(\n+                    s.strides, s.base.strides, base_replacement.strides,\n+                    fillvalue=1))\n+                if base_replacement.is_view:\n+                    offset += base_replacement.offset\n+                    base_replacement = base_replacement.base\n+                buf = base_replacement.initial_value\n+                initial_value = np.ndarray(\n+                    buffer=buf, dtype=s.dtype, shape=s.shape, offset=offset,\n+                    strides=strides)\n+                view_replacements[s] = Signal(\n+                    initial_value, name=s.name, base=base_replacement,\n+                    readonly=s.readonly)\n+            return s\n+\n+        cls._map_onto_op_signals(get_sig_view_replacement, ops)\n+        return view_replacements\n+\n+    @classmethod\n+    def _replace_op_signals(cls, ops, sig_replacements):\n+        \"\"\"Apply signal repacements `sig_replacements` to all opeators in\n+        `ops`.\n+        \"\"\"\n+        cls._map_onto_op_signals(lambda s: sig_replacements.get(s, s), ops)\n+\n+    def _reinitialize_model_ops(self, ops):\n+        \"\"\"Reinitializes the operator list of the builder model from `ops`.\"\"\"\n+        self.model.operators = []\n+        for op in ops:\n+            self.model.add_op(op)\n+\n+    def _update_model_sigs(self, sig_replacements):\n+        \"\"\"Updates the signal dictionary in the builder model with\n+        `sig_replacements`.\n+        \"\"\"\n+        for k in self.model.sig:\n+            for name, v in self.model.sig[k].items():\n+                self.model.sig[k][name] = sig_replacements.get(v, v)\n+\n+\n+class AbstractMerger(object):\n+    def can_merge(self, op1, op2):\n+        \"\"\"Checks if `op1` can be merged with `op2`.\n+\n+        This function is expected to be transitive and symmetric.\n+        \"\"\"\n+        raise NotImplementedError()\n+\n+    def merge(self, ops):\n+        \"\"\"Merges the operators `ops`.\n+\n+        May lead to undefined behaviour if ``can_merge`` returns ``False`` for\n+        any of the elements in ``ops``.\n+\n+        Returns\n+        -------\n+        Operator\n+            The merged operator.\n+        dict\n+            Dictionary mapping old signals to new signals to update the\n+            signals of other operators.\n+        \"\"\"\n+        raise NotImplementedError()\n+\n+\n+@OpMergeOptimizer.register_merger(operator.TimeUpdate)\n+class TimeUpdateMerger(AbstractMerger):\n+    def can_merge(self, op1, op2):\n+        return True\n+\n+    def merge(self, ops):\n+        replacements = {}\n+        step = merge_signals_or_views([o.step for o in ops], replacements)\n+        time = merge_signals_or_views([o.time for o in ops], replacements)\n+        return operator.TimeUpdate(step, time), replacements\n+\n+\n+@OpMergeOptimizer.register_merger(operator.Reset)\n+class ResetMerger(AbstractMerger):\n+    def can_merge(self, op1, op2):\n+        return compatible([op1.dst, op2.dst]) and op1.value == op2.value\n+\n+    def merge(self, ops):\n+        replacements = {}\n+        dst = merge_signals_or_views([o.dst for o in ops], replacements)\n+        return operator.Reset(dst, ops[0].value), replacements\n+\n+\n+@OpMergeOptimizer.register_merger(operator.Copy)\n+class CopyMerger(AbstractMerger):\n+    def can_merge(self, op1, op2):\n+        return (\n+            compatible([op1.dst, op2.dst]) and compatible([op1.src, op2.src]))\n+\n+    def merge(self, ops):\n+        replacements = {}\n+        dst = merge_signals_or_views([o.dst for o in ops], replacements)\n+        src = merge_signals_or_views([o.src for o in ops], replacements)\n+        return operator.Copy(src, dst), replacements\n+\n+\n+@OpMergeOptimizer.register_merger(operator.SlicedCopy)\n+class SlicedCopyMerger(AbstractMerger):\n+    def can_merge(self, op1, op2):\n+        return (\n+            compatible([op1.src, op2.src]) and\n+            compatible([op1.dst, op2.dst]) and\n+            op1.src_slice is Ellipsis and op1.dst_slice is Ellipsis and\n+            op2.src_slice is Ellipsis and op2.dst_slice is Ellipsis and\n+            op1.inc == op2.inc)\n+\n+    def _merged_slice(self, signals, slices):\n+        if all(s is Ellipsis for s in slices):\n+            return Ellipsis\n+        elif any(s is Ellipsis for s in slices):\n+            raise ValueError(\"Mixed Ellipsis with list of indices.\")\n+\n+        offset = 0\n+        merged_slice = []\n+        for sig, sl in zip(signals, slices):\n+            merged_slice.extend([i + offset for i in sl])\n+            offset += sig.size\n+        return merged_slice\n+\n+    def merge(self, ops):\n+        src_sigs = [o.src for o in ops]\n+        dst_sigs = [o.dst for o in ops]\n+\n+        replacements = {}\n+        src = merge_signals_or_views(src_sigs, replacements)\n+        dst = merge_signals_or_views(dst_sigs, replacements)\n+        src_slice = self._merged_slice(src_sigs, [o.src_slice for o in ops])\n+        dst_slice = self._merged_slice(dst_sigs, [o.dst_slice for o in ops])\n+        return operator.SlicedCopy(\n+            src, dst, src_slice=src_slice, dst_slice=dst_slice,\n+            inc=ops[0].inc), replacements\n+\n+\n+@OpMergeOptimizer.register_merger(operator.ElementwiseInc)\n+class ElementwiseIncMerger(AbstractMerger):\n+    def can_merge(self, op1, op2):\n+        return (\n+            compatible([op1.A, op2.A], axis=op1.A.ndim - 1) and\n+            compatible([op1.X, op2.X], axis=op1.X.ndim - 1) and\n+            compatible([op1.Y, op2.Y], axis=op1.Y.ndim - 1))\n+\n+    def merge(self, ops):\n+        replacements = {}\n+        A = merge_signals_or_views(\n+            [o.A for o in ops], replacements, axis=ops[0].A.ndim - 1)\n+        X = merge_signals_or_views(\n+            [o.X for o in ops], replacements, axis=ops[0].X.ndim - 1)\n+        Y = merge_signals_or_views(\n+            [o.Y for o in ops], replacements, axis=ops[0].Y.ndim - 1)\n+        return operator.ElementwiseInc(A, X, Y), replacements\n+\n+\n+@OpMergeOptimizer.register_merger(operator.DotInc)\n+class DotIncMerger(AbstractMerger):\n+    def can_merge(self, op1, op2):\n+        if op1.X is op2.X:\n+            # simple merge might be possible\n+            return compatible([op1.Y, op2.Y]) and compatible([op1.A, op2.A])\n+\n+        # check if BSR merge is possible\n+        try:\n+            # Not using compatible() for A, because A must not be a view.\n+            check_signals_mergeable([op1.A, op2.A])\n+            from scipy.sparse import bsr_matrix\n+            assert bsr_matrix\n+        except (ValueError, ImportError):\n+            return False\n+        return (compatible([op1.X, op2.X]) and\n+                compatible([op1.Y, op2.Y]) and\n+                op1.A.shape == op2.A.shape)\n+\n+    def merge(self, ops):\n+        replacements = {}\n+\n+        # Simple merge if all X are the same.\n+        if all(o.X is ops[0].X for o in ops):\n+            A = merge_signals_or_views([o.A for o in ops], replacements)\n+            Y = merge_signals_or_views([o.Y for o in ops], replacements)\n+            return operator.DotInc(A, ops[0].X, Y), replacements\n+\n+        # BSR merge if X differ\n+        X = merge_signals_or_views([o.X for o in ops], replacements)\n+        Y = merge_signals_or_views([o.Y for o in ops], replacements)\n+\n+        # Construct sparse A representation\n+        data = np.array([o.A.initial_value for o in ops])\n+        indptr = np.arange(len(ops) + 1, dtype=int)\n+        indices = np.arange(len(ops), dtype=int)\n+        name = 'bsr_merged<{first}, ..., {last}>'.format(\n+            first=ops[0].A.name, last=ops[-1].A.name)\n+        readonly = all([o.A.readonly for o in ops])\n+        A = Signal(data, name=name, readonly=readonly)\n+        for i, s in enumerate([o.A for o in ops]):\n+            replacements[s] = Signal(\n+                data[i], name=\"%s[%i]\" % (s.name, i), base=A)\n+            assert np.all(s.initial_value == replacements[s].initial_value)\n+            assert s.shape == replacements[s].shape\n+\n+        reshape = operator.reshape_dot(\n+            ops[0].A.initial_value, ops[0].X.initial_value,\n+            ops[0].Y.initial_value, tag=ops[0].tag)\n+        return (\n+            operator.BsrDotInc(\n+                A, X, Y, indices=indices, indptr=indptr, reshape=reshape),\n+            replacements)\n+\n+\n+@OpMergeOptimizer.register_merger(SimNeurons)\n+class SimNeuronsMerger(AbstractMerger):\n+    def can_merge(self, op1, op2):\n+        return (\n+            op1.neurons == op2.neurons and\n+            all(compatible(s) for s in zip(op1.all_signals, op2.all_signals)))\n+\n+    def _gather(self, ops, key):\n+        return [getattr(o, key) for o in ops]\n+\n+    def merge(self, ops):\n+        replacements = {}\n+        J = merge_signals_or_views(self._gather(ops, 'J'), replacements)\n+        output = merge_signals_or_views(\n+            self._gather(ops, 'output'), replacements)\n+        states = []\n+        for signals in zip(*self._gather(ops, 'states')):\n+            states.append(merge_signals_or_views(signals, replacements))\n+        return SimNeurons(ops[0].neurons, J, output, states), replacements\n+\n+\n+def compatible(signals, axis=0):\n+    \"\"\"Checks that all signals have a compatible shape along a given axis\n+    to allow for concatenation.\n+\n+    For views this includes also a check that the signals have a common\n+    base and agree on the strides.\n+\n+    In comparison to the `check_*_mergeable` functions, this function does\n+    not throw exceptions (either behavior might be desired dependent on the\n+    context) and allows for either signals or signal views.\n+    \"\"\"\n+    if len(set(signals)) != len(signals):\n+        # Signal appears twice in list.\n+        return False\n+    for s in signals:\n+        if s.ndim != signals[0].ndim:","path":"nengo/builder/optimizer.py","position":786,"original_position":786,"commit_id":"08a5b4ad057baa8d4c2d68291ad6cde41322fc6b","original_commit_id":"08a5b4ad057baa8d4c2d68291ad6cde41322fc6b","user":{"login":"Seanny123","id":1918825,"avatar_url":"https://avatars.githubusercontent.com/u/1918825?v=3","gravatar_id":"","url":"https://api.github.com/users/Seanny123","html_url":"https://github.com/Seanny123","followers_url":"https://api.github.com/users/Seanny123/followers","following_url":"https://api.github.com/users/Seanny123/following{/other_user}","gists_url":"https://api.github.com/users/Seanny123/gists{/gist_id}","starred_url":"https://api.github.com/users/Seanny123/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Seanny123/subscriptions","organizations_url":"https://api.github.com/users/Seanny123/orgs","repos_url":"https://api.github.com/users/Seanny123/repos","events_url":"https://api.github.com/users/Seanny123/events{/privacy}","received_events_url":"https://api.github.com/users/Seanny123/received_events","type":"User","site_admin":false},"body":"In my opinion and [in the opinion of StackOverflow](http://stackoverflow.com/q/22782785/1079075), you should only have a stack of if-statements if the cases aren't mutually exclusive. From what I understand, these conditions aren't mutually exclusive and their ordering is arbitrary, so I think I'm okay with the stacked if-statements.","created_at":"2016-11-10T09:07:39Z","updated_at":"2016-11-10T09:07:39Z","html_url":"https://github.com/nengo/nengo/pull/1035#discussion_r87353120","pull_request_url":"https://api.github.com/repos/nengo/nengo/pulls/1035","_links":{"self":{"href":"https://api.github.com/repos/nengo/nengo/pulls/comments/87353120"},"html":{"href":"https://github.com/nengo/nengo/pull/1035#discussion_r87353120"},"pull_request":{"href":"https://api.github.com/repos/nengo/nengo/pulls/1035"}}},"pull_request":{"url":"https://api.github.com/repos/nengo/nengo/pulls/1035","id":67799791,"html_url":"https://github.com/nengo/nengo/pull/1035","diff_url":"https://github.com/nengo/nengo/pull/1035.diff","patch_url":"https://github.com/nengo/nengo/pull/1035.patch","issue_url":"https://api.github.com/repos/nengo/nengo/issues/1035","number":1035,"state":"open","locked":false,"title":"Operator graph optimizer","user":{"login":"jgosmann","id":850157,"avatar_url":"https://avatars.githubusercontent.com/u/850157?v=3","gravatar_id":"","url":"https://api.github.com/users/jgosmann","html_url":"https://github.com/jgosmann","followers_url":"https://api.github.com/users/jgosmann/followers","following_url":"https://api.github.com/users/jgosmann/following{/other_user}","gists_url":"https://api.github.com/users/jgosmann/gists{/gist_id}","starred_url":"https://api.github.com/users/jgosmann/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jgosmann/subscriptions","organizations_url":"https://api.github.com/users/jgosmann/orgs","repos_url":"https://api.github.com/users/jgosmann/repos","events_url":"https://api.github.com/users/jgosmann/events{/privacy}","received_events_url":"https://api.github.com/users/jgosmann/received_events","type":"User","site_admin":false},"body":"I updated this description with the new template. The old description can be found below.\n\n**Description:**\nThis adds an optimizer to the simulator that goes through the operator graph and merges operators and their signals. This reduces the items to iterate over in slow Python (vs. fast NumPy) and gives larger blocks of sequentially aligned memory for improved CPU caching and prefetching.\n\n**Motivation and context:**\n\nNot everyone has a powerful GPU and can use nengo_ocl (especially at the summer school it is common to have a laptop without decent GPU). For those people this PR can significantly improve the run time.\n\nThis is also useful for running on high-performance clusters (in a serial-farming setup) like Sharcnet which mostly consist of CPU clusters and only few GPU clusters (and usually much more CPU cores than GPUs are provided).\n\nFurthermore, when using large ensemble arrays (as in SPA, especially with spaopt #941, dot products, circular convolutions) this reduces the overhead that is introduced by many small ensembles.\n\n**Interactions with other PRs:**\nNo real interactions afaik, but #941 will benefit.\n\n**How has this been tested?**\nThe optimizer is enabled by default and all the tests still pass. Furthermore, I am using the optimizer on my TCM model and on @ikajic's spa-rat model. Especially, the latter one has a large arrays of small ensembles (5018 elements in a cleanup memory) and uncovered a number of memory and runtime issues that have been fixed. @xchoo tested a slightly older version of the optimizer on Spaun. Read through the comments for quotes on run time improvements and additions to the build time (quoted build time for Spaun might be lower now with recent improvements).\n\nI did not add a lot of unit tests because for the most part it is not clear to me how to test the optimizer. It is tested through the existing tests (all those models still work) which verifies its correctness in a way, but doesn't test that it actually speed up things or isn't a no-op. Good ideas welcome.\n\n**Where should a reviewer start?**\n`optimizer.py` is the main algorithm and should be structured going from the high level to the low level of the algorithm. I tried to document it well, but it might not be sufficient to understand everything. Let me know where more comments would be helpful.\n\nMaybe it is best to go through the code with me as it is somewhat complex.\n\n**How long should this take to review?**\n\n<!--- Please estimate if this PR is a quick, average, or lengthy PR. -->\n\n<!--- Take into account both the size and complexity of the changes. -->\n\n<!--- Also note if this is a timely PR that should be reviewed by a certain date. -->\n\n<!--- Leave only the line that applies below: -->\n- Lengthy (more than 150 lines changed or changes are complicated)\n\n**Types of changes:**\n- New feature (non-breaking change which adds functionality)\n\n**Checklist:**\n\n<!--- Go over all the following points. Put an `x` in all the boxes that apply. -->\n\n<!--- If a box is not applicable, please justify below the checklist. -->\n\n<!--- If you're unsure about any of these, don't hesitate to ask. -->\n\n<!--- We're here to help! -->\n- [x] I have read the **CONTRIBUTING.rst** document.\n- [x] I have updated the documentation accordingly. (More documentation should be added, separate issue #1119.)\n- [x] I have included a changelog entry.\n- [ ] I have added tests to cover my changes.\n- [x] All new and existing tests passed.\n\n**Still to do:**\n#1119, but I think it should be a separate PR.\n# Old description for reference\n\nThis adds an optimizer to the simulator that goes through the operator graph and merges operators and their signals. This reduces the items to iterate over in slow Python (vs. fast NumPy) and gives larger blocks of sequentially aligned memory for improved CPU caching and prefetching.\n\nAt the moment the only operator that's being merged is `SimNeurons`, but I will look and see if this can be done for other operators too.\n\nThere is a trade-off, though. Running the simulation gets faster, but the build process will be slower. The algorithmic complexity of the optimizer is O(n^2 + e) where n is the number of operators and e the number of edges in the dependency graph.\n\nA few \"benchmarks\" I run:\n- Simulating an ensemble array with 100 one-dimensional ensembles with 50 neurons: Pure simulation time decreases from 18 to 4 seconds (4.5x speedup! :dash: )\n- `py.test -n 6` from 60s down to 51s\n- `py.test -n 6 --slow` from 415s down to 274s \n- `py.test` from 83s down to 71s\n\nI haven't tested in on any more complicated models yet, but that should definitely be done. It would be nice to have #937 implemented to easily see the effect on build time.\n\nIt probably would be a good idea to have an option to turn the optimization on and off. Probably with an rc setting, but I feel like this could be something people want to change per instantiation of the `Simulator`. Also wondering if there should be some more fine grained control which operators to merge (or if we add other optimizations which set of these should be done).\n\n~~I think there was an issue about adding optimizations to the simulator, but I can't find it right now.~~ Found it, this addresses #778.\n# TODO\n- [x] Merging of views has been implemented for `Copy` in the `op-opt-view` branch with a lot of code duplication. Refactor this.\n- [x] Look at view merging for other operators\n- [x] Look at general merging for other operators\n- [x] Add more documentation about how the optimization is performed and some of the finecky details (views get broken in the first pass, then fixed later, then view merging is done because first pass introduces more views)\n- [x] Could we need more than two passes? Or in other words could view merging introduce more views because of associated non-view signals? (--> only relevant if view merging is supported for other things than `Copy`)\n- [x] Add test for signal merging (this should be simple enough to unit test and is part of the public `Signal` API). Not sure if it makes sense to test the optimizer in any other way than checking that it does not break any of the existing tests. Complex interactions are hard to cover in any other way anyways. Not sure if it is worth to construct and check simple cases. Maybe that certain optimizations are done at all?\n- [x] Config options\n- [x] Under some circumstances the optimizer seems to require a lot of memory. I should investigate this.\n- [x] Always performs a minimum of two passes even if the first pass didn't lead to a reduction in the number of operators.\n- [x] This currently use the `np.stack` function in one place which requires NumPy 1.10. Replace it with an equivalent available in earlier versions. Also, add a test because that part of the code is apparently never hit in the tests (no failure on Travis-CI).\n","created_at":"2016-04-25T22:34:38Z","updated_at":"2016-11-10T09:07:39Z","closed_at":null,"merged_at":null,"merge_commit_sha":"6eb125de17c614956afd6897ae87b1c7191a9c2c","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/nengo/nengo/pulls/1035/commits","review_comments_url":"https://api.github.com/repos/nengo/nengo/pulls/1035/comments","review_comment_url":"https://api.github.com/repos/nengo/nengo/pulls/comments{/number}","comments_url":"https://api.github.com/repos/nengo/nengo/issues/1035/comments","statuses_url":"https://api.github.com/repos/nengo/nengo/statuses/08a5b4ad057baa8d4c2d68291ad6cde41322fc6b","head":{"label":"nengo:op-opt","ref":"op-opt","sha":"08a5b4ad057baa8d4c2d68291ad6cde41322fc6b","user":{"login":"nengo","id":9197486,"avatar_url":"https://avatars.githubusercontent.com/u/9197486?v=3","gravatar_id":"","url":"https://api.github.com/users/nengo","html_url":"https://github.com/nengo","followers_url":"https://api.github.com/users/nengo/followers","following_url":"https://api.github.com/users/nengo/following{/other_user}","gists_url":"https://api.github.com/users/nengo/gists{/gist_id}","starred_url":"https://api.github.com/users/nengo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nengo/subscriptions","organizations_url":"https://api.github.com/users/nengo/orgs","repos_url":"https://api.github.com/users/nengo/repos","events_url":"https://api.github.com/users/nengo/events{/privacy}","received_events_url":"https://api.github.com/users/nengo/received_events","type":"Organization","site_admin":false},"repo":{"id":9568894,"name":"nengo","full_name":"nengo/nengo","owner":{"login":"nengo","id":9197486,"avatar_url":"https://avatars.githubusercontent.com/u/9197486?v=3","gravatar_id":"","url":"https://api.github.com/users/nengo","html_url":"https://github.com/nengo","followers_url":"https://api.github.com/users/nengo/followers","following_url":"https://api.github.com/users/nengo/following{/other_user}","gists_url":"https://api.github.com/users/nengo/gists{/gist_id}","starred_url":"https://api.github.com/users/nengo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nengo/subscriptions","organizations_url":"https://api.github.com/users/nengo/orgs","repos_url":"https://api.github.com/users/nengo/repos","events_url":"https://api.github.com/users/nengo/events{/privacy}","received_events_url":"https://api.github.com/users/nengo/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/nengo/nengo","description":"A Python library for creating and simulating large-scale brain models","fork":false,"url":"https://api.github.com/repos/nengo/nengo","forks_url":"https://api.github.com/repos/nengo/nengo/forks","keys_url":"https://api.github.com/repos/nengo/nengo/keys{/key_id}","collaborators_url":"https://api.github.com/repos/nengo/nengo/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/nengo/nengo/teams","hooks_url":"https://api.github.com/repos/nengo/nengo/hooks","issue_events_url":"https://api.github.com/repos/nengo/nengo/issues/events{/number}","events_url":"https://api.github.com/repos/nengo/nengo/events","assignees_url":"https://api.github.com/repos/nengo/nengo/assignees{/user}","branches_url":"https://api.github.com/repos/nengo/nengo/branches{/branch}","tags_url":"https://api.github.com/repos/nengo/nengo/tags","blobs_url":"https://api.github.com/repos/nengo/nengo/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/nengo/nengo/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/nengo/nengo/git/refs{/sha}","trees_url":"https://api.github.com/repos/nengo/nengo/git/trees{/sha}","statuses_url":"https://api.github.com/repos/nengo/nengo/statuses/{sha}","languages_url":"https://api.github.com/repos/nengo/nengo/languages","stargazers_url":"https://api.github.com/repos/nengo/nengo/stargazers","contributors_url":"https://api.github.com/repos/nengo/nengo/contributors","subscribers_url":"https://api.github.com/repos/nengo/nengo/subscribers","subscription_url":"https://api.github.com/repos/nengo/nengo/subscription","commits_url":"https://api.github.com/repos/nengo/nengo/commits{/sha}","git_commits_url":"https://api.github.com/repos/nengo/nengo/git/commits{/sha}","comments_url":"https://api.github.com/repos/nengo/nengo/comments{/number}","issue_comment_url":"https://api.github.com/repos/nengo/nengo/issues/comments{/number}","contents_url":"https://api.github.com/repos/nengo/nengo/contents/{+path}","compare_url":"https://api.github.com/repos/nengo/nengo/compare/{base}...{head}","merges_url":"https://api.github.com/repos/nengo/nengo/merges","archive_url":"https://api.github.com/repos/nengo/nengo/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/nengo/nengo/downloads","issues_url":"https://api.github.com/repos/nengo/nengo/issues{/number}","pulls_url":"https://api.github.com/repos/nengo/nengo/pulls{/number}","milestones_url":"https://api.github.com/repos/nengo/nengo/milestones{/number}","notifications_url":"https://api.github.com/repos/nengo/nengo/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/nengo/nengo/labels{/name}","releases_url":"https://api.github.com/repos/nengo/nengo/releases{/id}","deployments_url":"https://api.github.com/repos/nengo/nengo/deployments","created_at":"2013-04-20T18:46:06Z","updated_at":"2016-11-08T18:08:08Z","pushed_at":"2016-11-10T07:47:28Z","git_url":"git://github.com/nengo/nengo.git","ssh_url":"git@github.com:nengo/nengo.git","clone_url":"https://github.com/nengo/nengo.git","svn_url":"https://github.com/nengo/nengo","homepage":"","size":28748,"stargazers_count":180,"watchers_count":180,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":56,"mirror_url":null,"open_issues_count":244,"forks":56,"open_issues":244,"watchers":180,"default_branch":"master"}},"base":{"label":"nengo:master","ref":"master","sha":"b07a200b174a06d2ef9ba36746caf14fd0ea80b1","user":{"login":"nengo","id":9197486,"avatar_url":"https://avatars.githubusercontent.com/u/9197486?v=3","gravatar_id":"","url":"https://api.github.com/users/nengo","html_url":"https://github.com/nengo","followers_url":"https://api.github.com/users/nengo/followers","following_url":"https://api.github.com/users/nengo/following{/other_user}","gists_url":"https://api.github.com/users/nengo/gists{/gist_id}","starred_url":"https://api.github.com/users/nengo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nengo/subscriptions","organizations_url":"https://api.github.com/users/nengo/orgs","repos_url":"https://api.github.com/users/nengo/repos","events_url":"https://api.github.com/users/nengo/events{/privacy}","received_events_url":"https://api.github.com/users/nengo/received_events","type":"Organization","site_admin":false},"repo":{"id":9568894,"name":"nengo","full_name":"nengo/nengo","owner":{"login":"nengo","id":9197486,"avatar_url":"https://avatars.githubusercontent.com/u/9197486?v=3","gravatar_id":"","url":"https://api.github.com/users/nengo","html_url":"https://github.com/nengo","followers_url":"https://api.github.com/users/nengo/followers","following_url":"https://api.github.com/users/nengo/following{/other_user}","gists_url":"https://api.github.com/users/nengo/gists{/gist_id}","starred_url":"https://api.github.com/users/nengo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nengo/subscriptions","organizations_url":"https://api.github.com/users/nengo/orgs","repos_url":"https://api.github.com/users/nengo/repos","events_url":"https://api.github.com/users/nengo/events{/privacy}","received_events_url":"https://api.github.com/users/nengo/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/nengo/nengo","description":"A Python library for creating and simulating large-scale brain models","fork":false,"url":"https://api.github.com/repos/nengo/nengo","forks_url":"https://api.github.com/repos/nengo/nengo/forks","keys_url":"https://api.github.com/repos/nengo/nengo/keys{/key_id}","collaborators_url":"https://api.github.com/repos/nengo/nengo/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/nengo/nengo/teams","hooks_url":"https://api.github.com/repos/nengo/nengo/hooks","issue_events_url":"https://api.github.com/repos/nengo/nengo/issues/events{/number}","events_url":"https://api.github.com/repos/nengo/nengo/events","assignees_url":"https://api.github.com/repos/nengo/nengo/assignees{/user}","branches_url":"https://api.github.com/repos/nengo/nengo/branches{/branch}","tags_url":"https://api.github.com/repos/nengo/nengo/tags","blobs_url":"https://api.github.com/repos/nengo/nengo/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/nengo/nengo/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/nengo/nengo/git/refs{/sha}","trees_url":"https://api.github.com/repos/nengo/nengo/git/trees{/sha}","statuses_url":"https://api.github.com/repos/nengo/nengo/statuses/{sha}","languages_url":"https://api.github.com/repos/nengo/nengo/languages","stargazers_url":"https://api.github.com/repos/nengo/nengo/stargazers","contributors_url":"https://api.github.com/repos/nengo/nengo/contributors","subscribers_url":"https://api.github.com/repos/nengo/nengo/subscribers","subscription_url":"https://api.github.com/repos/nengo/nengo/subscription","commits_url":"https://api.github.com/repos/nengo/nengo/commits{/sha}","git_commits_url":"https://api.github.com/repos/nengo/nengo/git/commits{/sha}","comments_url":"https://api.github.com/repos/nengo/nengo/comments{/number}","issue_comment_url":"https://api.github.com/repos/nengo/nengo/issues/comments{/number}","contents_url":"https://api.github.com/repos/nengo/nengo/contents/{+path}","compare_url":"https://api.github.com/repos/nengo/nengo/compare/{base}...{head}","merges_url":"https://api.github.com/repos/nengo/nengo/merges","archive_url":"https://api.github.com/repos/nengo/nengo/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/nengo/nengo/downloads","issues_url":"https://api.github.com/repos/nengo/nengo/issues{/number}","pulls_url":"https://api.github.com/repos/nengo/nengo/pulls{/number}","milestones_url":"https://api.github.com/repos/nengo/nengo/milestones{/number}","notifications_url":"https://api.github.com/repos/nengo/nengo/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/nengo/nengo/labels{/name}","releases_url":"https://api.github.com/repos/nengo/nengo/releases{/id}","deployments_url":"https://api.github.com/repos/nengo/nengo/deployments","created_at":"2013-04-20T18:46:06Z","updated_at":"2016-11-08T18:08:08Z","pushed_at":"2016-11-10T07:47:28Z","git_url":"git://github.com/nengo/nengo.git","ssh_url":"git@github.com:nengo/nengo.git","clone_url":"https://github.com/nengo/nengo.git","svn_url":"https://github.com/nengo/nengo","homepage":"","size":28748,"stargazers_count":180,"watchers_count":180,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":56,"mirror_url":null,"open_issues_count":244,"forks":56,"open_issues":244,"watchers":180,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/nengo/nengo/pulls/1035"},"html":{"href":"https://github.com/nengo/nengo/pull/1035"},"issue":{"href":"https://api.github.com/repos/nengo/nengo/issues/1035"},"comments":{"href":"https://api.github.com/repos/nengo/nengo/issues/1035/comments"},"review_comments":{"href":"https://api.github.com/repos/nengo/nengo/pulls/1035/comments"},"review_comment":{"href":"https://api.github.com/repos/nengo/nengo/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/nengo/nengo/pulls/1035/commits"},"statuses":{"href":"https://api.github.com/repos/nengo/nengo/statuses/08a5b4ad057baa8d4c2d68291ad6cde41322fc6b"}}}}
{"actor":{"display_login":"Seanny123"}}