C语言下大文件中int64_t暴力查找的优化方案咨询

Hey there! Brute-forcing through a 60GB file byte by byte is definitely going to be slow—disk IO is one of the biggest bottlenecks here, so we need to optimize around that. Let's walk through practical, efficient approaches tailored for your use case:

1. Memory-Map the File with mmap() #

Memory mapping lets you treat the entire file as a contiguous block of memory in your process address space, eliminating the need for repeated read() system calls and buffer copying. This is a game-changer for large files because it leverages the OS's page cache efficiently.

Here's a quick snippet to get you started:

#include <stdio.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdint.h>

int main(int argc, char *argv[]) {
    int fd = open(argv[1], O_RDONLY);
    if (fd == -1) { perror("open"); return 1; }

    struct stat sb;
    if (fstat(fd, &sb) == -1) { perror("fstat"); close(fd); return 1; }

    // Map the entire file (requires 64-bit system for 60GB)
    uint64_t file_size = sb.st_size;
    int64_t *file_data = mmap(NULL, file_size, PROT_READ, MAP_PRIVATE, fd, 0);
    if (file_data == MAP_FAILED) { perror("mmap"); close(fd); return 1; }

    // Search logic: iterate through each int64_t (note alignment!)
    uint64_t num_elements = file_size / sizeof(int64_t);
    int64_t target = YOUR_TARGET_VALUE;
    for (uint64_t i = 0; i < num_elements; i++) {
        if (file_data[i] == target) {
            printf("Found at offset %lu bytes\n", i * sizeof(int64_t));
            // Collect results as needed
        }
    }

    munmap(file_data, file_size);
    close(fd);
    return 0;
}

Note: You must use a 64-bit system—32-bit processes can't address enough memory for a 60GB mapping.

2. Parallelize the Search #

Split the file into chunks and use multiple threads/processes to search each chunk simultaneously. This takes advantage of multi-core CPUs to speed things up.

• For threads: Use pthread to spawn worker threads, each assigned a range of the file (e.g., thread 0 handles 0-15GB, thread 1 handles 15-30GB, etc.). Use a mutex to safely collect results from threads.
• For processes: Use fork() or posix_spawn, but threads are lighter weight for this task.

Just make sure each chunk starts at an int64_t boundary (multiple of 8 bytes) to avoid partial values at chunk edges.

3. Pre-Build an Index (For Repeated Searches) #

If you need to search the same file multiple times, build an index once and reuse it:

• Traverse the file once, recording the file offset of every int64_t value.
• Store this in a hash table (e.g., a custom implementation or using a library like glib's GHashTable) where the key is the int64_t value and the value is a list of offsets.
• Subsequent searches just look up the hash table instead of scanning the entire file.

This adds upfront overhead (one full file scan), but pays off massively for repeated queries.

4. Optimize Block IO (If Memory Mapping Isn't Feasible) #

If you can't map the entire file (e.g., limited RAM), use large, aligned buffers to read chunks of the file at once. For example:

#define BUFFER_SIZE (64 * 1024) // 64KB buffer, adjust based on your system
int64_t buffer[BUFFER_SIZE / sizeof(int64_t)];

ssize_t bytes_read;
off_t current_offset = 0;
while ((bytes_read = read(fd, buffer, sizeof(buffer))) > 0) {
    uint64_t num_in_buf = bytes_read / sizeof(int64_t);
    for (uint64_t i = 0; i < num_in_buf; i++) {
        if (buffer[i] == target) {
            printf("Found at offset %lu bytes\n", current_offset + i * sizeof(int64_t));
        }
    }
    current_offset += bytes_read;
}

Larger buffers reduce the number of system calls, which are expensive compared to in-memory operations.

5. Leverage SIMD Instructions (Advanced) #

Modern CPUs support SIMD (Single Instruction, Multiple Data) which lets you compare multiple int64_t values at once. For example, with AVX-512, you can compare 8 int64_t values in a single instruction.

You can use compiler intrinsics (e.g., _mm512_cmpeq_epi64) to implement this, which can significantly speed up the per-chunk search.

Key Notes to Remember #

• Alignment: Always ensure you're reading int64_t values at 8-byte aligned addresses to avoid undefined behavior (most OSes will handle this for mmap, but double-check for manual reads).
• Error Handling: Don't skip checking return values for mmap(), read(), pthread_create(), etc.—large files can expose edge cases like insufficient memory or disk errors.
• SSD vs HDD: If you're using an HDD, prioritize sequential reads (avoid random access) since HDDs have high seek times. SSDs are more forgiving, but sequential still beats random.

Hope these tips help you get that search speed way up!

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