4 ms·
More impressively, sum.c could go likely an order of magnitude or so faster, when optimized. > Friends who do high performance networking say it's possible to
by dom0 10y ago
More impressively, sum.c could go likely an order of magnitude or so faster, when optimized.
> Friends who do high performance networking say it's possible to get network roundtrips of 250ns (!!!),
Well stuff like Infiniband is less network, and more similar to a bus (e.g. RDMA, atomic ops like fetch-and-add or CAS).
> write_to_memory.py
Is also interesting because this is dominated by inefficiencies in the API and implementation and not actually limited by the memory subsystem.
> msgpack_parse.py
Again, a large chunk goes into inefficiencies, not so much the actual work. This is a common pattern in highly abstracted software. msgpack-c mostly works at >200 MB/s or so (obviously a lot faster if you have lots of RAWs or STRs and little structure). Funnily enough, if you link against it and traverse stuff, then a lot of time is spent doing traversals, and not the actual unpacking (in some analysis I've seen a ~1/3 - 2/3 split). So the cost of abstraction also bites here.
If you toy around with ZeroMQ you can see that you'll be able to send around 3 million msg/s between threads (PUSH/PULL) from C or C++, around 300k using pyzmq (this factor 10 is sometimes called "interpreter tax"), but only around 7000 or so if you try to send Python objects using send_pyobj (which uses Pickle). That's a factor 430.
- p1esk 10y agoHow would you optimize sum.c to be faster?
- gravypod 10y agoGCC with -O3 might try to unroll this loop into a single constant. O(0) is pretty fast.
- supergarfield 10y agoThat's very likely. Clang 8.0 collapses the loop with any optimizer setting other than -O0. But if you had to do it manually, loop unrolling and SIMD instructions (although not part of standard C) would be good bets and can probably get you an order of magnitude.
- dom0 10y agoGCC as expected, O>2 sub rsp, 8 mov rdi, QWORD PTR [rsi+8] mov edx, 10 xor esi, esi call strtol <-- atoi xor eax, eax <-- zero return value add rsp, 8 ret <-- return from main Interestingly enough it does not elide the entire function body.
- gravypod 10y agoHow do you get objdump -S to print out non AT&T syntax? My output looked like this: 000000000400400 <main>: 400400: 48 83 ec 08 sub $0x8,%rsp 400404: 48 8b 7e 08 mov 0x8(%rsi),%rdi 400408: ba 0a 00 00 00 mov $0xa,%edx 40040d: 31 f6 xor %esi,%esi 40040f: e8 dc ff ff ff callq 4003f0 <strtol@plt> 400414: 31 c0 xor %eax,%eax 400416: 48 83 c4 08 add $0x8,%rsp 40041a: c3 retq 40041b: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1) Which I'm not a fan of. I've always wanted "add (store), (get)" but could never get that.
- dom0 10y agoNot on a development machine right now, so I just went to godbolt ;) https://godbolt.org/ https://godbolt.org/
- userbinator 10y agoUse the '-M intel' option.
- gens 10y ago-M intel
- deleted 10y ago[deleted]
- jwilk 10y agoITYM "O(1)". "O(0)" is pretty much meaningless.
- gravypod 10y agoI mean O(0) because no operation occured. The only operation that will occur is parsing the data which is not the problem specified. When looking at the loop, and just the loop, O(0) is the correct answer for this.
- dom0 10y agoWell the obvious answer would be, eliminate the loop, which is what any compiler optimizer will do ;) But let's assume that the operation is not quite so trivial like here, then this structure would be a prime example where each loop operation is independent from each other, so you can sum a vector in parallel (=SIMD) and then sum the vector once in the end. Also, since we're obviously not using any compiler optimizations, you can unroll the loop, which reduces per-iteration loop overhead (the conditional jump) and in such a simple case as here is bound to give a nice boost.
- p1esk 10y agoWhen you say "eliminate the loop", do you mean loop unrolling? They are compiling with -O2, I'm not sure if that does loop unrolling. If it does, how much unrolling does it do, exactly? I can't imagine it would construct a block of code with a billion add instructions.
- corndoge 10y agos += NUMBER or s = NUMBER
- danellis 10y agoEliminating the loop means the compiler looks at the code and says "the value computed in this loop is never actually used, so might as well just get rid of that code altogether".
- DannyBee 10y agoFirst, it's unused, so it'll just kill it. If it wasn't, most compilers can compute sum reductions, etc, pretty well. Anything that is easily expressed as a set of simple recurrences that can be solved, it'll solve.
- halomru 10y agoYou can't really do loop unrolling and constant folding as some suggest because the number of iterations is determined at run time. But assuming his CPU takes one cycle for an addition and one cycle for a conditional jump, his CPU only needs to run at 1GHz to achieve his result. Given that branch prediction should be nearly perfect for such a simple and short loop, modern x86 CPUs doing at least 4 integer additions per cycle, and typical CPU speeds in the range of 2-4 GHz, a properly optimized version should be nearly an order of magnitude faster. So either more aggressive compiler flags and maybe SIMD intrinsics, or hand written assembly (easy here, not so easy in the real world)
- dom0 10y ago> You can't really do loop unrolling and constant folding as some suggest because the number of iterations is determined at run time. Huh?
- halomru 10y agoThat question is a bit unspecific :D >NUMBER = atoi(argv[1]); argv is populated at runtime based on what the OS passed you. But you are right if you meant that my statement is too strong: you can't do arbitrary loop unrolling. You can jump to a loop that's unrolled once if the number is even, etc. There are certainly also optimizers that will just output the input without any loop, but that's beyond anything I would expect of a current production compiler.
- gravypod 10y agoIf you are going from 0 -> NUMBER and adding one to a variable every iteration, what will the variable's final result be? NUMBER. The compiler can see this and will just do the following: s = i = atoi(argv[1]); Now the loop is gone. Edit: This will still happen even if you're doing other stuff in there. GCC will attempt to inline and optimize like this. If it is impossible then you will see a loop with most of the stuff factored out of it.
- EvilTerran 10y ago
- DesiLurker 10y agofor a data parallel problem like that you could vectorize it using the SIMD unit. It never ceases to amaze me at any point how much of silicon real estate just sits idle because no one really bothered to look behind the curtain and tailor the code for a specific architecture. for reference, a recent Intel chip will have 256b wide vector unit (512 for server class chips) that can be treated as a vector of 8/16/32/64b units to do parallel math. at a typical 16b ops you get 16x speedup for practically nothing. plus its considerably more if you have predictable but non standard data access patterns. now <rant> IMO what the parent commenter was trying to say is often this punchline about premature optimizations used as catch-all justification for all the convenience/expediency related decisions taken. & also it just works well to create future work. unfortunately that never gets scheduled as I have seen management time frame shrink too. almost everyone is in quick & dirty 'working' version to book a success and move on. with this culture if you try to push resolving these 'technical debt' type issues you are just perceived as a downer. </rant>
- p1esk 10y agoI've heard that modern processors are designed with the expectation (or even a requirement) that no more than 10% of the chip will be active at once. In addition, there are power density constraints (even those 10% of the chip that can be active at once must not be concentrated in the same spot).
- dom0 10y agoNope, but processors, especially larger ones, have pretty advanced power and clock management which allows them to deal with power envelope and thermal envelope constraints. E.g. the two clocking and core voltage ladders in Xeon E5/E7 for AVX vs. non-AVX code. (Though this particular example is a bit of a sledge-hammer approach).