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:
- script calls
CalculatePath->function
in code - gets
executed->thread
- calculates route->main thread calls script
- passes the end results
If you need the full code, it is located here.