以最快的方式获取16K键 - 值对？ [英] The fastest way to retrieve 16k Key-Value pairs?

问题描述

确定，这里是我的情况：

• 我有一个功能 - 比方说 U64计算（U64 X） - 这需要一个64位整型参数，执行一些CPU密集型操作，并返回64比特值


• 现在，因为我知道所有可能的输入（ X s）表示函数事先的（也有一些16000虽然），我想这可能是更好的pre-计算它们，然后获取它们点播（从阵列状结构）。


• 理想的情况是将其全部保存在某些阵列 U64 CALC [] 和索引（ X 再次）


• 如下的问题：我可以知道我的计算功能可能的输入是什么，但他们是最绝对不会连续（例如：未从1到16000，但值可能去低为0，高达上万亿部分 - 总withing 64位范围）

• I have a function - let's say U64 calc (U64 x) - which takes a 64-bit integer parameter, performs some CPU-intensive operation, and returns a 64-bit value
• Now, given that I know ALL possible inputs (the xs) of that function beforehand (there are some 16000 though), I thought it might be better to pre-calculate them and then fetch them on demand (from an array-like structure).
• The ideal situation would be to store them all in some array U64 CALC[] and retrieve them by index (the x again)
• And here's the issue : I may know what the possible inputs for my calc function are, but they are most definitely NOT consecutive (e.g. not from 1 to 16000, but values that may go as low as 0 and as high as some trillions - always withing a 64-bit range)

例如。

  X        CALC[X]
-----------------------
  123123   123123123
  12312    12312312
  897523   986123

  etc.

在这里，我的问题是：

• 您将如何保存呢？


• 什么解决方法是你preFER？


• 现在，假设这些值（从 CALC ）的将要被访问的一些数千到数百万次，每秒下，这将是最好的解决方案的性能代价？

• How would you store them?
• What workaround would you prefer?
• Now, given that these values (from CALC) will have to be accessed some thousands-to-millions of times, per sec, which would be the best solution performance-wise?

的 注意：我没有任何提及，我认为还是试图尽量不要把答案变成对B型的，事情的一些争论，而且大多不会影响任何人... 的

Note : I'm no mentioning anything I've thought of or tried so as not to turn the answers into some debate of A vs B type-of-thing, and mostly not influence anyone...

推荐答案

我将使用某种散列函数创建一个索引到U64对其中一个关键是从创建的值和其他的替换值。技术上，指数可能是三个字节长（假设1600万 - 16000000 - 对）如果你需要节省空间，但我会用u32s。如果存储的值不匹配上计算（哈希冲突）的价值，您需要输入溢出处理程序。

I would use some sort of hash function that creates an index to a u64 pair where one is the value the key was created from and the other the replacement value. Technically the index could be three bytes long (assuming 16 million -"16000 thousand" - pairs) if you need to conserve space but I'd use u32s. If the stored value does not match the value computed on (hash collision) you'd enter an overflow handler.

• 您需要确定一个自定义的哈希算法，以适应您的数据


• 既然你知道数据的大小，你不需要算法，允许数据增长。


• 我会谨慎使用一些标准算法，因为它们很少满足特定的数据


• 我想，除非你确信code是所见即所得（不产生大量的隐形电话）
谨防使用C ++的方法

• 您指数应比对的数量
大25％

• You need to determine a custom hashing algorithm to fit your data
• Since you know the size of the data you don't need algorithms that allow the data to grow.
• I'd be wary of using some standard algorithm because they seldom fit specific data
• I'd be wary of using a C++ method unless you are sure the code is WYSIWYG (doesn't generate a lot of invisible calls)
• Your index should be 25% larger than the number of pairs

通过所有可能的输入运行和确定最小值，最大值，为冲突的数量平均值和标准偏差，并使用这些来确定可接受的性能水平。然后配置文件，以达到最佳的code。

Run through all possible inputs and determine min, max, average and standard deviation for the number of collisions and use these to determine the acceptable performance level. Then profile to achieve the best possible code.

所需的存储空间（使用U32指数）出来（4 * 1.25）+ 8 + 8 = 21％的对或336字节MEB，一个典型的PC机上没有问题。

The required memory space (using a u32 index) comes out to (4*1.25)+8+8 = 21 bytes per pair or 336 MeB, no problem on a typical PC.

________ ________编辑

我一直在质疑的RocketRoy把我的钱用在我的嘴。这里所说：

I have been challenged by "RocketRoy" to put my money where my mouth is. Here goes:

问题有一个（固定大小）哈希索引冲突处理的事情。要设置阶段：

The problem has to do with collision handling in a (fixed size) hash index. To set the stage:

• 我具有n个条目的列表，其中在输入一个字段包含散列从计算出的值v


• 我有N * 1.25（约）的indeces的载体中，使得的indeces x的数量是一个素数


• 素数y计算它为x
的一小部分

• 矢量被初始化为-1说表示无人居住

pretty标准的东西，我想你会同意的。

Pretty standard stuff I think you'll agree.

在列表中的条目进行处理和散列值h计算并modulo'd并用来作为一个指数到载体和索引的条目被放置在那里。

The entries in the list are processed and the hash value h computed and modulo'd and used as an index into the vector and the index to the entry is placed there.

最后，我遇到这样的向量入口指向索引被占用的情况（不包含-1） - 瞧，碰撞

Eventually I encounter the situation where the vector entry pointed to by the index is occupied (doesn't contain -1) - voilà, a collision.

所以，我该怎么办？我保持原来的H作为豪，Y添加到小时，取模x，并得到一个新的索引到载体。如果该项未占用我使用它，否则我继续加上y模x，直到我到达豪。在理论上，这会发生，因为x和y是质数。在实践中，x是大于n所以它不会。

So what do I do? I keep the original h as ho, add y to h and take modulo x and get a new index into the vector. If the entry is unoccupied I use it, otherwise I continue with add y modulo x until I reach ho. In theory, this will happen because both x and y are prime numbers. In practice x is larger than n so it won't.

因此​​，重新哈希即RocketRoy声称这是非常昂贵的是没有这样的事情。

So the "re-hash" that RocketRoy claims is very costly is no such thing.

这种方法的棘手的部分 - 与所有散列方法 - 是：

The tricky part with this method - as with all hashing methods - is to:

• 确定对于x一个合适的值（变得不那么棘手X越大最终使用）


• 确定算法为H = A（V）％×使得轰的指数合理均匀（随机），并在尽可能少的冲突尽可能
索引矢量

• 确定y，使得碰撞指标一个合适的值相当均匀（随机）进入指数的vector

________ ________编辑

我很抱歉，我已经采取了这么久才产生这种code ...其他的东西有较高的优先级。

I'm sorry I've taken so long to produce this code ... other things have had higher priorities.

总之，这里是code这证明散列具有快速查找比一个二叉树更好的前景。它贯穿一束散列索引大小和算法寻找该特定数据的最合适的组合，以帮助的。对于每一个算法code将打印第一个索引的大小，使得没有查询需要更长的时间超过十四搜索（最坏情况二进制搜索），平均需要查找小于1.5的搜索。

Anyway, here is the code which proves that hashing has better prospects for quick lookups than a binary tree. It runs through a bunch of hashing index sizes and algorithms to aid in finding the most suitable combo for the specific data. For every algorithm the code will print the first index size such that no lookup takes longer than fourteen searches (worst case for binary searching) and an average lookup takes less than 1.5 searches.

我在这些类型的应用程序素数的喜爱，如果你还没有注意到。

I have a fondness for prime numbers in these types of applications, in case you haven't noticed.

有创造与强制性溢出处理哈希算法的许多方面。我选择了简单假设它会转化为速度......它确实。在我的笔记本电脑，在i5中号480 @ 2.67 GHz的平均查找需要55到60个时钟周期（出来以每秒约4500万的查询）。我实现了一个特殊的get操作具有恒定数量的indeces和同上翻版​​值和周期计数下降到40（每秒6​​500万的查询）。如果你看看行调用getOpSpec我相异或0x444到索引行使缓存，实现更真实的世界般的结果。

There are many ways of creating a hashing algorithm with its mandatory overflow handling. I opted for simplicity assuming it will translate into speed ... and it does. On my laptop with an i5 M 480 @ 2.67 GHz an average lookup requires between 55 and 60 clock cycles (comes out to around 45 million lookups per second). I implemented a special get operation with a constant number of indeces and ditto rehash value and the cycle count dropped to 40 (65 million lookups per second). If you look at the line calling getOpSpec the index i is xor'ed with 0x444 to exercise the caches to achieve more "real world"-like results.

我必须再次指出，程序会为具体数据合适的组合。其他数据可能需要不同的组合。

I must again point out that the program suggests suitable combinations for the specific data. Other data may require a different combo.

源$ C ​​$ C包含用于生成16000无符号长长对和测试不同的常数code（索引大小和老调重弹的值）：

The source code contains both the code for generating the 16000 unsigned long long pairs and for testing different constants (index sizes and rehash values):

#include <windows.h>

#define i8    signed char
#define i16          short
#define i32          long
#define i64          long long
#define id  i64
#define u8           char
#define u16 unsigned short
#define u32 unsigned long
#define u64 unsigned long long
#define ud  u64

#include <string.h>
#include <stdio.h>

u64 prime_find_next     (const u64 value);
u64 prime_find_previous (const u64 value);

static inline volatile unsigned long long rdtsc_to_rax (void)
{
  unsigned long long lower,upper;

  asm volatile( "rdtsc\n"
                : "=a"(lower), "=d"(upper));
  return lower|(upper<<32);
}

static u16 index[65536];

static u64 nindeces,rehshFactor;

static struct PAIRS {u64 oval,rval;} pairs[16000] = {
#include "pairs.h"
};

struct HASH_STATS
{
  u64 ninvocs,nrhshs,nworst;
} getOpStats,putOpStats;

i8 putOp (u16 index[], const struct PAIRS data[], const u64 oval, const u64 ci)
{
  u64 nworst=1,ho,h,i;
  i8 success=1;

  ++putOpStats.ninvocs;
  ho=oval%nindeces;
  h=ho;
  do
  {
    i=index[h];
    if (i==0xffff)    /* unused position */
    {
      index[h]=(u16)ci;
      goto added;
    }
    if (oval==data[i].oval) goto duplicate;

    ++putOpStats.nrhshs;
    ++nworst;

    h+=rehshFactor;
    if (h>=nindeces) h-=nindeces;
  } while (h!=ho);

  exhausted:    /* should not happen */
  duplicate:
    success=0;

  added:
  if (nworst>putOpStats.nworst) putOpStats.nworst=nworst;

  return success;
}

i8 getOp (u16 index[], const struct PAIRS data[], const u64 oval, u64 *rval)
{
  u64 ho,h,i;
  i8 success=1;

  ho=oval%nindeces;
  h=ho;
  do
  {
    i=index[h];
    if (i==0xffffu) goto not_found;    /* unused position */

    if (oval==data[i].oval)
    {
      *rval=data[i].rval;    /* fetch the replacement value */
      goto found;
    }

    h+=rehshFactor;
    if (h>=nindeces) h-=nindeces;
  } while (h!=ho);

  exhausted:
  not_found:    /* should not happen */
    success=0;

  found:

  return success;
}

volatile i8 stop = 0;

int main (int argc, char *argv[])
{
  u64 i,rval,mulup,divdown,start;
  double ave;

  SetThreadAffinityMask (GetCurrentThread(), 0x00000004ull);

  divdown=5;   //5
  while (divdown<=100)
  {
    mulup=3;  // 3
    while (mulup<divdown)
    {
      nindeces=16000;
      while (nindeces<65500)
      {
        nindeces=   prime_find_next     (nindeces);
        rehshFactor=nindeces*mulup/divdown;
        rehshFactor=prime_find_previous (rehshFactor);

        memset (index, 0xff, sizeof(index));
        memset (&putOpStats, 0, sizeof(struct HASH_STATS));

        i=0;
        while (i<16000)
        {
          if (!putOp (index, pairs, pairs[i].oval, (u16) i)) stop=1;

          ++i;
        }

        ave=(double)(putOpStats.ninvocs+putOpStats.nrhshs)/(double)putOpStats.ninvocs;
        if (ave<1.5 && putOpStats.nworst<15)
        {
          start=rdtsc_to_rax ();
          i=0;
          while (i<16000)
          {
            if (!getOp (index, pairs, pairs[i^0x0444]. oval, &rval)) stop=1;
            ++i;
          }
          start=rdtsc_to_rax ()-start+8000;   /* 8000 is half of 16000 (pairs), for rounding */

          printf ("%u;%u;%u;%u;%1.3f;%u;%u\n", (u32)mulup, (u32)divdown, (u32)nindeces, (u32)rehshFactor, ave, (u32) putOpStats.nworst, (u32) (start/16000ull));

          goto found;
        }

        nindeces+=2;
      }
      printf ("%u;%u\n", (u32)mulup, (u32)divdown);

      found:
      mulup=prime_find_next (mulup);
    }
    divdown=prime_find_next (divdown);
  }

  SetThreadAffinityMask (GetCurrentThread(), 0x0000000fu);

  return 0;
}

这是不可能包括所生成的对文件（一个答案是明显局限于30000个字符）。但是，消息发送到我的收件箱，我会寄出。

It was not possible to include the generated pairs file (an answer is apparently limited to 30000 characters). But send a message to my inbox and I'll mail it.

和这些结果如下：

3;5;35569;21323;1.390;14;73
3;7;33577;14389;1.435;14;60
5;7;32069;22901;1.474;14;61
3;11;35107;9551;1.412;14;59
5;11;33967;15427;1.446;14;61
7;11;34583;22003;1.422;14;59
3;13;34253;7901;1.439;14;61
5;13;34039;13063;1.443;14;60
7;13;32801;17659;1.456;14;60
11;13;33791;28591;1.436;14;59
3;17;34337;6053;1.413;14;59
5;17;32341;9511;1.470;14;61
7;17;32507;13381;1.474;14;62
11;17;33301;21529;1.454;14;60
13;17;34981;26737;1.403;13;59
3;19;33791;5333;1.437;14;60
5;19;35149;9241;1.403;14;59
7;19;33377;12289;1.439;14;97
11;19;34337;19867;1.417;14;59
13;19;34403;23537;1.430;14;61
17;19;33923;30347;1.467;14;61
3;23;33857;4409;1.425;14;60
5;23;34729;7547;1.429;14;60
7;23;32801;9973;1.456;14;61
11;23;33911;16127;1.445;14;60
13;23;33637;19009;1.435;13;60
17;23;34439;25453;1.426;13;60
19;23;33329;27529;1.468;14;62
3;29;32939;3391;1.474;14;62
5;29;34543;5953;1.437;13;60
7;29;34259;8263;1.414;13;59
11;29;34367;13033;1.409;14;60
13;29;33049;14813;1.444;14;60
17;29;34511;20219;1.422;14;60
19;29;33893;22193;1.445;13;61
23;29;34693;27509;1.412;13;92
3;31;34019;3271;1.441;14;60
5;31;33923;5449;1.460;14;61
7;31;33049;7459;1.442;14;60
11;31;35897;12721;1.389;14;59
13;31;35393;14831;1.397;14;59
17;31;33773;18517;1.425;14;60
19;31;33997;20809;1.442;14;60
23;31;34841;25847;1.417;14;59
29;31;33857;31667;1.426;14;60
3;37;32569;2633;1.476;14;61
5;37;34729;4691;1.419;14;59
7;37;34141;6451;1.439;14;60
11;37;34549;10267;1.410;13;60
13;37;35117;12329;1.423;14;60
17;37;34631;15907;1.429;14;63
19;37;34253;17581;1.435;14;60
23;37;32909;20443;1.453;14;61
29;37;33403;26177;1.445;14;60
31;37;34361;28771;1.413;14;59
3;41;34297;2503;1.424;14;60
5;41;33587;4093;1.430;14;60
7;41;34583;5903;1.404;13;59
11;41;32687;8761;1.440;14;60
13;41;34457;10909;1.439;14;60
17;41;34337;14221;1.425;14;59
19;41;32843;15217;1.476;14;62
23;41;35339;19819;1.423;14;59
29;41;34273;24239;1.436;14;60
31;41;34703;26237;1.414;14;60
37;41;33343;30089;1.456;14;61
3;43;34807;2423;1.417;14;59
5;43;35527;4129;1.413;14;60
7;43;33287;5417;1.467;14;61
11;43;33863;8647;1.436;14;60
13;43;34499;10427;1.418;14;78
17;43;34549;13649;1.431;14;60
19;43;33749;14897;1.429;13;60
23;43;34361;18371;1.409;14;59
29;43;33149;22349;1.452;14;61
31;43;34457;24821;1.428;14;60
37;43;32377;27851;1.482;14;81
41;43;33623;32057;1.424;13;59
3;47;33757;2153;1.459;14;61
5;47;33353;3547;1.445;14;61
7;47;34687;5153;1.414;13;59
11;47;34519;8069;1.417;14;60
13;47;34549;9551;1.412;13;59
17;47;33613;12149;1.461;14;61
19;47;33863;13687;1.443;14;60
23;47;35393;17317;1.402;14;59
29;47;34747;21433;1.432;13;60
31;47;34871;22993;1.409;14;59
37;47;34729;27337;1.425;14;59
41;47;33773;29453;1.438;14;60
43;47;31253;28591;1.487;14;62
3;53;33623;1901;1.430;14;59
5;53;34469;3229;1.430;13;60
7;53;34883;4603;1.408;14;59
11;53;34511;7159;1.412;13;59
13;53;32587;7963;1.453;14;60
17;53;34297;10993;1.432;13;80
19;53;33599;12043;1.443;14;64
23;53;34337;14897;1.415;14;59
29;53;34877;19081;1.424;14;61
31;53;34913;20411;1.406;13;59
37;53;34429;24029;1.417;13;60
41;53;34499;26683;1.418;14;59
43;53;32261;26171;1.488;14;62
47;53;34253;30367;1.437;14;79
3;59;33503;1699;1.432;14;61
5;59;34781;2939;1.424;14;60
7;59;35531;4211;1.403;14;59
11;59;34487;6427;1.420;14;59
13;59;33563;7393;1.453;14;61
17;59;34019;9791;1.440;14;60
19;59;33967;10937;1.447;14;60
23;59;33637;13109;1.438;14;60
29;59;34487;16943;1.424;14;59
31;59;32687;17167;1.480;14;61
37;59;35353;22159;1.404;14;59
41;59;34499;23971;1.431;14;60
43;59;34039;24799;1.445;14;60
47;59;32027;25471;1.499;14;62
53;59;34019;30557;1.449;14;61
3;61;35059;1723;1.418;14;60
5;61;34351;2803;1.416;13;60
7;61;35099;4021;1.412;14;59
11;61;34019;6133;1.442;14;60
13;61;35023;7459;1.406;14;88
17;61;35201;9803;1.414;14;61
19;61;34679;10799;1.425;14;101
23;61;34039;12829;1.441;13;60
29;61;33871;16097;1.446;14;60
31;61;34147;17351;1.427;14;61
37;61;34583;20963;1.412;14;59
41;61;32999;22171;1.452;14;62
43;61;33857;23857;1.431;14;98
47;61;34897;26881;1.431;14;60
53;61;33647;29231;1.434;14;60
59;61;32999;31907;1.454;14;60
3;67;32999;1471;1.455;14;61
5;67;35171;2621;1.403;14;59
7;67;33851;3533;1.463;14;61
11;67;34607;5669;1.437;14;60
13;67;35081;6803;1.416;14;61
17;67;33941;8609;1.417;14;60
19;67;34673;9829;1.427;14;60
23;67;35099;12043;1.415;14;60
29;67;33679;14563;1.452;14;61
31;67;34283;15859;1.437;14;60
37;67;32917;18169;1.460;13;61
41;67;33461;20443;1.441;14;61
43;67;34313;22013;1.426;14;60
47;67;33347;23371;1.452;14;61
53;67;33773;26713;1.434;14;60
59;67;35911;31607;1.395;14;58
61;67;34157;31091;1.431;14;63
3;71;34483;1453;1.423;14;59
5;71;34537;2423;1.428;14;59
7;71;33637;3313;1.428;13;60
11;71;32507;5023;1.465;14;79
13;71;35753;6529;1.403;14;59
17;71;33347;7963;1.444;14;61
19;71;35141;9397;1.410;14;59
23;71;32621;10559;1.475;14;61
29;71;33637;13729;1.429;14;60
31;71;33599;14657;1.443;14;60
37;71;34361;17903;1.396;14;59
41;71;33757;19489;1.435;14;61
43;71;34583;20939;1.413;14;59
47;71;34589;22877;1.441;14;60
53;71;35353;26387;1.418;14;59
59;71;35323;29347;1.406;14;59
61;71;35597;30577;1.401;14;59
67;71;34537;32587;1.425;14;59
3;73;34613;1409;1.418;14;59
5;73;32969;2251;1.453;14;62
7;73;33049;3167;1.448;14;61
11;73;33863;5101;1.435;14;60
13;73;34439;6131;1.456;14;60
17;73;33629;7829;1.455;14;61
19;73;34739;9029;1.421;14;60
23;73;33071;10399;1.469;14;61
29;73;33359;13249;1.460;14;61
31;73;33767;14327;1.422;14;59
37;73;32939;16693;1.490;14;62
41;73;33739;18947;1.438;14;60
43;73;33937;19979;1.432;14;61
47;73;33767;21739;1.422;14;59
53;73;33359;24203;1.435;14;60
59;73;34361;27767;1.401;13;59
61;73;33827;28229;1.443;14;60
67;73;34421;31583;1.423;14;71
71;73;33053;32143;1.447;14;60
3;79;35027;1327;1.410;14;60
5;79;34283;2161;1.432;14;60
7;79;34439;3049;1.432;14;60
11;79;34679;4817;1.416;14;59
13;79;34667;5701;1.405;14;59
17;79;33637;7237;1.428;14;60
19;79;34469;8287;1.417;14;60
23;79;34439;10009;1.433;14;60
29;79;33427;12269;1.448;13;61
31;79;33893;13297;1.445;14;61
37;79;33863;15823;1.439;14;60
41;79;32983;17107;1.450;14;60
43;79;34613;18803;1.431;14;60
47;79;33457;19891;1.457;14;61
53;79;33961;22777;1.435;14;61
59;79;32983;24631;1.465;14;60
61;79;34337;26501;1.428;14;60
67;79;33547;28447;1.458;14;61
71;79;32653;29339;1.473;14;61
73;79;34679;32029;1.429;14;64
3;83;35407;1277;1.405;14;59
5;83;32797;1973;1.451;14;60
7;83;33049;2777;1.443;14;61
11;83;33889;4483;1.431;14;60
13;83;35159;5503;1.409;14;59
17;83;34949;7151;1.412;14;59
19;83;32957;7541;1.467;14;61
23;83;32569;9013;1.470;14;61
29;83;33287;11621;1.474;14;61
31;83;33911;12659;1.448;13;60
37;83;33487;14923;1.456;14;62
41;83;33587;16573;1.438;13;60
43;83;34019;17623;1.435;14;60
47;83;31769;17987;1.483;14;62
53;83;33049;21101;1.451;14;61
59;83;32369;23003;1.465;14;61
61;83;32653;23993;1.469;14;61
67;83;33599;27109;1.437;14;61
71;83;33713;28837;1.452;14;61
73;83;33703;29641;1.454;14;61
79;83;34583;32911;1.417;14;59
3;89;34147;1129;1.415;13;60
5;89;32797;1831;1.461;14;61
7;89;33679;2647;1.443;14;73
11;89;34543;4261;1.427;13;60
13;89;34603;5051;1.419;14;60
17;89;34061;6491;1.444;14;60
19;89;34457;7351;1.422;14;79
23;89;33529;8663;1.450;14;61
29;89;34283;11161;1.431;14;60
31;89;35027;12197;1.411;13;59
37;89;34259;14221;1.403;14;59
41;89;33997;15649;1.434;14;60
43;89;33911;16127;1.445;14;60
47;89;34949;18451;1.419;14;59
53;89;34367;20443;1.434;14;60
59;89;33791;22397;1.430;14;59
61;89;34961;23957;1.404;14;59
67;89;33863;25471;1.433;13;60
71;89;35149;28031;1.414;14;79
73;89;33113;27143;1.447;14;60
79;89;32909;29209;1.458;14;61
83;89;33617;31337;1.400;14;59
3;97;34211;1051;1.448;14;60
5;97;34807;1789;1.430;14;60
7;97;33547;2417;1.446;14;60
11;97;35171;3967;1.407;14;89
13;97;32479;4349;1.474;14;61
17;97;34319;6011;1.444;14;60
19;97;32381;6337;1.491;14;64
23;97;33617;7963;1.421;14;59
29;97;33767;10093;1.423;14;59
31;97;33641;10739;1.447;14;60
37;97;34589;13187;1.425;13;60
41;97;34171;14437;1.451;14;60
43;97;31973;14159;1.484;14;62
47;97;33911;16127;1.445;14;61
53;97;34031;18593;1.448;14;80
59;97;32579;19813;1.457;14;61
61;97;34421;21617;1.417;13;60
67;97;33739;23297;1.448;14;60
71;97;33739;24691;1.435;14;60
73;97;33863;25471;1.433;13;60
79;97;34381;27997;1.419;14;59
83;97;33967;29063;1.446;14;60
89;97;33521;30727;1.441;14;60

COLS 1和2被用于计算翻版值和索引大小之间的粗略关系。接下来的两个是第一个索引大小/翻版要素组合这与14搜索最坏情况为平均查找小于1.5的搜索。然后平均和最坏的情况。最后，最后一列是每查找时钟周期的平均数目。它并没有考虑到阅读时间标记寄存器所需的时间。

Cols 1 and 2 are used to calculate a rough relationship between the rehash value and the index size. The next two are the first index size/rehash factor combination which averages less than 1.5 searches for a lookup with a worst case of 14 searches. Then average and worst case. Finally, the last column is the average number of clock cycles per lookup. It does not take into account the time required to read the time stamp register.

最佳常数的实际存储空间（的indeces的＃= 31253和翻版因子= 28591）出来到超过我最初显示（16000 * 2 * 8 + 1,25 * 16000 * 2 => 296000字节） 。的实际尺寸是16000 * 2 * 8 + 31253 * 2 => 318506

The actual memory space for the best constants (# of indeces = 31253 and rehash factor = 28591) comes out to more than I initially indicated (16000*2*8 + 1,25*16000*2 => 296000 bytes). The actual size is 16000*2*8+31253*2 => 318506.

最快的组合是11/31与35897索引大小和12721.老调重弹这个值，平均1.389（1哈希初期0.389 +老调重弹）最大的14（1 + 13）的大致比例。

The fastest combination is an approximate ratio of 11/31 with an index size of 35897 and rehash value of 12721. This will average 1.389 (1 initial hash + 0.389 rehashes) with a maximum of 14 (1+13).

________ ________编辑

我去掉了发现跳转;在main（）来显示所有的组合，这表明更好的性能，可以在一个更大的索引大小为代价的，当然。例如，组合57667和33797产量和1.192的平均和6的组合最大翻版44543 23399和产生一个1.249的平均10最大老调重弹（这样可以节省（57667-44543）* 2 = 26468字节的索引表相比， 33797分之57667）。

I removed the "goto found;" in main () to show all combinations and it shows that much better performance is possible, of course at the expense of a larger index size. For example the combination 57667 and 33797 yields and average of 1.192 and a maximum rehash of 6. The combination 44543 and 23399 yields a 1.249 average and 10 maximum rehashes (it saves (57667-44543)*2=26468 bytes of index table compared to 57667/33797).

与硬codeD散列索引的尺寸和老调重弹的因素专业功能将在比较变量的时候60-70％执行。这可能是由于编译器（gcc 64位）以取代乘法模，并没有从内存位置读取值，因为他们将是$ C $光盘作为即时值。

Specialized functions with hard-coded hash index size and rehash factor will execute in 60-70% of the time compared to variables. This is probably due to the compiler (gcc 64-bit) substituting the modulo with multiplications and not having to fetch the values from memory locations as they will be coded as immediate values.

________ ________编辑

在高速缓存的问题，我看到两个问题。

On the subject of caches I see two issues.

首先是数据cacheing我不认为将是可能的，因为查找将只是在一些较大的过程中迈出的一小步，你运行表数据的高速缓存行的风险开始失效较轻或（可能）更大程度上 - 如果不是全部 - 其他的数据访问在更大过程中的其他步骤。我的e越code所执行，并在过程数据存取作为一个整体的可能性就越小将是任何有关查找数据将保持在高速缓存（这可能是也可能不是相关的业务方案的情况）。找到使用（我的）散列你会遇到两个缓存缺失的项（一个加载索引的正确部分，另一加载区域containg条目本身）为每一个需要被执行的比较。查找第一次尝试一个项目将耗资2失误，第二次尝试4等。在我的例子查找每60个时钟周期平均成本意味着，该表可能完全在L2缓存和L1不必去那里居住中大多数的情况下。我X86-64 CPU有L1-3，RAM等待约4，10，40和100这对我表明RAM完全被拒之门外，各国L3居多。

The first is data cacheing which I don't think will be possible because the lookup will just be a small step in some larger process and you run the risk of the table data's cache lines begin invalidated to a lesser or (probably) greater degree - if not entirely - by other data accesses in other steps of the larger process. I e the more code executed and data accessed in the process as a whole the less likely it will be that any pertinent lookup data will remain in the caches (this may or may not be pertinent to the OP's situation). To find an entry using (my) hashing you will encounter two cache misses (one to load the correct part of the index, and the other to load the area containg the entry itself) for every comparison that needs to be performed. Finding an entry on the first try will have cost two misses, the second try four etc. In my example the 60 clock cycle average cost per lookup implies that the table probably resided entirely in the L2 cache and with L1 not having to go there in a majority of the cases. My x86-64 CPU has L1-3, RAM wait states of approximately 4, 10, 40 and 100 which to me shows that RAM was completely kept out and L3 mostly.

二是code cacheing这将有较显著影响，如果是小，紧张，内衬和一些控制权转移（跳转和调用）。我的哈希常规可能完全驻留在L1 code缓存。为更正常的情况下，较少的code高速缓存行的数目加载它会更快。

The second is code cacheing which will have a more significant impact if it is small, tight, in-lined and with few control transfers (jumps and calls). My hash routine probably resides entirely in the L1 code cache. For more normal cases, the fewer the number of code cache line loads the faster it will be.

这篇关于以最快的方式获取16K键 - 值对？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！