Computers are fast
jvns.ca
jvns.ca
[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)]
I think the real value is to show how to start having a play with things yourself.
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.
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).
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).
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.
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.
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.
Also I saw some news about a spanish uni developing one robot arm to catch space debris.
The thing is we still don't realize how fast they really are. We say all the time that computers are dumb. The perception is somewhat distorted for most people.
Moore's law has been almost completely eaten by the screen growth. That's the easiest least imaginative way.
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.
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.
The thing is, in some cases, all the productivity ends up costing a lot more. For small shops it will not be evident, but for bigger ones trying to scale, it'll be a major area of improvement (to use less cycles).
And that's OK... comes down to using the right tool for the right job, matching the skills of your developers with the challenge, how fast you want things delivered, etc, etc, etc.
I think the major issue people see is that when all of that slow programs are looked from a 10,000 feet view as a single thing, it looks like a damn waste of resources. Thus comments like "computing (as a whole) in the last X years has been terrible", etc. We can delve into programmer culture, lack of skills, people not caring about wasting resources, etc, etc, etc.
I think the solution is better tooling. Let the programmer be productive, deliver things fast, etc, but build something more intelligent that will strip it down to only the necessary bits and deploy.
My opinion is that investing the modest effort to select a high-performance platform and framework gives you the freedom to write inefficient application code first and to optimize later. It is the process that allows you to avoid the most expensive kind of premature optimization I've seen by postponing optimization until well after an application's concept has been vetted by its first several thousand users.
Performance is always important. If you can solve a problem in 10% more time using a performant language, then it makes sense to do so, and I've seen few problems that I can express in Python or Ruby (painfully slow) that I cannot express in C++ (highly performant) or Scala (moderately performant) in roughly that amount of extra time.
In most cases, when you are a professional developer, you are not the end-user of your product. In these cases, deliberately choosing a less performant language for the sake of developer productivity can mean you end up penalizing the end user.
And that is the bigger problem, people are running their websites on underpowered hardware in the first place. The limit should be the network connection, not the page rendering time... but unfortunately that isn't always the case.
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...
If your data structure is "a line of text, repeated x times" or "a blob representing an image", then unix pipes are very effective. For most everything else, they're not.
(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)
• Small is beautiful.
• 10 percent of the work solves 90 percent of the problems.
• When faced with a choice, do whatever is simpler.
Which sounds good until realize that these comments mean the exact same thing.
• A small program is more desirable than a program that is functional or correct.
• A shoddy job is perfectly acceptable.
• When faced with a choice, cop out.
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.
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. :-)
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).
And at least for regularly-used software, you can save even more user time by not optimising for the first five minutes of usage but for the long-term usage. Keyboard shortcuts are a good example for this: They are mostly not simple and certainly not intuitive per se (why does Alt+Tab switch windows in particular?), yet once you know them, they do save a lot of time.
That's an apples to oranges comparison if I ever saw one. It says nothing about whether Vista is bloated for the features it provides, by itself.
You mean 360.
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.
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.
Sounds like a good deal!
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.
Performance optimization is most definitely a cost/benefit trade off thing.
In your business as a consultant, it will almost never make sense to optimize for performance.
On the other hand, in my business (sw engineering for the semiconductor industry), performance and power consumption are some of the primary criteria our customers (consumer product manufacturers) make the choice between our product and our competitor's product. In our case, performance is a feature (if not the feature).
Most software engineers probably fall in to the former category and do not have to care about performance of the software they write. But it is dangerous to think that it would always be the case, and especially harmful to think that educational articles like the OP are wasted programmer time. Especially given that OP seems to be focused in low level operating system development, and who wouldn't want their operating systems, browsers, etc faster.
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
[1]: https://github.com/jvns/howcomputer/blob/master/bytesum.c
[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;
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.
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?"
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!
The talk starts just after 4 minutes in.
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# Though could be a VM or something.
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
$ 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
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
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.
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?
Using MAP_POPULATE, I'm seeing this go from 104,276 page faults down to 130 page faults. However, I'm only seeing a modest increase in overall performance, goes from 160 ms to 130 ms for my ~500 MB test file. MAP_POPULATE + MAP_NONBLOCK is as bad as not using MAP_POPULATE (same number of page faults).
Could the number of TLB misses from using huge pages be a major factor too? Page faults alone do not explain the huge perf difference. (edit: perf stat tells me I'm only missing 0.19% of TLB lookups and only 3% dcache misses)
I also tried with a 4 GB file and I see two interesting effects. First of all, using MAP_POPULATE is slower, which I presume is because physical memory is exhausted (6 G memory total). Secondly, I see less than 100k page faults which suggests that bigger pages (2M or 1G?) are being used (10x bigger file, a little less page faults).
HUGETLB_MORECORE=yes LD_PRELOAD=libhugetlbfs.soThe best wall times (that is, with OS time included) I get are obtained by reading L1-sized chunks into a small buffer instead of using mmap. YMMV.
For a 1 GB file, I get wall times of:
Original: .22 sec
MAP_POPULATE: .17 sec
Hugepages: .11 sec
Hugepages with prefetch: .07 sec
It means walking whatever structures the OS uses to keep things in cache. We generally don't know what they are, nor control them.
> What I don't understand is what MAP_POPULATE is doing that gets the speedup that it does.
MAP_POPULATE minimizes the number of page faults during the main loop, which are more expensive (and require a context switch) than TLB misses. Plus, TLB misses can be avoided in our loop, especially with such a friendly linear sweep.
The main problem here, in my view: trying to coax the OS into using memory the way we want. Huge pages surely help in that regard, but they help the most in code that we do not control. The sum itself over 1 GB of memory would be roughly the same speed, regardless of page size.
To put this to the test: generate 1 GB of random bytes on the fly, instead of reading them from a file, and do the same sum. Does the speed change much with the page size? I'd be interested in the results, especially if accompanied by fine-grained performance counter data.
To put this to the test: generate 1 GB of random bytes on the fly, instead of reading them from a file, and do the same sum. Does the speed change much with the page size? I'd be interested in the results, especially if accompanied by fine-grained performance counter data.
Yes, I'm pretty sure this is the case, and had in fact been assuming that it is the major effect. It's a little trickier to measure than the case from the file, since you don't want to include the random number generation as part of the measurement. This essentially excludes the use of 'perf', but luckily 'likwid' works great for this.
I'll try to post some numbers here in the next hour or so. What performance counters are you interested in?
Here's the standard case:
sudo likwid -C 1 -g
INSTR_RETIRED_ANY:FIXC0,
CPU_CLK_UNHALTED_CORE:FIXC1,
DTLB_LOAD_MISSES_WALK_COMPLETED:PMC0,
DTLB_LOAD_MISSES_WALK_DURATION:PMC1 -m ./anonpage
|RDTSC Runtime [s] | 0.0732768 |
|INSTR_RETIRED_ANY | 5.78816e+08 |
|CPU_CLK_UNHALTED_CORE | 2.62541e+08 |
|DTLB_LOAD_MISSES_WALK_COMPLETED | 262211 |
|DTLB_LOAD_MISSES_WALK_DURATION | 5.52261e+06 |
sudo likwid -C 1 -g
INSTR_RETIRED_ANY:FIXC0,
CPU_CLK_UNHALTED_CORE:FIXC1,
DTLB_LOAD_MISSES_WALK_COMPLETED:PMC0,
DTLB_LOAD_MISSES_WALK_DURATION:PMC1 -m ./hugepage
| RDTSC Runtime [s] | 0.0716703 |
| INSTR_RETIRED_ANY | 5.78816e+08 |
| CPU_CLK_UNHALTED_CORE | 2.56794e+08 |
| DTLB_LOAD_MISSES_WALK_COMPLETED | 63 |
| DTLB_LOAD_MISSES_WALK_DURATION | 4891 |
I think that MAP_POPULATE here will fill the page table with entries rather than leaving the page table empty and letting the CPU interrupt at (almost) every time a new page is accessed. That would be about 200k less interrupts for a 1G file.
MAP_POPULATE will probably also do the whole disk read in one go rather than in a lazy+speculative manner.
Page size is probably not affected and neither is number of TLB misses. I in my testing that the size of the file (and the mapping) will affect the page size, a 4G had significantly less page fault interrupts than a 500MB file.
And obviously, MAP_POPULATE is bad if physical memory is getting exhausted.
in my testing that the size of the file (and the mapping) will affect the page size
I'm doubtful of this, although it might depend on how you have "transparent huge pages" configured. But even then, I don't think Linux currently supports huge pages for file backed memory. I think something else might be happening that causes the difference you see. Maybe just the fact that the active TLB can no longer fit in L1?
And obviously, MAP_POPULATE is bad if physical memory is getting exhausted.
I'm confused by this, but this does appear to be the case. It seems strange to me that the MAP_POPULATE|MAP_NONBLOCK is no longer possible. I was slow to realize this may be closely related to Linus's recent post: https://plus.google.com/+LinusTorvalds/posts/YDKRFDwHwr6
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.
See https://software.sandia.gov/trac/kitten for an example.
You can also get pretty far on modern Linux by reserving cores for computation with NOHZ_FULL: http://www.breakage.org/2013/11/nohz_fullgodmode/
Funny how things come full circle sometimes...
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).
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.
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));
}
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.
What processor are you running this on? If Intel, you might have luck with some of the more Intel specific wrappers here: https://github.com/andikleen/pmu-tools
You also might have better luck with 'likwid': https://code.google.com/p/likwid/
Here's the arguments I was giving it to check:
sudo likwid -C 1 -g \
INSTR_RETIRED_ANY:FIXC0, \
CPU_CLK_UNHALTED_CORE:FIXC1,\
CPU_CLK_UNHALTED_REF:FIXC2, \
DTLB_LOAD_MISSES_WALK_COMPLETED:PMC0 \
./bytesum 1gb_file
| INSTR_RETIRED_ANY | 7.38826e+08 |
| CPU_CLK_UNHALTED_CORE | 5.42765e+08 |
| CPU_CLK_UNHALTED_REF | 5.42753e+08 |
| DTLB_LOAD_MISSES_WALK_COMPLETED | 1.04509e+06 |
sudo likwid -C 1 -g \
INSTR_RETIRED_ANY:FIXC0, \
CPU_CLK_UNHALTED_CORE:FIXC1,\
CPU_CLK_UNHALTED_REF:FIXC2, \
DTLB_LOAD_MISSES_WALK_COMPLETED:PMC0 \
./hugepage_prefetch 1gb_file
| INSTR_RETIRED_ANY | 5.79098e+08 |
| CPU_CLK_UNHALTED_CORE | 2.63809e+08 |
| CPU_CLK_UNHALTED_REF | 2.63809e+08 |
| DTLB_LOAD_MISSES_WALK_COMPLETED | 11970 |
ps. I think your 'argc' check is off by one. Since the name of the program is in argv[0], and argc is the length of argv, you want to check 'argc != 2' to confirm that a filename has been given.
(2 GHz) / (4 GB / s) = 0.5 instructions per byte
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.
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).
It turns out that each core has can only have 10 requests for memory outstanding (line fill buffers). Since in the end these requests are coming from RAM, each request has a latency of about 100 cycles. Since each request is for 64B, this gives us a maximum throughput of about about:
Bandwidth = 10 * 64B in flight / 100 cycles
Bandwidth = about 6B per cycle
All the author needs is PADDB (add packed bytes).
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>
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>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.
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?
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.
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.
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?
In the YouTube example, you have very real speed-of-light constraints. I fired up the Chrome debugger and loaded the main site. I had over 100 requests in the first couple of seconds. Even with a very low-latency connection, assuming that your browser can "batch" the requests together, and instantaneous server response there still is an overhead of request/response of at least tens of milliseconds for each request (or group of requests).
To reduce that time, it requires reducing the number of requests, assuming that javascript/images are already loaded, parallelizing or delaying the loading of "ancillary data" etc. All of which have nothing to do with the speed of the server or the client.
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.
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.
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
That's almost certainly already being done by the hardware. Loop unrolling has been counterproductive ever since ~Sandy Bridge or so, and probably hasn't been that great of an idea since the post-P4 days:
http://www.agner.org/optimize/blog/read.php?i=142#142
It is so important to economize the use of the micro-op cache that I would give the advice never to unroll loops.
Loop unrolling may be counterproductive, but loop unrolling for vectorization almost certainly isn't, even in the current CPUs. It really can't be done by the hardware, and all compilers unroll loops for vectorization, even if you disable loop unrolling in general.
But never mind, it's a fun post.
Anyone has ideas?
Isn't vectorization different than SIMD ?
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.
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...
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.
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
def main(filename):
d = open(filename, 'rb').read()
result = sum(d) % 256
print("The answer is: ", result) def main(filename):
d = open(filename, 'rb').read()
result = reduce(lambda i, j: (i + j) % 256, d)
print("The answer is: ", result)
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.
I timed it, and it took 0.5 seconds!!!
So our program now runs twice as fast,