O que pode tornar um programa mais lento ao usar mais threads?

Esta pergunta é sobre o mesmo programa que eu anteriormente perguntado sobre. Para recapitular, eu tenho um programa com uma estrutura de loop como esta:

for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1;

bin_index é uma função completamente determinística de seus argumentos que, para os fins desta pergunta, não usa ou altera nenhum estado compartilhado - em outras palavras, é manifestamente reentrant

Primeiro escrevi este programa para usar um único thread. Depois converti-o para usar vários threads, como o threadn executa todas as iterações do loop externo ondei1 % nthreads == n. Portanto, a função que é executada em cada thread se parece com

for (int i1 = n; i1 < N; i1 += nthreads)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        thread_local_histogram[bin_index(i1, i2, i3, i4)] += 1;

e todos osthread_local_histograms são adicionados no segmento principal no fina

Aqui está o estranho: quando executo o programa com apenas 1 thread para algum tamanho específico do cálculo, leva cerca de 6 segundos. Quando o executo com 2 ou 3 threads, fazendo exatamente o mesmo cálculo, leva cerca de 9 segundos. Por que é que? Eu esperaria que o uso de 2 threads fosse mais rápido que 1, já que eu tenho uma CPU de núcleo duplo. O programa não usa mutexes ou outras primitivas de sincronização, portanto, dois threads devem poder executar em paralel

Para referência: saída típica detime (este é no Linux) para um segmento:

real    0m5.968s
user    0m5.856s
sys     0m0.064s

e dois tópicos:

real    0m9.128s
user    0m10.129s
sys     0m6.576s

O código está emhttp: //static.ellipsix.net/ext-tmp/distintegral.cc

P.S. Eu sei que existem bibliotecas projetadas para exatamente esse tipo de coisa que provavelmente poderia ter um desempenho melhor, mas foi sobre isso que minha última pergunta, para que eu não precise ouvir essas sugestões novamente. (Além disso, eu queria usar pthreads como uma experiência de aprendizado.)