Slow array access during labeling algorithm

General Usage
,
1

Hi all,
I switched from Python to Julia and are currently implementing a column generation algorithm. Therefore, I created

struct Label
    cost             :: Float64 
    setReps          :: SBitSet{1,UInt128}
    node             :: Int64
    time             :: Float64 
    load             :: Int64
end

I have a function label_dominance(label::Label, label_comp::Label, inst::LabelInstance) to check whether one label dominates another. Labels are stored in all_labels= Matrix{Vector{Label}} for each node and time point (every node has a time window and time points outside this time window will always correspond to an empty vector).
The function check_dom_and_add_label!(all_labels::Matrix{Vector{Label}}, new_label::Label, inst::LabelInstance) checks if a new label is dominated by existing labels, removes dominated labels, and adds the new label:

function check_dom_and_add_label!(all_labels::Matrix{Vector{Label}}, new_label::Label, inst::LabelInstance)
    # check whether new_label is dominated by existing labels 
    node= new_label.node
    
    lb= inst.lbTW[node]
    time_label= label.time
    for t=lb:time_label
        labels= all_labels[t,node]
        if isempty(labels)
            continue 
        end 
        for i in eachindex(labels)
            exis_label= labels[i] 
            if label_dominance(exis_label, new_label, inst)
                return false     
            end 
        end
    end 

    # check whether new_label dominates existing labels 
    ub= inst.ubTW[node]
    for t=time_label:ub
        labels= all_labels[t,node]
        if !(isempty(labels))
            deleteat!(labels, (i for i in eachindex(labels) if label_dominance(new_label, labels[i], inst))) 
        end
    end

    # add new_label
    push!(all_labels[time_label, node], new_label)                   
    
    return true
end

After profiling the code, the profiler indicated that almost all time is spend within check_dom_and_add_label! , and about 80% of that time is spend on get_index (e.g., 60% of the time is spend on exis_label= labels[i] ). This seems counterintuitive for me, as I would expect more time to be spend inside the function label_dominance.

Can anyone explain why accessing the elements of an array is so time consuming? Could this potentially indicate other problems in my code?

Thanks!

2

Are you talking about column generation in optimization?

3

Yes indeed. I use the labeling algorithm to find a column with negative reduced cost.

4

I think you might get more and better answers if you provide a complete, runnable MWE as described in item 4 of this post.

5

Also tagging with the specific domain tag for optimization Optimization (Mathematical) - Julia Programming Language would help route it to more people who might be able to help.