# Tower hanoi in julia vs java - recursive function
**URL:** https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399
**Category:** Performance
**Created:** [January 5, 2024, 4:56pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399 "2024-01-05T16:56:21Z")
**Posts on this page:** 15
**Page:** 1
### Author:  [@fab6](https://discourse.julialang.org/u/fab6)
#### Post date: [January 5, 2024, 4:56pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/1 "2024-01-05T16:56:21Z")
Hi,
I am comparing a simple recursive function for the tower of hanoi in julia with java.
This is the java code:
```java
class hanoi
{
static void towerOfHanoi(int n, char source, char target, char helper)
{
if (n == 1)
{
System.out.println("Move disk 1 from source " + source + " to rod " + target);
return;
}
towerOfHanoi(n-1, source, helper, target);
System.out.println("Move disk " + n + " from rod " + source + " to rod " + target);
towerOfHanoi(n-1, helper, target, source);
}
public static void main(String args[])
{
int n = 15; // number discs
towerOfHanoi(n, 'A', 'C', 'B');
}
}
```
And this is the one in julia
```julia
function towerOfHanoi(n::Int, source::String, target::String, helper::String)
if (n == 1)
println("Move disk 1 from source $source to target $target ")
return
end
towerOfHanoi(n - 1, source, helper, target)
println("Move disk $n from source $source to target $target ")
towerOfHanoi(n - 1, helper, target, source)
end
n::Int = 15 # number discs
towerOfHanoi(n,"A"::String, "C"::String, "B"::String)
```
The julia code is much slower (depending on the number of discs and depending on the print-commands). Julia 0.64s and java 0.38s with simple `time` call on a macos system. It is julia 1.9.0.
Do you have some hint, how to improve the julia code?
I saw some other discussion that small recursive functions might not work to well in julia, but maybe my current setup is really not good. And I did not test it with 1.10 yet, which should be faster for this than 1.9.0, but was thinking that there might be some other improvements!?
Thank you in advance!
Fab
---
### Author:  [@mbauman](https://discourse.julialang.org/u/mbauman)
#### Post date: [January 5, 2024, 5:06pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/2 "2024-01-05T17:06:17Z")
How are you running the code and where is the output going? You’re not so much testing the performance of recursive functions as you are IO (the `println`s) and compilation. Depending on how I measure the Julia code, I can get numbers anywhere from 0.013s (looking at `@time towerOfHanoi(...)` with output going to a file) to 2.8 seconds (looking at `time julia test.jl`, outputting to a fancy terminal).
As an aside, all those type annotations in the Julia code are superfluous and don’t impact performance.
---
### Author:  [@fab6](https://discourse.julialang.org/u/fab6)
#### Post date: [January 5, 2024, 5:30pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/3 "2024-01-05T17:30:04Z")
Thank you for your quick reply!
Yes you are right, I tested before without the println in Julia and in java.
Here are some examples where I removed the IO print lines.
This is what I get for n=15 in julia
```julia
time julia hanoi_java.jl
julia hanoi_java.jl 0.19s user 0.13s system 86% cpu 0.367 total
```
for same number in java
```julia
time java hanoi
java hanoi 0.03s user 0.04s system 53% cpu 0.131 total
```
and n=30 in julia
```julia
time julia hanoi_java.jl
julia hanoi_java.jl 2.08s user 0.14s system 96% cpu 2.298 total
```
and in java
```julia
time java hanoi
java hanoi 1.19s user 0.04s system 97% cpu 1.249 total
```
Next with n=35
in julia:
```julia
time julia hanoi_java.jl
julia hanoi_java.jl 61.54s user 0.61s system 97% cpu 1:03.67 total
```
and java
```julia
time java hanoi
java hanoi 29.65s user 0.20s system 99% cpu 30.098 total
```
---
### Author:  [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)
#### Post date: [January 5, 2024, 5:35pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/4 "2024-01-05T17:35:12Z")
> [@fab6](#):
>
> `time julia hanoi_java.jl`
This measures julia startup time (which is improved, but can be long) and compilation time in addition to the actual run time.
> [@fab6](#):
>
> `time java hanoi`
Here you must have already compiled hanoi.java with javac. To make a farier comparison with the julia measurement, you need to time both javac and java.
Most julia performance measurement is done using `@time` or `@btime` in the source code. `@time` on the first invocation will include compilation time. A second invocation will include only the runtime. `@btime` does repeated invocation automatically so that you can easily see the true runtime performance without compilation time.
---
### Author:  [@fab6](https://discourse.julialang.org/u/fab6)
#### Post date: [January 5, 2024, 5:51pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/5 "2024-01-05T17:51:53Z")
Thank you!
yes, good comment about the compilation, this is what I get as quick test for javac
```julia
time javac hanoi.java
javac hanoi.java 0.87s user 0.08s system 176% cpu 0.538 total
```
I thought using `time` is for a quick test enough as it is easier to compare with java.
Below is a @btime output for n=35 and the code:
```julia
julia hanoi_java.jl
60.052 s (0 allocations: 0 bytes)
```
```julia
using BenchmarkTools
function towerOfHanoi(n::Int, source::String, target::String, helper::String)
if (n == 1)
# println("Move disk 1 from source $source to target $target ")
return
end
towerOfHanoi(n - 1, source, helper, target)
# println("Move disk $n from source $source to target $target ")
towerOfHanoi(n - 1, helper, target, source)
end
n::Int = 35 # number discs
@btime towerOfHanoi(n,"A"::String, "C"::String, "B"::String)
```
Probably there are better ways to benchmark this… Though, I understand, that there is for this case not so much to improve the actual code.
---
### Author:  [@mkitti](https://discourse.julialang.org/u/mkitti)
#### Post date: [January 5, 2024, 5:54pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/6 "2024-01-05T17:54:34Z")
> [@fab6](#):
>
> `time java hanoi`
Did you time the `javac` step?
Alternatively try `time java hanoi.java` after removing the class files.
The point is that `julia hanoi_java.jl` includes a compilation step. If you would like to remove compilation from the benchmark, we can help you do that.
Edit: I’m reading your latest post.
---
### Author:  [@mbauman](https://discourse.julialang.org/u/mbauman)
#### Post date: [January 5, 2024, 5:59pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/7 "2024-01-05T17:59:09Z")
It’s perhaps also worth noting that without the prints, a sufficiently advanced compiler could choose to optimize everything away to simply `return;` in either language. Benchmarking is hard 🙂
---
### Author:  [@fab6](https://discourse.julialang.org/u/fab6)
#### Post date: [January 5, 2024, 6:02pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/8 "2024-01-05T18:02:37Z")
Yes, no problem and thank you all for the comments and help. I was just thinking that I do something totally wrong.
---
### Author:  [@mkitti](https://discourse.julialang.org/u/mkitti)
#### Post date: [January 5, 2024, 6:57pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/9 "2024-01-05T18:57:39Z")
I just noticed that you are using `String` in Julia and `char` in Java. Julia has `Char` and also has single quote syntax for them.
```julia
function towerOfHanoi(n::Int, source::Char, target::Char, helper::Char)
if (n == 1)
println("Move disk 1 from source $source to target $target ")
return
end
towerOfHanoi(n - 1, source, helper, target)
println("Move disk $n from source $source to target $target ")
towerOfHanoi(n - 1, helper, target, source)
end
n::Int = 15 # number discs
towerOfHanoi(n, 'A', 'C', 'B')
```
I’m not sure if that matters for performance or not yet.
---
### Author:  [@mbaz](https://discourse.julialang.org/u/mbaz)
#### Post date: [January 5, 2024, 7:52pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/10 "2024-01-05T19:52:58Z")
> [@fab6](#):
>
> `time julia hanoi_java.jl`
To improve the accuracy of this benchmark, it’s a good idea to run Julia with `julia --startup-file=no`. This prevents Julia from running your config file, which may take substantial time.
In my case, for example:
```julia
0 [~] time julia -e "1+1"
real 0m0.299s
user 0m0.445s
sys 0m0.276s
0 [~] $ time julia --startup-file=no -e "1+1"
real 0m0.126s
user 0m0.077s
sys 0m0.055s
0 [~] $
```
---
### Author:  [@fab6](https://discourse.julialang.org/u/fab6)
#### Post date: [January 7, 2024, 12:42pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/11 "2024-01-07T12:42:56Z")
Yes, thank you for you advice
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [January 7, 2024, 1:27pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/12 "2024-01-07T13:27:23Z")
> [@mbaz](#):
>
> To improve the accuracy of this benchmark, it’s a good idea to run Julia with `julia --startup-file=no`.
You have to decide what you want to benchmark. Do you want to benchmark Julia startup time? Then time launching Julia how you normally do … your script doesn’t even need to do anything. Do you want to benchmark “recursive functions” in Julia? Then use BenchmarkTools.jl and put a `@btime` statement **inside** your script (so that it doesn’t include startup/compilation time).
The reason that we normally don’t include startup/compilation time in benchmarks is that synthetic benchmarks are usually toy versions of real-world problems, where in the real problem you care about performance because you are running similar calculations _many_ more times. In such cases, the startup time is irrelevant (it doesn’t scale with the size of the problem).
---
### Author:  [@Mason](https://discourse.julialang.org/u/Mason)
#### Post date: [January 7, 2024, 1:32pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/13 "2024-01-07T13:32:32Z")
Given that the OP reported that for `n=35`, julia was taking over a minute to run, and Java was 30 seconds, I seriously doubt this is explained by julia’s slow startup times.
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [January 7, 2024, 1:37pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/15 "2024-01-07T13:37:48Z")
For the original problem in this thread, it ran in \< 1s, in which case startup time is significant.
I agree that once the problem time is in the 10s of seconds, startup time doesn’t matter and benchmarking is much easier.
---
### Author:  [@sgaure](https://discourse.julialang.org/u/sgaure)
#### Post date: [January 7, 2024, 3:58pm UTC](https://discourse.julialang.org/t/tower-hanoi-in-julia-vs-java-recursive-function/108399/16 "2024-01-07T15:58:33Z")
That’s an interesting case. About half of the instructions generated by julia are `push` and `pop`. I don’t know what java generates. This could be some heuristic in LLVM’s register allocation which is unfortunate in this case. The function without IO doesn’t really do anything except a subtraction and the two calls, so saving a bunch of registers in every call seems ineffective.