nDPI icon indicating copy to clipboard operation
nDPI copied to clipboard

[Enhancement] Improve performance for bitmask operation

Open pengtianabc opened this issue 4 years ago • 1 comments

Hi, i found some point about performacne, take a look at:

// ndpi_main.c:6378
int NDPI_BITMASK_COMPARE(NDPI_PROTOCOL_BITMASK a, NDPI_PROTOCOL_BITMASK b) {
  int i;

  for (i = 0; i < NDPI_NUM_FDS_BITS; i++) {
    if(a.fds_bits[i] & b.fds_bits[i])
      return(1);
  }

  return(0);
}

If we increace NDPI_NUM_BITS , then the NDPI_NUM_FDS_BITS will increase also, ndpi has about 200+ protocols now, so the last half bitmask(consume it's 256) is always empty, this part will watse about 4 cycles in every call (256/NDPI_BITS(32bit)=4 ). it will be more worse if we set NDPI_NUM_BITS to a large value like 4096 or larger.

If the description is correct, could we imporve it, i have some idea:

  1. declare a current_max_fds_bits instead of NDPI_NUM_FDS_BITS to reduce the unuseful call (this will import a global vairable or parameter)
  2. use another efficient bitmask like RoaringBitmap to implemention this part (I don't know if it's worth it)
  3. use a more width bitmask unit(like int64_t or SSE/AVX operation) to reduce the compare count ( int64_t is easy, but SSE/AVX is not platform friendly, we must add some code for spefial architecture)

pengtianabc avatar Dec 23 '20 09:12 pengtianabc

RoaringBitmap is part of nDPI since 1efabef4cfce64a373f014ee43bab371a82f7e87. 2. seems worth a try.

utoni avatar Oct 06 '21 13:10 utoni