[swift-users] problems with simple binary-trees program
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
> 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()
check += bottomUpTree(i,depth).check()
check += bottomUpTree(-i,depth).check()
On my MacBook (i5, 2.6GHz) I get:
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):
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.
More information about the swift-users