Performance Characteristics of Fundamental Operations for Computational Estimation of Algorithmic Complexity

Answer 1

Intel has some information about their assembly implementation in their articles database. The good ones are pretty dense (like this 600-page PDF file), but they've got a lot of interesting information, including some tables with approximate latency times. There's also a table with some latency times for their 64-bit architecture, so you might be able to search for a similar 32-bit one if you want it.

I personally have no idea about any information for AMD's processors. Google might turn up some results, but I haven't used an AMD machine since the Athlon 3000 days, so I haven't had the need to look for this kind of information.

Answer 2

From what I know:
inc: min O(1) max O(log n)
add, sub: O(log n)
mul, div: O(n)

malloc: O(n*m) n is size allocated, m is number of previous allocations.
free: O(1) (sometimes O(log m)).

Answer 3

On most modern CPUs, the concept of "cycle time for a particular instruction" is not especially helpful. The pipeline will be handling multiple instructions at once, and they will be competing for various resources inside the CPU - so the performance of a given instruction can only be understood in the context of the surrounding instructions. And the details will vary significantly, within even the different models in a processor family.

Furthermore, if you're doing anything that is touching data, then cache behaviour is likely to be just as important as instruction execution times.

For x86: have a look at Agner Fog's "Software optimization resources".

Answer 4

The group of Reinhard Wilhelm in Saarbrücken does research on timing analysis, including cache behavior.