Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have made a function which calculates the index of a point to which an arbitrary point on a polygon made of XY points belong.

This is a visual representation:

enter image description here

And this is the function I made:

stock GetNodeIndexFromPolygonIndex(polygonid,Polygon_Size)
{
    new polid = (polygonid - (polygonid % 2));
    new mid = Polygon_Size/2;
    if(polid > mid)
    {
        polid /= 2;
        return (mid - (++polid));
    }
    else
    {
        polid /= 2;
        if(polid == 0)
        {
            return 0;
          }
        return --polid;
    }
}

Is there anything I can optimize here? This function is going to be called ~2000 times in the worst case in one run on a single threaded application. I would like this to be as optimal as possible. Is it already?

share|improve this question
2  
I personally don't understand the explanation. Why 3 in the first red circle for example? –  Quentin Pradet Feb 7 '13 at 14:32
    
The basic thing is thhat the red circles are a PATH which is created from XYZ points and have indexes from 0 to up. yet, there is a polygon around it which has to be closed so one polygon point has 4 indexes (XY, XY, first and last polygon point). The black points are thus the polygon around the red path with a specific width. Just like here: i.stack.imgur.com/x865n.png –  user19795 Feb 7 '13 at 16:15
add comment

1 Answer 1

up vote 1 down vote accepted

First, I do not know anything about PAWN.

Does it have a profiler? Can any profiler be used? If yes, probably use it.
If no, write at least some test units to measure execution time.

I will assume typical language elements. I will assume polygonid > 0 and Polygon_Size > 0, because I do not know (and did not find in short time) the behavior of / and % for negative numbers.

As far as I understood, there is a virtual machine between compiler and execution. This makes things a little bit more complex, but well, we will assume that nothing special happens there.

Some of the optimizations could change nothing, because the compiler already does it. I can not predict or test it.

That said, I will choose line after line. I do not know if you can change the algorithm, because like Cygal I do not understand the exact purpose.


new polid = (polygonid - (polygonid % 2));

This makes polid the next smallest even number? % is rather costly, you could either do a polygonid & 1 instead of polygonid % 2 or new polid = polygonid & (max_value - 1) which will set all bits, but the last one to zero. max_value - 1 should be precalculated.


new mid = Polygon_Size/2;

Change to: new mid = Polygon_Size >> 1 This will be done most probably by the compiler anyway, but we do not know, so lets try it.


polid /= 2;

This is calculated in both branches. It could help to do it before the branching:

new polid_half = polid >> 1;
...

return (mid - (++polid));

This depends on the language details. It could be that ++polid as preincrement operator will load polid, update it by one, and store polid back. We do not plan to use the modified polid, so we could try return (mid - polid + 1) assuming that ++polid is not some magic fast special instruction compared to the normal +.


    if(polid == 0)
    {
        return 0;
    }

This does only happen if polygonid is 0 or 1. If this happens a lot, you should return immediately at the beginning, saving all the rest:

if (polygonid < 2 )  //assuming polygonid > 0
    return 0;

And remove the check inside the else branch.


    return --polid;

Same as before, it could be better to return polid - 1


Depending on the branch prediction handling, it could be better to have only one return point, not one in every branch. You could introduce a return value and set it according to the current logic.


I would try one change after the next and profile every step. All together, it could be:

stock GetNodeIndexFromPolygonIndex(polygonid,Polygon_Size)
{
    if (polygonid < 2 )  //assuming polygonid > 0
        return 0;
    new result = 0;
    new polid = polygonid & (max_value - 1); //polid is a bad name
    new polid_half = polid >> 1;
    new mid = Polygon_Size >> 1;
    if(polid > mid)
        result = mid - polid_half + 1;
    else
        result = polid_half - 1;
    return result;
}
share|improve this answer
    
Another caveat: those micro-optimizations make the code way less readable, but since it's probably the only thing to do, here's an upvote for you. :) –  Quentin Pradet Feb 8 '13 at 8:28
    
@Cygal Well, the >> 1 are probably too much and some if-else braces would also increase readability. –  Sulthan Feb 8 '13 at 13:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.