c - C 中的 qsort 是我的程序中意想不到的瓶颈

Question

我正在编写一些代码来对齐天文图像。我是用C99写的。由于某种原因，我用于检测图像中星星的算法的运行速度比预期慢得多。我基本上需要忽略低于 99% 的所有像素(因为星星只是小亮点)。为了计算第 99 个百分位，我对图像中的像素副本应用了 qsort。当我分析代码时，它说它花费了 75% 的时间执行 qsort 使用的 compare_quantum 函数。整个恒星探测过程大约需要3秒。

我最初是用 C++ 编写代码的，相同的算法大约需要 0.2 秒。我猜测发生这种情况的原因是，与 C++ 不同，C 不能像 C++ 那样使用 std::sort 内联对比较函数的调用。

我可以编写自己的排序函数，但我只是想知道是否有人有任何其他想法可以使其运行得更快。我在代码的其他地方调用了 qsort，我想也许我需要删除所有这些。

我使用的是 gcc 5.2。 stars_map 中的第一个 qsort 是瓶颈。另外，quantum_t 只是 uint16_t 的 typedef。

int compare_quantum(const void* a, const void* b)
{
    return (*(quantum_t*)a > *(quantum_t*)b) - (*(quantum_t*)a < *(quantum_t*)b);
}

void star_register(quantum_t* grey, double* rowint, double* colint, double* lum, size_t row, size_t col, size_t w, size_t h)
{
    size_t gi = row * w + col;
    if(!(row >= 0 && col >= 0 && row < h && col < w && grey[gi]))
        return;

    *rowint += grey[gi] * row;
    *colint += grey[gi] * col;
    *lum += grey[gi];
    grey[gi] = 0;

    for(int dr = -1; dr <= 1; dr++)
    {
        for(int dc = -1; dc <= 1; dc++)
        {
            if(dc == 0 && dr == 0)
                continue;
            star_register(grey, rowint, colint, lum, row + dr, col + dc, w, h);
        }
    }
}

stars_t* stars_map(image_t* img, float detection_percentile)
{
    assert(img);

    quantum_t* grey = NULL;
    quantum_t* sorted = NULL;
    star_t* stars = NULL;
    size_t nstars = 0;
    size_t stars_alloc = 0;

    grey = malloc(sizeof(quantum_t) * img->w * img->h);
    if(grey == NULL) goto fail;

    sorted = malloc(sizeof(quantum_t) * img->w * img->h);
    if(sorted == NULL) goto fail;

    for(size_t i = 0; i < img->w * img->h; i++)
        sorted[i] = grey[i] = ((uint32_t)img->px[i].red + (uint32_t)img->px[i].green + (uint32_t)img->px[i].blue) / 3;
    //this qsort is the issue
    qsort(sorted, img->w * img->h, sizeof(quantum_t), compare_quantum);
    quantum_t cut = sorted[(size_t)(img->w * img->h * detection_percentile)];
    free(sorted);
    sorted = NULL;

    for(size_t i = 0; i < img->w * img->h; i++)
        grey[i] = clampq((int32_t)grey[i] - cut);

    for(size_t i = 0; i < img->h; i++)
    {
        for(size_t j = 0; j < img->w; j++)
        {
            if(grey[i * img->w + j])
            {
                if(nstars == stars_alloc)
                {
                    stars = realloc(stars, (stars_alloc += 500) * sizeof(star_t));
                    if(!stars) goto fail;
                }
                double rowint = 0.0;
                double colint = 0.0;
                double lum = 0.0;
                star_register(grey, &rowint, &colint, &lum, i, j, img->w, img->h);
                stars[nstars++] = (star_t){.x = colint / lum, .y = rowint / lum, .lum = lum};
            }
        }
    }

    free(grey);

    qsort(stars, nstars, sizeof(star_t), star_compare);

    stars_t* result = malloc(sizeof(stars_t) + nstars * sizeof(star_t));
    if(result == NULL) goto fail;
    result->npairs = nstars;
    memcpy(result->stars, stars, sizeof(star_t) * nstars);
    free(stars);


    return result;

    fail:
    if(grey) free(grey);
    if(sorted) free(sorted);
    if(stars) free(stars);

    return NULL;
}

我最初认为对 star_register 的递归调用会影响性能，但在配置文件中它几乎不重要。

Answer 1

问题是我忘记了我在 c++ 版本中使用的是 std::nth_element 而不是 std::sort 。这就是代码运行缓慢的原因。我写了一个 qselect，现在整个程序的速度大致相同。

quantum_t quantum_qselect(quantum_t *v, size_t len, size_t k)
{
    size_t i, st;

    for(st = i = 0; i < len - 1; i++)
    {
        if(v[i] > v[len - 1])
            continue;
        swap(quantum_t, v[i], v[st]);
        st++;
    }

    swap(quantum_t, v[len - 1], v[st]);

    return k == st ? v[st] : st > k ? quantum_qselect(v, st, k) : quantum_qselect(v + st, len - st, k - st);
}