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

follow up是1个million的insertion的优化处理

我有一个Unrolled LinkedList 或者  就是普通的linkedList, 或者比如其他的数据结构like deque，要怎么去做优化如果有1百万的insertion处理？

感谢大家！！

（这个好像不是完全的系统设计，只是做代码的优化之类的。）

lz不是已经走上了unrolled list之路了么，我觉得这已经摸到一大大大半的答案了，

有人已经提到分布式情况下如何处理的，那就是系统设计问题。如果不是系统设计而是数据结构问题，私以为主要的目标就是防止内存碎片化和cache miss，例如，我们可以构造一个非常恶心的linkedlist，在两个距离很远的segment上交错存放数据，每次next都会触发cache miss。

假设有1M个double要插入，8M的内存大小，还不够服务器CPU的L3缓存吃的。所以如果预先知道insert很多，那就提前开巨页，甚至可以直接开静态巨页，这样就可以显著减少缓存miss了。

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

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

striges1111 发表于 2022-8-6 16:24
那这就是unrolled linked list啊……

不用搞这些概念的游戏， 重点是明白别人问你这个问题的实质，就是大量同时写入冲突的问题，怎么样优化你的锁机制。

好像算是系统设计。。分布式存储？设计一个好的方式来存储这 1m deque，同时还要考虑 reliability, consistency 这就变成系统设计题目了

阵雨 发表于 2022-8-6 15:42
好像算是系统设计。。分布式存储？设计一个好的方式来存储这 1m deque，同时还要考虑 reliability, consist ...

可以细节的描述一下，你要怎么确保数据的consistency呢?

insert具体应用场景是什么？直接加在后面也是insert，要求order也是insert

techDiscussion 发表于 2022-8-6 13:49
可以细节的描述一下，你要怎么确保数据的consistency呢?

比如用 1k 个 node，每个保存 1k 个 deque element，然后 每个 node 又有其他的 replica。。这就有 consistency 的考量了。。

这个应该是锁的问题，如果一百万个插入每次插入都锁整个list的话，那就是排队插入。。。所以如果你开100个线程同时插入的话，那你就划分成桶，桶1： 1-100， 桶2： 101-200.。。。 在每个桶里每个线程拿一个index 插入，这样就可以避免不同线程抢一个index的情况。。。

loujian1989 发表于 2022-8-6 18:13
这个应该是锁的问题，如果一百万个插入每次插入都锁整个list的话，那就是排队插入。。。所以如果你开100个 ...

那这就是unrolled linked list啊……

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

如何优化锁呢?