关于一个LinkedList百万级别插入性能优化

loujian1989 发表于 2022-8-6 18:59
不用搞这些概念的游戏， 重点是明白别人问你这个问题的实质，就是大量同时写入冲突的问题，怎么样优化你 ...

在单线程情况下问题的实质就是内存管理和cache miss，多线程才需要考虑冲突的问题，而且unrolled list就是同时解决两个问题的答案

techDiscussion 发表于 2022-8-7 01:16
如何优化锁呢?

不用锁，你都用linked list了肯定是奔着lock free去的，没有delete的话保证每个chunk的counter是个atomic的就行

一个node维持milllions 级别的insert不合理吧，如果是分布式的话，就要注意每个node的balanace，防止hotspot。可以结合free memory + random algorithm 设计算法。另外没有要求的话直接插入每个block的末尾就可

techDiscussion 发表于 2022-8-6 22:16
如何优化锁呢?

是pure storage的那个面经题吗？

关于 linked list：
如果每个进程插入/删除的位置都不一样的话，可以考虑 lock-free 的算法，去掉全局锁。这样所有进程都能并行地插入。原理大概就是通过原子操作把锁和数据结合到了一起，甚至不需要给锁分配额外的储存空间。
http://15418.courses.cs.cmu.edu/spring2013/article/46
如果每个进程都要在同一个位置插入/删除（比如都是在头部/尾部），那我觉得该考虑换个数据结构了，比如 deque。
关于 deque：
虽然也有 lock-free 算法，但是即使 lock-free 也会有竞争。
https://arxiv.org/pdf/cs/0408016.pdf

如果顺序不重要的话，可以让每个进程先把自己的数据积攒起来打包成一个大数组，数组满了或者等待一定时间以后把整个数组的指针放进 deque。这样可以减少 deque 的插入/删除的次数，对缓存也比较友好。既然都并行插入了，那么进程之间交错的顺序本来就是没保障的，所以我觉得“顺序不重要”是一个合理的假设。

yuhta 发表于 2022-8-7 09:27
在单线程情况下问题的实质就是内存管理和cache miss，多线程才需要考虑冲突的问题，而且unrolled list就 ...

如果你单线程插入的话，是不是就有性能问题？ 如果每次插入需要50ms， 1 million 插入就需要 500 00秒 = 833 minutes = 13.88 hours。

是不是需要优化？ 如果是100个无冲突的线程同时插入，是不是就可以时间减少到500秒=8.3 minutes

关键是分析问题，其次再去考虑用什么数据结构， 你有没有认真的读一下unrolled linked list 实现的源码，他能帮助你多线程插入吗？

yuhta 发表于 2022-8-7 09:40
不用锁，你都用linked list了肯定是奔着lock free去的，没有delete的话保证每个chunk的counter是个atomic ...

如果多线程插入，是不是要抢同一个插入的index， 如果同时抢到了index，是不是会产生数据覆盖？   如果是单线程插入，是不是就有性能问题？

loujian1989 发表于 2022-8-7 18:24
如果你单线程插入的话，是不是就有性能问题？ 如果每次插入需要50ms， 1 million 插入就需要 500 00秒 =  ...

一般的linked list插入是在几纳秒到几十纳秒级别（不考虑memory allocation，假设没有cache miss），1 million插入在10ms这个数量级，考虑多线程更多是为了concurrency而不是性能优化。如果是普通的linked list只需要一个小改动就可以做成lock free的，只是对缓存不友好（还有遍历的时候有data dependency）。unroll的话就是我前面说的，只在每个chunk最后插入，需要把counter做成atomic的。

另外一般的linked list不会用index来access的，都是keep一个到node的指针。

yuhta 发表于 2022-8-7 18:02
一般的linked list插入是在几纳秒到几十纳秒级别（不考虑memory allocation，假设没有cache miss），1 mi ...

如果你在内存插入确实是纳秒级别， 但是如果你写到硬盘上就是毫秒级别， 这个需要跟面试官讨论，写在内存上就返回的话，有数据丢失的风险。 你在chunk后面不停的append的话，如果是单线程不需要担心锁的问题，如果是多线程的话，直接append就会有数据覆盖的风险，你count 是atomic的也没用，因为你是两步操作，先是插入数据，然后更新count