Thomas Karcher wrote:
Hi there,I'm writing a multithreaded merge sort that suffers from massive amounts of context switches (as seen by vmstat). The outline of the program is roughly as follows: ==== my @sortdata : shared; // the values to be sorted [...] // starting two threads new threads( \&mergesort_string, $begin, $half, $threaddepth - 1 ); new threads( \&mergesort_string, $half, $end, $threaddepth - 1 ); [...] sub mergesort_string { my ( $begin, $end, $threaddepth ) = @_; // sorting "my" part of @sortdata, as delimited // by $begin and $end } ==== By playing around, I discovered that the "shared" is what causes the context switches. They take up about 40% of the duration of the program for an array of 10,000 elements. I don't need any locking on the elements itself because the merge sort algorithm itself guarantees in my opinion that there is no conflicting access to them. Am I missing something here? How can I avoid those context switches that make the program essentially useless?
I'm afraid there isn't much you can do short of writing your own XS code that bypasses threads::shared. Due to the global lock on the shared interpretter (where shared variables are actually stored), each thread that touches the array is going to be trying to acquire the global lock, ergo lots of lock contention, leading to lots of probable context switches. You may be able to improve performance by copying parts of the array out to a private version, but that may not adapt to your algorithm. Dean Arnold Presicient Corp.
