6 ms·

Again, you say these are "must haves." But in the real world of software, none of these would make any difference to most of the software being built today, muc

Again, you say these are "must haves." But in the real world of software, none of these would make any difference to most of the software being built today, much of which is being build in higher level languages for web applications/web sites/microservices etc. Let's say someone is building a micro-service in C#.Net. Why would any of this stuff matter to them? The company cares about features and moving forward quickly. It's rather like forcing all your developers to be able to code every type of different sorting algorithm when they are only ever going to call "mylist.Sort()" in reality. This seems like another of those occasions when HN misjudges what the vast reality of practical day to day software creation looks like. Most engineers are not writing low-level code, they are not working on hardware directly, and they don't need to know exactly how RAM works at the transistor level. I'm not saying it's not interesting, but it's not going to change how I write my for-loops and if statements or make calls to BigTable, etc.

dragontamer 8y ago
> I'm not saying it's not interesting, but it's not going to change how I write my for-loops and if statements or make calls to BigTable, etc. You might be surprised at how much changing your for loops can be when accessing matrix data. for(int i=0; i<10000; i++){ for(int j=0; j<10000; j++){ blah[j][i] = whatever(); // Column oriented is very slow. } } for(int j=0; j<10000; j++){ for(int i=0; i<10000; i++){ // Very fast: We move row-wise now. With luck, this is SIMD-vectorized by your compiler. blah[j][i] = whatever(); } } Test that out, and you'll see a major performance improvement. ----------- If someone is writing high performance code, the #1 goal is to be able to read your profiler's output. If you can't read what the profiler says (cache hits, TLB hits, memory stalls, etc. etc.) then you can't make sense of the data. The PDF goes deeper than I'd personally go, but there's some concepts here that are absolutely necessary if you actually want to understand what a decent profiler gives you these days.
- saberience 8y ago
  If I saw that code at my company, I'd ask why someone building a rest api for web-services had to iterate through a 10000*10000 2D array while calling a method of every single cell. This isn't a use case I've seen in my 10 year career thus far. Also, you have to understand that saving 1 or 2 milliseconds isn't important when compared to getting software built faster. For the typical use case, optimizing a for-loop like this for in-memory data isn't going to change the total performance of your program by even 0.5%. This is what so many people just don't understand. For modern web based applications, 99.9% of the time spent is doing IO, either hard-drive, data storage, or across the network. Optimizing those calls is FAR more important, than wasting time trying to save 1 millisecond in a for-loop which is iterating over 100 in-memory objects. This is where the understanding that the practical reality of building software for a real business is very different to theoretical examples drummed up by computer scientists on discussion boards. I see so many engineers trying to make their in-memory code faster by parallizing it, saving (if they're lucky) 1 or 2 milliseconds, but making their code far less maintainable and potentially introducing bugs, while the users wouldn't notice any practical difference in the app. Meanwhile, the app really does feel slow, because some numb-nuts made a call to some api and blocked the ui thread.
  - magoghm 8y ago
    Were I work we have to process a few billion records per day. Knowing about how memory works and writing the code in a way that uses memory bandwidth efficiently, allows us to process all those records in smallish AWS instance instead of having to use Hadoop on a much more expensive cluster of instances.
    - saberience 8y ago
      Hadoop is for "big data." Big data is commonly defined as minimum of petabytes of data. That is, thousands of terabytes. Our ingest of new events to our cluster is upwards of 25B per day and we keep all that data in perpetuity. Our hadoop cluster is relatively small at 5PB right now, but I would be impressed indeed if you were processing PB of data on a smallish AWS instance. If you were considering using Hadoop for work that can be processed on a "smallish instance" then I'd suggest you maybe don't really understand big-data or the normal workloads for which Hadoop is intended. For example, we run ML models on our Hadoop cluster which take hours to run distributed over around 100 nodes. Let me know when this can be done on a "smallish instance."
- bogomipz 8y ago
  Can you elaborate why the second is faster in the general case? Is this an issue of row major vs column major orientation? Also does your example also hold in the absence of SIMD? Thanks.
  - dragontamer 8y ago
    There's at least 2 reasons (+1 non-reason) why it is slow. 1. L1 cache lines are 64-bytes long. By fetching column-wise, you are wasting the bandwidth between L1 and main-memory. L1 cache will always fetch 64-bytes. By moving "with" the cache, you allow the L1 --> Main Memory data-transfers to be far more efficient. 2. Virtual Memory is translated by the TLB before it returns the actual value. Moving within a 4kB page is more efficient than moving across pages. The non-reason: * Hardware prefetcher probably works, even on column-oriented data. All of these reasons hold even if the SIMD-optimizer fails. If the SIMD-optimizer is actually working, you'll more efficiently load/store to L1 cache. But this is likely a memory-bound problem and optimizing the core isn't as important.
    - bogomipz 8y ago
      Make perfect sense, thanks for the concise explanations. Cheers.
- esmi 8y ago
  I have to admit, I was skeptical but my complier did pick SIMD for the second and not the first and it did make a huge difference. % cat t.c #include <sys/time.h> #include <sys/resource.h> #include <stdio.h> double get_time() { struct timeval t; struct timezone tzp; gettimeofday(&t, &tzp); return t.tv_sec + t.tv_usec*1e-6; } int blah[SIZE][SIZE]; int whatever() { static int i=0; return ++i; } int main() { double t0 = get_time(); for(int i=0; i<SIZE; i++){ for(int j=0; j<SIZE; j++){ blah[j][i] = whatever(); // Column oriented is very slow. } } double t1 = get_time(); for(int j=0; j<SIZE; j++){ for(int i=0; i<SIZE; i++){ // Very fast: We move row-wise now. With luck, this is SIMD-vectorized by your compiler. blah[j][i] = whatever(); } } double t2 = get_time(); printf("SIZE=%5d dt1=%4.3e dt2=%4.3e\n",SIZE,t1-t0,t2-t1); return 0; } % for (( i=1; i<100000 ; i*=10 )) do gcc -DSIZE=$i -O t.c; ./a.out; done SIZE= 1 dt1=4.179e-04 dt2=0.000e+00 SIZE= 10 dt1=5.190e-04 dt2=0.000e+00 SIZE= 100 dt1=5.062e-04 dt2=9.537e-07 SIZE= 1000 dt1=4.014e-03 dt2=1.490e-04 SIZE=10000 dt1=1.347e+00 dt2=4.349e-02 2.8G Core i7 1600MHz DDR3
  - WallWextra 8y ago
    n.b. there would be a difference even without vectorization
  - gdy 8y ago
    Now you could try to time it with -fno-tree-vectorize or whatever gcc uses nowadays. You might be surprised again :)
    - dragontamer 8y ago
      Yup yup. SIMD is a CPU-level optimization, but the problem (at size 10,000 x 10,000) is DDR4 memory-limited. SIMD only really makes a difference at the L1 or L2 cache levels. Its a fancy micro-optimization that compilers do and can improve code speed in those cases... But the "big" change, going from column-wise traversal into row-wise traversal, is the huge memory optimization that programmers should know about. It just so happens that SIMD-optimizations are also easier for compilers to figure out on row-wise traversal, so you get SIMD-optimization "for free" in many cases.
3JPLW 8y ago
Sure, you don't really need to know any of this stuff unless you're actually needing to optimize code beyond the lowest hanging fruit. My list presupposes you've hit a wall and need the best performance you can get. That's not always the case, but I certainly wouldn't say that these optimizations don't make a difference in the "real world of softare." False sharing alone can be the difference between a 16x parallelization speedup and a 1000x+ slowdown over the naive serial algorithm. 16x can be the difference between actionable results tomorrow or three weeks from today... and if you didn't know about it, the 1000x+ slowdown would be otherwise inscrutable.
- cortesoft 8y ago
  Right, the question then becomes "What percentage of programmers are going to need to optimize code beyond the lowest hanging fruit" I don't know exactly what that number is going to be, but I do know it is going to be a lot less than 100%.
andyjpb 8y ago
Having a certain amount of Mechanical Sympathy (https://mechanical-sympathy.blogspot.com/2011/07/why-mechanical-sympathy.html https://mechanical-sympathy.blogspot.com/2011/07/why-mechani... ) is important for having a good intuitive feel for the appropriate way to implement something. For example, an O(n^2) algorithm can often beat an O(n) one when n is "small". How do you get that "experienced" feel for which to choose when you're designing your program? This is even important for people doing REST APIs, Web Services and Microservices. Milliseconds matter when the load gets beyond a certain point and your system ends up full of stragglers. How do you get that "experienced" feel for where that point might be and how far you can push a particular architecture without investing in a major rework? The effect of tail latency on most web servers might surprise you: http://latencytipoftheday.blogspot.com/ http://latencytipoftheday.blogspot.com/ http://latencytipoftheday.blogspot.com/2014/06/latencytipoftheday-most-page-loads.html http://latencytipoftheday.blogspot.com/2014/06/latencytipoft... TL;DR: most of your visitors will experience the bottom 1% of your performance curve on every page load.
nickpsecurity 8y ago
"Why would any of this stuff matter to them?" Back when I started, both the BASIC and Common Lisp camps had heuristics on helping the compiler generate more efficient code. The reasons are similar to today: increase throughput for scaling or customer experience while simultaneously reducing what you spend on hardware and/or electricity. Lean, easy-to-manage setups can also sometimes let you afford extra personnel to build stuff faster. There's definitely a cut-off where micro-optimizations wouldn't be necessary. A lot of efficiency gains are simple, though. Just gotta consistently use what you learn.
scoutt 8y ago
"most of the software being built today" "web applications/web sites/microservices" The world is bigger than you think it is. There could be more code in making a single AAA videogame than in the entire Amazon infrastructure.

dragontamer 8y ago

> I'm not saying it's not interesting, but it's not going to change how I write my for-loops and if statements or make calls to BigTable, etc. You might be surprised at how much changing your for loops can be when accessing matrix data. for(int i=0; i<10000; i++){ for(int j=0; j<10000; j++){ blah[j][i] = whatever(); // Column oriented is very slow. } } for(int j=0; j<10000; j++){ for(int i=0; i<10000; i++){ // Very fast: We move row-wise now. With luck, this is SIMD-vectorized by your compiler. blah[j][i] = whatever(); } } Test that out, and you'll see a major performance improvement. ----------- If someone is writing high performance code, the #1 goal is to be able to read your profiler's output. If you can't read what the profiler says (cache hits, TLB hits, memory stalls, etc. etc.) then you can't make sense of the data. The PDF goes deeper than I'd personally go, but there's some concepts here that are absolutely necessary if you actually want to understand what a decent profiler gives you these days.

saberience 8y ago
If I saw that code at my company, I'd ask why someone building a rest api for web-services had to iterate through a 10000*10000 2D array while calling a method of every single cell. This isn't a use case I've seen in my 10 year career thus far. Also, you have to understand that saving 1 or 2 milliseconds isn't important when compared to getting software built faster. For the typical use case, optimizing a for-loop like this for in-memory data isn't going to change the total performance of your program by even 0.5%. This is what so many people just don't understand. For modern web based applications, 99.9% of the time spent is doing IO, either hard-drive, data storage, or across the network. Optimizing those calls is FAR more important, than wasting time trying to save 1 millisecond in a for-loop which is iterating over 100 in-memory objects. This is where the understanding that the practical reality of building software for a real business is very different to theoretical examples drummed up by computer scientists on discussion boards. I see so many engineers trying to make their in-memory code faster by parallizing it, saving (if they're lucky) 1 or 2 milliseconds, but making their code far less maintainable and potentially introducing bugs, while the users wouldn't notice any practical difference in the app. Meanwhile, the app really does feel slow, because some numb-nuts made a call to some api and blocked the ui thread.
- magoghm 8y ago
  Were I work we have to process a few billion records per day. Knowing about how memory works and writing the code in a way that uses memory bandwidth efficiently, allows us to process all those records in smallish AWS instance instead of having to use Hadoop on a much more expensive cluster of instances.
  - saberience 8y ago
    Hadoop is for "big data." Big data is commonly defined as minimum of petabytes of data. That is, thousands of terabytes. Our ingest of new events to our cluster is upwards of 25B per day and we keep all that data in perpetuity. Our hadoop cluster is relatively small at 5PB right now, but I would be impressed indeed if you were processing PB of data on a smallish AWS instance. If you were considering using Hadoop for work that can be processed on a "smallish instance" then I'd suggest you maybe don't really understand big-data or the normal workloads for which Hadoop is intended. For example, we run ML models on our Hadoop cluster which take hours to run distributed over around 100 nodes. Let me know when this can be done on a "smallish instance."
bogomipz 8y ago
Can you elaborate why the second is faster in the general case? Is this an issue of row major vs column major orientation? Also does your example also hold in the absence of SIMD? Thanks.
- dragontamer 8y ago
  There's at least 2 reasons (+1 non-reason) why it is slow. 1. L1 cache lines are 64-bytes long. By fetching column-wise, you are wasting the bandwidth between L1 and main-memory. L1 cache will always fetch 64-bytes. By moving "with" the cache, you allow the L1 --> Main Memory data-transfers to be far more efficient. 2. Virtual Memory is translated by the TLB before it returns the actual value. Moving within a 4kB page is more efficient than moving across pages. The non-reason: * Hardware prefetcher probably works, even on column-oriented data. All of these reasons hold even if the SIMD-optimizer fails. If the SIMD-optimizer is actually working, you'll more efficiently load/store to L1 cache. But this is likely a memory-bound problem and optimizing the core isn't as important.
  - bogomipz 8y ago
    Make perfect sense, thanks for the concise explanations. Cheers.
esmi 8y ago
I have to admit, I was skeptical but my complier did pick SIMD for the second and not the first and it did make a huge difference. % cat t.c #include <sys/time.h> #include <sys/resource.h> #include <stdio.h> double get_time() { struct timeval t; struct timezone tzp; gettimeofday(&t, &tzp); return t.tv_sec + t.tv_usec*1e-6; } int blah[SIZE][SIZE]; int whatever() { static int i=0; return ++i; } int main() { double t0 = get_time(); for(int i=0; i<SIZE; i++){ for(int j=0; j<SIZE; j++){ blah[j][i] = whatever(); // Column oriented is very slow. } } double t1 = get_time(); for(int j=0; j<SIZE; j++){ for(int i=0; i<SIZE; i++){ // Very fast: We move row-wise now. With luck, this is SIMD-vectorized by your compiler. blah[j][i] = whatever(); } } double t2 = get_time(); printf("SIZE=%5d dt1=%4.3e dt2=%4.3e\n",SIZE,t1-t0,t2-t1); return 0; } % for (( i=1; i<100000 ; i*=10 )) do gcc -DSIZE=$i -O t.c; ./a.out; done SIZE= 1 dt1=4.179e-04 dt2=0.000e+00 SIZE= 10 dt1=5.190e-04 dt2=0.000e+00 SIZE= 100 dt1=5.062e-04 dt2=9.537e-07 SIZE= 1000 dt1=4.014e-03 dt2=1.490e-04 SIZE=10000 dt1=1.347e+00 dt2=4.349e-02 2.8G Core i7 1600MHz DDR3
- WallWextra 8y ago
  n.b. there would be a difference even without vectorization
- gdy 8y ago
  Now you could try to time it with -fno-tree-vectorize or whatever gcc uses nowadays. You might be surprised again :)
  - dragontamer 8y ago
    Yup yup. SIMD is a CPU-level optimization, but the problem (at size 10,000 x 10,000) is DDR4 memory-limited. SIMD only really makes a difference at the L1 or L2 cache levels. Its a fancy micro-optimization that compilers do and can improve code speed in those cases... But the "big" change, going from column-wise traversal into row-wise traversal, is the huge memory optimization that programmers should know about. It just so happens that SIMD-optimizations are also easier for compilers to figure out on row-wise traversal, so you get SIMD-optimization "for free" in many cases.

3JPLW 8y ago

Sure, you don't really need to know any of this stuff unless you're actually needing to optimize code beyond the lowest hanging fruit. My list presupposes you've hit a wall and need the best performance you can get. That's not always the case, but I certainly wouldn't say that these optimizations don't make a difference in the "real world of softare." False sharing alone can be the difference between a 16x parallelization speedup and a 1000x+ slowdown over the naive serial algorithm. 16x can be the difference between actionable results tomorrow or three weeks from today... and if you didn't know about it, the 1000x+ slowdown would be otherwise inscrutable.

cortesoft 8y ago
Right, the question then becomes "What percentage of programmers are going to need to optimize code beyond the lowest hanging fruit" I don't know exactly what that number is going to be, but I do know it is going to be a lot less than 100%.

andyjpb 8y ago

Having a certain amount of Mechanical Sympathy (https://mechanical-sympathy.blogspot.com/2011/07/why-mechanical-sympathy.html https://mechanical-sympathy.blogspot.com/2011/07/why-mechani... ) is important for having a good intuitive feel for the appropriate way to implement something. For example, an O(n^2) algorithm can often beat an O(n) one when n is "small". How do you get that "experienced" feel for which to choose when you're designing your program? This is even important for people doing REST APIs, Web Services and Microservices. Milliseconds matter when the load gets beyond a certain point and your system ends up full of stragglers. How do you get that "experienced" feel for where that point might be and how far you can push a particular architecture without investing in a major rework? The effect of tail latency on most web servers might surprise you: http://latencytipoftheday.blogspot.com/ http://latencytipoftheday.blogspot.com/ http://latencytipoftheday.blogspot.com/2014/06/latencytipoftheday-most-page-loads.html http://latencytipoftheday.blogspot.com/2014/06/latencytipoft... TL;DR: most of your visitors will experience the bottom 1% of your performance curve on every page load.

nickpsecurity 8y ago

"Why would any of this stuff matter to them?" Back when I started, both the BASIC and Common Lisp camps had heuristics on helping the compiler generate more efficient code. The reasons are similar to today: increase throughput for scaling or customer experience while simultaneously reducing what you spend on hardware and/or electricity. Lean, easy-to-manage setups can also sometimes let you afford extra personnel to build stuff faster. There's definitely a cut-off where micro-optimizations wouldn't be necessary. A lot of efficiency gains are simple, though. Just gotta consistently use what you learn.

scoutt 8y ago

"most of the software being built today" "web applications/web sites/microservices" The world is bigger than you think it is. There could be more code in making a single AAA videogame than in the entire Amazon infrastructure.