Round robin algorithm in a loop

Question

How round-robin algorithm can be implemented that runs in a loop for ever?

for (int i = 0; ;i++){
    roundRobinIndex = i % numberOfWorkers;
}

The problems with the way above is that integer overflow problem. It can also be implemented with checking the value of i:

for (int i = 0; ;i++){
    roundRobinIndex = i % numberOfWorkers;
    if i == maxNumber{
        i = 0;
    }
}

But this way seems ugly. Maybe there is more elegant way?

"ugly" is a very subjective notion :) what's ugly here, to me, is that we're using a modulo call, which is expensive. — Olivier Sohn, Jul 06 '18 at 14:09
@OlivierSohn What do you replace the `%` operation with? In the past I have tried various tricks to avoid the "expensive" call but nothing I did was better for variable inputs. To be clear, not trolling looking to learn. — Matt, Jul 06 '18 at 14:16
@Matt Don't worry about these micro-optimizations unless you can prove that they matter. This is premature optimization, and it is may be that your compiler generates better code for modulo than you could come up with yourself (e.g. if the number of workers is a compile time constant). — Max Langhof, Jul 06 '18 at 14:19
Do you need both the `i` and `roundRobinIndex` variables or just the latter? — Bob__, Jul 06 '18 at 16:03

Thibault D. · Accepted Answer · 2018-07-06T13:55:01.577

3

Why not ?

int numberOfWorkers = 10
int roundRobinIndex = numberOfWorkers - 1
while(true){
    roundRobinIndex = (roundRobinIndex + 1) % numberOfWorkers
}

or with a for-loop

for (int i = 0; ;i = (i + 1) % numberOfWorkers){
    roundRobinIndex = i;
}

We can now get rid of i

edited Jul 06 '18 at 13:55

answered Jul 06 '18 at 13:44

Thibault D.

1,567
10
23

It may be premature optimization, but you can also just write `i++; if (i == numberOfWorkers) i = 0;` or some variation. Most compilers will likely do this transformation for you instead of a more costly modulus operation but it's just as short. – Max Langhof Jul 06 '18 at 13:58
Indeed, it depend on what we aim to do, I suspected OP wanted some elegant code, not the most effective – Thibault D. Jul 06 '18 at 14:05
BTW, [the infinite loop is UB without "visible" effects](https://stackoverflow.com/a/5905171/2684539). – Jarod42 Jul 06 '18 at 15:04

Olivier Sohn · Answer 2 · 2018-07-06T15:02:22.203

3

Avoiding any modulo call, we can do:

constexpr int nextRR(int curIdx, int sz) {
    if(curIdx==sz-1) {
        return 0;
    }
    return curIdx+1;
}

for (int rrIndex = 0;;rrIndex = nextRR(rrIndex, sz)) {
    // use rrIndex here ...

}

This will be performance-wise more effective than any modulo-based solution, if the number of workers is not known at compile time.

Note that nextRR can also be written like this, to optimize even further for platforms where comparison with 0 is faster than a comparison with a variable:

constexpr int nextRR(int curIdx, int sz) {        
    if(curIdx==0) {
        return sz-1;
    }
    return curIdx-1;
}

edited Jul 06 '18 at 15:02

answered Jul 06 '18 at 14:02

Olivier Sohn

1,292
8
18

This is 1. rejected in the question itself and 2. not guaranteed to be faster (even ignoring the fact that your compiler will probably optimize all the mentioned solutions to the same machine code). – Max Langhof Jul 06 '18 at 14:06
@MaxLanghof please show me a compiler that does that :) and I disagree with you first point too, as said in the comment : "ugly" is a subjective notion... – Olivier Sohn Jul 06 '18 at 14:07
For example, if your max index is a compile time constant, your compiler may replace the modulo by something much faster (like `and` for powers of two) which can easily beat branching (or conditional moves). See [here](https://godbolt.org/g/sQMbeF). I couldn't immediately get it to transform both into the same, but your universal performance claim is simply false. – Max Langhof Jul 06 '18 at 14:16
@MaxLanghof yes, "if" it is a compile time constant. But it's not the case here... – Olivier Sohn Jul 06 '18 at 14:18
2

I dislike the name you gave to your function and variables, but I agree: an `if(overflow) { reset; }`is easier to read (you get it at first glance) than modulo arithmetic. Finally, I don't care about performance at that level except if I did a profile first. +1 anyway – YSC Jul 06 '18 at 14:18
@YSC I changed the variable name, hope you like it better :) I profiled similar alternatives on an earlier project and saw that the non-modulo option was faster – Olivier Sohn Jul 06 '18 at 14:23
@OlivierSohn It is unspecified whether this is a compile-time constant, which means your statement is not generally true. I've also seen modulo transformed into simple conditional code (for constant modulus) in my own code. – Max Langhof Jul 06 '18 at 14:27
@MaxLanghof it's not specified in the question that it's a constant. But I agree with you, compilers do smart things when they have info a compile time. – Olivier Sohn Jul 06 '18 at 14:30
@MaxLanghof I'm glad you like it now :) – Olivier Sohn Jul 06 '18 at 14:42
Why are you checking `curIdx==sz-1` instead of, say `return curIdx < sx ? curIdx + 1 : 0;`? – Bob__ Jul 06 '18 at 14:45
@Bob__ Because your condition is incorrect. If `curIdx` is not smaller than `sx`, you are already out of range. You either need to increment beforehand (see my comment [here](https://stackoverflow.com/a/51211812/9528746)) or twice if you don't want the check with `-1`. Or do something unreadable like `++curIdx < sx ? curIdx : 0`. – Max Langhof Jul 06 '18 at 14:53
@Bob__ I agree that testing using an inequality may be more robust, in case `sz` changes. Then it would be `return curIdx < sz-1 ? curIdx+1 : 0`. – Olivier Sohn Jul 06 '18 at 15:11
@Bob__: [Your code](https://godbolt.org/g/MQgU5g) is UB btw. infinite loop without needed operation. – Jarod42 Jul 06 '18 at 15:12
@Jarod42 I think you meant to comment on an other answer, as the code in the link and my code don't match. Can you move your comment please? – Olivier Sohn Jul 06 '18 at 15:15
@OlivierSohn: code matches (first) comment of Bob (that's why I notified Bob and not you). – Jarod42 Jul 06 '18 at 15:18
@Jarod42 yeah, since C++11, right? The point was showing that compilers can make drastic choices and OP's code hasn't side effects too. – Bob__ Jul 06 '18 at 15:18
@Bob__: I think it is worded differently before but with same effect. – Jarod42 Jul 06 '18 at 15:27

score 0 · Answer 3 · answered Jul 06 '18 at 13:59

0

For completeness (I agree that pLopeGG's answer is more elegant) - your way would work perfectly well if you make i an unsigned int rather than int since the overflow is defined in the standard for unsigned overflows, but not signed.

ie

for (unsigned int i = 0; ;i++){
    roundRobinIndex = i % numberOfWorkers;
}

answered Jul 06 '18 at 13:59

UKMonkey

6,941
3
21
30

2

This is (in theory) problematic if your number of workers is not a power of two. Note that this is the [same reason](https://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator) why you may get bias with mapping a random integer into your desired range. – Max Langhof Jul 06 '18 at 14:02
@MaxLanghof an error of 1 every 4,294,967,295 isn't a strong enough bais to be worth worrying about. – UKMonkey Jul 06 '18 at 14:06
1

If the code depends on round-robin indices actually proceeding in round-robin fashion and not restarting from 0 randomly, it very much is worth worrying about. – Max Langhof Jul 06 '18 at 14:06
@MaxLanghof don't disagree - I also don't think OP cares since they suggest that algorithm in the question - which is why I posted the version that didn't result in UB. – UKMonkey Jul 06 '18 at 14:09

score -1 · Answer 4 · answered Jul 06 '18 at 14:17

-1

Why not put the % into the loop?

for (int i = 0; ;++i, i %= numberOfWorkers)
{
}

answered Jul 06 '18 at 14:17

Caleth

52,200
2
44
75

1

...why not just `i = (i+1) % numberOfWorkers`? – Max Langhof Jul 06 '18 at 14:19
3

Nobody likes that poor, lonely coma operator :( – YSC Jul 06 '18 at 14:20

Round robin algorithm in a loop

4 Answers4