4 ms·

I don't get it. Isn't it obvious that the last routine would be the fastest? What is the point of the other algos?

ColinWright 12y ago
Added in edit: Why do you think the last version must be faster? In short, if you implement these things on multi-core machines, then no, it isn't obvious that the last algorithm will be the fastest. With modern experimental parallelizing compilers on suitable hardware, the exact algorithm matters, and these show significantly different results. I spend most of my time working on "odd" hardware configurations, and as a result, sometimes these more "interesting" algorithms are the ones I immediately turn to rather than doing what others think of as instantly obvious.
- kabdib 12y ago
  I would expect that for a vector of things in Python, iteration would be fastest. The array is in memory, right there. Spooling up a series of parallel threads (and in Python, establishing the right locking, whatever that is...) just to distribute a bunch of ADD operations seems like a waste of time. If the problem domain is indeed massive and needs to be parallel, okay. But the introduction was about doing some simple image processing, so the direction that this guy took with parallelism surprised me. I wouldn't call this a waste of time (I learned some more Python, which is nice). But I think I would have had this done in a minute or two and moved on.
- srean 12y ago
  That sure surprised me, I would have rooted for reduce. May be lambda overhead is screwing it up. Could you try the reduction with from operator import add I cannot try it out on Colin's version of Python, however on Python 2.7.6 | 32-bit | [GCC 4.1.2 20080704] from operator import add def sum1(l): return reduce(lambda a,b:a+b,l) def sum2(l): return reduce(add,l) The times to compute sum1(l) and sum2(l) on xrange(3333333) are 11.69s and 6.38s respectively. So sum2 is about twice faster, which is expected. The timings are the minimum of 5 runs. Given Colin's reduce was about twice slower than his for loop, there is a fair chance that the updated reduce will beat the for loop occasionally. I was surprised that trying the same on an array turned out to be marginally slower than using an xrange. I would have expected the array to be faster. xrange is possibly faster because it can be held in cache whereas the array would definitely spill outside, although I expected locality to be a win.
onli 12y ago
It depends where you come from. If you started with the typical C-influenced programming languages, sure, the last one is not only obviously the fastest (edit: on a normal computer), it is also the first one you would write. But things are different if you are used to write in functional lisp-like languages, and one can clearly see that he is coming from that direction (using recursion as first try, knowing reduce, …).
- thegeomaster 12y ago
  But a Lisper would do something along the lines of (defun list-sum (lyst &optional (acc 0)) (if (eql 0 (length lyst)) acc (list-sum (cdr lyst) (+ acc (car lyst))))) And any respectable compiler (with TCO) would compile it to a plain old loop. In this case, I'm puzzled because the author implemented this solution knowing that it is going to be compiled to a slow recursive routine.
  - adwf 12y ago
    I'd hope they'd also first think of: (reduce #'+ list-of-numbers) Then using a library like lparallel [1], you can convert it to the parallel version easily: (preduce '+ list-of-numbers) [1] http://lparallel.org/preduce/ http://lparallel.org/preduce/
parennoob 12y ago
This is part of the "surprised expert" routine that I would like to see go out of vogue. No, it isn't entirely obvious to me that the last routine is the fastest. Perhaps I'm a person who is running a web design company in Outer Mongolia "coding up webpages" using Microsoft FrontPage. But please, for the love of Cthulhu, could you elaborate on why this is obvious?
- thegeomaster 12y ago
  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.

Added in edit: Why do you think the last version must be faster? In short, if you implement these things on multi-core machines, then no, it isn't obvious that the last algorithm will be the fastest. With modern experimental parallelizing compilers on suitable hardware, the exact algorithm matters, and these show significantly different results. I spend most of my time working on "odd" hardware configurations, and as a result, sometimes these more "interesting" algorithms are the ones I immediately turn to rather than doing what others think of as instantly obvious.

kabdib 12y ago
I would expect that for a vector of things in Python, iteration would be fastest. The array is in memory, right there. Spooling up a series of parallel threads (and in Python, establishing the right locking, whatever that is...) just to distribute a bunch of ADD operations seems like a waste of time. If the problem domain is indeed massive and needs to be parallel, okay. But the introduction was about doing some simple image processing, so the direction that this guy took with parallelism surprised me. I wouldn't call this a waste of time (I learned some more Python, which is nice). But I think I would have had this done in a minute or two and moved on.
srean 12y ago
That sure surprised me, I would have rooted for reduce. May be lambda overhead is screwing it up. Could you try the reduction with from operator import add I cannot try it out on Colin's version of Python, however on Python 2.7.6 | 32-bit | [GCC 4.1.2 20080704] from operator import add def sum1(l): return reduce(lambda a,b:a+b,l) def sum2(l): return reduce(add,l) The times to compute sum1(l) and sum2(l) on xrange(3333333) are 11.69s and 6.38s respectively. So sum2 is about twice faster, which is expected. The timings are the minimum of 5 runs. Given Colin's reduce was about twice slower than his for loop, there is a fair chance that the updated reduce will beat the for loop occasionally. I was surprised that trying the same on an array turned out to be marginally slower than using an xrange. I would have expected the array to be faster. xrange is possibly faster because it can be held in cache whereas the array would definitely spill outside, although I expected locality to be a win.

onli 12y ago

It depends where you come from. If you started with the typical C-influenced programming languages, sure, the last one is not only obviously the fastest (edit: on a normal computer), it is also the first one you would write. But things are different if you are used to write in functional lisp-like languages, and one can clearly see that he is coming from that direction (using recursion as first try, knowing reduce, …).

thegeomaster 12y ago
But a Lisper would do something along the lines of (defun list-sum (lyst &optional (acc 0)) (if (eql 0 (length lyst)) acc (list-sum (cdr lyst) (+ acc (car lyst))))) And any respectable compiler (with TCO) would compile it to a plain old loop. In this case, I'm puzzled because the author implemented this solution knowing that it is going to be compiled to a slow recursive routine.
- adwf 12y ago
  I'd hope they'd also first think of: (reduce #'+ list-of-numbers) Then using a library like lparallel [1], you can convert it to the parallel version easily: (preduce '+ list-of-numbers) [1] http://lparallel.org/preduce/ http://lparallel.org/preduce/

parennoob 12y ago

This is part of the "surprised expert" routine that I would like to see go out of vogue. No, it isn't entirely obvious to me that the last routine is the fastest. Perhaps I'm a person who is running a web design company in Outer Mongolia "coding up webpages" using Microsoft FrontPage. But please, for the love of Cthulhu, could you elaborate on why this is obvious?

thegeomaster 12y ago
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.