Faster lookup than std::set

Question

I need a faster membership lookup for some legacy packet processing code which needs to identify if a packet with a particular ID is in a particular list.

The list is only updated every few seconds while the packet matching happens very very often, so lookup performance is more important than insertion/deletion etc.

General Flow:

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

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

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

And right now, aSpecialPkt(pktId) is defined as:

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

gprof reports a lot of time spent in the std::set::find()

The range of pktId is only 8192 possible values. Allocate a linear array would be much faster at the expense of memory, something like:

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

My question is whether there is a more "C++" way of doing this while maintaining top performance?

Answer 1

If you know that there are precisely 8192 possibilities, your best bet is probably std::bitset<8192>, which will use a kilobyte and is very cache-friendly.