5 ms·
Look at the Go benchmark program: https://benchmarksgame-team.pages.debian.net/benchmarksgame/program/binarytrees-go-8.html https://benchmarksgame-team.pages.d
by tossaway32 5y ago
Look at the Go benchmark program:
https://benchmarksgame-team.pages.debian.net/benchmarksgame/program/binarytrees-go-8.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
Needs to be faster? Use a pool like the C benchmark programs, but super simple: just a slice, local to the goroutine.
Trivially make the Go program 10x faster, 5 minutes of work, a few edits:
type Tree struct {
Left int
Right int
}
func itemCheck(id int, pool []Tree) uint32 {
tree := &pool[id]
if tree.Left != -1 && tree.Right != -1 {
return uint32(1) + itemCheck(tree.Right, pool) + itemCheck(tree.Left, pool)
}
return 1
}
func bottomUpTree(depth uint32, pool *[]Tree) int {
var tree Tree
if depth > uint32(0) {
tree.Left = bottomUpTree(depth-1, pool)
tree.Right = bottomUpTree(depth-1, pool)
} else {
tree.Left = -1
tree.Right = -1
}
id := len(*pool)
*pool = append(*pool, tree)
return id
}
func inner(depth, iterations uint32) string {
var (
pool []Tree
chk = uint32(0)
)
for i := uint32(0); i < iterations; i++ {
a := bottomUpTree(depth, &pool)
chk += itemCheck(a, pool)
pool = pool[:0]
}
return fmt.Sprintf("%d\t trees of depth %d\t check: %d",
iterations, depth, chk)
}
If it matters, your Go program can be made as fast as a C program.
Easily.
- dandotway 5y agoWould you mind posting a complete example that compiles and runs? Your above changes to Go#8 break it. E.g. the function 'run' needs to be updated to use your new 'bottomUpTree' and 'inner'.
- tossaway32 5y agoI'm not going to paste 170 lines of code into the thread. Add this line: var pool []Tree to each of the stretch and long-lived closures in run(), pass &pool as the second argument to bottomUpTree(), pass pool as the second argument to itemCheck(). The call to inner() doesn't change. It's trivial.
- dandotway 5y ago+1 Not bad, your simple pool improved performance from about 10.9 secs to 1.4 secs on my laptop here. However, it does break the stated rules for the benchmark.[1] The Java version doesn't use a pool and doesn't change Tree pointers into ints as your version does. The C/C++/Rust versions are required to use a "library memory pool." The rules state, Please don't implement your own custom "arena" or "memory pool" or "free list" - they will not be accepted." Donald Knuth uses integers instead of proper pointers in the source code for TeX for maximum portability and performance so your technique is legit used by master programmers but in general replacing pointers with integer indices into arrays only works for monolithic programs of small to medium size. For example, could the Chromium maintainers rewrite the 20 million lines of C++ into Golang replacing most pointers with integer offsets into arrays for performance? No, impossible with current tools and practices, the technique won't scale to that, so this benchmark rule isn't totally stupid and unfair. This binary trees benchmark was originally devised decades ago by Hans Boehm, a notable GC researcher, as a way of testing GC performance that he as a GC implementer found informative. [1] https://benchmarksgame-team.pages.debian.net/benchmarksgame/description/binarytrees.html#binarytrees https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
- tossaway32 5y agoYou don't rewrite your whole program to use pooled allocations. Just the parts of your program where allocation performance needs to be improved. If part of your program is doing many allocations, and it's too slow, use a simple pool. Go makes pooled allocation easy and safe. I have written huge Go programs (e.g., https://NN-512.com https://NN-512.com), and the garbage collector is not a problem. Quite the opposite, it's a major, major benefit. Pooled allocations are rarely needed.
- sigmaml 5y agoSeveral (about 10) years ago, I submitted essentially the same program. It was one of the fastest of all the implementations across all the languages. However, Isaac rejected it, saying it violated the conditions.
- tex0 5y agoDebian Maintainers doing Debian Things.
- lifthrasiir 5y agoOf course. The problem description [1] specifically calls for the following: When possible, use default GC; otherwise use per node allocation or use a library memory pool. As a practical matter, the myriad ways to tune GC will not be accepted. As a practical matter, the myriad ways to custom allocate memory will not be accepted. Please don't implement your own custom "arena" or "memory pool" or "free list" - they will not be accepted. In the other words, this problem measures the memory allocation performance with the "natural" strategy, which is either a default GC, a memory pool or a per-node allocation in the order of availability. If the target implementation doesn't support GC by default the code would be necessarily more complex, which makes up the performance benefit. So you can't really compare submissions with different strategies, because they are just doing different things and there is no reasonable way to make them do the same thing [2]. [1] https://benchmarksgame-team.pages.debian.net/benchmarksgame/description/binarytrees.html#binarytrees https://benchmarksgame-team.pages.debian.net/benchmarksgame/... [2] You may still argue that every submission should use a per-node allocation for the fair comparison, but a per-node allocation with GC and without GC is pretty different.
- sigmaml 5y agoMy submission did violate the conditions. I was just recollecting what happened; it is not a complaint. I am at variance with those conditions, though. I refer to the benchmarks suite itself, broadly. When programs dip into GMP, PCRE, etc., we are no longer comparing the speeds of the different language implementations per se. Now, they are mixed with FFI speeds of those implementations, the choices of the foreign language libraries/algorithms, etc.. In the same vein, as you remark in your second footnote, for a fair comparison, the same algorithm should be used in all programs. That will shed light on the strengths and weaknesses of the different language implementations better. I don't intend to say that the current system is useless; I am saying that using the same set of algorithms is likely to be more illustrative.
- azth 5y agoNow do the same in Java and it will be as fast, if not faster. The point is the benchmark is looking at GC performance. In large real world programs, it is not trivial to make such changes.
- tossaway32 5y agoDo it. Show me that Java can avoid allocating/collecting the Tree objects. Go has no indirection for the Tree objects, in this example. The Trees are contiguous in memory. Measure the performance. I have no garbage collection performance problems in the various large Go projects I have worked on. But I am also a competent programmer, so "your mileage may vary".
- azth 5y agoFor the time being, until Valhalla is finalized, Java can emulate this approach simply by using an int array. After making the modifications, on my local machine, Java ran as low as ~820ms, compared to golang's ~932ms. golang's GC is no silver bullet as we see here: * https://blog.discord.com/why-discord-is-switching-from-go-to-rust-a190bbca2b1f https://blog.discord.com/why-discord-is-switching-from-go-to... * https://news.ycombinator.com/item?id=21670110 https://news.ycombinator.com/item?id=21670110
- tossaway32 5y agoThanks for doing the test!
- azth 5y agoNo problem. I'll try to download a Valhalla JVM build and see how it fairs.
- tossaway32 5y agoHow does Java do without using an array of ints, or Valhalla? In other words, what's the cost of Java's forced indirection? What happens if you use pool := make([]Tree, 0, 256) instead of var pool []Tree in the Go so it doesn't waste time growing tiny slices?