For循环性能和多线程性能问题

3

我有点无聊,所以想尝试使用std :: thread,并最终测量单线程和多线程控制台应用程序的性能。这是一个双重问题。因此,我从一个单线程的整数向量求和开始(800000个整数)。

int sum = 0;
auto start = chrono::high_resolution_clock::now();

for (int i = 0; i < 800000; ++i)
    sum += ints[i];

auto end = chrono::high_resolution_clock::now();
auto diff = end - start;

然后我添加了基于范围和迭代器的for循环,并使用chrono:: high_resolution_clock以同样的方式进行了测量。

for (auto& val : ints)
    sum += val;

for (auto it = ints.begin(); it != ints.end(); ++it)
    sum += *it;

此时控制台输出如下:

index loop: 30.0017ms
range loop: 221.013ms
iterator loop: 442.025ms

这是一个调试版本,所以我改成了发布版本,索引型for循环的优势约为1ms。虽然不是大问题,但出于好奇:在这三个for循环中,调试模式下应该有如此大的差异吗?或者在发布模式下甚至有1ms的差异?
我转向线程创建,并尝试使用基于索引的for循环对数组进行并行求和,使用lambda(通过引用捕获所有内容,以便可以使用先前声明的int向量和互斥锁)。
auto func = [&](int start, int total, int index)
{
    int partial_sum = 0;

    auto s = chrono::high_resolution_clock::now();
    for (int i = start; i < start + total; ++i)
        partial_sum += ints[i];
    auto e = chrono::high_resolution_clock::now();
    auto d = e - s;

    m.lock();
    cout << "thread " + to_string(index) + ": " << chrono::duration<double, milli>(d).count() << "ms" << endl;
    sum += partial_sum;
    m.unlock();
};

for (int i = 0; i < 8; ++i)
    threads.push_back(thread(func, i * 100000, 100000, i));

基本上每个线程都在对总数组的1/8进行求和,最终控制台输出为:
thread 0: 6.0004ms
thread 3: 6.0004ms
thread 2: 6.0004ms
thread 5: 7.0004ms
thread 4: 7.0004ms
thread 1: 7.0004ms
thread 6: 7.0004ms
thread 7: 7.0004ms
8 threads total: 53.0032ms

所以,我猜这个问题的第二部分是什么?使用2个线程的解决方案也以约30毫秒结束。缓存乒乓?还是其他什么?如果我做错了什么,正确的方法是什么?另外,如果有关系的话,我是在一台带有8个线程的i7上尝试的,所以是的,我知道我没有计算主线程,但是我尝试了7个单独的线程,基本上得到了相同的结果。
编辑:抱歉忘记提到这是在Windows 7上使用Visual Studio 2013和Visual Studio的v120编译器或者它被称为什么。
编辑2:这是整个主函数:http://pastebin.com/HyZUYxSY

什么平台、编译器等? - BoBTFish
你是否也尝试过使用一些本地线程实现而不使用那些std :: thread工具? - BitTickler
我改成了release版本,结果索引循环的速度比其他方式快了约1毫秒。你重复测量了多少次?相对于方差来说,这1毫秒是否显著?你采取了哪些步骤来确保缓存更热时不会偏向某个测试? - eerorika
当然,它是本地线程的抽象。但是,任何使用过本地线程的人都知道有多少自由度和需要做出多少决策。因此,这个抽象是通过该决策树的一条路径。 - BitTickler
为了提高性能,线程内执行的代码必须比创建、切换和销毁线程的开销更长。线程是在单个核心、多个核心或不同处理器上运行取决于操作系统。 - Thomas Matthews
显示剩余5条评论
5个回答

2

如果没有开启优化,所有在后台执行的方法调用都很可能是真实的方法调用。内联函数很可能不会被内联,而是真正地被调用。对于模板代码,你真的需要开启优化,以避免所有代码被文字逐字打出。例如,你的迭代器代码很可能会调用iter.end() 800,000次,并且进行800,000次比较的operator!=,这将调用operator==等等。

对于多线程代码,处理器很复杂。操作系统也很复杂。你的代码不是独自在计算机上运行。你的计算机可以改变时钟速度,转入超级模式,转入热保护模式。而将时间舍入到毫秒并不真正有帮助。一个线程可能需要6.49毫秒,另一个线程可能需要6.51毫秒,但它们舍入的方式不同。


是的,我知道。我检查过了,当这个程序在运行时,CPU 的频率是4.5GHz。 - rndm

2

在调试模式下,这三个for循环的差别应该会很大吗?

是的。如果允许,一个不错的编译器可以为每个不同的循环产生相同的输出,但如果没有启用优化,则迭代器版本具有更多的函数调用,而函数调用具有一定的开销。

甚至在发布模式下,1毫秒的差异也会有所不同吗?

你的测试代码:

    start = ...
    for (auto& val : ints)
            sum += val;
    end = ...
    diff = end - start;
    sum = 0;

循环结果未被使用,因此在优化时,编译器应该会选择丢弃代码,从而得到以下结果:

    start = ...
    // do nothing...
    end = ...
    diff = end - start;

为你的所有循环提供帮助。

在使用标准库的"high_resolution_clock"时,高精度可能会产生1毫秒的差异,并且在执行期间进程调度的差异也可能导致差异。我测量了基于索引的速度比其他方法慢0.04毫秒,但这个结果是没有意义的。


1

除了std::thread在Windows上的实现方式之外,我想指出您可用的执行单元和上下文切换。

i7并不具有8个真实的执行单元。它是一个带有超线程的四核处理器。无论如何进行宣传,HT都不能神奇地将可用线程数加倍。这是一个非常聪明的系统,它尝试在可能的情况下从额外的管道中安排指令。但最终,所有指令都只通过四个执行单元。

因此,运行8(或7)个线程仍然比您的CPU同时处理的能力要多。这意味着您的CPU必须在8个热线程之间频繁切换以获得计算时间。再加上来自操作系统的几百个线程,尽管其中大多数处于休眠状态,需要时间,您的测量结果将存在很高的不确定性。

使用单线程的for循环,操作系统可以将单个核心专用于该任务,并将半休眠线程分配到其他三个核心上。这就是为什么您在1个线程和8个线程之间看到如此大的差异。

关于您的调试问题:您应该检查Visual Studio是否在调试中启用了迭代器检查。当它被启用时,每次使用迭代器时都会进行边界检查等操作。请参见:https://msdn.microsoft.com/en-us/library/aa985965.aspx 最后,请看一下-openmp开关。如果您启用它并将OpenMP #pragmas应用于for循环,就可以摆脱所有手动线程创建。我玩过类似的线程测试(因为这很酷。:)),OpenMP的性能非常好。

你使用了std::thread吗?OpenMP是否提供更好的性能?我刚刚测试了std::thread和本地Windows线程,结果显示出了巨大的差异。 - rndm
根据你的代码,我做了一个自己的版本来测试Index For、Iterator For、Ranged For、StdThread和BoostThread。目前我还没来得及加入POSIX/Windows线程。而且结果与你的匹配。 在i7-860上,使用100,000,000个整数和8个线程,发布版,VS2013。 三个单线程均小于1毫秒。 std::thread约120毫秒,boost 130毫秒。OpenMP 3800毫秒。 OpenMP令人失望,但这三个都显示了线程切换的影响。然而,VS2013使用2.0,而4.0已经发布。这是我的代码链接:https://dl.dropboxusercontent.com/u/6108803/thread_tester.cpp - Nathilion
我刚在一台装有Intel G1820(双核,双线程)的Linux机器上进行了测试。我使用了带有OpenMP4的GCC 4.9.1进行编译,并期望OpenMP能够有更好的表现。可悲的是:结果与Windows机器相同。单线程循环比多线程版本快得多。std::thread仍然胜过boost::thread。而OpenMP仍然像没有腿一样落后。这真是一个让人失望的结果。相比其他多线程版本,OpenMP版本要容易得多!结果:0、0、0(索引、范围、迭代器)、18(std)、23(boost)、4098毫秒(OpenMP)。 - Nathilion
好的,OpenMP 的结果让我感到困扰,所以我想我一定做错了什么。我用一个新的测试更新了我的代码,展示了一个更好的 OMP 结构。现在,在我的办公机器上,使用 i7-4770、Win8.1 和 VS2013,结果如下:Index/Ranged/Iterator: <1ms。std:117-152 毫秒,boost:127-156 毫秒,OpenMP 旧版:约 1900 毫秒,OpenMP 新版:77-136 毫秒。OpenMP 现在比其他线程测试更加稳定快速。 - Nathilion
感谢分享你的结果。一旦我有些空闲时间,我将尝试使用OpenMP并进行操作。我重构了初始代码,并使用std :: thread让多线程测试比单线程更快。当将所有测量相关内容移出线程使用的lambda时,结果有很大不同。 - rndm

1
对于第一个问题,关于范围、迭代器和索引实现之间性能差异的问题,其他人已经指出,在非优化构建中,许多通常会被内联的内容可能不会被内联。
然而,还有一个额外的问题:默认情况下,在调试构建中,Visual Studio将使用checked iterators。通过checked iterator访问进行安全检查(迭代器是否引用有效元素?),因此使用它们的操作,包括基于范围的迭代,受到严重惩罚。
对于第二部分,我必须说这些持续时间似乎异常长。当我在本地运行代码,在一个核心i7-4770(Linux)上使用g++ -O3编译时,我得到每种方法的亚毫秒计时,实际上比运行之间的抖动还要少。将代码更改为迭代每个测试1000次会给出更稳定的结果,没有额外调整的情况下,索引和范围循环的每个测试时间为0.33毫秒,并且并行测试大约为0.15毫秒。
并行线程总共执行相同数量的操作,而且更重要的是,使用所有四个核限制了CPU动态增加其时钟速度的能力。那么如何需要更少的总时间呢?
我敢打赌,这些收益来自更好地利用每个核心的L2高速缓存,总共有四个。事实上,使用四个线程而不是八个线程将总并行时间减少到0.11毫秒,与更好的L2高速缓存使用一致。
浏览英特尔处理器文档,所有Core i7处理器(包括移动版)都至少有4MB的L3高速缓存,可以容纳80万个4字节整数。因此,我对原始时间比我看到的时间大100倍以及8线程时间总和如此之大感到惊讶,正如你所推测的那样,这是它们正在争夺高速缓存的强烈暗示。我假设这演示了调试版本代码的非最佳性能。您能发布优化构建的结果吗?

通过优化的发布版本和 800,000 个整数,我只得到了零,所以我将其增加到了 80,000,000,得到了以下结果: 索引循环:28.0016 毫秒,8 个线程总共:87.0051 毫秒。 - rndm

1

不知道std :: thread类是如何实现的,53ms的可能解释是:

线程在实例化时立即启动。(我看不到thread.start()或threads.StartAll()等)。因此,在第一个线程实例变为活动状态的时间内,主线程可能会(也可能不会)被抢占。毕竟,并没有保证线程在单独的核心上生成(线程亲和性)。

如果您仔细查看POSIX API,就会发现“应用程序上下文”和“系统上下文”的概念,这基本上意味着可能存在OS策略,不会将所有内核用于1个应用程序。

在Windows上(这是您进行测试的地方),可能线程不是直接产生的,而是通过线程池间接产生的,可能具有一些额外的std :: thread功能,这可能会产生开销/延迟。 (例如完成端口等)。

不幸的是,我的机器非常快,因此必须增加处理的数据量才能产生显着的时间。但好处是,这提醒我指出,通常,当计算时间远远超过时间片的时间时,开始并行处理才开始划算(经验法则)。

这是我的“本地”Windows实现,对于足够大的数组,最终使线程胜过单线程计算。

#include <stdafx.h>
#include <nativethreadTest.h>

#include <vector>
#include <cstdint>
#include <Windows.h>
#include <chrono>
#include <iostream>
#include <thread>

struct Range
{
    Range( const int32_t *p, size_t l)
        : data(p)
        , length(l)
        , result(0)
    {}
    const int32_t *data;
    size_t length;
    int32_t result;
};

static int32_t Sum(const int32_t * data, size_t length)
{
    int32_t sum = 0;
    const int32_t *end = data + length;
    for (; data != end; data++)
    {
        sum += *data;
    }
    return sum;
}

static int32_t TestSingleThreaded(const Range& range)
{
    return Sum(range.data, range.length);
}

DWORD 
WINAPI 
CalcThread
(_In_  LPVOID lpParameter
)
{
    Range * myRange = reinterpret_cast<Range*>(lpParameter);
    myRange->result = Sum(myRange->data, myRange->length);
    return 0;
}

static int32_t TestWithNCores(const Range& range, size_t ncores)
{
    int32_t result = 0;
    std::vector<Range> ranges;
    size_t nextStart = 0;
    size_t chunkLength = range.length / ncores;
    size_t remainder = range.length - chunkLength * ncores;
    while (nextStart < range.length)
    {
        ranges.push_back(Range(&range.data[nextStart], chunkLength));
        nextStart += chunkLength;
    }
    Range remainderRange(&range.data[range.length - remainder], remainder);

    std::vector<HANDLE> threadHandles;
    threadHandles.reserve(ncores);
    for (size_t i = 0; i < ncores; ++i)
    {
        threadHandles.push_back(::CreateThread(NULL, 0, CalcThread, &ranges[i], 0, NULL));
    }
    int32_t remainderResult = Sum(remainderRange.data, remainderRange.length);
    DWORD waitResult = ::WaitForMultipleObjects((DWORD)threadHandles.size(), &threadHandles[0], TRUE, INFINITE);
    if (WAIT_OBJECT_0 == waitResult)
    {
        for (auto& r : ranges)
        {
            result += r.result;
        }
        result += remainderResult;
    }
    else
    {
        throw std::runtime_error("Something went horribly - HORRIBLY wrong!");
    }
    for (auto& h : threadHandles)
    {
        ::CloseHandle(h);
    }
    return result;
}

static int32_t TestWithSTLThreads(const Range& range, size_t ncores)
{
    int32_t result = 0;
    std::vector<Range> ranges;
    size_t nextStart = 0;
    size_t chunkLength = range.length / ncores;
    size_t remainder = range.length - chunkLength * ncores;
    while (nextStart < range.length)
    {
        ranges.push_back(Range(&range.data[nextStart], chunkLength));
        nextStart += chunkLength;
    }
    Range remainderRange(&range.data[range.length - remainder], remainder);

    std::vector<std::thread> threads;
    for (size_t i = 0; i < ncores; ++i)
    {
        threads.push_back(std::thread([](Range* range){ range->result = Sum(range->data, range->length); }, &ranges[i]));
    }

    int32_t remainderResult = Sum(remainderRange.data, remainderRange.length);
    for (auto& t : threads)
    {
        t.join();
    }
    for (auto& r : ranges)
    {
        result += r.result;
    }
    result += remainderResult;
    return result;
}

void TestNativeThreads()
{
    const size_t DATA_SIZE = 800000000ULL;
    typedef std::vector<int32_t> DataVector;
    DataVector data;
    data.reserve(DATA_SIZE);

    for (size_t i = 0; i < DATA_SIZE; ++i)
    {
        data.push_back(static_cast<int32_t>(i));
    }

    Range r = { data.data(), data.size() };
    std::chrono::system_clock::time_point singleThreadedStart = std::chrono::high_resolution_clock::now();
    int32_t result = TestSingleThreaded(r);
    std::chrono::system_clock::time_point singleThreadedEnd = std::chrono::high_resolution_clock::now();
    std::cout
        << "Single threaded sum: "
        << std::chrono::duration_cast<std::chrono::milliseconds>(singleThreadedEnd - singleThreadedStart).count()
        << "ms." << " Result = " << result << std::endl;

    std::chrono::system_clock::time_point multiThreadedStart = std::chrono::high_resolution_clock::now();
    result = TestWithNCores(r, 8);
    std::chrono::system_clock::time_point multiThreadedEnd = std::chrono::high_resolution_clock::now();

    std::cout 
        << "Multi threaded sum: "
        << std::chrono::duration_cast<std::chrono::milliseconds>(multiThreadedEnd - multiThreadedStart).count()
        << "ms." << " Result = " << result << std::endl;

    std::chrono::system_clock::time_point stdThreadedStart = std::chrono::high_resolution_clock::now();
    result = TestWithSTLThreads(r, 8);
    std::chrono::system_clock::time_point stdThreadedEnd = std::chrono::high_resolution_clock::now();

    std::cout
        << "std::thread sum: "
        << std::chrono::duration_cast<std::chrono::milliseconds>(stdThreadedEnd - stdThreadedStart).count()
        << "ms." << " Result = " << result << std::endl;
}

这是我的机器上运行此代码的输出:

Single threaded sum: 382ms. Result = -532120576
Multi threaded sum: 234ms. Result = -532120576
std::thread sum: 245ms. Result = -532120576
Press any key to continue . . ..

最后但并非最不重要的是,我感到有必要提到这段代码的编写方式更像是一个内存IO性能基准测试而不是一个核心CPU计算基准测试。更好的计算基准测试应该使用少量数据,这些数据是本地的,适合于CPU缓存等。
也许将数据分成范围进行实验会很有趣。如果每个线程从开始到结束跳过ncores个间隔遍历数据呢?线程1:0 8 16... 线程2:1 9 17 ...等等。也许这样可以获得额外的速度优势。

那么,有没有一种方法可以强制std :: thread在单独的核心上生成?或者使用本机Windows线程? - rndm
Windows: SetThreadAffinityMask()。这个答案的重点是,std::thread可能做的事情比在基准测试中使用它好得多。另一个例子:它是否调用CoInitializeEx(..)? - BitTickler
对于8,000,000: 单线程求和:13毫秒。结果= -1805322496 多线程求和:2毫秒。结果= -1805322496 对于80,000,000: 单线程求和:133毫秒。结果= 216376832 多线程求和:22毫秒。结果= 216376832 我无法运行它以进行800,000,000次操作。这基本上破坏了我原始帖子中的std::thread性能,因为所有操作都是在未经优化的调试构建中完成的。 - rndm

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接