Developer forums (C::B DEVELOPMENT STRICTLY!) > CodeCompletion redesign

Interesting multithreading stuff that might be useful for code completion...

(1/2) > >>

rickg22:
Remember how we kept discussing and talking about using shared resources for the Code Completion plugin?

Well, take a look at this - I didn't know until today.

http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms


--- Quote ---The lock-free approach
Writing a program that uses lock-free data structures is not a simple matter of merely rewriting the algorithms you would normally protect with a mutex to be lock-free. Because lock-free algorithms are so difficult to write, researchers focus on writing lock-free versions of basic data structures such as stacks, queues, sets, and hash tables. These allow programs to easily exchange data between threads asynchronously.

--- End quote ---

And more recently...

http://en.wikipedia.org/wiki/Hazard_pointer


--- Quote ---In a multithreaded computing environment, a hazard pointer is an element used by a methodology that allows the memory allocated to the nodes of lock-free dynamic shared objects to be reclaimed. Using the methodology, each thread keeps a list of hazard pointers indicating which nodes the thread may later access. This list can only be written to by the particular thread but can be read by any thread. When a thread wishes to remove a node, it places it on a private list and periodically scans the lists of all other threads for pointers referencing that node. If no such pointers are found the memory occupied by the node can be safely freed.

--- End quote ---

thomas:
According to what Martin discovered from the wxGurus, these won't help us, though... as it's wxString that is unsafe.

Apart from that, I've read a lot about and implemented several lock-free algorithms, and while they're on several orders of magnitude faster in the right conditions, they likewise perform miserably in the wrong conditions. Also, they are by no means easier than locking schemes, or more resistant to failure. Contrarily, they bring a whole different set of problems, and errors can be hard to anticipate or detect.

In fact, lock-free algorithms are not even sufficiently understood by many who think that they can write articles about them, as you can see for example at Dr. Dobb's Journal.

rickg22:

--- Quote from: thomas on September 04, 2008, 09:20:33 am ---According to what Martin discovered from the wxGurus, these won't help us, though... as it's wxString that is unsafe.

--- End quote ---

I see...


--- Quote ---Apart from that, I've read a lot about and implemented several lock-free algorithms,

--- End quote ---

Cool! How did you manage to implement the CAS primitive? (msg me)


--- Quote ---Also, they are by no means easier than locking schemes, or more resistant to failure...
In fact, lock-free algorithms are not even sufficiently understood by many who think that they can write articles about them, as you can see for example at Dr. Dobb's Journal.

--- End quote ---

Heh. I see. Thanks for answering, then :)

thomas:

--- Quote from: rickg22 on September 05, 2008, 12:07:05 am ---Cool! How did you manage to implement the CAS primitive? (msg me)
--- End quote ---
There's not much to manage, really. Previously, I've had it implemented it with 3 lines of inline assembly. Now, that's no longer necessary, because beginning with version 4.2, gcc has CAS (and pretty much any other atomic operation) as built-in intrinsic. They're much easier to use, portable, take care of pointer sizes, and optimize better.

killerbot:
lock free : try to find articles/presentations from Scott Meyers or Herb Sutter : these 2 have good explanations.

Navigation

[0] Message Index

[#] Next page