Will limiting memory to 1mb force this to be chunked?

Yes, there was 77 chunks before, and 7 or 8 now. Timings for this test are now reduced to a few 100s ms.

I think we should be constructing the Parallel instance in pairwise_distances_chunked

It could be but it wouldn't be that simple. pairwise_distances_chunked calls pairwise_distances, so we would need to make parallel calls of pairwise_distances with n_jobs=1 for each instance of it. It would not be very clean.

However I don't think the purpose of pairwise_distances_chunked is to make lots of small chunks. It's main purpose is to limit memory usage, but I see no use case where you want to limit it to a few Mo. And as soon as your chunks are big enough, the overhead of thread creation/destruction becomes negligible. Also maybe some day loky will have a threading backend with reusable threads :)