稀疏哈希映射对于特定数据非常慢

tl;dr:为什么关键查找sparse_hash_map对于特定数据，速度变慢约 50 倍？

我正在测试速度关键查找 for sparse_hash_map来自 Google 的稀疏哈希库，使用我编写的非常简单的 Cython 包装器。哈希表包含uint32_t键和uint16_t价值观。对于随机键、值和查询，我每秒的查找次数超过 100 万次。然而，对于特定数据，我需要的性能勉强超过 20k 查找/秒。

包装纸是here https://github.com/Pastafarianist/cython-sparsehash。运行缓慢的表是here https://drive.google.com/file/d/0B0Jnpz9ldbuHUzFuRGhUSkVtYWc/view?usp=sharing。基准测试代码是：

benchmark.pyx:

from sparsehash cimport SparseHashMap
from libc.stdint cimport uint32_t
from libcpp.vector cimport vector
import time
import numpy as np

def fill_randomly(m, size):
    keys = np.random.random_integers(0, 0xFFFFFFFF, size)
    # 0 is a special domain-specific value
    values = np.random.random_integers(1, 0xFFFF, size)
    for j in range(size):
        m[keys[j]] = values[j]

def benchmark_get():
    cdef int dummy
    cdef uint32_t i, j, table_key
    cdef SparseHashMap m
    cdef vector[uint32_t] q_keys
    cdef int NUM_QUERIES = 1000000
    cdef uint32_t MAX_REQUEST = 7448 * 2**19 - 1  # this is domain-specific

    time_start = time.time()

    ### OPTION 1 ###
    m = SparseHashMap('17.shash')

    ### OPTION 2 ###
    # m = SparseHashMap(16130443)
    # fill_randomly(m, 16130443)

    q_keys = np.random.random_integers(0, MAX_REQUEST, NUM_QUERIES)

    print("Initialization: %.3f" % (time.time() - time_start))

    dummy = 0

    time_start = time.time()

    for i in range(NUM_QUERIES):
        table_key = q_keys[i]
        dummy += m.get(table_key)
        dummy %= 0xFFFFFF  # to prevent overflow error

    time_elapsed = time.time() - time_start

    if dummy == 42:
        # So that the unused variable is not optimized away
        print("Wow, lucky!")

    print("Table size: %d" % len(m))
    print("Total time: %.3f" % time_elapsed)
    print("Seconds per query: %.8f" % (time_elapsed / NUM_QUERIES))
    print("Queries per second: %.1f" % (NUM_QUERIES / time_elapsed))

def main():
    benchmark_get()

benchmark.pyxbld（因为pyximport应在 C++ 模式下编译）：

def make_ext(modname, pyxfilename):
    from distutils.extension import Extension
    return Extension(
        name=modname,
        sources=[pyxfilename],
        language='c++'
    )

run.py:

import pyximport
pyximport.install()

import benchmark
benchmark.main()

结果为17.shash are:

Initialization: 2.612
Table size: 16130443
Total time: 48.568
Seconds per query: 0.00004857
Queries per second: 20589.8

对于随机数据：

Initialization: 25.853
Table size: 16100260
Total time: 0.891
Seconds per query: 0.00000089
Queries per second: 1122356.3

密钥分布在17.shash这是 （plt.hist(np.fromiter(m.keys(), dtype=np.uint32, count=len(m)), bins=50)):

从文档上sparsehash https://sparsehash.googlecode.com/svn/trunk/doc/implementation.html and gcc https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a01206_source.html#l00118似乎这里使用了简单的哈希（即x散列到x).

除了哈希冲突之外，还有什么明显的因素可能导致此行为吗？根据我的发现，集成自定义哈希函数（即重载std::hash<uint32_t>）在 Cython 包装器中。

我找到了一个可行的解决方案，但它并不漂亮。

sparsehash_wrapper.cpp:

#include "sparsehash/sparse_hash_map"
#include "stdint.h"

// syntax borrowed from
// https://stackoverflow.com/questions/14094104/google-sparse-hash-with-murmur-hash-function

struct UInt32Hasher {
    size_t operator()(const uint32_t& x) const {
        return (x ^ (x << 17) ^ (x >> 13) + 3238229671);
    }    
};

template<class Key, class T>
class sparse_hash_map : public google::sparse_hash_map<Key, T, UInt32Hasher> {};

这是一个自定义哈希函数，我可以将其集成到现有包装器中，只需进行最少的代码更改：我只需替换sparsehash/sparse_hash_map与路径sparsehash_wrapper.cpp在赛通.pxd文件。到目前为止，唯一的问题是pyximport找不到sparsehash_wrapper.cpp除非我指定完整的绝对路径.pxd.

问题确实在于冲突：重新创建具有相同内容的哈希映射后17.shash从头开始（即创建一个空映射并插入每个（键，值）对17.shash进入其中），性能达到 1M+ req/sec。