Benchmarks with block_size=None, attempting to follow #6151:

import numpy as np
from sklearn.metrics.cluster import silhouette_score
n_features = 100
for n_samples in [10000, 1000, 100]:
    for n_labels in [4, 6, 100]:
        print('n_features', n_features, 'n_samples', n_samples, 'n_labels', n_labels)
        X = np.random.rand(n_samples, n_features)
        y = np.random.randint(n_labels, size=n_samples)
        %timeit silhouette_score(X, y)

master                                        block_size=None                               block_size=100
n_features 100 n_samples 10000 n_labels 4     n_features 100 n_samples 10000 n_labels 4     n_features 100 n_samples 10000 n_labels 4
1 loop, best of 3: 3.28 s per loop            1 loop, best of 3: 4.03 s per loop            1 loop, best of 3: 1.61 s per loop
n_features 100 n_samples 10000 n_labels 6     n_features 100 n_samples 10000 n_labels 6     n_features 100 n_samples 10000 n_labels 6
1 loop, best of 3: 3.16 s per loop            1 loop, best of 3: 4.12 s per loop            1 loop, best of 3: 1.64 s per loop
n_features 100 n_samples 10000 n_labels 100   n_features 100 n_samples 10000 n_labels 100   n_features 100 n_samples 10000 n_labels 100
1 loop, best of 3: 3.48 s per loop            1 loop, best of 3: 4.05 s per loop            1 loop, best of 3: 1.61 s per loop
n_features 100 n_samples 1000 n_labels 4      n_features 100 n_samples 1000 n_labels 4      n_features 100 n_samples 1000 n_labels 4
100 loops, best of 3: 16.9 ms per loop        10 loops, best of 3: 30.2 ms per loop         100 loops, best of 3: 15.8 ms per loop
n_features 100 n_samples 1000 n_labels 6      n_features 100 n_samples 1000 n_labels 6      n_features 100 n_samples 1000 n_labels 6
100 loops, best of 3: 18.3 ms per loop        10 loops, best of 3: 30 ms per loop           100 loops, best of 3: 15.7 ms per loop
n_features 100 n_samples 1000 n_labels 100    n_features 100 n_samples 1000 n_labels 100    n_features 100 n_samples 1000 n_labels 100
1 loop, best of 3: 226 ms per loop            10 loops, best of 3: 30.8 ms per loop         100 loops, best of 3: 16.7 ms per loop
n_features 100 n_samples 100 n_labels 4       n_features 100 n_samples 100 n_labels 4       n_features 100 n_samples 100 n_labels 4
1000 loops, best of 3: 688 µs per loop        1000 loops, best of 3: 570 µs per loop        1000 loops, best of 3: 608 µs per loop
n_features 100 n_samples 100 n_labels 6       n_features 100 n_samples 100 n_labels 6       n_features 100 n_samples 100 n_labels 6
1000 loops, best of 3: 1.01 ms per loop       1000 loops, best of 3: 572 µs per loop        1000 loops, best of 3: 600 µs per loop
n_features 100 n_samples 100 n_labels 100     n_features 100 n_samples 100 n_labels 100     n_features 100 n_samples 100 n_labels 100
10 loops, best of 3: 57.9 ms per loop         1000 loops, best of 3: 591 µs per loop        1000 loops, best of 3: 587 µs per loop

defaulting to block_size=100 is looking pretty good too...

Instead of allowing the user to specify size as a unit of memory usage, I am wondering if block_size should specify maximum number of cells created by the pairwise_distances operation, rather than number of rows. I.e. the latter is the former divided by n_samples.

I've now tried to just have the user specify the pairwise distance memory consumption in bytes...

I've now tried to just have the user specify the pairwise distance memory consumption in bytes...

If it needs to be in memory units, could we have it in MBs as users will need to enter a smaller number?

If it needs to be in memory units, could we have it in MBs as users will need to enter a smaller number?

It doesn't need to be, but I think it is a more practical data-invariant measure. Yes, can have in MiB

@raghavrv now in MiB

Instead of allowing the user to specify size as a unit of memory usage, I am wondering if block_size should specify maximum number of cells created by the pairwise_distances operation, rather than number of rows. I.e. the latter is the former divided by n_samples.

@jnothman I'm a little bit late but +1 to have the memory usage. I think it's an easier measure to specify. And also +1 for MiB.

You're earlier than everyone but @raghavrv. Thanks for the input. That's where it's converged anyway.

@jnothman I do a review in a few moment.

The performances are similar on my computer.

I'd appreciate another opinion on this: should we make a memory efficiency parameter constant, given that we know the constant is sensible on some modern platforms (and hard to explain to the user), or directly configurable by the user? In the context of a learning algorithm, configurability seems more valuable, but for an evaluation metric, is it sensible to just say: 64 MiB is the max pairwise distance evaluation available. Also, should this be 64 // n_jobs? (perhaps I need to benchmark the interaction with n_jobs.)

Not sure who to ask: @GaelVaroquaux, @MechCoder, @amueller?

Fixed a problem where n_jobs wasn't being used, and changed to use threading backend for parallelism (only marginal gains for euclidean, but I've not seen multiprocessing be worth the overhead here).

Sorry for piggy backing on this conversation... How do you usually definitively decide between multiprocessing and threading? As joblib memmaps the data I don't see why multiprocessing is any worse than threading given that it is usually a bit faster than threading (for larger datasets) and much faster when gil is not released... Or am I wrong?

I don't have any good answers for you, @raghavrv, but for the scale of problem and processor I've tried, multiprocessing always results in slower times. Afaik, threading is a good option when there's a lot of work in non-GIL operations, and when copying the inputs and outputs competes with the calculation for cost. I'm considering just dropping n_jobs support as ineffectual until someone can show me it actually benchmarks a more-than-marginal benefit.

@jnothman I think for blocked computations, we set "reasonable" defaults and allow configuration, IIRC. Do you want a review on this? It doesn't seem high priority to me. [OT: why are you using this score?]

I'd like review on this, but no I'm not using silhouette personally. I worked on it because an issue came in, and because I wanted to ascertain that #1976 could be improved upon. I also think we should be reviewing the potential blockwise computations everywhere that pairwise_distances is used, such as KNN. Perhaps I should make an issue for that.

To be sure, it's not high priority, except that it closes a few issues and avoids more appearing over the next release.

Also, #5988 should be fixed.

Could you refactor #7438 out of this PR and make a rebase. I can try and take a deeper look at this before the weekend :)

@jnothman Ping :)