Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (577)
games submitted by our members
Games in WIP (498)
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  
  Coordinates representation: vectors vs int,int  (Read 1813 times)
0 Members and 1 Guest are viewing this topic.
Offline DooM77

Junior Newbie





« Posted 2009-03-03 23:01:02 »

The need of processing some form of coordinates (tile coordinates, pixel coordinates and so on) is very common in game developing. My post is about comparing the papproach of using vector object (for example 2-dimensional vectors) with approach of using pairs of int (for example x,y) in every place we need to process coordinates.

1  
2  
3  
4  
5  
6  
7  
8  
9  
//Vector version
public Tile getTile(Vector2 coords){
      return tiles[coords.getX()][coords.getY()];
}

//Pair of ints version
public Tile getTile(int tx,int ty){
   return tiles[coords.getX()][coords.getY()];
}


Here are my recent experiences with vectors. At some point I realized that most of my methods is having two overweighted versions: one taking vector parameters and second taking int,int parameters to express coordinates (like in example above).The rest of them are having only vector or ints version what is even worse because I have to remember all the time whether method 'fun` that I want to use is accepting vector or pair of ints as parameters. It was too big mess for me so I decided that I will unify the whole system and all my methods operating on coordinates will be using only vectors. After doing so, I realized that now a big number of Vector objects is being created so I added a lot of vector-specific methods in Vector class and implemented some decent vector pooling system - now the vectors are being reused so much less Vector objects has to be created.
 
The drawback is that I had to spend a lot of time for doing this and now I have to remember about returning unused vectors to pool if I want everything to work well. Moreover when I incidentally return to pool the object that is still being used, a lot of hard for debugging problems can take place.

So summing everything up, I've put a lot of time and effort and made my life harder and whats the profit? Maybe using vectors is more object-oriented and code that is using vectors is shorter and less cumbersome but still if I had stayed by int pairs, I haven't need to implement pool system and vector algebraic functions and everything would work faster (while using pair of ints there would be no need to create special custom object like Vector at all and no need to invoke vector's getters and setters all the time) and were much simplier.

I'm wondering what is your opinion on that? Wchich approach do you personally prefer and how could you ground it? 
Online Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2009-03-03 23:15:11 »

Did you actually measure whether the creation of Vector2's was slowing down your game?

Most likely there are other bottlenecks in your code, so that even if pooling your Vector2's would be twice as fast, you still wouldn't notice in your game, as, for example, drawing all the images takes 99% of your CPU cycles anyway.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline DooM77

Junior Newbie





« Reply #2 - Posted 2009-03-03 23:27:39 »

Did you actually measure whether the creation of Vector2's was slowing down your game?

Most likely there are other bottlenecks in your code, so that even if pooling your Vector2's would be twice as fast, you still wouldn't notice in your game, as, for example, drawing all the images takes 99% of your CPU cycles anyway.

Nope, I haven't done any profiler measures so far. Anyways, from what you've said I can understand that it's worth to use vectors instead of int pairs when posibble because it's more elegant and object oriented and gives no real performance penalties, because it will never be the bottleneck if drawing on screen and other expensive activities are performed. Am I right?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #3 - Posted 2009-03-03 23:42:31 »

I'm just saying the bottleneck is probably somewhere else.

If you're running a physics engine with lots of bodies however, the bottleneck is probably in object allocation.

Measure it.

And remember: premature optimisation is the root of all evil.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline ewjordan

Junior Member





« Reply #4 - Posted 2009-03-04 03:08:04 »

If you're running a physics engine with lots of bodies however, the bottleneck is probably in object allocation.
+1 on that. Smiley  #1 best way to optimize physics is to get rid of every damn vector creation, but that's just about the only place I've ever seen it matter.

Quote
Measure it.

And remember: premature optimisation is the root of all evil.
I agree completely.  To give you a real world example of when you might have to worry, in physics applications I tend to find that vector allocations start to be a problem when you are doing over 30,000 or so per frame.  Less that that, it's usually not an issue.  If you've got less than 10,000 per frame, any time you spend reducing those allocations is absolutely 100% wasted, don't even bother thinking about it.  Check out http://jbox2d.org/v2demos/ - JBox2d hasn't completely eliminated allocations, so I put a count of Vec2 creations per frame, and different demos have various average numbers of allocs (hit right arrow to move between examples), so you can get a sense how it relates to performance.  A lot of the performance drain in that is due to graphics, but if you run a demo with 50k allocs per frame and it's ticking at 60 hz, you know that you don't have to worry about 50k allocs in your application.

Again, though, I've never seen a non-physics application that needs 50k vector allocations per frame, so that's probably not your bottleneck.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 12


Game Engineer


« Reply #5 - Posted 2009-03-04 03:52:38 »

The main reason I use vectors:

Vector functions.

I have written my own vector class that has all the notable and useful calculations you might want to perform with a vector, like dot product, cross product scale, divide, etc. etc. If you're doing any sort of vector math, having this is a must.

If you're simply doing Array access, the only real reason to use a vector (although I would call what you have a Pair, not a Vector) is to have logically related information contained in one place. So your entity can have a Vector position variable instead of a positionX and positionY float.

So in conclusion if you're just accessing X/Y pairs in an array, you don't really have vectors and should be calling it something else. A vector is this --> or this <---- . It's a directional line segment, in a way. They are very very useful in almost any movement/graphical calculation, but not especially important for array access or anything like that.

See my work:
OTC Software
Offline jezek2
« Reply #6 - Posted 2009-03-04 06:30:44 »

Good way to find out if allocations are affecting you too much is to enable GC logging. Use these arguments for JVM:

1  
-XX:+PrintGC -XX:+PrintGCTimeStamps


This will show you when GC is occurring including timestamps. You can then count how many of them are per second, if just few, you're perfectly ok, hotspot can handle many many short-lived allocations.

When working on JBullet physics engine, there were about 10s (maybe even 100s, didn't count exactly) of minor GCs per second, and hotspot actually did well even at that rate. For final application you could leave that probably, but as JBullet is a library, you must need to count for other libraries that would be used in final app, and then it could be really over limit.

So I did a library for easy to use stack allocation (well really object pooling in heap, but behaving like stack), it has really simple and easy to use API, the only downside is that it needs bytecode instrumentation step in your build script (ant task provided). It's available here.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2009-03-04 06:50:39 »

There is a different between allocation time and GC time.

GC time can be minimal (if most of your objects are in Eden) even when the allocation time overhead is significant.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline pjt33
« Reply #8 - Posted 2009-03-04 10:41:31 »

The need of processing some form of coordinates (tile coordinates, pixel coordinates and so on) is very common in game developing. My post is about comparing the approach of using vector object (for example 2-dimensional vectors) with approach of using pairs of int (for example x,y) in every place we need to process coordinates.
A lot of the time I'll use a single int and pack x and y into it as val = x + y * WIDTH. I'll also use a single-dimensional array. You need to know the width of the grid you're representing, but it's easy to extract stuff from the array, easy to pass around, easy to pass back from a method (which is the major drawback of the pair-of-ints approach), and doesn't require any allocation.
Offline DooM77

Junior Newbie





« Reply #9 - Posted 2009-03-04 10:56:35 »

First of all, thank you guys for a great feedback, it was actually very helpful for me.

A lot of the time I'll use a single int and pack x and y into it as val = x + y * WIDTH. I'll also use a single-dimensional array. You need to know the width of the grid you're representing, but it's easy to extract stuff from the array, easy to pass around, easy to pass back from a method (which is the major drawback of the pair-of-ints approach), and doesn't require any allocation.

It's an interesting approach. Actually easy returning restult from methods was important reason for me to use vectors. However operations on packed coordinates may be quite cumbersome (you have to do unpack-process-pack cycle each time) and hard to read. But I will remember about such a possibility. 

Quote
Measure it.

For what I was able to do with a simple profiler I could only find out that there was almost no difference between taken heap memory size with vector pooling system enabled and disabled. Moreover it seems that at this point application with vector pooling enabled seems to need a little more memory (cached vectors are locked for GC) though. I need to learn how to use more advanced profilers to check how it influences CPU business.

For clearing it up for me: heap memory is where objects (instances of classes) are residing and non-heap memory is where classes are loaded to, tu put it simply. Am I right?

Quote
I have written my own vector class that has all the notable and useful calculations you might want to perform with a vector, like dot product, cross product scale, divide, etc. etc. If you're doing any sort of vector math, having this is a must.

If you're simply doing Array access, the only real reason to use a vector (although I would call what you have a Pair, not a Vector) is to have logically related information contained in one place. So your entity can have a Vector position variable instead of a positionX and positionY float.

Yes, I know about it, and I've implemented some of vector operations in my Vector class. I put such examples where it seems that I'm treating vectors just as a pair of int for indexing arrays only to make example possibly the simplest. However I/you could with equal result implement these vector operations not in Vector class but in some static methods/singleton utility class taking (int,int) as agruments ant performing equvalent operations and all these operations would be kept in one place. That wouldn't enforce us to creation of Vector objects unlike keeping these operations in Vector class. So as I can quess, it's all about the clarity ant good style of programming.  

Good way to find out if allocations are affecting you too much is to enable GC logging. Use these arguments for JVM:

1  
-XX:+PrintGC -XX:+PrintGCTimeStamps


This will show you when GC is occurring including timestamps. You can then count how many of them are per second, if just few, you're perfectly ok, hotspot can handle many many short-lived allocations.

Since my game is in early development stage, garbage collections in generated log are really rare. There are some at game initialisation stage and later only when I enforce the game to perform some more activity through input (regardless of pooling system being enabled/disabled). I think that there has to bo some smaller GC's that aren't logged because it's impossible for me that GC can be done so rarely. Forgive me my ignorance, but could you explain me this log syntax? When we take such a line:

1  
[java] 1.580: [GC 1522K->707K(5056K), 0.0025902 secs]


My guessing is that it means: minor (as opposite to "full") garbage collection has taken place after 1.580s of application start, it decreased a heap memory from 1522K down to 707K (but what is that 5056K?), this garbage collection lasted and stopped program execution for 0.0025902 seconds. Is my guessing OK? Also thanks for the ling to library, maybe I'll find it useful in later development.

There is a different between allocation time and GC time.

GC time can be minimal (if most of your objects are in Eden) even when the allocation time overhead is significant.

Just another ignorant question... What does it mean that objects are in Eden? I am really interested.


Quote
I agree completely.  To give you a real world example of when you might have to worry, in physics applications I tend to find that vector allocations start to be a problem when you are doing over 30,000 or so per frame.  Less that that, it's usually not an issue.  If you've got less than 10,000 per frame, any time you spend reducing those allocations is absolutely 100% wasted, don't even bother thinking about it.  Check out http://jbox2d.org/v2demos/ - JBox2d hasn't completely eliminated allocations, so I put a count of Vec2 creations per frame, and different demos have various average numbers of allocs (hit right arrow to move between examples), so you can get a sense how it relates to performance.  A lot of the performance drain in that is due to graphics, but if you run a demo with 50k allocs per frame and it's ticking at 60 hz, you know that you don't have to worry about 50k allocs in your application.

Again, though, I've never seen a non-physics application that needs 50k vector allocations per frame, so that's probably not your bottleneck.

Thanks a lot! Finally I'm getting some picture in my mind and intuition about cost of creation of small objects. And you're right, I kind of wasted my time trying to optimise it but it was a chance to learn a lot about performance issues.

Again, sorry for my noobish questions and thanks for a great help.

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

JGO Kernel


Medals: 51
Projects: 11


Monkey for a head


« Reply #10 - Posted 2009-03-04 11:39:46 »

Just another ignorant question... What does it mean that objects are in Eden? I am really interested.

Heap memory is divided up into different "generation", and objects are placed within the generations based on how long they've existed for. New allocations are made out of the Eden generation, which is for short-lived objects. Periodically Eden will be garbage collected and any objects still live will be promoted to the next generation.

The idea with this is that it's quicker to garbage collect a smaller area of memory, especially when most of the contents will be dead and can be removed. So your temporary vector objects will get wiped before they ever get out of the Eden generation, making the whole process very fast. The above is massively simplified, google for more. Smiley

IMHO, if you're expecting to run on 1.5 or later then the garbage collector is freaking fast. While I wouldn't encorage throwing objects around willy and, indeed, nilly, unless you know you're creating an object in a really tight inner loop then go with whatever is easiest to write now and come back and change it later.

Edit: Oh, and I wouldn't ever try and pool vector objects myself, just because the bugs it can throw up are hideous and hard to track down. If I really need a vector or temporary object but don't want the overhead I usually just make a static object and allocate it once and reuse it. While that still can go wrong it tends to produce much more localised bugs and be much easier to track down.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Online Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2009-03-04 16:54:15 »

The Garbage Collectors in just didn't scale very well, if your heap got larger than a a few GB.

Hurray for the new G1 (GarbageFirst) collector, it almost scales infinitely, but is a tad slower on average, yet reduces the full GC pauses, in 'normal' sized heaps.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
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.

xsi3rr4x (23 views)
2014-04-15 18:08:23

BurntPizza (18 views)
2014-04-15 03:46:01

UprightPath (32 views)
2014-04-14 17:39:50

UprightPath (16 views)
2014-04-14 17:35:47

Porlus (32 views)
2014-04-14 15:48:38

tom_mai78101 (58 views)
2014-04-10 04:04:31

BurntPizza (116 views)
2014-04-08 23:06:04

tom_mai78101 (216 views)
2014-04-05 13:34:39

trollwarrior1 (183 views)
2014-04-04 12:06:45

CJLetsGame (190 views)
2014-04-01 02:16:10
List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:05:20
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!