tag:blogger.com,1999:blog-29331675.post6517532501851329890..comments2024-03-05T17:37:00.995+01:00Comments on The Delphi Geek: Lock-free stack problemgabr42http://www.blogger.com/profile/06903558857617342477noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-29331675.post-3085884627233527292008-07-22T23:33:00.000+02:002008-07-22T23:33:00.000+02:00BTW, Wikipedia agrees with 'my' definition of lock...BTW, Wikipedia agrees with 'my' definition of <A HREF="http://en.wikipedia.org/wiki/Lock-free" REL="nofollow">lock-free</A>.<BR/><BR/>See also description of the <A HREF="http://en.wikipedia.org/wiki/ABA_problem" REL="nofollow">ABA problem</A> where a while loop is used in a 'lock-free' algorithm.gabr42https://www.blogger.com/profile/06903558857617342477noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-52943854250963084412008-07-22T17:02:00.000+02:002008-07-22T17:02:00.000+02:00Indeed, indeed. After all, chainHead^ is a record,...Indeed, indeed. After all, chainHead^ is a record, not a pointer.<BR/><BR/>Thanks for the catch, I've updated the main article.gabr42https://www.blogger.com/profile/06903558857617342477noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-44759349322632439932008-07-22T14:44:00.000+02:002008-07-22T14:44:00.000+02:00mov eax, [edx]is actuallyResult := chainHead;bec...mov eax, [edx]<BR/><BR/>is actually<BR/><BR/>Result := chainHead;<BR/><BR/>because it's a var parameterUnknownhttps://www.blogger.com/profile/14233636573671943454noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-11877337503191920312008-07-21T20:33:00.000+02:002008-07-21T20:33:00.000+02:00Why do I always think of one more statement just a...Why do I always think of one more statement just after I click the Publish button???<BR/><BR/>You could say that the lock-free approach is equivalent to a spinlock that locks only few instructions (pointer swapping) and which automatically releases the lock.gabr42https://www.blogger.com/profile/06903558857617342477noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-45761671381601095382008-07-21T20:31:00.000+02:002008-07-21T20:31:00.000+02:00@olaf: We are using spinlocks in OTL, you know :)T...@olaf: We are using spinlocks in OTL, you know :)<BR/><BR/>There is a big difference between using spinlocked stack and lock-free stack.<BR/><BR/>In spinlock version, you do:<BR/>spinlock.Acquire;<BR/>stack.Push; //without spinning<BR/>spinlock.Release;<BR/><BR/>Spinning is used to acquire the lock.<BR/><BR/>In lock-free version (sorry, but that's how the term is used - as I've said before, this approach is lock-free but not stack-free), no acquire/release cycle is used. The code goes:<BR/><BR/>stack.Push; //with spinning if required<BR/><BR/>However, you are correct that the approach is similar and that the speed is on the same order of magnitude.gabr42https://www.blogger.com/profile/06903558857617342477noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-68923267021182902222008-07-21T20:10:00.000+02:002008-07-21T20:10:00.000+02:00The approach you describe above is basically simil...The approach you describe above is basically similar to how "Spin Locks" work. ("jnz @Spin" is where it, well, spins)<BR/><BR/>Spin Locks are much faster (actually /may be/ much faster) if used in situations where locks are held for *very short* times (as in your example). The advantage come from saved context switches - which outweighs the actual code execution time that needs synchronized (in examples like this one).<BR/><BR/>Spin locks may come at a cost though: If for some reason the code to be synchronized runs too long, the OS may decide to *force* a context switch, as the time slice is "used up". At that point spin locks start burning cpu cycles - so you have to very carefully here.<BR/><BR/>@GJ: Yes, the OmniThreadLibrary has a very good performance - but it's not lock free, but uses fast locks ;-)Olaf Monienhttps://www.blogger.com/profile/02628979334210981429noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-38155586479845696392008-07-21T19:24:00.000+02:002008-07-21T19:24:00.000+02:00@Xepol:This is typical 100% "lock free" method.The...@Xepol:<BR/>This is typical 100% "lock free" method.<BR/>There is no locking of the memory buffer. So all involved threads can read and write at any time to the some location in memory buffer. Of course the memory conflicts exist. If some thread interrupts the writing of another thread the write operation will be repeated! <BR/><BR/>If you still doubt then check the OmniThreadLibrary performance.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-29331675.post-12395833542242251302008-07-21T16:59:00.000+02:002008-07-21T16:59:00.000+02:00But yes, you could call the traditional approach '...But yes, you could call the traditional approach 'pesimistic locking' and lock-free approach 'optimistic locking', if you wish.gabr42https://www.blogger.com/profile/06903558857617342477noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-32614486825594623622008-07-21T16:58:00.000+02:002008-07-21T16:58:00.000+02:00Depends on how you look at it.It is lock-free. It ...Depends on how you look at it.<BR/><BR/>It is lock-free. It doesn't acquire a lock and it doesn't require centralized service that manages locks (yep, locking can be decentralized, I know).<BR/><BR/>It aint wait-free. It would be nice to have a lock-free wait-free structure but I don't think that's achievable on the Intel32 architecture.gabr42https://www.blogger.com/profile/06903558857617342477noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-8530582473980945802008-07-21T16:46:00.000+02:002008-07-21T16:46:00.000+02:00I wish people would stop calling code "lock free" ...I wish people would stop calling code "lock free" - it just isn't so.<BR/><BR/>This code is just uses much lighter locking that a mutex or critical section allows when done correctly, but using a flag like this makes the flag the lock.<BR/><BR/>Sorry, this bit of angst and annoyance was brought to you by the letters x and y and the number 3.Xepolhttps://www.blogger.com/profile/07501635065767343244noreply@blogger.comtag:blogger.com,1999:blog-29331675.post-58200539789731971122008-07-21T15:40:00.000+02:002008-07-21T15:40:00.000+02:00I not only appreciate the library itself but I'm r...I not only appreciate the library itself but I'm really enjoying your writing about it here -- i hope you'll keep doing it.Anonymousnoreply@blogger.com