unexpected allocation in this code

[freddycct]

Some of my functions contains a loop that operates on an array which occupies a big chunk of memory. But no data is created or destroyed in those loops. Julia should detect that and avoid calling the GC in these loops. This will significantly improve performance. Infact, knowing when to call GC can lead to significant improvements in the code execution.

[johnmyleswhite]

I suspect this issue would be easier to address if you could include an example of complete code where GC is the main performance bottleneck and where GC could be turned off with provable safety.

[freddycct]

function speed_estimation(iterations::Int64, records::Array{Record}, 
    bus_stops::Dict{Int64, Bus_Stop}, bus_services::Dict{ASCIIString, Bus_Service}, 
    eta::Float64, tau::Float64, total_hops::Int64)
    # iteration starts
    for iter=1:iterations
        # shuffle it
        @printf("Iteration: %d/%d", iter, iterations)

        tic()
        shuffle!(records) # potentially expensive operation
        time_elapsed = toq()
        @printf(", Shuffling takes: %f secs", time_elapsed)
        flush(STDOUT)

        tic()
        for record in records
            # determine the routes
            # get the bus service number
            bus_no = record.bus_no
            bus_service = bus_services[bus_no]

            # get the origin and dest
            origin_id = record.origin
            destination_id = record.destination

            # get the direction
            direction = record.direction

            # retrieve the list_nodes associated with them
            bus_stops_dict = bus_service.bus_stops[direction]

            #@printf("bus: %s, orig: %d, dest: %d, dir: %d\n", bus_no, origin_id, destination_id, direction)

            origin_node = bus_stops_dict[ bus_stops[origin_id] ]
            destination_node = bus_stops_dict[ bus_stops[destination_id] ]

            # stochastic gradient descent of the segment speeds
            # iterate through the segments, must find an easy way of doing this...

            # the segments between origin and destination requires SGD update

            # first find the sum of the times
            tmp = summation_time(origin_node, destination_node)

            current_node = origin_node
            while current_node != destination_node
                #get bus stop of node
                src_bus_stop = current_node.bus_stop
                tar_bus_stop = current_node.next.bus_stop

                edge = src_bus_stop.edges[tar_bus_stop]

                dist = edge.distance
                speed = edge.speed

                # deduct from tmp
                tmp2 = tmp - (dist/speed)

                # this is the stochastic gradient descent !!!
                speed = speed - eta * ((record.time_taken-tmp)*(dist/(speed*speed))-(tau/speed))

                if speed <= 0
                    println("Violate constraints!")
                    edge.speed = 0.1
                    #break
                else
                    edge.speed = speed
                    #println(edge.speed)
                end

                # add it back to tmp
                tmp = tmp2 + (dist / speed)
                current_node = current_node.next
            end # end while loop
        end # end for loop
        # calculate the RMSE
        time_elapsed = toq()
        @printf(", SGD takes: %f secs", time_elapsed)
        #squared_error = calculate_squared_error(records, bus_stops, bus_services)
        #@printf(", per: %f secs\n", time_elapsed / length(records))
        @printf(", per: %e secs\n", time_elapsed / total_hops)
        #@printf(", error: %f\n", squared_error)
        flush(STDOUT)
    end # end of this iteration
    # loop this iteration
end

None of the code here does any form of new() but the memory increases significantly after looping for a short while. Disabling the GC also improves the performance significantly, please let me know if there is any code here that misuse more memory than it should..

[edit by @ihnorton: quotes around code]

[JeffBezanson]

The compiler will generate code that allocates memory as necessary. If your data types store numbers, do their fields have specific declared types? If not, it will cause allocation of boxed numbers.

[freddycct]

I have declared types for all of them. So far, I am adding gc_disable() before each loop and gc_enable(), gc() after each loop. Maximum memory usage is 10GB now. I am pretty convinced that Julia needs a better GC to compete with Java...

I hope gc improves soon, as I am currently using Julia for a really huge project.

[JeffBezanson]

As it happens, there is already a large GC improvement waiting to be merged here: #5227
Java's GC is extremely good.

The @time macro will report bytes allocated. Could you try wrapping bits of the code with @time begin ... end to see if we can narrow down where memory is getting allocated?

[timholy]

I find the Profiler + ProfileView is the easiest way to figure out problematic lines: it will highlight in red any lines that trigger garbage collection.

[freddycct]

abstract EdgeAbstract

type Bus_Stop
id::Int64
edges::Dict{Bus_Stop, EdgeAbstract}
end

type Edge <: EdgeAbstract
src::Bus_Stop
tar::Bus_Stop
speed::Float64
distance::Float64
end

I have isolated the problem. It is this circular dependency that is currently not supported in Julia that causes the loosely typed code and memory allocation problem.

I subsequently remove the circular dependency and the abstract type. Now the code works fast. So GC does not work well for circular dependency...

[timholy]

The GC handles circular references just fine. The problem is that Bus_Stop is not a concrete type. See a lengthy explanation here:
http://docs.julialang.org/en/latest/manual/faq/#how-do-abstract-or-ambiguous-fields-in-types-interact-with-the-compiler
Also be sure to read the section after that one.

You should make your Bus_Stop a parametric type, then it would be concrete and you would likely avoid any allocation.

[JeffBezanson]

For example:

type Bus_Stop{T<:EdgeAbstract}
  id::Int64
  edges::Dict{Bus_Stop, T}
end