Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Operation Costs in CPU Clock Cycles

ithare.com

Post reply on HN
Print view View original

41–50 of 69 posts

Re: Operation Costs in CPU Clock Cycles

#41

Post by no-bugs »

acchow wrote: post #4
falcolas wrote: post #3

The small difference between direct C calls and virtual C++ calls surprised me, actually. I thought it would be much bigger.

A virtual call in C++ is just a vtable lookup then a direct C call. Literally one pointer away. (or perhaps one pointer then one integer addition away? For the offset)

However, the address of this C call is calculated, which means that branch prediction (and the cost of potential misprediction) is involved. So additional cost we're talking about, is roughly a cost of L1 read (3-4 clocks by itself) - plus (0-<cost-of-branch-misprediction))

Re: Operation Costs in CPU Clock Cycles

#42

Post by jdub »

kikoreis wrote: post #30
jdub wrote: post #24

Earlier quoted context omitted.

I don't think there's much NUMA action on single socket at the moment, but as CPU area increases and more of the transistors are not actually doing CPU work (to spread out the heat-making bits) which increases distances on a single die, this will change.

Unless there is core-specific RAM on the die, why? Isn't the essential aspect of NUMA the fact that there is some memory which is "near", and some which is "far"?

Yeah, as distance (latency) to RAM increases, the amount of on-die cache increases (another handy way to distribute heat with a performance bonus) and coherency becomes more costly, so in effect it becomes the core-specific RAM you mention.

(Oh, hi Kiko!)

Re: Operation Costs in CPU Clock Cycles

#43

Post by no-bugs »

gpderetta wrote: post #11
jackmott wrote: post #6

Earlier quoted context omitted.

one pointer can be as slow as a sqrt if it isn't in cache.

The cost of virtual calls (and calls in general) in the article is greatly exaggerated. Jumps, calls and indirect calls have an effective latency of zero as they are resolved in the fetch stage (and speculated if the target is not known) and a troughput of one taken jump every one or two cycles. In a virtual call, the offset computation and load is only used to compute the jump target (which is only used later on com…

> The cost of virtual cals is usually due to missed optimizations and the possibility of misprediction.

Yep (plus one L1 read to get that VMT pointer). And the OP is pretty much consistent with this (at least within declared "indications of the order of magnitude" precision).

Re: Operation Costs in CPU Clock Cycles

#44

Post by no-bugs »

fdsaaf wrote: post #29

I am extremely skeptical of "full" rows in the table, the ones that purport to measure the overall costs of cache invalidation. These costs are so workload specific that a single number is meaningless and likely to mislead. My own benchmarks show costs that are nowhere near the ones cited.

> My own benchmarks show costs that are nowhere near the ones cited.

This is heavily dependent on the benchmark. In the OP, there is a ref to an academic research showing these numbers - and from my own real-world experience (NOT artificial benchmarks), the costs of 10K-100K are very usual. From a completely different perspective - there should be reasons why nginx beats Apache performance-wise :-).

Re: Operation Costs in CPU Clock Cycles

#45

Post by glangdale »

In places, this is quite simple-minded, though there is a nod to the distinction between throughput and latency. A function call may effectively cost nothing; if the function and its caller do useful work, a few store/load pairs (save and restore registers) and correctly predicted return address may be a handful of microoperations merged in with a stream of other instructions. The idea that there is 20-50 cycles of actual cost from a function call is outlandish.

Similarly, the virtual function call number looks way out of whack as long as the indirect branch target is correctly predicted (which, if the use of virtual functions is substituting for a more straightforward approach, is likely - and if it's quite unpredictable where the indirect branch in your virtual function call would go, any other approach probably just moves the branch mispredict somewhere else).

The numbers are not overall "crazy-wrong", but there is a tone of precision and certainty to them that is a bit deceptive. Talking about how much an operation costs is pointless; build things one way, measure that, then make the smallest change possible and measure that. Most of these costs make sense only in context (if you're on a critical path, measure latency, if you're on oversubscribed execution resource, measure throughput, etc).

Re: Operation Costs in CPU Clock Cycles

#46

Post by AlphaSite »

jdub wrote: post #24
CountSessine wrote: post #21

This is a fantastic resource; kudos to the author. But there is one thing in this reference that I found unexpected: One further thing which is related to memory accesses and performance, is rarely observed on desktops (as it requires multi-socket machines – not to be confused with multi-core ones ... When multiple sockets are involved, modern CPUs tend to implement so-called NUMA architecture, with each processor (w…

I don't think there's much NUMA action on single socket at the moment, but as CPU area increases and more of the transistors are not actually doing CPU work (to spread out the heat-making bits) which increases distances on a single die, this will change.

Are core specific caches write through or write Back?

Re: Operation Costs in CPU Clock Cycles

#47

Post by no-bugs »

glangdale wrote: post #45

In places, this is quite simple-minded, though there is a nod to the distinction between throughput and latency. A function call may effectively cost nothing; if the function and its caller do useful work, a few store/load pairs (save and restore registers) and correctly predicted return address may be a handful of microoperations merged in with a stream of other instructions. The idea that there is 20-50 cycles of a…

> may be a handful of microoperations merged in with a stream of other instructions.

It may indeed in theory, but most of the time in real-world it won't. And BTW - let's not forget about implicit costs of being unable to inline (which can be huuuuuge). Speaking of the real-world - we've just got our article accepted, presenting supposedly the fastest universal hashing function as of today (in spite of math being more heavy compared to the existing ones) - and the numbers in the OP are consistent with our real-world experiences while we were optimising it (well, within an order of magnitude at least).

> but there is a tone of precision and certainty to them that is a bit deceptive.

OP: "Last but not least, a word of caution: all the estimates here are just indications of the order of magnitude".

> Talking about how much an operation costs is pointless; build things one way, measure that, then make the smallest change possible and measure that.

Sure. The problem is that almost-nobody has time to do it in real-world projects. Which leads to even cruder estimates (such as "virtual function calls costs are negligible, regardless of the number of times they're called") being used - causing lots of crazily inefficient programs. IMO, OP is a reasonable middle ground between an all-out quasi-stationary testing and even worse guesstimates ;-).

Re: Operation Costs in CPU Clock Cycles

#48

Post by exDM69 »

eloff wrote: post #9
currysoup_t wrote: post #7

Earlier quoted context omitted.

As usual, memory access is the expensive operation. If the virtual function is already in L1 cache a virtual function should be only a minor slowdown. If it's all the way off in main memory it will be significantly slower. Eric Brumer has a great talk on this: https://channel9.msdn.com/Events/Build/2013/4-329

Exactly. Calling a virtual function in a tight loop, almost indistinguishable from a direct (non-inlined) function call. Calling a virtual function every now and then, much more expensive, but also not as likely to matter much to the performance of your program on the whole anyway. Still worth noting that every VM like Java or .NET or LuaJIT will optimize for the case that a virtual call usually has only one or two c…

Virtual function / function pointer calls can still have a big performance impact, especially if it could be inlined away.

Compare C standard library qsort with C++ std::sort performance for sorting integers. The difference is huge in favor of std::sort. If you write your own qsort and put it in a header file so the indirect calls can be inlined, they should be equal.

Re: Operation Costs in CPU Clock Cycles

#49

Post by eloff »

JoshTriplett wrote: post #40
eloff wrote: post #38

Earlier quoted context omitted.

It absolutely is fair. For a long time after a syscall your program will run slower thanks to the increased cache misses from the kernel clobbering your stuff in cache. That's a real price that you pay for a syscall and it would be wrong not to count it. However, if you found some other way of doing the work, e.g user code, kernel bypass, amortized bulk syscall, those will also have a (lesser) effect on the cache. So…

If you have enough CPU cache, the CPU will cache both kernel and user code/data for your process. If you run long enough and access enough user data that the kernel bits get evicted, then you'll take more of a performance hit, but the same thing applies to accessing enough user data that different parts of your user data get evicted.

Maybe this is more reflective on the kinds of software I work on, but I don't find that I have enough cache. So syscalls always come at a steep price. In fact I am tempted to break up one program into multiple processes and use the cache partitioning in Xeon v4 to prevent the different parts of my program from clobbering it's own cache.

Re: Operation Costs in CPU Clock Cycles

#50

Post by taneq »

logicallee wrote: post #25

For people who make interactive applications, here is an interesting thing to add: Making a user interpret an error message or notification of some kind (8 seconds) and have to dismiss a window (3 seconds) rather than be able to continue seamlessly: 44,000,000,000 operations, or 275,000,000,000 operations if we include the idling GPU. Distance light travels in this time: around the world 77 times, all while we keep t…

If you want to put it that way, you can think of information in the user's brain as being stored in peripheral memory at the end of a horribly slow, high-latency, unreliable bus. :)
Post reply on HN