多线程解析.mtx文件的性能瓶颈排查与优化求助

一、解决有序链表插入慢的问题 #

• 批量攒边+排序去重后一次性处理
  既然文件里同一顶点的边是扎堆出现的，别边读边往缓冲区丢单条边。生产者线程可以先搞个临时缓存，按顶点ID分组存边——比如用个哈希表，键是顶点ID，值存该顶点的邻接边列表。等某个顶点的边攒到一定数量（比如1000条），或者连续好几行都没再出现这个顶点了，就把这个列表排序，然后扫一遍去掉重复的（有序列表里重复的肯定挨在一起），最后一次性把整组边塞到对应顶点的存储结构里。
  这种方式比单条边插入省太多事，不用每次都遍历链表找插入位置，批量排序去重的时间远低于几十上百次单条插入的总耗时。

• 把链表换成动态数组
  要是你需要的是有序+范围访问，动态数组（比如C++的std::vector）比链表好用一万倍：数组内存连续，缓存命中率高，范围访问直接用下标就行。批量排序后的边直接拷到数组末尾，后续有新边的话，同样攒一批排序去重后合并进去（两个有序数组合并是O(n)复杂度，比链表插入快多了）。

二、解决线程频繁阻塞的问题 #

• 按顶点分组分配任务
  别把所有边都塞到同一个环形缓冲区里。可以搞多个缓冲区，按顶点ID哈希取模分配，每个缓冲区对应一批不重叠的顶点。消费者线程各管各的缓冲区，这样同一顶点的边只会被一个线程处理，彻底避免多线程抢同一个锁的情况。
  嫌多缓冲区麻烦的话，生产者往缓冲区塞边前，先按顶点ID打乱顺序——比如给顶点ID做个哈希再排序，让缓冲区里的边尽量分散到不同顶点，减少线程抢锁的概率。

• 缩短锁的持有时间
  不管你用bitmap还是细粒度锁，能少锁就少锁，锁了就赶紧干完。比如批量处理同一顶点的边时，一次性把锁拿了，把所有边都处理完再释放，别插一条边锁一次、解一次。这样锁的竞争次数会大幅减少，阻塞时间也会短很多。

三、文件读取提速 #

• 用内存映射（mmap）读文件
  200MB的文件直接用mmap映射到进程内存里，直接在内存里解析数据，比传统的逐行读快太多——省了好多系统调用和磁盘IO等待的时间。解析的时候按块读，效率更高。

四、其他小优化 #

• 预先分配内存
  临时存边的容器（比如哈希表的value列表）提前预估好大小，分配足够的内存，别频繁扩容浪费时间。
• 压缩存储
  要是顶点ID是32位整数，直接用紧凑数组存，别用链表——链表每个节点的指针占额外内存，还影响缓存效率。

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