adonisjs5的Ioc机制初探

什么是Ioc

Ioc(Inversion of Control)是一种设计模式.它指的是使用某对象/资源的代码,不负责该对象的依赖对象的创建和维护,而交给一个专门的容器来负责.这样,怎么创建对象的控制权就转移到了这个专门的容器,即实现了所谓的控制反转.Ioc用来降低对象之间由依赖关系产生的耦合.(按照软件工程理论,依赖算是最弱的一种耦合了.依赖 < 关联 < 聚合 < 组合< 继承)我感觉,Ioc算是一个升级版的工厂模式,它管理了大量的工厂函数和对应的资源名称.可以把创建资源/对象的依赖写在Ioc里面.

adonisjs5中的Ioc

我感觉有点奇怪,adonisjs5的官方文档中没有专门提及Ioc. https://docs.adonisjs.com/guides/introduction 但在adonisjs4.x https://legacy.adonisjs.com/docs/4.1/ioc-container 的官方文档中却有单独的一节来讲Ioc.以至于,我第一次读完adonis5的文档后,对Ioc竟然没什么印象.而Ioc却是adonis最为重要的概念.anyway~,看看adonis的源代码怎么处理Ioc吧.

注册Ioc

在adonisjs的代码中搜索一下,

find node_modules/@adonisjs -iname "*ioc*"

很容易发现adonisjs实现Ioc的代码在node_modules/@adonisjs/fold/build/src/Ioc/这个目录中.目录名就是Ioc,毫不掩饰自己的目的.
逛一逛Ioc这个目录下的js文件,发现最重要的是index.js 和 binBindings.js这两个文件.其中index.js中有一个类就叫Ioc, 而注册到Ioc中的资源被放在Bindings.js文件中Bindings类中.

    /**
     * Define a binding
     */
    register(binding, callback, singleton) {
        this.list.set(binding, { callback, singleton });
        return this;
    }

Binding类中的register函数非常显眼.显然注册一个资源到Ioc的代码会走到这里.在这里下断点,调起调试器.发现register函数的三个参数的含义是: binding即资源的的namespace,通过调试器发现注册的第一个资源的namespace是“Adonis/Core/Application”;callback相当于创建这种资源的工厂函数,调用它即生产出一个对应的对象;而singleton则是一个boolean值,指示该种资源是不是一个单件.看看栈的上一个frame,是Ioc类的singleton()函数.看来,“Adonis/Core/Application”这个资源是通过Ioc.singleton()创建的.

    /**
     * Same as the [[bind]] method, but registers a singleton only. Singleton's callback
     * is invoked only for the first time and then the cached value is used
     */
    singleton(binding, callback) {
        helpers_2.ensureIsFunction(callback, '"ioc.singleton" expect 2nd argument to be a function');
        this.bindings.register(binding, callback, true);
        return this;
    }

Ioc.singleton()函数注释告诉我们.single()函数跟bind()函数一样,只不过是注册一个单件,单件的callback工厂函数仅调用一次.第一次创建会把资源cache起来,而后直接返回cache.这个cache即Bindings类中的list成员.虽然名字是list,但却是一个Map.映射namespace到对象/资源.

    constructor(container) {
        this.container = container;
        /**
         * Registered bindings
         */
        this.list = new Map();   // 明明是个Map,为何叫list?misnomer~~
    }

在看Ioc.singleton()函数的注释时提到了它的friend, Ioc.bind()函数.于是,在Ioc.bind()中下断点看看.发现了’Adonis/Core/Helpers’的,会调到这里.Helpers竟然不是singleton,有点意外.Ioc.bind()同样会调用Bindings.register()把工厂函数存起来.

    /**
     * Register a binding with a callback. The callback return value will be
     * used when binding is resolved
     */
    bind(binding, callback) {
        helpers_2.ensureIsFunction(callback, '"ioc.bind" expect 2nd argument to be a function');
        this.bindings.register(binding, callback, false);
        return this;
    }

从Ioc创建对象/资源

最开始看adonisjs4的官方文档 ,提到从Ioc创建对象直接调用Ioc.use(‘namespace’).后来看到adnoisjs的作者(大佬HARMINDER VIRK)写的一篇博客 https://blog.adonisjs.com/introducing-adonisjs-v5/ 中讲他特希望把Ioc的use()干掉,改成用EM的import.但Virk大佬没说use()换成import有什么好处.其实在adonisjs5中,使用use()仍然是可以的。

If I ever wanted to improve something to AdonisJS, that was getting rid of the use method to import dependencies,
…
Finally, we have been able make ESM imports work with the AdonisJS IoC container. It means, you can import bindings from the container as follows:

import Route from '@ioc:Adonis/Core/Route'

大佬Virk还提到,用这种方式不能用alias,理由是IDE会帮你补全名称,所以使用长名字不是一个问题.

那么我们看看import是怎么让Ioc创建对象/资源的.在Bindings类的resolve()函数中下断点:

    /**
     * Resolve a binding. An exception is raised, if the binding is missing
     */
    resolve(binding) {
        const bindingNode = this.list.get(binding);
        if (!bindingNode) {
            throw IocLookupException_1.IocLookupException.lookupFailed(binding);
        }
        let resolvedValue;
        if (bindingNode.singleton) {
            bindingNode.cachedValue = bindingNode.cachedValue ?? bindingNode.callback(this.container);
            resolvedValue = bindingNode.cachedValue;
        }
        else {
            resolvedValue = bindingNode.callback(this.container);
        }
        return resolvedValue;
    }

这个函数根据namespace的名字创建对象.如果是单件,就返回cache中的原有对象;如果不是就创建一个返回.断点第一次命中是,resolve函数的binding参数是”adonis/Core/Env”.看来拦到了创建“donis/Core/Env”对象的代码.看栈的上一帧是Ioc.resolveBinding(),上上帧则是Ioc.use(),再往上就是import语句

import Env from '@ioc:Adonis/Core/Env'

这~~~import之后就直接到了Ioc.use()!!!魔法呀~~从栈的显示来看import语句被显示成<anonymous>.我猜import应该是被解析成一个特殊的无名函数,而有某种方法可以Hook这个无名函数,让import的时候,模块名前面五个字符是”@ioc:”时,就跳去Ioc.use().

不过,后来我搞懂了这个机制。adonisjs5自己整了一个Typescript的编译器。它提供了一个visitor模式可以访问typescript被编译成javascript的代码结构,并可以做修改。于是,用这个visitor模式可以把import Env from ‘@ioc:Adonis/Core/Env’ 替换成一个Ioc.use()调用,载入对象。这个Typescript编译器在这个工程中:https://github.com/adonisjs/require-ts

只写这么多吧.其实里面的内容还有很多~~

Fiduccia Mattheyses算法(即FM算法)的论文解读

kamuszhou的博客,转载请注明URL。

现代大规模集成电路图(VLSI)非常庞大,当我们希望用多个FPGA仿真一个VLSI时,需要把VLSI在满足一些约束条件的情况下切割成多个小部分,每个部分都可以装进一个FPGA。

这个问题抽象成数学模型,实际上就是一个超图分割的问题。在超图分割领域有一篇发表于1982年的论文,名字是”A Linear-Time Heuristic for Improving Network Partitions”。这篇论文提出了一种改进的“超图二分问题”算法,简称为FM算法。虽然在1982年这篇论文发表时,“超图分割”算法领域已经发展了近十年。但这篇论文似乎有着近乎祖师爷级论文的地位,相当多的后期该领域的论文都会引用这篇文章。论文发表之后该领域继续发展出的“层次化超图多分割”算法可以看成是FM算法发展而来。该算法中涉及到的概念和思路是后续算法的基础,是很好的该领域入门学习的资料。
(更多超图及超图分割的基础概念请自行搜索,本博客主要解读论文)

论文的下载地址:
https://ieeexplore.ieee.org/document/1585498

在论文的摘要部分论述到:本文提出了一种启发式的,利用最小割(mincut)的迭代算法解决超图二分问题。该算法在最坏情况下的时间复杂度也是线性的。在实际应用中,绝大多数情况下,该算法都只需要很少次数的迭代。算法有三个特点:
1. 超图被分成两个Block。每次移动一个结点把它从原来的Block移往另一个Block。同时维持两个Block的平衡。重要的是,这个平衡不是基于每个Block中的结点数量,而是更一般的size of block的概念,它考虑到了每个结点的权重是不一样的。
2. 利用一个相当高效的数据结构,可以在O(1)常数时间复杂度内找到需要移动的最佳结点。
3. 在移动了某个结点后,再高效地更新受上次移动影响的结点的信息(即论文后面会提到的结点的gain值)。这第三个特点亦在论文的Introduction中被再次提到,作者认为这是该论文的主要贡献(main contribution).

术语及基本概念

  • n(i): 当i是超边的编号时,n(i)定义为每个超边上的结点数目。
  • s(i)或p(i): 当i表示结点时,s(i)或p(i)表示结点上的PIN数目,即结点一共跟多个条超边有连接,更多时候亦称为结点的size。
  • 邻居结点: 如果两个结点至少能通过一条超边连接,即为邻居结点。
  • A,B: 代表超图二分割后的两个BLOCK。
  • |A|: |A| = \sum_{i=i}^{n}{s(i)} 即Block A的size定义为Block A中所有的结点的size的连加。
  • A(n)或B(n): n表示编号为n的边,A(n)则表示该条n在Block A中的结点数。
  • cut: 在A和B中都有结点的超边。
  • cutstate: 一条超边是不是cut(后来发展成多分割问题中的cutsize)。
  • cell gains: 当移动一个结点到另一个BLOCK时,cut减少的数目。
    cell gains

维持平衡

最容易想到的是就是使超图二分割后的两个BLOCK中的结点数量大致相同。不过,可以稍微变复杂一点,即考虑每个结点的权重。
* W = |A| + |B| 所有结点的size连加和
* r = |A| / (|A| + |B|) 一个大小0到1之间的比率
* smax = \max_{1<i<n}{s(i)} 最大的结点size
* rW – k * smax <= |A| <= rW + k * smax;k > 1 平衡公式

公式不难,描述地很清楚。简单地讲,block的size考虑到了每个结点的权重不同。另外,允许每个block的size在满足比率r的附近上下浮动k个最大结点size。它的含义是,在刚好满足分割比率r的时候,还能够至少移动k个结点。

算法描述

  1. 随机找到一个划分A, B (初始划分并未严格要求是在平衡状态)
  2. 从A和B中都找出它们各自拥有最高gain值的结点,即有两个预备结点。
  3. 淘汰掉移动后会导致不平衡状态出现的预备结点。如果两个预备结点均被淘汰,则算法结束。
  4. 在这两个结点中选择拥有最高gain值的结点移动到对端。如果这两个预备结点gain值一样,就选会导致更好平衡状态的结点。如果还是一样,那就随你的心情挑一个(break ties as desired)。
  5. 锁定该结点,在本次迭代中不准再使用。
  6. 更新各个结点的gain值,跳到步骤2继续下一次迭代。

高效的数据结构

FM算法中有两个难点,即如何快速找到每个Block中gain值最高的结点以及高效的更新gain值以反应移动结点带来的变化。第一问题由下图所示的数据结构解决。
data structures

如图的数据结构共有两个。A,B两个BLOCK各有一个。其中 pmax即所有结点中最大size。显然,每个结点的gain值都在[-pmax, +pmax]之间。当pmax值相对较小时,可以用一个静态数组表示。FM论文中即用静态数组,但后来VLSI持续发展,静态数组太大的时候,即可换成用hash表。图中,坚着的数组表示在每一个gain值下面用链表存放Free结点,并用一个标记记录当前最高gain值是多少。横着的数组则存放了所有的结点。这样,就能在常数时间内找到最大的gain值和任意一个结点。

高效地更新gain值

当一个结点从当前BLOCK移到对端BLOCK后,会造成它的所有邻居结点的gain值有可能发生变化。如果用一个naive的算法,效率会很低。论文中论述了naive方法的时间复杂度O(P^2),P表示超图中所有PIN的总数目。这个时间复杂度很吓人,但我认为这是最坏极端情况下。但更详细的论述这里就略过吧,主要讲FM算法是怎么做的,这是该论文作者最得意的部分。

先引入关键边的概念。
critical net
当且仅当A(n)或B(n)等于0或者等于1时,一条边能称之为关键边。

(kamuszhou的博客,转载请注明源URL)

两个重要论述:

  1. If the net is not critical, its cutstate cannot be affected by a move

    如果一条边不是关键边,那么不可能只通过一次移动改变该边的cutstate。

  2. A net which is not critical either before or after a move cannot possibly influence the gains of any of its cells.

    如果一条边在移动前和移动后,它都不是关键边,那这条边则不影响gain值的更新。

那不就是~~~~
如何更新gain值,只用管移动前是关键边,或者移动后是关键边这两种情况么!!!

考察一个结点,把该结点从From Block移动到To Block这个移动前后的状态。
F(n)定义为一条超边n在From Block中的结点数。
T(n)定义为一条超边n在To Block中的结点数。
移动前符合哪些条件的边是超边呢?
F(n) = 1 or T(n) = 0 or T(n) = 1 其中F(n) = 0违反条件,不存在。
移动后哪些边是超边呢?
T(n) = 1 or F(n) = 0 or F(n) = 1 其中T(n) = 0违反条件,不存在。

再度惊人地发现!!!
移动前的F(n) = 1 即是移动后的 F(n) = 0
移动前的T(n) = 0 即是移动后的 T(n) = 1

于是~~符合什么条件的超边将影响gain值简化为:
移动前符合:
T(n) = 0 or T(n) = 1
移动后符合:
F(n) = 0 or F(n) = 1

于是,得到算法:
udpate gains

本文未尽细节

本文省略了如何计算每个结点的初始gain值,和如何生成初始状态的数据结构。因为这两个算法都相对简单,所以就略过,着重于论文作者最为得意的高效更新gain值的部分。

Our main contribution consists of an analysis of the effects a cell move has on its neighboring cells and a subsequent efficient implementaion of these results.

本文还省略了论者发现的几个命题(proposition),及一些算法复杂度的分析和证明。

还省略了其他细节~最好还是读原文!给你不一样的丝滑感受。

FM算法的缺点

在另一篇论文中,提到FM算法的3个缺点。
1. 当两边Block选出的gain值一样时,给的处理方式过于简单,不够有洞察力(insightful)。
2. 当一条超边在两个Block中的结点数都大于或等于两个时,它们就没有资格在第一时间被选为待移动结点。这显然太过greedy了。
3. 好像还提到过其他缺点但是我忘记了~

读后感

为何大佬那么厉害~
一个结点的移动对它的邻居结点gain值的影响的分析确实相当之精彩。虽然没有复杂的数学公式,但同样逻辑严谨,抽丝剥茧的分析。让人拍案叫绝~
为何作者能思考得这么有条理和深入??
除了具体的算法本身,还能学到哪些思考分析复杂问题的方式呢?
1. 简化问题
2. 提炼规律

转载请注明出处。