FindTheLargestNumIn10GBFile

在十亿个数中找到最大的一个数字

标准库IO读取，遍历，单线程

int main()
{
    std::ifstream ifs;
    ifs.open("bigdata.txt", std::ios::in);


    int max_num = INT32_MIN;
    int x;
    BENCHMARK::BENCHMARK_BEGIN();
    while(ifs >> x) {
        if(x > max_num) {
            max_num = x;
        }
    }
    BENCHMARK::BENCHMARK_END();
    BENCHMARK::OUTPUT_DURATION();
    std::cout << "max num: " << max_num << std::endl;
    return 0;
}

测试结果：

35950.3ms
max num: 2147483646

mmap读取， 遍历，单线程

第一种方法每一次读取数据时都有一次系统调用，进入内核态拷贝数据到用户缓存中，我们可以用mmap将物理文件直接映射到
内存中，这样后面访问文件中的数据就类似于访问内存一样，没有额外的开销。
此外，ifs >> x 会有一些固定的开销，比如检查字符，跳过字符，异常处理，当然我们手动解析也有一定的开销，但是相对比
标准库来说肯定没有那么全面，所以消耗少一些。

int main() 
{
    int fd = open("bigdata.txt", O_RDONLY);
    if(fd == -1) {
        std::cout << "open file failed.\n";
        return 0;
    }

    struct stat st{};
    if(0 != fstat(fd, &st)) {
        std::cout << "get file attribute failed.\n";
        return 0;
    }

    size_t len = st.st_size;
    const char* data = (const char*)mmap(nullptr, len, PROT_READ, MAP_PRIVATE, fd, 0);
    if(data == MAP_FAILED) {
        std::cout << "mmap failed.\n";
        close(fd);
        return 0;
    }
    close(fd);

    std::cout << "file len: " << len << '\n';
    const char* p = data;
    const char* end = data + len;
    int max_num =INT32_MIN;
    BENCHMARK::BENCHMARK_BEGIN();
    int cnt = 0;
    while(true) {
        while(p < end && std::isspace(*p)) {
            ++p;
        }
        if(p > end) break;
        
        int num{0};
        while(p < end && std::isdigit(*p)) {
            num = num *10 + (*p - '0');
            ++p;
        }
        cnt ++;
        ++p;
        max_num = std::max(max_num, num);
    }


    BENCHMARK::BENCHMARK_END();
    BENCHMARK::OUTPUT_DURATION();
    munmap((void*)data, len);
    std::cout << "max num: " << max_num << ", cnt: " << cnt <<'\n';
    return 0;
}

测试结果：

file len: 10482569725
20034.6ms
max num: 2147483646

可以开出，速度快出了很多，但是很容易想到，这没有利用到多线程的威力，我们的计算是没有依赖的，局部最大最后可以归并计算出全局最大。

mmap读取， 分片，多线程

如果我们的机器是多核的，就可以发挥多线程并行计算的功力，由于只是求最大值，所以我们可以采用分片的策略。
按照机器的核心数分成多片，每个线程计算每个分片中最大的值，然后最后所有线程汇集后，再计算最大的值。
需要注意的是，我们的一个分片可能正好在一个数字中间，所以我们要处理一下边界情况：

对于一个分片[start, end]:
如果start在数字位，向前移动到第一个非数字位

如果end在数字位，向前移动到第一个非数字位

这样就能覆盖全所有的数字，代码如下

struct Chunk {
    size_t start;
    size_t end;
};

void parse_chunck(const char* data, size_t start, size_t end, int& local_max) {
    const char* p = data+start;
    const char* ed = data + end;
    local_max =INT32_MIN;

    while(true) {
        while(p < ed && std::isspace(*p)) {
            ++p;
        }
        if(p > ed) break;
        
        int num{0};
        while(p < ed && std::isdigit(*p)) {
            num = num *10 + (*p - '0');
            ++p;
        }
        ++p;
        local_max = std::max(local_max, num);
    }
}

int main() 
{
    int fd = open("bigdata.txt", O_RDONLY);
    if(fd == -1) {
        std::cout << "open file failed.\n";
        return 0;
    }

    struct stat st{};
    if(0 != fstat(fd, &st)) {
        std::cout << "get file attribute failed.\n";
        return 0;
    }

    size_t len = st.st_size;
    const char* data = (const char*)mmap(nullptr, len, PROT_READ, MAP_PRIVATE, fd, 0);
    if(data == MAP_FAILED) {
        std::cout << "mmap failed.\n";
        close(fd);
        return 0;
    }
    close(fd);

    std::cout << "file len: " << len << '\n';

    int threads = std::thread::hardware_concurrency();
    std::vector<Chunk> chunks(threads);
    size_t pos = 0, base = len / threads, left = len % threads;
    for(int i = 0; i < threads; ++i) {
        int block = base + (i < int(left) ? 1 : 0);
        chunks[i].start = pos;
        chunks[i].end = pos + block;
        pos += block;
    }


    for(int i = 0; i < threads; ++i) {
        auto& c = chunks[i];

        if(c.start > 0) {
            size_t b = c.start;
            while(b > 0 && std::isdigit(data[b])) --b;
            c.start = b;
        }

        if(c.end < len) {
            size_t e = c.end;
            while(e > 0 && std::isdigit(data[e])) --e;
            c.end = e;
        }
    }

    size_t total_b{0};
    for(const auto& item : chunks) {
        std::cout << item.start << " " << item.end << '\n';
        std::cout << *(data + item.start) << "  " << *(data + item.end) << '\n';
        total_b += (item.end - item.start + 1);
    }
    std::cout << "total bytes: " << total_b << '\n';
    std::vector<std::thread> pool;
    std::vector<int> local_maxs(threads, 0);
    BENCHMARK::BENCHMARK_BEGIN();
    for(int i = 0; i<threads; ++i) {
        pool.emplace_back([data, chunks, i, &local_maxs]{
            if(chunks[i].start < chunks[i].end) {
                parse_chunck(data, chunks[i].start, chunks[i].end, local_maxs[i]);
            }
        });
    }
    for(auto &t : pool) {
        t.join();
    }
    BENCHMARK::BENCHMARK_END();
    
    int g_max = INT32_MIN;
    for(int i : local_maxs) {
        g_max = std::max(g_max, i);
    }
    BENCHMARK::OUTPUT_DURATION();
    std::cout << "max num: " << g_max <<'\n';
    munmap((void*)data, len);
    return 0;
}

测试结果：

total bytes: 10482569745
12529.6ms
max num: 2147483646