Application in OpenMp slower than serial code c++

Question

I am struggling with OpenMp task

I have to optimize calculation of a few methods - among them is a histogram.

I spent 3 days and tried about 50 different approaches for it, but still my code is slower than the serial execution

Does anybody could enlighten me what I am doing wrong? Do you have any clues how to solve this problem?

Here is a code that needs to be optimized : (par1 usually is less than 10000, the code posted below is put inside some method and during test it is called about 100 times)

unsigned long index;
for (unsigned int par1 = 0; par1 < limit; par1++) {
    for (unsigned int par2 = 0; par2 < par1; par2++) {
        index = getDistance(par1, par2) / param;
        if (index < size) {
            hist[index]++;
        }
    }
}

...

The problem is that the amount of calculation that needs to be done per iteration is changeable - the amount of operations grows sharply when iteration counter grows

I know that the reduction is probably the best way, but I dont know how to apply it for this array

Here is one of my tries, but it is slower than serial execution, (I merged two loops into one):

  signed long max = elements * elements;
  int par1 = 0;
  int par2 = 0;
  unsigned long index;

  #pragma omp parallel for firstprivate(par1, par2, index, max, size) shared(histogram)
  for (unsigned long x = 0; x < max; x++) 
  {
        par1 = x / elements;
        par2 = x % elements;
        if(par1 > par2)
        {
          index = getDistance(par1, par2) / param;
          if (index < size) 
          {
              #pragma omp atomic
              histogram[index]++;   
          }
        }
  }