b*******s
发帖数: 5216 | |
W***o
发帖数: 6519 | 2 这帖子太长了，粗看了一下。还是通过提问讨论学习一下吧。
有几个问题：
1. 如果几个processes要access shared data structure, 怎么避免race ?
2. 一个 process 对 common data structure 操作结束，怎么通知下一个 process? 按
照什么顺序？
3. 最后一个 process 处理完 common data structure, 怎么告诉其他 processes to
move
on ?
【在 b*******s 的大作中提到】
: http://kukuruku.co/hub/cpp/lock-free-data-structures-the-inside
|
t****t
发帖数: 6806 | 3 1. usually lock-free structures use atomic operations and (possibly) retry t
o guarantee race-free conditions without lock. how? read the article. are yo
u waiting others to spoon feed you...?
2. there is no lock so there is no notification. while one thread gain acces
s, the others just keep retrying.
3. since it's the last process, usually the other process already move on. i
guess you are thinking about barrier...
按
to
【在 W***o 的大作中提到】
: 这帖子太长了，粗看了一下。还是通过提问讨论学习一下吧。
: 有几个问题：
: 1. 如果几个processes要access shared data structure, 怎么避免race ?
: 2. 一个 process 对 common data structure 操作结束，怎么通知下一个 process? 按
: 照什么顺序？
: 3. 最后一个 process 处理完 common data structure, 怎么告诉其他 processes to
: move
: on ?
|
t****t
发帖数: 6806 | 4 你还不如看看c++ concurrency in action那本书. 写得不错.
【在 b*******s 的大作中提到】
: http://kukuruku.co/hub/cpp/lock-free-data-structures-the-inside
|
W***o
发帖数: 6519 | 5 谢谢，你说的第二点有点像busy waiting/spinning; 如果是一个分布式系统，这样快
有很高的 network communication overhead 吧
今天晚上没心情静下心来读，明天白天有空再详细读一下；
PS，如果这个idea很有创新，原作者应该会投给期刊发表出来了吧？呵呵
t
yo
acces
i
【在 t****t 的大作中提到】
: 1. usually lock-free structures use atomic operations and (possibly) retry t
: o guarantee race-free conditions without lock. how? read the article. are yo
: u waiting others to spoon feed you...?
: 2. there is no lock so there is no notification. while one thread gain acces
: s, the others just keep retrying.
: 3. since it's the last process, usually the other process already move on. i
: guess you are thinking about barrier...
:
: 按
: to
|
t****t
发帖数: 6806 | 6 yes, busy waiting is essential for lock-free structures. no one says busy wa
iting should be used everywhere though.
and of course the idea is not new. in fact, every lock is internally impleme
nted with some kind of lock-free structures, using atomic operations. ultima
tely hardware guarantees an operation is atomic.
【在 W***o 的大作中提到】
: 谢谢，你说的第二点有点像busy waiting/spinning; 如果是一个分布式系统，这样快
: 有很高的 network communication overhead 吧
: 今天晚上没心情静下心来读，明天白天有空再详细读一下；
: PS，如果这个idea很有创新，原作者应该会投给期刊发表出来了吧？呵呵
:
: t
: yo
: acces
: i
|
g*********e
发帖数: 14401 | |
b*******s
发帖数: 5216 | 8 多谢，看过了
【在 t****t 的大作中提到】
: 你还不如看看c++ concurrency in action那本书. 写得不错.
|
w***g
发帖数: 5958 | 9 这种东西学术界折腾有几年了。Lock在性能上其实没那么不济。Lock free主要还是为
了程序写起来方便，性能上可能还不如lock。
【在 b*******s 的大作中提到】
: http://kukuruku.co/hub/cpp/lock-free-data-structures-the-inside
|
t****t
发帖数: 6806 | 10 程序写起来都一样, lock free和locked不能互相替代, 是两个不同情况用的东西.
【在 w***g 的大作中提到】
: 这种东西学术界折腾有几年了。Lock在性能上其实没那么不济。Lock free主要还是为
: 了程序写起来方便，性能上可能还不如lock。
|
|
|
b****s
发帖数: 872 | 11 写起来不一样。
如果共享的就是个计数器，不用lock free，还用lock就太傻了。可惜大部分人根本不
知道lock free，一个计数器还在用lock
【在 t****t 的大作中提到】
: 程序写起来都一样, lock free和locked不能互相替代, 是两个不同情况用的东西.
|
t****t
发帖数: 6806 | 12 计数器这种trivial的情况不谈, 大多数lock-free的结构如果不用跟锁看起来一样的
spin, 那写起来肯定比带锁的麻烦. 我说的一样是指几个可能的操作都是预先设计好,
写一次就搞定的意思.
【在 b****s 的大作中提到】
: 写起来不一样。
: 如果共享的就是个计数器，不用lock free，还用lock就太傻了。可惜大部分人根本不
: 知道lock free，一个计数器还在用lock
|
b****s
发帖数: 872 | 13 为了追求高性能，麻烦还是有必要的。
程序拿不到锁，会进入睡眠状态，导致context switch，这个开销很大。用lock-free
就灵活多了
,
【在 t****t 的大作中提到】
: 计数器这种trivial的情况不谈, 大多数lock-free的结构如果不用跟锁看起来一样的
: spin, 那写起来肯定比带锁的麻烦. 我说的一样是指几个可能的操作都是预先设计好,
: 写一次就搞定的意思.
|
b*******s
发帖数: 5216 | 14 不是新点子，很多人实现过
【在 W***o 的大作中提到】
: 谢谢，你说的第二点有点像busy waiting/spinning; 如果是一个分布式系统，这样快
: 有很高的 network communication overhead 吧
: 今天晚上没心情静下心来读，明天白天有空再详细读一下；
: PS，如果这个idea很有创新，原作者应该会投给期刊发表出来了吧？呵呵
:
: t
: yo
: acces
: i
|
b*******s
发帖数: 5216 | 15 看情况，单个任务很短暂，但任务切换很频繁数量很大的情况，lock-free不错
【在 w***g 的大作中提到】
: 这种东西学术界折腾有几年了。Lock在性能上其实没那么不济。Lock free主要还是为
: 了程序写起来方便，性能上可能还不如lock。
|
b*******s
发帖数: 5216 | 16 很多都是，比如quickfix engine就是
新的c++类库都自带atomic_flag这种test n set的spin lock
【在 b****s 的大作中提到】
: 写起来不一样。
: 如果共享的就是个计数器，不用lock free，还用lock就太傻了。可惜大部分人根本不
: 知道lock free，一个计数器还在用lock
|
n******t
发帖数: 4406 | 17 lock-free 和高性能没有任何必然联系。觉得性能不好改用lock-free这是很多人的误
区。
free
【在 b****s 的大作中提到】
: 为了追求高性能，麻烦还是有必要的。
: 程序拿不到锁，会进入睡眠状态，导致context switch，这个开销很大。用lock-free
: 就灵活多了
:
: ,
|
F****n
发帖数: 3271 | 18 lock-free reduces the chance of human-caused performance problem
【在 n******t 的大作中提到】
: lock-free 和高性能没有任何必然联系。觉得性能不好改用lock-free这是很多人的误
: 区。
:
: free
|
b****s
发帖数: 872 | 19 简单的性能例子，一个共享计数器更新，两个线程同时访问更新，数据更新不能冲突。
在1分钟之内，是用lock free更新的总次数多，还是用lock更新的总次数多。
【在 n******t 的大作中提到】
: lock-free 和高性能没有任何必然联系。觉得性能不好改用lock-free这是很多人的误
: 区。
:
: free
|
b*******s
发帖数: 5216 | 20 这个例子是有偏颇的，比如你有个线程忙得很，要很长时间才clear spin lock，这时
lock free就可能降低效率，因为所有在等的线程都在瞎忙，如果数量一大，就开销很
大了
【在 b****s 的大作中提到】
: 简单的性能例子，一个共享计数器更新，两个线程同时访问更新，数据更新不能冲突。
: 在1分钟之内，是用lock free更新的总次数多，还是用lock更新的总次数多。
|
|
|
b****s
发帖数: 872 | 21 所以看使用场合，lock free还是很有用的。传统的锁，拿不到会导致线程睡眠。
如果有1000个线程，同时有一个紧俏资源，大家都要用，但你不希望线程睡眠在这个锁
上，导致大量上下文切换，lock free就有用了。
【在 b*******s 的大作中提到】
: 这个例子是有偏颇的，比如你有个线程忙得很，要很长时间才clear spin lock，这时
: lock free就可能降低效率，因为所有在等的线程都在瞎忙，如果数量一大，就开销很
: 大了
|
s********k
发帖数: 6180 | 22 看在什么平台上面吧，你说的这种在mobile上最优选择吧，不停地spin lock的话反而
功耗上没法承受
free
【在 b****s 的大作中提到】
: 为了追求高性能，麻烦还是有必要的。
: 程序拿不到锁，会进入睡眠状态，导致context switch，这个开销很大。用lock-free
: 就灵活多了
:
: ,
|
b****s
发帖数: 872 | 23 spin lock可以很快的，要看场合。
假设一个FIFO的queue的场合，一个线程读queue头内容，然后立刻释放锁，1000个线程
添加内容到queue尾，每个线程加入queue尾内容，然后立刻释放锁。queue的读和写操
作速度很快，一个线程就算一下抢不到，只要等一小会就能抢到。
但如果出现冲突，用传统锁，导致的线程切换，开销肯定大约spin lock
【在 s********k 的大作中提到】
: 看在什么平台上面吧，你说的这种在mobile上最优选择吧，不停地spin lock的话反而
: 功耗上没法承受
:
: free
|
n******t
发帖数: 4406 | 24 实际程序几乎没你这么写的。。。
没事共享计数器干什么？？？
【在 b****s 的大作中提到】
: 简单的性能例子，一个共享计数器更新，两个线程同时访问更新，数据更新不能冲突。
: 在1分钟之内，是用lock free更新的总次数多，还是用lock更新的总次数多。
|
p*u
发帖数: 2454 | 25
lock-free queues are very important, esp multiple-producer-single-consumer
and single-producer-single-consumer queues...
【在 n******t 的大作中提到】
: 实际程序几乎没你这么写的。。。
: 没事共享计数器干什么？？？
|
b*******s
发帖数: 5216 | 26 1000个threads就算你用lock free，也一样可能会有context switch的
【在 b****s 的大作中提到】
: 所以看使用场合，lock free还是很有用的。传统的锁，拿不到会导致线程睡眠。
: 如果有1000个线程，同时有一个紧俏资源，大家都要用，但你不希望线程睡眠在这个锁
: 上，导致大量上下文切换，lock free就有用了。
|
k**********g
发帖数: 989 | 27 昏特。
本质上就是根据各任务的时间性，选择适当的保护方案。
Inefficiency = (average time per operation including lock overhead) divided
by (average time per operation excluding lock overhead) minus 1.0
The numerator is the actual performance. The divisor is the time spent "
doing useful stuff".
Ideally inefficiency = 0, i.e. zero overhead. In practice, make inefficiency
small.
Corollary: If the task takes longer time, it's okay to use lock with larger
overhead per-operation, because the inefficiency won't increase much.
nano-scale : lock-free, together with immutable/copyable types.
micro-scale : OS locks.
milli-scale : DB transactions
second-scale : need to show something to the user e.g. sandglass or spinning
beachball |
b*******s
发帖数: 5216 | 28 总结得不错
divided
inefficiency
larger
【在 k**********g 的大作中提到】
: 昏特。
: 本质上就是根据各任务的时间性，选择适当的保护方案。
: Inefficiency = (average time per operation including lock overhead) divided
: by (average time per operation excluding lock overhead) minus 1.0
: The numerator is the actual performance. The divisor is the time spent "
: doing useful stuff".
: Ideally inefficiency = 0, i.e. zero overhead. In practice, make inefficiency
: small.
: Corollary: If the task takes longer time, it's okay to use lock with larger
: overhead per-operation, because the inefficiency won't increase much.
|
n******t
发帖数: 4406 | 29 you apparently used very little MPSC queues in real life, at least in
performance critical settings.
One thing I think you probably do not know is, lock-free algos typically
make things slower, do you know why?
【在 p*u 的大作中提到】
:
: lock-free queues are very important, esp multiple-producer-single-consumer
: and single-producer-single-consumer queues...
|
c*****4
发帖数: 1777 | 30 晕死。打酱油地弱弱的问一句，搞清楚茴香豆的茴字有多少种写法真能赚到钱么？有多
少职务是要自己实现同步的。
【在 b*******s 的大作中提到】
: http://kukuruku.co/hub/cpp/lock-free-data-structures-the-inside
|
|
|
p*u
发帖数: 2454 | 31
yes, that's because ur co-workers or urself are incompetent.
【在 n******t 的大作中提到】
: you apparently used very little MPSC queues in real life, at least in
: performance critical settings.
: One thing I think you probably do not know is, lock-free algos typically
: make things slower, do you know why?
|
b*******s
发帖数: 5216 | 32 如果你用不到，忽略好了
【在 c*****4 的大作中提到】
: 晕死。打酱油地弱弱的问一句，搞清楚茴香豆的茴字有多少种写法真能赚到钱么？有多
: 少职务是要自己实现同步的。
|
n******t
发帖数: 4406 | 33 man, let's be techinical and say some real stuff. typing some shit like a
randominternet dude makes yourself a random internet dude.
【在 p*u 的大作中提到】
:
: yes, that's because ur co-workers or urself are incompetent.
|
w***w
发帖数: 84 | 34 1000个线程都不睡 那不得1000个core啊 这个lock free应该是在low contention，
short critical session 时有用吧 并且数据结构得够简单 update 得isolated. CAS
又是个hack 总之是费力不讨好 多年前听过 现在还有人做吗? |
j********x
发帖数: 2330 | 35 扯淡。。。
【在 n******t 的大作中提到】
: you apparently used very little MPSC queues in real life, at least in
: performance critical settings.
: One thing I think you probably do not know is, lock-free algos typically
: make things slower, do you know why?
|
j********x
发帖数: 2330 | 36 lock-free vs lock肯定是前者快，当然前提是不做大的架构变化。
【在 n******t 的大作中提到】
: you apparently used very little MPSC queues in real life, at least in
: performance critical settings.
: One thing I think you probably do not know is, lock-free algos typically
: make things slower, do you know why?
|
n******t
发帖数: 4406 | 37 同学你这么肯定，你家里人知道么？
还架构变化，一看就是连lock-free定义都没搞清楚的，更不要说做过"重大架构变化了
"。
【在 j********x 的大作中提到】
: lock-free vs lock肯定是前者快，当然前提是不做大的架构变化。
|
o*******0
发帖数: 699 | |
