Xamarin c# - Multi-threading algorythm sorted into list

Emixam23Emixam23 USMember ✭✭✭
edited July 2016 in General

It's hard to describe what I want to do into as title so I hope the question seems clear to you ! :)

For a personnal project, I would like to make something faster than what I have.
The goal is, you have 3 point on the map, let say Paris (Because I'm from france ! :p), Brussels (French people likes belgium people so..) and Moscow (Don't be afraid vlad, we just speaking, nothing more !).

So to make a Polyline onto my map, I will need the geopoints to reach each of them. The polyline will so joins Paris -> Brussels -> Moscow. Of course, the Direction API Google will help us

We will then get, by making a request, a json object.

[Routes][Legs][Steps] will be the data we'll focus. For each steps, we got 3 things I need, start_location, end_location & polyline.

We need to decrypt polyline, and for this, I have this code (Which works):

    /// <summary>
    /// Decode google style polyline coordinates.
    /// </summary>
    /// <param name="encodedPoints"></param>
    /// <returns></returns>
    public static List<Position> Decode(string encodedPoints)
    {
        if (string.IsNullOrEmpty(encodedPoints))
            throw new ArgumentNullException("encodedPoints");

        char[] polylineChars = encodedPoints.ToCharArray();
        int index = 0;

        int currentLat = 0;
        int currentLng = 0;
        int next5bits;
        int sum;
        int shifter;

        List<Position> polylinesPosition = new List<Position>();

        while (index < polylineChars.Length)
        {
            // calculate next latitude
            sum = 0;
            shifter = 0;
            do
            {
                next5bits = (int)polylineChars[index++] - 63;
                sum |= (next5bits & 31) << shifter;
                shifter += 5;
            } while (next5bits >= 32 && index < polylineChars.Length);

            if (index >= polylineChars.Length)
                break;

            currentLat += (sum & 1) == 1 ? ~(sum >> 1) : (sum >> 1);

            //calculate next longitude
            sum = 0;
            shifter = 0;
            do
            {
                next5bits = (int)polylineChars[index++] - 63;
                sum |= (next5bits & 31) << shifter;
                shifter += 5;
            } while (next5bits >= 32 && index < polylineChars.Length);

            if (index >= polylineChars.Length && next5bits >= 32)
                break;

            currentLng += (sum & 1) == 1 ? ~(sum >> 1) : (sum >> 1);

            polylinesPosition.Add(new Position(Convert.ToDouble(currentLat) / 1E5, Convert.ToDouble(currentLng) / 1E5));
        }

        return (polylinesPosition);
    }

Then I add it to map, I draw the polyline etc etc.. But it's long if I have to reach multiple points, so if we take my example (Paris -> Brussels -> Moscow) I would like to run on something like a thread-pool for all of the polyline I have to make. When I say all polyline, I mean (Paris-Brussels and Burssels-Moscow). The thing is, in our case, the first polyline will be finish sooner due to the shortest distance, but what about a first polyline longest than a second polyline in the algorythm? I though about mutex and lock (as in C) but is it the best way to handle it? Also, I would like to decode each popyline code (that I got from json response of Google API) into a thread-pool by following the same logic.

The final result has to be a List<Position> so make something into multi-thread seems really easy, but how to get it still in order?

Maybe it would be juste an index or an ID that I would keep for each action, but it seems weird and I think, anyway, that I'm not looking to the right direction..

Any advices about it?

Thank for reading, and thank in advance for help !

Answers

  • BradChase.2654BradChase.2654 USMember ✭✭✭

    You will either need a thread safe collection or will need to do a lock on each add to the collection. Also your variables will need to be pushed down into your while loop. Then you will need to wait on all threads to come back before returning your collection.

    The problem you are going to have here is the creation of the threads are going to be more expensive than the work being done so you will likely be slower than before. That said if you reuse threads in your pool then you might see a speed increase. How big can that collection be? Are we talking in the thousands? You might try writing a routine for batching them into fewer threads and that might yield the best results.

    As far as ordering, you can reorder by linq or indexing after you pack them up.

    As far as rendering, are you using forms or native? I have found forms WAY OVER DOES measures and layouts. So you can override the layout and measure calls and only do it when they all come back. Anyway you look at it, you only have one ui thread, so you want to make sure to present all the data at once to it.

  • Emixam23Emixam23 USMember ✭✭✭

    If I would count it, it would be 2 main thread (for the example, one by polyline) and then, one by step so yeah, maybe 1000. But now, I juste want to use something as 8 thread, but dispatching work, do you see what I mean?

    Thank for your answer :) I red it, it's interesting :)

  • BradChase.2654BradChase.2654 USMember ✭✭✭

    Hmm yea you definitely dont want to create a 1000 threads. Can you start by making 10 threads and then do say 100 each and batch them up? Anyway you look at it they all have to come back before going to the one UI thread. So you can just wait on them all or I guess I should say await on them all and then push to the ui thread your final output. One thing to double down on here, is DO NOT keep creating new threads. Reuse the same threads, it will be much much faster.

  • DavidDancyDavidDancy AUMember ✭✭✭✭

    @Emixam23 I am wondering if the TPL Dataflow library will help you to do what you want. You can use it to set up processing pipelines that guarantee the order of processing, yet still run asynchronously. And because it's all based on Tasks the whole thing runs nicely in the .NET thread pool and will take advantage of multiple cores to run concurrently where they are available.

    Have a look here: https://msdn.microsoft.com/en-us/library/hh228603(v=vs.110).aspx

  • DavidDancyDavidDancy AUMember ✭✭✭✭

    @Emixam23 In addition you may find the example here helpful: https://github.com/programmation/DataflowQueue.

    I'm fairly sure you could improve on it.

  • Emixam23Emixam23 USMember ✭✭✭
    edited July 2016

    Anyway brad, it does following a MVVM logic so when its finish, a callback is called on the UI part, this function update the bindable property and the renderer get the event by OnElementPropertyChanged :) I did it like that because I though it was logic, doesn't it? :/

    Also thank to you David, however, I'll take a look later for your answer, sorry but it's currently 2am in France and I have a long day in much that a big party during all of the weekend :P But I keep this thread/question in my mind so you will get an answer probably on Monday !

  • BradChase.2654BradChase.2654 USMember ✭✭✭
    edited July 2016

    @Emixam23 Yea thats definitely the way to do it. If you have your collection size already known before the threading then you can just create an array of known size and index the thread returns then when all are done set your property. No need for added libraries unless you plan on doing alot of this stuff. That way you dont have to linq it for an enumerator which would yield better speed but even in the thousands, you are splitting hairs.

    EDIT: To add, if you use linq, you have to remember that each time that property is called, it will traverse and redo your enumerator every time. Which can be costly.

Sign In or Register to comment.