Computers are fast

http://jvns.ca/blog/2014/05/12/computers-are-fast/

by bdcravens • 12 years ago

315 154 12 years ago

infogulch• 12 years ago

Nice writeup! I like how even simplistic approaches to performance can easily show clear differences! However! I noticed you use many (many!) exclamation points! It gave me the impression that you used one too many caffeine patches! [1]

[1] https://www.youtube.com/watch?v=UR4DzHo5hz8

bithush2• 12 years ago

Shows how excited they were. I always like to see blog posts where the poster is excited about the post!

personalcompute• 12 years ago

I particularly enjoyed the writing style in this article, largely because of the extent that the author provided unverified and loose figures in the article - cputime distributions etc. My experience is usually people are extremely hesitant to publish any uninformed, fast, and incomplete conclusions despite them being, in my opinion, still extremely valuable. It may not be perfectly correct, but that small conclusion is still often much better than the practically non existent data on the situation I start off with and allows me to additionally read the article far faster than slowing down to make these minor fuzzy conclusions myself. There is this misconception that when writing you can do two things - you can tell a fact or you can say a false statement. In reality it is a gray gradient space, and when the reader starts off knowing nothing, that gray is many times superior. Anyways, awesome job, I really want to see more of this writing style in publications like personal blogs.

[In case it isn't clear, I'm referring to statements like "So I think that means that it spends 32% of its time accessing RAM, and the other 68% of its time doing calculations.", and "So we’ve learned that cache misses can make your code 40 times slower." (comment made in the context of a single non-comprehensive datapoint)]

josephlord• 12 years ago

It doesn't come across as a benchmark of a particular system or a performance tuning guide. It is a few simple experiments to get ballpark figures for just how fast a modern computer is and to trigger a couple of effects (such as cache misses) that can really slow down the system.

I think the real value is to show how to start having a play with things yourself.

kijin• 12 years ago

Agreed. At first, the writing style (too! many! exclamation! points! Are you Unidan or what?) made me think that the article wasn't serious. The fact that I immediately thought, "you're just going to be benchmarking your disk!" didn't help, either. But the author did take the disk performance into account, and the rest of the article was surprisingly interesting as well. It's a quick and dirty exposition for a quick and dirty suite of benchmarks.

StavrosK• 12 years ago

I don't know, I love her enthusiasm.

skywhopper• 12 years ago

Her style is definitely different, but after discovering her last year and reading a ton of posts, I find it energizing. I recognize that feeling of excitement she's capturing in her writing style! I should be experiencing it more than I do! She's an inspiring writer. The exact details aren't really the point--they can be gotten easily enough. The process and the discovery are what she's documenting so well.

drb311• 12 years ago

The style works because she's going on an adventure of discovery and taking us along for the ride.

Loose guesses that you hope are good enough are more fun than exact calculations. It's fun watching Indiana Jones guessing how much sand he needs to equal the weight of the statue, and it makes him seem more heroic. In that case he might have been better taking his time to do it properly, though.

Our minds are programmed to learn in a particular way:

- Try stuff

- See what happens

- Try to guess at a rule that would explain why it happened

- Test your guess by trying other stuff

... repeat until you know everything

It's fun sharing that process with another person, and a pretty good way to learn too -- especially where precision is not important. Technical writers should use it more.

AnimalMuppet2• 12 years ago

In fairness, it only takes one datapoint to learn that cache misses can in fact make your code 40 times slower.

cessor• 12 years ago

I like the "free" style of the article. Here is another conclusion: In my professional life I have heard many, many excuses in the name of performance. "We don't need the third normal form, after all, normalized databases are less performant, because of the joins". Optimizing for performance should not mean to make it just as fast as it could possibly run, but to make it just fast enough.

Julia's article shows a good example for this. Of course, the goal appears to generate a feeling of what tends to make a program fast and slow and get a feeling for how slow it will be or how fast it can get; yet I'd like to point out that this...

https://github.com/jvns/howcomputer/blob/master/bytesum_intr...

... might be 0.1 Seconds faster than the original code when started as "already loaded into ram" which she claims runs at 0.6 seconds. Yet this last piece of code is way more complicated and hard to read. Code like this

Line 11: __m128i vk0 = _mm_set1_epi8(0);

might be idiomatic, fast and give you a great sense of mastery, but you can't even pronounce it and it it's purpose does not become clear in any way.

Writing the code this way may make it faster, but that makes it 1000x harder to maintain. I'd rather sacrifice 0.1 seconds running time and improve the development time by 3 days instead.

bithush2• 12 years ago

Depends if that 0.1 seconds is going to add up to a very significant amount. Obviously these are just tests but in a production system running 24/7 that 0.1 seconds per run is going to add up to a lot. The code might be ugly but that is when comments are most important.

pjc50• 12 years ago

Or it might add up to next to nothing, if a full run is eight hours. Or it might finish early and then be blocked waiting for some other part of the system.

The moral of "computers are fast" is that guessing about bottlenecks and twiddling with the lowest level of code is unlikely to help; you need to start at the top with a profiler, and start asking the questions "do we need to compute this at all?", "can we make it O(n log n) or better?", and "can we partition this to scale horizontally?"

heffo• 12 years ago

I believe that the author meant to write 0.25 seconds, instead of 0.5 seconds. She says that the one step halves the running time, and later on she is investigating how the 0.25 seconds are split up.

A >50% speedup is not to be sniffed at! I completely agree with your point though, unless it is mission critical that this code runs as fast as possible, then you are better off keeping it simple!

blt2• 12 years ago

That's why you write a C++ class wrapping the SSE intrinsics :)

zokier5• 12 years ago

So I think that means that it spends 32% of its time accessing RAM, and the other 68% of its time doing calculations

Not sure if you can do such conclusion actually, because of pipelining etc. I'd assume that the CPU is doing memory transfers simultaneously while doing the calculations.

I also think that only the first movdqa instruction is accessing RAM, the others are shuffling data from one register to another inside the CPU. I'd venture a guess that the last movdqa is shown taking so much time because of a pipeline stall. That would probably be the first place I'd look for further optimization.

On the other hand, I don't have a clue about assembly programming or low-level optimization, so take my comments with a chunk of salt.

userbinator6• 12 years ago

It spends the other 68% of its time doing calculations and waiting for the results of the memory accesses.

I personally don't like using per-instruction timings like the one presented in the article to measure performance; on a pipelined, superscalar/out-of-order CPU, the fact that one instruction takes a long time to execute doesn't matter so much since others can execute "around it" if they don't depend on it.

On the other hand, macrobenchmarks like the timing of the execution of a whole program, are very useful.

I timed it, and it took 0.5 seconds!!! [...] So our program now runs twice as fast

0.5s down from 0.6s is not "twice as fast", it is a 16.67% improvement. I'm not sure where the 0.25s was pulled from.

zokier5• 12 years ago

It spends the other 68% of its time doing calculations and waiting for the results of the memory accesses.

It is bit odd though, the code is processing data at about 4GB/s, and modern system should have lot more RAM bandwidth (eg about 10GB/s for DDR3-1333). It feels like there should be still significant room for optimization.

0.5s down from 0.6s is not "twice as fast", it is a 16.67% improvement. I'm not sure where the 0.25s was pulled from.

I think the 0.5 was typo (missing '2') and should be instead 0.25

kingosticks• 12 years ago

Unless 0.5 is a typo and it should have actually read 0.25. Then the last line makes more sense too. Except of course 20/0.25 = 80x and not 20x as claimed in step 4...

But never mind, it's a fun post.

chpatrick2• 12 years ago

It's 1.08s on my computer for one line of Python, which is respectable:

  python2 -m timeit -v -n 1 -s "import numpy" "numpy.memmap('1_gb_file', mode='r').sum()"                                                                                    
  raw times: 1.08 1.09 1.08

hesselink• 12 years ago

Isn't a lot of numpy implemented in C?

chpatrick2• 12 years ago

Sure, but the point is that you can get some pretty nice speeds without writing any C yourself.

buster• 12 years ago

Python is implemented in C as well and it's still a dynamic language, which was the point here, i guess.

pekk• 12 years ago

So what? Do you live in an alternative universe where you cannot use libraries implemented in C? Then you also cannot use, for example, Node.js (based on libuv).

sitkack2• 12 years ago

Where is the sum?

chroma• 12 years ago

For an in-depth presentation on how we got to this point (cache misses dominating performance), there's an informative and interesting talk by Cliff Click called A Crash Course in Modern Hardware: http://www.infoq.com/presentations/click-crash-course-modern...

The talk starts just after 4 minutes in.

cgag• 12 years ago

The rest of her blog is great as well, I really like her stuff about os-dev with rust.

userbinator6• 12 years ago

I wrote a new version of bytesum_mmap.c [...]and it took about 20 seconds. So we’ve learned that cache misses can make your code 40 times slower

What's being benchmarked here is not (the CPU's) cache misses, but a lot of other things, including the kernel's filesystem cache code, the page fault handler, and the prefetcher (both software and hardware). The prefetcher is what's making this so much faster than it would otherwise be if each one of those accesses were full cache misses. If only cache misses were only 40 times slower, performance profiles would be very different than they are today!

Here are some interesting numbers on cache latencies in (not so) recent Intel CPUs:

https://software.intel.com/en-us/forums/topic/287236

I’m also kind of amazed by how fast C is.

For me, one of the points that this article seems to imply is that modern hardware can be extremely fast, but in our efforts to save "programmer time", we've sacrificed an order of magnitude or more of that.

skrebbel• 12 years ago

For me, one of the points that this article seems to imply is that modern hardware can be extremely fast, but in our efforts to save "programmer time", we've sacrificed an order of magnitude or more of that.

Sounds like a good deal!

zxcdw• 12 years ago

To who and in what situations? To businesses(hardware and software) sure, they get products out faster and are motivated to push new stuff out. To end users, not so much, because they wait more and their batteries drain faster. They also pay more for hardware to have a "good experience".

exDM697• 12 years ago

For me, one of the points that this article seems to imply is that modern hardware can be extremely fast, but in our efforts to save "programmer time", we've sacrificed an order of magnitude or more of that.

There's still plenty of reasons to write fast code. If the code ends up being run repeatedly and is known to be the bottleneck, optimizing a piece of code may save on hardware costs. And power and cooling costs.

Or if we're talking about a mobile device, doing something quickly and then powering off the CPU will save a lot of those precious milliwatts. (I do this in my day job)

In this case, there was a 10x improvement in the time it takes, allowing the CPU to be powered off for 2 seconds. That translates to longer battery life and happy customers.

While you're right in that CPU time is usually cheaper than programmer time, there's still a time and a place for writing fast code. Computers may be "fast enough" but the hardware is still expensive and the power it consumes is more important than ever.

Cthulhu_• 12 years ago

Re: last paragraph, I agree; however, it's a cost / benefit thing. I work as a consultant, and while I want to make the most optimal software ever on the one hand, my customer also wants features. The more you optimize, the harder it gets and the more maintenance you'll need to do. It all depends on how much time (and money) you want to invest in optimization vs features.

thegeomaster• 12 years ago

Anyone notice how the author is all excited? Got me in a good mood, reading this.

sanxiyn6• 12 years ago

I wonder why GCC does not autovectorize the loop in bytesum.c even with -Ofast. With autovectorizer, GCC should make the plain loop as fast as SIMD intrinsics. Autovectorizer can't handle complex cases, but this is as simple as it can get.

Anyone has ideas?

rsp1984• 12 years ago

Maybe I'm just oldschool but I found that auto-vectorization hardly ever does what one thinks it should do. I view it as a nice tool in my belt but I don't ever expect it to magically speed things up for me by large factors. If I want real SIMD I get down to intrinsics or assembler myself.

jokoon• 12 years ago

I don't think compilers are able to know when to use SIMD

Isn't vectorization different than SIMD ?

dbaupp4• 12 years ago

No, vectorization is converting scalar operations (i.e. one piece of data at a time, e.g. summing one byte at a time) to vector ones (operating on multiple pieces of data at once, e.g. summing 16 bytes in parallel), and these operations are exactly what SIMD is.

sanxiyn6• 12 years ago

Compilers certainly can, although they aren't exactly good.

dbaupp4• 12 years ago

pbsd investigated above[1] and found that the problem was the use of signed chars.

[1] https://news.ycombinator.com/item?id=7737582

sanxiyn6• 12 years ago

Argh, this is annoying indeed. And yes, compiler is correct not to autovectorize in this case then.

exDM697• 12 years ago

I posted the following as a comment to the blog, I'll duplicate it here in case someone wants to discuss:

This program is so easy on the CPU that it should be entirely limited by memory bandwidth and the CPU should be pretty much idle. The theoretical upper limit ("speed of light") should be around 50 gigabytes per second for modern CPU and memory.

In order to get closer to the SOL figure, try adding hints for prefetching the data closer to the CPU. Use mmap and give the operating system hints to load the data from disk to memory using madvise and/or posix_fadvise. This should probably be done once per a big chunk (several megabytes) because the system calls are so expensive.

Then try to make sure that the data is as close to the CPU as possible, preferably in the first level of the cache hierarchy. This is done with prefetching instructions (the "streaming" part of SSE that everyone always forgets). For GCC/Clang, you could use __builtin_prefetch. This should be done for several cache lines ahead because the time to actually process the data should be next to nothing compared to fetching stuff from the caches.

Because this is limited on memory bandwidth, it should be possible to do some more computation for the same price. So while you're at it, you can compute the sum, the product, a CRC sum, a hash value (perhaps with several hash functions) at the same cost (if you count only time and exclude the power consumption of the CPU).

sanxiyn6• 12 years ago

Yup, __builtin_prefetch certainly, if one wants to get it faster. (Compilers can't do this themselves, because they don't know how much they should prefetch ahead, and if you get that wrong it's worse than no prefetching.)

I am less sure about madvise. It seems to me default heuristics should work fine for this case, and as you said, system calls are expensive.

exDM697• 12 years ago

I am less sure about madvise. It seems to me default heuristics should work fine for this case, and as you said, system calls are expensive.

System calls are expensive but so are page faults or having to access the disk. If you can avoid page faults by using madvise to prefetch from disk to memory, it should be worth it. In particular, the first run with cold caches should be faster.

However, the operating system may be smart and realize that we're doing a sequential access and may speculatively read ahead and madvise calls would be time wasted.

The same happens with CPU caches too, the CPU internal prefetcher is pretty good in recognizing a sequential access and grabbing the next cache line in advance. A few naively placed __builtin_prefetches doesn't seem to help here (I just tried this out).

Prefetching hints work a lot better in non-sequential access patterns (linked lists, etc).

fulafel• 12 years ago

Also, TLB misses. Also the reason why mmap(2) doesn't always beat read(2).

dekhn• 12 years ago

You know you're using a machine properly when you don't just blow the TLB. You blow the TLB for the TLB. I was pretty skeptical when my coworkers insisted my code did this, until I collected some great Intel performance counter data and, indeed, I blew the 2nd level TLB. Good read: http://www.realworldtech.com/haswell-cpu

krick• 12 years ago

Pretty naïve, I'm surprised to see it here. Not that this is pointless study, but it's pretty easy to guess up these numbers if you know about how long it takes to use a register, L1, L2, RAM, hard drive (and you should). And exactly how long it would take is task-specific question, because depends more on what optimization techniques can be used for the task and what cannot, so unless you are interested specifically in summation mod 256, this information isn't much of use, as "processing" is much broader than "adding moulo 256".

But it's nice that somewhere somebody else understood, that computers are fast. Seriously, no irony here. Because it's about time for people to realize, what disastrous world modern computing is. I mean, your home PC processes gigabytes of data in the matter of seconds, amount of computations (relative to its cost) it is capable of would drive some scientist 60 years ago crazy and it gets wasted. It's year 2014 and you have to wait for your computer. It's so much faster than you, but you are waiting for it! What an irony! You don't even want to add up gigabyte of numbers, you want to close a tab in your browser or whatever, and there are quite a few processes running in the background that actually have to be running right now to do something useful, unfortunately OS doesn't know about that. Unneeded data cached in the RAM and you wait while OS fetches memory page from HDD. But, well, after 20 layers of abstraction it's pretty hard to do only useful computations, so you make your user wait to finish some computationally simple stuff.

About every time I write code I feel guilty.

narag2• 12 years ago

Do you know what would make people instantly realise how fast computers are?

Reaction: a program that reads a camera and reacts to some user action instantly moving a robot arm. Add to that an ultra-slow-motion camera so we can see what happened afterwards.

yayitswei• 12 years ago

Reminds me of the robot that wins rock-paper-scissors every time: http://www.theguardian.com/technology/video/2013/nov/06/japa...

jordan0day• 12 years ago

There's a passage in Stephen Levy's book "Hackers" where he talks about a robot built by some students at MIT that could catch a ping pong ball thrown to it by a human. I don't recall what year this project was done, but I do recall what computer they used: a PDP-6.

So a computer built 50 years ago is already fast enough to pass your instant-reaction test. (Well, admittedly, maybe it didn't respond instantly, but if it could catch a thrown ping pong ball, it was probably pretty quick).

This comment isn't meant to scoff at your suggestion -- far from it -- I think an instant-reaction-bot will still impress most people (and rightfully so). I just wonder if we, as programmers and scientists and engineers, haven't been taking as much advantage of Moore' law as we ought to.

zokier5• 12 years ago

It's year 2014 and you have to wait for your computer. It's so much faster than you, but you are waiting for it!

The same is also evident on the web. In so many cases you need to wait for content, maybe couple of KB of text, to load even with our tens of Mb/s at last mile and tens of Gb/s at datacenter.

http://en.wikipedia.org/wiki/Wirth%27s_law

Negitivefrags• 12 years ago

This is just due to the ridiculous way the development ecosystem for the web has grown. Nobody seems to care about fast languages anymore.

Check out this website. http://forum.dlang.org/

Notice how amazingly fast it is. It's written in D.

Oh, but I forgot, the bottleneck is in the database so feel free to waste millions of cycles every request chasing pointers around and around the vast quantities of memory that your dynamic language consumes.

People don't even know what speed is anymore.

fsniper2• 12 years ago

Exactly How I feel. We are adding up abstraction over abstraction, backwards compatibility, hardware compatibility, software compatibility, unrelated ui/ux features, animations..

I believe modern computing has 80/20 rule in a bad way. We use 80 percent of the computing power to do unrelated 20 percent of the job.

we need to re-find Unix philosophy for modern day computing. Software should do a single task but do it well.

Also have a look at Zawinski's Law. http://en.wikipedia.org/wiki/Jamie_Zawinski#Zawinski.27s_law...

ygra2• 12 years ago

And when you need to glue lots of things together that do just a single task, you end up spending much more (development and run) time at the joints, as in, constantly converting and parsing data again.

maxerickson• 12 years ago

I wonder how much of the Unix philosophy is accidental success. 'Do one thing well' is a (relatively) easy way to make something that actually works correctly, so I guess I'm wondering if doing one thing is actually important, or if actually doing something in a consistent, reliable and predictable way is the more important aspect.

(Small programs that enable composition are great, but so is, for example, a program that can uncompress any format in place with only an option or two)

JoachimS• 12 years ago

To me, one of the really mind boogling things in terms of waste is how we today basically create piles of complete systems just to run a single application. The system used to run a single application is filled with other applications, libraries and functions that are never used.

And the application being run is probably using shared lib and other complex mechanisms designed for shared environments when no sharing will in fact happen.

Yes, these servers are virtual and just part of a file. But the overhead in space and energy is still mind boggling.

7952• 12 years ago

The computers are fast point really strikes a cord with me. Because so much of what programmers do seems to be about using abstractions and infrastructure to achieve things that are too slow when written naively in actual code. Just try plotting some 3D data using python. Should I use matplotlib, or a game engine, or maybe OpenGL? Each option could be too slow, even though the machine can easily process the raw data almost instantly.

userbinator6• 12 years ago

I agree completely. Hardware has gotten orders of magnitude faster, yet the experience, as a user, hasn't changed nearly that much. You'll probably find this comparison interesting: http://hallicino.hubpages.com/hub/_86_Mac_Plus_Vs_07_AMD_Dua...

I think the saying that programmer time is more expensive than machine time is, like the quote about premature optimisation, responsible for promoting an inherently wasteful culture in programming when people are taught to take them at face value; looking at it another way, power isn't free, and when machine time translates to user time, then the situation definitely changes. I always keep in mind that users are using the software I create to do work, and their time is just as valuable if not more so than my own, especially if there are more of them. To me, it's a question of balancing the tradeoffs --- it's not worth spending a day to optimise software that will save a few minutes across all its users over its lifetime, but it is very well worth it to spend a week to optimise something so that it may save a year or more of its users' time. Whenever a programmer complains about certain tools (e.g. compiler, IDE, etc.) being slow, I keep that in mind to mention the next time he/she flippantly dismisses a time-saving optimisation using the "my time is more expensive" excuse. Programmers are users too. :-)

couchand• 12 years ago

Found this gem in the linked article: Windows Vista demands enough real estate on your hard drive that you could easily fit 30,000 full-length novels into it.

A nitpick: a day of work, say six hours, is only 3600 minutes. If you can optimize some task to save a few minutes per user, it only takes a few thousand users to be worth it.

However, I think the worst optimizations to leave on the table are in an area many developer-types won't think about: usability. We can save much more of a user's time by creating simple, intuitive interfaces than we can checking cache misses (in most modern development).

demallien• 12 years ago

"Hardware has gotten orders of magnitude faster, yet the experience, as a user, hasn't changed nearly that much."

I see what you mean, but I feel that this misses out an important fact - a lot of those speed increases are only available if you modify your code to use an optimized path. Memory I/O is a classic example - it has sped up a lot but only if you make sure that you aren't generating cache misses on every memory access. Branch-prediction-friendly code is another good example that can make a huge difference to the performance of a system.

That means that a lot of the performance gains that we have achieved (not all, certainly, but a substantial chunk) are not necessarily made available to naively-written code. It is not terribly surprising then that we sometimes struggle to achieve the speed-ups the hardware has made available to us.

This problem is only compounded by the fact that performance is one of the leakiest things going when we are talking about abstraction layers. It makes things extremely difficult to think about because you need to know intimate detail of your entire software stack, which these days is huge, if you wish to effectively optimize your code.

fixermark• 12 years ago

In terms of balancing tradeoffs, I continue to find this cheat-sheet useful whenever the topic comes up.

http://xkcd.com/1205/

sjtrny• 12 years ago

But not fast enough

dbaupp4• 12 years ago

Interesting investigation!

I had an experiment with getting the Rust compiler to vectorise things itself, and it seems LLVM does a pretty good job automatically, e.g. on my computer (x86-64), running `rustc -O bytesum.rs` optimises the core of the addition:

  fn inner(x: &[u8]) -> u8 {
      let mut s = 0;
      for b in x.iter() {
          s += *b;
      }
      s
  }

  .LBB0_6:
  	movdqa	%xmm1, %xmm2
  	movdqa	%xmm0, %xmm3
  	movdqu	-16(%rsi), %xmm0
  	movdqu	(%rsi), %xmm1
  	paddb	%xmm3, %xmm0
  	paddb	%xmm2, %xmm1
  	addq	$32, %rsi
  	addq	$-32, %rdi
  	jne	.LBB0_6

I can convince clang to automatically vectorize the inner loop in [1] to equivalent code (by passing -O3), but I can't seem to get GCC to do anything but a byte-by-byte tranversal.

[1] https://github.com/jvns/howcomputer/blob/master/bytesum.c

pbsd6• 12 years ago

GCC vectorizes the sum fine if the input is unsigned bytes, cf [1]. My guess is some odd interaction between integer promotions and the backend.

[1] http://goo.gl/B7KX1V

detrino• 12 years ago

I think it's just the type of the accumulator[1] that influences this, GCC seems to vectorize it fine for any type other than signed char/signed short.

[1] s in your code, result in the author's

Edit: The reason for the failure appears to be this:

    test.c:7:2: note: reduction: not commutative/associative: s_11 = (int8_t) _10;

Edit: GCC vectorizes this fine when compiling with -fwrapv, which gives you the semantics the author probably expected.

jxf2• 12 years ago

This link seems to be breaking the HN comments for this page. :)

userbinator6• 12 years ago

One of the things I've always wanted is autovectorisation by the CPU - imagine if there was a REP ADDSB/W/D/Q instruction (and naturally, repeated variants of the other ALU operations.) It could make use of the full memory bandwidth of any processor by reading and summing entire cache lines the fastest way the current microarchitecture can, and it'd also be future-proof in that future models may make this faster if they e.g. introduce a wider memory bus. Before the various versions of SSE there was MMX, and now AVX, so the fastest way to do something like sum bytes in memory changes with each processor model; but with autovectorisation in hardware, programs wouldn't need to be recompiled to take advantage of things like wider buses.

Of course, the reason why "string ALU instructions" haven't been present may just be because most programs wouldn't need them and only some would receive a huge performance boost, but then again, the same could be said for the AES extensions and various other special-purpose instructions like CRC32...

TheLoneWolfling2• 12 years ago

This is why I'm in favor of client-side compilation.

Devs compile to an intermediate language or bytecode of some sort, which then gets compiled on installation / first use / update of the client runtime client-side. Kind of like Java, but instead of being JITted (which causes inconsistent performance) it's compiled and cached.

That way things can be optimized for your specific architecture / computer.

Of course, you can actually do this at the kernel level.

nkurz14• 12 years ago

1/4 second to plow through 1 GB of memory is certainly fast compared to some things (like a human reader), but it seems oddly slow relative to what a modern computer should be capable off. Sure, it's a lot faster than a human, but that's only 4 GB/s! A number of comments here have mentioned adding some prefetch statements, but for linear access like this that's usually not going to help much. The real issue (if I may be so bold) is all the TLB misses. Let's measure.

Here's the starting point on my test system, an Intel Sandy Bridge E5-1620 with 1600 MHz quad-channel RAM:

  $ perf stat bytesum 1gb_file
  Size: 1073741824
  The answer is: 4
  Performance counter stats for 'bytesum 1gb_file':

  262,315 page-faults         #    1.127 M/sec
  835,999,671 cycles          #    3.593 GHz
  475,721,488 stalled-cycles-frontend   #   56.90% frontend cycles idle
  328,373,783 stalled-cycles-backend    #   39.28% backend  cycles idle
  1,035,850,414 instructions            #    1.24  insns per cycle
  0.232998484 seconds time elapsed

Hmm, those 260,000 page-faults don't look good. And we've got 40% idle cycles on the backend. Let's try switching to 1 GB hugepages to see how much of a difference it makes:

  $ perf stat hugepage 1gb_file
  Size: 1073741824
  The answer is: 4
  Performance counter stats for 'hugepage 1gb_file':

  132 page-faults               #    0.001 M/sec
  387,061,957 cycles                    #    3.593 GHz
  185,238,423 stalled-cycles-frontend   #   47.86% frontend cycles idle
  87,548,536 stalled-cycles-backend     #   22.62% backend  cycles idle
  805,869,978 instructions              #    2.08  insns per cycle
  0.108025218 seconds time elapsed

It's entirely possible that I've done something stupid, but the checksum comes out right, but the 10 GB/s read speed is getting closer to what I'd expect for this machine. Using these 1 GB pages for the contents of a file is a bit tricky, since they need to be allocated off the hugetlbfs filesystem that does not allow writes and requires that the pages be allocated at boot time. My solution was a run one program that creates a shared map, copy the file in, pause that program, and then have the bytesum program read the copy that uses the 1 GB pages.

Now that we've got the page faults out of the way, the prefetch suggestion becomes more useful:

  $ perf stat hugepage_prefetch 1gb_file
  Size: 1073741824
  The answer is: 4

  Performance counter stats for 'hugepage_prefetch 1gb_file':
 132 page-faults            #    0.002 M/sec
 265,037,039 cycles         #    3.592 GHz
 116,666,382 stalled-cycles-frontend   #   44.02% frontend cycles idle
 34,206,914 stalled-cycles-backend     #   12.91% backend  cycles idle
 579,326,557 instructions              #    2.19  insns per cycle
 0.074032221 seconds time elapsed

That gets us up to 14.5 GB/s, which is more reasonable for a a single stream read on a single core. Based on prior knowledge of this machine, I'm issuing one prefetch 512B ahead per 128B double-cacheline. Why one per 128B? Because the hardware "buddy prefetcher" is grabbing two lines at a time. Why do prefetches help? Because the hardware "stream prefetcher" doesn't know that it's dealing with 1 GB pages, and otherwise won't prefetch across 4K boundaries.

What would it take to speed it up further? I'm not sure. Suggestions (and independent confirmations or refutations) welcome. The most I've been able to reach in other circumstances is about 18 GB/s by doing multiple streams with interleaved reads, which allows the processor to take better advantage of open RAM banks. The next limiting factor (I think) is the number of line fill buffers (10 per core) combined with the cache latency in accordance with Little's Law.

exDM697• 12 years ago

Good stuff! The low numbers (4 GB/s, one tenth the available memory bandwidth) that we're seeing sounds like a lot of time is wasted in page faults (and indeed, perf stat confirms it). However, the solution you propose sounds difficult, you need a special file system and need to know what kind of page sizes the CPU supports.

Can you think of ways to get reduce the number of page faults from inside the application itself? Or methods that would be portable to architectures with different page sizes?

I tried a simple call to madvise and posix_fadvise to inform the operating system ahead of time that I am going to need the memory but that did not have any effect on the number of page faults.

Any other tips for squeezing some more perf out? Did you happen to do any cache miss stats your benchmarks?

pbsd6• 12 years ago

You get a similar effect to huge pages by passing MAP_POPULATE to mmap, which pre-faults all pages itself before returning.

userbinator6• 12 years ago

Any other tips for squeezing some more perf out?

Ditch the OS and go into huge unreal mode ala LoseThos. Disable interrupts in the loop. No MMU means no page faults, no TLB, no interrupts, you can't possibly get any faster than that! :-)

More seriously, I think 14.5GB/s is getting close to the limits of memory bandwidth on a single core already. Multicore CPU's memory controllers are optimised for multiple cores accessing memory, so a single one trying to saturate the bus might not perform so well.

nkurz14• 12 years ago

However, the solution you propose sounds difficult, you need a special file system and need to know what kind of page sizes the CPU supports.

Yes, I've definitely offered a "proof of concept" rather than a solution. But it has gotten simpler with recent Linux kernel versions: http://lwn.net/Articles/533499/.

One difficulty in emulating Julia's particular benchmark is (at least on Linux) transparent hugepages can't be used for file-backed memory. It's easier if you are just allocating an anonymous buffer, and even easier if you don't need to share that buffer between unrelated processes.

Can you think of ways to get reduce the number of page faults from inside the application itself?

"Page faults" is an overloaded term (used for semi-related OS and hardware level events), so probably best to avoid it (even though I was using it, and even though 'perf' does). I was actually using 'likwid' to do most of the measuring, and switched to 'perf' for the post since it's more generally available. Our goal here is to avoid TLB misses, or the consequent 'page walks'.

With that in mind, the subgoal becomes allocating memory that uses hugepages. If you are OK with the default 2MB pages, this is reasonably straightforward. 'libhugetlbfs' (a library distributed independently of the 'hugetlbfs' distributed with the kernel) may make this easier.

Or methods that would be portable to architectures with different page sizes?

The number of page sizes supported is not a big issue. There are only a few sizes out there. In practice, all 64-bit systems will support the 2MB hugepages, and this is almost always the default hugepage size. In this particular case with a linear scan of memory, there is almost no difference in performance between these and the harder to specify 1GB pages.

I tried a simple call to madvise and posix_fadvise to inform the operating system ahead of time that I am going to need the memory but that did not have any effect on the number of page faults.

This is the overloading of the terms getting you. Presuming a system with ample free memory, after the first run you won't have any OS level page faults. But anytime you try to have a working set of more than 512 4K regions in RAM, you will have TLB misses aka "page exceptions".

The madvise() option that should help here is MAP_HUGETLB. You should also be able to use this in mmap(), but not (to my knowledge) if you are doing a file backed allocation.

Any other tips for squeezing some more perf out?

Not really, learning these is my goal as well. For me, it's probably going to involve getting more familiar with the "uncore" performance monitors. Sandy Bridge and post, these are accessed via PCI rather than MSR's, and are difficult to use from 'perf'. 'likwid' supports them better, and is definitely worth exploring.

The other place to get further gains is by trying to understand the actual memory access patterns, and trying to get them to read full DRAM pages each time a bank is opened. John McCalpin (author of the Stream benchmark) goes into it here: http://blogs.utexas.edu/jdm4372/2010/11/09/optimizing-amd-op...

Did you happen to do any cache miss stats your benchmarks?

This is directly related to the performance improvement, but I didn't look at the numbers separately. Glancing now, it looks like practically everything is hitting L3, but a lot of things are missing L1. This is probably worth exploring further. I think one issue is that the hardware prefetcher deposits things in L2 (~12 cycles), but not L1 (~6 cycles).

JoshTriplett• 12 years ago

That gets us up to 14.5 GB/s, which is more reasonable for a a single stream read on a single core.

If you want to see roughly the limit of memory speed on your machine, try booting into memtest86+; in addition to testing memory, it benchmarks memory.

jvns3• 12 years ago

Can you share the prefetching code you wrote? I tried to use __builtin_prefetch, but couldn't figure out how to make it faster.

nkurz14• 12 years ago

My approach was somewhat ugly. I went this this:

  for (int i = 0; i < n; i += 8*16) {
      __builtin_prefetch(&a[i + 512]);
      for (int j = 0; j < 8; j++) {
        __m128i v = _mm_load_si128((__m128i *)&a[i + j*16]);
        __m128i vl = _mm_unpacklo_epi8(v, vk0); 
        __m128i vh = _mm_unpackhi_epi8(v, vk0);
        vsum = _mm_add_epi32(vsum, _mm_madd_epi16(vl, vk1));
        vsum = _mm_add_epi32(vsum, _mm_madd_epi16(vh, vk1));
    }

The goal is to issue one prefetch for each 128B block of data you read. There are probably better ways to do this than what I did. I'm hoping the compiler did something reasonable, and haven't really looked at the generated assembly.

Also, if it indeed is that case that TLB misses are the major factor (and I think it is), I don't think you will have much success with by adding prefetch alone. Trying right now, I get a slight slowdown with just the prefetch. It may only in combination with hugepages that you get a positive effect.

cshimmin2• 12 years ago

Naively, it sounds about right just on dimensional grounds. CPU clock: ~ 2GHz, so that means

    (2 GHz) / (4 GB / s) = 0.5 instructions per byte

For a 64 bit processor, you might imagine the best you can do is, say, 2 instructions per 8 bytes (load 64 bits, add+store accumulator).

But of course in practice, the CPU is occupied by other things (i.e. operating system), so I think it's still pretty amazing to get this close to the "theoretical" maximum efficiency.

nkurz14• 12 years ago

I'm not sure if this is the right way to look at the problem. With the right numbers, it does provide a theoretical limit, but the problem is that there are other lower I/O limits that get in the way first.

As a stab at the right numbers, on Sandy Bridge you can issue two 16B loads per cycle. Since modern processors are superscalar, in that same cycle you can issue the two vector adds. So your actual CPU limit is more like 32B per cycle (.03 cycles per byte).

hyp0• 12 years ago

  I timed it, and it took 0.5 seconds!!!
  So our program now runs twice as fast,

minor typo above: time is later stated as 0.25. super neat!

Udo• 12 years ago

I wrote a comment pointing that out on the author's blog, but it appears to have since been deleted :/

okso2• 12 years ago

Naïve Python3 is not as fast as Numpy, but pretty elegant:

  def main(filename):
      d = open(filename, 'rb').read()
      result = sum(d) % 256
      print("The answer is: ", result)

jdiez17• 12 years ago

Note that sum(d) will generate a huge number, possibly using lots of memory and processing power. A better option would be:

    def main(filename):
      d = open(filename, 'rb').read()
      result = reduce(lambda i, j: (i + j) % 256, d)
      print("The answer is: ", result)

Note how this is similar to the squaring algorithm used in cryptography: http://en.wikipedia.org/wiki/Exponentiation_by_squaring

zokier5• 12 years ago

wouldn't you need at least 2^55 byte (36 petabytes) size file to go over 64bit integer 'sum' variable? I think such limitation is far preferable to an extra modulo operation for each and every byte. Not sure though how python does its integers, so the threshold for using bignum might be lower.

okso2• 12 years ago

That approach would be very well adapted to a low-level language such as C with the risk of overflow.

Python handles long integers transparently, and the overhead of managing the lambda function and additional variables in Python is probably much more time consuming than handling a long integer.

tejbirwason• 12 years ago

Great post. If you want to dig in even deeper you can learn certain nuances of underlying assembly language like loop unrolling, reducing the number of memory accesses, number of branch instructions per iteration of any loops by rewriting the loop, rearranging instructions or register usage to reduce the dependencies between instructions.

I took a CPSC course last year and for one of the labs we improved the performance of fread and fwrite C library calls by playing with the underlying assembly. We maintained a leader board with the fastest times achieved and it was a lot of fun to gain insight into the low level mechanics of system calls.

I digged up the link to the lab description - http://www.ugrad.cs.ubc.ca/~cs261/2013w2/labs/lab4.html

ChuckMcM• 12 years ago

Nice. I remember the first time I really internalized how fast computers were, even when people claimed they were slow. At the time I had a "slow" 133Mhz machine but we kept finding things it was doing that it didn't need too, and by the time we had worked through that there it was idling a lot while doing our task.

The interesting observation is that computers got so fast so quickly, that software is wasteful and inefficient. Why optimize when you can just throw CPU cycles or memory at the problem? What made that observation interesting for me was that it suggested the next 'era' of computers after Moore's law stopped was going to be about who could erase that sort of inefficiency the fastest.

I expect there won't be as much time in the second phase, and at the end you'll have approached some sort of limit of compute efficiency.

And hats off for perf, that is a really cool tool.

bane2• 12 years ago

It's pretty clear that we're wasting unbelievably huge amounts of computing power with the huge stacks of abstraction we're towering on.

So let's make this interesting, assuming a ground up rewrite of an entire highly optimized web application stack - from the metal on up, how many normal boxes full of server hardware could really just be handled by one? 2? a dozen?

I'd be willing to bet that a modern machine with well written, on the metal software could outperform a regular rack full of the same machines running all the nonsense we run on today.

Magnified over the entire industry, how much power and space are being wasted? What's the dollar amount on that?

What's the developer difference to accomplish this? 30% time?

What costs more? All the costs of potentially millions of wasted machines, power and cooling or millions of man hours writing better code?

AnimalMuppet2• 12 years ago

Could we do this by devoting 30% of industry-wide developer time to creating faster infrastructure? Yes, perhaps we could.

Would it only cost an individual developer 30% of his/her time to write on-the-metal software rather than use all the abstractions? No way. 80%, maybe. Those abstractions save us an amazing amount of work. That's why we use them.

insensible• 12 years ago

Running Varnish is fun for these reasons. And of course reading Poul-Henning Kamp's clearly-stated opinions. :-)

chadgeidel2• 12 years ago

I'll take that bet.

We gain a lot with "the huge stack of abstraction". The OS gives us a ton of "goodies" for free (memory abstraction, process/thread safety, networking, etc) and the languages/libraries give us more goodies (the ability to focus on higher-level tasks rather than "bit twiddling"). One could also point to the fact that your team is taking advantage of hundreds (thousands?) of domain experts in every aspect of the stack to get the "best" solution.

I would argue that it's not "30% time". It's the accumulated time of each level of abstraction you are using combined. It is very likely the case that one team couldn't rewrite the web application stack "from the metal up" and offer significant improvements.

bane2• 12 years ago

Still it's pretty shocking that billions of people might have to wait even a noticeable unit of time that can often be measured in seconds for a web page to go from request to final render. We're doing something wrong.

Server and desktop computing power is impressively more powerful today than when this [1] was first created, which loads almost as fast as I can take my finger off of the mouse button that clicked the link to take me there

1 - http://info.cern.ch/hypertext/WWW/TheProject.html

yet I was able to actually count "one onethousand two onethousand three onethousand" before www.youtube.com finished rendering. I don't know, is 2.xx seconds times a billion people more efficient than a few hundred developers spending 2x or 3x longer to write efficient code?

mrb2• 12 years ago

The author's SSE code is a terribly overcomplicated way of summing up every byte. The code is using PMADDW (a multiply and add?!), and is strangely trying to interleave hardcoded 0s and 1s into registers with PUNPCKHBW/PUNPCKLBW, huh?

All the author needs is PADDB (add packed bytes).

mrb2• 12 years ago

Here is how it should be done with PADDB: http://pastebin.com/MY9tENpW This is 20% faster than the author's version on my computer: 0.210 sec vs. 0.260 sec to process 1GiB. The tight loop is simple:

  400710:	66 0f fc 04 07       	paddb  (%rdi,%rax,1),%xmm0
  400715:	48 83 c0 10          	add    $0x10,%rax
  400719:	48 39 c6             	cmp    %rax,%rsi
  40071c:	77 f2                	ja     400710 <sum_array+0x10>

Compare this to the author's complex version:

  400720:	66 0f 6f 14 07       	movdqa (%rdi,%rax,1),%xmm2
  400725:	48 83 c0 10          	add    $0x10,%rax
  400729:	48 39 c6             	cmp    %rax,%rsi
  40072c:	66 0f 6f c2          	movdqa %xmm2,%xmm0
  400730:	66 0f 68 d4          	punpckhbw %xmm4,%xmm2
  400734:	66 0f 60 c4          	punpcklbw %xmm4,%xmm0
  400738:	66 0f f5 d1          	pmaddwd %xmm1,%xmm2
  40073c:	66 0f f5 c1          	pmaddwd %xmm1,%xmm0
  400740:	66 0f fe c3          	paddd  %xmm3,%xmm0
  400744:	66 0f fe c2          	paddd  %xmm2,%xmm0
  400748:	66 0f 6f d8          	movdqa %xmm0,%xmm3
  40074c:	77 d2                	ja     400720 <sum_array+0x20>

sitkack2• 12 years ago

Do you even lift?

enjoy-your-stay2• 12 years ago

The first time I realised how fast computers could be was when I first booted up BeOS on my old AMD single core, probably less than 1Ghz machine.

The thing booted in less than 10 seconds and performed everything so quickly and smoothly - compiling code, loading files, playing media and browsing the web (dial up modem then).

It performed so unbelievably well compared to Windows and even Linux of the day that it made me wonder what the other OSes were doing differently.

Now my 4 core SSD MacBook pro has the same feeling of raw performance, but it took a lot of hardware to get there.

Computers are fast

Related Stories