Lock-free concurrent Lua?

For some time now I've been thinking about how to make Lua concurrent. That is, having several threads of execution, all in the same Lua space, sharing all data; but without the Big Language Lock that effectively sequentializes execution of most of the code.

Of course, the problem is that LuaThreads (the only Lua multithreading extension that puts all threads on the same space) uses just one lock per space, and all threads fight for this one resource.

One 'obvious' solution would be to use one lock per object. A little better might be to use readers/writers locks, to allow concurrent readings. yep, should work.

But a couple of days ago I saw this: Scalable Nonblocking Data Structures on Slashdot about a guy that got lock-free hashtables with great scalability on 700+ threads (with even more cores than threads!). The article was very simplistic, and seemingly inconsistent; but one /.er pointed to the Google Talk. Now that's inspiring!

I've previously read about lock-free algorithms and data structures, but this guy (that turned to be the Cliff Click)

So, after a couple of days of mulling about it, I'm hacking some code!

The original idea was to see if it's possible to lock-free'ize Lua tables. It's no easy task. The main stumbling block is that it seems that the CAS primitives available in gcc operate on pointer-sized values; since Lua tables store values directly in the hash table (and specially on the array part of the table), it's important to swap values atomically.

Much easier, and what I'm doing now, is to write new table code, lock-free from the start.

Of course, I'm using lots of naïve code in several parts, but hope to get the main ideas set, and clean silly things later (initialization right now looks very slow). Also, I still have no idea how to do the array part, and there are some unresolved issues on table resizing; but they all seem doable. And the code is coming surprisingly clean.

:-)