search

willow-ahrens / Finch.jl

Sparse tensors in Julia and more! Datastructure-driven array programing language.
http://willowahrens.io/Finch.jl/
MIT License
152 stars 13 forks source link

SDDMM speedup goal #538

Closed willow-ahrens closed 1 month ago

willow-ahrens commented 2 months ago

Lets get a real speedup in https://github.com/pydata/sparse/pull/674

mtsokol commented 2 months ago

@willow-ahrens We merged https://github.com/pydata/sparse/pull/674 and with Finch v0.6.26 we have x2.5 speedup (It's still away from x100) for NxN arrays where N=10000 and density is 0.0001 compared to both Numba and SciPy! :tada: Great progress! Thank you! 

Finch
Took 8.787564675013224 s.

Numba
Took 22.904020706812542 s.

SciPy
Took 22.59452811876933 s.

https://github.com/pydata/sparse/actions/runs/9078498356/job/24945650514#step:5:299

willow-ahrens commented 2 months ago

That's great! I'll try to run it in debug mode to see if the autoscheduler can be improved

willow-ahrens commented 1 month ago

Finch Took 0.009948968887329102 s.

Numba Took 0.44066866238911945 s.

SciPy Took 0.2068446477254232 s.

mtsokol commented 1 month ago

Wow! This looks amazing!

Did you change any parameters/code in https://github.com/pydata/sparse/blob/main/examples/sddmm_example.py?

willow-ahrens commented 1 month ago

https://gist.github.com/willow-ahrens/94f35177fa163cc78ed3d0242b6051ef

willow-ahrens commented 1 month ago

I changed some of the code. The issue right now is that the performance of dense matmul is pretty good, so I changed the density and dimensions

willow-ahrens commented 1 month ago

this is a 43x improvement, I think this is good enough to close the issue 🎉 . I am curious what kind of matmul is being used in numba.

mtsokol commented 1 month ago

x43 is what we needed for sure! Thank you!!!