Pydaal cited speedups of about 40x for a single cpu between their lloyd k-means and ours.
It would be great to reproduce and identify bottlenecks. Also, we should compare against our elkan and see what the differences are.
I think this was done for several low-dim spaces, n_clusters=100 and varying n_samples.