面向文件层级病毒特征搜索的C++高效搜索方案咨询

Great question—virus signature matching lives or dies by raw throughput, so refining your implementation for speed is totally smart. Your current bitset-based approach works, but it’s leaving a lot of performance on the table. Let’s walk through the most impactful optimizations you can implement:

1. Fix the I/O Bottleneck First #

File I/O is almost always the biggest slowdown here. Using ifstream with default small buffers forces frequent system calls, which are expensive. Here are better options:

• Memory-map the file with mmap: This lets you access the file directly as if it’s in RAM, eliminating the need to copy data into a buffer manually. The OS handles caching and reduces overhead automatically.

  #include <sys/mman.h>
  #include <fcntl.h>
  #include <unistd.h>
  
  int fd = open("target_file", O_RDONLY);
  off_t file_size = lseek(fd, 0, SEEK_END);
  uint8_t* file_data = static_cast<uint8_t*>(mmap(nullptr, file_size, PROT_READ, MAP_PRIVATE, fd, 0));
  
  // Scan file_data directly like a byte array
  // Don't forget to clean up: munmap(file_data, file_size); close(fd);
  

• Tune ifstream buffers if you stick with it: Increase the buffer size and disable C/stdio synchronization to cut overhead:

  std::ifstream file("target_file", std::ios::binary);
  char buffer[65536]; // 64KB buffer (adjust based on your system's page size)
  file.rdbuf()->pubsetbuf(buffer, sizeof(buffer));
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr); // Unlink cin from cout to avoid unnecessary flushes
  

2. Replace Bitset Matching with Efficient Pattern Algorithms #

std::bitset adds unnecessary overhead for byte-based signature matching (most virus signatures are byte sequences, not arbitrary bit patterns). Swap to algorithms built for fast pattern scanning:

• Boyer-Moore Algorithm: Perfect for single signatures. It preprocesses the signature to create skip tables, letting you jump large chunks of the file when a mismatch occurs (instead of checking every byte). It’s especially fast for longer signatures.
• Aho-Corasick Algorithm: If you’re scanning for multiple signatures at once, this builds a trie of all signatures and scans the file in a single pass. Ideal for bulk signature databases.
• SIMD-Accelerated Matching: Use SSE/AVX instructions to compare 16-32 bytes at once. For example, with AVX2:

  #include <immintrin.h>
  
  bool simd_compare(const uint8_t* file_ptr, const uint8_t* signature, size_t sig_len) {
      size_t i = 0;
      // Compare 32 bytes at a time until near the end of the signature
      for (; i <= sig_len - 32; i += 32) {
          __m256i file_chunk = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(file_ptr + i));
          __m256i sig_chunk = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(signature + i));
          __m256i eq = _mm256_cmpeq_epi8(file_chunk, sig_chunk);
          if (_mm256_movemask_epi8(eq) != 0xFFFFFFFF) { // Mismatch found
              return false;
          }
      }
      // Compare remaining bytes one by one
      for (; i < sig_len; ++i) {
          if (file_ptr[i] != signature[i]) return false;
      }
      return true;
  }
  

3. Preprocess and Filter to Reduce Unnecessary Checks #

Avoid full signature comparisons whenever possible:

• Hash Pre-Screening: Compute a rolling hash (like CRC32, MurmurHash, or xxHash) of each window in the file. Only run a full signature comparison if the window’s hash matches the signature’s precomputed hash. This filters out most mismatches in microseconds.
• Group Signatures by Length: Sort your signatures by their byte length, and scan for longer signatures first. Longer matches are less likely to be false positives, and you can skip smaller windows once a longer match is found.

4. Parallelize the Work #

If you’re scanning multiple files (or a single huge file), split the load across threads:

• Multi-File Scanning: Use a thread pool to assign each file to a separate thread. Just make sure to avoid shared resource contention (e.g., use a mutex if writing to a shared log file).
• Single Large File Scanning: Split the file into chunks, and scan each chunk in parallel. Be careful to handle signatures that span chunk boundaries—overlap chunks by the length of your longest signature to avoid missing matches.

Final Notes #

The fastest combination will depend on your use case, but a solid baseline is:

1. Use mmap for file access
2. Implement Boyer-Moore (or Aho-Corasick for multiple signatures)
3. Add SIMD acceleration for byte comparisons
4. Throw in hash pre-screening to cut down on full matches

This stack will blow your current bitset-based approach out of the water in terms of speed.

内容的提问来源于stack exchange，提问作者LetuceLizard