Calculate the difference between multiples of two different numbers

Let's start with some general points. It's always better to start with intuitive code that you and your colleagues can understand. Then evaluate performance and find bottlenecks. If you try to hyper-optimize from the start, you will:-

• Makes code complex, error-prone and hard to understand.
• Most likely to optimize code that has little impact on overall performance while ignoring major bottlenecks. Unless you don't understand the nuances of processors, compilers, programming languages, and environments, there's a good chance you'll get worse performance if you try to guess at these optimizations.

It's better to measure, find bottlenecks, and then improve the performance of those bottlenecks. If you suspect a slow algorithm/implementation, profile it. If you want to know which algorithm/implementation works best, have a competition. Test with varying datasets, as an input that performs well for one set of inputs (3, 5) may not work for another set of inputs (3, 500000000).

Having said that, let's start with what we have, explore some options, and finally provide an initial implementation for the situation you described in your edit (i.e. multiple values). Note that some of these implementations may not be suitable for your situation or your environment, but they involve a general approach.

Status (your code is as it is)

The code performs some conditional and arithmetic operations. These are the operations that processors eat before breakfast...before they wake up...when the nanoparticle's eyelids blink, ie very fast . Now, I know you're using an Arduino, so you won't have the most powerful processors in the world, but these can still do these things quickly. I wanted to create some benchmarks of my own, so I implemented a function very similar to yours in C++ (you mentioned in your question that C++ is OK). I call it a test ConditionalTestbecause it follows the if...elseprocess, and because I have a bad name.

Note: While I've done some preliminary testing with the results, the code presented in these answers is by no means production-ready. It lacks basic parameter checking (such as null or uninitialized variables) and has some performance optimizations that I usually ignore for safety reasons. Anyway, the code is:

static void ConditionalTest( int startA, int startB, unsigned long long testIterations )
{       
    gl_result = 0;      
    gl_current=0;
    int distToA = startA;
    int distToB = startB;

    for( unsigned long long i = 0; i < testIterations; i++ )
    {           
        if( distToA > distToB ) //B comes first
        {           
            gl_result = distToB;
            gl_current += distToB;
            distToA -= distToB;
            distToB = startB;               
        }
        else if( distToB > distToA ) //A comes first
        {       
            gl_result = distToA;
            gl_current += distToA;
            distToB -= distToA;
            distToA = startA;                               
        }
        else
        {       
            gl_result = distToA; 
            gl_current += distToA; //Arbitrarily, could be distToB
            distToA = startA;
            distToB = startB;
        }
    }    
} 

Notice: -

• I assign the value to the global gl_result instead of printing it to save time filling messages on the console, and also bloat the result because printing to screen takes longer than others.
• I have to use unsigned long longfor testIterationsand some other variables because otherwise they intwrap around.
• gl_is a global variable in the test.

The nice thing about this algorithm is that it uses a very basic structure, so

• Even other programmers with a very basic understanding of programming or other programming languages ​​will quickly understand what it is doing.
• It's very portable - easy to translate into other languages ​​and operating systems.
• Regarding performance, what you see is what you get - what you see is what you get, so it's unlikely to hide a big performance bottleneck in a 3rd party library call.

Right now, I'm running a rather dirty machine (i7 2600), so it took 1000000000 (1 billion) iterations to start, which turned out to take over a second. In this case, it takes an average of 2400 ms for 1 billion iterations. I think it's fast, but let's see how we can improve it. First let's see what adjustments we can make.

Make adjustments to your implementation

The parameters are (3,5), so initially distA is 3 and distB is 5. Note that 3 is less than 5. The first ifwill check distToA > distToB:then elif distToB > distToA:. However, distToB (originally 5) is twice as large as distToA (originally 3). To improve performance, you want ifto satisfy the first condition as much as possible to minimize the number of conditions checked in each iteration. I'm making some assumptions about the compiler when I say this, but more on that later.

So very simple, we can swap ifsaround. However, it's not that simple. The problem I found was that the compiler did some nice optimizations on the second if and last. Did you see your comment Arbitrarily, could be distToB? Well, the truth is, you have to be gl_current += distToA;in else ifand gl_current += distToAout of elseallowing the compiler to optimize that statement. So in my case it's not arbitrary (in your case it will depend on your compiler). Therefore, we need to change the else to allow these optimizations to happen. The final code is:

static void ConditionalTestV2( int startA, int startB, unsigned long long testIterations )
{       
    gl_result = 0;      
    gl_current=0;
    int distToA = startA;
    int distToB = startB;

    for( unsigned long long i = 0; i < testIterations; i++ )
    {                       
        if( distToB > distToA ) //A comes first (where a is more likely to be first than b)
        {       
            gl_result = distToA;
            gl_current += distToA;
            distToB -= distToA;
            distToA = startA;                               
        }
        else if( distToA > distToB ) //B comes first
        {           
            gl_result = distToB;
            gl_current += distToB;
            distToA -= distToB;
            distToB = startB;               
        }
        else
        {       
            gl_result = distToB;   //Should be distToB for optimisations
            gl_current += distToB; //Should be distToB for optimisations
            distToA = startA;
            distToB = startB;
        }
    }      
} 

Note: if( distToB > distToA )before else if( distToA > distToB ), while other now has gl_result = distToBand gl_current += distToB. After making these changes, the time it took for the test to run was: 2108 ms. These simple tweaks reduced execution time by 12%, which is good.

The biggest lesson from this is to measure any changes you make for unintended consequences.

Your compiler and execution environment may differ from mine, so your results may vary. If you plan to tune at this level, I recommend that you become familiar with the assembler and step through the assembly at key points to determine how the condition is actually executed. I'm sure there are other optimizations that could be made. If you really like it, and you're using GNU C++, __builtin_expectyou can call something in there to direct the compiler which branch to choose.

You may not always get the starting values ​​in order, in which case you need to compare the cost of a one-time sort to the total time to execute the algorithm.

Some other things to point out are:-

• You maintain a variable current, but you don't use it. If you are not using currentit, you can delete it. If the compiler has already optimized it, you may not see a performance gain.
• Your range is 100, but the loop will repeat 3*5=15 times. So you can either stop when the current you need is 15, or you can store the result and then write it out (see the Modes section).

modulus

Looking at algorithms, we always get the distance from a value, so one method that comes to mind is to take the modulo (there are answers to this question). I'm a bit skeptical about performance since modulo tends to use division, which is slower than your subtraction. Anyway, this is what I came up with:

static void ModuloTest( int startA, int startB, unsigned long long testIterations )
{   
    unsigned long long current = 0;
    unsigned long long prev = 0;
    int distToA = startA;
    int distToB = startB;

    for( long long i = 0; i < testIterations; i++ )
    {       
        current += (gl_result = FastMin(distToA - (current%distToA), distToB - (current%distToB)));
    }
}

The result is 23349 milliseconds. Almost 10 times slower than the original.

Now, I don't usually write a line with has current += (gl..., but I'm trying to reduce the number of allocations. Usually it's a stupid thing to do, because the compiler will optimize better than I do, and it's more error-prone. Still, the test is a lot slower, and I wanted to make sure I gave it a good shot. Since the process is slightly different, it's a bit unfair to start pointing your finger directly at the modulus, so something else might be to blame. So I did a simpler modulo test:

static void PureModuloTest( unsigned long long testIterations, unsigned long long mod )
{
    for(long long i = 1; i <= testIterations; i++)
    {
        gl_result = mod % i;
    }
} 

where mod is 50000, and even in this case the test takes 5x longer than yours, so I think the mod goes away if we want pure performance. I also found stl min() to have some surprising inefficiencies, but going into detail would make this longer post longer.

The next thing I want to do is look at the data. Sometimes, if you can find features/patterns in your data, you can optimize your implementation accordingly.

model

Looking at your data again, what jumps out is that the difference will repeat every a * bcycle . So in the test, once it reaches 15, the distance will repeat once. You're probably aware of this, but in your snippet, the test runs for 100 cycles ( for i in xrange(100)), so I'm not sure.

One way to use this fact is to store the value until it arrives a * b, then reuse the value until done. Note that this is essentially a matter of starting with an algorithm and then traversing the list from the beginning.

static void PatternTest( int startA, int startB, unsigned long long testIterations )
{
    int stop = startA * startB;
    list<int> resultList;
    int distToA = startA;
    int distToB = startB;   
    int val = 0;
    long long count = 0;
    while( val < stop  )
    {   
        if( distToB > distToA ) //A comes first (where a is more likely to be first than b)
        {       
            gl_result = distToA;                
            distToB -= distToA;
            distToA = startA;                               
        }
        else if( distToA > distToB ) //B comes first
        {           
            gl_result = distToB;                
            distToA -= distToB;
            distToB = startB;               
        }
        else
        {       
            gl_result = distToB;                
            distToA = startA;
            distToB = startB;
        }
        val += gl_result;
        resultList.push_back(gl_result);
        count++;
    }
    std::list<int>::const_iterator iter;
    while( count < testIterations )
    {
        for( iter = resultList.begin(); iter != resultList.end() && count < testIterations; iter++ )
        {
            gl_result = *iter;
            count++;
        }       
    }
}

The test took 1711 milliseconds, which is 29% faster than the original speed and 18% faster than the current best speed. I'm not sure if this applies in your case, but it's just an example of how analyzing expected data can improve performance.

Thread bonanza!

Now, this probably won't work in your case since you're using an Arduino. But maybe threads will be supported in the future, or you can assign the problem to other processors. Either way, it would be impractical not to include thread benchmarks, because that's what they're aiming for. Also, my computer has 8 cores and 7 of them take a lot of time, so it's nice to give them a chance to run.

If the data or algorithm can be decomposed into independent discrete parts, then the program can be designed to run independent operations on independent threads. Now we know from before that the sequence repeats every time a * b. So we can start from the different point where n"(n modulo(a*b)) == 0" .

However, we can do better and first get the value of the first one a * band then loop through the values ​​in a separate thread. This is what I do here. I choose to run 4 threads.

struct BonanzaThreadInfo
{
    long long iterations;
    list<int> resultList;
    int result;
};

static void BonanzaTestThread( void* param )
{
    BonanzaThreadInfo* info = (BonanzaThreadInfo*)param;    

    std::list<int>::const_iterator iter;
    for( long long count = 0; count < info->iterations; )
    {
        for( iter = info->resultList.begin(); iter != info->resultList.end() && count < info->iterations; iter++ )
        {
            info->result = *iter;           
            count++;
        }   
    }
    delete param;
}

static void ThreadBonanzaTest( int startA, int startB, unsigned long long testIterations )
{   
    int stop = startA * startB;
    list<int> resultList;
    int distToA = startA;
    int distToB = startB;   
    int val = 0;
    long long count = 0;
    while( val < stop  )
    {       
        if( distToB > distToA ) //A comes first (where a is more likely to be first than b)
        {       
            gl_result = distToA;                
            distToB -= distToA;
            distToA = startA;                               
        }
        else if( distToA > distToB ) //B comes first
        {           
            gl_result = distToB;                
            distToA -= distToB;
            distToB = startB;               
        }
        else
        {       
            gl_result = distToB;                
            distToA = startA;
            distToB = startB;
        }
        val += gl_result;
        resultList.push_back(gl_result);
        count++;
    }
    long long threadIterations = (testIterations - count) / NUMTHREADS;
    long long iterationsLeft = testIterations-count;
    thread* bonanzaThreads = new thread[NUMTHREADS];
    for( int i = 0; i < NUMTHREADS; i++ )
    {
        BonanzaThreadInfo* bonanzaThreadInfo = new BonanzaThreadInfo;
        if( i == (NUMTHREADS - 1) )
        {
            bonanzaThreadInfo->iterations = iterationsLeft;
        }
        else
        {
            iterationsLeft -= threadIterations;
            bonanzaThreadInfo->iterations = (threadIterations);
        }       
        bonanzaThreadInfo->resultList = resultList;
        bonanzaThreads[i] = thread(BonanzaTestThread,bonanzaThreadInfo);//http://stackoverflow.com/a/10662506/746754        
    }
    for( int i = 0; i < NUMTHREADS; i++ )
    {
        bonanzaThreads[i].join();
    }
    delete [] bonanzaThreads;
}

Turns out this took 574ms. Save up to 76%! Some basic notes about threads:-

• Complexity and room for error have dramatically increased.
• If there is any shared resource between threads, that resource will need to be protected by a mutex. If threads frequently require the same protected resource at the same time, all threads that require that resource will need to wait until it becomes available, which can result if performance is poor.

Here's a graph of our work so far:

Now edit multiple values.

multiple values

Well, as far as I know, if you have multiple input values ​​(a, b, c, d...), your ifstatements will become very nested and fast in length.if a < b && a < c && a < d...

Usually, we're trying to sort the next value, so that's where I would start. My first thought was to store the values ​​in some sort of ordered data structure. I chose to use sets because sets are naturally ordered by keys (actually, it's multi-set since we need to allow duplicates). Inside the collection, a structure is placed (called ValuesStruct because I'm not comfortable with the name ) that contains the value to increment (a,b,c) and the next integer that is closest to that value. The <operator is to let the STL know where to put this value in the set.

struct ValuesStruct
{
public:
    int Value;
    long long Next;
    ValuesStruct( int start )
    {
        Value = start;
        Next = start;
    }
    bool operator < (const ValuesStruct& rOther) const
    {
        return (Next < rOther.Next);
    }
private:
    ValuesStruct()
    {

    }
};

Then, all I have to do is iterate over the collection. On each iteration, the front of the collection will have the smallest next value. So I can calculate the current time interval by subtracting the current time interval. Then I just need a do..while()loop to remove the value from the list and add it back with the updated Next value so it will take its proper place in the collection. I need to do this for all values ​​that have this value Next(e.g. this is the case at 15 for the simple 3,5 example). I call it a test MultiConditionalTestbecause we need to check multiple comparison conditions, and because I have a bad name.

static void MultiConditionalTest( multiset<ValuesStruct>& values, unsigned long long testIterations )
{               
    unsigned long long prev = 0;
    for( unsigned long long i = 0; i < testIterations; i++ )
    {
        multiset<ValuesStruct>::iterator iter = values.begin();     
        gl_result = (*(iter)).Next - prev;
        prev = (*(iter)).Next;
        do //handle case where equal
        {
            ValuesStruct valuesStruct = *iter;
            values.erase(iter);
            valuesStruct.Next += valuesStruct.Value;
            values.insert( valuesStruct );
            iter = values.begin();
        }while( (*iter).Next == prev );
    }
}

The usage of this function is as follows:

multiset<ValuesStruct> values;
values.insert(ValuesStruct(3));
values.insert(ValuesStruct(5));
values.insert(ValuesStruct(7));
values.insert(ValuesStruct(11));
MultiConditionalTest( values, testIterations );

As you can see, there's a lot going on here, so I expected a performance boost: 105156ms - 50x slower. It's still less than a microsecond per iteration, so again it depends on your goals. Since I'm just bashing this evening without doing a lot of analysis, I'm pretty sure there are performance optimizations. First, the set is usually implemented as a binary search tree. I'll do some research and find out if this is the best data structure for this problem. Also, when inserting new values ​​in the list, hints can be given about where to place them. If we choose the location wisely, then we might be able to speed up the operation. And, as before, the sequence repeats when we reach (a*b*c*d...) so we can store the value and then write it out. I'll also look into the problem space to see if there's a way to optimize the algorithm, maybe ask the math sequences at math.stackexchange.com - those folks are pretty smart.

Anyway, it's just an option, and depending on your actual performance requirements, it might not work for you.

Some other ideas:

1. How likely are you to get the same set of values ​​(a,b,c,d...)? You may want to cache previous results if possible. Then just read them from the cached array, which is very fast.
2. Another way to improve performance is to turn on compiler optimizations. How you do this, and how effective it is, depends on your compiler.

good luck.