Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (133)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Vector looping  (Read 7175 times)
0 Members and 1 Guest are viewing this topic.
Offline retrosoft

Senior Newbie




oh, just work....,


« Posted 2002-12-08 23:02:15 »

Hi people,

I have a vector with about 10,000 objects in it that I need to iterate through on each frame of game loop, now the million dollar question is what is the fastest way to do this?

At the moment im using

Enumeration enum = land.elements();
        while (enum.hasMoreElements())
          Things element = (Things)enum.nextElement();

Would it be faster to use a different way?

And I heard that putting it all in a
try
    {}
     catch (ArrayIndexOutOfBoundsException aioobe) {}

could speed things up , any truth to that?

Thanks for all your help in advance :)

public void myGame extends www.retrosoft.co.uk
Offline princec

« JGO Spiffy Duke »


Medals: 436
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #1 - Posted 2002-12-08 23:16:23 »

The fastest most readable way is this:

1  
2  
3  
4  
5  
int n = land.getSize();
for (int i = 0; i < n; i ++) {
 Things thing = (Things) land.elementAt(i);
 //...
}


Cas Smiley

Offline cknoll

Junior Devvie




Flame On!


« Reply #2 - Posted 2002-12-09 00:03:19 »

Hey,
 If you need to iterate through them, you need to iterate through them, but is there a way to trim down that number?  Also, maybe if you could store those objects in an array of the object's type, you will avoid the casting overhead.

-Chris
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline leknor

Junior Devvie




ROCK!!!


« Reply #3 - Posted 2002-12-09 01:15:43 »

If you can use Java 1.2 or better you could use java.util.ArrayList which isn't synchronized. You'll have to use an Iterator instead of an Emumeration but that's not a big deal.

Or you could use the toArray() method to get access to all elements with out the synchronized overhead. eg:
1  
2  
3  
4  
5  
Things[] elements = {}; // empty, non-null array
elements = (Things[])land.toArray(elements);
for (int i=0; i < elements.length; i++) {
// do something
}

The Vector.toArray(Object[]) method will preserve the type of array when it grows it so you shouldn't have to do any casting.

I don't know if the above ideas are actually faster in a meaningful way. You'll have to test and see.
Offline rsk

Senior Newbie




I love YaBB 1G - SP1!


« Reply #4 - Posted 2002-12-09 11:35:29 »

I agree with princec, casting, as I've found with 1.4.1 under Windows costs near nothing.

I tried comparing the casting of 2million strings to not casting (accessing them in a for loop) and the time difference was like 23ms (on a 2.8ghz P4). Granted its a fast machine, but if the difference is 23ms after 2 million objects I figure that's a good "idea" of what it is.

Note: I ran these comparisons 15 times each and averages the times.

Also my co worker mentioned that casting is more expensive for "deeper" objects (something that extends many levels) so I tried casting 500k JButtons as compared to 500k Objects, same thing, almost no difference...

NOTE: J<anything> are EXPENSIVE, more expensive that I had realized... I was running out of memory like crazy with these tests.

Also as you mentioned you are accessing this collection every frame, I would stop creating the enumeration each time, you know how many items are in the collection, just go through them by index, caching the size as prince suggested to avoid the method call each time to check it.

Also, assuming you were taking these suggestions literally (as to have them in your rendering loop) don't put a toArray into the loop. You'll kick performance right in the nuts (I realize the author didn't mean for you to, I'm just clarifying incase).

But taking Leknor's suggestion, assuming you can do it, and having your "toArray" outside of the rendering loop, and converting it once, yea that would be the fastest since you don't need any casting... but I'm assuming your "land objects" is probably changing all the time, so this might not be a good idea as you'll need to toArray a lot.
Offline zparticle

Senior Devvie




Thick As A Brick


« Reply #5 - Posted 2002-12-09 13:15:07 »

just curious did you actuall create 2 million different strings or did you cast the same one 2 million times?

Offline rsk

Senior Newbie




I love YaBB 1G - SP1!


« Reply #6 - Posted 2002-12-09 13:23:43 »

method
{

//create array
//fill array with 2million diff strings
//enter outside loop, do 15 times
//start timer
//do inside loop, casting/accessing strings
//add time diff to running total
//done 15 times
//get time average


//do same thing, except don't cast, just use as object.
}

was that what you wanted?
Offline zparticle

Senior Devvie




Thick As A Brick


« Reply #7 - Posted 2002-12-09 15:12:37 »

yeah I was just thinking that if you had used the same string then the VM could possibly have optimized things out.

Offline retrosoft

Senior Newbie




oh, just work....,


« Reply #8 - Posted 2002-12-09 17:45:31 »

Hi again, thanks for all your input, I thought I should try to explain what im trying to do with the collection so you can suggest if im going about it in a sensible manner

If you have a look at www.retrosoft.co.uk and go on the menu to fun->project water

I want to use a Vector so that when the water flows to the bottom of the screen it can be removed from the collection, ie the collection is going to be changing dynamically all the time (it doesn&#8217;t do this yet)

Also the collection elements are a class that holds the position of the element and holds its methods for updating its state. Would it be more sensible to have an updater class?

The reason I have it this way is so I only have to run through the loop once to update and draw.

public void myGame extends www.retrosoft.co.uk
Offline princec

« JGO Spiffy Duke »


Medals: 436
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #9 - Posted 2002-12-10 10:00:24 »

Removal from a collection can be arbitrarily slow (ie. linear time) unless you get more specialised.

Swapping the tail with the element you want do delete and decrementing the size by one is one of the fastest ways to remove an element from a list but it breaks any ordering you might have already imposed on the list.

Just a thought.

Perhaps a better alternative, which will cost you about 80k of RAM in this case, is to use a doubly-linked list which offers very fast insertion and removal but without indexes. And indeed very fast iteration.

Cas Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline rsk

Senior Newbie




I love YaBB 1G - SP1!


« Reply #10 - Posted 2002-12-10 11:10:08 »

good point prince...

yea if you don't care about ordering, what prince suggested is the best idea, but you could probably cut that memory requirement down by using singly linked, and just keeping a permanent link to the first node (which is a dummy node), and the node before the last node.... so to remove you just do:

secondToLastNode.next = null;

to insert you pull a:

insertedNode.next = dummyNode.next;
dummyNode.next = insertedNode;

This helps you save memory on the double linking, but it does suck more to work with. if you can spare the extra mem, double linked is sexy.

If ordering DOES matter, then you really have to go back to ground zero Sad
Offline cknoll

Junior Devvie




Flame On!


« Reply #11 - Posted 2002-12-10 12:07:17 »

What about a circular array to handle the collection?  You can even preallocate objects ahead of time...say you have an aray of 1000 droplets like so:

1  
2  
3  
4  
5  
int ARRAY_SIZE = 1000;
Droplet droplets[]  = new Droplet[ARRAY_SIZE ]
int startindex = 0
int endindex = 0
// prefill the array, or create objects on the fly.


To insert an object, just increment endIndex % ARRAY_SIZE and make sure you don't increment onto startIndex.  This gives you ordering, fast index, and after your array is filled up, you can reuse the objects outside of the index range...for example if at somepoint in your code you have 600 droplets in your code, and then you need to remove a droplet and add a droplet in an iteration, your start and end index will increment to 1 and 601...2 and 602...etc (provided you have 600 droplets on the screen right now, but you are always loosing 1 and gaining one each frame...eventually you will get to the point where your start index is 900 and your end index is 499...it keeps cycling!  And instead of maing new objects, when you insert, you can check to see if you already created a droplet in the new endIndex position, and if so, reset the value instead of re-creating the object.  It's like object pooling!  Does this make sense? And empty list is when startIndex = endIndex.  Your list is full when endIndex + 1 % ARRAY_SIZE = startIndex.

I also realized that if you use soft referenes, you can allocate a HUGE array and as memory is needed the soft references will be collected.  Deletion means that you swap a strong reference with a weak one in the array in addition to incrementing start index.  Hmm, interesting, total theory tho, not sure how it would perform.


Oh oh oh! I forgot to say what happens when you run out of room but you need to have more objects in the collection.  Well, after thinking about it a little bit, you can recreate a collection array at the new size (Say, increment by ARRAY_SIZE) and use ArrayCopy to copy the segments of the array to the new array collection, and reset the start/end indexes if necessary.  This is only complicated when the start index is physically after the end index (the list overlapps) because in this case you need to copy the beginningof the array to the middle of the new array...so if you have the following:

startIndex = 900
end index = 200

You create your new array holder

Droplet newArray[] = new Droplet[droplets.size + ARRAY_SIZE]

and then you do the array copy copying the contents from endIndex + 1 to droplets.size():

1  
2  
3  
System.arraycopy(droplets,  endIndex + 1, newArray, 0, droplets.size - endIndex + 1);
System.arraycopy(droplets, 0, newArray, droplets.size - endIndex + 1, endIndex);
endIndex = droplets.size;


And you only need to do this when endIndex < startIndex, otherwise it's a straightforward array copy from the old array to the new array.

-Chris

Offline rsk

Senior Newbie




I love YaBB 1G - SP1!


« Reply #12 - Posted 2002-12-10 12:19:09 »

hmmm interesting suggestion... I don't know if that would work for this situation as he has an ever growing amount of droplets it seems (they stay at the bottom of the screen)...

For a constant number of ever changing items though, this seems to be a fantastic idea in that it avoids the arraycopy to move everything down one element when a new item arrives...

visually in my head, I imagine a frontIndex pointer, and an endIndex pointer, chasing eachother backwards around in a circle (assuming he ads to the front). Although I think the end result is the same as the linked list, less memory though... more computation and bounds double checking though....

I would be interested to see how this worked in a good implementation... the worst case scenarios being if they insert more objects and you just have to grow the array stays the same though...

hmm I'll go think about this.
Offline cknoll

Junior Devvie




Flame On!


« Reply #13 - Posted 2002-12-10 12:28:25 »

Hi, I added to my post instead of making a reply (i just noticed you replied) so please re-read that to see if it addresses your points.  As far as having no upper bound on how many droplets you have, maybe you should reconsider that, as you _will_ be having limited amounts of resources on the computer....if you are going to allow 10,000 dots, then so be it, if you hae a screen of 800x600 and the worst case scenerio is that you have a full screen of droplets, that's 480,000 droplets.  That's HUGE, to be sure, but if you use soft references then the objects will be cleanred out as memory is needed, and you'll just need to re-create them as you walk through the list.  I don't know how much ram 480,000 references uses, but if cas says 10,000 is 80k, then 480,000 is 3,840k or 3.8 MB.  Not bad considering all the data you are storing...and if you make them strong references, you won't experience garbage collection delays because there's no garbage to be collected.

-Chris
Offline cknoll

Junior Devvie




Flame On!


« Reply #14 - Posted 2002-12-10 12:32:04 »

Hi, Me again,  I just wanted to ask: You aren't drawing each one of those blue pixels individually are you?  I think you would get much faster performance if you made a memoryimageSource out of it and just set pixel colors of each pixel and then drawing teh backbuffer as opposed to individual drawLine()s (if that is what you are doing, I don't know).

-Chris
Offline rsk

Senior Newbie




I love YaBB 1G - SP1!


« Reply #15 - Posted 2002-12-10 12:43:24 »

Chris

The arraycopy is the "worst case" I was referring to, in that we can't avoid it. BUT your solution has a nice elegance to it, thanks for the suggestion (I'm not writing this water applet, just like the conversation)

As far as different reference types... I've never used them... i think I'm missing a huge optimization oportunity from what it sounds like (avoiding GC, using easily collected items, etc...) very cool!
Offline cknoll

Junior Devvie




Flame On!


« Reply #16 - Posted 2002-12-10 12:48:14 »

Ok, well the array copy in my example only happens when you need the circular array to grow... you can always initialize it to a max value and when it's full, you can't create more 'water' until you expire some of the droplets in the list (which could be complicated, because I don't know if you can guaruntee that the first one in will always die before the second one, such as in the case that a spot of water gets collected in a user drawn cup, and then you poke a hole in it on the other side, and suddenly droplets that have been created last are going to die first).

Maybe a DLL is better, or maybe a combo of the two. But whatever you decide, have fun doing it (even if you're just having pleasant conversation (hehe, sorry didn't read all of your post about you aren't writing the applet) Smiley

-Chris
Offline retrosoft

Senior Newbie




oh, just work....,


« Reply #17 - Posted 2002-12-10 13:00:04 »

wow great info people, btw my names Dave for reference. Yes I thought using a Vector was perhaps not the most efficient means of trying to do what I wanted to do.

Im going to have a look at implementing cknolls idea for the collection at the weekend. (to be honest I didnt expect such a quick response, and ive got to get my interim report finished for my dissertation by Thursday, then Ill have some time).

At the moment the paint systems works by having 2 offscreen images one for the back buffer and one to hold the drawn picture. In the rendering loop the drawn picture is used to erase the backbuffer and then the droplets are drawn with drawRect (as they are 4 pix each) on to backbuffer.

I don&#8217;t quite get what you mean cknoll with the memoryimageSource could you explane how that can speed things up.

The end applets going to be a lot of fun as im going to put some momentum in the water and tiny little surfers that can surf down the courses that you have drawn : )

public void myGame extends www.retrosoft.co.uk
Offline rsk

Senior Newbie




I love YaBB 1G - SP1!


« Reply #18 - Posted 2002-12-10 13:00:27 »

haha after all this pleasent conversation I want to go implement my own water applet! Smiley
Offline rsk

Senior Newbie




I love YaBB 1G - SP1!


« Reply #19 - Posted 2002-12-10 13:12:11 »

dave

that sounds really slick! I like it already, but if I can torture surfers that's gonna be great.

a memory image source is a class (MemoryImageSource I think) that stores a 2D int array representing pixel data... each pixel (x/y coord) can have a RGB value that you can get from java.awt.Color (Color.white.getRGB() for example) or make yourself. The javadoc decribes which bits define which color.

Anyway, he was suggesting that you actually manipulate the pixel color data, and then draw the memory image source (I think).

Also you can use a BufferedImage, where you can set the pixel data any time you want... so you could have a blue dot move around the screen by setting the x/y/RGB values for different pixels, then repainting the BufferedImage.


I'm skipping over performance here and also want to note that I think I confused the functionality of BufferedImage and MemoryImageSource... Buffered seems more friendly to mutability while Memory seems more tuned for creating and using. But I'm fairly new to this, so YMMV.
Offline cknoll

Junior Devvie




Flame On!


« Reply #20 - Posted 2002-12-10 13:21:06 »

Hi,

Re: MemoryImageSource

Basically, you can represent an image by an array of ints, and so instead of drawing rects over and over (which could be slow, and prone to garbage creation) you can directly modify the integer in the array to set the appropriate color (either black or blue).  When you are done going through the array, you signal the image that the image has been changed, and then you can draw it to the screen.  Check out the API docs on MemoryImage source but here's a little code snipit that gets an image of a car and makes it semi-transparent by changing the alpha bit of the int of the pixel and then creating an image out of that array.

image contains the opaque image of the car.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
      // load up transparent image for the car
      int[] pixels = new int[image.getWidth() * image.getHeight()];
      PixelGrabber pg = new PixelGrabber(image, 0, 0, image.getWidth(), image.getHeight(), pixels, 0, image.getWidth());
      try
      {
        pg.grabPixels();
      }
      catch(InterruptedException e)
      {}

      for(int ctr = 0; ctr < pixels.length; ctr++)
      {
        int alpha = (pixels[ctr] >> 24) & 0xff;
        if (alpha != 0)
        {
          // set this pixels transparancy to 25%
          pixels[ctr] =  0x4F000000 | (pixels[ctr] & 0x00FFFFFF);
        }
      }
      carTransImages[i] = Toolkit.getDefaultToolkit().createImage(
        new MemoryImageSource(image.getWidth(),image.getHeight(),pixels,0,image.getWidth()));
    }


Now, don't quote me, but I think that if you create an image from a MemoryImageSource, the array of integers is the actual data of the image, so modifying the array will actually modify the image.  This, obviosuly is a very non-OO way to manipulate images, but the whole theme behind the water applet seems to fit very nicely into this model.

-Chris
Offline rsk

Senior Newbie




I love YaBB 1G - SP1!


« Reply #21 - Posted 2002-12-10 13:23:05 »

Chris's explination is much better than mine, listen to him Smiley

Chris,

I was wondering that exact thing about manipulating the int array instead of using the new* methods... if this is the case, and changing the array changes the source, that is gonna be slick as hell for performance minded programming that needs that functionality...

Can anyone verify/deny this?
Offline cknoll

Junior Devvie




Flame On!


« Reply #22 - Posted 2002-12-10 13:28:53 »

I did do a performance comparision between drawing an image and doing an arraycopy of a block of pixels and saw virtually no difference  when in the case of where the image was the same size as the drawing surface (maybe under the covers there is a check to see if the geometry of the image is the same as the drawing surface, it does a straight memory copy).  I kinda stopped there (I'm a lazy bastard) because when drawing a smaller image to a larger surface, you aren't writing a continuous line of arrays anymore, you have to do one array copy per row of the smaller image to the proper offset of the drawing surface (this is a bit unclear, I know, but i'm sorry).  Stick with drawImage when the image and the drawing surface is compatable....I think it does exactly what you would do if you modified the image source by hand.  In the case of this water applet, however, if 1 droplet is exactly 1 pixel, then you save yourself the overhead of a drawRect or DrawLine or FillRect and instead just do a single integer assignment (this, I would argue would be much faster).

-Chris
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #23 - Posted 2002-12-13 13:54:54 »

Be very careful with speeding up iteration - as someone else has pointed out, the best performance boost will most likely come from using different data-structures, and different algorithms - but there are some pitfalls here. The rest of this explains the problems and gotchas. Although it appears not to be directly relevant to the original poster's situation, anyone trying to use the suggestions in their oen programs might benefit from reading it :). PS I'm sure those providing suggestions realise the dangers, but I know there's plenty of people reading this who won't.

The suggestion to iterate with for() from i=0 to i=Vector.size() is *really* dangerous. The suggestion to take the array-form of the Vector with Vector.toArray() is not so dangerous, but both will often give you very unexpected, very hard to track down bugs (unless you appreciate what you're doing). The iterator() system isn't only there to provide compatibility with the Collection interface, nor just to look pretty.

If you read the start of the Vector (and many other Collections classes) API javadocs, you'll find a paragraph mentioning that "the iterator provided is fail-fast" with an explanation of what that means.

In the first example (the really dangerous one), the size of the Vector can change WHILST you are in the middle of your for loop. If it increases in size, you will not get ALL of the elements (and, depending on the implementation of the Vector, you may end up doing some - or even many - elements twice, or even more times! This is one of those very confusing bugs). If it decreases, you'll be accessing items outside the size of the Vector. This is most likely why you heard the suggestion "wrap it in a try{ }catch( ArrayIndexOutOfBoundsException" - to prevent crashes in the case where the Vector shrinks. Note, this still provides  NO PROTECTION AT ALL if the Vector grows.

In the second example, we can guarantee that the array will NOT change in size or contents. However, if it takes a significant time to iterate over that array (unlikely, but I've seen cases where it happens, e.g. when the array contains Sockets, and the for() loop is sending a message on each), then you may find your app appears to "ignore" things once they've been added to the Vector.

malloc will be first against the wall when the revolution comes...
Offline rsk

Senior Newbie




I love YaBB 1G - SP1!


« Reply #24 - Posted 2002-12-13 14:03:54 »

blahh bllahh, I appreciate the post... those are important points to consider...
Offline swpalmer

JGO Coder


Exp: 12 years


Where's the Kaboom?


« Reply #25 - Posted 2002-12-13 16:48:56 »

My water applet...
http://www.cfxweb.net/java.php?op=contest&num=3rd&entry=marvin

(source code is there somewhere too)

Offline cknoll

Junior Devvie




Flame On!


« Reply #26 - Posted 2002-12-13 18:23:52 »

Nice job, very smoothe, no jerks. You handle memory allocation very well. Smiley

-Chris
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Mr.CodeIt (10 views)
2014-12-23 03:34:11

rwatson462 (38 views)
2014-12-15 09:26:44

Mr.CodeIt (31 views)
2014-12-14 19:50:38

BurntPizza (62 views)
2014-12-09 22:41:13

BurntPizza (99 views)
2014-12-08 04:46:31

JscottyBieshaar (60 views)
2014-12-05 12:39:02

SHC (74 views)
2014-12-03 16:27:13

CopyableCougar4 (77 views)
2014-11-29 21:32:03

toopeicgaming1999 (138 views)
2014-11-26 15:22:04

toopeicgaming1999 (127 views)
2014-11-26 15:20:36
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!