2
\$\begingroup\$

I am trying to reduce the total execution time of my code.

I have a GPS system which calculates routes between two points, and returns all points in between them.

I did a simple profile and the calculation of the route takes on average 30 ms while, from main thread input to main thread output, it takes almost 700ms to travel.

Do you have any suggestions on improving this?

Definitions

#if defined(WIN32) || defined(_WIN32) || defined(__WIN32__)
#   include <process.h>
#   define OS_WINDOWS
#else
#   include <pthread.h>
#   define sscanf_s sscanf
#   define sprintf_s sprintf
#endif

#if defined(WIN32) || defined(_WIN32) || defined(__WIN32__)
#   define MUTEX CRITICAL_SECTION
#else
#   define MUTEX pthread_mutex_t
#endif

#ifdef OS_WINDOWS
#   define EXIT_THREAD() { _endthread(); }
#   define START_THREAD(a, b) { _beginthread( a, 0, (void *)( b ) ); }
#else
#   define EXIT_THREAD() { pthread_exit( NULL ); }
#   define START_THREAD(a, b) { pthread_t thread;\
                                pthread_create( &thread, NULL, a, (void *)( b ) ); }
#endif

As you can see, the mutexes on windows are defined as CRITICAL_SECTION:

Variables and Structures

struct QuedData
{
    int start;
    int end;
    int extraid;
    AMX * script;
    QuedData(int start_,int end_,int extraid_, AMX * script_)
    {
        start = start_;
        end = end_;
        extraid = extraid_;
        script = script_;
    }
};

struct PassData //thanks to DeadMG for improvements.
{
    std::vector<cell> Paths;
    int extraid;
    AMX * script;
    int MoveCost;
    template<typename Iterator> PassData(Iterator begin, Iterator end, int extraid_, int MoveCost_, AMX * script_)
        : Paths(begin, end)
    {
        extraid = extraid_;
        MoveCost = MoveCost_;
        script = script_;
    }
    ~PassData()
    {
        Paths.clear();
    }

};

vector          <QuedData>                      QueueVector;
queue           <PassData>                      PassVector;

This are the two variables and their structures which are important for transporting the data from input to output

Mutex

#if defined OS_WINDOWS

struct Lock //thanks to 'doublep' from StackOverflow for this RAII solution, edited it
{
  MUTEX mutex;
  bool    locked;

  Lock (MUTEX mutex)
    : mutex (mutex),
      locked (false)
  {
  }

  ~Lock ()
  {
      release ();
  }

  bool acquire (int timeout = -1)
  {

    if (!locked && TryEnterCriticalSection(&mutex) != 0)
    {
        locked = true;
    }
    return locked;
  }

  int release ()
  {
    if (locked)
    {
        LeaveCriticalSection(&mutex); locked = false;
        return true;
    }
    return false;
  }
};

MUTEX mutex_q;
MUTEX mutex_p;
#else
struct Lock //and here is my little edit for linux
{
  MUTEX&  mutex;
  bool    locked;

  Lock (MUTEX& mutex)
    : mutex (mutex),
      locked (false)
  { }

  ~Lock ()
  { release (); }

  bool acquire (int timeout = -1)
  {
    if (!locked && pthread_mutex_lock (&mutex) == 0)
      locked = true;
    return locked;
  }

  int release ()
  {
    if (locked)
      locked = (pthread_mutex_unlock (&mutex) == 1);
    return !locked;
  }
};

MUTEX mutex_q = PTHREAD_MUTEX_INITIALIZER;
MUTEX mutex_p = PTHREAD_MUTEX_INITIALIZER;

#endif

This is the code I use to avoid deadlocks / lockups etc:

Initialization

PLUGIN_EXPORT bool PLUGIN_CALL Load( void **ppData )
{
    #if defined OS_WINDOWS
    InitializeCriticalSection(&mutex_q);
    InitializeCriticalSection(&mutex_p);
    #else
    pthread_mutex_init (&mutex_q,NULL);
    pthread_mutex_init (&mutex_p,NULL);
    #endif
    START_THREAD( Thread::BackgroundCalculator, 0);
    return true;
}

Here I initialize the critical sections/mutexes where needed:

Calculation Thread

#ifdef OS_WINDOWS
    void Thread::BackgroundCalculator( void *unused )
#else
    void *Thread::BackgroundCalculator( void *unused )
#endif
{
    int startid;
    int endid;
    int extra;
    AMX *amx;
    vector <cell>way;
    int costx;
    while( true )
    {
        if(!QueueVector.empty())
        {
            Lock  q (mutex_q);
            Lock  p (mutex_p);
            if (q.acquire ())
            {
                startid = QueueVector.back().start;
                endid = QueueVector.back().end;
                extra = QueueVector.back().extraid;
                amx = QueueVector.back().script;
                QueueVector.pop_back();
                q.release();
                ///////////////////////////////////////
                /*LARGE_INTEGER frequency;        // ticks per second
                LARGE_INTEGER t1, t2;           // ticks
                double elapsedTime;

                // get ticks per second
                QueryPerformanceFrequency(&frequency);

                // start timer
                QueryPerformanceCounter(&t1);*/
                ///////////////////////////////////////
                dgraph->findPath_r(xNode[startid].NodeID ,xNode[endid].NodeID,way,costx);
                ///////////////////////////////////////
                //QueryPerformanceCounter(&t2);
                //elapsedTime = (t2.QuadPart - t1.QuadPart) * 1000.0 / frequency.QuadPart;
                ///////////////////////////////////////
                //cout << elapsedTime << " ms.\n";
                ///////////////////////////////////////
                dgraph->reset();

                while(p.acquire () == false)
                {}
                PassVector.push(PassData(way.begin(),way.end(),extra,costx,amx));
                way.clear();
                costx = 0;
                p.release();
            }
        }
        SLEEP(30);
        //-------------------------
    }

    EXIT_THREAD();//should be never reached..
}

This is where the calculation of the route actually happens:

Main thread - input

static cell AMX_NATIVE_CALL n_CalculatePath( AMX* amx, cell* params )
{
    if(params[1] < 0 || params[1] > (MAX_NODES-1) || params[2] < 0 || params[2] > (MAX_NODES-1))
        return 0;
    Lock  q (mutex_q);
    int tries = 0;
    while (q.acquire (1) == false && ++tries < 10)
    {
    }
    if(q.locked)
    {
        QueueVector.push_back(QuedData(params[1],params[2],params[3],amx));
        q.release ();
        return 1;
    }
    return 0;
}

This is the function in the main thread which gets called from a 'script':

Main thread - output

PLUGIN_EXPORT void PLUGIN_CALL
    ProcessTick()
{
    if(g_Ticked++ == g_TickMax)
    {
        if(!PassVector.empty())
        {
            Lock  q (mutex_p);
            int tries = 0;
            while (q.acquire (1) == false && ++tries < 10)
            {
            }
            if(q.locked)
            {
                int ptr;
                float Cx;
                for (std::vector<AMX *>::iterator a = amx_list.begin(); a != amx_list.end(); ++a)
                {
                    if (!amx_FindPublic(* a, "GPS_WhenRouteIsCalculated", &ptr) && PassVector.front().script == *a)
                    {
                        Cx = (float)PassVector.front().MoveCost;
                        amx_Push(* a, amx_ftoc(Cx));
                        amx_Push(* a, PassVector.front().Paths.size());
                        cell * RawPath = new cell[PassVector.front().Paths.size()+1];
                        copy(PassVector.front().Paths.begin(),PassVector.front().Paths.end(),RawPath);
                        amx_PushArray(* a, &ppamx_addr, &ppamx_physAddr, RawPath, PassVector.front().Paths.size()+1);
                        amx_Push(* a, PassVector.front().extraid);
                        amx_Exec(* a, NULL, ptr);
                        amx_Release(* a,ppamx_addr);
                        free(RawPath);
                    }
                }
                PassVector.pop();
                q.release ();
            }
        }
        g_Ticked = 0;
    }
}

Here the result is returned to the 'script'.

The way the route calculation happens:

  1. script calls CalculatePath->function in code
  2. gets executed->thread
  3. calculates route->main thread calls script
  4. passes the end results

If you need the full code, it is located here.

\$\endgroup\$
5
  • \$\begingroup\$ Why don't you use the mutex objects on Windows? It surely does have them and critical section is anything but a mutex. \$\endgroup\$
    – fork0
    Nov 26, 2012 at 20:02
  • \$\begingroup\$ it's not for sharing across multiple processes so I think I am supposed to use critical sections? Correct me if I am wrong. \$\endgroup\$
    – user19795
    Nov 26, 2012 at 20:07
  • \$\begingroup\$ You are wrong. Mutexes in Windows, if left unnamed (the usual case), are restricted to a process and are the fastest synchronization primitive. \$\endgroup\$
    – fork0
    Nov 26, 2012 at 20:35
  • \$\begingroup\$ I did use Mutexes in the past exactly with this code which lead to this topic: stackoverflow.com/questions/9523532/mutex-cant-acquire-lock , it confuses me now. \$\endgroup\$
    – user19795
    Nov 26, 2012 at 20:57
  • \$\begingroup\$ Well, the answer in the question doesn't suggest that mutexes are exclusively inter-process. Or does it? \$\endgroup\$
    – fork0
    Nov 27, 2012 at 12:24

1 Answer 1

1
\$\begingroup\$

I suggest to replace your code with the implementation of boost.lockfree and boost.thread to be system independant.

  • boost.lockfree for message passing (replacing yor queue vector with it)
  • boost.thread (or standard threads if you have a c+11 compiler) to replace threading and synchronisation with platform agnostic calls (same interface as the standard c+11 thread interface)

As for the mutex vs critical section debate, fork0 is wrong. look here for a proof.

\$\endgroup\$
13
  • \$\begingroup\$ the boost.lockfree containers seem good, I have a RemoveFromQueue function in the script, sho an element should be removable at any position, is this possible with boost.lockfree, and any simple example code on running threads etc? \$\endgroup\$
    – user19795
    Nov 27, 2012 at 13:53
  • \$\begingroup\$ else I will rewrite the RemoveFromQueue function or remove it. \$\endgroup\$
    – user19795
    Nov 27, 2012 at 13:54
  • \$\begingroup\$ lockfree can remove an object from the queue, but not from any position. only the top one with pop(), as it's a first in first out container. there is also a lifo queue (named stack). usually, on mutlithreaded queues, you only need fifo queues. \$\endgroup\$
    – geekpp
    Nov 27, 2012 at 14:18
  • \$\begingroup\$ if a function gets executed in a thread and only reads global variables which don't change, it's safe to execute that function in multiple threads? \$\endgroup\$
    – user19795
    Nov 27, 2012 at 14:22
  • \$\begingroup\$ yes, it's safe if no other threads are going to change the variables. \$\endgroup\$
    – geekpp
    Nov 27, 2012 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.