为什么这个简单的Go程序比它的Node.js对应程序运行得更慢？

Question

我将尝试使用Go语言实现一个二叉树，其中叶子节点上有值，即与以下等价：

data Tree a 
  = Node {left: Tree, right: Tree} 
  | Leaf {value: a}

我遇到了两个问题：1、我没能找到一种方法来创建具有多个构造函数的类型，所以我必须将所有数据都放在一个构造函数中。2、我无法使其多态化，因此我只能使用 interface{}（我猜这是对类型系统的“放弃”？）。这是我能做到的最好程度：

package main

import ("fmt")

type Tree struct {
  IsLeaf bool
  Left *Tree
  Value interface{}
  Right *Tree
}

func build(n int) *Tree {
  if (n == 0) {
    return &Tree{IsLeaf: true, Left: nil, Value: 1, Right: nil}
  } else {
    return &Tree{IsLeaf: false, Left: build(n - 1), Value: 0, Right: build(n - 1)}
  }
}

func sum(tree *Tree) int {
  if (tree.IsLeaf) {
    return tree.Value.(int)
  } else {
    return sum(tree.Left) + sum(tree.Right)
  }
}

func main() {
  fmt.Println(sum(build(23)))
}

它实现了类型并通过对生成的大树求和来测试它。我已经在JavaScript中进行了等效实现（包括构造函数上的冗余数据，以保证公平性）：

const build = n => {
  if (n === 0) {
    return {IsLeaf: true, Value: 1, Left: null, Right: null};
  } else {
    return {IsLeaf: false, Value: 0, Left: build(n - 1), Right: build(n - 1)};
  }
}

const sum = tree => {
  if (tree.IsLeaf) {
    return tree.Value;
  } else {
    return sum(tree.Left) + sum(tree.Right);
  }
}

console.log(sum(build(23)));

我已经使用go build test.go编译了Go代码，使用time ./test运行了它。我使用node test.js运行了Node.js代码。经过多次测试，Go程序平均运行时间约为2.5秒，而Node.js程序平均运行时间约为1.0秒。

这意味着对于这个简单的程序，Go要比Node.js慢2.5倍，但这显然是不正确的，因为Go是一种静态类型、编译语言，拥有成熟的编译器，而JavaScript则是一种未经类型检查的解释型语言。

那么我的Go程序为什么会这么慢呢？我是否遗漏了某些编译选项，或者代码本身存在问题？

- MaiaVictor

---

Go的哪个版本？如果您不为值使用接口会发生什么？通过将Value强制转换为int，您会失去一些速度。 - reticentroot

我认为真正的问题在于实现和Go处理递归的方式。https://medium.com/@felipedutratine/iterative-vs-recursive-vs-tail-recursive-in-golang-c196ca5fd489 - reticentroot

递归在Go中速度较慢：请参见：https://medium.com/@felipedutratine/iterative-vs-recursive-vs-tail-recursive-in-golang-c196ca5fd489 - Jack

你可能想看一下这个利用Go的一些特性实现的树结构。使用通道来实现它，你可能会看到速度上的提升。https://golang.org/doc/play/tree.go - reticentroot

我认为这里的问题在于对象模型的解释。我会给你写一份更详细的答案。 - Timothy Jones

Answer 1

摘要

这段代码因为类型断言和冗余数据而变慢。

Go 不鼓励在热点位置写类型断言：

tree.Value.(int) 

移除这个类型断言（并相应地将Value更改为int类型），你的代码将运行得快大约两倍（应该接近您的节点示例的速度）。

同时删除冗余数据，你的代码将运行得快约三倍。请参见本帖子末尾的游乐场示例。

细节

我认为这是设计上的错误，而不是实现上的错误。阅读您的问题，我认为有些困惑关于Go的类型系统如何工作。

Go的对象模型不鼓励您使用通用类型进行多态（请参见这篇优秀答案的前一半部分，了解Go的多态性讨论）。

在JavaScript世界中，每个对象都是特定类型的。在Go中，如果一个struct满足interface的合同，则可以将其视为特定的接口类型。请注意，structs不是对象-所谓的构造函数只是struct初始化器。

可以编写操作 interface{} 作为所有类型的占位符的 Go 代码，但是这种方式并不是语言鼓励使用的方式（正如您在问题中指出的那样，在 JavaScript 中编写干净的代码是一项挑战）。

由于 Go 实际上没有对象，因此在 Go 中尝试编写感觉非常面向对象的代码将是具有挑战性的（此外，Go 没有标准继承或方法重载）。因此，我认为您的代码不是 Go 鼓励程序员编写的代码。因此，这不是一个公平的测试。

类型断言很慢。（我不太了解 Go 内部设计，但肯定这表明程序员不应该编写大量的类型断言）。因此，您的代码性能不佳并不令人意外。我将您的代码更改为：

type Tree struct {
  IsLeaf bool
  Left *Tree
  Value int
  Right *Tree
} 
 .....
func sum(tree *Tree) int {
  if (tree.IsLeaf) {
    return tree.Value
  } else {
    return sum(tree.Left) + sum(tree.Right)
  }
}

我在我的机器上实现了2倍的速度提升。

可能还有其他优化方法 - 您可以尝试删除IsLeaf，并且您不需要在非叶节点存储值（或者，您可以将值分布到整个树中，因此永远不会浪费Value）。我不知道JavaScript是否会优化掉这些不必要的Value，但我不认为Go会。

因此，我认为您的代码使用的内存比所需的多得多，这也不会帮助性能。

这重要吗？

我个人不太相信“我用X和Y编写了此程序，并发现Y更慢”，特别是在跨框架公平比较方面很难。还有许多其他的差异来源 - 程序员知识，机器负载，启动时间等等。

要进行公正的测试，您需要编写每种语言中惯用的代码，但同时使用相同的代码。我不认为两者都能实现。

如果这段代码是您特定情况下的代码，并且性能是主要目标，则此测试可能有所帮助。但是，否则，我认为这不是一个非常有意义的比较。

在大规模情况下，我会预期其他考虑因素会超过创建和遍历树的速度。存在技术问题，例如数据吞吐量和负载下的性能，还有更加软性的问题，例如程序员时间和维护工作。

不过，这种学术练习很有趣。编写这样的代码是找到框架边缘的好方法。

---

编辑：我尝试让你的代码更符合Go语言的风格，这样做有额外的好处，可以将速度提高3倍。

https://play.golang.org/p/mWaO3WR6pw

树对于游乐场来说有点重，但你可以复制并粘贴代码在本地运行。

还有更多的优化可能性我没有尝试过，比如并行构建树。

你可以扩展这个设计以拥有你想要的多态行为（通过提供替代的Leaf实现），但是我不确定非数字类型的Sum()是什么意思。不知道如何定义Sum()是决定不通过泛型来包含多态性的思考方式的一个很好的例子。

- Timothy Jones

---

对于那些刚接触Go语言的人（可能会对这种不同的多态性视角感到不满），Go具有类型组合和许多其他强大的概念，比如“接口”系统——但这些概念鼓励以不同的方式构建程序。 - Timothy Jones

Go语言并不鼓励你禁用类型检查器，我认为恰恰相反。它鼓励你拥有具体的实现而非泛型。 - Timothy Jones

我并不是在主张禁用多态性，我只是说Go语言不鼓励你编写上述方式的多态代码。有其他方法可以编写相同的代码，但通常情况下，Go语言不允许你进行泛型编程。一开始我觉得这很令人沮丧，但使用了一段时间后，我不再感到遗憾。这只是一种不同的风格。 - Timothy Jones

“只是不同风格”是什么意思？我不是在谈论风格，而是在谈论一个实际的问题。假设我刚刚实现了某种类型的容器（比如说，一个整型列表）。然后我想要重用该容器的方法（concat、reverse等）用于另一种类型（比如字符串）。在Go中我该怎么做呢？这就是多态性解决的问题。你说有解决方案，但我还没有看到解决方案。我已经为此发布了一个单独的问题。 - MaiaVictor

你是说Go语言有一个弱类型系统...从一个做JavaScript的人口中说出来...哈哈哈。 - RickyA

Answer 2

我认为这可能会有所帮助。这是我实现的平衡二叉树，使用了递归、go程和通道。它旨在用作包，因此我使用了导出和未导出函数。导出函数是您应该使用/修改等的功能。我很久以前就写了它......有很多东西可以写得更好......但是我现在加了一个Sum函数给你。 我添加了23个节点，并在1/4秒内获得了总和。

更新：我添加了一个名为GetTreeTotal()的新功能，如果您查看Tree结构，我现在保留了一个Total字段。在Add()函数中，我在添加节点时更新该字段。现在，sum()不必进行大量计算，它只是树的元数据的一部分。从这个意义上说。超快。使用类似的逻辑，还可以将树上的节点数保存为元数据。知道这些信息将加快类似于TreeToArray()之类的函数，因为可以预先定义切片的大小。更少的分配等等。

更新2：这个问题让我感到好奇，我重写了下面的代码并将其转换为软件包。https://github.com/marcsantiago/GoTree迭代插入速度几乎快了3倍（包括基准测试），但当插入的数量非常高时才能真正看到这种差异。

package main

import (
    "encoding/json"
    "errors"
    "fmt"
    "math/rand"
    "sync"
    "time"
)

type node struct {
    Left  *node
    Right *node
    Data  int
}

// Tree ...
type Tree struct {
    Root  *node
    Total int
}

// FindNode ...
func (t *Tree) FindNode(data int) bool {
    newNode := node{
        Data: data,
    }
    if t.Root != nil {
        if t.findNode(t.Root, newNode) != nil {
            return true
        }
    }
    return false
}

func (t *Tree) findNode(search *node, target node) *node {
    var returnNode *node
    if search == nil {
        return returnNode
    }
    if search.Data == target.Data {
        return search
    }
    returnNode = t.findNode(search.Left, target)
    if returnNode == nil {
        returnNode = t.findNode(search.Right, target)
    }
    return returnNode
}

// Add ...
func (t *Tree) Add(data int) {
    t.Total += data
    if data < 0 {
        panic(errors.New("Only submit positive integers"))
    }
    nodeToAdd := node{
        Data: data,
    }
    if t.Root == nil {
        t.Root = new(node)
    }
    if t.Root.Data == 0 {
        t.Root = &nodeToAdd
        return
    }

    t.add(t.Root, nodeToAdd)
    return
}

func (t *Tree) add(oldnode *node, newNode node) {
    if newNode.Data < oldnode.Data {
        if oldnode.Left == nil {
            // t.Total += newNode.Data
            oldnode.Left = &newNode
        } else {
            // t.Total += newNode.Data
            t.add(oldnode.Left, newNode)
        }
    } else if newNode.Data > oldnode.Data {
        if oldnode.Right == nil {
            // t.Total += newNode.Data
            oldnode.Right = &newNode
        } else {
            // t.Total += newNode.Data
            t.add(oldnode.Right, newNode)
        }
    }
    return
}

// InOrderTraversal ...
func (t *Tree) InOrderTraversal() {
    if t.Root != nil {
        currentNode := t.Root
        if currentNode.Left == nil && currentNode.Right == nil {
            fmt.Println(currentNode.Data)
        } else {
            t.inOrderTraversal(currentNode)
        }
    }
    return
}

func (t *Tree) inOrderTraversal(n *node) {
    if n.Left != nil {
        t.inOrderTraversal(n.Left)
    }
    fmt.Println(n.Data)
    if n.Right != nil {
        t.inOrderTraversal(n.Right)
    }
    return
}

// Traversal ...
func (t *Tree) Traversal() {
    if t.Root != nil {
        currentNode := t.Root
        if currentNode.Left == nil && currentNode.Right == nil {
            fmt.Println(currentNode.Data)
        } else {
            t.traversal(currentNode)
        }
    }
    return
}

func (t *Tree) traversal(n *node) {
    fmt.Println(n.Data)
    if n.Left != nil {
        t.traversal(n.Left)
    }

    if n.Right != nil {
        t.traversal(n.Right)
    }
    return
}

// Sum ...
func (t *Tree) Sum() (total int) {
    var wg sync.WaitGroup
    c := make(chan int, 100)
    if t.Root != nil {
        currentNode := t.Root
        if currentNode.Left == nil && currentNode.Right == nil {
            return 1
        }
        wg.Add(1)
        t.sum(currentNode, c, &wg)
    }
    go func() {
        wg.Wait()
        close(c)
    }()
    for n := range c {
        total += n
    }
    return total
}

func (t *Tree) sum(n *node, counter chan int, wg *sync.WaitGroup) {
    defer wg.Done()

    if n.Left != nil {
        wg.Add(1)
        go t.sum(n.Left, counter, wg)
    }

    counter <- n.Data

    if n.Right != nil {
        wg.Add(1)
        go t.sum(n.Right, counter, wg)
    }

    return
}

// CountEdges ...
func (t *Tree) CountEdges() (edges int) {
    c := make(chan int, 10)
    if t.Root != nil {
        currentNode := t.Root
        if currentNode.Left == nil && currentNode.Right == nil {
            return 1
        }
        t.countEdges(currentNode, c)
    }

    for {
        n := <-c
        if n == 0 {
            close(c)
            break
        }
        edges++
    }
    return edges
}

func (t *Tree) countEdges(n *node, counter chan int) {
    if n.Left != nil {
        go t.countEdges(n.Left, counter)
    }

    if n.Left == nil && n.Right == nil {
        counter <- 0
    } else {
        counter <- 1
    }

    if n.Right != nil {
        go t.countEdges(n.Right, counter)
    }
    return
}

// GenerateRandomTree ...
func (t *Tree) GenerateRandomTree() {
    u := time.Now()
    source := rand.NewSource(u.Unix())
    r := rand.New(source)
    arr := r.Perm(1000)
    for _, a := range arr {
        t.Add(a)
    }
    return
}

// GetRootData ...
func (t *Tree) GetRootData() int {
    return t.Root.Data
}

// GetTreeTotal ...
func (t *Tree) GetTreeTotal() int {
    return t.Total
}

// TreeToArray ...
func (t *Tree) TreeToArray() []int {
    ch := make(chan int, 10)
    arr := []int{}
    if t.Root != nil {
        currentNode := t.Root
        if currentNode.Left == nil && currentNode.Right == nil {
            return []int{currentNode.Data}
        }
        t.traversalGetVals(currentNode, ch)
    }

    for {
        n := <-ch
        if n == -1 {
            close(ch)
            break
        }
        arr = append(arr, n)
    }
    return arr
}

func (t *Tree) traversalGetVals(n *node, ch chan int) {
    if n.Left != nil {
        ch <- n.Left.Data
        go t.traversalGetVals(n.Left, ch)
    }

    if n.Right != nil {
        ch <- n.Right.Data
        go t.traversalGetVals(n.Right, ch)
    }
    if n.Left == nil && n.Right == nil {
        ch <- -1
    }
    return
}

// ShiftRoot ...
func (t *Tree) ShiftRoot(newRoot int) {
    arr := t.TreeToArray()
    n := Tree{}
    n.Add(newRoot)
    for _, i := range arr {
        n.Add(i)
    }
    *t = n
}

// PrintTree ...
func (t *Tree) PrintTree() {
    b, err := json.MarshalIndent(t, "", " ")
    if err != nil {
        panic(err)
    }
    fmt.Println(string(b))
}

func main() {
    // t := Tree{}
    // t.GenerateRandomTree()
    // t.PrintTree()
    // fmt.Println("total:", t.Sum())

    t := Tree{}
    t.Add(10)
    t.Add(100)
    t.Add(2)
    t.Add(3)

    fmt.Println(t.Sum()) // should be 115
    fmt.Println(t.GetTreeTotal())

    // t := Tree{}
    // for i := 1; i <= 23; i++ {
    //  t.Add(i)
    // }
    // fmt.Println("total:", t.Sum())

}

- reticentroot

---

太厉害了！我还没有探索go routines的领域。但是请注意，我发布的测试中有16777216个（即2 ^ 23）叶节点，而不是23个。 - MaiaVictor

我没想到那个...哈哈，在这种情况下，求和函数需要更多的工作。首先，我正在使用一个缓冲通道，大小为十...可能更好的是将其增加...尽管我认为最好跟踪添加到树中的总数..因此在 Tree 结构中，在 Root 旁边添加 Total...这样你就不必一次计算所有内容。 - reticentroot

@MaiaVictor 我已经更新了帖子...现在不需要计算Sum。可以查询它。所以现在的限制因素是节点添加的速度有多快。 - reticentroot

Answer 3

主要问题在于分段内存分配（通过递归堆栈）。这会导致许多小的分配，随后垃圾回收器的工作量很大。您可以通过预先分配一个包含所有节点的数组并保持运行索引来避免这种情况：

bar.go

package bar

type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
    IsLeaf bool
}

func build(level int, curridx *int, src *[]Tree) *Tree {
    if level == 0 {
        (*src)[*curridx] = Tree{Left: nil, Value: 1, Right: nil, IsLeaf:true}
        *curridx++
        return &(*src)[*curridx-1]
    } else {
        (*src)[*curridx] = Tree{Left: build(level-1, curridx, src), Value: 1, Right: build(level-1, curridx, src)}
        *curridx++
        return &(*src)[*curridx-1]
    }
}

func sum(tree *Tree) int {
    if (tree.IsLeaf) {
        return tree.Value.(int)
    } else {
        return sum(tree.Left) + sum(tree.Right)
    }
}

bar_test.go

package bar

import "testing"
import "math"

func TestMe(t *testing.T) {
    for x := 0; x < 10; x++ {
        levels := 23
        nrnodes := int(math.Pow(2.0, float64(levels+1))) //there are actually 24 levels
        mapping := make([]Tree, nrnodes, nrnodes)
        index := 0
        t.Error(sum(build(levels, &index, &mapping)))
    }
}

这将加快每次迭代的速度至0.5秒。

请注意内置的性能分析： go test -cpuprofile cpu.out 和 go tool pprof cpu.out + web

- RickyA

---

这里的 sum 函数不正确。请注意数据类型，您只应该对叶节点求和。非叶节点上存在 Value 的唯一原因是我找不到如何在 Go 中表示 联合类型，所以我必须使用一个单一的结构体，并在分支节点中包含 Value int。 - MaiaVictor

回滚了，但这并不影响速度。 - RickyA