Uncategorized

Modulo based counters

Sometimes we need counters that wrap around at certain intervals ex:

1,2,3,1,2,3,1,2,3


One way of doing this would be to increment our ‘counter’ and then reset it when it reaches our number

int N = 3;
int counter = 0;
if (counter == N){
  counter = 0;
}
counter++;

But there are also couple other ways this same could be achieved.

Modulus

Using modulus operator ‘%’ we can divide the counter and get our wrapped value, where N is the value we will wrap at.

counter = (counter+1) % N;

Binary AND

This is almost this same approach as modulus but we are ‘AND’ing the counter with a power of 2. ex 1, 2, 4, 8, 16 … 2^n . Only problem here is that we have to AND with a power of 2.

counter = (counter+1) & 0x1;

produces 0,1,0,1,0,1

Test program

/**
 * Test program  for testing Modulus, Binary AND increments
 * @author greg
 *
 */
public class ModulePowerCounter {
 
	private static final int MAX_LOOP = 100000000;
	private static final int N = 2;
	private static final int POWER_OF_2 = 0x1;
 
	public static void main(String[] args) {
		long modTime = modulo();
		long counterTime = counter();
		long po2Time = powerOf2();		
 
		System.out.println(String.format("modTime = %s", modTime));
		System.out.println(String.format("counterTime = %s", counterTime));
		System.out.println(String.format("po2Time = %s", po2Time));
	}
 
	private static long powerOf2(){
		long start = System.currentTimeMillis();
		int counter = 0;
		for (int i = 0; i < MAX_LOOP; i++) {
			counter = (counter+1) & POWER_OF_2;
		}				
		return System.currentTimeMillis() - start;
	}
 
	private static long modulo(){
		long start = System.currentTimeMillis();
		int counter = 0;
		for (int i = 0; i < MAX_LOOP; i++) {
			counter = (counter+1) % N;
		}				
		return System.currentTimeMillis() - start;
	}
 
	private static long counter(){
		long start = System.currentTimeMillis();
		int counter = 0;
		for (int i = 0; i < MAX_LOOP; i++) {
			if(counter == N)counter = 0;
			counter++;
		}				
		return System.currentTimeMillis() - start;
	}
}

Performance

This is the fun part, so we have 3 different ways to achieve same thing but how do they perform.

Lets think about it, division is much more expensive than ‘addition and test’ which is more expensive than binary manipulation, our test program confirms our assumption.

modTime = 1258
counterTime = 449
po2Time = 108

As we see Power of 2 outperforms other methods by far, but its only for powers of 2, also our plain counter is almost 2.5 times faster than modulus as well. So why would we like to use modulus increments at all? Well in my opinion I think they provide a clean code and if used properly they are a great tool to know of.

Leave a Reply

Your email address will not be published. Required fields are marked *

* Copy This Password *

* Type Or Paste Password Here *