为什么这个简单的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代码go build test.go并运行它time ./test.我已经运行了Node.js代码node test.js.经过多次测试后,Go程序2.5 平均运行大约几1.0秒钟,而Node.js则运行几秒钟.

这使得2.5x这个简单程序的Go 慢于Node.js,这是不正确的,因为Go是一个带有成熟编译器的静态类型的编译语言,而JavaScript是一个无类型的,解释的.

为什么我的Go程序这么慢？我错过了一些编译器标志,还是代码有问题？

Answer 1

摘要

由于类型断言和reduntant数据,此代码较慢.

Go不鼓励你在热门地方写类型断言:

tree.Value.(int) 

取出这种类型的断言(并相应地更改Value为int类型),并且您的代码将执行大约两倍的速度(这应该是您的节点示例的速度).

同时取出冗余数据,您的代码执行速度大约是原来的三倍.请参阅帖子末尾的游乐场示例.

细节

我认为这是设计的错误,而不是实施.阅读你的问题,我认为Go的类型系统如何运作存在一些混乱.

Go的对象模型不鼓励你使用catch-all类型进行多态性(有关Go的多态性的讨论,请参阅这个优秀答案的上半部分).

在JavaScript世界中,每个对象都是特定类型.在Go中,struct如果a符合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()是一种很好的例子,这种思维导致不决定通过泛型包含多态性.