查找速度比 std::set

Question

我需要更快地查找一些遗留数据包处理代码的成员资格，这些代码需要识别具有特定 ID 的数据包是否在特定列表中。

列表每隔几秒更新一次，而数据包匹配非常频繁，因此查找性能比 insertion/deletion 等更重要

一般流程：

forall(special_PacketIDs)
{
  pktIdSet.insert(theSpecialPktId)
}

while (1)
{
  pkt = readPkt();
  pktID = getPktIdOfPkt(pkt);

  if ( aSpecialPkt(pktID) )
    doSomething();
}

现在，aSpecialPkt(pktId) 定义为：

bool PktProcessor::aSpecialPkt(unsigned short pid)
{
  return pktPidSet.find(pid) != pktPidSet.end();
}

gprof 报告在 std::set::find()

中花费了大量时间

pktId 的范围只有 8192 个可能的值。分配线性数组会更快，但会占用内存，例如：

class LinearSet
{
public:
  void insert(pid) { mPktIdSet[pid] = true; }
  bool elementExists(pid)  { return mPktIdSet[pid]; }
private:
  bool mPktIdSet[8192];
}

我的问题是，是否有更多 "C++" 方法可以在保持最佳性能的同时做到这一点？

Answer 1

如果您知道恰好有 8192 种可能性，那么您最好的选择可能是 std::bitset<8192>，它将使用 1 KB 并且对缓存非常友好。

Answer 2

std::bitset<8192> 是一个不错的选择，但这实际上取决于您的平台以及特殊数据包 ID 的数量。看到这个问题：Choosing between set<int> vs. vector<bool> vs. vector<boolean_t> to use as a bitmap (bitset / bit array)

查找速度比 std::set

Faster lookup than std::set

c++

stdset