Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 100.00%. Comparing base (763c8a4) to head (2a6d30e).

@@            Coverage Diff            @@
##              main      #194   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files           14        14           
  Lines         1635      1733   +98     
=========================================
+ Hits          1635      1733   +98     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

• ❄ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

It seems that compress can return Br and Bc with a different type (it's fine) and eltype (not fine)

• Br -> Matrix{Int64}
• Bc -> SparseArrays.SparseMatrixCSC{Bool, Int64}

ERROR: LoadError: MethodError: no method matching SparseMatrixColorings.JoinCompressed(::Int64, ::Int64, ::Int64, ::Matrix{Int64}, ::SparseArrays.SparseMatrixCSC{Bool, Int64}, ::Dict{Int64, Int64}, ::Dict{Int64, Int64})
The type `SparseMatrixColorings.JoinCompressed` exists, but no method is defined for this combination of argument types when trying to construct it.

I only got this error during the benchmarks.
All unit tests passed.

@gdalle
For row_color_ind and col_color_ind, I propose to use two Vector{Int} instead of two Dict{Int,Int}.
get_index will be faster and we will use less memory:

julia> a = Dict{Int,Int}(i => i+1 for i = 1:100)
julia> Base.summarysize(a)
4464

julia> b = Vector{Int}(undef, 100)
julia> Base.summarysize(b)
840

We have a factor 5 in terms of storage.

The reason why they are dictionaries is that not every color is used for a row, or for a column. But we could probably put zeros as indices for unused colors

@gdalle I rebased the branch but I will need your help to fix issue with compress for bicoloring.
It could return matrices Br and Bc of different types if one of them is empty.
The benchmarks are failing because of that.

Update: I fixed it. If the type of the matrice that we want to compress is Bool, we need to ensure to the type of the compressed matrix is Int. In the context of bicoloring, Br and Bc can have a different eltype because of that if the group of row colors / column colors is empty.

Benchmark Results

Hot damn!

I don't understand these results. I am wondering if Br and Bc are dense matrices or not in the benchmarks.
All other results are excellent.

I just profiled the problematic case and we're spending most of the time in the new getindex, as I feared. Even though both Br and Bc are dense.

On the other hand, in the previous version of the code (the one on main), I see that Br or Bc can be sparse (!!!). This means the benchmarking will be biased because they should be dense in the first place. I'll try to fix that first.

We also should use random ordering in the benchmarks, otherwise the results will be trivial.

I just merged the modifications from #198, the upcoming benchmarks will be more realistic

@amontoison the benchmarks are updated and now we don't see any significant speedups, but we still have the huge slowdowns on some instances. I'm not sure it's worth the memory savings, what do you think?

Another issue with the benchmarks is that, in the current state, we're unable to pre-allocate Br_and_Bc due to mismatched decompression_eltype. #199 fixes that

@gdalle

Note that I still need to do an efficient decompression for acyclic bicoloring.

@gdalle The PR is finally ready for review!