Ship AIs that talk to each other

[Will]

AngleWyrm said:
I have an older model CPU: An AMD 3200+ that runs at a frequency of 2 Ghz. That's two billion instructions per second.

It's up to the programmer to do speed optimizations where appropriate, which is usually handled by profiling the code and then tightening up the sections that take up the most time.

It could just as easily be the way the program parses text files that is causing it to run slowly. But again, without actually profiling the code, it's all just speculation.

Well, that's partially right... a 2Ghz CPU has two billion clock ticks per second, but not necessarily two billion operations; the Athlons had a theoretical issue rate of 6x (micro)instructions per clock, for maximum theoretical 12 billion operations per second... however, it isn't often you will decode 6 instructions every clock, and since it is an out-of-order architecture, not every operation that issues will necessarily be completed. If you have a program that is almost entirely cache-resident, then you could probably get it up to 5 or so billion ops/sec.

And these days, it's up to the compiler to do profiling optimizations, not the programmer. The only optimization really left to programmers now are macro-level... i.e. choosing a O(n log n) algorithm over an O(n^2) algorithm.

And yes, I/O is the main bottleneck in computation. Fetching a 512 byte block from disk to memory (usually 512 is the minimum, it can go higher) takes on the same order of time as several million instructions. You can optimize that away to a point, such as by prefetching blocks from disk, but it is not always known what block will be needed, so prefetching doesn't always work. The same for fetching from memory, bringing a page of memory to the cache takes on order of hundreds to thousands of instruction cycles. And then from cache to registers takes on order of tens to hundreds of cycles.

Anyway, with regard to the algorithm itself: it's a standard auction algorithm, fairly common in AI literature. It's popular because it's fairly fast, gets close to optimal results most of the time, and is simple to understand and implement. It is a close relative to the Traveling Salesman problem, so there is no known polynomial time algorithm that will give the optimal solution; auctions get close (minus a few fringe cases) in O(2n). If a system can play a graphical RTS game, it probably can also do this algorithm at the same time, since the graphics take far more processing than the algorithm does.

</computer-nerd>

[AngleWyrm]

Will said:
And these days, it's up to the compiler to do profiling optimizations, not the programmer. The only optimization really left to programmers now are macro-level... i.e. choosing a O(n log n) algorithm over an O(n^2) algorithm.

Compilers can do a lot, but the coder should look at a profile as well. In one project (Hat random container), when I profiled the code, I found out that it was spending a lot of time in one particular function call (the update_weights function). With this information, I was able to get a good speed boost by moving one locally constructed variable into a class member position.

[Will]

AngleWyrm said:

Compilers can do a lot, but the coder should look at a profile as well. In one project (Hat random container), when I profiled the code, I found out that it was spending a lot of time in one particular function call (the update_weights function). With this information, I was able to get a good speed boost by moving one locally constructed variable into a class member position.

Yes, but that's still what I would call "macro-level". You're getting the speed boost because instead of calculating a value that doesn't change much n times, you store it in a higher scope and calculate it fewer (one?) times. That's an algorithmic choice, much like choosing mergesort over bubblesort is, only with less dramatic results.

Even then, compilers will do a lot of that within function or method blocks. It can't be done like you were saying up to the class-level, because then optimizations would be changing the data-structure of an object, which breaks compatibility with un-optimized code. But anything that is in a self-contained block with an immutable interface to other code the compiler will optimize better than a human programmer would. So, it's best not to worry about those and focus instead on building good algorithms and data structures.

--edit: and damn! I wish the people I work with commented their code thoroughly like you did. Just a note, you may want to split hat.h into hat.h and hat.cpp, that way if you ever make a change to the methods that don't affect the interface, you don't need to recompile everything that #includes hat.h. It's a habit best learned early, lest you need to recompile and relink thousands of source files instead of just relinking thousands and recompiling one

[AngleWyrm]

Thanks on the comments commentary; I'm a big believer in them too. The best thing I learned on comments is make them read at a higher level than the code they describe.

About the single-file implementation: I had read that templated classes have problems with putting the implementation into a separate file, but I don't remember the specific reason anymore. Seems like it had something to do with the way compilers generate code for each used template-parameter pair.

Have you had a different experience with templated classes? Do they work in a normal two-file header/source layout?

BTW, Happy Birthday!