Back to General and Gameplay Programming

[C++] Need help optimizing performace of a small function

Tyler Olsen · 2011-11-22T06:43:53

Hello. I have a relatively simple problem that I wrote a function to solve but I'm running into performance issues when the input size to this function gets exceptionally high. Basically, I'm trying to find the number of ways that I can build a wall of height "n" using a number of different arrangements of lines of blocks. Not all lines are allowed to be placed on top of one another. Each "BlockLine" object has a vector container called "compatible_lines" that contain the indeces of all lines that this line is compatible with. So for example if line 0 was compatible with lines 1 and 2, line 1 was compatible with 0 and 3, line 2 was compatible with 0, and line 3 was compatible with line 1, then the number of ways I can build a wall of height "3" would be: 0-1-0 0-2-0 0-1-3 1-0-1 1-3-1 1-0-2 2-0-2 2-0-1 3-1-3 3-1-0 For a total of 10 ways. Make sense? I already have written a function that calculates the correct result when given a wall height (between 1 and 10) and a set of BlockLine objects that already have their compatible_line data entered. The function works great for small to mid-size wall configurations (a wall of height 10 with 65 possible lines is computed in a fraction of a second). But when I change the number of lines to a larger number (3329 in the test that I'm using) the function is exceptionally slow for larger heights. (3329, 5) is still computed in under a second, but (3329, 10) takes much much too long (several minutes). So I'm trying to figure out how to optimize this code so that it performs well for the larger input sets. Here's the source: [source] /** \brief Determines the number of possible configurations that can build a block wall of a specific height *** \param wall_height The height of the wall, as a number of wall lines *** \param lines A reference to the container where all possible block line permutations are stored *** \return The number of wall configurations *** \note The BlockLine objects stored in the lines argument must have all their line compatibilities *** set before this function is called. *** *** This function works by starting with constructing the base of the wall with all possible lines. For each *** line at the base, the compatible lines are placed on top, and those lines have their compatible lines placed *** on top of them and so on until the wall has reached its maximum height. **/ int64_t ComputeNumberWallConfigurations(int wall_height, vector<BlockLine>& lines) { // In the case that the height of the wall is one, the number of configurations is simply the number of line permutations if (wall_height == 1) { return lines.size(); } // A counter that keeps track of the number of wall configurations int64_t num_configurations = 0; // A stack of all the lines that build the current configuration being examined vector<int> line_stack; // A companion stack that tracks the index of the next compatible line to examine for each line in the stack vector<int> next_stack; for (int i = 0; i < lines.size(); i++) { // Lines that are not compatible with any other line can not be used to form a wall that is two or more lines tall if (lines.compatible_lines.empty() == true) { continue; } line_stack.push_back(i); next_stack.push_back(0); int64_t temp = 0; printf("Constructing wall with base line: %d ... ", i); // With the base line established, now determine all possible configurations for the wall for the provided base line while (line_stack.empty() == false) { int this_line = line_stack.back(); // (Case 1): If the next line pushed on the stack would be the top of the wall, add the number of compatible lines for this line and pop if (line_stack.size() == (wall_height - 1)) { temp += lines[this_line].compatible_lines.size(); num_configurations += lines[this_line].compatible_lines.size(); line_stack.pop_back(); next_stack.pop_back(); } // (Case 2): There are no more compatible lines to examine for this configuration on this level. Pop back to a lower level. else if (next_stack.back() >= lines[this_line].compatible_lines.size()) { line_stack.pop_back(); next_stack.pop_back(); } // (Case 3): Add another line to the top of the stack and increment the current line's "next" index else { int next_line = next_stack.back(); next_stack.back() += 1; line_stack.push_back(lines[this_line].compatible_lines[next_line]); next_stack.push_back(0); } } printf("number configurations == %lld\n", static_cast<long long int>(temp)); } return num_configurations; } [/source] Its a pretty simple algorithm as you can see. It used to be a recursive function, but I rewrote it to be an iterative version when I noticed how slow it ran. Basically I build the wall up from the bottom one line at a time until I'm at the second to last line from the top. Then I simply add to my accumulator variable (num_configurations) the amount of lines I can put at the top, then pop back down the stack. I realize that this algorithm is a prime candidate for multithreading and that could improve performance (launch each while(line_stack.empty()) loop logic in its own thread) but I don't really want to make this code multithreaded if I don't have to. Plus, I'm kind of doubtful that it would give me the degree of performance that I'm seeking unless I'm launching these threads across 64 different processor cores or something. I've been staring at this function for an hour and I haven't though of any way to drastically increase the performance. Is there something that I'm missing? One behavior that I did notice during my testing with these larger input sets is that the further along I get, the slower it seems to take for each base line. What I mean is, when this function starts running the first few hundred lines are printed out very quickly (each line computed quickly, hundredths of a second) Constructing wall with base line: 0 ... number configurations == 1 Constructing wall with base line: 1 ... number configurations == 252 Constructing wall with base line: 2 ... number configurations == 731808 Constructing wall with base line: 3 ... number configurations == 267227532 Constructing wall with base line: 4 ... number configurations == 13534077843 (each line computed slowly, several seconds each) Constructing wall with base line: 468 ... number configurations == 1733285040 Constructing wall with base line: 469 ... number configurations == 2477179776 Constructing wall with base line: 470 ... number configurations == 2673027300 Constructing wall with base line: 471 ... number configurations == 2108819760 Constructing wall with base line: 472 ... number configurations == 808799196 Constructing wall with base line: 473 ... number configurations == 6573600 I examined my performance monitor and I didn't see anything wrong with the memory usage. The process remains static at 800KB of memory and 100% CPU, so I'm pretty certain that this is a computationally bound performance issue and has nothing to do with inefficient memory access.

General and Gameplay Programming Programming

Started by Roots November 21, 2011 04:42 PM

12 comments, last by Roots 12 years, 5 months ago

alvaro

21,604

November 21, 2011 08:31 PM

So I think I worked out a much faster solution. I will write the pseudo code and use your example

If you read the matrix formulation I proposed, what your code is doing is its most naive implementation. And yes, this is a very reasonable solution.

Telastyn

3,778

November 21, 2011 08:34 PM

So I think I worked out a much faster solution.

I came up with this as well. I wouldn't be surprised if this could be solved in essentially constant time with respect to the wall's height with some fancy math involving the ratio of incoming to outgoing connections.

-- Tangent Developer Journal - Delegates - Part 2

landagen

376

November 21, 2011 09:12 PM

[quote name='landagen' timestamp='1321906965' post='4886326']
So I think I worked out a much faster solution. I will write the pseudo code and use your example

If you read the matrix formulation I proposed, what your code is doing is its most naive implementation. And yes, this is a very reasonable solution.
[/quote]

I was formulating my post when you posted yours and had not read yours. I think both will work just fine. In the case of sparse line compatibilities I think mine will consume less memory and will be faster, but yours will be quicker in the event of dense line compatibilities.

alvaro

21,604

November 21, 2011 11:22 PM

[quote name='alvaro' timestamp='1321907485' post='4886332']
[quote name='landagen' timestamp='1321906965' post='4886326']
So I think I worked out a much faster solution. I will write the pseudo code and use your example

If you read the matrix formulation I proposed, what your code is doing is its most naive implementation. And yes, this is a very reasonable solution.
[/quote]

I was formulating my post when you posted yours and had not read yours.[/quote]
Sure, I wanted to point out to the OP that we were basically saying the same thing.

I think both will work just fine. In the case of sparse line compatibilities I think mine will consume less memory and will be faster, but yours will be quicker in the event of dense line compatibilities.
[/quote]

Well, I didn't propose a specific algorithm to compute the product of matrices I posted. Your pseudocode is a perfectly good way to do it. If the height is large, a dense matrix representation will work better. It might even be worth diagonalizing the matrix, so this method can be used.

alvaro

21,604

November 22, 2011 12:06 AM

Ah, one more comment for the OP: If your function is not going to modify the container that it gets passed, make it a const reference.

Roots

1,626

Author

November 22, 2011 06:43 AM

Thanks for all your help thus far everyone. landagen, I implemented the algorithm you described and yes, it is much much faster. Easily fast enough for my requirements. Also I am using 64-bit integers to compute this total as that is the maximum size I am expecting for any given input. I still am not quite sure about how the solution works though. This is just something that I need to think about and study on my own though. I think if I work the algorithm through an example data set I will understand it better. Thanks so much, I really appreciate the help on this!

Hero of Allacrost - A free, open-source 2D RPG in development.
Latest release June, 2015 - GameDev annoucement

[C++] Need help optimizing performace of a small function

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

[C++] Need help optimizing performace of a small function

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines