逻辑门的快速计算

Question

我创建了以下代码来计算逻辑门（AND、OR、NOT）的结果。该函数将用于从网表文件中读取电路的电路仿真中。一个电路最多可以包含 50000 个逻辑门。

基于这个函数在模拟过程中经常被调用的事实，我想知道是否可以用另一种方式实现它，这样生成的机器代码会更有效率？

一个逻辑门可以有两个以上的输入（除非只有一个输入）但大多数逻辑门只有两个。所以我考虑测试两个输入，然后写这样的东西： return input->predecessors[0]->result && return input->predecessors[1]->result; 和 return input->predecessors[0]->result || return input->predecessors[1]->result; 但这可能会引入新的分支。输入的数量可以直接存储在Node中，以防止调用size()方法。

#include <vector>

enum class NodeType { NOT, AND, OR };

struct Node {
    NodeType type;
    bool result;
    std::vector<Node *> predecessors;
};

bool evaluate(Node *input) {
    switch (input->type) {
        case NodeType::NOT: {
            return !input->predecessors[0]->result;
        }

        case NodeType::AND: {
            bool result = true;

            for (const auto &node : input->predecessors) {
                result = result && node->result;
            }

            return result;
        }

        case NodeType::OR: {
            bool result = false;

            for (const auto &node : input->predecessors) {
                result = result || node->result;
            }

            return result;
        }
    };
};

Answer 1

我很想获得第一个输入并将其状态合并到 switch()；喜欢：

    bool result = input->predecessors[0];
    switch((input->type << 1) | result) {
         case (NodeType::NOT << 1) | false:
             return true;
         case (NodeType::NOT << 1) | true:
             return false;
         case (NodeType::AND << 1) | false:
             return false;
         case (NodeType::OR << 1) | true:
             return true;
         case (NodeType::AND << 1) | true: {
             for (const auto &node : input->predecessors) {   // Note: Can skip 1st iteration
                 result = result && node->result;
                 if(result == false) {
                     return false;
                 }
             }
             return true;
         }
         case (NodeType::OR << 1) | false:
             for (const auto &node : input->predecessors) {   // Note: Can skip 1st iteration
                 result = result || node->result;
                 if(result == true) {
                     return true;
                 }
             }
             return false;
         }

希望编译器能够将其转换为跳转 table（例如，单个“jmp [table+rax*8]”指令替换所有 switch() 和其余一半代码）。

警告：要使其正常工作，您必须确保 input->predecessors[0] 使用 1 作为 "true"（并且没有其他值用于 true）。如果这是一个潜在的问题；你可以使用 bool result = !!input->predecessors[0];

Answer 2

看起来你做的真的是一个接口

struct Node {
    std::vector<Node *> predecessors;
    virtual bool evaluate() const;
};

struct NodeNot : Node {
    bool evaluate() const {
        return !input->predecessors[0]->result;
    }
};

struct NodeAnd : Node {
    bool evaluate() const {
         for (const auto &node : input->predecessors) {
             if(!node->result) {
                  // there is no need to accumulate the result
                  // fail fast
                  return false;
             }
         }
         return true;
    }
};

struct NodeOr : Node {
    bool evaluate() const {
         for (const auto &node : input->predecessors) {
             if (node->result) {
                 return true;
             }
         }
         return false;
    }
};

这样您就可以完全消除对 switch 的需求，只需一次 virtual 调用即可获得相同的结果。它可能比 switch 方法更快或更慢，这实际上取决于许多因素以及您在 Node::result 成员中缓存结果的程度。分析您的代码以确保最有效。

Answer 3

我正在考虑使用 std::variant。仍然有点 hacky，因为我使用的是 void 指针......任何帮助清理它都会很好

#include <tuple>
#include <variant>
#include <stdexcept>
#include <assert.h>

using vcpc = void const* const;

struct NOT { vcpc ptr; };
struct OR { vcpc ptr1; vcpc ptr2; };
struct AND { vcpc ptr1; vcpc ptr2; };

using Node = std::variant<NOT, OR, AND, bool>;

// from https://en.cppreference.com/w/cpp/utility/variant/visit
template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> overloaded(Ts...)->overloaded<Ts...>;

using Ncpc = Node const* const;

constexpr bool evaluate(Ncpc input) {
    return std::visit(overloaded{
        [](NOT const& arg) { return !evaluate((Ncpc)arg.ptr); },
        [](OR const& arg) { return evaluate((Ncpc)arg.ptr1) || evaluate((Ncpc)arg.ptr2); },
        [](AND const& arg) { return evaluate((Ncpc)arg.ptr1) && evaluate((Ncpc)arg.ptr2); },
        [](bool arg) { return arg; },
        }, *input);
}

int main() {
    Node const isTrue{ true };
    Node const invTrue{ NOT{&isTrue} };
    assert(evaluate(&invTrue) == false);

    Node const andTrueFalse{ AND{&isTrue, &invTrue} };
    assert(evaluate(&andTrueFalse) == false);

    Node const orTrueFalse{ OR{&isTrue, &andTrueFalse} };
    assert(evaluate(&orTrueFalse) == true);
}

逻辑门的快速计算

Fast computation of logic gates

c++

simulation

performance