code takes too long to execute

W

Wizumwalt

Hey all, well, I finally got a profiler to work and my code was simple
enough that what I thought it was doing, it actually was doing, so I'm
still at a loss as to why it's so slow. I'm still trying to learn the
profiler a bit better to use, cause it took about 4 hours before I
could get any results after running the following code (literally, I
left it running for 4 hours while it was chugging away in this section
of code w/ the profiler running, my machine has 512Mb RAM).

So now I'm posting my code and maybe someone could tell me why it takes
25 seconds to run this w/o debugging. The section within '---' is what
I've timed to take 25 seconds and the supporting code is below.
Everything that is prefixed w/ either get or set is exactly that.

Code: 
// --- time start
// elements is a HashMap of 10676 in size.
Iterator eKeyIter = elements.keySet().iterator();

for (Iterator iter = elements.values().iterator(); iter.hasNext();) {
Element elem = (Element)iter.next();

if (elem.getShape() == ElementSupport.TRIANGLE) {
ttl++;
buildEdgeList(elem);
}
}
// --- time ends (25 seconds)


public void buildEdgeList(Element elem) {
WingedEdge[] wEdges = new
WingedEdge[ElementSupport.TRIANGLE_EDGE_COUNT];

for (int edge = 0; edge < ElementSupport.TRIANGLE_EDGE_COUNT;
edge++) {	      edgeGUID++;
wEdges[edge] = new WingedEdge(edgeGUID);

if (edge <= 1) {
wEdges[edge].setStartVertexId(elem.getVertex(edge));
wEdges[edge].setEndVertexId(elem.getVertex(edge + 1));
wEdges[edge].setRightFace(findAdjacentFace(elem.getId(),
elem.getVertex(edge), elem.getVertex(edge + 1)));
}
else {
wEdges[edge].setStartVertexId(elem.getVertex(2));
wEdges[edge].setEndVertexId(elem.getVertex(0));
wEdges[edge].setRightFace(findAdjacentFace(elem.getId(),
elem.getVertex(2), elem.getVertex(0)));
}

wEdges[edge].setLeftFace(elem.getId());

Triangle tri = (Triangle) elem;
tri.setEdge(edge, wEdges[edge]);
}

traverseEdges(wEdges);
}


public void traverseEdges(WingedEdge[] weds) {
for (int edge = 0; edge < ElementSupport.TRIANGLE_EDGE_COUNT;
edge++) {
switch (edge) {
case 0:
weds[edge].setPredecessor(ElementSupport.CCW, weds[2].getId());
weds[edge].setSuccessor(ElementSupport.CCW, weds[1].getId());
break;

case 1:
weds[edge].setPredecessor(ElementSupport.CCW, weds[0].getId());
weds[edge].setSuccessor(ElementSupport.CCW, weds[2].getId());
break;

case 2:
weds[edge].setPredecessor(ElementSupport.CCW,
weds[1].getId());
weds[edge].setSuccessor(ElementSupport.CCW,
weds[0].getId());
break;
}

edgeList.add(weds[edge]);
}

return;
}

public int findAdjacentFace(int source, int start, int end) {
Iterator eKeyIter = elements.keySet().iterator();

while (eKeyIter.hasNext()) {
Element elem = (Element) elements.get(eKeyIter.next());

if (elem.getId() == source) {
// found the exact same element so continue on.
continue;
}

if (elem.getShape() == ElementSupport.TRIANGLE) {
for (int i = 0; i < ElementSupport.TRIANGLE_EDGE_COUNT; i++) {
if (i <= 1) {
if (elem.getVertex(i) == end &&
elem.getVertex(i + 1) == start) {

return elem.getId();
}
}
else {
if (elem.getVertex(2) == end &&
elem.getVertex(0) == start) {

return elem.getId();
}
}
}
}
}

return 0;
}
 
O

Oliver Wong

Hey all, well, I finally got a profiler to work
Click to expand...

Hooray. =)
So now I'm posting my code and maybe someone could tell me why it takes
25 seconds to run this w/o debugging. The section within '---' is what
I've timed to take 25 seconds and the supporting code is below.
Everything that is prefixed w/ either get or set is exactly that.
Click to expand...

[sniped code]

Okay, so I see the codeblock which takes 25 seconds actually calls other
methods. So is the bottleneck really in the codeblock, or is it in one of
the method it calls? For example, if of those 25 seconds, 24.7 of them are
spent in the "buildEdgeList()" method, it'd be a waste of time trying to
optimize the codeblock itself. Can you find the one particular method or
block of code in which most of the time is being spent?

- Oliver
 
R

Roedy Green

Iterator eKeyIter = elements.keySet().iterator();

for (Iterator iter = elements.values().iterator(); iter.hasNext();) {
Click to expand...

not crucial. But the first line should be commented out.
 
R

Roedy Green

for (Iterator iter = elements.values().iterator(); iter.hasNext();) {
Element elem = (Element)iter.next();
Click to expand...

you can use the new JDK 1.5 syntax:

// I T E R A T O R : Java 1.5
// getFilesToProcess returns an Iterator<File> parameterised Iterator
// note for, not while
for ( File f : getFilesToProcess() )
{
...
}
 
R

Roedy Green

for (int edge = 0; edge < ElementSupport.TRIANGLE_EDGE_COUNT;
edge++) { edgeGUID++;
Click to expand...

this is a loop within a loop. So the stuff outside this is likely not
the problem.
 
R

Roedy Green

(elem.getVertex(edge)
Click to expand...

I am suspicious of this code. What sort of lookup are you doing on
edge?

You did not post that method.

But you used a profiler. It should tell you exactly which lines are
crucial.

If all the operations are trivial the problem simply could be that you
are randomly accessing objects all over the place and there is not
enough REAL ram for them so you are swapping like mad. To fix that
you would somehow have to change your algorithm to partition your
objects into camps, then process them camp by camp and camp pairs to
keep the real memory footprint down.

Make sure no other tasks are running to free up as much real ram as
possible.

You could also try REDUCING the virtual memory size to help keep your
objects compact.
 
P

Patricia Shanahan

Hey all, well, I finally got a profiler to work and my code was simple
enough that what I thought it was doing, it actually was doing, so I'm
still at a loss as to why it's so slow. I'm still trying to learn the
profiler a bit better to use, cause it took about 4 hours before I
could get any results after running the following code (literally, I
left it running for 4 hours while it was chugging away in this section
of code w/ the profiler running, my machine has 512Mb RAM).

So now I'm posting my code and maybe someone could tell me why it takes
25 seconds to run this w/o debugging. The section within '---' is what
I've timed to take 25 seconds and the supporting code is below.
Everything that is prefixed w/ either get or set is exactly that.

Code: 
// --- time start
// elements is a HashMap of 10676 in size.
Iterator eKeyIter = elements.keySet().iterator();

for (Iterator iter = elements.values().iterator(); iter.hasNext();) {
Element elem = (Element)iter.next();

if (elem.getShape() == ElementSupport.TRIANGLE) {
ttl++;
buildEdgeList(elem);
}
}
// --- time ends (25 seconds)


public void buildEdgeList(Element elem) {
WingedEdge[] wEdges = new
WingedEdge[ElementSupport.TRIANGLE_EDGE_COUNT];

for (int edge = 0; edge < ElementSupport.TRIANGLE_EDGE_COUNT;
edge++) {	      edgeGUID++;
wEdges[edge] = new WingedEdge(edgeGUID);

if (edge <= 1) {
wEdges[edge].setStartVertexId(elem.getVertex(edge));
	 wEdges[edge].setEndVertexId(elem.getVertex(edge + 1));
wEdges[edge].setRightFace(findAdjacentFace(elem.getId(),
	 elem.getVertex(edge), elem.getVertex(edge + 1)));
}
else {
wEdges[edge].setStartVertexId(elem.getVertex(2));
	 wEdges[edge].setEndVertexId(elem.getVertex(0));
	 wEdges[edge].setRightFace(findAdjacentFace(elem.getId(),
	    elem.getVertex(2), elem.getVertex(0)));
}

wEdges[edge].setLeftFace(elem.getId());

Triangle tri = (Triangle) elem;
tri.setEdge(edge, wEdges[edge]);
}

traverseEdges(wEdges);
}


public void traverseEdges(WingedEdge[] weds) {
for (int edge = 0; edge < ElementSupport.TRIANGLE_EDGE_COUNT;
edge++) {
switch (edge) {
case 0:
	    weds[edge].setPredecessor(ElementSupport.CCW, weds[2].getId());
	    weds[edge].setSuccessor(ElementSupport.CCW, weds[1].getId());
	    break;

case 1:
	    weds[edge].setPredecessor(ElementSupport.CCW, weds[0].getId());
	    weds[edge].setSuccessor(ElementSupport.CCW, weds[2].getId());
break;

case 2:
weds[edge].setPredecessor(ElementSupport.CCW,
weds[1].getId());
weds[edge].setSuccessor(ElementSupport.CCW,
weds[0].getId());
break;
}

edgeList.add(weds[edge]);
}

return;
}

public int findAdjacentFace(int source, int start, int end) {
Iterator eKeyIter = elements.keySet().iterator();

while (eKeyIter.hasNext()) {
Element elem = (Element) elements.get(eKeyIter.next());

if (elem.getId() == source) {
// found the exact same element so continue on.
continue;
}

if (elem.getShape() == ElementSupport.TRIANGLE) {
for (int i = 0; i < ElementSupport.TRIANGLE_EDGE_COUNT; i++) {
if (i <= 1) {
if (elem.getVertex(i) == end &&
elem.getVertex(i + 1) == start) {

return elem.getId();
}
}
else {
if (elem.getVertex(2) == end &&
elem.getVertex(0) == start) {

return elem.getId();
}
}
}
}
}

return 0;
}
Click to expand...

Each call to findAdjacentFace scans, on average, half the elements,
about 5,000, because it returns when it finds the one it is looking for.
You call findAjacentFace once for each triangle edge, I assume three
times, per call to buildEdgeFace. You call buildEdgeFace about 10,000 times.

If I'm reading your code correctly the while loop in findAdjacentFace
does about 10,000*3*5,000 = 150,000,000 iterations. You can check by
sticking a counter down in the findAdjacentFace loop to see how many
times it actually runs.

150,000,000 iterations in 25 seconds is 6 million iterations per second,
or about one iteration per 166 nanoseconds. Depending on the sizes of
data structures, you could be having significant cache miss rates, in
which case that seems reasonable.

Is there any way you could link together related structures as you
build, rather than waiting until you have 10676 elements and then doing
an O(n**2) search?

Patricia
 
W

Wizumwalt

Oliver said:
Hooray. =)
Click to expand...

Yeah, I tried yourkit and jprofiler, still messing between the two
trying to get one that shows me what I need. Getting the hang of these
will take me a bit longer to get it to the point where I want it to
show me what I need to know.
Okay, so I see the codeblock which takes 25 seconds actually calls other
methods. So is the bottleneck really in the codeblock, or is it in one of
the method it calls? For example, if of those 25 seconds, 24.7 of them are
spent in the "buildEdgeList()" method, it'd be a waste of time trying to
optimize the codeblock itself. Can you find the one particular method or
block of code in which most of the time is being spent?
Click to expand...

I have several other code blocks before and after in this entire
process, but this is the one that takes the most time and where I need
to focus on. The buildEdgeList() is where most of the time is taken,
and in one of the set methods of buildEdgeList(), there's another
search again through this entire HashMap (i.e. findAdjacentFace())
which is where I'm sure all the time is going. But I'm not sure how to
cut this down. This is why I was thinking maybe I should move my
HashMap to an ArrayList and try to find a shortcut of ways to search.
 
O

Oliver Wong

I have several other code blocks before and after in this entire
process, but this is the one that takes the most time and where I need
to focus on. The buildEdgeList() is where most of the time is taken,
and in one of the set methods of buildEdgeList(), there's another
search again through this entire HashMap (i.e. findAdjacentFace())
which is where I'm sure all the time is going.
Click to expand...

You shouldn't have to guess about this kind of stuff. Your profiler
should be able to tell you exactly how much time is being spent in each
method. In other words, it should be reporting how much time is spent in
buildEdgeList and findAdjacentFace (as well as all your other methods). Then
you can find the method which is taking up the most time.

- Oliver
 
W

Wizumwalt

I stuck a counter in there and it iterated 113,272,072 times.

That's actually what I'm trying to do, build a graph in memory of my
model by linking the related data structures together. So each edge
knows of it's local edges and the edges, faces of the opposite element.

But I'm certain I'm not doing it the correct way for it to take that
long. That's too long for my users.


--- my data structure

public class WingedEdge
{
private int guid;
private int start = 0;
private int end = 0;
private int leftFace = 0;
private int rightFace = 0;

private int leftTraversalSuccessor = 0;
private int rightTraversalSuccessor = 0;
private int leftTraversalPredecessor = 0;
private int rightTraversalPredecessor = 0;

private boolean isFrontier = false;

public WingedEdge(int id) {
guid = id;
}

public int getId() {
return guid;
}

public void setPredecessor(int direction, int edge) {
if (direction == ElementSupport.CCW) {
leftTraversalPredecessor = edge;
}
else if (direction == ElementSupport.CW) {
rightTraversalPredecessor = edge;
}

return;
}

public int getPredecessor(int direction) {
if (direction == ElementSupport.CCW) {
return leftTraversalPredecessor;
}
else if (direction == ElementSupport.CW) {
return rightTraversalPredecessor;
}

return 0;
}

public void setSuccessor(int direction, int edge) {
if (direction == ElementSupport.CCW) {
leftTraversalSuccessor = edge;
}
else if (direction == ElementSupport.CW) {
rightTraversalSuccessor = edge;
}

return;
}

public int getSuccessor(int direction) {
if (direction == ElementSupport.CCW) {
return leftTraversalPredecessor;
}
else if (direction == ElementSupport.CW) {
return rightTraversalPredecessor;
}

return 0;
}

public int getStartVertexId() {
return start;
}

public void setStartVertexId(int id) {
start = id;

return;
}

public int getEndVertexId() {
return end;
}

public void setEndVertexId(int id) {
end = id;

return;
}

public void setLeftFace(int val) {
leftFace = val;

return;
}

public int getLeftFace() {
return leftFace;
}

public void setRightFace(int val) {
rightFace = val;

return;
}

public int getRightFace() {
return rightFace;
}

public void setFrontier(boolean val) {
isFrontier = val;

return;
}

public boolean isFrontier() {
return isFrontier;
}
}
 
W

Wizumwalt

(elem.getVertex(edge)
I am suspicious of this code. What sort of lookup are you doing on
edge?
Click to expand...

public class Element implements ElementSupport {

private int id = 0;
private int shape = 0;
private int propertyId = 0;
private int totalNodes = 0;
protected int[] vertices = new int[MAX_ELEMENTS];
private Vector nodes = null;

private double x = 0.0f;
private double y = 0.0f;
private double z = 0.0f;

public Element() {

for (int i = 0; i < MAX_ELEMENTS; i++) {
vertices = 0;
}

nodes = new Vector();
}

public int getVertex(int idx) {
return vertices[idx];
}

...
You did not post that method.

But you used a profiler. It should tell you exactly which lines are
crucial.
Click to expand...

Haven't used it efficiently enough. Still working on this part.
 
T

Thomas Hawtin

public int findAdjacentFace(int source, int start, int end) {
Click to expand...

You are calling this method (thrice) for each element you iteration of
the outer loop.
Iterator eKeyIter = elements.keySet().iterator();

while (eKeyIter.hasNext()) {
Element elem = (Element) elements.get(eKeyIter.next());
Click to expand...

And now you are going to iterate through the loop again. O(n^2). Ouch.
if (elem.getId() == source) {
// found the exact same element so continue on.
continue;
}

if (elem.getShape() == ElementSupport.TRIANGLE) {
for (int i = 0; i < ElementSupport.TRIANGLE_EDGE_COUNT; i++) {
if (i <= 1) {
if (elem.getVertex(i) == end &&
elem.getVertex(i + 1) == start) {

return elem.getId();
}
}
else {
if (elem.getVertex(2) == end &&
elem.getVertex(0) == start) {

return elem.getId();
}
}
}
}
}

return 0;
}
Click to expand...

So you're trying to find an edge that exactly matches. Sort of thing a
HashMap would be good for. If you kept a parallel map from edges to an
array/list of elements (a poor man's multimap), you could reduce the
algorithm to O(n). It still might not be particularly efficient, but it
should be bundles better for large sets.

Tom Hawtin
 
P

Patricia Shanahan

I stuck a counter in there and it iterated 113,272,072 times.

That's actually what I'm trying to do, build a graph in memory of my
model by linking the related data structures together. So each edge
knows of it's local edges and the edges, faces of the opposite element.

But I'm certain I'm not doing it the correct way for it to take that
long. That's too long for my users.
Click to expand...

You should quote enough to give some context. By "in there" I'm assuming
you mean in the findAdjacentFace while loop.

Detailed tuning of an O(n**2) algorithm is doable, but something of a
last resort. The first thing to do is to question your algorithm and
data structures. I'm not getting the big picture of where the data is
coming from, and in what form.

Can more than two triangles be adjacent to an edge? Can more than three
edges be adjacent to a triangle? If not, you may be able to get some
gain from a data structure that only tracks faces and edges that don't
yet have their quota.

Patricia
 
R

Roedy Green

public int getVertex(int idx) {
return vertices[idx];
Click to expand...

since we are now in optimisation mode, one thing you can do is make
that method final to ensure it is inlined. However I doubt this
method is the problem. In one of those methods you call must be yet
another loop.
 
R

Roedy Green

while (eKeyIter.hasNext()) {
Element elem = (Element) elements.get(eKeyIter.next());

if (elem.getId() == source) {
Click to expand...

It seems to me your overall problem is essentially this. You have
numbered objects that you logically connect together by id number and
you want direct references to tie them together.

What if these id numbers were dense or almost dense? i.e. numbered
0,1,2,3...n

Then you could build a simple array[] or ArrayList index to the
objects by object number. Lookup would be almost instantaneous.

If these numbers are not unique, at the index slot, you could have a
hashMap or ArrayList or some other collection to hold the duplicates.

Alternatively, you make the id numbers unique and dense in a pre-pass.

Let's assume your id numbers are extremely sparse. Then you could
start with an HashMap from id number to object.

The other posters have a much clearer idea of what you are doing than
I do. So take this with a grain of salt.
 
R

Roedy Green

Then you could build a simple array[] or ArrayList index to the
objects by object number. Lookup would be almost instantaneous.
Click to expand...

The other thing is, instead of looking at object A and trying to find
all other objects that link to it by scanning the other objects, run
down the list of all objects and attach them to whatever they are
linked to. In other words, work from source to target not target to
source. Then you will have an o(n) process.
 
T

Thomas Hawtin

Roedy said:
since we are now in optimisation mode, one thing you can do is make
that method final to ensure it is inlined. However I doubt this
Click to expand...

Making methods used to make things faster. However, Sun HotSpot at least
ignores final (after verification). Inlining appears to be encouraged by
calling small methods *from small methods*.

Tom Hawtin
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Making sure this javascript code works 1
Python code problem 2
Processing in Python help 0
Q for a source code in an exercise 1
How to position the *tooltip* comment on these buttons? 9
Uncaught ReferenceError: item is not defined at HTMLButtonElement.onclick in the: <button onclick="item.inserir()">Inserir dados</button> 1
Qsort() messing with my entire Code 0
Help with Loop 0

Members online

No members online now.
Total: 41 (members: 0, guests: 41)
Robots: 223

Forum statistics

Threads
473,997
Messages
2,570,240
Members
46,828
Latest member
LauraCastr

Latest Threads

Top