Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Python, Ruby, and Javascript are Slow

speakerdeck.com

Post reply on HN
Print view View original

111–120 of 203 posts

Re: Why Python, Ruby, and Javascript are Slow

#111

Post by jholman »

mixmastamyk wrote: post #104
jholman wrote: post #97

Earlier quoted context omitted.

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).…

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.

Resizing is not a linked-list advantage, though. Resizing is an ammortized-constant-time operation.

The only advantage I'm aware of for linked lists is insert and delete (but not append and pop), which are constant time in a linked list but O(n) in an array.

The thing is, though, that doing insert() on a linked-list usually requires a seek first. Which is O(n) on a linked-list (and may be O(n), O(logn), or O(1) on an array, depending on what you mean by "seek"). So in _practice_, usually inserts and deletes are O(n) in a linked-list as well. (But not always, because you could already have a pointer to the relevant thing, for example if you have multiple different pointed-based data structures with pointers into each other.)

Basically, as far as I can tell, linked-lists are almost useless, unless you're forced to write all your data structures from scratch and you have too little time to write yourself a proper library. The main exception is for really hairy shit where you have multiple linked-list views traversing the same data in different orders.

Re: Why Python, Ruby, and Javascript are Slow

#112

Post by sb »

DannyBee wrote: post #93

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…

Interesting point of view, the problem in compiler construction is well known ("Proebsting's law", though it says it's more like 18 years instead of 10.)

The issue with benchmarks is surely well known, also by the PyPy authors; I wonder what the biggest application is that they have benchmarked or that runs on PyPy.

Your point on the JIT compiler interrupting program execution is certainly valid, too, but not necessarily so. One could easily do the code generation in a separate background thread and let execution switch over only if necessary. But, as you have already said, a latency issue certainly exists. This is one of the cases where interpreters usually have a leg up, and there are promising ways of optimizing interpreters.

Re: Why Python, Ruby, and Javascript are Slow

#113

Post by alxp »

aroberge wrote: post #17
systematical wrote: post #6

Earlier quoted context omitted.

I think its time people stop using shitty slide decks to get their point across.

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.

Much better to turn your notes from the talk into an article than to just throw up the slides.

Re: Why Python, Ruby, and Javascript are Slow

#114

Post by csense »

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.

Re: Why Python, Ruby, and Javascript are Slow

#115

Post by DannyBee »

sb wrote: post #112
DannyBee wrote: post #93

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…

Interesting point of view, the problem in compiler construction is well known ("Proebsting's law", though it says it's more like 18 years instead of 10.) The issue with benchmarks is surely well known, also by the PyPy authors; I wonder what the biggest application is that they have benchmarked or that runs on PyPy. Your point on the JIT compiler interrupting program execution is certainly valid, too, but not necessa…

Yes, you could do a background thread, with some caveats:

1. On most current CPU's, this will cause really bad cache/memory thrashing, enough to probably impact the program.

2. This may actually cause significant slowdown, depending on how long it takes to optimize a given set of code (IE it may be better to spend 100ms paused optimizing than 5000ms in the background). This is, of course, a latency issue.

3. State of the art for most JIT's is still to use one thread. The number of folks doing actual parallel code generation is nil. So sadly, even if you had 4 cores, 3 empty, you'll still, at best, get to use one of them for the background thread doing the optimizing. There are parts that are trivial to parallelize if you've structured the JIT "right", but they aren't always the parts that are slow.

Re: Why Python, Ruby, and Javascript are Slow

#116

Post by DannyBee »

jewel wrote: post #110
DannyBee wrote: post #93

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…

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?

See above. It varies. In some cases, it may be worse to do this than to stop the program. It's not as simple as "always work in the background until ready" .

Re: Why Python, Ruby, and Javascript are Slow

#117

Post by tikhonj »

andolanra wrote: post #80
CJefferson wrote: post #57

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.

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 so…

Most of the Haskell optimizations are aimed at making high-level code faster, not absolute speed. Something like loop fusion is trivial to do by hand, so it doesn't confer any advantage on hand-optimized Haskell programs. And when you're comparing to C, you're in the realm of performance where hand-optimizing code at the expense of simplicity, maintainability or even correctness is necessary. Otherwise you wouldn't have considered C.

So high-level optimizations like loop fusion do matter, but only for the 95% of the code which is not entirely performance critical. It's great for letting you write pretty (and therefore easier to write and more maintainable) code but not great for squeezing out all the possible performance in an inner loop.

Considering that many GHC optimizations are of this nature, it's really impressive that GHC is still good at speed in an absolute sense as well. So if you desperately need to wring out an extra bit of performance, you can still do it in Haskell instead of having to use C. Sure, the highly optimized Haskell will be relatively ugly, but it's still better than C and much easier to integrate with the rest of your codebase.

Re: Why Python, Ruby, and Javascript are Slow

#118

Post by gingerlime »

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.

Re: Why Python, Ruby, and Javascript are Slow

#119

Post by pcwalton »

DannyBee wrote: post #115
sb wrote: post #112

Earlier quoted context omitted.

Interesting point of view, the problem in compiler construction is well known ("Proebsting's law", though it says it's more like 18 years instead of 10.) The issue with benchmarks is surely well known, also by the PyPy authors; I wonder what the biggest application is that they have benchmarked or that runs on PyPy. Your point on the JIT compiler interrupting program execution is certainly valid, too, but not necessa…

Yes, you could do a background thread, with some caveats: 1. On most current CPU's, this will cause really bad cache/memory thrashing, enough to probably impact the program. 2. This may actually cause significant slowdown, depending on how long it takes to optimize a given set of code (IE it may be better to spend 100ms paused optimizing than 5000ms in the background). This is, of course, a latency issue. 3. State of…

Background compilation in a separate thread actually works pretty well. IE9 has been shipping it with Chakra for a while, and Firefox is now getting it (and it improved the benchmarks a lot, especially on ARM).

Re: Why Python, Ruby, and Javascript are Slow

#120

Post by sb »

DannyBee wrote: post #115
sb wrote: post #112

Earlier quoted context omitted.

Interesting point of view, the problem in compiler construction is well known ("Proebsting's law", though it says it's more like 18 years instead of 10.) The issue with benchmarks is surely well known, also by the PyPy authors; I wonder what the biggest application is that they have benchmarked or that runs on PyPy. Your point on the JIT compiler interrupting program execution is certainly valid, too, but not necessa…

Yes, you could do a background thread, with some caveats: 1. On most current CPU's, this will cause really bad cache/memory thrashing, enough to probably impact the program. 2. This may actually cause significant slowdown, depending on how long it takes to optimize a given set of code (IE it may be better to spend 100ms paused optimizing than 5000ms in the background). This is, of course, a latency issue. 3. State of…

ad 1) Hm, this seems to be a good point, but what's with the following line of thinking: some thread A interprets a program P, while another thread B compiles P to native machine code (P'). Now, if another thread C would start executing P' (taking the data/snapshot from A), then C's caches should build up and remain accurate. Of course, if this happens too often, then the caching behavior will be shitty. I always wondered (based on my interest in interpretation), how much I-cache misses the instruction cache flushes after inline-caching in native machine code cause. (If you have some data on that, please let me know.)

ad 3) I am well aware of that. However, I remember that at PLDI'11 there was a talk from Univ. of Edinburgh chaps doing parallel trace-based dynamic binary translation. Obviously, DBT is less work than a high level, full-blown JIT, but at least it's not nil :)

Post reply on HN