5 ms·

I don't understand all the hate about the post, one of the referenced articles is actually very good and gives a quite compelling case (maybe it should have bee

• betterunix 13y ago
  I do not think our theoretical models diverge from reality; the theoretical models are based on how the performance relates to the size of the input, and remain valid even if you have a very fast computer. What modern architectures have done is to change the constant factors a bit; that just raises the threshold for problem sizes, but it does not eliminate it. Sure, there are cases where asymptotic analysis can be dismissed. Matrix multiplication comes to mind: the fastest algorithms have impractically large constant factors. Usually, though, asymptotic analysis does matter, because it is often the case that input sizes will grow unexpectedly.
  • stiff 13y ago
    This has nothing to do with simply having a "fast computer", it would be all fine if we just used 486s clocked at 10Ghz, but we don't, the changes in the architecture of CPUs do indeed make the theoretical model more diverged from reality, because it presupposes a lot of things, like that every instruction takes the same time to execute, also implying that instruction execution times are independent, that one instruction gets executed at a time, etc. If those assumptions do not hold you cannot assume the factor is really constant, and even if it were so, you cannot dismiss this difference indefinitely on this ground, if on datasets of the size commonly encountered in practice the algorithms with a larger asymptotic complexity start outperforming the ones with a smaller one. For matrix multiplication this was known for years, for linked lists it is a relatively new development that came with larger and faster CPU caches etc.
    • betterunix 13y ago
      Except that the theoretical model is not affected by any of the things you mentioned. The existence of caches, branch prediction, instruction reordering, parallel execution, etc. does not chance as problem sizes change. If your inputs become large enough, you will reach the upper limit of your CPU's ability to speed up execution with those features. In the limit, the asymptotics still matter, and experience has shown that the limit is not at all far-fetched in most cases. What makes matrix multiplication an exceptional case is that the constant factor on the best known algorithm is so large that we do not know how to build a computer with enough memory to store a problem large enough to overcome that constant. That is not the case with this analysis of linked lists; all one can say is that the data sets chosen in that particular article (possibly representative of the most common data sets) are not big enough. One can certainly store a large enough data set to overcome the advantages arrays have, and so the only real question is, "Is it possible that the inputs will be so large?" Maybe the answer is truly, "No, that is unlikely." I am skeptical, though, as there are not many cases where such statements can be made. Even software written for embedded systems that target specific products is likely to be repurposed for new systems with different inputs. Even researchers, who write software for the particular datasets sitting on their hard drives, often re-use their code in future work. There are "border" cases, like integer multiplication, but typically libraries will just select the best algorithm for a given input size (e.g. for multiplication, you'll probably only see FFT methods applied above a particular threshold). Perhaps linked lists are now a "border" case, but all that would mean is that we need to use abstract "sequence" operations that dynamically choose particular implementations to use as their sizes change.
      • LesZedCB 13y ago
        I don't think he means big-O notation as a theoretical model... Processors are not the same as they were when they were single core machines. The entirety of computing and thinking about problem solving has become different than it was before 2005 because of multicore processor architecture. Projects like parallela make this obvious. Programmers in general don't understand how much this makes things that weren't a big deal 10 years ago a huge deal now. And stuff with threading is not even the tip of it. Threading is trivial compared to real parallelism. Our model of computation is different than it is now, and will continue to diverge until everybody starts thinking with parallel as a first priority. That's the most convincing argument the OP makes about why linked lists are bad. In parallel computing, they are definitely hard/bad.
• gsg 13y ago
  That's a much better, much more careful article. For example: > Just in case my Mea Culpa and Introduction did not cover it. Let me be clear: This article is not disqualifying the linked-list for other types of usages, such as when it contains types that have pointers to other types, large and expensive-to-copy types (and yes, POD can also be too large). The OP displays no such nuanced understanding.