What is the explication for the difference execution time for the same instruction?

Question

As you know when we run instruction in our code

like long a = b;
we will not have the same ticks each to be executed.
first exeution it take 2ticks;
second exeution it take 3ticks;
third exeution it take 2ticks;

It depends for memory state, caches, instruction pipeline, branch prediction.

For the memory state:

We will have different time execution because the state of memory is not the same for situation 1,2,3,.. OS can do the allocation in 2 tick and next time it will need more time like 3 tick because lot of program change the state of the memory.

The example above was one of examples which they change the execution time, their are other examples that i need to understand, like how can caches, instruction pipeline, branch prediction effect this variation.

Please can someone explain it to me.

And also I need to know if the time of affected by each operation is the kernel time or user time for the process which execute the instruction.

Answer 1

Modern CPUs don't do one instruction at a time. Instead, they might be decoding one group of instructions while an earlier group are waiting for dependencies and waiting to be sent to execution units, while even earlier instructions are being executed, while even earlier instructions are being retired (committed to state). It's (literally) a pipeline of stages where many instructions are "in flight" at various stages at the same time.

How long an instruction takes depends on so many different things (what it depends on and when those dependencies are satisfied, what else is happening at each stage in the pipeline as it passes through). This is what causes the variability in how long an instruction takes.

For instructions that read from memory things get more complicated - in addition to everything else, they also depend on how quickly the data can be obtained, which depends on where the data has to come from (a very close store forwarding buffer, a close L1 data cache, a nearby L2 data cache, ..., all the way through a quickpath link to a memory controller that's able to talk to the actual RAM chip) and also depend on things like bandwidth utilisation along the paths the data needs to take (e.g. if the RAM chips are flat out handling something else, then you're going to have to wait your turn).

On top of all of that; there's higher level things to consider. If an instruction reads or writes to memory, then maybe that causes TLB miss and the CPU has to do a page table walk. Maybe the TLB miss becomes a page fault and the OS's kernel has load data from a memory mapped file. Maybe the memory mapped file is on an networked file system. Maybe the network connection has a high number of packet errors. Maybe it takes a full 10 seconds for all of this to happen before the instruction is retried and is able to complete.

Answer 2

If you're talking about the difference between 2 ticks and 3 ticks, it could simply be that, for a given execution, you started counting ticks early or late in a single tick cycle, and that the execution times are actually identical.

You should look into using timers with a higher precision than ticks; ticks are a very coarse measurement.

Answer 3

This question is too broad; there are too many factors that could contribute to the fluctuations in the time taken to execute some source code.

The poorly-written question also doesn't help - it is unclear whether the asker is more interested in knowing the possible factors that affect nanoscopic performance (on the order of 1 - 10 CPU instructions) or macroscopic performance (on the order of millions to billions of CPU instructions, i.e. on a timescale that is perceivable and relevant to a human).

Therefore, despite me trying to write an answer (to cover some factors that hasn't been mentioned so far), this question still has my downvote.

---

Because of a knowledge gap, no amount of explanation is going to help. The asker is encouraged to borrow a copy of this book from a local library or close friend:

Computer Architecture, Fifth Edition: A Quantitative Approach (The Morgan Kaufmann Series in Computer Architecture and Design)

---

The factors listed below are patently non-exhaustive. There are infinitely many factors, including CPU temperature throttling, which could arguably be influenced by cosmic rays raining down on your computer or a butterfly flapping wings on the other side of the Earth.

_{This dry humor is intended to soften the emotional damage from the harsh words in this answer.}

---

Some factors that contribute to fluctuations in the execution time on the nano-scopic level:

• A bubble in the pipeline (en.wikipedia.org)

  • A bubble can be caused by anything - anything deemed by the designers of the CPU that would prevent the next instruction from being executed immediately. Examples are: all execution units are busy; the input value to the instruction is still being computed (by a previous instruction), the input value is still being loaded from memory and hasn't yet arrived, etc.

• Design limitations (imperfections) in superscalar architecture

  • In an ideal world, a superscalar architecture should be able to schedule up to the theoretically optimum. In practice, sometimes it might generate a bubble despite having the input values and execution unit available. This is due to imperfection of the design.

• The CPU running at a different (fluctuating) frequency than the clock

  • Thanks to the creativity and resourcefulness of CPU vendors, a CPU can run somewhat faster, or somewhat slower than the advertised "normal speed", depending on the workload of the CPU.

• But isn't the clock supposed to run at the same frequency as the CPU's execution units?

  • No. Most new CPUs implement something called Invariant TSC, which means the TSC (the highest-resolution timer you'll find on a computer, specifically on the CPU) will run at a constant (advertised) frequency, unaffected by the frequency fluctuations of the execution.

• Cache, as pointed out in the other answers.

---

I need to do a nano-benchmark, and I want my results to be comparable and repeatable. How to I minimize these nanoscopic fluctuations?

• Turn off the frequency scaling features of the CPU when you conduct your benchmarks.

  • This may require restarting the computer for the changes to take effect.

• Cache Warm-up.

• Take a look at the disassembly (CPU instructions) that are being generated, to get a sense of how it will play out with the superscalar architecture. Unfortunately, you can only get a fuzzy insight from this, and typically you have no influence over how such low-level machine code is generated or executed.

• The CPU vendor may have tools that help gather insights such as cache misses and/or CPU pipeline stalls (bubbles).

---

Some factors that contribute to fluctuations on the microscopic level:

• Just-in-time compilation (as opposed to ahead-of-time compilation) if your test code is written in a managed language (such as C#, .NET, Java, or many other high-level languages).

---

Some factors that contribute to fluctuations on the milli-scopic level:

• Context switching
  • Open up the task manager (on Windows or Ubuntu), or top (on Linux command-line), and you will see many background processes running in the operating system in addition to your test code.
    • (You might need to flip a switch to see "all background processes".)
  • Once a while, your test program will be interrupted (or preempted), which means it will take a pause from execution, and the CPU will be told by the OS to execute something else instead.
  • If your test code is very CPU intensive, it will occupy a very high percentage of the CPU's time, but still it will not be a full 100 percent. It might be more like 95 - 98 percent.