search

frol / completely-unscientific-benchmarks

Naive performance comparison of a few programming languages (JavaScript, Kotlin, Rust, Swift, Nim, Python, Go, Haskell, D, C++, Java, C#, Object Pascal, Ada, Lua, Ruby)
Apache License 2.0
542 stars 70 forks source link

Can we use non-recursive techniques? #67

Closed johnperry-math closed 5 years ago

johnperry-math commented 5 years ago

Hello

I tried to implement this in Eiffel. Unlike many of the languages used here, Eiffel doesn't allow one to modify arguments to a procedure, so I had to work around this by boxing the arguments. This requires me to perform a lot of copying, which slows the code significantly. (I noticed that the Python code seems to do the same thing.)

One way to get around this (recommended by some Eiffel gurus) is to use non-recursive techniques. The easiest to see would be has_value(), because checking whether the tree has a value can be done with a simple loop that descends into the tree. On the other hand, it can give an unfair advantage to this one procedure because it's no longer detaching & re-attaching nodes the way as this version does via split() and merge().

So: for languages that don't allow one to modify arguments to a procedure, is it acceptable to use a different technique if that improves timing, so long as the resulting work is "the same"?

For what it's worth, changing has_value() to a loop cut running time by 33%.

frol commented 5 years ago

We deliberately choose the algorithm and it must be exactly the same in order to compare languages. Thus, it is unacceptable to optimize the algorithm.

johnperry-math commented 5 years ago

Thanks! I figured that would be the case, but it can't hurt to ask!

frol commented 5 years ago

Sure! No problem with asking. I'm glad you find this benchmark interesting, and you are welcome to make contributions ;)