Re: Lock Free Algorithms

["D Burgess" <dburgess@...>]

Thanks for the response MIke. I dont think I will be writing
a thesis.
However,  observations :
1)  the "lock free" reviews make a clear statement about the
problems with OS thread implementations.
2) a set of ANSI C basic "lock free" containers lists, queues (LIFO, FIFO)
would be a perfect world.

David B.

On 2/28/06, Mike Pall <mikelu-0602@mike.de> wrote:
> Hi,
>
> D Burgess wrote:
> > Is something like this applicable for Lua locks? i.e. multiple
> > OS threads and Lua VMs?
>
> Maybe. But not by replacing lua_lock/lua_unlock. You need to
> change all of the underlying algorithms in the Lua core which
> operate on shared structures. The two biggest problems are the
> hash tables and the garbage collector.
>
> I'm not sure there is a lock free variant of Brent's variation to
> chained hashing. But this is essential for Lua's performance.
>
> There has been a lot of research on lock-free garbage collection.
> The main work is integrating such an algorithm into the Lua core.
> It's also a minefield of patents ...
>
> Pros:
> + It would be very fast and you could run multiple Lua threads at
>   full speed (unlike the current lua_lock/lua_unlock scheme).
> + It could benefit from the current move to multi-core CPUs.
>
> Cons:
> - You need high-level synchronization primitives in your Lua code
>   to protect shared resources. You may end up in mutex hell.
> - You still need machine-specific primitives (compare-and-swap
>   and memory barriers). It's not very portable.
> - Many details need to be resolved. There may be a yet unknown
>   dead-end.
> - This is a larger undertaking.
>
> Personally I have no plans to research this any further. But it
> would make an interesting topic for a thesis (hint, hint).
>
> Bye,
>      Mike
>