Processing 1.0 - Processing Discourse - ArrayCopy CircularBuffer ?!

We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.

‹ Previous Topic | Next Topic ›

Pages: 1

ArrayCopy CircularBuffer ?! (Read 1038 times)

jazz

ArrayCopy CircularBuffer ?!
Feb 24^th, 2010, 2:07am

Hi there, its me again with another question. Dont say i am not trying to solve the problems on my own using the board Wink

I have found a little piece of code by Cedric. He wrote a little loop that is greating a continouus grahph here : http://processing.org/discourse/yabb2/num_1258658941.html
as he mentioned it is a bit slow. Maybe it doenst matter in some cases but in my, i tested it. it slows down my programm by almost 80 frames.
They both mentioned some other ways like arrayCopy or Circular Buffer. What is this exactly and how does it work

Thank you!
Jazz

edit: oh the more important question is actually, how can i improve performance, not what is arraycopy etc. would be good to know, but if there are other ways. i am open for everything

Krzysztof Trzewiczek

Re: ArrayCopy CircularBuffer ?!
Reply #1 - Feb 24^th, 2010, 3:40am

I think that could help:

Quote:

int[] numbers = new int[400];
int beginning = 0;

void setup()
{
  size(400,400);
  smooth();
}

void draw()
{
  background(255);
  stroke(0);
  beginShape();

  for( int i = 0; i < numbers.length; ++i )
  {
    int realIndex = ( i + beginning ) % numbers.length;
    int xPosition = i % numbers.length;

    vertex( xPosition, 350 - numbers[ realIndex ] );
  }

  endShape();

}

void mouseMoved()
{

  numbers[ (beginning ) % numbers.length ] = mouseY;

  if( beginning < numbers.length )
    ++beginning;
  else
    beginning = 0;
}

The circular concept means that you override the values in the array instead of copying anything from one place to another. With circular concept what you change is the "beginning" of the array - where to start to read it. The amount of values is the same, so you just circularly override unused values and move "the beginning" forward. When reaches the end of the array, you go to its beginning and so on circularly.

The advise to use arrayCopy instead of manual copy comes from the reference as arrayCopy seems to be "the fastest possible" way to copy values from one array to another. If it's possible thou, better not to copy at all.

koogy

Re: ArrayCopy CircularBuffer ?!
Reply #2 - Feb 24^th, 2010, 4:16am

i always worry about the amount of divisions that all the % operations are introducing. maybe i shouldn't.

i'd be tempted to use a power of two and then use bitmasking (& 0xFF...) or something which will be quicker. or just do a comparison before the wrap - if (i > MAX){i = 0;} which looks remedial but will be quicker than a % generally.

koogy

Re: ArrayCopy CircularBuffer ?!
Reply #3 - Feb 24^th, 2010, 4:25am

ha, took 2 minutes to test:

Code:


public class Main {

    private static final int MAX = 10000000;
    private static final int MOD = 256;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
	  // TODO code application logic here

	  long start;

	  // mod
	  start = System.nanoTime();
	  int index = 0;
	  for (int i = 0 ; i < MAX ; i++) {
		index = (index + 1) % MOD;
	  }
	  System.out.println("Elapsed1: " + (System.nanoTime() - start));

	  // bitmask
	  start = System.nanoTime();
	  index = 0;
	  for (int i = 0 ; i < MAX ; i++) {
		index = (index + 1) & 0xFF;
	  }
	  System.out.println("Elapsed2: " + (System.nanoTime() - start));

	  // compare
	  start = System.nanoTime();
	  index = 0;
	  for (int i = 0 ; i < MAX ; i++) {
		index++;
		if (index > MOD) {
		    index = 0;
		}
	  }
	  System.out.println("Elapsed3: " + (System.nanoTime() - start));
    }
}

so 10M loops, with counter changing modulo 256

results here:
Elapsed1: 26392678 (modulo 100%)
Elapsed2: 17154477 (bitmask 65%)
Elapsed3: 25672393 (condition 97%)

Krzysztof Trzewiczek YaBB Newbies Offline Posts: 13 Kraków, Poland	Re: ArrayCopy CircularBuffer ?! Reply #4 - Feb 24^th, 2010, 4:27am I'm not good at bit operations (thou I know they're powerful!), so actually I don't get the powering and bit-masking method. Would you explain it a bit? It sounds interesting!! Thx in advance!!

jazz Ex Member	Re: ArrayCopy CircularBuffer ?! Reply #5 - Feb 24^th, 2010, 4:33am aeh yes, i dont get it either.... so what is the fastest method now. because testing the one Krzysztof Trzewiczek suggested, didnt change the frameRate in my sketch.

koogy

Re: ArrayCopy CircularBuffer ?!
Reply #6 - Feb 24^th, 2010, 5:15am

oh, it's still doing the circular buffer thing, it's just the way you wrap around the ends of the buffer that i'm talking about, the % that Krzysztof was using.

you have to think about the binary representation of the numbers to understand the bitmasking and it only works with numbers on bit boundaries, ie 2, 4, 8, 16, 32, 64... 256, 512, 1024, 2048...

so, taking 8 as your boundary and using 8 bit representations

0 = 00000000
1 = 00000001
2 = 00000010
3 = 00000011
...
7 = 00000111
8 = 00001000
9 = 00001001

and ANDing (&) with a bitmask means that all the bits that aren't both 1s in the two operators are replaced with 0

so 3 & 0x7 =
3 = 00000011
7 = 00000111
& = 00000011 = 3

and 10 & 0x7 =
Code:


10 = 00001010
 7 = 00000111
 & = 00000010 = 2

effectively doing %8 without an expensive division. ints are 32 bit in java. this also works going backwards whereas % gives you -ve remainders which won't work as indexes.

some links:
http://en.wikipedia.org/wiki/Bitwise_operation#AND
http://www.darklump.co.uk/blog/?p=295

koogy

Re: ArrayCopy CircularBuffer ?!
Reply #7 - Feb 24^th, 2010, 5:18am

it's probably not worth worrying about if the circular buffer thing didn't help (which is a surprise, perhaps arraycopy() is doing something similar or the data isn't big enough to warrant such optimisations). it's probably a tiny fraction of the time that everything else takes but, y'know, the computer scientist in me always looks for efficiency. 8)

Krzysztof Trzewiczek

Re: ArrayCopy CircularBuffer ?!
Reply #8 - Feb 24^th, 2010, 7:23am

first of all: thanx!! i'm a self-taught programmer, so bit-operations are a little scarry for me. i know how it works with color and how it works in general, but using it easily is a problem always (it's like recursion - another monster!).

and then: it's funny that from the very beginning i heard all the time - efficiency, optimization and so on. and finaly 90% of times it turned out that it's true for example for loops bigger than let say 100 000 iterations. and i spent a lot of time doing some voodoo programing dances just to "optimize" for loop with 1000 iterations, because i thought that 1000 points is A LOT!! Grin

I don't care recently about that up till the moment i work with live cam or I know my has to run on old machines - then i even try to use bit-operations... Wink

thx anyway!

davbol

Re: ArrayCopy CircularBuffer ?!
Reply #9 - Feb 24^th, 2010, 7:56am

fwiw, often the simplest way is best, and you can implement a circular buffer simply by looping twice - once from pointer-to-end, then again from start-to-pointer. If the pointer exactly equals 0 or n-1 then one of the loops won't do anything, but all it "costs" is one conditional test outside the loop, and avoids the need to wrap the index (with % or & or if) inside the loop. For example:

Code:


  int n = numbers.length;
  int xPosition = 0;
  for (int i=beginning; i<n; i++)
	vertex(xPosition++, 350-numbers[i]);
  for (int i=0; i<beginning; i++)
	vertex(xPosition++, 350-numbers[i]);

TfGuy44 Full Member Offline Posts: 209	Re: ArrayCopy CircularBuffer ?! Reply #10 - Feb 24^th, 2010, 7:59am That's really neat, davbol.

Krzysztof Trzewiczek YaBB Newbies Offline Posts: 13 Kraków, Poland	Re: ArrayCopy CircularBuffer ?! Reply #11 - Feb 24^th, 2010, 8:16am Yeah, ROCKS !!!

Pages: 1

‹ Previous Topic | Next Topic ›