4 ms·

No, it's not a "surprised expert routine". I'm going to ignore the aggressive undertone in your comment for the sake of the conversation. A vector of elements

No, it's not a "surprised expert routine". I'm going to ignore the aggressive undertone in your comment for the sake of the conversation. A vector of elements is contiguous in (virtual) memory. An addition operation takes one single cycle on most, if not all, CPUs, given that the values are available. Since memory access is orders of magnitude slower than this CPU operation, your runtime here will be dominated by the time you need to get the values from memory. In this case, you want to make your memory access patterns as predictable as possible, to hit as much cache as you can. Sequential iteration over a contiguous block of memory is the most cache-friendly memory access pattern. You may incur some penalties when you hit page boundaries and jump to another page somewhere else in physical memory, but you can't do better than that. Divide-and-conquer non-obviously jumps between vector elements, and, depending on the size of the vector, it will miss the cache more often than the ordinary loop iteration algo. I imagine the first version would be as fast as the last one if TCO was in effect... but it wasn't. Using reduce (which proved to be significantly faster than the first couple algos) does the same, but it incurs an overhead within the Python interpreter from calling the lambda. Yes, unlike other methods, it may be parallelized, but it won't help much because RAM is shared across cores, and waiting time for it will still dominate the runtime. "Non-obvious" algorithms can shine when they reduce the problem's big O cost (going from O(n^2) insertion sort to O(n log n) quicksort) and/or the CPU time dominates the real time (opening the door for parallelization). But when you're memory-bound it simply doesn't help. A plain old loop will be faster (or as fast). So I'm not a "surprised expert". I don't think of myself as an expert as I have zero formal education in CS or programming or whatever. Maybe this is obvious to me because I am used to writing C/C++ code, or maybe because I think a lot about how programs really work "on the inside". Still, I maintain that kind of thinking can be very useful when you're analyzing the practical implications of how your algorithms perform.

srean 12y ago
You are assuming that Python code executes the same way that a C code does. There is a whole lot more going on in a Python execution, so intuition drawn from C does not apply line by line to Python code. You have to think in terms of Python bytecode and think about how that byte code is interpreted by CPython. You have to think about the fact that Python is dynamic so for every value it also has to look up the type. But then I would not have known all this when I was 17, not even the C execution model, so keep hacking. In fact I redid my tests and reduce is actually consistently faster than the for loop. Not by much but always faster (by that I mean the minimum of 10 runs of reduce is faster than the minimum of 10 runs of for loop. My box was fairly loaded during these tests https://news.ycombinator.com/item?id=7961091 https://news.ycombinator.com/item?id=7961091 , the numbers halved when I tried again, but their relative ranking remains the same.
- thegeomaster 12y ago
  That is a fair point. Perhaps I got too carried away by analyzing the raw performance that I forgot what kinds of things need to happen behind the scenes. However, I imagine that the type checking has to be done by reduce as well as within a loop. Reduce is probably faster because the underlying native C function can iterate over a vector faster than the bytecode-compiled for loop, and since you're passing a builtin to it, it doesn't ever need to leave the native realm until it returns from reduce. If the for loop wasn't JIT'ed, I'd understand why this is slower. What about PyPy? How about trying the code on that? Maybe it will be smart enough to compile the for loop into native code that is equivalent to the reduce builtin. I'm really curious about what happens under the hood here...
parennoob 12y ago
All of that was completely non-obvious to me, so thanks for laying it out. I guess the core concept here is that when your algorithm is memory-bound, you have to think about cache access patterns, and how your program's elements in memory will be mapped in memory. At least that helps me understand why the naive loop is faster than the divide by two. Still don't exactly understand why the lambda would be slower, but I'll work on it. See how you helped me understand something more? If I had just read your "this is obvious" comment, I would have wandered away scratching my head and thinking, "Oh okay, guess I'm too dumb to understand this stuff. Let me go read some comics." I come across this attitude a lot in real life too, "Oh it's obvious. Isn't it?", and get discouraged a lot because of it. A visceral reaction to that yet again was the reason for the aggressive undertone. Apologies for it.
- thegeomaster 12y ago
  The lambda approach is slower because a function call always has some overhead. In lower-level C-like languages the overhead is usually lighter than in interpreted languages such as Python. In this case, reduce will have to call the lambda everytime, which is a few more instructions for the processor and some checking by the interpreter. Then the lambda will compute the sum, and then return to the caller. It's not a lot of time, but it's certainly faster than knowing what you need to do at the call site. As srean pointed out, however, it's not all black and white like I described. He raises some good points like what the Python interpreter does when it needs to look up the type of the variable, etc etc. I come across those kinds of "it's obvious" things all the time, too, especially in the world of more functional and powerful languages. When people write Ruby or Lisp (I'm learning them ATM) some solutions are simply obvious to them, when I would've done the complete opposite. I got used to this and simply accepted that these will become obvious to me one day, when I grok the concepts. And when I really don't understand something that is "obvious", I ask, and people are very happy to explain it to me. I've never once encountered a condescending reaction. So no need to get upset because of it. We're all used to doing different things and different things are obvious to us. Doesn't mean that anyone is arrogant or something, it's simply that people usually look at the world through their own eyes :)

srean 12y ago

You are assuming that Python code executes the same way that a C code does. There is a whole lot more going on in a Python execution, so intuition drawn from C does not apply line by line to Python code. You have to think in terms of Python bytecode and think about how that byte code is interpreted by CPython. You have to think about the fact that Python is dynamic so for every value it also has to look up the type. But then I would not have known all this when I was 17, not even the C execution model, so keep hacking. In fact I redid my tests and reduce is actually consistently faster than the for loop. Not by much but always faster (by that I mean the minimum of 10 runs of reduce is faster than the minimum of 10 runs of for loop. My box was fairly loaded during these tests https://news.ycombinator.com/item?id=7961091 https://news.ycombinator.com/item?id=7961091 , the numbers halved when I tried again, but their relative ranking remains the same.

thegeomaster 12y ago
That is a fair point. Perhaps I got too carried away by analyzing the raw performance that I forgot what kinds of things need to happen behind the scenes. However, I imagine that the type checking has to be done by reduce as well as within a loop. Reduce is probably faster because the underlying native C function can iterate over a vector faster than the bytecode-compiled for loop, and since you're passing a builtin to it, it doesn't ever need to leave the native realm until it returns from reduce. If the for loop wasn't JIT'ed, I'd understand why this is slower. What about PyPy? How about trying the code on that? Maybe it will be smart enough to compile the for loop into native code that is equivalent to the reduce builtin. I'm really curious about what happens under the hood here...

parennoob 12y ago

All of that was completely non-obvious to me, so thanks for laying it out. I guess the core concept here is that when your algorithm is memory-bound, you have to think about cache access patterns, and how your program's elements in memory will be mapped in memory. At least that helps me understand why the naive loop is faster than the divide by two. Still don't exactly understand why the lambda would be slower, but I'll work on it. See how you helped me understand something more? If I had just read your "this is obvious" comment, I would have wandered away scratching my head and thinking, "Oh okay, guess I'm too dumb to understand this stuff. Let me go read some comics." I come across this attitude a lot in real life too, "Oh it's obvious. Isn't it?", and get discouraged a lot because of it. A visceral reaction to that yet again was the reason for the aggressive undertone. Apologies for it.

thegeomaster 12y ago
The lambda approach is slower because a function call always has some overhead. In lower-level C-like languages the overhead is usually lighter than in interpreted languages such as Python. In this case, reduce will have to call the lambda everytime, which is a few more instructions for the processor and some checking by the interpreter. Then the lambda will compute the sum, and then return to the caller. It's not a lot of time, but it's certainly faster than knowing what you need to do at the call site. As srean pointed out, however, it's not all black and white like I described. He raises some good points like what the Python interpreter does when it needs to look up the type of the variable, etc etc. I come across those kinds of "it's obvious" things all the time, too, especially in the world of more functional and powerful languages. When people write Ruby or Lisp (I'm learning them ATM) some solutions are simply obvious to them, when I would've done the complete opposite. I got used to this and simply accepted that these will become obvious to me one day, when I grok the concepts. And when I really don't understand something that is "obvious", I ask, and people are very happy to explain it to me. I've never once encountered a condescending reaction. So no need to get upset because of it. We're all used to doing different things and different things are obvious to us. Doesn't mean that anyone is arrogant or something, it's simply that people usually look at the world through their own eyes :)