Quote:
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>