[swift-users] problems with simple binary-trees program

Pascal Urban mail at pscl.de
Sun Dec 20 11:58:13 CST 2015


> A simple Swift program that completed the workloads within an hour time-out would be an incredible improvement :-)
> 
> Instead of looking at the "Winners" compare with the TypeScript program
> 
> http://benchmarksgame.alioth.debian.org/u64q/program.php?test=binarytrees⟨=typescript&id=2
> 
> Why does a Swift transliteration of that program perform so slowly?
> 


Both of these implementations are slow because they always create binary trees with a depth of maxDepth instead of, well, the correct depth.
Changing the following lines (and the respective lines in David's implementation) leads to a more reasonable runtime:

check += bottomUpTree(i,maxDepth).check()
check += bottomUpTree(-i,maxDepth).check()

to

check += bottomUpTree(i,depth).check()
check += bottomUpTree(-i,depth).check()

On my MacBook (i5, 2.6GHz) I get:

n=20
David: ~16 - 17s
Isaac: ~120 - 126s

Because all of the winners are doing it:
Here is a quickly thrown together parallel version of David's implementation using libdispatch (contains also the fixes from above):
https://gist.github.com/psclde/8244c4350b1d4fd1b24b

This version takes about 7 - 8s for n=20.

But libdispatch is currently not working on Linux so it's not really relevant for the benchmark.

Pascal



More information about the swift-users mailing list