线程安全的已排序链表
我正在尝试编写一个线程安全的已排序单链表 。 我写了两个版本：粗粒度同步和细粒度同步。 以下是两个实现：
细粒度：
public void add(T t) { Node curr = head; curr.lock.lock(); while (curr.next != null) { // Invariant: curr is locked // Invariant: curr.data < t curr.next.lock.lock(); if (t.compareTo(curr.next.data) <= 0) { break; } Node tmp = curr.next; curr.lock.unlock(); curr = tmp; } // curr is acquired curr.next = new Node(curr.next, t); if (curr.next.next != null) { // old curr's next is acquired curr.next.next.lock.unlock(); } curr.lock.unlock(); } 粗粒度：
public void add(T t) { lock.lock(); Node curr = head; while (curr.next != null) { if (t.compareTo(curr.next.data) <= 0) { break; } curr = curr.next; } curr.next = new Node(curr.next, t); lock.unlock(); }
我将4个线程（在4个逻辑CPU核心上）的两个版本定时插入20000个整数。 每个线程的时间显示CPU时间（即它不包括等待时间）。
Fine grained: Worked 1 spent 1080 ms Worked 2 spent 1230 ms Worked 0 spent 1250 ms Worked 3 spent 1260 ms wall time: 1620 ms Coarse grained: Worked 1 spent 190 ms Worked 2 spent 270 ms Worked 3 spent 410 ms Worked 0 spent 280 ms wall time: 1298 ms
我最初的想法是.lock()和.unlock()是问题，但我分析了实现，他们一起只消耗了30％的时间。 我的第二个猜测是，细粒度的解决方案有更多的缓存未命中，但我怀疑它，因为单个链表与数组不同，本质上容易出现缓存未命中。
知道为什么我没有得到预期的并行化吗？
是的，这可能是由于缓存未命中。 包含锁的缓存行在CPU之间不断弹跳。
另外，请注意你已经获得了很多相似之处：
Fine grained: Worked 1 spent 1080 ms Worked 2 spent 1230 ms Worked 0 spent 1250 ms Worked 3 spent 1260 ms wall time: 1620 ms Coarse grained: Worked 1 spent 190 ms Worked 2 spent 270 ms Worked 3 spent 410 ms Worked 0 spent 280 ms wall time: 1298 ms
虽然每个单独的线程由于缓存未命中（以及增加的开销）而花费更多时间，但整个过程仅稍微慢一些。
您可以通过首先遍历没有锁的列表来获得接近每线程粗粒度版本的挂壁时间，以便找到间隙然后从当前，并且这次使用锁定，走遍列表以确保没有干预在当前和当前之间插入其他线程 – > next。 （当然我打折扣“头”总是至高无上的事实:)
除了ninjalj的答案 – 精美的锁也
- 禁用现有代码中的某些编译器优化
- 禁用一些CPU优化 – 比如预取
- 强制内存在锁定时获取语义，并在解锁时释放语义 – 导致跨CPU同步和无效缓存 – 这不会直接显示为分析器中的lock（）成本，但会增加跟踪数据访问的成本。
我错过了什么吗？ 我的代码中没有看到任何类型的缓存。 此外，您应该重新考虑使用锁定的方式。 您应该只锁定整个列表以限制锁定数量，并且还可以防止出现争用情况，如下所示。
thread1: Read Element X thread2: Removes X + 1 thread1: Read Element X + 1 and fails since the element is no long valid. thread1: Is unable to finish going through the list since it has been removed.
您可以对列表进行分区，但必须处理读取分区中最后一个元素并删除下一个分区中第一个元素的情况。
您还可以根据正在发生的操作类型（即，它是读取操作并且当前没有发生写入操作）仅使某些function需要锁定/解锁。
确实存在性能问题。 我认为你应该将性能与内置实现和单线程版本进行比较。
for (int r = 0; r < 5; r++) { long start = System.nanoTime(); ConcurrentLinkedQueue list = new ConcurrentLinkedQueue (); for (int i = 0; i < 500000; i++) list.add(i); long time = System.nanoTime() - start; System.out.printf("Adding 500K %,d took ms%n", time / 1000 / 1000); }
版画
Adding 500K 192 took ms Adding 500K 154 took ms Adding 500K 95 took ms Adding 500K 211 took ms Adding 500K 424 took ms