Failures on this PR might are fixed by #23990.

Using perf(1), we can see that when running pairwise_distances(X, Y, dist="manhattan"), 98% of the time is spent computing distances, i.e. in ManhattanDistance{32,64}.dist:

I am not entirely but looking at cycles spent on the assembly code line, we can see that loop unrolling + SIMD is could used (here, SSE registers are used on scalars):

Percent│
       │    Disassembly of section .text:
       │
       │    00000000000104b0 <__pyx_f_7sklearn_7metrics_13_dist_metrics_17ManhattanDistance_dist>:
       │    __pyx_f_7sklearn_7metrics_13_dist_metrics_17ManhattanDistance_dist():
  0.30 │      test   %rcx,%rcx
  0.04 │    ↓ jle    40
  0.00 │      movq   __pyx_k_C+0x6b4b,%xmm2
  0.01 │      xor    %eax,%eax
       │      pxor   %xmm1,%xmm1
  0.00 │      nop
  0.00 │18:   movsd  (%rsi,%rax,8),%xmm0
  0.28 │      subsd  (%rdx,%rax,8),%xmm0
  0.25 │      add    $0x1,%rax
  0.04 │      andpd  %xmm2,%xmm0
  0.18 │      addsd  %xmm0,%xmm1
+98.76 │      cmp    %rax,%rcx
  0.10 │    ↑ jne    18
  0.00 │      movapd %xmm1,%xmm0
  0.04 │    ← retq
       │      nop
       │40:   pxor   %xmm1,%xmm1
       │      movapd %xmm1,%xmm0
       │    ← retq   

It's insightful to see how it's done, and to assess that 98.76% the time here is spent checking if j has reached the range bound, size. I do not know what causes the execution to be spent mostly on this comparison.

As discussed in real life, it might be interesting to see of the chunking is not detrimental for this operation: indeed chunking will cause non-contiguous writing of the distance values in the distance matrix output array.

It might be worthwhile to conduct dedicated benchmarks to use a chunk size of 1 to see if contiguous writing is beneficial or not.

It might be worthwhile to conduct dedicated benchmarks to use a chunk size of 1 to see if contiguous writing is beneficial or not.

My first intuition is that simply setting chunk_size=1 might help but we will still relies on a rather to complicated scheduling for this case: some details like the heuristic will be adapted, we might spend a lot of time jumping in many places due to singletonic chunks, etc..

I think _parallel_on_{X,Y} in this case can be made relatively simpler (namely it would just generalised the current _sparse_manhattan logic).

What do you think?

I am removing it from the 1.2 milestone as it needs more thought and thread-offs' assessments.

Turning this into a draft for two reasons; to me:

• this brings less value to end-users compared to other work (some of which is part of PERF PairwiseDistancesReductions initial work #22587) that has been started in the meantime
• there exists alternative implementations that are more lightweight and that do not necessitate the whole infrastructure for the distance matrix chunking; see FEA Introduce PairwiseDistances #23958 (comment)

Closing since this has been superseded by #25561.