将向量转换为数组会使我的程序变慢

Question

我分析了一个程序，发现最耗时的部分是递归调用的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 战斗故事： 在运行 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: 现在它运行得很慢。

发生的情况是，我的性能丢失了很多。相比于以前的6秒，我的示例程序现在需要44秒才能运行。再次使用vtune进行分析显示，一个函数被反复调用：std::swap（对于gcc用户来说，这在bits/move.h中），而这个函数又被std::swap_ranges（bits/stl_algobase.h）调用。

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

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

- qdii

---

如果你交换vector，你交换的是指向底层数组的指针；如果你交换array，则会使用临时副本来复制数组。 - Daniel Fischer

不应该通过排序来实现 min，因为通过顺序扫描查找值比任何可能的排序算法都要快！ - danielschemmel

@dionadar 你是说一个std::minimal示例吗（好的，我会停止；） - Christian Rau

在优化构建中，行很容易混淆，你确定不是这个导致了瓶颈：col.swap(prevCol);。你应该尝试让 std::array<...> *pCol, *pPrevCol; 指向两个真实的数组，通过指针更改所有访问并交换指针...或者将外部循环每次迭代两个并在第二个循环中手动交换 col 和 prevCol（你需要在两个半部分之间添加额外的测试和分支语句，并且return 语句将需要某种条件判断）。 - CB Bailey

使用Howard Hinnant的栈分配器（stack allocator）来为std::vector分配内存，结合了指针交换和无动态分配的优点。 - TemplateRex

Answer 1

为了一项实验，我基本未更改您的原始代码，使用一对短字符串分别测试了数组版本和向量版本的时间，得到的结果为数组版本约36秒，向量版本约8秒。

您的版本似乎非常依赖于选择“MAX_STRING_SIZE”。当我将其从512改为50（这只适合我的字符串）时，数组版本的计时降至约16秒。

然后，我手动转换了您的主循环以去除显式交换。这进一步将数组版本的时间减少到11秒，并且更有趣的是，现在使得数组版本的计时与选择的“MAX_STRING_SIZE”无关。当将其恢复为512时，数组版本仍需11秒。

这很好地证明了数组显式交换是您的版本中性能问题的主要来源。

数组版本和向量版本之间仍存在显着差异，数组版本大约需要多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];

- CB Bailey

Answer 2

首先：@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];
}

- danielschemmel

---

std::unique_ptr<size_t[]> col(new size_t[len2 + 1]); - 这不就是一个 std::vector 吗？ - Christian Rau

虽然某些编译器可以进行优化处理，但你的gcc似乎无法做到。这种线性数组交换有哪些优化方法？ - Christian Rau

事实上，一开始我甚至完全无法重现这个问题：通过优化，OP的数组版本甚至比向量版本运行得更快了约15％！ - danielschemmel

“unique_ptr<size_t[]>非常类似于vector，只是它的开销更小。” - 那么这个开销是什么？你是只想要交换/移动std::vector需要的额外两个指针的开销，还是认为std::vector会带来更多开销？ - Christian Rau

我并不是说它完全无关紧要，只是我不确定你所指的开销具体是什么（但现在我知道了）。 - Christian Rau