¿Qué puede hacer que un programa funcione más lento cuando se usan más hilos?

Esta pregunta es sobre el mismo programa que yopreviamente preguntado sobre. Para recapitular, tengo un programa con una estructura de bucle 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 es una función completamente determinista de sus argumentos que, a los fines de esta pregunta, no utiliza ni cambia ningún estado compartido; en otras palabras, es manifiestamente reentrante.

Primero escribí este programa para usar un solo hilo. Luego lo convertí para usar múltiples hilos, como ese hilon ejecuta todas las iteraciones del bucle externo dondei1 % nthreads == n. Entonces la función que se ejecuta en cada hilo se ve como

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;

y todo elthread_local_histograms se suman en el hilo principal al final.

Aquí está lo extraño: cuando ejecuto el programa con solo 1 subproceso para un tamaño particular del cálculo, toma alrededor de 6 segundos. Cuando lo ejecuto con 2 o 3 hilos, haciendo exactamente el mismo cálculo, me lleva unos 9 segundos. ¿Porqué es eso? Esperaría que usar 2 hilos sería más rápido que 1 hilo ya que tengo una CPU de doble núcleo. El programa no utiliza mutex ni otras primitivas de sincronización, por lo que dos subprocesos deberían poder ejecutarse en paralelo.

Para referencia: salida típica detime (esto está en Linux) para un hilo:

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

y dos hilos:

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

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

PD. Sé que hay bibliotecas diseñadas para este tipo de cosas que probablemente podrían tener un mejor rendimiento, pero de eso se trataba mi última pregunta, así que no necesito escuchar esas sugerencias nuevamente. (Además, quería usar pthreads como una experiencia de aprendizaje).