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

Question

我现在已经做了几年c#,我正在尝试学习一些新东西.所以我决定看看c ++,以不同的方式了解编程.

我一直在做大量阅读,但我今天刚开始写一些代码.

在运行VS2010的Windows 7/64位机器上,我创建了两个项目: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 ++,没有太多的想法进入它(试图学习,对吗？)int输入;

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

现在,一些警告.我设法找到了这个相关的SO问题.其中一个人写了一篇长篇答案,提到WOW64扭曲结果.我已经将项目设置为发布并经历了c ++项目的"属性"选项卡,启用听起来像它的所有内容都会让它变得快速.将平台更改为x64,但我不确定是否解决了他的问题.我对编译器选项没有经验,也许你们有更多的线索？

哦,结果:c#:0.32ms c ++:8.26ms.这有点奇怪.我是否误解了什么.Quad意味着什么？我从Web上的某个地方复制了c ++计时器代码,经历了所有的boost安装和include/libfile rigmarole.或许我实际上是在不知不觉中使用不同的乐器？或者有一些我没有使用的关键编译选项？或者c#代码可能是优化的,因为平均值是常数？

这是c ++命令行,来自Property页面 - > C/C++ - >命令行:/ 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:queue

任何帮助将不胜感激,谢谢.

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.9ms(从之前的10ms).这对我来说,实际上,你的绝大部分时间都不是花在哈希表中,而是花在分配器上.这是一个不公平的比较的原因是因为你的GC永远不会在这样一个简单的程序中收集,给它带来不正当的性能优势,并且原生分配器会对可用内存进行重要的缓存 - 但这种情况永远不会发生在如此微不足道的事情中例如,因为您从未分配或取消分配任何内容,因此无需缓存.

最后,Boost池实现是线程安全的,而您从不使用线程,因此GC可以回退到单线程实现,这将更快.

我使用了一个手动,非释放的非线程安全池分配器,对于C++,在C#(在我的机器上)下降到0.525ms到0.45ms.结论:由于两种语言的内存分配方案不同,原始结果非常偏斜,一旦解决了这些问题,差异就会变得相对最小.

自定义哈希(如Alexandre的回答中所述)将我的C++时间减少到0.34ms,现在比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
}