c# 到 c++ 字典到 unordered_map 结果

Question

我现在已经使用了几年的 C#，我正在尝试学习一些新东西。所以我决定看看 C++，以不同的方式了解编程。

我一直在做大量的阅读，但我今天才开始写一些代码。

在我的 Windows 7/64 位机器上，运行 VS2010，我创建了两个项目:1) 一个 c# 项目，可以让我按照习惯的方式编写内容。2) 一个让我玩的c++“makefile”项目，试图实现同样的事情。据我了解，这不是 .NET 项目。

我开始尝试用 10K 值填充字典。出于某种原因，C++ 慢了几个数量级。

这是下面的 c#。请注意，我在时间测量之后放入了一个函数，以确保它没有被编译器“优化”掉:

var freq = System.Diagnostics.Stopwatch.Frequency;

int i;
Dictionary<int, int> dict = new Dictionary<int, int>();
var clock = System.Diagnostics.Stopwatch.StartNew();

for (i = 0; i < 10000; i++)
     dict[i] = i;
clock.Stop();

Console.WriteLine(clock.ElapsedTicks / (decimal)freq * 1000M);
Console.WriteLine(dict.Average(x=>x.Value));
Console.ReadKey(); //Don't want results to vanish off screen

这是 c++，没有太多思考(尝试学习，对吧？) 整数输入；

LARGE_INTEGER frequency;        // ticks per second
LARGE_INTEGER t1, t2;           // ticks
double elapsedTime;

// get ticks per second
QueryPerformanceFrequency(&frequency);

int i;
boost::unordered_map<int, int> dict;
// start timer
QueryPerformanceCounter(&t1);

for (i=0;i<10000;i++)
    dict[i]=i;

// stop timer
QueryPerformanceCounter(&t2);

// compute and print the elapsed time in millisec
elapsedTime = (t2.QuadPart - t1.QuadPart) * 1000.0 / frequency.QuadPart;
cout << elapsedTime << " ms insert time\n";
int input;
cin >> input; //don't want console to disappear

现在，一些注意事项。 I managed to find this related SO question.其中一个人写了一个很长的答案，提到 WOW64 扭曲了结果。我已经将项目设置为发布，并通过了 c++ 项目的“属性”选项卡，启用了一切听起来会使其快速的东西。将平台更改为 x64，但我不确定这是否解决了他的 wow64 问题。我对编译器选项不是很熟悉，也许你们有更多线索？

哦，还有结果:c#:0.32ms c++: 8.26ms。这有点奇怪。我是否误解了 .Quad 的含义？我从网上的某个地方复制了 c++ 计时器代码，经历了所有的升压安装和 include/libfile rigmarole。或者也许我实际上在无意中使用了不同的乐器？或者有一些我没有使用过的关键编译选项？还是因为平均值是常数，所以优化了 C# 代码？

这里是c++命令行，来自Property page->C/C++->Command Line:/I"C:\Users\Carlos\Desktop\boost_1_47_0"/Zi/nologo/W3/WX-/MP/Ox/Oi/Ot/GL/D "_MBCS"/Gm-/EHsc/GS-/Gy-/arch:SSE2/fp:fast/Zc:wchar_t/Zc:forScope/Fp"x64\Release\MakeTest.pch"/Fa"x64\Release\"/Fo"x64\Release\"/Fd"x64\Release\vc100 .pdb"/Gd/errorReport:队列

如有任何帮助，我们将不胜感激。

Answer 1

一个简单的分配器更改将大大缩短时间。

boost::unordered_map<int, int, boost::hash<int>, std::equal_to<int>, boost::fast_pool_allocator<std::pair<const int, int>>> dict;

在我的系统上为 0.9 毫秒(之前为 10 毫秒)。这向我表明，实际上，你绝大部分的时间根本没有花在哈希表上，而是花在了分配器上。这是一个不公平比较的原因是因为您的 GC 永远不会在这样一个微不足道的程序中进行收集，从而赋予它不当的性能优势，并且 native 分配器会对空闲内存进行大量缓存 - 但它永远不会在这样一个微不足道的程序中发挥作用例如，因为您从未分配或取消分配任何东西，所以没有任何东西可以缓存。

最后，Boost 池实现是线程安全的，而您从不使用线程，因此 GC 可以退回到单线程实现，这会快得多。

我求助于手动滚动的非释放非线程安全池分配器，将 C++ 的时间降至 0.525 毫秒，C# 的时间降至 0.45 毫秒(在我的机器上)。结论:由于两种语言的内存分配方案不同，您的原始结果非常偏斜，一旦解决，差异就会变得相对较小。

自定义哈希器(如 Alexandre 的回答中所述)将我的 C++ 时间降低到 0.34 毫秒，现在比 C# 更快。

static const int MaxMemorySize = 800000;
static int FreedMemory = 0;
static int AllocatorCalls = 0;
static int DeallocatorCalls = 0;
template <typename T>
class LocalAllocator
{
  public:
      std::vector<char>* memory;
      int* CurrentUsed;
      typedef T value_type;
      typedef value_type * pointer;
      typedef const value_type * const_pointer;
      typedef value_type & reference;
      typedef const value_type & const_reference;
      typedef std::size_t size_type;
      typedef std::size_t difference_type;

    template <typename U> struct rebind { typedef LocalAllocator<U> other; };

    template <typename U>
    LocalAllocator(const LocalAllocator<U>& other) {
        CurrentUsed = other.CurrentUsed;
        memory = other.memory;
    }
    LocalAllocator(std::vector<char>* ptr, int* used) {
        CurrentUsed = used;
        memory = ptr;
    }
    template<typename U> LocalAllocator(LocalAllocator<U>&& other) {
        CurrentUsed = other.CurrentUsed;
        memory = other.memory;
    }
    pointer address(reference r) { return &r; }
    const_pointer address(const_reference s) { return &r; }
    size_type max_size() const { return MaxMemorySize; }
    void construct(pointer ptr, value_type&& t) { new (ptr) T(std::move(t)); }
    void construct(pointer ptr, const value_type & t) { new (ptr) T(t); }
    void destroy(pointer ptr) { static_cast<T*>(ptr)->~T(); }

    bool operator==(const LocalAllocator& other) const { return Memory == other.Memory; }
    bool operator!=(const LocalAllocator&) const { return false; }

    pointer allocate(size_type count) {
        AllocatorCalls++;
        if (*CurrentUsed + (count * sizeof(T)) > MaxMemorySize)
            throw std::bad_alloc();
        if (*CurrentUsed % std::alignment_of<T>::value) {
            *CurrentUsed += (std::alignment_of<T>::value - *CurrentUsed % std::alignment_of<T>::value);
        }
        auto val = &((*memory)[*CurrentUsed]);
        *CurrentUsed += (count * sizeof(T));
        return reinterpret_cast<pointer>(val);
    }
    void deallocate(pointer ptr, size_type n) {
        DeallocatorCalls++;
        FreedMemory += (n * sizeof(T));
    }

    pointer allocate() {
        return allocate(sizeof(T));
    }
    void deallocate(pointer ptr) {
        return deallocate(ptr, 1);
    }
};
int main() {
    LARGE_INTEGER frequency;        // ticks per second
    LARGE_INTEGER t1, t2;           // ticks
    double elapsedTime;

    // get ticks per second
    QueryPerformanceFrequency(&frequency);
    std::vector<char> memory;
    int CurrentUsed = 0;
    memory.resize(MaxMemorySize);

    struct custom_hash {
        size_t operator()(int x) const { return x; }
    };
    boost::unordered_map<int, int, custom_hash, std::equal_to<int>, LocalAllocator<std::pair<const int, int>>> dict(
        std::unordered_map<int, int>().bucket_count(),
        custom_hash(),
        std::equal_to<int>(),
        LocalAllocator<std::pair<const int, int>>(&memory, &CurrentUsed)
    );

    // start timer
    std::string str;
    QueryPerformanceCounter(&t1);

    for (int i=0;i<10000;i++)
        dict[i]=i;

    // stop timer
    QueryPerformanceCounter(&t2);

    // compute and print the elapsed time in millisec
    elapsedTime = ((t2.QuadPart - t1.QuadPart) * 1000.0) / frequency.QuadPart;
    std::cout << elapsedTime << " ms insert time\n";
    int input;
    std::cin >> input; //don't want console to disappear
}