Can someone look over my code and identify the error (Linux)

In my experiments I have been working with the Collatz Conjecture. I thought about running it using multi-threading and it worked when I gave it low number but then seemed to topple over when I started giving it bigger ranges to test.

import Base.Threads.@spawn

StepsTaken = []
Limit = BigInt(2)^17

function calculate(n)
	step = 0
    Number = n
    
    while (Number ≠ 1)
        if Number % 2 == 0
            Number = Number / 2
            step += 1
        elseif Number % 2 > 0 
            Number = Number * 3 + 1
            step += 1
        end
    end

	append!(StepsTaken, step)
end

for i in 2:Limit
	k = @spawn calculate(i)
end

println(StepsTaken)
println("Completed!")

Where Limit = BigInt(2)^17 it works fine. However, any powers greater then 17 generates the following error.

double free or corruption (out)

signal (6): Aborted
in expression starting at /home/james/julia-1.5.3/bin/array.jl:27
gsignal at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
abort at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x7fa6d68753ed)
unknown function (ip: 0x7fa6d687d47b)
unknown function (ip: 0x7fa6d687f11f)
jl_realloc_aligned at /buildworker/worker/package_linux64/build/src/gc.c:249 [inlined]
gc_managed_realloc_ at /buildworker/worker/package_linux64/build/src/gc.c:3376 [inlined]
jl_gc_managed_realloc at /buildworker/worker/package_linux64/build/src/gc.c:3393
array_resize_buffer at /buildworker/worker/package_linux64/build/src/array.c:660
jl_array_grow_at_end at /buildworker/worker/package_linux64/build/src/array.c:875 [inlined]
jl_array_grow_end at /buildworker/worker/package_linux64/build/src/array.c:939
_growend! at ./array.jl:892 [inlined]
resize! at ./array.jl:1085 [inlined]
_append! at ./array.jl:987 [inlined]
append! at ./array.jl:981
unknown function (ip: 0x7fa6ba8775e9)
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2214 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2398
calculate at /home/james/julia-1.5.3/bin/array.jl:20
#1 at ./threadingconstructs.jl:169
unknown function (ip: 0x7fa6ba87729c)
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2214 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2398
jl_apply at /buildworker/worker/package_linux64/build/src/julia.h:1690 [inlined]
start_task at /buildworker/worker/package_linux64/build/src/task.c:705
unknown function (ip: (nil))
Allocations: 139211030 (Pool: 139210836; Big: 194); GC: 23
Aborted (core dumped)

I am running Julia on Linux Mint (latest) using the official binaries off the website. The CPU is a Ryzen 5 with 8GB RAM. I am then running my code as

JULIA_NUM_THREADS=4 ./julia array.jl

Where array.jl is the program to run.

Have I hit some sort of limit on my CPU/RAM?

Just a humble and honestly friendly tip: if you sketched already in the subject of your post the technical essence of your problem (I do not know, maybe something like “Problems with multithreading and hitting the memory limits”?), your chances of getting a qualified answer would be higher. Every other post here is some sort of a request for help with a code.

3 Likes
append!(StepsTaken, step)

This line is a big problem, you have multiple threads appending to the same array. So 2 (or more threads) could try to increase the size, or even write to the same location. You could do something like:

import Base.Threads.@spawn

StepsTaken = []
Limit = BigInt(2)^17
Chan = Channel{Int}()

# Everything in a big sync block to make sure 
# it's done before moving to the next step.
@sync begin 

    # Single task that adds the steps to StepsTaken
    @async begin
        for step in Chan
            append!(StepsTaken, step)
        end
    end

    function calculate(n)
    	step = 0
        Number = n
    
        while (Number ≠ 1)
            if Number % 2 == 0
                Number = Number / 2
                step += 1
            elseif Number % 2 > 0 
                Number = Number * 3 + 1
                step += 1
            end
        end
    
        put!(Chan, step)
    end
 
    # Another sync block, we don't want to close the channel until
    # we're done adding to it.
    @sync for i in 2:Limit 
    	k = @spawn calculate(i)
    end

   # Close the channel so the task appending to StepsTaken finishes.
   close(Chan) 

end

println(StepsTaken)
println("Completed!")
2 Likes

I do agree with you here and the “Can you make this code faster?” questions really bug me.

1 Like

@zdenek_hurak & @pixel27 Thank you for replies. I am sorry maybe I could have worded the first post better so that it makes the process easier. I do apologies for that.

I am still wrapping my head around the multithreaded approach and the tutorials I have followed never mentioned anything about the need to sync it all. So that is dumb ignorance on my part.

It’s no problem, multi-threading brings in all new issues you have to watch out for. The key is to watch out with multiple thread changing the same object. You made me start thinking about your code some more. Another option is:

StepsTaken = Vector{Int}(undef, Limit-1)

...

function calculate(n)
   ...
   StepsTaken[n-1] = step
end
``
This would remove the @async block reading the channel (and the channel).  Basically you have each instance of the function write to it's own location in the Vector (and the vector's length doesn't change) so you are thread safe.  You still want the sync in your for loop, so it doesn't exit until the spawned tasks finish.
2 Likes

Thank you. I think for the process of using multithreading might be a little ott at the moment. But thank you for explaining that it was because I wasn’t using any kind of syncing.

Another suggestion:
The two operations (three with check for even/uneven) needed for Collatz are quite easy to implement in a binary representation. Julia seems to be great to do this in self defined types. With that you will be open for very large numbers:
n/2 is binary of course straight forwards.
3n+1 = 2n + n + 1 which again is binary very easy.