Author Topic: Interesting multithreading stuff that might be useful for code completion...  (Read 8198 times)

Offline rickg22

  • Lives here!
  • ****
  • Posts: 2283
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.

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.


Offline thomas

  • Administrator
  • Lives here!
  • *****
  • Posts: 3979
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.
"We should forget about small efficiencies, say about 97% of the time: Premature quotation is the root of public humiliation."

Offline rickg22

  • Lives here!
  • ****
  • Posts: 2283
According to what Martin discovered from the wxGurus, these won't help us, though... as it's wxString that is unsafe.

I see...

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

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.

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

Offline thomas

  • Administrator
  • Lives here!
  • *****
  • Posts: 3979
Cool! How did you manage to implement the CAS primitive? (msg me)
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.
"We should forget about small efficiencies, say about 97% of the time: Premature quotation is the root of public humiliation."

Offline killerbot

  • Administrator
  • Lives here!
  • *****
  • Posts: 5297
lock free : try to find articles/presentations from Scott Meyers or Herb Sutter : these 2 have good explanations.

Offline rickg22

  • Lives here!
  • ****
  • Posts: 2283

because beginning with version 4.2, gcc has CAS (and pretty much any other atomic operation) as built-in intrinsic.

Thomas: That's awesome!! (Edit: By the way, I researched a bit, and it's version 4.1.0 that began implementing the built-in atomics. This is great, since the GCC version I got at home is 4.1.x).

So, With those primitives we could implement fast mutexes for quick variable changes (lock, change variable, unlock) instead of having to waste at least 1 millisecond (which would be equivalent of a million operations in today's computers) in a sleep cycle. Maybe that could speed up code completion a lot. Who knows...

Anyway, thanks for the info about the GCC primitives!
« Last Edit: September 05, 2008, 07:20:41 pm by rickg22 »

Offline thomas

  • Administrator
  • Lives here!
  • *****
  • Posts: 3979
I smell danger.
"We should forget about small efficiencies, say about 97% of the time: Premature quotation is the root of public humiliation."