CoordinateDescent performance vs. sklearn

[mileslucas]

Hi all,

I'm using NMF for an image-processing algorithm and there are noticable performance differences between the implementation using NMF.jl and the implementation using sklearn.decomposition.NMF

In my package, I have a benchmark showing performance for my alg vs. the python implementation here. Basically, the julia version is 1.5 orders of magnitude slower than python.

More directly, I tested sklearn's NMF.fit_transform vs nnmf. The results are similar to the benchmark above-

julia> @btime NMF(10).fit_transform($Y);
  599.550 ms (36 allocations: 6.81 KiB)

julia> @btime nnmf($Y, 10, init=:nndsvd, alg=:cd);
  10.426 s (534662908 allocations: 8.01 GiB)

julia> @btime nnmf($Y, 10, init=:nndsvd, alg=:greedycd);
  5.207 s (64315993 allocations: 6.38 GiB)

---

I'm not super knowledgeable about the difference in NMF algorithms, but the sklearn implementation is what is "accepted" so far in my field. The coordinate descent and the GreedyCD algs both seem to do a decent job of matching the sklearn output, but the runtime is a little concerning.

[ghost]

Hello, I confirmed the same problem.

julia> Random.seed!(1234);

julia> Y = rand(1000, 1000);

julia> @btime NMF(10, max_iter=100).fit_transform($Y);
  185.509 ms (61 allocations: 81.45 KiB)

julia> @btime nnmf($Y, 10, init=:nndsvd, alg=:cd, maxiter=100);
  1.792 s (59293667 allocations: 974.16 MiB)

julia> @btime nnmf($Y, 10, init=:nndsvd, alg=:greedycd, maxiter=100);
  1.439 s (17715168 allocations: 2.45 GiB)

After reviewing the code, I found that my implementation of GreedyCD had a problem on memory allocation. Fixing the problem yields the following result.

julia> @btime nnmf($Y, 10, init=:nndsvd, alg=:greedycd, maxiter=100);
  562.258 ms (449 allocations: 69.97 MiB)

The performance of GreedyCD has been improved, but there may still be room for improvement.

[ghost]

@vilim I don't fully understand coorddesc.jl, but coorddesc.jl might have a memory allocation problem.

[ghost]

Status [Julia v1.5.3, NMF v0.5.1]:

julia> Random.seed!(1234);

julia> Y = rand(1000, 1000);

julia> @btime NMF(10, max_iter=100).fit_transform($Y);
  185.509 ms (61 allocations: 81.45 KiB)

julia> @btime nnmf($Y, 10, init=:nndsvd, alg=:cd, maxiter=100);
  358.167 ms (33 allocations: 54.06 MiB)

julia> @btime nnmf($Y, 10, init=:nndsvd, alg=:greedycd, maxiter=100);
  562.258 ms (449 allocations: 69.97 MiB)

[ghost]

Status [Julia v1.6.0, NMF v0.5.1]:

julia> Random.seed!(1234);

julia> Y = rand(1000, 1000);

julia> @btime NMF(10, max_iter=100).fit_transform($Y);
  225.007 ms (54 allocations: 81.25 KiB)

julia> @btime nnmf($Y, 10, init=:nndsvd, alg=:cd, maxiter=100);
  447.225 ms (33 allocations: 54.06 MiB)

julia> @btime nnmf($Y, 10, init=:nndsvd, alg=:greedycd, maxiter=100);
  862.726 ms (451 allocations: 69.97 MiB)

[ghost]

Status [Julia v1.6.0, NMF v0.5.2]:

julia> Random.seed!(1234);

julia> Y = rand(1000, 1000);

julia> @btime NMF(10, max_iter=100).fit_transform($Y);
  225.007 ms (54 allocations: 81.25 KiB)

julia> @btime nnmf($Y, 10, init=:nndsvd, alg=:cd, maxiter=100);
  122.348 ms (49 allocations: 8.86 MiB)

julia> @btime nnmf($Y, 10, init=:nndsvd, alg=:greedycd, maxiter=100);
  559.035 ms (467 allocations: 24.76 MiB)

[mileslucas]

Thanks for the effort in improving the speeds. I'm really satisfied with how much improvement was made! Thank you.