5 ms·

I have reimplemented the function in Julia and it took 16.51 seconds to run, compared to 0.19 seconds when running C version. Here is the code, perhaps someone

I have reimplemented the function in Julia and it took 16.51 seconds to run, compared to 0.19 seconds when running C version. Here is the code, perhaps someone else would know how to optimize it. CODE: function main(max_a0) longest = max_len = len = a = 0 for a0 in 1:max_a0 a = a0 len = 0 while a != 1 len += 1 a = ((a%2==0) ? a : 3*a+1)/2 end if len > max_len max_len = len longest = a0 end end println("($max_len, $longest)") end @time main(1000000) CMD: $ julia collatz.jl (329, 837799) elapsed time: 16.436623922 seconds (4206873264 bytes allocated) $ julia --version julia version 0.3.0-prerelease+143

antimora 13y ago
WOW, I was able to optimize down to 0.88 seconds by specifying type for a variable like this a::Int64. It's by a factor of 18.6! Here is the new code: function main(max_a0) longest = max_len = len = a = 0 for a0 in 1:max_a0 a = a0 len = 0 while a != 1 len += 1 a::Int64 = ((a%2==0) ? a : 3*a+1)/2 end if len > max_len max_len = len longest = a0 end end println("($max_len, $longest)") end @time main(1000000) CMD: $ julia collatz.jl (329, 837799) elapsed time: 0.882312881 seconds (1377276 bytes allocated)
- mhath 13y ago
  You can avoid allocating so much memory by changing a::Int64 = ((a%2==0) ? a : 3*a+1)/2 to a = ((a%2 == 0) ? a : 3a+1) >> 1 or a = div((a%2 == 0) ? a : 3a+1, 2) for me this gives (329, 837799) elapsed time: 0.449473338 seconds (544 bytes allocated) For reference the C version gives ./a.out 1000000 0.40s user 0.00s system 99% cpu 0.407 total
  - toolslive 13y ago
    what about: a = ((a & 0x01)? (a*3)+1 : a)>>1; anyway, when you think about it, you can skip everything between 0 and max_a0/2 because for any value there there is one with a longer chain (its double). that's a factor 2 in all languages.
    - mhath 13y ago
      Of course halving the range checked would also be an improvement. My own improvement was meant only to reduce the memory usage of antimora's code.
- KenoFischer 13y ago
  Indeed, the problem here is the type instability in the inner loop. There are a few optimization techniques that we intend to implement to deal with that but as you noticed, we're not quite there yet.
  - StefanKarpinski 13y ago
    This isn't really a missing optimization, but an understandable mistranslation of the C code – the / operator with integer operands doesn't mean the same thing in Julia as it does in C. In C it means div whereas in Julia it does floating point division.
    - KenoFischer 13y ago
      It's both. Declaring the `::Int64`, doesn't magically turn it into integer division, but it does insert a convert(Int64,...), hence all the speedup here is obtained through type stability, even though the algorithm is still different.
      - StefanKarpinski 13y ago
        Right, fair enough.

antimora 13y ago

WOW, I was able to optimize down to 0.88 seconds by specifying type for a variable like this a::Int64. It's by a factor of 18.6! Here is the new code: function main(max_a0) longest = max_len = len = a = 0 for a0 in 1:max_a0 a = a0 len = 0 while a != 1 len += 1 a::Int64 = ((a%2==0) ? a : 3*a+1)/2 end if len > max_len max_len = len longest = a0 end end println("($max_len, $longest)") end @time main(1000000) CMD: $ julia collatz.jl (329, 837799) elapsed time: 0.882312881 seconds (1377276 bytes allocated)

mhath 13y ago
You can avoid allocating so much memory by changing a::Int64 = ((a%2==0) ? a : 3*a+1)/2 to a = ((a%2 == 0) ? a : 3a+1) >> 1 or a = div((a%2 == 0) ? a : 3a+1, 2) for me this gives (329, 837799) elapsed time: 0.449473338 seconds (544 bytes allocated) For reference the C version gives ./a.out 1000000 0.40s user 0.00s system 99% cpu 0.407 total
- toolslive 13y ago
  what about: a = ((a & 0x01)? (a*3)+1 : a)>>1; anyway, when you think about it, you can skip everything between 0 and max_a0/2 because for any value there there is one with a longer chain (its double). that's a factor 2 in all languages.
  - mhath 13y ago
    Of course halving the range checked would also be an improvement. My own improvement was meant only to reduce the memory usage of antimora's code.
KenoFischer 13y ago
Indeed, the problem here is the type instability in the inner loop. There are a few optimization techniques that we intend to implement to deal with that but as you noticed, we're not quite there yet.
- StefanKarpinski 13y ago
  This isn't really a missing optimization, but an understandable mistranslation of the C code – the / operator with integer operands doesn't mean the same thing in Julia as it does in C. In C it means div whereas in Julia it does floating point division.
  - KenoFischer 13y ago
    It's both. Declaring the `::Int64`, doesn't magically turn it into integer division, but it does insert a convert(Int64,...), hence all the speedup here is obtained through type stability, even though the algorithm is still different.
    - StefanKarpinski 13y ago
      Right, fair enough.