17 ms·

Why Python, Ruby, and Javascript are Slow

367 points by jasonostrander 14y ago

arocks 14y ago
It is almost time that people stop referring to Languages as Fast or Slow. It is an implementation that is fast or slow, not a language.
- masklinn 14y ago
  Have you considered reading the fucking presentation before snarking out on it?
  - arocks 14y ago
    What makes you think I didn't? The author seems to agree with me. He even concludes that we should improve the implementation rather than the language for optimisation.
    - ynniv 14y ago
      No, the author concludes that languages based on hash table lookups and lacking copy avoidance mechanisms are inherently slower.
    - masklinn 14y ago
      Which makes your comment useless and redundant. The very point of the presentation pretty much being "this declaration makes no sense"
    - tptacek 14y ago
      I didn't get that from the presentation at all. What I read is a guy complaining that idiomatic Python is necessarily slow because it depends, for its clarity and terseness, on not controlling allocations or memory layout, and that Python- the- language abets the problem by having its standard library build on the same idiom.
- systematical 14y ago
  I think its time people stop using shitty slide decks to get their point across.
  - rscott 14y ago
    He gave a talk yesterday at Waza, Heroku's conference. I believe Heroku is planning on uploading videos of the talks in the coming days. I've been interested in this talk since I saw it announced on Twitter, but prefer to watch/listen rather than go through these slides.
  - aroberge 14y ago
    Didn't it occur to you that these slides were for a presentation and that sharing them enable more people than just those that were at the presentation be informed of their content? I, for one, am very grateful to speakers that make the extra effort required to share with a larger group what they have already shared (or are about to share) with a smaller group.
    - alxp 14y ago
      Much better to turn your notes from the talk into an article than to just throw up the slides.
      - koide 14y ago
        But much harder. Slides (with notes!) are a VERY good compromise. Remember: the author does not owe you anything.
- cpressey 14y ago
  This is one of my pet peeves, too.
- rwj 14y ago
  While I agree that implementations can be fast or slow, it does not completely eliminate the effect of the language. At minimum, different languages require different levels of effort to reach their optimum. So, while a language can be hurt by a poor implementation, it does not follow that all languages have the same potential performance. As an example, just consider the enormous amount of effort that has gone into the JVM, and Java is still generally considered to be ~2x slower that C.
- simonster 14y ago
  It's true that implementation makes a bigger difference to performance than language features, but language features can indeed affect speed. One clear example is that a language that checks for integer overflow will be slower than a language that doesn't. There are a lot of situations where there's no way you could optimize out the extra instructions you'd need to check for overflow. Some language features are easy to optimize away for some common cases (e.g. array bounds checks, so that your program throws an exception instead of segfaulting), but you can't optimize these if, for example, you're iterating over data you read from a file using indices you also read from that file.
wheaties 14y ago
Great bit of slides. Straight and to the point. If you've ever ventured under the hood of Python you'd see this in the code. If you've ever had to optimize the bejeesus out of code in C++ or C, you'd know exactly the kinds of things he's talking about.
cheald 14y ago
Kind of a poorly-named deck. It's really about why programs use features of these languages that end up causing poor performance relative to C, rather than why the individual VMs themselves are slow. It's no surprise that trading the byte-precision of C for the convenience of a garbage collector and heap-allocated data structures results in a performance decrease. Dynamically-typed languages are often easier to program in, but require more copying (and memory allocation) as a result. Hash tables are heap-allocated and have to be garbage collected, but they're flexible - something you don't get with structs. Allocating and freeing memory has a cost, and that can add up quickly. Your primary line of optimization in most of these languages is "avoid the GC", which really boils down to "don't allocate more than you need to", which is sound advice in every language, scripting or otherwise.
- TazeTSchnitzel 14y ago
  I'm certain you could have a language that is easy to program in, but doesn't use so much copying or use dictionaries so much. I'm not sure such a thing exists, though.
  - wmf 14y ago
    There's a whole continuum of stuff between Python/Ruby/JS and C, like Go, OCaml, and Rust. There's still a lot of refinement that could be done, though.
- bcoates 14y ago
  If the deck is to be believed, it's not the garbage collector or the heap that's causing the performance loss, it's that APIs and algorithms they enable are allocation-heavy compared to other "faster" languages. Heap allocations are expensive even in non-GC languages.
  - mzs 14y ago
    The first example is lookup based on name, you can get away from that in python with slots but the common consensus is that it's not worth the performance improvement. That somehow translates into a dogma like, "Never use slots," but sometimes it is worth it.
meunier 14y ago
Someone actually posting notes with slides! It's a miracle!
- NateDad 14y ago
  yes thank god. I almost skipped it when I saw it was a slide deck, until I saw the notes. I hate it when people link to a slide deck with no notes. It's almost completely useless.
bithive123 14y ago
If you want to learn more about what the Ruby VM has to do in order to execute your code, and some of the performance challenges for Ruby implementors (such as it's extremely flexible parameter parsing) I suggest this talk by Koichi Sasada: http://www.youtube.com/watch?v=lWIP4nsKIMU http://www.youtube.com/watch?v=lWIP4nsKIMU
- chadcf 14y ago
  I really wish this talk had been done by someone who spoke english, I found it rather painful to try and get through... Any good articles that summarize this info?
  - StavrosK 14y ago
    I find this attitude a bit entitled. The speaker does speak English, his accent is just not very understandable. However, opening the video and seeking to a random point, I must say that the phrase "Ruby release policy: Ruby level compatibility" isn't doing any Japanese speaker a favour.
    - jholman 14y ago
      You find his attitude entitled, I find your reply needlessly confrontational. It's not like chadcf said "This talk is bullshit, that guy doesn't even speak English". chadcf said "I experienced this difficulty, I wish that the following thing existed, can anyone help me?" Maybe he could afford to have done s/speak English/speak more fluent English/
njharman 14y ago
Meh, MEH. I'm almost never waiting on my python code. I'm waiting on network or disk or database or joe to check in his changes or etc. I'm sure there are people who do wait. But that's why numpy, c extensions, all the pypy, psycho, and similar things exist. Python and more broadly "scripting" languages are for speed of development. Something else can take on speed of execution faster than 90% of people need it to be.
- tptacek 14y ago
  It's not an unresolved question whether idiomatic Python is slower than idiomatic C/C++ for solving comparable problems. Python is much, much slower than C.
  - ynniv 14y ago
    Meh, when there's an io call or a network request in front of the computation you'll never know. EDIT: removed an additional comment about scientific computing that is now relevant as someone replied to it.
    - tptacek 14y ago
      Does that mean we can't discuss what makes languages or their implementations performant without having a detailed conversation about the relevance of performance?
      - ynniv 14y ago
        No, I'm in complete agreement with the OP, but you said Python is slower than idiomatic C/C++ for solving comparable problems And when io and especially network is involved, that is not true. Your efficient C code can't make up for time lost elsewhere in the system. No one is clamoring for curl to be rewritten in assembly.
        tptacek 14y ago
        True, but obvious.
cschmidt 14y ago
A nice talk. The punchline for me was: Things that take time •Hash table lookups •Allocations •Copying Interestingly, that's exactly how you write fast C++ code. His point is that languages like Python lack good API's for preallocating memory.
- kyllo 14y ago
  It's how you write fast algorithms in general, in any programming language. Minimize the number of reads and writes per iteration/recursion. In higher-level programming languages, it's just a bit harder to control the number of reads and writes because you're working at several layers of abstraction above them, and are concerned with solving higher-level problems. Use the language that provides the appropriate level of abstraction for the problem you're trying to solve.
  - PeterisP 14y ago
    On the other hand, why should the abstraction layers prevent that? I mean, abstraction layers abstract away the [hopefully] unimportant low-level choices from me - but "copy or not copy" or "allocate once or allocate thrice" isn't a choice that I need to make anyway; the abstraction layer simply should make the 'non-copy' choice for me. Exactly the same way that the C abstraction layer right now makes the proper opcode-ordering choices for me as good (or better) than I can do manually in assembler. The problem is that we haven't yet implemented those abstraction layers in this smart way - for example, Haskell can implement 'fusion' of multiple string operations so that they are merged together and executed without intermediate copies; and the abstraction layer for that is exactly as high-level as the Python examples in original poster's slides. Sure, it's objectively hard to change core Python like that - but it theoretically can be done, so it should&will be done.
    - metaphorm 14y ago
      its not always possible to go with the "non-copy" choice. for example, there are very good reasons for having immutable strings, and once you've made that choice at the language level every string function you write is going to copy at least once. I think Alex Gaynor is correct and that basically what is wrong at the moment is that dynamic languages lack API's that have any sensitivity to performance concerns. There's always going to be a hard limit based on the nature of using a JIT vs. a static multi-pass compiler. There's always going to be a hard limit based on fundamental language choices (implementations of primitives, mutable vs. immutable strings, amount of overhead in object instantation, etc.) But we're nowhere near those limits right now.
riobard 14y ago
Completely agree. APIs are so important for many optimizations to pull off. I'd really like to use a lot more buffer()/memoryview() objects in Python. Unfortunately many APIs (e.g. sockets) won't work well with them (at least in Python 2.x. Not sure about 3.x). So we ended up with tons of unnecessary allocation and copying all over the place. So sad.
rasmusfabbe 14y ago
This is misleading and contains errors like calling C++ "C". Unless you have a great deal of knowledge about these things already, I urge you not to learn from this but read the slides purely for entertainment. Question: The author claims to be a compiler author. After some digging I haven't found any information on what compilers he has written or are part of writing. Could someone point me to the compiler(s) Alex is involved with? Thanks.
- aroberge 14y ago
  Look up PyPy.
- tptacek 14y ago
  I've been a C/C++ programmer since ~1993 and apart from wondering why he had to "look up" a C hash table (there's one in K&R) I saw nothing to complain about.
- cschmidt 14y ago
  He mentioned it directly in the talk: PyPy. Or are you being snarky and saying he doesn't know what he's talking about because PyPy isn't a "real" compiler. Alex has made huge contributions to several open source projects. I can't imagine too many people who know more about making Python go fast.
- jeffdavis 14y ago
  "This is misleading and contains errors like calling C++ "C"." In what ways did that detract from his overall point?
- cgh 14y ago
  He's on this page: http://pypy.org/people.html http://pypy.org/people.html He works on the JIT, among other things.
- emidln 14y ago
  Your reading comprehension is extremely poor here. His notes mention that he wanted to use a pure C version but couldn't find a C version by a quick google search. It did not say "here is a pure C version".
ippa 14y ago
His suggestion for better preallocate APIs made me think of this ruby patch from Charles Nutter: http://www.ruby-forum.com/topic/173802 http://www.ruby-forum.com/topic/173802 4 years later and they still discuss it, heh.
dicroce 14y ago
As a C/C++ programmer I find these slides kind of amusing... These languages are popular because they make things simpler, and his suggestions may very well get a nicely jit'd language on par with C, but I suspect you'll then have the same problems C does (complexity).
- graue 14y ago
  Depending on the application, speed may matter only for 5% (or less) of your code. If you can write that 5% in Ruby or Python, same as you wrote the other 95% in, you save a lot of difficulty compared to calling out to a C library — even if the optimized part of the code is a bit complex.
- mistercow 14y ago
  I don't think that added complexity invalidates the usefulness of high performance APIs in high level languages. The point would not be to write all of your code to be highly performant (that would be premature optimization), but to optimize the hot spots. Currently, if you want to really optimize a hot spot in, say, Python, your only real option is to write that part in C. Then you have all the additional complexity of gluing that into your Python program, along with portability concerns and a more complex build process. It would be so much easier if there were a way to sacrifice local simplicity and idiom for performance while still staying in the language. And in the case of JS, I'm not sure you have much in the way of options at all for optimizing hot spots to reduce allocations. Maybe you could write it in C and compile it to JS via emscripten? I don't know if that would even help currently, but maybe if asm.js takes off. But once again, wouldn't you rather sacrifice a small amount of elegance for performance rather than switching languages?
- Symmetry 14y ago
  There's a lot to be said for writing everything out in a simple manner for the first pass, then profiling and adding complexity to the places where there's a big benefit from it. And if something goes wrong what you get is bad performance, not a segfault.
Nate75Sanders 14y ago
He mentions that he couldn't find a pure C hash table. http://linux.die.net/man/3/hcreate http://linux.die.net/man/3/hcreate
- SourPatch 14y ago
  Back in the early 2000s it seemed like a lot people were using kazlib: http://www.kylheku.com/~kaz/kazlib.html http://www.kylheku.com/~kaz/kazlib.html
- pjmlp 14y ago
  Not portable.
edanm 14y ago
Very interesting talk Leads me to wonder - has anyone done a study of any large-scale program to check where the slow spots are? It's not that I don't trust the speaker, he makes excellent points and is obviously a great memeber of the community. But it would be very interesting if he were able to say: "Using PyPy's secret 'hint' API, only in drop-dead obvious places, improved performance by a factor of 5".
defen 14y ago
Back when I wanted to investigate the numeric performance of v8 I wrote a Runge-Kutta integrator + Lorenz attractor in C and in JavaScript as a simple-but-not-entirely-trivial benchmark. I was actually pretty impressed with how fast the v8 version was. On the downside, it's fairly non-idiomatic js and not that much nicer to look at than the C. Doing a million steps on my machine takes 0.65 seconds in node.js v0.8.4, 0.41 seconds in C compiled with gcc -O0, and 0.13 seconds with gcc -O3. Here is the code if anyone is interested. Note that it's not commented, not thread-safe, and doesn't free memory, so use at your own risk :) https://gist.github.com/anonymous/5066486 https://gist.github.com/anonymous/5066486 gcc strange.c rk4.c; ./a.out node strange.js
- masklinn 14y ago
  > Back when I wanted to investigate the numeric performance of v8 Straightforward numerical computations really isn't a good jit benchmark, because numerical computations are by far the easiest thing to JIT, and JITted perfs are going to be much closer to AOT than in the general case (unless the problem can be vectorized an the AOT compiler is vectorizing, I don't think JITs can usually vectorize)
  - defen 14y ago
    Yup...I wanted to try to quickly measure just how good the JIT was for that kind of stuff, to see if we were getting to the point where it's feasible to do physics in the browser. Turns out it's "fast enough", and yet still 5x slower than equivalent stock C.
CJefferson 14y ago
One main thought on this topic -- languages like Haskell and lisp also have very poor support for direct memory control, but tend to be viewed (perhaps untruthfully?) as much closer in performance to C than Python/Ruby.
- tikhonj 14y ago
  No, Haskell really does have significantly better performance than Python or Ruby. Same with some Lisp variants as well--there was even a research whole-program optimizing compiler for Scheme that apparently sometimes beat hand-optimized C (Stalin Scheme). So one way to improve performance is simply by having a good compiler. And GHC, at least, is a very good compiler. Also, Haskell support for direct memory control is not that bad. In fact, in some ways, it's better than even Java--you can have your own unboxed data types which essentially act like structs, for example. This also means that you can have unboxed arrays of more than just primitive types. Haskell also does some very clever things with both the heap and the stack, but I'm not familiar enough with its internals to comment. My understanding is that Haskell makes heap allocation much cheaper and has a GC optimized for handling lots of small allocations (as you would expect for a functional language). Ultimately, the point is that the question is fairly nuanced and you won't be able to pin down a single language or implementation feature that uniquely determines performance.
- andolanra 14y ago
  Haskell and languages in the ML family have a lot of opportunities for elaborate static analysis, which often allows the resulting programs to be quite clever about optimizing the resulting programs. As one example, the GHC Haskell compiler uses loop fusion to combine multiple passes over a list into a single pass with no intermediate copies of the list produced. Consequently, Haskell code like map f (map g (map h someList)) is going to involve allocating exactly one list of the same size as someList, while a direct translation into Python map(f, map(g, map(h, someList))) is going to involve the creation of several intermediate lists.
  - koenigdavidmj 14y ago
    In the Haskell case you could also do something like this to avoid needing that optimisation: map (f . g . h) someList And in Python 3, map returns an iterator, not a list, so you aren't building the full list until you ask for it, and you never build intermediate lists in your example. You can do the same thing in Python 2 with the itertools.imap function.
pcwalton 14y ago
Related to this is the importance of deforestation. Some good links: * http://en.wikipedia.org/wiki/Deforestation_%28computer_science%29 http://en.wikipedia.org/wiki/Deforestation_%28computer_scien... * http://www.haskell.org/haskellwiki/Short_cut_fusion http://www.haskell.org/haskellwiki/Short_cut_fusion Deforestation is basically eliminating intermediate data structures, which is similar to what the "int(s.split("-", 1)[1])" versus "atoi(strchr(s, '-') + 1)" slides are about. If you consider strings as just lists of characters, then it's basically a deforestation problem: the goal is to eliminate all the intermediate lists of lists that are constructed. (It's something of a peculiar case though, because in order to transform into the C code you need to not only observe that indexing an rvalue via [1] and throwing the rest away means that the list doesn't have to be constructed at all, but you also need to allow strings to share underlying buffer space—the latter optimization isn't deforestation per se.) I don't know if there's been much effort into deforestation optimizations for dynamic languages, but perhaps this is an area that compilers and research should be focusing on more. On another minor note, I do think that the deck is a little too quick to dismiss garbage collection as an irrelevant problem. For most server apps I'm totally willing to believe that GC doesn't matter, but for interactive apps on the client (think touch-sensitive mobile apps and games) where you have to render each frame in under 16 ms, unpredictable latency starts to matter a lot.
- cwzwarich 14y ago
  Automatic deforestation can remove intermediate results in a pipeline of computation, but it can not rewrite a program that is based around the querying / updating of a fixed data structure to use an efficient imperative equivalent throughout.
- lucian1900 14y ago
  Deforestation is easily done in lazy languages like Haskell. As for GC, it would be nice to have good real time GCs in runtimes.
  - klodolph 14y ago
    > As for GC, it would be nice to have good real time GCs in runtimes. After decades of GC research, I think the conclusion is, "Yeah, that would be nice." Current state of the art gives us some very nice GCs that penalize either throughput or predictability. One of my favorite stories about GC is here: http://samsaffron.com/archive/2011/10/28/in-managed-code-we-trust-our-recent-battles-with-the-net-garbage-collector http://samsaffron.com/archive/2011/10/28/in-managed-code-we-...
jderick 14y ago
I think the preallocate APIs sound like a cool idea. Perhaps there could also be some kind of 'my hashtable is an object' hint that could let the compiler do the same kind of optimizations on hashtables that it does on objects (assuming that your hash keys don't change much).
wting 14y ago
I have a few comments about some of the slides, feel free to correct any misunderstandings. Dictionary vs Object: Lookups in both data structures is O(1), the difference being the hashing cost (and an additional memory lookup for heap) vs a single memory lookup on the stack (1 line of assembly). Squares list: > ... so every iteration through the list we have the potential need to size the list and copy all the data. This is no different than stl::vector which has an amortized cost of O(1) for a push_back(). It's not going to be as fast as C, but I'd also argue for a generator version instead: def squares(n): return (i*i for i in xrange(n)) One of the main reasons people choose Python is for expressiveness and not manually managing memory, although pre-allocation does seem like a good idea.
- kragen 14y ago
  You mean std::vector, from the STL. And yes, the amortized cost is O(1) per element and thus O(N) in total, but the constant factor and lower-order terms (the O(1) time to do the allocation and garbage-collect it later) do matter.
kingkilr 14y ago
Author/speaker here: I don't have time to read all the comments now (thanks for all the interest though!). I just want to say I think when the video comes out it'll answer a lot of questions people are having.
- jholman 14y ago
  I'm looking forward to the video. I'm also interested in proof of the "lame myths" claims, or links to debunkings of those myths, etc. And also if you have rants about those If There's Time topics in your last slide, I'd like to read those too. Thanks!
mixmastamyk 14y ago
Question: def squares(n): sq = [] for i in xrange(n): sq.append(i*i) return sq A basically idiomatic version of the same in Python. No list pre-allocation, so every iteration through the list we have the potential to need to resize the list and copy all the data. That's inefficient. Is that true? I'd expect .append() to change a pointer or two, not "resize and copy" the list. Even an .insert() should just move pointers at the C-level... no need to "defrag" it. I guess the key word is potential.
- chimeracoder 14y ago
  I believe you're correct - Python lists should be O(1) for appending[0]. [0] http://wiki.python.org/moin/TimeComplexity http://wiki.python.org/moin/TimeComplexity
  - jholman 14y ago
    I think you're both right and wrong. mixmastamyk's comment implies that (s)he believes that Python lists are, under the hood, linked lists. This is wrong. Python lists are ultimately backed by C arrays. This is why get() and set() are O(1), and insert() is O(n). However, dynamically resizing an array to support append operations, if you're not stupid, takes amortized constant time. Individual operations may be O(n). Python implementers, happily, are not stupid. However, insert() operations do require "defragmenting". So, the primary question mixmastamyk asked about the cost of def squares(n): sq = [] for i in xrange(n): sq.append(i*i) return sq is totally correct, but a lot of the sub-reasoning is wrong.
    - mixmastamyk 14y ago
      Yes, I've always just assumed that internally a resizable Python list was a linked-list I learned about in C... fits perfectly. I suppose using an array must improve performance in typical cases, while the resizing (a linked-list advantage) happens less often.
      - 14y ago
moreati 14y ago
Great presentation, thank you for making me aware of an aspect of Python performance. One slide struck me as odd - the "basically pythonic" squares() function. I understand it's a chosen example to illustrate a point, I just hope people aren't writing loops like that. You inspired me to measure it $ cat squares.py def squares_append(n): sq = [] for i in xrange(n): sq.append(i*i) return sq def squares_comprehension(n): return [i*i for i in xrange(n)] $ PYTHONPATH=. python -m timeit -s "from squares import squares_append" "squares_append(1000)" 10000 loops, best of 3: 148 usec per loop $ PYTHONPATH=. python -m timeit -s "from squares import squares_comprehension" "squares_comprehension(1000)" 10000 loops, best of 3: 74.1 usec per loop $ PYTHONPATH=. pypy -m timeit -s "from squares import squares_append" "squares_append(1000)" 10000 loops, best of 3: 46.9 usec per loop $ PYTHONPATH=. pypy -m timeit -s "from squares import squares_comprehension" "squares_comprehension(1000)" 100000 loops, best of 3: 8.67 usec per loop I'm curious to know how many allocations/copies a list comprehension saves in CPython/PyPy. However I wouldn't begin to know how to measure it.
- ericmoritz 14y ago
  If you really want power, use NumPy: from numpy import arange def squares_numpy(n): a = arange(n) return a * a $ python -m timeit -s "from squares import squares_append" "squares_append(1000)" 10000 loops, best of 3: 130 usec per loop $ python -m timeit -s "from squares import squares_comprehension" "squares_comprehension(1000)" 10000 loops, best of 3: 95.4 usec per loop $ python -m timeit -s "from squares import squares_numpy" "squares_numpy(1000)" 100000 loops, best of 3: 5.31 usec per loop
DannyBee 14y ago
Speaking as a compiler guy, and having a hand in a few successful commercial JITs: The only reason he thinks they aren't slow is because they haven't yet reached the limits of making the JIT faster vs the program faster. Yes, it's true that the languages are not slow in the sense of being able to take care of most situations through better optimization strategies. As a compiler author, one can do things like profile types/trace/whatever, and deoptimize if you get it wrong. You can do a lot. You can recognize idioms, use different representations behind people's back, etc. But all those things take time that is not spent running your program. On average, you can do pretty well. But it's still overhead. As you get farther along in your JIT, optimization algorithms get trickier and trickier, your heuristics, more complex. You will eventually hit the wall, and need to spend more time doing JIT'ing than doing real work to make optimizations to some code. This happens to every single JIT, of course. This is why they try to figure out which code to optimize. But even then, you may find there is too much of it. Because of this, the languages are slower, it's just the overhead of better JIT algorithms, not slower code. In practice, you hope that you can optimize enough code well enough that nobody cares, because the ruby code takes 8ms, and the C code takes 5ms. For example: Almost all of the allocations and copying can be optimized, but depending on the language, the algorithms to figure out what you can do safely may be N^3. Also, PyPy is still pretty young in its life cycle (in this iteration of PyPy:P) for folks to say that they can make stuff much faster if they only had a few things. It really needs a very large set of production apps being rin by a very large set of folks for quite a while to see where the real bottlenecks still are. Past a certain point, you run out of optimization algorithm bullets. The way compilers get the last 20% is by tuning the algorithms for 10 years. Of course, i'm not trying to slag on PyPy, I think they've done an amazing job of persevering through multiple rewrites to get somewhere that seems to be quite good now. I just am a little wary of a fairly young JIT saying that all big performance problems fall into a few categories.
- jewel 14y ago
  To counter the overhead of the JIT algorithm, would it be possible to do that work in a background thread or cache the JIT optimizations to disk?
  - 14y ago
Zak 14y ago
The creators of Common Lisp knew what Alex is talking about. Lisp is, of course just as dynamic as Ruby, Python or Javascript, but it exposes lower-level details about data structures and memory allocation iff the programmer wants them. Features that come to mind include preallocated vectors (fixed-size or growable), non-consing versions of the standard list functions and the ability to bang on most any piece of data in place. There are fairly few situations in which a CL program can't come within a factor of 2 or 3 of the performance of C.
- pjmlp 14y ago
  In the early 80's there was a time Lisp compilers could even beat FORTRAN for floating point computations. http://www.cs.berkeley.edu/~fateman/papers/lispfloat.pdf http://www.cs.berkeley.edu/~fateman/papers/lispfloat.pdf
  - cliffbean 14y ago
    From the discussion of their most relevant benchmark (Singular value decomposition): The Allegro CL 4.1 times of 3.9 seconds beat the f77 time of 4.8 [seconds]; Nice! setting on optimization for f77 brought its time down to 0.45 seconds. Thus for this system, the [LISP] compiled code can have quite comparable speed to that of the corresponding unoptimized Fortran in this case as well. Oh really.
    - pjmlp 14y ago
      It's been a few decades since I have read the paper, so it seems my memory is a bit fuzzy on that regard. On the other hand, given that C always had issues to beat even unoptimized Fortran, due to the optimization restrictions before C99, it is quite commendable that Lisp achieves such results.
      - cliffbean 14y ago
        It's not obvious how optimized C in the '80s wouldn't have been as fast as unoptimized Fortran 77, even with whatever optimization restriction you might be thinking of. The way the authors of that paper talk about unoptimized code in that paper gives the impression that they don't know what they're talking about. Your comments here begin to put you at risk of a similar appearance.
d0mine 14y ago
atoi(strchr(s, '-') + 1) What does this do? Finds the first instance of a -, and converts the remainder of a string to an int. 0 allocations, 0 copies. Doing this with 0 copies is pretty much impossible in Python, and probably in ruby and Javascript too. </quote> The copying could be avoided in non-idiomatic Python: int(buffer(s, s.find("-") + 1))
- ricardobeat 14y ago
  +s.substr(s.indexOf('-') + 1)
csense 14y ago
The example he gives for strings could be optimized to near the efficiency of the C version by a sufficiently smart compiler: int(s.split("-", 1)[1]) If the JIT knows that s is the builtin string type and the split() method has not been overridden [1], it can speed this up by using "pseudo-strings," where a pseudo-string is an index and length into another string. This would require only O(1) time and space. Garbage-collecting pseudo-strings would be an interesting exercise, but I'm sure it's a solvable problem [2] [3]. [1] If the preconditions for your optimization don't hold, you can always fall back to interpreting it. As noted by the speaker, this sort of logic is already a critical part of many JIT's including Pypy. [2] The problem is actually GC'ing the parent. When the parent string is gc'ed, you have to compact the orphan strings to reclaim the remaining space; otherwise it'll be possible to write user code that uses a small finite amount of memory in CPython but has an unbounded memory leak in your compiler. [3] You can avoid the trickiness in [2] if the parent string can be proven to outlive its children, which is the case in this example. You could probably optimize a lot of real-world code, and have an easier time implementing the compiler, if you only used pseudo-strings when they could be proven to be shorter-lived than the parent. As a bonus, this partial GC would build some infrastructure that could be recycled in a general implementation.
gingerlime 14y ago
Interesting slides, and good point about having better APIs. Perhaps I'm nitpicking, but with a function called `newlist_hint`, I struggle to see how anybody would adopt it. I had to go back to the slides maybe 3 times, and I still don't remember the name of this function... Those APIs must have the most obvious, logical and simple names.
rjzzleep 14y ago
i'm actually surprised noone ever talks about perl. isn't perl crazy fast compared to the other interpreted languages?
- metaphorm 14y ago
  no. Perl is mildly faster, not crazy faster. same order of magnitude.
revelation 14y ago
Looking at CPython and the bytecode it uses, it's not very hard to see why it would be slow. It's basically designed as a reference implementation, with only very tame optimizations.
estavaro 14y ago
My own piece of feedback based on my experience. The slides were good. But like others, JIT is not all rosy. In V8 and Dart and .NET, code gets compiled to native code as soon as possible. I think that's the best case scenario in general. You then don't have to guess as much. The author didn't mention method dispatching. I think it's an issue for many languages. In Dart, they tried to optimize it by the specification by mostly eliminating the need to change methods at runtime. In Ruby I watched a video by one of the core Ruby developers and he said that in Ruby method dispatching can be very complicated requiring up to 20 steps to resolve them. As important as getting the best performance out of programs is to get the programs created in the first place. That's why I'm against shying away from larger codebases. I'm in favor of OO programming exactly because I think getting things done comes first, even if that could complicate the implementation of the toolset. And OO is all about layers of abstractions that bring more performance costs with them. That said, I absolutely abhor type annotations. They make code hideous and decrease the opportunities for experimentations. Instead of reading a + b = c algorithms, you may need to parse A a + B b = C c source code. In Dart we have Optional Types. But the core developers are fond of type annotations, so most samples they post come with them. I take relief in being able to omit type annotations while experimenting, researching and ultimately prototyping. Although in a way I feel like a rebel in the community for this disregard. Thankfully there is this chance to share a community with them. Reading the part that you don't like adding heuristics to help programs to go faster reminded of adding types to them even if they are mostly disregarded as in Dart. Then again, not all "dynamic languages" are the same. Some are truly dynamic with eval and runtime method changes. Others, not so much. Sometimes the tradeoffs allow for other kinds of gains that could come into play like when deploying. So there is a lot more to it than just getting the algorithms correct.
kristianp 14y ago
As a ruby lover, I'm interested in the ruby implementation the Author wrote and mentioned, topaz [1]. Has anyone here tried it? "Topaz is a high performance implementation of the Ruby programming language, written in Python on top of RPython (the toolchain that powers PyPy)." [1] http://docs.topazruby.com/en/latest/ http://docs.topazruby.com/en/latest/
coldtea 14y ago
Speak about Python and Ruby. Javascript is insanely fast, with V8 and its ilk. And I'm not talking about "toy benchmarks" either, I'm talking about envolved stuff written in plain JS (no C extensions), from the QT port to JS/Canvas, to the h264 encoder and such. Try doing those on Python and you'll see what you get. And of course all the toy benchmarks also agree. Javascript with v8 is like a faster PyPy (with less performance deviation): 10 to 20 times faster than plain Python code. Sure, you can extend Python with fast C code. But as the core languages are concerned, JS beats CPython hands down. (Oh, and you can also extend JS with fast C/C++ code if you need that. Node modules do it all the time).
- deleted 14y ago
  [deleted]
irahul 14y ago
Mike Pall of luajit fame has an interesting take on it. http://www.reddit.com/r/programming/comments/19gv4c/why_python_ruby_and_js_are_slow/c8nyejd http://www.reddit.com/r/programming/comments/19gv4c/why_pyth... <quote> While I agree with the first part ("excuses"), the "hard" things mentioned in the second part are a) not that hard and b) solved issues (just not in PyPy). Hash tables: Both v8 and LuaJIT manage to specialize hash table lookups and bring them to similar performance as C structs (1). Interestingly, with very different approaches. So there's little reason NOT to use objects, dictionaries, tables, maps or whatever it's called in your favorite language. (1) If you really, really care about the last 10% or direct interoperability with C, LuaJIT offers native C structs via its FFI. And PyPy has inherited the FFI design, so they should be able to get the same performance someday. I'm sure v8 has something to offer for that, too. Allocations: LuaJIT has allocation sinking, which is able to eliminate the mentioned temporary allocations. Incidentally, the link shows how that's done for a x,y,z point class! And it works the same for ALL cases: arrays {1,2,3} (on top of a generic table), hash tables {x=1,y=2,z=3} or FFI C structs. String handling: Same as above -- a buffer is just a temporary allocation and can be sunk, too. Provided the stores (copies) are eliminated first. The extracted parts can be forwarded to the integer conversion from the original string. Then all copies and references are dead and the allocation itself can be eliminated. LuaJIT will get all of that string handling extravaganza with the v2.1 branch -- parts of the new buffer handling are already in the git repo. I'm sure the v8 guys have something up their sleeves, too. I/O read buffer: Same reasoning. The read creates a temporary buffer which is lazily interned to a string, ditto for the lstrip. The interning is sunk, the copies are sunk, the buffer is sunk (the innermost buffer is reused). This turns it into something very similar to the C code. Pre-sizing aggregates: The size info can be backpropagated to the aggreagate creation from scalar evolution analysis. SCEV is already in LuaJIT (for ABC elimination). I ditched the experimental backprop algorithm for 2.0, since I had to get the release out. Will be resurrected in 2.1. Missing APIs: All of the above examples show you don't really need to define new APIs to get the desired performance. Yes, there's a case for when you need low-level data structures -- and that's why higher-level languages should have a good FFI. I don't think you need to burden the language itself with these issues. Heuristics: Well, that's what those compiler textbooks don't tell you: VMs and compilers are 90% heuristics. Better deal with it rather than fight it. tl;dr: The reason why X is slow, is because X's implementation is slow, unoptimized or untuned. Language design just influences how hard it is to make up for it. There are no excuses. </quote> Also interesting is his research on allocation sinking: http://wiki.luajit.org/Allocation-Sinking-Optimization http://wiki.luajit.org/Allocation-Sinking-Optimization
jdhuang 14y ago
Interesting presentation, but it can't be the whole story. Even projects like SciPy which use the most rudimentary data structures (basically just a large array of floats) and algorithms (sometimes just looping through the elements in order a few times) see a considerable advantage when rewritten in C. http://www.scipy.org/PerformancePython http://www.scipy.org/PerformancePython
oscargrouch 14y ago
Its time to face it: People start to create computer languages without carrying too much about the target processor opcodes (because in that time processor were just getting faster with time) and focus more on programmer convenience, and wild beasts like python and ruby were born.. C is fast because it was created with processor awareness in mind.. pretty simple... these days kids are all about trying to create more and more crappy convenient sintax languages.. and they get worry when the languages dont scale? for what computer they design the language? from venus ? nobody should be doing any serious software in python or ruby.. is such a waste of talent .. use it for education.. for fun.. or for the things they are best.. wich is not in the system/plumbing side of things
- dmg8 14y ago
  Please don't ever comment again. Thanks in advance.
lsiebert 14y ago
As a programmer that first learned c and still thinks like a C programmer in a lot of ways, this actually explains a lot to me.

367 points by jasonostrander 14y ago

It is almost time that people stop referring to Languages as Fast or Slow. It is an implementation that is fast or slow, not a language.

masklinn 14y ago
Have you considered reading the fucking presentation before snarking out on it?
- arocks 14y ago
  What makes you think I didn't? The author seems to agree with me. He even concludes that we should improve the implementation rather than the language for optimisation.
  - ynniv 14y ago
    No, the author concludes that languages based on hash table lookups and lacking copy avoidance mechanisms are inherently slower.
  - masklinn 14y ago
    Which makes your comment useless and redundant. The very point of the presentation pretty much being "this declaration makes no sense"
  - tptacek 14y ago
    I didn't get that from the presentation at all. What I read is a guy complaining that idiomatic Python is necessarily slow because it depends, for its clarity and terseness, on not controlling allocations or memory layout, and that Python- the- language abets the problem by having its standard library build on the same idiom.
systematical 14y ago
I think its time people stop using shitty slide decks to get their point across.
- rscott 14y ago
  He gave a talk yesterday at Waza, Heroku's conference. I believe Heroku is planning on uploading videos of the talks in the coming days. I've been interested in this talk since I saw it announced on Twitter, but prefer to watch/listen rather than go through these slides.
- aroberge 14y ago
  Didn't it occur to you that these slides were for a presentation and that sharing them enable more people than just those that were at the presentation be informed of their content? I, for one, am very grateful to speakers that make the extra effort required to share with a larger group what they have already shared (or are about to share) with a smaller group.
  - alxp 14y ago
    Much better to turn your notes from the talk into an article than to just throw up the slides.
    - koide 14y ago
      But much harder. Slides (with notes!) are a VERY good compromise. Remember: the author does not owe you anything.
cpressey 14y ago
This is one of my pet peeves, too.
rwj 14y ago
While I agree that implementations can be fast or slow, it does not completely eliminate the effect of the language. At minimum, different languages require different levels of effort to reach their optimum. So, while a language can be hurt by a poor implementation, it does not follow that all languages have the same potential performance. As an example, just consider the enormous amount of effort that has gone into the JVM, and Java is still generally considered to be ~2x slower that C.
simonster 14y ago
It's true that implementation makes a bigger difference to performance than language features, but language features can indeed affect speed. One clear example is that a language that checks for integer overflow will be slower than a language that doesn't. There are a lot of situations where there's no way you could optimize out the extra instructions you'd need to check for overflow. Some language features are easy to optimize away for some common cases (e.g. array bounds checks, so that your program throws an exception instead of segfaulting), but you can't optimize these if, for example, you're iterating over data you read from a file using indices you also read from that file.

wheaties 14y ago

Great bit of slides. Straight and to the point. If you've ever ventured under the hood of Python you'd see this in the code. If you've ever had to optimize the bejeesus out of code in C++ or C, you'd know exactly the kinds of things he's talking about.

cheald 14y ago

Kind of a poorly-named deck. It's really about why programs use features of these languages that end up causing poor performance relative to C, rather than why the individual VMs themselves are slow. It's no surprise that trading the byte-precision of C for the convenience of a garbage collector and heap-allocated data structures results in a performance decrease. Dynamically-typed languages are often easier to program in, but require more copying (and memory allocation) as a result. Hash tables are heap-allocated and have to be garbage collected, but they're flexible - something you don't get with structs. Allocating and freeing memory has a cost, and that can add up quickly. Your primary line of optimization in most of these languages is "avoid the GC", which really boils down to "don't allocate more than you need to", which is sound advice in every language, scripting or otherwise.

TazeTSchnitzel 14y ago
I'm certain you could have a language that is easy to program in, but doesn't use so much copying or use dictionaries so much. I'm not sure such a thing exists, though.
- wmf 14y ago
  There's a whole continuum of stuff between Python/Ruby/JS and C, like Go, OCaml, and Rust. There's still a lot of refinement that could be done, though.
bcoates 14y ago
If the deck is to be believed, it's not the garbage collector or the heap that's causing the performance loss, it's that APIs and algorithms they enable are allocation-heavy compared to other "faster" languages. Heap allocations are expensive even in non-GC languages.
- mzs 14y ago
  The first example is lookup based on name, you can get away from that in python with slots but the common consensus is that it's not worth the performance improvement. That somehow translates into a dogma like, "Never use slots," but sometimes it is worth it.

meunier 14y ago

Someone actually posting notes with slides! It's a miracle!

NateDad 14y ago
yes thank god. I almost skipped it when I saw it was a slide deck, until I saw the notes. I hate it when people link to a slide deck with no notes. It's almost completely useless.

bithive123 14y ago

If you want to learn more about what the Ruby VM has to do in order to execute your code, and some of the performance challenges for Ruby implementors (such as it's extremely flexible parameter parsing) I suggest this talk by Koichi Sasada: http://www.youtube.com/watch?v=lWIP4nsKIMU http://www.youtube.com/watch?v=lWIP4nsKIMU

chadcf 14y ago
I really wish this talk had been done by someone who spoke english, I found it rather painful to try and get through... Any good articles that summarize this info?
- StavrosK 14y ago
  I find this attitude a bit entitled. The speaker does speak English, his accent is just not very understandable. However, opening the video and seeking to a random point, I must say that the phrase "Ruby release policy: Ruby level compatibility" isn't doing any Japanese speaker a favour.
  - jholman 14y ago
    You find his attitude entitled, I find your reply needlessly confrontational. It's not like chadcf said "This talk is bullshit, that guy doesn't even speak English". chadcf said "I experienced this difficulty, I wish that the following thing existed, can anyone help me?" Maybe he could afford to have done s/speak English/speak more fluent English/

njharman 14y ago

Meh, MEH. I'm almost never waiting on my python code. I'm waiting on network or disk or database or joe to check in his changes or etc. I'm sure there are people who do wait. But that's why numpy, c extensions, all the pypy, psycho, and similar things exist. Python and more broadly "scripting" languages are for speed of development. Something else can take on speed of execution faster than 90% of people need it to be.

tptacek 14y ago
It's not an unresolved question whether idiomatic Python is slower than idiomatic C/C++ for solving comparable problems. Python is much, much slower than C.
- ynniv 14y ago
  Meh, when there's an io call or a network request in front of the computation you'll never know. EDIT: removed an additional comment about scientific computing that is now relevant as someone replied to it.
  - tptacek 14y ago
    Does that mean we can't discuss what makes languages or their implementations performant without having a detailed conversation about the relevance of performance?
    - ynniv 14y ago
      No, I'm in complete agreement with the OP, but you said Python is slower than idiomatic C/C++ for solving comparable problems And when io and especially network is involved, that is not true. Your efficient C code can't make up for time lost elsewhere in the system. No one is clamoring for curl to be rewritten in assembly.
      - tptacek 14y ago
        True, but obvious.

cschmidt 14y ago

A nice talk. The punchline for me was: Things that take time •Hash table lookups •Allocations •Copying Interestingly, that's exactly how you write fast C++ code. His point is that languages like Python lack good API's for preallocating memory.

kyllo 14y ago
It's how you write fast algorithms in general, in any programming language. Minimize the number of reads and writes per iteration/recursion. In higher-level programming languages, it's just a bit harder to control the number of reads and writes because you're working at several layers of abstraction above them, and are concerned with solving higher-level problems. Use the language that provides the appropriate level of abstraction for the problem you're trying to solve.
- PeterisP 14y ago
  On the other hand, why should the abstraction layers prevent that? I mean, abstraction layers abstract away the [hopefully] unimportant low-level choices from me - but "copy or not copy" or "allocate once or allocate thrice" isn't a choice that I need to make anyway; the abstraction layer simply should make the 'non-copy' choice for me. Exactly the same way that the C abstraction layer right now makes the proper opcode-ordering choices for me as good (or better) than I can do manually in assembler. The problem is that we haven't yet implemented those abstraction layers in this smart way - for example, Haskell can implement 'fusion' of multiple string operations so that they are merged together and executed without intermediate copies; and the abstraction layer for that is exactly as high-level as the Python examples in original poster's slides. Sure, it's objectively hard to change core Python like that - but it theoretically can be done, so it should&will be done.
  - metaphorm 14y ago
    its not always possible to go with the "non-copy" choice. for example, there are very good reasons for having immutable strings, and once you've made that choice at the language level every string function you write is going to copy at least once. I think Alex Gaynor is correct and that basically what is wrong at the moment is that dynamic languages lack API's that have any sensitivity to performance concerns. There's always going to be a hard limit based on the nature of using a JIT vs. a static multi-pass compiler. There's always going to be a hard limit based on fundamental language choices (implementations of primitives, mutable vs. immutable strings, amount of overhead in object instantation, etc.) But we're nowhere near those limits right now.

riobard 14y ago

Completely agree. APIs are so important for many optimizations to pull off. I'd really like to use a lot more buffer()/memoryview() objects in Python. Unfortunately many APIs (e.g. sockets) won't work well with them (at least in Python 2.x. Not sure about 3.x). So we ended up with tons of unnecessary allocation and copying all over the place. So sad.

rasmusfabbe 14y ago

This is misleading and contains errors like calling C++ "C". Unless you have a great deal of knowledge about these things already, I urge you not to learn from this but read the slides purely for entertainment. Question: The author claims to be a compiler author. After some digging I haven't found any information on what compilers he has written or are part of writing. Could someone point me to the compiler(s) Alex is involved with? Thanks.

aroberge 14y ago
Look up PyPy.
tptacek 14y ago
I've been a C/C++ programmer since ~1993 and apart from wondering why he had to "look up" a C hash table (there's one in K&R) I saw nothing to complain about.
cschmidt 14y ago
He mentioned it directly in the talk: PyPy. Or are you being snarky and saying he doesn't know what he's talking about because PyPy isn't a "real" compiler. Alex has made huge contributions to several open source projects. I can't imagine too many people who know more about making Python go fast.
jeffdavis 14y ago
"This is misleading and contains errors like calling C++ "C"." In what ways did that detract from his overall point?
cgh 14y ago
He's on this page: http://pypy.org/people.html http://pypy.org/people.html He works on the JIT, among other things.
emidln 14y ago
Your reading comprehension is extremely poor here. His notes mention that he wanted to use a pure C version but couldn't find a C version by a quick google search. It did not say "here is a pure C version".

ippa 14y ago

His suggestion for better preallocate APIs made me think of this ruby patch from Charles Nutter: http://www.ruby-forum.com/topic/173802 http://www.ruby-forum.com/topic/173802 4 years later and they still discuss it, heh.

dicroce 14y ago

As a C/C++ programmer I find these slides kind of amusing... These languages are popular because they make things simpler, and his suggestions may very well get a nicely jit'd language on par with C, but I suspect you'll then have the same problems C does (complexity).

graue 14y ago
Depending on the application, speed may matter only for 5% (or less) of your code. If you can write that 5% in Ruby or Python, same as you wrote the other 95% in, you save a lot of difficulty compared to calling out to a C library — even if the optimized part of the code is a bit complex.
mistercow 14y ago
I don't think that added complexity invalidates the usefulness of high performance APIs in high level languages. The point would not be to write all of your code to be highly performant (that would be premature optimization), but to optimize the hot spots. Currently, if you want to really optimize a hot spot in, say, Python, your only real option is to write that part in C. Then you have all the additional complexity of gluing that into your Python program, along with portability concerns and a more complex build process. It would be so much easier if there were a way to sacrifice local simplicity and idiom for performance while still staying in the language. And in the case of JS, I'm not sure you have much in the way of options at all for optimizing hot spots to reduce allocations. Maybe you could write it in C and compile it to JS via emscripten? I don't know if that would even help currently, but maybe if asm.js takes off. But once again, wouldn't you rather sacrifice a small amount of elegance for performance rather than switching languages?
Symmetry 14y ago
There's a lot to be said for writing everything out in a simple manner for the first pass, then profiling and adding complexity to the places where there's a big benefit from it. And if something goes wrong what you get is bad performance, not a segfault.

Nate75Sanders 14y ago

He mentions that he couldn't find a pure C hash table. http://linux.die.net/man/3/hcreate http://linux.die.net/man/3/hcreate

SourPatch 14y ago
Back in the early 2000s it seemed like a lot people were using kazlib: http://www.kylheku.com/~kaz/kazlib.html http://www.kylheku.com/~kaz/kazlib.html
pjmlp 14y ago
Not portable.

edanm 14y ago

Very interesting talk Leads me to wonder - has anyone done a study of any large-scale program to check where the slow spots are? It's not that I don't trust the speaker, he makes excellent points and is obviously a great memeber of the community. But it would be very interesting if he were able to say: "Using PyPy's secret 'hint' API, only in drop-dead obvious places, improved performance by a factor of 5".

defen 14y ago

Back when I wanted to investigate the numeric performance of v8 I wrote a Runge-Kutta integrator + Lorenz attractor in C and in JavaScript as a simple-but-not-entirely-trivial benchmark. I was actually pretty impressed with how fast the v8 version was. On the downside, it's fairly non-idiomatic js and not that much nicer to look at than the C. Doing a million steps on my machine takes 0.65 seconds in node.js v0.8.4, 0.41 seconds in C compiled with gcc -O0, and 0.13 seconds with gcc -O3. Here is the code if anyone is interested. Note that it's not commented, not thread-safe, and doesn't free memory, so use at your own risk :) https://gist.github.com/anonymous/5066486 https://gist.github.com/anonymous/5066486 gcc strange.c rk4.c; ./a.out node strange.js

masklinn 14y ago
> Back when I wanted to investigate the numeric performance of v8 Straightforward numerical computations really isn't a good jit benchmark, because numerical computations are by far the easiest thing to JIT, and JITted perfs are going to be much closer to AOT than in the general case (unless the problem can be vectorized an the AOT compiler is vectorizing, I don't think JITs can usually vectorize)
- defen 14y ago
  Yup...I wanted to try to quickly measure just how good the JIT was for that kind of stuff, to see if we were getting to the point where it's feasible to do physics in the browser. Turns out it's "fast enough", and yet still 5x slower than equivalent stock C.

CJefferson 14y ago

One main thought on this topic -- languages like Haskell and lisp also have very poor support for direct memory control, but tend to be viewed (perhaps untruthfully?) as much closer in performance to C than Python/Ruby.

tikhonj 14y ago
No, Haskell really does have significantly better performance than Python or Ruby. Same with some Lisp variants as well--there was even a research whole-program optimizing compiler for Scheme that apparently sometimes beat hand-optimized C (Stalin Scheme). So one way to improve performance is simply by having a good compiler. And GHC, at least, is a very good compiler. Also, Haskell support for direct memory control is not that bad. In fact, in some ways, it's better than even Java--you can have your own unboxed data types which essentially act like structs, for example. This also means that you can have unboxed arrays of more than just primitive types. Haskell also does some very clever things with both the heap and the stack, but I'm not familiar enough with its internals to comment. My understanding is that Haskell makes heap allocation much cheaper and has a GC optimized for handling lots of small allocations (as you would expect for a functional language). Ultimately, the point is that the question is fairly nuanced and you won't be able to pin down a single language or implementation feature that uniquely determines performance.
andolanra 14y ago
Haskell and languages in the ML family have a lot of opportunities for elaborate static analysis, which often allows the resulting programs to be quite clever about optimizing the resulting programs. As one example, the GHC Haskell compiler uses loop fusion to combine multiple passes over a list into a single pass with no intermediate copies of the list produced. Consequently, Haskell code like map f (map g (map h someList)) is going to involve allocating exactly one list of the same size as someList, while a direct translation into Python map(f, map(g, map(h, someList))) is going to involve the creation of several intermediate lists.
- koenigdavidmj 14y ago
  In the Haskell case you could also do something like this to avoid needing that optimisation: map (f . g . h) someList And in Python 3, map returns an iterator, not a list, so you aren't building the full list until you ask for it, and you never build intermediate lists in your example. You can do the same thing in Python 2 with the itertools.imap function.

pcwalton 14y ago

Related to this is the importance of deforestation. Some good links: * http://en.wikipedia.org/wiki/Deforestation_%28computer_science%29 http://en.wikipedia.org/wiki/Deforestation_%28computer_scien... * http://www.haskell.org/haskellwiki/Short_cut_fusion http://www.haskell.org/haskellwiki/Short_cut_fusion Deforestation is basically eliminating intermediate data structures, which is similar to what the "int(s.split("-", 1)[1])" versus "atoi(strchr(s, '-') + 1)" slides are about. If you consider strings as just lists of characters, then it's basically a deforestation problem: the goal is to eliminate all the intermediate lists of lists that are constructed. (It's something of a peculiar case though, because in order to transform into the C code you need to not only observe that indexing an rvalue via [1] and throwing the rest away means that the list doesn't have to be constructed at all, but you also need to allow strings to share underlying buffer space—the latter optimization isn't deforestation per se.) I don't know if there's been much effort into deforestation optimizations for dynamic languages, but perhaps this is an area that compilers and research should be focusing on more. On another minor note, I do think that the deck is a little too quick to dismiss garbage collection as an irrelevant problem. For most server apps I'm totally willing to believe that GC doesn't matter, but for interactive apps on the client (think touch-sensitive mobile apps and games) where you have to render each frame in under 16 ms, unpredictable latency starts to matter a lot.

cwzwarich 14y ago
Automatic deforestation can remove intermediate results in a pipeline of computation, but it can not rewrite a program that is based around the querying / updating of a fixed data structure to use an efficient imperative equivalent throughout.
lucian1900 14y ago
Deforestation is easily done in lazy languages like Haskell. As for GC, it would be nice to have good real time GCs in runtimes.
- klodolph 14y ago
  > As for GC, it would be nice to have good real time GCs in runtimes. After decades of GC research, I think the conclusion is, "Yeah, that would be nice." Current state of the art gives us some very nice GCs that penalize either throughput or predictability. One of my favorite stories about GC is here: http://samsaffron.com/archive/2011/10/28/in-managed-code-we-trust-our-recent-battles-with-the-net-garbage-collector http://samsaffron.com/archive/2011/10/28/in-managed-code-we-...

jderick 14y ago

I think the preallocate APIs sound like a cool idea. Perhaps there could also be some kind of 'my hashtable is an object' hint that could let the compiler do the same kind of optimizations on hashtables that it does on objects (assuming that your hash keys don't change much).

wting 14y ago

I have a few comments about some of the slides, feel free to correct any misunderstandings. Dictionary vs Object: Lookups in both data structures is O(1), the difference being the hashing cost (and an additional memory lookup for heap) vs a single memory lookup on the stack (1 line of assembly). Squares list: > ... so every iteration through the list we have the potential need to size the list and copy all the data. This is no different than stl::vector which has an amortized cost of O(1) for a push_back(). It's not going to be as fast as C, but I'd also argue for a generator version instead: def squares(n): return (i*i for i in xrange(n)) One of the main reasons people choose Python is for expressiveness and not manually managing memory, although pre-allocation does seem like a good idea.

kragen 14y ago
You mean std::vector, from the STL. And yes, the amortized cost is O(1) per element and thus O(N) in total, but the constant factor and lower-order terms (the O(1) time to do the allocation and garbage-collect it later) do matter.

kingkilr 14y ago

Author/speaker here: I don't have time to read all the comments now (thanks for all the interest though!). I just want to say I think when the video comes out it'll answer a lot of questions people are having.

jholman 14y ago
I'm looking forward to the video. I'm also interested in proof of the "lame myths" claims, or links to debunkings of those myths, etc. And also if you have rants about those If There's Time topics in your last slide, I'd like to read those too. Thanks!

mixmastamyk 14y ago

Question: def squares(n): sq = [] for i in xrange(n): sq.append(i*i) return sq A basically idiomatic version of the same in Python. No list pre-allocation, so every iteration through the list we have the potential to need to resize the list and copy all the data. That's inefficient. Is that true? I'd expect .append() to change a pointer or two, not "resize and copy" the list. Even an .insert() should just move pointers at the C-level... no need to "defrag" it. I guess the key word is potential.

chimeracoder 14y ago
I believe you're correct - Python lists should be O(1) for appending[0]. [0] http://wiki.python.org/moin/TimeComplexity http://wiki.python.org/moin/TimeComplexity
- jholman 14y ago
  I think you're both right and wrong. mixmastamyk's comment implies that (s)he believes that Python lists are, under the hood, linked lists. This is wrong. Python lists are ultimately backed by C arrays. This is why get() and set() are O(1), and insert() is O(n). However, dynamically resizing an array to support append operations, if you're not stupid, takes amortized constant time. Individual operations may be O(n). Python implementers, happily, are not stupid. However, insert() operations do require "defragmenting". So, the primary question mixmastamyk asked about the cost of def squares(n): sq = [] for i in xrange(n): sq.append(i*i) return sq is totally correct, but a lot of the sub-reasoning is wrong.
  - mixmastamyk 14y ago
    Yes, I've always just assumed that internally a resizable Python list was a linked-list I learned about in C... fits perfectly. I suppose using an array must improve performance in typical cases, while the resizing (a linked-list advantage) happens less often.
    - 14y ago

moreati 14y ago

Great presentation, thank you for making me aware of an aspect of Python performance. One slide struck me as odd - the "basically pythonic" squares() function. I understand it's a chosen example to illustrate a point, I just hope people aren't writing loops like that. You inspired me to measure it $ cat squares.py def squares_append(n): sq = [] for i in xrange(n): sq.append(i*i) return sq def squares_comprehension(n): return [i*i for i in xrange(n)] $ PYTHONPATH=. python -m timeit -s "from squares import squares_append" "squares_append(1000)" 10000 loops, best of 3: 148 usec per loop $ PYTHONPATH=. python -m timeit -s "from squares import squares_comprehension" "squares_comprehension(1000)" 10000 loops, best of 3: 74.1 usec per loop $ PYTHONPATH=. pypy -m timeit -s "from squares import squares_append" "squares_append(1000)" 10000 loops, best of 3: 46.9 usec per loop $ PYTHONPATH=. pypy -m timeit -s "from squares import squares_comprehension" "squares_comprehension(1000)" 100000 loops, best of 3: 8.67 usec per loop I'm curious to know how many allocations/copies a list comprehension saves in CPython/PyPy. However I wouldn't begin to know how to measure it.

ericmoritz 14y ago
If you really want power, use NumPy: from numpy import arange def squares_numpy(n): a = arange(n) return a * a $ python -m timeit -s "from squares import squares_append" "squares_append(1000)" 10000 loops, best of 3: 130 usec per loop $ python -m timeit -s "from squares import squares_comprehension" "squares_comprehension(1000)" 10000 loops, best of 3: 95.4 usec per loop $ python -m timeit -s "from squares import squares_numpy" "squares_numpy(1000)" 100000 loops, best of 3: 5.31 usec per loop

DannyBee 14y ago

Speaking as a compiler guy, and having a hand in a few successful commercial JITs: The only reason he thinks they aren't slow is because they haven't yet reached the limits of making the JIT faster vs the program faster. Yes, it's true that the languages are not slow in the sense of being able to take care of most situations through better optimization strategies. As a compiler author, one can do things like profile types/trace/whatever, and deoptimize if you get it wrong. You can do a lot. You can recognize idioms, use different representations behind people's back, etc. But all those things take time that is not spent running your program. On average, you can do pretty well. But it's still overhead. As you get farther along in your JIT, optimization algorithms get trickier and trickier, your heuristics, more complex. You will eventually hit the wall, and need to spend more time doing JIT'ing than doing real work to make optimizations to some code. This happens to every single JIT, of course. This is why they try to figure out which code to optimize. But even then, you may find there is too much of it. Because of this, the languages are slower, it's just the overhead of better JIT algorithms, not slower code. In practice, you hope that you can optimize enough code well enough that nobody cares, because the ruby code takes 8ms, and the C code takes 5ms. For example: Almost all of the allocations and copying can be optimized, but depending on the language, the algorithms to figure out what you can do safely may be N^3. Also, PyPy is still pretty young in its life cycle (in this iteration of PyPy:P) for folks to say that they can make stuff much faster if they only had a few things. It really needs a very large set of production apps being rin by a very large set of folks for quite a while to see where the real bottlenecks still are. Past a certain point, you run out of optimization algorithm bullets. The way compilers get the last 20% is by tuning the algorithms for 10 years. Of course, i'm not trying to slag on PyPy, I think they've done an amazing job of persevering through multiple rewrites to get somewhere that seems to be quite good now. I just am a little wary of a fairly young JIT saying that all big performance problems fall into a few categories.

jewel 14y ago
To counter the overhead of the JIT algorithm, would it be possible to do that work in a background thread or cache the JIT optimizations to disk?
- 14y ago

Zak 14y ago

The creators of Common Lisp knew what Alex is talking about. Lisp is, of course just as dynamic as Ruby, Python or Javascript, but it exposes lower-level details about data structures and memory allocation iff the programmer wants them. Features that come to mind include preallocated vectors (fixed-size or growable), non-consing versions of the standard list functions and the ability to bang on most any piece of data in place. There are fairly few situations in which a CL program can't come within a factor of 2 or 3 of the performance of C.

pjmlp 14y ago
In the early 80's there was a time Lisp compilers could even beat FORTRAN for floating point computations. http://www.cs.berkeley.edu/~fateman/papers/lispfloat.pdf http://www.cs.berkeley.edu/~fateman/papers/lispfloat.pdf
- cliffbean 14y ago
  From the discussion of their most relevant benchmark (Singular value decomposition): The Allegro CL 4.1 times of 3.9 seconds beat the f77 time of 4.8 [seconds]; Nice! setting on optimization for f77 brought its time down to 0.45 seconds. Thus for this system, the [LISP] compiled code can have quite comparable speed to that of the corresponding unoptimized Fortran in this case as well. Oh really.
  - pjmlp 14y ago
    It's been a few decades since I have read the paper, so it seems my memory is a bit fuzzy on that regard. On the other hand, given that C always had issues to beat even unoptimized Fortran, due to the optimization restrictions before C99, it is quite commendable that Lisp achieves such results.
    - cliffbean 14y ago
      It's not obvious how optimized C in the '80s wouldn't have been as fast as unoptimized Fortran 77, even with whatever optimization restriction you might be thinking of. The way the authors of that paper talk about unoptimized code in that paper gives the impression that they don't know what they're talking about. Your comments here begin to put you at risk of a similar appearance.

d0mine 14y ago

atoi(strchr(s, '-') + 1) What does this do? Finds the first instance of a -, and converts the remainder of a string to an int. 0 allocations, 0 copies. Doing this with 0 copies is pretty much impossible in Python, and probably in ruby and Javascript too. </quote> The copying could be avoided in non-idiomatic Python: int(buffer(s, s.find("-") + 1))

ricardobeat 14y ago
+s.substr(s.indexOf('-') + 1)

csense 14y ago

The example he gives for strings could be optimized to near the efficiency of the C version by a sufficiently smart compiler: int(s.split("-", 1)[1]) If the JIT knows that s is the builtin string type and the split() method has not been overridden [1], it can speed this up by using "pseudo-strings," where a pseudo-string is an index and length into another string. This would require only O(1) time and space. Garbage-collecting pseudo-strings would be an interesting exercise, but I'm sure it's a solvable problem [2] [3]. [1] If the preconditions for your optimization don't hold, you can always fall back to interpreting it. As noted by the speaker, this sort of logic is already a critical part of many JIT's including Pypy. [2] The problem is actually GC'ing the parent. When the parent string is gc'ed, you have to compact the orphan strings to reclaim the remaining space; otherwise it'll be possible to write user code that uses a small finite amount of memory in CPython but has an unbounded memory leak in your compiler. [3] You can avoid the trickiness in [2] if the parent string can be proven to outlive its children, which is the case in this example. You could probably optimize a lot of real-world code, and have an easier time implementing the compiler, if you only used pseudo-strings when they could be proven to be shorter-lived than the parent. As a bonus, this partial GC would build some infrastructure that could be recycled in a general implementation.

gingerlime 14y ago

Interesting slides, and good point about having better APIs. Perhaps I'm nitpicking, but with a function called `newlist_hint`, I struggle to see how anybody would adopt it. I had to go back to the slides maybe 3 times, and I still don't remember the name of this function... Those APIs must have the most obvious, logical and simple names.

rjzzleep 14y ago

i'm actually surprised noone ever talks about perl. isn't perl crazy fast compared to the other interpreted languages?

metaphorm 14y ago
no. Perl is mildly faster, not crazy faster. same order of magnitude.

revelation 14y ago

Looking at CPython and the bytecode it uses, it's not very hard to see why it would be slow. It's basically designed as a reference implementation, with only very tame optimizations.

estavaro 14y ago

My own piece of feedback based on my experience. The slides were good. But like others, JIT is not all rosy. In V8 and Dart and .NET, code gets compiled to native code as soon as possible. I think that's the best case scenario in general. You then don't have to guess as much. The author didn't mention method dispatching. I think it's an issue for many languages. In Dart, they tried to optimize it by the specification by mostly eliminating the need to change methods at runtime. In Ruby I watched a video by one of the core Ruby developers and he said that in Ruby method dispatching can be very complicated requiring up to 20 steps to resolve them. As important as getting the best performance out of programs is to get the programs created in the first place. That's why I'm against shying away from larger codebases. I'm in favor of OO programming exactly because I think getting things done comes first, even if that could complicate the implementation of the toolset. And OO is all about layers of abstractions that bring more performance costs with them. That said, I absolutely abhor type annotations. They make code hideous and decrease the opportunities for experimentations. Instead of reading a + b = c algorithms, you may need to parse A a + B b = C c source code. In Dart we have Optional Types. But the core developers are fond of type annotations, so most samples they post come with them. I take relief in being able to omit type annotations while experimenting, researching and ultimately prototyping. Although in a way I feel like a rebel in the community for this disregard. Thankfully there is this chance to share a community with them. Reading the part that you don't like adding heuristics to help programs to go faster reminded of adding types to them even if they are mostly disregarded as in Dart. Then again, not all "dynamic languages" are the same. Some are truly dynamic with eval and runtime method changes. Others, not so much. Sometimes the tradeoffs allow for other kinds of gains that could come into play like when deploying. So there is a lot more to it than just getting the algorithms correct.

kristianp 14y ago

As a ruby lover, I'm interested in the ruby implementation the Author wrote and mentioned, topaz [1]. Has anyone here tried it? "Topaz is a high performance implementation of the Ruby programming language, written in Python on top of RPython (the toolchain that powers PyPy)." [1] http://docs.topazruby.com/en/latest/ http://docs.topazruby.com/en/latest/

coldtea 14y ago

Speak about Python and Ruby. Javascript is insanely fast, with V8 and its ilk. And I'm not talking about "toy benchmarks" either, I'm talking about envolved stuff written in plain JS (no C extensions), from the QT port to JS/Canvas, to the h264 encoder and such. Try doing those on Python and you'll see what you get. And of course all the toy benchmarks also agree. Javascript with v8 is like a faster PyPy (with less performance deviation): 10 to 20 times faster than plain Python code. Sure, you can extend Python with fast C code. But as the core languages are concerned, JS beats CPython hands down. (Oh, and you can also extend JS with fast C/C++ code if you need that. Node modules do it all the time).

deleted 14y ago
[deleted]

irahul 14y ago

Mike Pall of luajit fame has an interesting take on it. http://www.reddit.com/r/programming/comments/19gv4c/why_python_ruby_and_js_are_slow/c8nyejd http://www.reddit.com/r/programming/comments/19gv4c/why_pyth... <quote> While I agree with the first part ("excuses"), the "hard" things mentioned in the second part are a) not that hard and b) solved issues (just not in PyPy). Hash tables: Both v8 and LuaJIT manage to specialize hash table lookups and bring them to similar performance as C structs (1). Interestingly, with very different approaches. So there's little reason NOT to use objects, dictionaries, tables, maps or whatever it's called in your favorite language. (1) If you really, really care about the last 10% or direct interoperability with C, LuaJIT offers native C structs via its FFI. And PyPy has inherited the FFI design, so they should be able to get the same performance someday. I'm sure v8 has something to offer for that, too. Allocations: LuaJIT has allocation sinking, which is able to eliminate the mentioned temporary allocations. Incidentally, the link shows how that's done for a x,y,z point class! And it works the same for ALL cases: arrays {1,2,3} (on top of a generic table), hash tables {x=1,y=2,z=3} or FFI C structs. String handling: Same as above -- a buffer is just a temporary allocation and can be sunk, too. Provided the stores (copies) are eliminated first. The extracted parts can be forwarded to the integer conversion from the original string. Then all copies and references are dead and the allocation itself can be eliminated. LuaJIT will get all of that string handling extravaganza with the v2.1 branch -- parts of the new buffer handling are already in the git repo. I'm sure the v8 guys have something up their sleeves, too. I/O read buffer: Same reasoning. The read creates a temporary buffer which is lazily interned to a string, ditto for the lstrip. The interning is sunk, the copies are sunk, the buffer is sunk (the innermost buffer is reused). This turns it into something very similar to the C code. Pre-sizing aggregates: The size info can be backpropagated to the aggreagate creation from scalar evolution analysis. SCEV is already in LuaJIT (for ABC elimination). I ditched the experimental backprop algorithm for 2.0, since I had to get the release out. Will be resurrected in 2.1. Missing APIs: All of the above examples show you don't really need to define new APIs to get the desired performance. Yes, there's a case for when you need low-level data structures -- and that's why higher-level languages should have a good FFI. I don't think you need to burden the language itself with these issues. Heuristics: Well, that's what those compiler textbooks don't tell you: VMs and compilers are 90% heuristics. Better deal with it rather than fight it. tl;dr: The reason why X is slow, is because X's implementation is slow, unoptimized or untuned. Language design just influences how hard it is to make up for it. There are no excuses. </quote> Also interesting is his research on allocation sinking: http://wiki.luajit.org/Allocation-Sinking-Optimization http://wiki.luajit.org/Allocation-Sinking-Optimization

jdhuang 14y ago

Interesting presentation, but it can't be the whole story. Even projects like SciPy which use the most rudimentary data structures (basically just a large array of floats) and algorithms (sometimes just looping through the elements in order a few times) see a considerable advantage when rewritten in C. http://www.scipy.org/PerformancePython http://www.scipy.org/PerformancePython

oscargrouch 14y ago

Its time to face it: People start to create computer languages without carrying too much about the target processor opcodes (because in that time processor were just getting faster with time) and focus more on programmer convenience, and wild beasts like python and ruby were born.. C is fast because it was created with processor awareness in mind.. pretty simple... these days kids are all about trying to create more and more crappy convenient sintax languages.. and they get worry when the languages dont scale? for what computer they design the language? from venus ? nobody should be doing any serious software in python or ruby.. is such a waste of talent .. use it for education.. for fun.. or for the things they are best.. wich is not in the system/plumbing side of things

dmg8 14y ago
Please don't ever comment again. Thanks in advance.

lsiebert 14y ago

As a programmer that first learned c and still thinks like a C programmer in a lot of ways, this actually explains a lot to me.