4

我分析了我的一个程序，发现热点是levenshtein_distance递归调用的。我决定尝试优化它。

lvh_distance levenshtein_distance( const std::string & s1, const std::string & s2 )
{
    const size_t len1 = s1.size(), len2 = s2.size();
    std::vector<unsigned int> col( len2+1 ), prevCol( len2+1 );

    const size_t prevColSize = prevCol.size();
    for( unsigned int i = 0; i < prevColSize; i++ )
        prevCol[i] = i;

    for( unsigned int i = 0, j; i < len1; ++i )
    {
        col[0] = i+1;
        const char s1i = s1[i];
        for( j = 0; j < len2; ++j )
        {
            const auto minPrev = 1 + std::min( col[j], prevCol[1 + j] );
            col[j+1] = std::min( minPrev, prevCol[j] + ( static_cast<unsigned int>( s1i != s2[j] ) ) );
        }
        col.swap( prevCol );
    }
    return prevCol[len2];
}

TL;DR：我改变了std::string→std::array

War Story：在它上面运行 vtune 之后，我发现更新的那一行col[j+1]是减慢一切的那一行（90% 的时间都花在它上面）。我想：好吧，也许这是一个别名问题，也许编译器无法确定字符串对象中的字符数组是无别名的，因为它们被字符串接口屏蔽，并且花费 90% 的时间检查程序的其他部分修改了它们。

所以我把我的字符串改成了静态数组，因为那里，没有动态内存，下一步本来就是restrict用来帮助编译的。但与此同时，我决定检查是否通过这样做获得了任何性能。

lvh_distance levenshtein_distance( const std::string & s1, const std::string & s2 )
{
    const size_t len1 = s1.size(), len2 = s2.size();
    static constexpr unsigned MAX_STRING_SIZE = 512;
    assert(len1 < MAX_STRING_SIZE && len2 < MAX_STRING_SIZE);
    static std::array<unsigned int, MAX_STRING_SIZE> col, prevCol;

    for( unsigned int i = 0; i < len2+1; ++i )
        prevCol[i] = i;

    // the rest is unchanged
}

TL；DR：现在它运行缓慢。

发生的事情是我失去了表现。很多。我的示例程序现在在 44 秒内运行，而不是在 ~ 6 秒内运行。再次使用 vtune 进行分析表明，一个函数被一遍又一遍地调用：（std::swap对你来说，gcc 人，这是在 bits/move.h 中），而它又由std::swap_ranges(bits/stl_algobase.h) 调用。

我想这std::min是使用 实现的quicksort，这解释了为什么要进行交换，但我不明白为什么在这种情况下交换需要这么多时间。

编辑：编译器选项：我正在使用带有选项“-O2 -g -DNDEBUG”的 gcc 和一堆警告说明符。

4

2 回答 2

4

对于一个实验，我使用一对短字符串运行了一个基本未修改的原始代码版本，数组版本的时间约为 36 秒，向量版本的时间约为 8 秒。

您的版本似乎很大程度上取决于MAX_STRING_SIZE. 当我使用 50 而不是 512（正好适合我的琴弦）时，阵列版本的时间下降到大约 16 秒。

然后，我对您的主循环进行了手动翻译，以摆脱显式交换。这进一步将数组版本的时间减少到了 11s，更有趣的是，现在数组版本的时间独立于MAX_STRING_SIZE. 放回512的时候，阵列版还是用了11s。

这很好地证明了数组的显式交换是您的版本的大部分性能问题所在。

数组和向量版本之间仍然存在显着差异，数组版本的时间长了大约 40%。我还没有机会确切地调查为什么会这样。

for( unsigned int i = 0, j; i < len1; ++i )
{
    {
        col[0] = i+1;
        const char s1i = s1[i];
        for( j = 0; j < len2; ++j )
        {
            const auto minPrev = 1 + std::min( col[j], prevCol[1 + j] );
            col[j+1] = std::min( minPrev, prevCol[j] + ( static_cast<unsigned int>( s1i != s2[j] ) ) );
        }
    }

    if (!(++i < len1))
        return col[len2];

    {
        prevCol[0] = i+1;
        const char s1i = s1[i];
        for( j = 0; j < len2; ++j )
        {
            const auto minPrev = 1 + std::min( prevCol[j], col[1 + j] );
            prevCol[j+1] = std::min( minPrev, col[j] + ( static_cast<unsigned int>( s1i != s2[j] ) ) );
        }
    }
}
return prevCol[len2];
于 2013-05-15T21:28:25.853 回答
1

首先：@DanielFischer 很可能已经指出了导致性能下降的原因：交换std::arrays是线性时间操作，而交换std::vector是恒定时间操作。虽然一些编译器可能能够优化这一点，但您的 gcc 似乎无法这样做。

同样重要的是：static像您在此处使用的数组会使您的代码本质上不是线程安全的。这通常不是一个好主意。

删除其中一个数组（或向量）和相关的交换并使用动态分配的 c 数组实际上非常容易，并且可以带来卓越的性能（至少对于我的设置而言）。
更多的转换（如始终使用size_t）会产生以下函数：

unsigned int levenshtein_distance3( const std::string & s1, const std::string & s2 )
{
    const size_t len1 = s1.size(), len2 = s2.size();
    ::std::unique_ptr<size_t[]> col(new size_t[len2 + 1]);

    for(size_t i = 0; i < len2+1; ++i )
        col[i] = i;

    for(size_t i = 0; i < len1; ++i )
    {
        size_t lastc = col[0];
        col[0] = i+1;
        const char s1i = s1[i];
        for(size_t j = 0; j < len2; ++j )
        {
            const auto minPrev = 1 + (::std::min)(col[j], col[j + 1]);
            const auto newc = (::std::min)(minPrev, lastc + (s1i != s2[j] ? 1 : 0));
            lastc = col[j+1];
            col[j + 1] = newc;
        }
    }
    return col[len2];
}
于 2013-05-15T12:10:59.370 回答