手动编译Lua代码

如果将一段Lua代码直接翻译成C++代码,可能会存在一个问题:Luatail callC++没有tail call。 例如下面这个函数(求二叉树所有结点的和),第二次递归调用Visittail call,如果直接翻译成C++代码,会失去一部分优化效果。

function SumTree(root)
    local Sum = 0
    local function Visit(CurNode)
        if not CurNode then
            return    
        end
        Sum = Sum + CurNode.val
        Visit(CurNode.left)
        Visit(CurNode.right) -- tail call
    end
    Visit(root)
    return Sum
end

有一种方法可以将这段代码转化成高效的C++代码,保留tail call的效果,同时避免大部分函数调用的开销。
第一步,用 cps变换 将代码转换成下面的样子,每个函数调用都是tail call,每个函数增加了一个参数Cont
代码运行时系统的栈不会增长,访问left的时候Cont才会增长。
这个变换的作用是用自定义的Cont代替系统的栈,同时保留tail call的效果。

function SumTree(root)
    local Sum = 0

    local function ApplyCont(Cont)
        Cont()
    end

    local function ID()
    end

    local function Visit(CurNode, Cont)
        if not CurNode then
            return ApplyCont(Cont)
        end
        Sum = Sum + CurNode.val
        local Cont1 = function()
            Visit(CurNode.right, Cont)
        end
        Visit(CurNode.left, Cont1) -- Cont增长
    end
    Visit(root, ID)
    
    return Sum
end

第二步,用自定义的数据结构代表Cont,主要是将Cont函数捕捉的free vars与函数的代码分离开。

function SumTree(root)
    local Sum = 0

    local Visit
    local ActionMap = {
        function(FreeVars, Cont)
            Visit(FreeVars[1], Cont)
        end,
    }

    local function ApplyCont(Cont)
        if not Cont then
            return
        end
        local Action = ActionMap[Cont.ActionIndex]
        Action(Cont.FreeVars, Cont.Cont)
    end

    local ID = nil

    Visit = function(CurNode, Cont)
        if not CurNode then
            return ApplyCont(Cont)
        end
        Sum = Sum + CurNode.val
        local Cont1 = {
            FreeVars = {CurNode.right},
            ActionIndex = 1,
            Cont = Cont,
        }
        
        Visit(CurNode.left, Cont1)
    end
    Visit(root, ID)
    
    return Sum
end

第三步,上面代码中的Cont是一个简单的链表,而且只在一端操作,所以可以替换成一个外部的Stack,删掉所有函数的Cont参数。 同时将ActionMap中的代码inlineApplyCont 中。这段代码中只有一种Action,所以ActionIndex不是必须的。

function SumTree(root)
    local Sum = 0

    local Visit
    local Stack = {}

    local function ApplyCont()
        if #Stack == 0 then
            return
        end
        local Top = Stack[#Stack]
        Stack[#Stack] = nil
        if Top.ActionIndex == 1 then
            Visit(Top.FreeVars[1])
        end
    end

    Visit = function(CurNode)
        if not CurNode then
            return ApplyCont()
        end
        Sum = Sum + CurNode.val
        table.insert(Stack, {
            FreeVars = {CurNode.right},
            ActionIndex = 1,
        })
        
        Visit(CurNode.left)
    end
    Visit(root)
    
    return Sum
end

第四步,用tail call的方式调用函数时,当前函数中的参数和局部变量的生命周期就结束了,所以可以用一些外部的register来代替函数的参数和局部变量。同时调整一下Stack的结构,上面代码中的FreeVars主要是为了更好地说明问题。

function SumTree(root)
    local Sum = 0

    local Stack = {}
    local R_CurNode, R_Temp
    
    local Visit

    local function ApplyCont()
        if #Stack == 0 then
            return
        end
        R_Temp = Stack[#Stack]
        Stack[#Stack] = nil
        if R_Temp.ActionIndex == 1 then
            R_CurNode = R_Temp.Node
            Visit()
        end
    end

    Visit = function()
        if not R_CurNode then
            return ApplyCont()
        end
        Sum = Sum + R_CurNode.val
        table.insert(Stack, {
            ActionIndex = 1,
            Node = R_CurNode.right,
        })
        R_CurNode = R_CurNode.left
        Visit()
    end
    R_CurNode = root
    Visit()
    
    return Sum
end

第五步,将上面代码翻译成C++代码,其中,每个函数都没有参数、没有返回值、没有局部变量,每个函数调用都是tail call,所以可以直接用goto语句代替函数调用。有多种Action的时候,ActionIndex就有存在的必要了。

int SumTree(TreeNode* root) 
{
    int Sum = 0;

    struct StackNode 
    {
        int ActionIndex;
        TreeNode* Node;
    };
    vector<StackNode> Stack;

    TreeNode* R_CurNode = root;  //对应上面代码中的第一次调用Visit
    goto L_Visit; 

L_ApplyCont:
    if (Stack.empty())
    {
        return Sum; // 将最后的return移到此处
    }
    // 此处微调一下,不再需要R_Temp
    switch (Stack.back().ActionIndex)
    {
    case 1:
        R_CurNode = Stack.back().Node;
        Stack.pop_back();
        goto L_Visit;
        //break; 不需要
    }

L_Visit:
    if (!R_CurNode)
    {
        goto L_ApplyCont;
    }
    Sum += R_CurNode->val;
    Stack.push_back({
        1, R_CurNode->right
    });
    R_CurNode = R_CurNode->left;
    goto L_Visit;
}

最后,用Leetcode上的N-ary Tree Level Order Traversal 验证一下这种方法的正确性和优化效果。
这个问题比较聪明的答案是利用queue实现一个迭代算法,Leetcode官方版本的迭代代码最短执行时间是40ms,但是我用同样的代码提交,执行时间大约在45~70ms之间。
先实现一个无脑的递归算法,下面这段代码的执行时间大概在60~100ms之间,最短时间58秒。

vector<vector<int>> levelOrder(Node* root) {
    vector<vector<int>> Results;
    function<void(Node*, int)> Visit;
    Visit = [&](Node* CurNode, int Depth)
    {
        if (!CurNode)
        {
            return;
        }
        if (Results.size() < Depth)
        {
            Results.resize(Depth);
        }
        Results[Depth - 1].push_back(CurNode->val);
        for (auto Child : CurNode->children)
        {
            Visit(Child, Depth + 1);
        }
    };
    Visit(root, 1);
    return Results;
}

然后利用上面的方法转化成下面的代码,能通过所有testcase,执行时间大概在45~85ms之间,最短时间44ms。这个递归算法的实现中没有tail call,所以主要的优化效果来源于goto语句。

vector<vector<int>> levelOrder(Node* root) {
    vector<vector<int>> Results;
    struct StackNode {
        int ChildIndex;
        Node* CurNode;
        int CurDepth;
    };
    vector<StackNode> Stack;
    int R_ChildIndex;
    Node* R_CurNode = root;
    int R_CurDepth = 1;
    goto L_Recursive;

L_ApplyCont:
    if (Stack.empty())
    {
        return Results;
    }
    R_ChildIndex = Stack.back().ChildIndex;
    R_CurNode = Stack.back().CurNode;
    R_CurDepth = Stack.back().CurDepth;
    Stack.pop_back();
    goto L_LoopChild;

L_LoopChild:
    if (R_ChildIndex < R_CurNode->children.size())
    {
        Stack.push_back({
            R_ChildIndex+1, R_CurNode, R_CurDepth
        });
        R_CurNode = R_CurNode->children[R_ChildIndex];
        R_CurDepth++;
        goto L_Recursive;
    } 
    else
    {
        goto L_ApplyCont;
    }

L_Recursive:
    if (!R_CurNode)
    {
        goto L_ApplyCont;
    }
    if (Results.size() < R_CurDepth)
    {
        Results.resize(R_CurDepth);
    }
    Results[R_CurDepth - 1].push_back(R_CurNode->val);
    R_ChildIndex = 0;
    goto L_LoopChild;
}

这个转换代码的方法有一个灵活之处,我们可以将那些不需要优化的函数调用视为基本操作(类似+ - * /),最后生成的C++代码中添加上对这些Lua函数的调用。

糖果

糖果
LUA教程

Lapis框架的常用处理方法

Lapis框架的常用处理方法 Continue reading

MoonScript实现选择排序

Published on February 26, 2017

MoonScript与Redis客户端

Published on January 19, 2017