`
aigo
  • 浏览: 2635790 次
  • 性别: Icon_minigender_1
  • 来自: 宜昌
社区版块
存档分类
最新评论

Benchmarking level generation: Go, Rust, Haskell and D (and now Scala).

阅读更多

原文:https://togototo.wordpress.com/2013/07/23/benchmarking-level-generation-go-rust-haskell-and-d/

该文章的测试时间是2013,下面的测试数据不代表当前各语言的最新版本

 

其他文章参考:

系统级编程语言性能大PK的笑话-Go语言

http://my.oschina.net/chai2010/blog/150379

 

I’m working on a random level generator for a game that, although written in C++, is modular such that the level generator can be written in something more high-level. As C++ isn’t always the most fun and productive language to program in, I set out to benchmark some potential alternatives, using a simple Roguelike level generation benchmark that relies heavily on iteration and conditionals and hence roughly mimics the actual generator. The code used is available here: https://github.com/logicchains/levgen-benchmarks. Any suggestions for improving the code used would be most welcome. The majority of the running time is spent on this (using the Haskell version as I think it’s the easiest to read):

roomHitRoom Room {rPos=(x,y), rw=w, rh=h} Room {rPos=(x2, y2), rw=w2, rh=h2}
| (x2 + w2 +1 ) < x || x2 > (x+w+1 ) = False
| (y2 + h2 +1 ) < y  || y2 > (y+h+1 ) = False
| otherwise = True

Checking a newly generated room against a list of previous rooms to see if they collide or not, discarding it if it does (it’s a brute-force level generation technique; the actual engine is a bit more sophisticated, but still relies on the same principle). Much of the rest of the time is spent on random number generation, so take these benchmarks with a grain of salt, as to a degree they’re as much a benchmark of the respective languages’ random number generators as they are of their general speed (i.e. these benchmarks are relevant to my goal, not necessarily yours. I enclose the generalisations made later in this post within the context of that statement).

All implementations now use the XorShift PRNG, with Rust, Go, C and D using the exact same code (a 32bit xorshift function), Scala using a 128-bit xorshift function, and Haskell using a 128-bit xorshift library. It is hence now less unreasonable to make comparisons between the languages, compilers and implementations.

The results are as follows:

Compiler Speed(s)  %Fastest  SLOC 
LDC 0.256 100% 107
Clang 0.279 92% 140
FCC* 0.283 90% 111
Rustc 0.303 85% 103
6g 0.323 79% 131
G++ 0.330 78% 127
Scala 0.344 74% 79
GCC 0.347 74% 140
LLVM-GHC 0.428 60% 78
GHC 0.546 47% 78
DMD 0.567 45% 136
GCCGO 0.598 43% 131

*A Redditor submitted a version in a language they’re working on called Neat, currently built on top of the LLVM and inspired by D; the compiler is here https://github.com/FeepingCreature/fcc. I was impressed by how a new language can take advantage of the LLVM like that to achieve the same level of performance as much maturer languages.

**Edit: Improvements to the D code make it now the fastest implementation. Most of the speedup came from rearranging the checkColl function to allow for better LLVM optimisation, but I’m not personally familiar enough with the language or the LLVM to explain the optimisations in question.  

The LLVM version used by LDC, Rust and Clang is 3.2. GCC and GCCGo used GCC version 4.7.3, while GDC used GCC version 4.6.4. Rust was version “0.8-pre (9da42dc 2013-07-17 04:16:42 -0700)”, GHC was version 7.6.2, DMD was 2.036 and 6g (Go) was 1.1.1. They were all run with 03 where available, –opt-level=3 for Rust, -release for DMD, and -funbox-strict-fields for Haskell. D now also runs with -inline and -noboundscheck.

D was the fastest non-C language tested, with Rust following close behind. It’s worth noting that for this task at least both D and Rust “beat C” at the same code, when comparing their results to the GCC C executable’s. The LLVM appears to do a much better job of optimising this kind of PRNG than GCC, showing how sometimes compiler effectiveness at optimising a given piece of code can be a bigger factor than language choice in determining speed. I will be excited to run these benchmarks again in a year’s time and see how Clang, LLVM D and LLVM Rust compare then.

Scala really surprised me; I didn’t realise a JVM language could run so fast for this kind of code. It even matched the speed of GCC C, putting a lie to the statement that languages running on a VM must necessarily be slower. Many thanks to markehammons for submitting the Scala code! Although I haven’t yet learned Scala, the code is surprisingly easy to read, and isn’t full of ugly optimisation code like I’d have expected a fast JVM program to be. Definitely a language worth considering even for speed-critical tasks.

Rust’s speed was impressive, for such a new language. Its flexibility with memory (optional GC) made it interesting to write in, however Rust’s flexibility (at least currently) comes at a slight price, as its syntax takes a bit of getting used to; to pass a heap-allocated vector by reference I need to use myFunc(& mut myVector) (even though it’s already a mutable vector), and the function receiving it needs myAlias:&mut~[myVector] in its type signature, like fn myFunc(myAlias:&mut ~[myVector]) {..}. Compared even to C ( void myFunc(struct MyType myAlias[arrayLength]){..} ), the Rust version looks a bit byzantine. For those who haven’t been following Rust, there are around seven different kinds of pointers: @ (garbage collected heap allocation), ~ (uniquely owned heap allocation), & (borrowed pointer to heap/stack allocation), * (raw C pointer, only useable in unsafe code), and mutable versions of the first three of those (actually, I’m not sure if there’s a mut & pointer, so maybe just six pointers in total). Note also that a pointer to a mutable value behaves differently than a pointer to a non-mutable value.

**Quoting kibwen on YCombinator:
“We’re moving the garbage-collected pointers (@) out into a library, so by default we’ll have only a single pointer, ~ (and there’s no mutable version of this). We’ll still have & and &mut, but those aren’t pointers, they’re references (it’s our own fault for calling them “borrowed pointers” in our documentation). So depending on how you count, that’s either one or three pointer types, which I’m happy with. The “unsafe” pointers exist only for C interop and have no bearing on normal code, so it’s inaccurate to count them.” So there’s actually really only three relevant kinds of pointer.

I also benchmarked a version of the Rust code using stack-allocated vectors, but there was no noticeable speed difference. I did however learn that stack-allocating vectors in Rust is currently rather verbose, as since uninitialised values aren’t allowed, I had to create an instance of the object I wanted an array of that had all its values set to zero and fill the vector with that upon creation. Hopefully in future Rust will adopt something like Go’s automatic initialisation of all values to zero, or at least have this as an option (or document it better, if it already is an option). Currently it looks like this:

**Apparently it is already possible, as described here: https://news.ycombinator.com/item?id=6094819. Hopefully it’ll be documented in the Rust tutorial next time it’s updated.**

let emptyr = Room {X:0,Y:0,W:0,H:0,N:0};
let emptyt = Tile{X:0,Y:0,T:0};
let emptyl = Lev{TS : [emptyt,..2500] , RS : [emptyr,..100] };
let mut ls : [Lev, ..100] = [emptyl,..100];

Which is a lot of unnecessary code, and would quickly become cumbersome in a large project that made heavy use of stack-allocated arrays (although there doesn’t seem to be a reason for doing so, as in this test at least they performed no faster than heap-allocated ones).

Go was impressive, performing well for a relatively new language albeit still falling behind D. The default PRNG was quite lacking in speed, so changing it to use XorShift resulted in a massive speedup. Interestingly, while GCCGo was faster with the default PRNG, the standard 6g runtime was faster with the bitshifted XorShift PRNG. The freedom from semicolons is a nice experience, and in terms of my subjective experience it was the most enjoyable language to write imperative code in. I’m quite looking forward to the development of LLVM Go.

Although it took me quite a while to optimise, I’m happy with Haskell’s performance, especially since it has to carry a vector of [initially] ten million random Ints around (random numbers can’t just be generated in the middle of functions, as that breaks purity). Writing recursively was a nice change, and the naive Haskell version was the most concise implementation of the languages tested (it grew significantly when I switched from lists to vectors and to the faster random number generator, as I couldn’t get pattern matching to work on vectors so had to stick [unsafe]Head and Tail everywhere).

**Updated the Haskell version to use MWC generator instead of Mersenne, and updated again to use more idiomatic code, resulting in a speedup to 0.770s. Updated yet again to use XorShift, now got the running time down to 0.546s. Running with -fllvm speeds it up to 0.428s.

Any more improvements to the Haskell code would be most welcome. Stay tuned for parallel level generation benchmarks! (Eventually..)

Finally, the moral of the story: there’s no such thing as a slow language, only an insufficiently optimising compiler.

Second moral of the story: if cryptographic-level randomness isn’t needed, then XorShift is the best PRNG algorithm available in terms of speed.

分享到:
评论

相关推荐

    Systems Performance:Enterprise and the Cloud

    Until now, however, little reliable, practical information has been available to IT professionals who are responsible for running these systems efficiently and cost-effectively. Systems Performance: ...

    Benchmarking with DEA, SFA, and R

    本部分所提及的书名为《Benchmarking with DEA, SFA, and R》,其内容侧重于讲述企业效率评价的最新方法,尤其是数据包络分析(Data Envelopment Analysis, DEA)和随机前沿分析(Stochastic Frontier Analysis, SFA...

    [Go语言入门(含源码)] The Way to Go (with source code)

    The Way to Go,: A Thorough Introduction to the Go Programming Language 英文书籍,已Cross the wall,从Google获得书中源代码,分享一下。喜欢请购买正版。 目录如下: Contents Preface......................

    Rust思维导图.pdf

    ### Rust 编程语言知识点详解 #### 一、基础概念 **1.1 简介** - **什么是 Rust:** Rust 是一门由 Mozilla 基金会开发的系统级编程语言,它专注于速度、内存安全性和并发性。Rust 的设计目标是在不牺牲性能的...

    pi-rust:使用 Rust 语言估算 Pi

    在本文中,我们将深入探讨如何使用 Rust 语言编写一个程序来估算圆周率 Pi。Rust 是一种系统级编程语言,以其内存安全、并发性和高性能而闻名。在 "pi-rust" 示例中,我们看到一个利用蒙特卡罗模拟方法来估算 Pi 的...

    The way to go

    go程序设计语言 Contents Preface................................................................................................................................. xix PART 1—WHY LEARN GO—GETTING ...

    benchmarking-talk:关于基准测试的演示项目

    安装如果未安装 Gradle: git clone https://github.com/danielmitterdorfer/benchmarking-talk.gitcd benchmarking-talk./gradlew shadowjava -jar build/libs/benchmarking-talk-0.1.0-all.jar或者,如果安装了 ...

    ethminer-0.16.0.dev3

    - realistic benchmarking against arbitrary epoch/DAG/blocknumber - on-GPU DAG generation (no more DAG files on disk) - stratum mining without proxy - OpenCL devices picking - farm failover (getwork + ...

    开源项目-gilbertchen-benchmarking.zip

    开源项目-gilbertchen-benchmarking.zip,A performance comparison of Duplicacy, restic, Attic, and duplicity

    Python_BenchMarking_Template:主要使用utils功能对代码进行基准测试,以查看运行该代码需要花费多少时间

    Python_BenchMarking_Template描述: 主要使用utils功能对代码进行基准测试,以查看运行该代码需要花费多少时间。编码标准: 项目使用干净代码和模块化的概念。前提条件None内容 作者信息姓名: SUGAANTH MOHAN 电子...

    Pro .NET Benchmarking.pdf

    使用此深度指南正确设计基准,测量.... 这本书提供了几十个案例研究,以帮助您... NET 特定的内容,而且还包括关于性能测量的基本知识,这些知识可以应用于任何语言或平台( 通用的基准方法、统计和现代硬件的低级特性)。

    Inside Microsoft SQL Server 2000

    Prototyping, Benchmarking, and Testing . Creating Useful Indexes . Monitoring Query Performance . Concurrency and Consistency Tradeoffs . Resolving Blocking Problems . Resolving Deadlock ...

    Benck mark.pdf

    ### Benchmarking的内涵 #### 1.1 什么是Benchmarking? Benchmarking,即标杆管理或基准管理,是一种通过比较自身业务流程与行业内最佳实践来进行自我评估和改进的管理方法。从字面上理解,“benchmark”一词原意...

    C++ benchmarking framework.zip

    C++ Benchmarking Framework 在软件开发中,性能测试和基准测试是至关重要的步骤,尤其是在优化代码和提升系统效率时。C++ Benchmarking Framework就是为了这个目的而设计的,它允许开发者评估和比较不同算法或实现...

    Performance Evaluation and Benchmarking DEA with Spreadsheets 2014

    Quantitative Models for Performance Evaluation and Benchmarking Data Envelopment Analysis with Spreadsheets 数据包络分析:绩效评估与标杆

    GO语言学习,持续更新.zip

    Go语言,又称Golang,是Google在2009年推出的一种静态类型的、编译型的、并发型的、垃圾回收的、C风格的编程语言。它的设计目标是提高开发者的生产力和系统的可扩展性,尤其适合云计算环境和大型分布式系统。 1. **...

Global site tag (gtag.js) - Google Analytics