Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (120)
games submitted by our members
Games in WIP (577)
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  
  Optimization help?  (Read 1563 times)
0 Members and 1 Guest are viewing this topic.
Offline LordChandar

Junior Duke


Projects: 1



« Posted 2012-12-14 12:08:32 »

Greetings.

So I have been profiling my code, and I have smoothed out almost all of the rough edged.  I have this one though that kinda baffles me.

I have a function that returns a series of points when drawing a line.  Kind of like an itinerary of points.  It is used for several things.  I use it to calculate a projectile's path, and I also use it to calculate line of sight.  Lots of stuff.  

Problem is it sucks.  I am guessing a large part of the suckiness is the allocating of new points in the loop as the path grows.

Can some nice person on here help me optimize it, or give me ideas on how I could optimize it myself?

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
public static void calc_line(ArrayList<RPGUtil.point> xitinerary,RPGUtil.point source, RPGUtil.point dest, int max_size)
    {
        RPGUtil.point lp;

        xitinerary.clear();
        int x2 = dest.x;
        int y2 = dest.y;
        int x = source.x;
        int y = source.y;

        int dx = Math.abs(x2 - x), sx = x < x2 ? 1 : -1;
        int dy = Math.abs(y2 - y), sy = y < y2 ? 1 : -1;
        int err = (dx>dy ? dx : -dy)/2;

          while (!(x == x2 && y == y2))
          {
            lp = new RPGUtil.point(x,y);
            xitinerary.add(lp);
            if ( (max_size !=0 ) && (xitinerary.size() >= max_size) )
            {
                xitinerary.clear();
                break;
            }
            int e2 = err;
            if (e2 > -dx)
            {
                err -= dy;
                x += sx;
            }
            if (e2 < dy)
            {
                err += dx;
                y += sy;
            }
          }
    }
Offline UprightPath
« Reply #1 - Posted 2012-12-14 12:24:15 »

You could always save a bit of time (Sacrificing Memory) by using what is called an object pool.

Basically, when you call xitinerary.clear(), you'd add all of them to some sort of collect or array (With a maximum size). Whenever you need an object of that type, you would call ObjectType.getInstance(Type1 val1, Type2 val2, ...) whatever you'd need to set the values. It would either pull an object off your collection or instantiate a new one.

Online princec

JGO Kernel


Medals: 404
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #2 - Posted 2012-12-14 12:37:54 »

Nothing particularly stands out in that function there that should be any kind of a performance problem, unless you are calling it 10000x per frame, or making lines that are 1,000,000 points long. It's basically about as fast looking as it could be, without resorting to passing in parallel arrays of int[] x/y (which is legit and will stop you needing to allocate points). So I'd do that and if it still ain't fast enough, reconsider how it's being called in the first place.

Cas Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline gouessej
« Reply #3 - Posted 2012-12-14 12:38:51 »

You could always save a bit of time (Sacrificing Memory) by using what is called an object pool
It isn't very efficient any more (since Java 1.5).

Offline UprightPath
« Reply #4 - Posted 2012-12-14 12:40:44 »

I stand corrected!

It was the first thing that came to mind. And I'm not surprised that it in'it that good (More a statement of, I'm not surprised to hear that my knowledge is incorrect, than me saying I purposefully gave bad advice. xD)

Offline gouessej
« Reply #5 - Posted 2012-12-14 12:50:25 »

UprightPath, it is still a good advice when programming on Android, the DVM sucks  Cry

Online princec

JGO Kernel


Medals: 404
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #6 - Posted 2012-12-14 12:51:51 »

It's still efficient in the case of objects that are relatively expensive to construct or in the case of objects that are produced and discarded in their thousands per frame, though.

Cas Smiley

Offline UprightPath
« Reply #7 - Posted 2012-12-14 13:03:55 »

UprightPath, it is still a good advice when programming on Android, the DVM sucks  Cry
Which is what I tend to program in when I'm doing anything game related. It's the only reason I purchased the phone I have. xD

It's still efficient in the case of objects that are relatively expensive to construct or in the case of objects that are produced and discarded in their thousands per frame, though.

Cas Smiley
And I thought so, but I wasn't sure. I would guess that the number of times this operation is actually used per frame would end up mattering?

Offline LordChandar

Junior Duke


Projects: 1



« Reply #8 - Posted 2012-12-14 13:22:40 »

I guess maybe I just went into optimization overdrive?  I had a horrid issue with screen painting last night, and after fixing it, this was the method that floated to the top of the execution time.

This is the most expensive thing that happens once per turn for the hero, and once per turn for any NPC/spawn that is attempting to move somewhere.  During my last profile test, this function was called 81 times in the 5 or so moves I made. 

The hero uses this function like a radar and going completely around himself to see what he can see and stop when he can't.  It works like a wind shield wiper blade. 

The monsters simply do it to see if they can see the nearest prey for possible attack persons.
Offline Best Username Ever

Junior Duke





« Reply #9 - Posted 2012-12-14 21:46:38 »

Try taking the ArrayList out of the parameter and make it a return value. It could be the fact that your existing ArrayList is in a older generation than your newly created points. The way many non-Android garbage collectors work means it's more expensive to store things in old objects than it is to create a new temporary storage object to hold more temporary objects.

A better solution is to not use ArrayList. Create an object with an
void add(int x, int y)
,
getX(int index)
, and
getY(int index)
method. And store the x,y coordinates interleaved in the same array (
{x0, y0, x1, y1, ..., xn, yn}
), not in parallel arrays. This will guarantee that all the point data gets grouped together and there is no memory management problem stemming from how a point is used or how long it lives.

You can also use a profiler for a block of code inside a method by specifying a range of line numbers to time. Then you can pinpoint which lines inside a method take longest to execute once you know which method takes the most time. Besides that, you should not start a class name with a lowercase letter. (But obviously that would not alter the performance.)
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online princec

JGO Kernel


Medals: 404
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #10 - Posted 2012-12-14 23:08:50 »

Try taking the ArrayList out of the parameter and make it a return value. It could be the fact that your existing ArrayList is in a older generation than your newly created points. The way many non-Android garbage collectors work means it's more expensive to store things in old objects than it is to create a new temporary storage object to hold more temporary objects.
That could be interpreted in all sorts of wrong ways by those with just not quite enough knowledge. It is not more expensive to use old objects, at all, per se. It is very slightly more expensive to garbage collect them with some collectors, though.

Cas Smiley

Offline Best Username Ever

Junior Duke





« Reply #11 - Posted 2012-12-15 01:14:53 »

Good point, but not really the problem behind that usage. It occurred to me that the OP is probably attempting unnecessary optimization. The method would have to be called a lot more for it to be a problem for either object creation trouble or inner loop performance. I'll still clarify to avoid confusion. If this method created thousands of Objects, it would add up, but it probably does not unless the two points are far away.

...

Generational garbage collectors divide objects into groups based on the assumption that newer objects are likely to be temporary and older objects are likely to stick around even longer. Garbage collecting in the young generation uses an algorithm that scales with the number of live references and, for the old generation, uses an algorithm that depends on the number of total objects created.

So keeping temporary objects entirely in the young generation means that it's cheap to create lots of temporary objects. It's okay for a young object to reference an object in any generation, but an old generation object that even temporarily references younger generation objects is bad. It means that the thousands of objects you create in the young generation suddenly have to be scanned using the old gen algorithm instead of the young gen one.

...

Has anyone done testing on object pooling compared to generating immutable objects with G1? I haven't tried anything with huge numbers of objects in that version.
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.

Longarmx (52 views)
2014-10-17 03:59:02

Norakomi (43 views)
2014-10-16 15:22:06

Norakomi (33 views)
2014-10-16 15:20:20

lcass (37 views)
2014-10-15 16:18:58

TehJavaDev (68 views)
2014-10-14 00:39:48

TehJavaDev (66 views)
2014-10-14 00:35:47

TehJavaDev (59 views)
2014-10-14 00:32:37

BurntPizza (73 views)
2014-10-11 23:24:42

BurntPizza (45 views)
2014-10-11 23:10:45

BurntPizza (85 views)
2014-10-11 22:30:10
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

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
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!