Sending Messages between Threads

[dragonjim]

Here is the final effort - which isn't much of an improvement if truth be told...

ThreadTest1b.G32 (2.66 KB)

This version tries to use messaging to force the main thread to wait inactive while the x number of threads specified are doing their stuff; it also tries to cut down time lag between one thread ending and another starting by creating all the threads first in suspended mode, and then, when a space becomes available, resuming them: this does cut down the lag marginally but, as the threads have to be created in the first place, it does nothing to reduce the overall time.

In other words, this is about as streamlined as it is possible to get with the idea of using only those cores that are available. Rather than being depressing, this shows the superiority of GFA in linear operation - it has optimised string handling routines which process those 64 strings extremely quickly - BUT linear only beats the multithreading hands down because it only has to create the string in memory once (when it is created as the same length as buf$(n)); in ThreadTest2, of which your copy with only a few 'DoEvents' statements commented is below...

ThreadTest2.G32 (2.82 KB)

...GFA is forced to increment the length of the string every time it adds another character which means that there is a lot of memory swapping and which explains why, in that example, multithreading is more efficient.

Finally, all that can be said about ThreadTest3 has been said about ThreadTest1 (I think)

If you want to know which versions I am referring to, they are preserved in your post from which I got them.

I wouldn't give up on multithreading as you seem to have the basics right - what seems to be tripping you up are some of the peculiarities of GFA data handling and address management. When working in a linear format, GFA is generally so efficient (and extremely good at clearing up our rubbish for us), that it outperforms most other programming languages run through the IDE and, sometimes, when compiled - not bad for a 20 year old program; sadly, I don't think its internal routines were ever optimised for multithreading, which is illustrated by the fact that there is only one command for it, hence the reliance on the less-optimised API functions and need for us to be more careful in clearing up. This would fit in with your original usage of multithreading of having two or more threads doing different tasks running side-by-side as being the most efficient, although as ThreadTest2 shows, multithreading using similar threads can also show some speed advantages, although whether they are great enough for the hassle involved in creating them is another matter...

Keep in mind that multithreading using GFABasic is relatively new and unknown territory - or it is for those left of us still using the language; what we've been doing over the passed few weeks is the classic experimentation technique - as you stated in your last post - of trial and error which can be extremely frustrating (you know that already) and can hinge on the smallest factor: a quick example is, when I was rewriting ThreadTest1, I entered the parameter for OtherThread as 'n'; all of a sudden, nothing worked, errors were thrown and I became extremely proficient in closing down and restarting GFA; then I remembered that the parameters for procedures default to variants (and CreateThread doesn't pass variants well) and that I should have entered n% instead and all worked fine; in a linear routine, GFA would have thrown an error message - sadly, GFA error management breaks down in multithreading which is actually, I believe, the main cause of the 'GFABasic has stopped working' error. This just makes things harder and forces us to work out our mistakes for ourselves.

Anyway, enough rambling on. Keep up the good work.

[troycheek]

For the record, I know that creating very long strings one character at a time is terribly inefficient and almost intentionally designed to give the memory management routines a heart attack. I chose to do that deliberately because I was desperate to find something that would bog down GB32 enough to create a job that took long enough to execute to be measurable. GB32 is so bleeping fast, especially on modern machines which would have been considered science fiction 20 years ago, that multi-threading turns out to be unnecessary for pretty much any task I can think up. Stupid Moore's Law. Or, as we've seen, the overhead involved in creating, destroying, and sending messages between threads can eat up any advantage they have.

I'm tempted to program an unoptimized Bubble Sort and throw a few hundred thousand elements at it just to see what happens. I know it will be slower than the built-in Quick Sort command, but I have the sneaking suspicion that it will be fast enough for any real world data set I'd want to use it on that I'd never get around to optimizing it, and I've optimized a lot of Bubble Sort routines over the years. It's kind of a hobby. "Sure, Quick Sort is faster in general usage and superior in every way, but with this data set and these optimizations, my Bubble Sort is just as fast with half the code, no stack, and no recursion."

On the other hand, a recursive sort like Quick Sort could conceivably benefit from multi-threading...

EDIT: I was half kidding about using threads in Quick Sort, but it turns out that it's been done for Quick Sort and Merge Sort and other divide and conquer sorting methods.  In fact, I just read an article where threads were suggested for Bubble Sort.  Communication between threads is necessary, I think, to keep two threads from seeing the same adjacent elements and both trying to swap them.  So, some kind of "I'm at element 20, so stay at least two elements away from that one.  Now I'm at element 21."  I expect a lot of effort for little return, as an O(n^2) algorithm with 8 threads is still an O(n^2) algorithm, even if it reaches the theoretical 8 times speed increase.

[dragonjim]

That's an interesting idea and worth having a shot at - I'll be interested to see how you get on.

For the record, I understood why you had used the multi-step increments in your examples - I was simply trying to explain why the multithreading played the mythical hare in one example and the tortoise in the other.

[troycheek]

Once again, consider this the short, stupid version of the long, intelligent message I was writing when the power decided to go off.  I really must get around to buying a new UPS.

Short version:  The built-in Qsort command is so fast on standard numeric and string arrays that it's almost always best to just use it.  It's so fast that it's probably faster to massage any non-standard arrays or TYPE structures into some kind of string array and use Qsort on that.

I've implemented the following sorts in single-threaded routines so as to get a better grasp of how they work and how they could best benefit from multi-threading:

Bubble Sort:  Works by iterating over the array, comparing and swapping adjacent elements.  Multiple threads could scan the array at the same time, comparing and swapping elements as needed.   Best case, regular time divided by T threads.  Threads would have to constantly update each other on their positions to keep multiple threads from trying to swap the same or adjacent elements.  (At best, one thread could end up swapping elements that another thread just swapped, putting the elements back in their original places or even further out of sorts.)  Conflicts could be reduced by partitioning up the array and confining each thread to its own partition, but what to do with elements that need to move to another partition?  Bubble Sort's optimization comes from keeping track of where the swaps have occurred, so that information would need to be passed around as well.  This also results in smaller and smaller number of elements being repeatedly scanned, leading to more conflicts.  Outlook:  not so good.

Selection Sort:  Works by scanning the entire array for the smallest element, swapping it with element in the first position, then repeating for each additional position.  Same number of scans but fewer swaps than Bubble.  Could partition array into T parts and have each thread scan its partition, reporting back smallest element in each partition.  Main thread compiles and checks this short list for smallest element overall, performs swap.  Initial scan, regular time divided by T threads.  If you keep track of short list, only need to re-scan partitions where swaps occur.  Needs only 2 threads for subsequent scans.  Outlook:  possible, but probably not much of an improvement.  Plus, by partitioning, probably turned this into bucket or merge or some other type of sort.

Insertion Sort:  Check each element, scan back among already sorted part, insert it into proper position, shuffling all later elements down one.  Can be done either by shifting elements one by one or using the built-in DELETE and INSERT commands.  Fewer scans but more swaps than Selection.  So much shifting around of elements that I'm not sure how to divide it up for multi-threading.  Outlook:  bad.

Bucket Sort:  Divide elements into multiple "buckets" based on criteria such as 26 buckets based on first letter of last name or something like that.  Two ways to go from here.  1) re-combine elements into original array and sort with Bubble or Insertion, which are more efficient when elements are closer to final positions.  Not any use for multiple threads.  2) sort each bucket (Bubble or Insertion are more efficient with smaller number of elements) with sorting method of choice, T buckets at a time, then re-combine into original array.  No overlap, only need to communicate when threads are finished and ready for next bucket assignment.  Regular time divided by T, plus whatever performance boost your sort method of choice gets from working with lists 1Tth the usual size.  Down side: if many more buckets than threads, lots of starting and stopping of threads.  Outlook:  pretty good.

Merge Sort:  Separate elements into T buckets (not based on criteria like above), one thread for each bucket.  Each thread sorts its bucket by Bubble or Insertion (more efficient with smaller number of elements) or other sort method of choice.  Perform T-way merge (check each bucket's lowest element for lowest element overall, move it to main array, repeat).  OR shuffle buckets into main array (move first element of each bucket into main array, second element, etc) then sort whole array with Bubble or Insertion, which are more efficient when elements are closer to final positions.  Regular time divided by T, plus whatever performance boost your sort method of choice gets from working with lists 1/Tth the usual size.  Outlook:  good.

Quick Sort:  Pick pivot point (entire articles have been written about that part), partition all smaller elements to lower half on one side of pivot, all larger ones to upper half.  Sort lower half, sort upper half, with recursive Quick Sort or other method of choice.  The more partitions, the faster the sort.  For multi-threading, divide into T partitions and assign each partition to a thread.  Allow thread to sort its partition with method of choice or continue partitioning.  Already quick time divided by T.  Outlook:  good, but I have least experience programming it and least instinctive understanding of this method, so I'm least likely to use it.

Next step:  I'll probably develop some kind of mutant offspring of Merge or Bucket and Quick to divide up the data into T partitions, one for each thread.  Each thread will probably use Merge or Quick to further partition, Bubble or Insertion to do final actual sorting.  I just never liked the partition down to the last element, single elements are by definition sorted, back your way out of deep recursion, way of doing things.

[dragonjim]

For a short, stupid message, that was quite long and informative.

I have to agree with what I believe is your conclusion that the Quick Sort principle would work best, but with a few tweaks to suit multitasking, such as:

1. Do one scan through the data to be sorted and record the maximum and minimum values (for strings, use the ASCII/ANSI value of the first letter)
2. Select the optimum number of threads for your system and assign a maximum and minimum acceptable value to each thread in the following way: If the overall max is 32 and the min is 3 and you have decided on six threads, then the range for each thread would be five. This means that for thread one, the minimum would be 3 and the maximum 7; for thread two, 8 and 12; thread three, 13 and 17; thread four, 18 and 22; thread five 23 and 27 and, finally, thread six 28 to 32.
3. Now do a second scan of the data array and make a record of how many elements would be within the max and min of each thread.
4. Now, create the threads and get each thread to create a local array with the number of elements dependent upon the values attained from step 3; in the main thread create a new master array with the same number of elements as the original data source.
5. Then, get each thread to scan the original data and extract only the values that fall within its prescribed max and min values and put them into its local array.
6. Get each thread to run whichever form of search you believe to be the quickest for shorter arrays and, when complete, feed the sorted results into the relative elements of the master array in the main thread (hence, if the first thread is sorting 31 values, it would enter its results into elements 1 to 31 (if using base 1) while the second thread, which is sorting 46 values, would pass its results to elements 32 to 77, and thread three...etc.). Then close the thread.

This way you get six (or however many you wish) shorter searches being done almost simultaneously without the added time of then having to assimilate the results into one bigger array.

Just an idea...