Most of these latencies were measured and written up for a bunch of systems by Carl Staelin and I back in the 1990's. There is a usenix paper that describes how it was done and the benchmarks are open source, you can apt-get them.
His standard interview question is to show the candidate that graph and say "tell me everything you can about this processor and memory system". It's usually a 2 hour conversation if the candidate is good.
lmbench was trying to give you both bandwidths and latencies of everything in a computer system, not just memory. This is one place where it is actually worth memorizing the rough numbers, they help immensely when you are sketching out a design. lmbench tried to give you insight into latency/bw of network, disks, memory, etc.
Do you know, to the nearest order of magnitude
round trip time over the network
bandwidth over your data center's network
seek time end to end (not the silly 1/3rd seek / no rot delay)
bandwidth at the fast end
bandwidth at the slow end
memory read / write / bcopy bandwidth
random read from memory
I've sat in hundreds of design meetings where someone was claiming they'd build an XYZ server that did $BIG_NUMBER of ops/sec and I'd just stare at the ceiling, think about the network, and go "Maybe" or "not possible" based on the numbers. There must have been some time that I was wrong but I don't remember it.
It's somewhat harder today because all the big machines have multiple cores so it's not as simple as knowing what 1 core, with 1 network interface can do, but you should at least know that, you can assume linear scaling as an upper bound and have some idea of the capacity of the machine.
It's always amazed me how easy it is to get a feel for these numbers and yet many people in the biz don't take the time to do so. I can only guess they think it is harder than it actually is.
Latency does not prevent X opps/second. It's not that hard to build a server that does a simple transaction 100,000 times a second. Keeping synchronized across several machines at that throughput level can be next to impossible.
Pedantic quip: I have a hard time believing you guys were measuring half nanosecond cache latencies on a machine with a 100MHz clock. :)
And actually the cache numbers seem optimistic, if anything. My memory is that a L1 cache hit on SNB is 5 cycles, which is 2-3x as long as that table shows.
We didn't believe it either until we put a logic analyzer on the bus and found that the numbers were spot with respect to the number of cycles. I don't remember how far off they were but it wasn't much, all the hardware dudes were amazed that software could get that close.
tl;dr: the numbers were accurate to the # of cycles, might have been as much as 1/2 of 1 cycle off.
Edit: I should add this was almost 20 years ago, I dunno how well it works today. Sec, lemme go test on a local machine.
OK, I ran on a Intel(R) Core(TM) i7-3930K CPU @ 3.20GHz (I think that's a Sandy Bridge) that is overclocked to 4289 MHz according to mhz, and it looks to me like that machine takes 4 cycles to do a L1 load. That sound right? lmbench says 4.05 cycles.
That mem_lat3 is pretty interesting, is there more info about it anywhere? Do you know what "Latency" refers to? Is that for Sandy Bridge consumer quad core? (hence ending at 8MB since that is L3$ size...)?
Wasn't aware of it, so thanks for the question. I took a quick look and it looks like Agner is using performance counters, which, while being more accurate, are platform specific. One of the goals of lmbench was to be accurate across different platforms and CPU architectures. So it's all userland software only.
You can get pretty far that way, Carl wrote a userland tool called mhz that has been working without modification since around 1998 (when the fastest clock rate was 600mhz on an alpha). Still pretty accurate to this day when CPUs have clock rates 7x faster and fairly different architectures.
Honestly, I'd rather programmers know how to _measure_ these numbers than just have them memorized.
I mean, if I told them that their machine had L3 cache now, what would they do find out how that changes things? (This comment is also a shameless plug for the fantastic CS:APP book out of CMU).
Honest question: how would you measure an L2 cache lookup? (What program would I need to write which ensures that a value is stored in L2, such that when I read it later, I would know the lookup time to indeed be the L2 time?)
At that, how would one measure this kind of thing at the nanoseconds level? Would using C's clock_gettime() functions be good enough? Is there any other facility to count cycles which have passed between two operations?
cracks knuckles Let's see if I remember enough of what I'm supposed to know in an exam in a couple of months or so.
You need to know the size of a page in your L1 cache. Then you can write a program that goes through a big enough chunk of memory that an "out of space" error occurs predictably in L1 cache, but not in L2 cache.
That way you can know when specifically your program went to L2 cache to swap out a page of L1 cache when it was needed.
The caveat being that you can probably only do this well enough in some sort of assembler code (for your architecture) and that you would have to be running a single-process system without interrupts enabled. Otherwise all sorts of things can mess up your cache lookups.
That's actually not good enough, because modern CPUs have prefetchers, so if you just access a 33kB chunk sequentially, it will still almost always be from L1 (the prefetcher proabably uses misses to train, so you'll have a few misses before it catches up), even if the L1 is just 32kB.
To predictably miss caches you need to have a random access pattern.
Well, back in the early 90's, HP RISC was the only cache controller we found that had cache line prefetch. If you keep increasing your stride you eventually get to a big enough one that you are skipping enough cache lines that they stopped fetching.
We switched to going backwards, that fooled them for a while but now most cache controllers seem to detect forwards, backwards, and uniform strides, which is actually pretty neat.
So yeah, today it would seem that random is what you need.
What you could do is write a program that uses increasing amounts of memory. Measure the time it takes to complete a few million iterations of some function that accesses that memory. As the total usage increases, you'll see steps in the timing. For example, you might see a jump at ~32K, then ~2MB, then ~8MB.
I think you'd just need to access memory in increasingly larger increments (eg, sequential reads of 32k, 64k, ...2x size of l2 cache). But there's more to it as the L2 cache is often shared amongst cores in a multi-cpu system (where as the L1 is per-core). Also, the organization of the cache (eg, n-way set associative) means that you'd want to vary the size of the jump (stride) for your reads/writes and see how that also affects throughput.
>But there's more to it as the L2 cache is often shared amongst cores in a multi-cpu system (where as the L1 is per-core)
As comatose_kid notes, this is highly dependent on CPU architecture. Intel's architectures from Nehalem to the current Ivy Bridge have smaller per-core L2 caches, and a shared L3 cache across all cores.
You can't just access memory in that pattern because an out of order processor will just issuse the next N loads in parallel. Instead lmbench sets up a linked list in memory ans walks the list. That way the address for each load is not known until the previous load completes. -Wayne
I don't know how you actually measure how long a lookup takes, but just FYI if you're interested in the number of lookups you're doing from the various caches (and in things like number of missed branch predictions you're causing), you can use OProfile or Cachegrind. OProfile is a bit more complicated to set up because the flags you need to set are processor-specific, but it causes much less slowdown.
I love performance counters and good profile tools. But the whole point of knowning this stuff is to get a handle on expected performance before you have written a line of code. Then you can make good decisions about what to do. Later the profile tools can help you fix what is broken when your code doesn't match expectations.
+1 to CS: APP (Computer Systems: A Programmer's Perspective, by Bryant and O'Hallaron). I thought Computer Architecture: A Quantitative Approach by Hennessey was dry and better suited to EE's. CS: APP, on the other hand, really sucked me in - and I'm not the kind of guy that typically gets enthralled by CS texts.
My problem with the memorization approach is that the technology is still moving quickly enough that the orders of magnitude still "wiggle," particularly in the middle numbers.
For example, at a glance, the disk seek numbers are off by orders of magnitude for SSD drives. And the 1MB of RAM read numbers appear not to have used the SSE streaming load/store instructions. I don't know anything about datacenters, but I'd certainly want to measure that one myself before building a system assuming that number was in its correct place in the hierarchy.
I've love to able to either measure or use all this lovely information in my running Linux desktop GUI app. But I happen to know that would probably not be worth my time except some rather specific cases. Plus the direction of PC architecture seems to be towards more and more levels of cache and that implies more and more work if you actually take these into account.
Just finding the time that library calls take is quite a pain in Linux.
Given all this, I'm inclined to think that I'd rather architect cache-oblivious data structures than root-around endless when background threads and other stuff suddenly get slow...
This reminds me of one of the pages that Google has internally that, very roughly, breaks down the cost of various things so you can calculate equivalencies.
As an example of what I mean (i.e., these numbers and equivalencies are completely pulled out of thin-air and I am not asserting these in any way):
* 1 Engineer-year = $100,000
* 25T of RAM = 1 Engineer-week
* 1ms of display latency = 1 Engineer-year
This allows engineeers to calculate tradeoffs when they're building things and to optimize their time for business impact. E.g.: it's not worth optimizing memory usage by itself, Latency is king, Don't waste your time shaving yaks, etc etc.
Yet everyone uses much slower RAM in servers and will likely continue to do so, all the while caches swell, etc.
Optimizing memory usage is almost irrelevant today, until it starts being a bandwidth problem, and that's still solvable but only through complex scaling strategies that also cost several engineer-years.
These numbers by Jeff Dean are relatively true but need to be refreshed for modern DRAM modules & controllers. Specifically, the main memory latency numbers are more applicable to DDR2 RAM vs the now widely deployed DDR3/DDR4 RAM (more channels = more latency). This has been a industry trend for a while and theres no change on the horizon. Additionally, memory access becomes more expensive because of CPU cross chatter when validating data loads across caches.
A potential pitfall with these numbers is they give engineers a false sense of security. They serve as a great conceptual aid - network/disk I/O are expensive and memory access is relatively cheap but engineers take that to an extreme, and get lackadaisical about memory access.
When utilizing a massive index (btree) our search engine failed to meet SLA because of memory access patterns. Our engineers tried things at the system (numa policy) and application level (different userspace memory managers, etc.)
Ultimately, it all came down to improving the efficiency around memory access. We used Low-Level Data Structure to get the 2x improvements in memory latency:
Scaling up to human timeframes, one billion to one:
Pull the trigger on a drill in your hand 0.5s
Pick up a drill from where you put it down 5s
Find the right bit in the case 7s
Change bits 25s
Go get the toolkit from the truck 100s
Go to the store, buy a new tool 3000s
Work from noon until 5:30 20000s
Part won't be in for three days 250000s
Part won't be in until next week 500000s
Almost four months 10000000s
8 months 20000000s
Five years. 150000000s
This is the same basic advice that I try to keep in mind when writing English text. A word that the reader already knows is in "L1." A word they have to stop and think about is an L1 miss. If they have to reach for the dictionary, it's an L2 miss -- and probably several more cycles for a line fill, as they get distracted reading the next few entries in the dictionary.
As programmers, Strunk & White might have made the list of the all-time greats.
This is shameless self promotion (well, me and Carl promotion) but we were measuring these sorts of things in the late 80's and wrote a paper about it that got best paper at Usenix in 95. I think we had most of those numbers, not in the same format.
Pissed off the BSD folks because it made them look bad. Oh, well.
Helped make Linux better, largely because while the BSD guys refused to engage, Linus did. He and I spent many many hours discussing what was the right thing to measure and what should not be measured. We both felt that lmbench would influence OS design (and it's influenced processor design, see all the cache prefetch stuff, I'm pretty convinced that's because all the processor people used lmbench). Linus was already on the "OS should be cheap path" but lmbench helped him make the case to other people who wanted to add overhead because of their pet project.
The cool part about working with Linus was he was never about making Linux look better, he was about measuring the right things. If Linux sucked, oh, well, he'd fix it or get someone else to fix it. Awesome attitude, I feel the same way.
The only published work that might predate lmbench for these sorts of numbers is Hennessy and Patterson computer architecture. They talked about memory latency but so far as I recall, didn't have a benchmark. That said, that book is friggin awesome and anyone who cares about this sort of thing and hasn't carefully read that book is missing out.
For anyone thinking about watching: the presentation is incredibly good. The name is kinda misleading -- they talk more about modern x86 architecture and actual numbers of various algorithms than the lock free algorithms themselves. Both of those guys have a high emphasis on measuring and testing to improve performance.
Considering that so many programmers are currently enthralled with JavaScript, Ruby, Python and other very very high level languages, the top half of this chart must look very mysterious and unattainable.
Agreed, I think the real lesson is: reading is 10x cheaper than branching, so if you can do something with 10 non-branching ops it'll be just as fast as a single branch.
There are definite rules, documented by the CPU vendor. A forward branch is assumed not taken, while a backward branch is assumed to come at the end of a loop that will probably iterate more than once. See http://software.intel.com/en-us/articles/branch-and-loop-reo... for example.
I'd assume the particulars will vary between CPU manufacturers and families, but the idea that backward branches will probably be taken seems fairly universal.
This is outdated information; Intel chips have not used static prediction for conditional branches since NetBurst (Pentium 4).
"Pentium M, Intel Core Solo and Intel Core Duo processors do not statically predict
conditional branches according to the jump direction. All conditional branches are
dynamically predicted, even at first appearance."
Depends on data dependencies and the number of registers, but yes, L1 latency is rarely the bottleneck (more likely to be load/store throughput, in-register shuffles, or arithmetic dependencies for such tight kernels).
The thing here that is eye opening to me, and relevant to any web programmer, is that accessing something from memory from another box in the same datacenter is about 25x times as fast as accessing something from disk locally. I would not have guessed that!
Such items are important to web developers and they can use them to justify looking at one or other technology. Or perhaps attempt at least benchmarking and have them as one of the guides in configuring and setting up services. Comes to mind why is Redis can be better then mongodb and in what configuration.
As well in discussion about this and that these can be of help too.
Adding misaligned memory penalties such as on word boundary and page boundary can enhance such document. This might be a good cheatsheet if one inclined to research and make one.
Also, these numbers don't mean much on their own. E.g. L2 Cache is faster than main memory, but that doesn't help you if you don't know how big your L2 Cache is. Same for main memory vs. disc.
E.g. I optimized a computer vision algorithm for using L2 and L3 caches properly (trying to reuse images or parts of images still in the caches). Started off with an Intel Xeon: 256KB L2 Cache, 12MB L3 Cache. Moved on to an AMD Opteron: 512KB L2 Cache (yay), 6MB L3 Cache (damn).
Also, the concept of the L2 Cache has changed. Before multi-cores it was bigger and the last-level-cache. Now it has become smaller and the L3 Cache is the last-level-cache, but has some extra issues due to the sharing with other cores.
The important concepts every programmer should know are memory hierarchy and network latency. The individual numbers can be looked up on a case-by-case basis.
I assume that the mutex's memory is warmed, so the processor doesn't have to go to RAM. But, it does have to synchronize with any other processors/cores in the machine to prevent them from locking the mutex at the same time.
In a Intel Nahalem or Sandy Bridge system, this goes over the QuickPath Interconnect which has a latency of ~20ns. HyperTransport fills the same role in AMD systems, and probably has a similar latency, but I don't have numbers for that.
I'm basing this on this presentation, especially the architecture diagram at 2m 40s:
I actually don't think that's true. My understanding is that on x86, atomic instructions have implicit lock instructions before them. (Or you can make some instructions atomic by putting a lock instruction before them.) Such instructions lock the bus and prevent other cores or SMT threads from accessing memory. In that way, you can safely perform an atomic operation on a value in the cache.
Note that this implies that atomic operations slow down others cores and SMT threads.
Locks are often implemented using an xchg instruction, which is implicitely locked.
All processor's caches are committed/flushed for the affected cache line. So its correct to say other processors are slowed down. But it also in that sense IS a main memory operation, just not yours.
Just because a lock is shared does not mean that it's contended.
For example, some multi-threading techniques attempt to access only CPU-local data but use locks purely to guard against the case where a process is moved across CPUs in the middle of an operation (thus defeating the best-effort CPU-locality).
Maybe I'm missing something, but if the cache line is only in use by one CPU, I don't see why the value would need to be immediately propagated to main memory or to any other CPU's cache until it is written as part of the normal cache write-back.
Correct. Typically the cache snoops the main memory bus. If a remote CPU starts a read on a cached memory location, the caching CPU sends a "stall" or "retry" signal to the reader, does a cache flush to main memory, and then lets the remote CPU proceed with the (now correct) main memory read.
Does anyone feel like this is sort of an apples to oranges table? It compares reading one item from L1 cache to reading 1M byte from memory, without adjusting for the amount of data being read (10^6 more). It looks like the data was chosen to minimize the number of digits in the right column.
L3 is generally on the order of the same time as main memory - it's main purpose is to reduce the total amount of requests in order to conserve bandwidth
SSDs are on the order of 0.1ms, so 100,000 ns, give or take a factor of 10.
Someone smarter than me will have to answer the NUMA node question.
I think L3 is much faster; perhaps 1/3rd of main memory, assuming the line is available and not in another core. Here are some numbers for L3 cache, from Intel (probably specific to the 5500 series)[1]:
L3 CACHE hit, line unshared ~40 cycles
L3 CACHE hit, shared line in another core ~65 cycles
L3 CACHE hit, modified in another core ~75 cycles
remote L3 CACHE ~100-300 cycles
Local Dram ~60 ns
Remote Dram ~100 ns
I was trying to make the point that these numbers are somewhat arbitrary (i.e. why do I need to know the access speed to disc, when I keep everything in memory on a NUMA system?) and don't apply to all programmers (e.g. embedded systems may not have discs, L2 Caches or internet access).
I find myself thinking of figures like these every time I see results for benchmarks that barely touch the main memory brought up in debates about the relative merits of various programming languages.
When working on low latency distributed systems I more than once had to remind a client that it's a minimum of 19 milliseconds from New York to London, no matter how fast our software might be.
Interesting but unnecessary for most programmers today. I'd rather my programmers know the latency of redis vs memcached vs mysql and data type ranges.
Every programmer that understands (rather than "knows") the number mentioned in the link would know the numbers you are looking for (or at least, the relationships between those.)
I'm not sure this relation holds for the opposite direction.
Network transmit time is almost irrelevant. It takes orders of magnitude more time to call the kernel, copy data, and reschedule after the operation completes than the wiretime.
This paradox was the impetus behind Infiniband, virtual adapters, and a host of other paradigm changes that never caught on.
Part of the reason I wrote lmbench was to make sure that what you are saying is not true. And it is not in Linux, kernel entry and exit is well under 50 nanoseconds. Passing a token back and forth, round trip, in an AF_UNIX socket is 30 usecs. A ping over gig ether is 120 usecs.
Unless I'm completely misunderstanding, you are saying that the OS overhead should be "orders of magnitude" more than the network time, that's not at all what I'm seeing on Linux.
I guess what you are saying is that given an infinitely fast network, the overhead of actually doing something with the data is going to be the dominating term. Yeah, true, but when do we care about the infinitely fast network in a vacuum? We always want that data to do something so we have to pay something to actually deliver it to a user process. Linux is hands down the best at doing so, it's not free but it is way closer to free than any other OS I've seen.
Linux sounds fast. 50ns is blazingly fast. Benchmarks I surveyed show figures around 1-10usec but they are old and processors are faster now.
Kernel entry and exit are of course contributors to i/o overhead. Also include data copy time (2K times all those main memory flushes), ip stack time (well into scores of usec now) and driver overhead.
Add the latency of the result being signalled to your user-mode application. Interrupt latency, user-mode task scheduling time and if a receive then data copy time again.
Of course router delays are negligible on the backbone, but your local cable modem etc will add something.
I think we're over 16usec now, which if I did the math right is the wire time.
Another way to estimate all this is to benchmark achieved transfer rate peer-to-peer on an otherwise idle link. Folks report from 100mbit to 300mbit depending on other bottlenecks (disk speed, bus etc), but that's often using very large block sizes, not our 2K. Even so we see most of the Gigabit rate whittled away.
This may be ignorant and please correct if I am off base but given the same physical medium isn't sending 2k across the network the same cost whether you are at fastE or gigE? Given the network is not saturated?
fastE is 100Mbits/sec, gigE is 1000Mbits/sec, so given the same size packet, gigE is in theory 10x faster.
However, to make things work over copper I believe that gigE has a larger minimum packet size so it's not quite apples to apples on pings (latency).
For bandwidth, the max size (w/o non-standard jumbo grams), is the same, around 1500 bytes, and gigE is pretty much linear, you can do 120MB/sec over gigE (and I have many times) but only 12MB/sec over fastE.
Some day I need to do a post about what I learned from SGI's numa interconnect. I used to think big packets are good, that interconnect taught me that bigger is not better.
If I have 1000Mbits to send then gigE is 10 times faster. But in the article we are transferring only 2k across the network. Mixing latency and bandwidth here. The latency to send 2k across an empty network isn't 10 times greater on a fastE versus gigE network, right?
2K is going to be 2 packets, a full size and and a short packet, roughly 1.5K and .5K.
For any transfer there is the per packet overhead (running it through the software stack) plus the time to transfer the packet.
The first packet will, in practice, transfer very close to 10x faster, unless your software stack really sucks.
The second packet is a 1/3rd size packet so the overhead of the stack will be proportionally larger.
And it matters _a lot_ if you are counting the connect time for a TCP socket. If this is a hot potato type of test then the TCP connection is hot. If it is connect, send the data, disconnect, that's going to be a very different answer.
Not sure if I'm helping or not here, ask again if I'm not.
Someone should add basic numbers like ns count for 63 cycles modulo and that type of stuff -
That'll help bad devs realize why putting another useless cmp inside a loop is dumb, and why alt rows in a table should NEVER be implemented by use of a modulo, for example.
Yes I know that's not latency per se but in the end it is too.
I think if you're worried about whether or not you use modulo to calculate alternating table rows (and you don't work for Facebook), then you're almost certainly optimizing prematurely.
Some approaches are NOT acceptable, it's not about optimizing prematurely, it's about coding obvious crap.
While you may be used to the usual "code crap, fix later" and "waste cycles, there are too many of it" , it doesn't mean you're right.
Everyone says it but you're still running on C (linux, unix), you're still going nuts over scaling issues (lol nosql for everyone) and you're still paying your amazon cloud bill.
I know you're ranting to the world at large, but I am not "going nuts over scaling issues". All my websites are static HTML files. I regenerate them as needed using custom Python code and my "databases", which are text files in JSON.
I have several sites running on a single smallest Linode, and the CPU utilization virtually never cracks 1%.
Also, note that I am not advocating "coding crap". I'm talking about not berating coworkers over the nanosecond cost of an extra modulo inside a loop.
Quite to the contrary, the optimization of using any particular method to colour rows is so tiny it can easily be outweighed over its lifetime by the 50 or so extra keystrokes it needs to type. That's how trivial this is (which is why people are reacting to your extremely aggressive tone).
Indeed, I should drop the agression.
However, the subject is not optimization but coding correctly in the first place.
And the anti-optimization argument would be correct if:
-typing represented more than 1% of dev work
-code was never reused
-code was never massively used
-code had a short lifespan
So let me help you see clearly:
-I'm not a typist
-Every bad code tutorial out there creates millions of code bits that contain the N times slower version, with an aggregate impact that actually matters
-Any 10% opt mistake in a codebase like iptables would cause more carbon than you can imagine
-Fortran is still in use because it's the fastest language there is with the best math libraries.
Those seem to be eternal so far, and C seems to remain the only other relevant language throughout the short history of coding.
Sure, there are much more problematic cases than the dumb even odd example, but I picked that one because many would recognize it.
It does cost considerable time and brain bandwidth to learn to "code correctly" if coding correctly means knowing how to avoid every excess few nanoseconds.
If your code is expressive, easy to reason about and fast enough, then less expressive, harder to reason about and even faster code isn't more correct.
I suppose you are referring to the very particular case of the right shift, but as much as that's easily predictable, it's a corner case.
Who knows maybe the trend will be 3 colors instead of two.
Or maybe it'll be another instruction that's wrongly abused.
Or another compiler that actually sucks, like most JS interpreters.
The idea really is to use the simplest logical approach to the problem rather than the wrong one.
In the very well known case of the alt row table, it looks to me like we're alternating odd and even, why not just code that to start with, before any optimization ?
I find the modulo easier to read in this case, but I guess that's a question of taste. It's certainly not 'wrong' to use a modulo, and probably worth the trade off in most cases if it makes your code clearer.
Yes, sometimes the compiler can compensate bad decisions from the programmer, the jvm can collect your garbage etc. - none of these will save you from stupid data models and idiotic objects.
Indeed it should never be spelled wrong, as it means in itself in latin, my bad really.
Alt rows are a simple concept, the first row is odd, the next is even, etc.
A good step forward is an if/then/else or a switch or an unrolled loop - a huge step forward in terms of performance too, as a mod takes 63 cycles and a cmp takes almost nothing.
Unrolling loops is premature optimization, and we all should know what that is the equivalent of.
Unroll your loop once they are tried, tested, and working correctly, and a profiler finds out you spend much too time in the specific parts that would be discarded when unrolling.
The liberties you took with your pseudocode above prove the point: as others have noted, you've chosen premature optimization over using a fitting data type. The first could be easily fixed before release. The latter is harder.
> profile = function(fn) { var start = Date.now(); fn(); return Date.now() - start; }
> cmp = function() { for (var i=0; i < 1000000000; i++) { var z = 'odd' === 'even'; } }
> mod = function() { for (var i=0; i < 1000000000; i++) { var z = 101 % 2; } }
> prof(cmp)
20329
> prof(mod)
40792
Whether you think those 20 nanoseconds per test are worth saving is, I guess, an open question. :) I can imagine it being useful for game programming, for example.
I love fairy tail
Indeed you can do much better, flipping boolean + cmp if you only need two states, and integer + array if you need three or more - main thing is, even the "stupid" string comparison is much cheaper than a modulus, and it's a very logical basic approach that says " if the previous row was odd, this one must be even ".
My idea with that is that it's extremely important to reach that conclusion, as it matches the problem perfectly and thus is much more efficient than our (often natural) standard approach of mod(x,2).
When you've reached that step, you can further improve by using a boolean instead of a short string, but that steps clearly into optimization, as it's not "formulating the problem correctly" but "finding a better way to implement the same solution".
There is major cost in not formulating the problem correctly (even odd is an approach to alternating colors, not the problem itself), and mod for table rows is a prime example of that.
It might only be an example but if you're going to complain about people's inefficient/wrong code, the least you can do is provide a good demonstration.
As I said above, that's a better implementation of the same solution which is, pick two states and alternate by using the knowledge that if the previous is odd the next is even.
In essence your solution and the strcmp one follow the same logic, except yours is limited to two states as it is - but indeed the best n-state solution uses an array too.
What you posted here is a somewhat optimized implementation of the right solution, which is slightly better, like the boolean one (indeed you're using one bit that you flip ...).
But the BIG difference between the mod family of solutions and ours is that mod is over ten times slower because it does not correctly use the problem data.
I'm not the best coder there is, but I know it is much simpler to base yourself on something you already know (the state of the previous row) rather than doing additional computing because an analytical approach says alternating two colors is like having a color for even rows and one for odds.
By the way. your code is evil, if you're going to implement two-state logic, you're expected to use a boolean, and it will run faster with an if(b){str1}else{str2} than with an array that costs additional processing because of its nature (I'm talking straight out of my ass btw, but I still know it's inevitable that an array of two strings requires more bits and ops than two strings).
Also, the point of using an array for such an exercise would be to support n-state logic, yet your fake-boolean int approach makes it doubtful ;)
I'm not aware of any compiler that optimises such a structure to avoid branch misprediction. An array of two strings might require more bits and ops in an unoptimised interpreted language, or one in which bounds checking is always enabled, but I can assure you that an indexed load is 1 instruction and a load for each string is... well, more than that. You are right, you are definitely talking straight out of your ass!
The n-state solution is a state machine, btw - but it is right to use a simple solution if that is all your problem requires.
For 99% of code, worrying about the number of cycles in an operation is an utter waste of time. It just doesn't matter. Correctness and readability trump machine efficiency.
Do you work on real-time systems, embedded code, or something similar?
You are repeating a point of view you do not understand.
You don't know WHY people started saying that, WHEN they started and WHO started.
It was started by old people a while ago who told even older people that for the simple stuff they were writing for DESKTOP computers, it didn't matter anymore.
Indeed, if you have a 486dx4 and all you want to do is word processing, it didn't matter much wether it was optimized or microsoft word as the thing was way too powerful for that kind of stuff already.
Today, battery life is a concern, virtualization is a reality, scalability is a CORE issue, there are low power states etc.
Today, making your application 100 times more efficient gives you 10x more battery life,100x lower cloud hosting costs, 100x better scalability, etc.
Think that's unlikely ? You've been stacking inefficient blocks for a lifetime, sometimes with inefficiencies multiplying, where do you think you are today ?
Simple example, from a pgsql>jdbc>jboss>j2ee>hibernate>java report factory to a dumb php script that did simple SQL, you already have factors above 20 in favor of the simple solution.
That's before you make a better data model or even try using a fast language or a more suiting data store depending on your needs.
Besides, your argument is nonsense, the simplest most correct way IS the most efficient, that's the power of programming, there is absolutely NO compromise between reliability and efficiency in terms of code.
Readability is over rated, as long as you don't code crap, any COMPETENT coder will be able to read and understand fast enough, even without comments.
Do you work on overweight UIs that drain phone batteries or cloud-hosted applications or anything that needs scaling ?
http://www.bitmover.com/lmbench/lmbench-usenix.pdf
If you look at the memory latency results carefully, you can easily read off L1, L2, L3, main memory, memory + TLB miss latencies.
If you look at them harder, you can read off cache sizes and associativity, cache line sizes, and page size.
Here is a 3-D graph that Wayne Scott did at Intel from a tweaked version of the memory latency test.
http://www.bitmover.com/lmbench/mem_lat3.pdf
His standard interview question is to show the candidate that graph and say "tell me everything you can about this processor and memory system". It's usually a 2 hour conversation if the candidate is good.