Re: Lock Free Algorithms

[Mike Pall <mikelu-0602@...>]

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