I like this chart. In particular, I like that they break apart "thread context switch (direct costs)" and "thread context switch (total costs, including cache invalidation)". I've often heard that context switches are cheap because people only consider the direct costs.
Operation Costs in CPU Clock Cycles
61–69 of 69 posts
Re: Operation Costs in CPU Clock Cycles
#62i'm curious where this information comes from. a lot of it jars heavily against personal experience and measurements i can do for myself. the idea that floating point division is that much more expensive than multiplication for instance... the only difference afaik is latency, not timing. the idea that an indirect call and a virtual function call are so close as well... when it is a read followed by an indirect call-…
There is a "references" section at the bottom:
[Agner4] Agner Fog, “Instruction tables. Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs”
[Agner3] Agner Fog, “The microarchitecture of Intel, AMD and VIA CPUs. An optimization guide for assembly programmers and compiler makers”
[Intel.Skylake] “Intel® 64 and IA-32 Architectures Optimization Reference Manual”, 2-6, Intel
[Levinthal] David Levinthal, “Performance Analysis Guide for Intel® CoreTM i7 Processor and Intel® XeonTM 5500 processors”, 22
[NoBugs] 'No Bugs' Hare, “C++ for Games: Performance. Allocations and Data Locality”
[AlBahra] Samy Al Bahra, “Nonblocking Algorithms and Scalable Multicore Programming”
[eruskin] http://assemblyrequired.crashworks.org/how-slow-are-virtual-...
[Agner1] Agner Fog, “Optimizing software in C++. An optimization guide for Windows, Linux and Mac platforms”
[Efficient C++] Dov Bulka, David Mayhew, “Efficient C++: Performance Programming Techniques”Amazon, p. 115
[Drepper] Ulrich Drepper, “Memory part 5: What programmers can do”, section 6.2.2
[TCMalloc] Sanjay Ghemawat, Paul Menage, “TCMalloc : Thread-Caching Malloc”
[Wikipedia.ProtectionRing] “Protection Ring”, Wikipedia
[Ongaro] Diego Ongaro, “The Cost of Exceptions of C++”
[LiEtAl] Chuanpeng Li, Chen Ding, Kai Shen, “Quantifying The Cost of Context Switch”
Re: Operation Costs in CPU Clock Cycles
#63Earlier quoted context omitted.
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).
No, the load is not on the critical path, so it is not normally part of the overhead.
Re: Operation Costs in CPU Clock Cycles
#64I like this chart. In particular, I like that they break apart "thread context switch (direct costs)" and "thread context switch (total costs, including cache invalidation)". I've often heard that context switches are cheap because people only consider the direct costs.
Context switches are cheap because context switches are cheap. You can, with enough finnegaling, make the "indirect costs" of anything arbitrarily high.
Re: Operation Costs in CPU Clock Cycles
#65Earlier quoted context omitted.
I have been working in this area for 10 years, made millions of dollars of revenue from a product that was largely dependent on getting this sort of thing right, sold a startup to Intel whose main business was in this area, and work for Intel. I'm not 100% sure you are well situated to lecture me about the 'real world' because you wrote an academic paper. Congratulations on getting a paper accepted (and would be inte…
> made millions of dollars of revenue... I'm not 100% sure you are well situated to lecture me about the 'real world' because you wrote an academic paper. So, we're going to discuss millions of dollars instead, sigh... This way Trump should be one of the best programmers in the universe, I guess. > Typically it will be inherently cheaper than 15-30 cycles - but lost opportunities for optimization may take you to numb…
I don't think Trump made his money doing low-level performance programming for the past 10 years, so I'm not sure your analogy is valid.
However, since you, whoever you are, have not only written a hash table, but discovered profundities like 'Sometimes list costs 780x as much as vector for "absolutely zero reason"', and 'don't try to offload 100 cycles of work to another thread' I'm going to defer to your expertise. I recommend you stick a bone through your beard, pronounce yourself a performance guru, and make bank. Have fun.
Re: Operation Costs in CPU Clock Cycles
#66i'm curious where this information comes from. a lot of it jars heavily against personal experience and measurements i can do for myself. the idea that floating point division is that much more expensive than multiplication for instance... the only difference afaik is latency, not timing. the idea that an indirect call and a virtual function call are so close as well... when it is a read followed by an indirect call-…
Multiplies are significantly cheaper than divisions in most recent processors.
First of all latency is the most important parameter: after memory bandwith, the latency of the longest dependency chain is tipically the bottleneck, especially for floating point code.
For example on Skylake float muls have 4 cycle latency (same as adds and MADs) vs over a minimum of 14 cycles for divisions.
But even when only cosidering thoughput, Skylake has two fully pipelined MAD units and can start 2 multiplies every clock cycle, while its single division unit is only partially pipelined and can start a new div only every fourth clock cycle (it is also, IIRC, only 128 bit wide so 256 bits vector divs are more expensive still).
Avoiding divs (and mods) is something that it is still worth optimising for.
Re: Operation Costs in CPU Clock Cycles
#67Earlier 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.
Are core specific caches write through or write Back?
I think that they're always write-back, but it gets complicated with the different levels and it's different between Intel and AMD - my understanding is that Intel uses an 'inclusive' method where everything that's in a higher-level cache line will also be in a lower-level cache line; i.e. if something is in L1 it will always also be in L2 and L3, but then with AMD's exclusive scheme L1 or L2, when clearing a dirty line, can/will effectively 'write-around' L2 or L3 straight to a lower level.
Re: Operation Costs in CPU Clock Cycles
#68Earlier quoted context omitted.
> made millions of dollars of revenue... I'm not 100% sure you are well situated to lecture me about the 'real world' because you wrote an academic paper. So, we're going to discuss millions of dollars instead, sigh... This way Trump should be one of the best programmers in the universe, I guess. > Typically it will be inherently cheaper than 15-30 cycles - but lost opportunities for optimization may take you to numb…
I don't think Trump made his money doing low-level performance programming for the past 10 years, so I'm not sure your analogy is valid. However, since you, whoever you are, have not only written a hash table, but discovered profundities like 'Sometimes list costs 780x as much as vector for "absolutely zero reason"', and 'don't try to offload 100 cycles of work to another thread' I'm going to defer to your expertise.…
> I recommend you stick a bone through your beard, pronounce yourself a performance guru, and make bank. Have fun.
:-) :-) I LOVE when my opponent has to resort to personal insults :-). Leaving aside any sarcastic remarks in this regard:
For Intel's sake I Really Hope that these "profundities" are indeed very well-known to you - and believe it or not, they're very well-known to me too for at least 10 years. However, this is not the point; the point is that there are LOTS of developers out there who do NOT know them - and the OP is intended for them (and not for "performance gurus").
It is actually THIS simple. Eliminating 90% of inefficiency does not really require black magic or "performance gurus" who know exactly how the pipeline of specific CPU works. And this is exactly what I'm arguing for - to educate app-level developers and architects about this low-hanging fruit of 10x+ inefficiencies; I can assure you that it is very far from being universal knowledge in app-level development circles.
Re: Operation Costs in CPU Clock Cycles
#69Earlier quoted context omitted.
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!)
Hey Jeff.. the nick fonts are really small on HN; I didn't see it was you!
I don't think latency to near RAM will increase; it would have too material a performance impact. Even in disaggregated designs like Rackscale there is definitely a concept of "near RAM", which is not cache, but which has very low latency.
However, your post made me realize that as the number of cores go up, as with KNL, they are likely to be organized hierarchically with some clustered sharing of cache, so indeed NUMA-style affinity of workload to core starts paying off there. IOW, if you have thousands of cores on a chip, they definitely aren't going to be all sharing the same L2 and L3.