Ask HN: Is C/C++ really faster than Python? | Hacker News Reader

Ask HN: Is C/C++ really faster than Python?

36 pointssunilkumarc110 comments

I have seen many people saying they choose C/C++ over Python during programming challenges because the performance of Python is lesser compared to C/C++. How correct is this fact?

If Python is actually slower compared to C/C++, how much slower is it when we implement the same algorithm in C/C++?

Is it really necessary to use only C/C++ and not Python when solving some questions which involve a lot of computation?

View on HN

Yes. It's much faster. The reason C++ is fast is because you have explicit control over allocations and it compiles to native code (among other reasons). There are also a lot of subtle things that you can control in C++ that you can't in python, like memory layout. Memory layout is extremely important for CPU cache, and CPU cache is extremely important for performance. (Reading data from RAM is generally orders of a magnitude slower than reading from an L1 or L2 cache. For some reason this never gets mentioned in university CS courses, but there are a lot of data structures that are "theoretically" fast for certain things but in practice very unfriendly to hardware. For instance, linked lists. Sure insert/delete is O(1), but since linked lists are quite possibly the least cache friendly data structures in existence, you're better off with a vector/array even if you're inserting all the time. I'm not just making this up, you can read talks by people like Bjarne Stroustroup on this topic)

As to whether it matters for the algorithm, it depends on the algorithm. It's almost always going to be much faster in C, but, how fast do you really need it to be? Python is very good at saving programmer time, so if performance is not particularly important, I just wouldn't worry about it.

Mike Acton gave a great presentation on this kind of optimization at CppCon2014: https://www.youtube.com/watch?v=rX0ItVEVjHc

While this is true, and linked lists are somewhere between exotic and obsolete, the presentation by Bjarne Stroustroup had buried in it him saying 'the time to find the element takes so long a vector is always faster'. But, of course if you include a search linked lists are going to be way slower.

Also I wouldn't say that the same algorithm would be faster in C, there is no reason why C++ can't be as fast as C, even idiomatic modern C++.

Exotic? Obsolete? Really? Linked lists are used in pretty much all functional programming languages (because head/tail splitting is extremely useful)

Exotic at least for performance. Not only do you have to chase pointers to loop through them, you have to deal with the heap on every append or delete. They can be great for software that doesn't have speed as a high priority.

I'd be interested to know how you arrived at this conclusion, like what domain do you spend all your time in where this is true? I frequently see linked lists used for all manner of things, in some widely deployed performant code:

https://github.com/mackyle/sqlite/search?q=linked+list

https://github.com/freebsd/freebsd/search?l=c&q=linked+list

Stroustrup gave a talk where he demonstrated that the performance of a linked list is terrible compared to a vector. Here[0] is a summary.

[0] http://bulldozer00.com/2012/02/09/vectors-and-lists/

I'm not debating that iterating over a vector is faster than iterating over a linked list, I'm asking where this guy has seen linked lists become "exotic". I'd love to dive into that code, because I've actually spent a lot of time implementing parallel arrays vs linked lists or arrays of structs, it would be nice to see how folks have addressed the pain points like sorting in constant space...

What do you mean by sorting in constant space?

I mean sorting parallel arrays with a compile time constant amount of memory for sorting scratch space, this of course also means no unbound recursion into the stack. The most obvious solution is an additional index array, but that seems pretty wasteful. This is one area, in my experience, where linked lists beat out vectors, multidimensional sorting. Consider all that data that needs to get moved around in a parallel arrays implementation, vs simply changing the * prev and * next pointers in a linked list.

Sure, but I think you need to consider how fast moving blocks of memory can be on modern computers. memcpy feels intuitively slow, but because it's such a ubiquitous operation, it's really really fast. On the other hand, changing pointers sounds fast, until you consider that a pointer read might flush everything out of cache and result in the cpu stalling for hundreds of cycles while the RAM retrieves something.

I'm not suggesting like, never used linked lists or anything. I just think that most computer science is predicated on an abstract machine with predictable memory latency, and naturally people tend to design things with that in mind, while in reality, unless you're processing data sets so large that memory latency is insignificant, an O(1) operation might be way slower than an O(N) operation.

Well for a bunch of parallel arrays you aren't really moving big blocks. Consider this:

  struct City {
    char *name;
    int   popstrat[5];
    float bounds[2];
  };

A a memcpy on struct City would take care of eight distinct values, whereas a copy operation on a parallel arrays version would take at least three separate memcpy calls (maybe eight if naively implemented).

I certainly agree with you on the weight given to O notation though.

I've actually dug into this a tremendous amount, and sorting using an array of indices is the way to go. I tried a lot of different things and a lot of different memory layouts and I couldn't beat std::partition swapping a vector of ints.

There is no way a linked list will be the fastest way to do this on modern hardware. A big part of the reason it is so fast I think is because intel cpus are so good at prefetching, caching, and instruction reordering.

If you are talking about kd-trees specifically you might want to ask questions if you have any. I've done 4 full implementations, each one with more refinement.

I see more what you are saying below but I can't reply to it. First, you could have that a vector of that struct and memmove the elements on swap, which wouldn't be too bad performance-wise. In a struct of arrays set up it wouldn't perform as well since the swaps would be multiple cache-incoherent reads and writes (sort of as you said).

Sorting an array of ints will be very fast and likely the fastest way to do it. Then you can structure your data however you want and re-write it once you've sorted it.

Yeah I'm not very happy about needing to allocate an n sized array for sort operations, but it doesn't look like there is any way around it. To be clear, the struct is really just a opaque data type for what is essentially a dynamically defined struct of arrays. Most of the work has gone into compressing the array contents, as memory is the primary point of concern. I look forward to finishing it so that I can rewrite it a few more times :)

You can always sort portions of it and then merge those portions. In that case it might actually make sense to use packets on dense memory in a linked list. You could put the packet with the highest high value ahead of the other and merge middle out.

Yeah, I'd considered something like that to avoid large reallocs - I hadn't considered independent sort state for each chunk. That would allow for a single compile time constant sort index. Sounds like a good idea, thanks for that.

No problem, let me know how it turns out, it would be very satisfying to me if it ended up working well.

He's referring to spatial complexity of sorting algorithms. For example, mergesort can be implemented in parallel and in place (O(1) spatial) easily using linked lists.

Introsort and quicksort can be done in place using an array, but constant spatial complexity isn't always priority one. Some of the more recent algorithms aren't constant (timsort, spreadsort).

Linked lists (doubly linked lists) still have valid uses, but it's generally better to use an array (or vector) until you can justify otherwise.

Those are just search results for linked lists. It isn't as if sqlite using a linked list somewhere slows the entire thing down.

I can promise you that if there is a linked list in a performance crucial place that it could be sped up a non trivial amount.

Linked lists can be convenient and they can be consistent, but they aren't fast. The pointer chasing hurts performance. The extra heap allocations may or may not be able to be avoided. The alternative is something like a vector of pointers (although I would in practicality not being using a raw pointer, it would be some sort of larger data structure). That will be faster with the exception of resizes, which should be fast in general, since what they hold should be small, but they won't be consistent.

Beyond that there is the idea that concurrency could mean that needing to lock a data structure makes a linked list less of an outlier because the time that it would need to remain locked would be smaller. In that case I think a vector would likely still be much better in general, since you could keep the current index to write to in an atomic, which wouldn't require a lock.

The point of the search results is that I'm not seeing the use of linked lists, in code bases that I could consider fairly performant, at a level that I would describe as "exotic". I'm not trying to be argumentative, I'd really love for you to point me to a code base that has replaced linked lists with arrays. I've spent the last week writing a library to do just that, but I'd happily abandon it in a heartbeat if I could (the novelty of binary packing parallel arrays wore off after day two). You're preaching to the choir on deference overhead, that I why I prefer c over c++ :)

Linked lists aren't fast in general but there are workloads on which they outperform vectors -- which is why it is important to understand the advantages and disadvantages of each data structure.

Most lower-level memory allocators e.g. tend to use linked-lists afaik because you end up removing and inserting slabs a lot, the Linux kernel also makes wide use of linked lists as well. If there were substantial performance gains to be made without other large tradeoffs it would have been done.

EDIT: Some additional info: http://www.jikos.cz/jikos/Kmalloc_Internals.html

Context matters a lot. Linked lists are great for small lists, where you want very little memory overhead and you care more about each operation taking a pretty small, consistent amount of time.

Vectors/Arrays are great when you don't care as much about the total memory consumption, but you want to reduce the amount of heap fragmentation.

A downside to using arrays like this, and likely a leading reason you don't see them used that much in the linux kernel is that every once and a while an insert is going to force a realloc which takes a relatively long time. std::vector and the like mitigate this by reserving more space than they'll need and so they minimize the # of reallocs required.

There is also performance implications to doing std::vector<myStruct> vs std::vector<myStruct*>. The later can very easily mimic the same cache coherence issues that happen with a linked list of myStructs.

So when we are talking about speed in terms of millions of items in some data crunching program, vector is almost always going to win out. But if we are talking about minimal memory footprint where we want consistent timings , linked lists are a contender.

The only thing that I really agree with in that is that context matters :) My view on the matter is pretty simple, if you know how much data you are going to handle, before your first malloc, and the dimensionality is low, arrays win from the perspective of both processing speed and low memory usage. Otherwise (a lot of cases fall into otherwise) use linked lists - for your listing needs. BTW, a linked list of arrays is a pretty nice way of getting around the realloc problem. Sorting arrays across the linked list is not very nice though...

If it weren't for pointer overhead I'd just throw everything into a graph, but 64-bit addressing makes that expensive.

Well, I think you'd agree to that if random access is a requirement, arrays are nearly always going to work better.

Even then, that might be a good strategy if inserting into a vector type data structure required a realloc everytime. However, most implementations use an exponential strategy, so for a million item vector grown one at a time, you'd see only 10-20 reallocs. Which is to say, the realloc problem is only a problem in memory constrained -- think embedded or kernel -- systems where a memory overhead of 1.5-2x isn't viable.

You can do the same thing -- and some linked list implementations do -- with linked lists, where you grab a block of nodes at a time. If you don't though, just in inserts, the vector will be faster. Mallocs are non-trivial in most applications and can easily become the bottleneck.

I think the thing you might be underestimating is how much faster it is to iterate over a vector than a linked list, nevermind random access. Cache issues really, really do matter. If you want to see this in action and happen to have a SoC dev board around, disable the data cache and run some benchmarks with vectors. If you re-enable it, you will easily see a 10x-20x improvement.

If you watch https://www.youtube.com/watch?v=YQs6IC-vgmo, he goes into some of the use cases and some benchmarks that might be compelling to you.

> Which is to say, the realloc problem is only a problem in memory constrained -- think embedded or kernel...

Or userland, when your software is processing hundreds of millions of datapoints - each with several additional independent properties.

> I think the thing you might be underestimating is how much faster it is to iterate over a vector than a linked list...

No, I'm well aware of the effects of locality - the linked list of arrays is an easily tuned compromise between speed and memory consumption (leaning much more towards memory considerations).

The point I was trying to make though is that even with 100mil datapoints you are looking at probably less than 50 reallocs. In userland, the story is even nicer because that actual reserve space in the vector is mostly going to be deferred until you actually write to it.

I don't get the point about additional independent properties. Size of the struct changes the memory you need to grab, but not the number of reallocs you have to do.

See: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector... for actual benchmarks on this. If you disagree with these benchmarks, and find your own results to be different, I'd love to see the write up on that, and I'm sure I'm not the only one.

Yeah the disconnect seems to me to be that I'm talking about performance from the perspective of a presupposition that I haven't adequately explained.

You've got hundreds of millions of data points to slurp into ram, each data point may have additional properties from a fixed set, data points are independent of one another - so not a good fit for a graph, adjacency matrix, etc. Disk access outside of the initial slurp is a no go, so we have to make this fit in ram.

Throwing the data point into a struct is nice and easy, plus it eases the system call overhead for m/re/callocs. But you've got a bunch of wasted space in padding, locality is gone, compressibility is much more limited.

Throwing the data into a bunch of parallel arrays is about the most memory efficient way of doing it, especially considering the ease with which you can use delta encoding and bin packing. But now every memory/sort operation is magnified by the number of arrays you've got.

As far as a writeup, I'm working on a succinct atomic map for strings - I look forward to releasing the code once I finish... and rewrite it in such a way that my employer doesn't sue me (it isn't organic to the business, but better safe than sorry).

I'm afraid I don't quite get the data problem. Is there a toy example of the kind of data you are talking about?

Not entirely clear on how the indexing would work to your benefit with parallel arrays. If there is a 1 to 1 mapping between datapoints to items in each || array, the memory consumption is the same as a struct, so I assume thats not it.

It almost sounds like you are describing a (possibly non-numeric? non-homogenous?) sparse matrix, which are usually worked with in vastly different formats for construction vs manipulation vs iterating over.

> Is there a toy example of the kind of data you are talking about?

Not that I know of, sorry.

> Not entirely clear on how the indexing would work to your benefit with parallel arrays.

Lets say that we have data that would be represented in an array of structs like so:

  typedef struct
  {
      char* name;
      int   age;
  } prsnT1;
  prsnT1* peopleAOS = calloc(100, sizeof(*peopleAOS));

You could also represent it as a struct of arrays:

  typedef struct
  {
      char** name;
      int*   age;
  } prsnT2;
  prsnT2* peopleSOA = malloc(sizeof(*peopleSOA));
  peopleSOA->name   = calloc(100, sizeof(*peopleSOA->name));
  peopleSOA->age    = calloc(100, sizeof(*peopleSOA->age));

Now why would you want to use SOA over AOS (disregarding the AOS alignment padding overhead)? Locality and compression. When you want to search on age, you don't need to waste cache space stepping over name. Age can also be bin packed pretty tightly, so in reality it wouldn't be an int* - but a variably sized ADT. Ideally name wouldn't be char either, but another ADT. Transparent zlib compression isn't unheard of.

> ... which are usually worked with in vastly different formats for construction vs manipulation vs iterating over.

Yup, classic abstract data type - doing OO in C the hard way :)

I should preface this by saying I love functional programming, I think it's a great way to write stable and testable code, it's likely the future, but...

Functional programming is much more popular in academic circles than in industry. I think academics tend to hand wave away practical concerns like cache coherency as "an implementation detail" or as an "exercise for the reader." Big O times are often considered, but rarely do researchers make a career off of "how well does this fit into an X86 L3 cache"

So yes, functional programming tends to depend on linked lists, and that's probably why you don't see it in things like the game industry. This might change in the future, for instance, I could see it being the case where having provably immutable memory could allow processors to manage more memory efficiently, but I don't think you can have a fast language that considers the CPU as an abstract entity; you have to design these things in.

Erlang is used quite a bit in the gaming industry (backend stuff for online games) and depends quite strongly on the linked list concept.

He is obviously talking about engine programming. For tools and back ends game studios will use whatever.

C is absolutely not faster than C++. Generic types in C are typically done through type erasure or an intrusive type. C++ templates explictly allow different instances of code to be generated for each of the types. So, the code can be specialized for each type, which most of the time is faster. In general, template metaprogramming allows for drastically more complex optimization at compile time.

The biggest reason to write in C over C++ is simplicity and higher level of control over algorithms and data structures. Portability is another reason though.

Very much right, unless CPU icache limits start to bite. C++ templates can generate a lot of code.

For simple functions, templates are usually always a pure win. For example, C qsort is horrible. Function pointer to a otherwise so inlinable small sort function is always going to get beaten by C++ template based sort.

But if each iteration of loop needs to fetch 10 kB of instructions because of specialized separately compiled templated forms, suddenly pointers win again. It can also invalidate TLB, branch predictor, etc. caches.

But most cases templates are a win. Just remember microbenchmarking can really mislead here, if the program as whole has an icache bottleneck as a consequence.

Yeah, but nothing says you can't specialize your C code.

And C compilers can generate specializations if everything is in the same translation unit. What I was trying to point out is that less abstract doesn't imply better performance. It isn't C > C++ > Python. What the machine ultimately has to do is what matters.

I think programs written in dynamic languages are generally harder to optimize because they're more likely to take advantage of complex features. Since these languages often compile to C, you can obviously write the same program in C, but you aren't as likely to.

I tend to use C and C++ interchangeably (and yeah, I know there are vast differences), I didn't mean to imply that you can't write code in C++ that is as fast as C, I just get bored writing "C/C++"

This is not always true but depends on the operation. Cython/Numpy take advantage of Python's extensibility at the operating system level. See: http://stackoverflow.com/questions/2119761/simple-python-cha...

I wonder why we don't yet have CPUs and memory access that are more friendly to higher level structures. The Burroughs 5000 tried to do that and it worked. http://www.smecc.org/The%20Architecture%20%20of%20the%20Burr...

It's basically 100% true. Any program written in python can be translated to an equivalently functioning C++ program which requires fewer expensive operations to run.

The Python VM is doing a fair bit more work per instruction it executes; for example, incrementing an int isn't going to be a simple register add, it's going to involve a pointer dereference, some comparisons and branches, execution of several C functions, and overhead for interpreting the VM bytecode.

That said, if you understand what Python is doing under the hood you can greatly speed up your programs and approach C++ performance in some areas.

That said, I strongly recommend all performance-sensitive code is written in C++ with wrappers to drive it from Python.

It's true, you can translate any Python program to C++. When you do this you'll have the benefit of having debugged it and getting the logic correct in a safe language. Just have to make sure all of that translates correctly. It's nicer to develop an algorithm in Python first where your off by one errors will not segfault or worse silently fail.

See "The Computer Language Benchmarks Game" at http://benchmarksgame.alioth.debian.org/ for a head-to-head comparison of various small programs as measured across a wide number of language implementations. Do be careful that a "language" has no performance, only implementations of the language. For example, different implementations of Python may differ by an order of magnitude on a given task, as might different C compilers. Java and Javascript used to be considered slow languages, but the effective billions of dollars of R&D improved the implementations.

The overall solution space is complex. For example, development time on Python is about 1/2 that of C++ (the classic paper is http://page.mi.fu-berlin.de/prechelt/Biblio/jccpprt_computer... - is there something more recent?). Since algorithms can trump raw performance, it may be that in 8 hours its possible to develop a more sophisticated implementation in Python which outperforms the naive implementation in C++.

In the late 1990s, when people started using Python for traditional supercomputing problems, the phrase was to use Python to "steer" the low-level code written in a faster language. For example, NumPy is a Python API which uses C/ Fortran/ assembly code at lower levels for doing array calculations. Thus, only some people need to be skilled in both levels, while most can focus on writing Python code. The actual code has parts written in multiple languages, and not "only C/C++".

Didn't the PyPy folks have some issue with the language shootout, which led them to make their own?[1][2]. IIRC a lot of the Python code wasn't that optimized at all compared to the C/C++ programs.

1. http://speed.pypy.org/

2. https://alexgaynor.net/2011/apr/03/my-experience-computer-la...

No. Programs optimized specifically for PyPy were already being shown on the benchmarks game.

Previously, factual corrections to that blog post were shown in the comments but now the comments are not shown.

[2] The blog post tell's us that Alex Gaynor confirmed "with some CPython core developers" that his program didn't work because of a bug in CPython.

But the blog post doesn't tell us that Alex Gaynor never said there was any problem with a CPython bug.

Alex Gaynor's blog post tell's us that "It's also not possible to send any messages once your ticket has been marked as closed, meaning to dispute a decision you basically need to pray the maintainer reopens it for some reason."

But that's completely untrue! You can send messages when the ticket is marked closed! And you can open topics in the public forum! And you can click on a username and send email in 2 clicks.

There just wouldn't be any story to blog about, if Alex Gaynor admitted that he could easily have told me -- the bug is in CPython not in my program, so show my program -- but chose to say nothing.

I think "The Computer Language Benchmarks Game" is so politically loaded, that it shouldn't be referred anymore.

It can give people very wrong idea of performance between different languages. Especially people who don't have significant software development experience.

> so politically loaded

why do you say this?

That benchmark does not allow faster implementations of languages to be part of the benchmark. Like they allow only interpreted implementation of certain languages, not fast JIT version.

It's just the end results are even less meaningful this way.

All this is entirely within their rights, of course.

Someone else should create a competing programming language benchmark that includes all reasonable language implementations and all reasonable benchmark entries in those languages. Unfortunately, no one has bothered.

So you believe the reason for this is because of some political agenda? Are there conflicts of interest with the maintainers of the site? or I guess what are your reasons for your believing this?

I'm genuinely asking / curious. I've only looked at the site in passing maybe a few times.

Please take the program source code and measurement scripts and publish your own measurements.

http://benchmarksgame.alioth.debian.org/play.html#languagex

What is a better resource? The page itself talks about how no one should put much stock in the results, but there aren't really alternatives that give the same type of information.

Also see https://www.plat-forms.org/

Programming languages aren't slower or faster. The implementations of them are.

Provided no FFI or extensions written in other languages, non-I/O bound interpreted CPython is 50-100x slower than C/C++. JIT compiled (PyPy, etc.) Python might be in 2-10x slower bracket.

If extensions written in C/C++ are used, then you might be effectively comparing those extensions against another C/C++ implementation.

So if your code is going to be I/O bound and/or can effectively offload all computation in modules written in C/C++ (like NumPy), then Python might be practically as fast as C/C++.

If you use pure interpreted Python and implement compute limited algorithm in it, your code is going to be 50-100x slower than C/C++.

Real life scenarios are probably somewhere in between those two extreme cases.

> Programming languages aren't slower or faster. The implementations of them are.

People only say this if they haven't implemented a language.

Look at something like PyPy. The work is absolutely brilliant, written by insanely smart people... and it's still vastly slower than C for reasons that are implicit in the language. There are just aspects of the language that are hard to deal with (a lot of hidden allocations on the heap, etc.)

Here's a good talk on the subject: https://speakerdeck.com/alex/why-python-ruby-and-javascript-...

PyPy is still just a Python VM--it's not compiled, like C is.

You could write a Python compiler, but it would be difficult, and you'd need to sacrifice certain parts of the language (and/or extend it, even).

Take a look at Crystal[1]. Most Ruby code will compile without modification. Sure, some cases where type deduction is not possible (like `[]`), and certain cases of meta programming (like dynamic class creation at run-time), or accidentally calling a method on Nil (which is actually a feature to prevent runtime NPE[2]).

[1]: http://crystal-lang.org/ [2]: Null Pointer Exception, in case the acronym was ambiguous.

Well, there is a python compiler. And the compiled code is fast (although, the compile times are absurdly long). Specifically, RPython is a compiled language, and PyPy is written in RPython. So yeah, it's possible, and it has been done, but on the other hand... RPython is only superficially like Python, the semantics are vastly different. It's technically a subset, but the way you approach writing it is way different. It tends to feel like C with some syntactic sugar. So I don't think that invalidates what I'm saying, I think it actually demonstrates it: if you want efficient code the language needs to make efficiency a priority.

I agree, although I wouldn't say efficiency needs to be a priority. The language should simply be aware of the machine model instead of abstract those. It should know there's a processor, and that there's memory. Crystal does a pretty good job at being efficient without sacrificing much!

Look at implementing the Python language, couldn't you say that Python is faster than C if PyPy is faster than CPython ;-)

Not even Mike Pall, the author of LuaJIT and possibly the king of scripting language JIT performance, would say the language doesn't matter. He has said the language does matter and has talked about why Lua lends itself to good JIT performance.

> He has said the language does matter and has talked about why Lua lends itself to good JIT performance.

I didn't say it's equally easy. The problem is essentially "find fastest set of operations that give equivalent output". That can be a very hard problem to solve.

For practical purposes, some languages make it easier, some harder.

What you aren't factoring in is that dynamic languages mean that input can change the types of variables, so types essentially become inputs.

Then there is the issue of heap allocation of most if not all variables since their life times are hard if not impossible to determine. Heap allocation is fast, but not so fast that you can do it for every variable.

Compilers have been steadily advancing for 40 years now. Doing a lot of things previously deemed too hard or almost impossible. I'm pretty sure there will be further breakthroughs compiling more dynamic cases into some high performance form.

> Then there is the issue of heap allocation of most if not all variables since their life times are hard if not impossible to determine.

It's actually other way around. In most JITted "scripting languages", by far most variables have lifetimes that can be determined and stack allocated.

https://en.wikipedia.org/wiki/Escape_analysis

So you think scripting languages that have no type constraints will somehow advance to the point of being the same as writing native code?

Or.. do you think that maybe you know only scripting and dynamic languages and you want to believe that at some point a solution will come to you instead you having to learn programming at a lower level?

I've seen the latter attitude in plenty of people. It is better to just bite the bullet and learn a lower level language. And there is always Julia.

> So you think scripting languages that have no type constraints will somehow advance to the point of being the same as writing native code?

Absolutely. It's just a matter of time. Javascript JITters and LuaJIT are pretty good examples already. And there's so much more that can be done!

> maybe you know only scripting and dynamic languages and you want to believe that at some point a solution will come to you instead you having to learn programming at a lower level?

I do C/C++ (20+ years of experience). And a lot of other languages. Firmware and kernel driver development. 6502 (almost 30 years ago), 68k, x86 (+SSE/AVX/etc.), ARM (+NEON/etc)...

Sufficiently low level?

> I've seen the latter attitude in plenty of people.

There's a difference between where the buck is at right now and where it's going.

Ok, but what evidence suggests this to you other than optimism? What I see is dynamic languages having more underpinnings of fast native code or things like web assembly, which make them effectively faster.

I don't see any evidence that dynamic languages in general will somehow get much faster though.

> Ok, but what evidence suggests this to you other than optimism?

Intuition and optimism is a major part of it I guess. The fact that compilers have gotten increasingly clever over time. If current tracing JITs could handle branching in the trace instead of bailing out of any unexpected branch with a guard condition, we'd be closer to native performance.

From data side, for example Google's V8 can infer hidden classes and member types, turn javascript object (read: hash) into a binary structure, akin to C struct.

Well, one idea here: I envision profiling and tracing "superJITs" that can build a model of deterministic target code data flow (including target internal state), execution flow and computation. Not looking so much at the code itself at binary level, but analyzing the critical points that actually decide or compute something.

Once the model is built, the "superJIT" will compute constraints for model validity and build AST out of it. Data flow is used to see through hash tables and other transformations and where predictable, used to build binary structs for transient and state data. Simplify and optimize. Vectorize where possible. Output executable binary. Cache to RAM and to disk.

Limitations will of course be number of execution paths and too complicated data flow taints. Rarer execution paths could be pruned and special cased, and just generating fast code for the very likely paths.

Is this particular idea realistic? Frankly, I have no idea.

Do I think something similar will be built? Yes, but of course with constraints. The performance gap might never be completely removed, but incrementally narrowed. Perhaps eventually to few percent range.

We'll see.

strongly typed variables will always be faster than duck typing.

Manual memory management will always be faster than garbage collection.

Saying the language doesn't matter with regards to the performance is completely inaccurate.

> strongly typed variables will always be faster than duck typing.

If the types can be deducted, they'll be just as fast. And when not, you fall into a dynamic case. Such as polymorphism in OOP languages, pointers in C, etc.

> Manual memory management will always be faster than garbage collection.

That's a very strong statement. So you're saying it'll always be faster in terms of total used CPU time to use manual memory management vs. garbage collection?

I wouldn't dare to make a strong statement about memory management either way!

If you're talking about shared heap manual memory allocation, like C malloc/free style, that shared part will make sure it won't scale with CPU core count. You'll also need to track lifetimes of your object destruction. What if some other thread followed a pointer into the structure you're about to free and got pre-empted by the operating system? That calls for more thread synchronization, and puts hard limits to your scalability.

I think if CPUs with tens or hundreds of cores become popular, garbage collection might be the only realistic way to avoid object lifetime synchronization bottlenecks.

> Saying the language doesn't matter with regards to the performance is completely inaccurate.

It affects the difficulty of compiling it into a performant form. Dynamic features do make it more difficult, but just look at the progress in dynamic language compilation in recent years.

Who could have guessed for example Javascript could ever be within order of magnitude of C/C++ performance? But now it is there, and the gap is only getting narrower. In my own tests, occasionally I've seen Javascript and Lua JITters generating practically same code as "gcc -O3 -march=native" does!

"if", "could", "occasionally....practically the same".... you're talking about a lot of theoretical fringe cases to produce similar yet not the same performance results. And to what end? You're not disproving my point if you have to invent a use case where C is crippled to the point that Javascript is only "practically the same". Sorry, but that's just hypothetical hokum.

There's no denying that a lot of optimisations can occur with (and for want a better term) "scripting" languages. Nor that "scripting" languages aren't serious tools for serious development these days. But I also think it's fair to say that one language would out perform another in an idiomatic like-for-like contest - simply because those languages that trade in raw CPU performance do so at the gain of development time / productivity or application portability.

Thankfully these days most target platforms are powerful enough that we don't need to go that low level in pursuit of performance. And even on many popular cloud services / web sites where micro-optimisations can quickly multiply, productivity is often still a critical metric (case in point: I've barely touched C++ in recent years yet have written thousands of lines of Go, Perl, Javascript, etc).

So rather than arguing hypothetical fringe cases, we really should be praising praising the "slower" languages for providing useful abstractions.

> compute limited algorithm

If it wasn't compute limited it wouldn't be a very good performance test.

> Programming languages aren't slower or faster. The implementations of them are.

This is not true. Different languages provide different guarantees, which allow implementations to safely make different optimisations. For a trivial example, c99 is a faster language than c89, because the 'restrict' keyword was added.

The argument is that the mythical "sufficiently smart compiler" will figure out where restrict can be used automatically. In practice "sufficiently smart" means "at least as smart as a human", in which case pointer aliasing is the least of your concerns.

No. The 'restrict' keyword makes it just easier to write a compiler that can properly optimize pointer access. In other words: the compiler can be less sophisticated: it doesn't need to globally prove how a pointer is used. When it sees 'restrict', it can simply take shortcuts and assume no aliasing possible and no pointer tricks are used.

Can you add the keyword in appropriate places based on a set of rules when to use 'restrict' keyword? Yes? Then a hypothetical compiler could follow the same rules and get to same conclusions.

In theoretical extreme, you're correct. Even with a dynamically typed language like Scheme, if you do the whole program analysis you can eliminate most of run-time type checking, boxing/unboxing and some transient allocations (e.g. Stalin). The problem is that the cost of whole program analysis is superlinear and it'll doomed to be impractical as the size of program grows, imho.

Even whole program analyzing compilers can't necessarily outperform a well-tuned regular compiler, see e.g. MLTon vs OCaml in this (micro-) benchmark. The OCaml compiler is just well-written and well-tuned and performs surprisingly well.

http://www.ffconsultancy.com/languages/ray_tracer/performanc...

But then as always, this benchmark may just test an implementation detail (afair OCaml is unboxing floats or float arrays (?) or maybe some of the MLTon standard lib is really slow). I seem to remember other benchmarks mirroring these results though.

Interesting report. Thanks. Does MLTon recompile including standard lib? (Stalin does---it recompiles and inlines all std lib functions used from the program every time, which is why it takes so long to compile.)

Even if we ignore the massive complexity problems with whole-program analysis, what if you can't globally prove how the pointer is used? Pointer arithmetic can be done based on runtime information. A compiler doesn't have access to knowledge like 'this system will never encounter data that causes those pointers to alias'. If you add a system to provide information like that, well, you're pretty much defining a language extension right there.

Now, obviously you'd hope that people aim not to write programs that rely so subtly hopes and dreams of runtime information, but hopefully it's illustrative as a counterexample.

Also consider that fixed point optimization algorithms can only ever approach the optimal solution. Languages that are closer to the hardware generally have simpler (tighter) optimization constraints, and compilers for them will generally get closer to the optimal solution.

I find Python's speed is highly uneven and dependent on what you are doing with it.

Are you doing something that has some kind of underlying C implementation (file I/O usually)? Then it should be pretty quick.

Are you doing something that is all handled by the Python interpreter? Expect it to be slower than you'd like. e.g. for loops in Python are usually slower than list comprehensions.

It can be kind of frustration to write a bunch of code that runs lightning quick and then suddenly see your runtimes explode when you add a few more fairly trivial lines to complete off some code. I'd almost rather Python had a more consistent performance profile even if it was a bit slower on average than fastest possible, because it would make it easier to reason about the performance of your code.

So far I mainly just use the default Python implementation, but if you're really struggling with it, it's probably worth it to look into using one of the JIT or JVM implementations for more consistent speed profiles.

BTW, there's also all sorts of weird performance tweaks in the community...mostly of the form of syntax A vs. syntax B, and I've found that surprisingly few of them are "real" or offer more than trivial speedups.

In other cases, in other languages, you know what you need to do to speed things up, but Python either doesn't offer that mechanism in the language or buries it under somewhere else (try finding out how to preallocate lots of entries in a dictionary instead of incrementally growing it, it exists, but it's almost impossible to find using search words like "preallocate")

If you consider the raw languages, C/C++ is indeed faster. But unfortunately it's not that easy.

It's easier and faster to write a program in python that in C++. So given limited programmer time, it might be possible to write a faster solution in python than in C/C++ because you have more time to optimize your algorithm instead of fighting with the compiler. If you have a big project, you can spend the extra programmer time you gain by using python by moving crucial code from python to C. The crucial code can be found by using a profiler. (Saw an article about this some time ago, but don't remember which company actually did this)

Finally, python has a lot of math libraries that offer good speed for computation intensive operations, see http://www.scipy.org/.

So yes, it's not that easy. I would suggest use Python because it programs easier/faster, and if you really run into a wall, you can always port parts to C.

The same code is faster (and easier) to write, correctly, in Python than in either C or C++. (this depends a little on what you're writing, but not much: C/C++ make you specify much more about your code than python does.)

The same code, however, will run faster on C/C++. This is because python is doing some of the work for you, and you did that work upfront when writing the C/C++.

If you are doing something which involves a lot of computation, which all fits in RAM (using numpy in python will make that a fairer test between the two choices), then C/C++ will be faster.

Remember that a good pattern is to write your high-level logic in Python, and write a python implementation of your app, and then profile it to work out the slow parts of the code and speed them up using Cython[1], which will allow you to convert python-like code to efficient C (you can also straight up borrow C/C++ implementations from other people, too). This pattern is designed to balance minimising both programmer-time (since you will only have to code the important bits in C) and run time (since the performance-critical bits can be optimised.)

[1] http://cython.org/

(for pedants: I am referring to the CPython implementation, which is the only one which supports C/C++ extensions.)

Yes , and there is no point to ask questions like is X scripting is faster then c++ . each software that is running by software will be slower then native code .

I wish people would stop saying "C/C++" , these are 2 different languages.

Python* itself is written in C, not in Python. Which should give you clues to mediate and find your own answers.

*: Python, the canonical implementation.

> Python itself is written in C, not in Python. Which should give you clues to mediate and find your own answers.

PyPy is written in Python and is much faster than CPython in a lot of cases, so I'm not sure the argument you're making here is valid. http://speed.pypy.org/

This might be a silly question as I don't know much about compilers or interpreters, but how is that possible? Also, why hasn't the Python community tried to make PyPy the default then?

Various packages are incompatible with PyPy.

http://pypy.org/compat.html

PyPy is written in a subset of python called RPython. It is translated into c then executed.

> how is that possible

PyPy is written in a restricted subset of Python called RPython, which gets translated into C

https://rpython.readthedocs.org/en/latest/faq.html

I wish people would stop saying "C/C++" , these are 2 different languages.

That's disingenuous. C++ is largely a superset of C, to the point that a large C project such as gcc could be compiled with a C++ compiler without too much effort:

https://lwn.net/Articles/542457/

CPython is built more naively for lots of operations. A global lookup is a dictionary lookup. Getting a symbol out of an object is a dictionary lookup. An object creation is always an allocation; variables don't go on the stack. Everything is reference counted. The old 'range' builtin would create an actual list of that length in memory, rather than just keep track of the start and end points like a C-style for loop.

Other implementations could theoretically do better. PyPy can detect after a while that a variable can safely be declared on the stack, and so it will start to do that. If the object type is known, then a field lookup becomes just adding an offset to the pointer. It can even use different implementations for the same Python-visible classes (to store a range result in constant space, but still appear to be the full list, or use a different type of dictionary for objects and {}, or other things like that).

The "Python is the language, not the implementation" answer has already been given by @dalke, so I'll answer whether cPython, the implementation of Python that Python developers commonly use, is slower than C/C++:

cPython is necessarily slower and uses more memory than C for most tasks, and that's because cPython is implemented in C. You couldn't expect a new programming language that was implemented in Python to be faster than Python, either.

This is less of a concern for scientists and others with very tough performance requirements than it otherwise would be, in part, because cPython code can delegate C and C++ code[0]. This means portions of your program that need to be highly optimized can be implemented in C or C++, while the rest of your program can continue to be written in Python.

[0] https://docs.python.org/3/extending/extending.html

>cPython is necessarily slower and uses more memory than C for most tasks, and that's because cPython is implemented in C. You couldn't expect a new programming language that was implemented in Python to be faster than Python, either.

You are probably thinking of purely interpreted languages because for compiled languages this is not true. You could write a compiler for a new statically typed language in Python and that language could be orders of magnitude faster than any Python implementation.

Ah, yes. Good point.

My perspective having developed with Python for over 20 years now: it depends on the nature and context of the problem being solved.

In my experience, you usually need a CPU intensive problem for the implementation language to be a speed concern. Many practical everyday problems solved with Python (outside of contests and specialized fields) tend to be I/O bound.

Secondly, even when you do have a CPU bound problem, many Python modules you might use to solve it are wrappers for C/C++ implementations.

As a result, I've come to think of Python as a control and integration language and less as a platform for base algorithm implementation.

Viewed that way, I've found Python to be unbeatable for speed of implementation and long-term maintainability (two of my top metrics for valuing code).

I implemented an algorithm in Python and C++. Heavily IO bound task, read a float, multiply it with a factor, save to another file. Input file was several Gigabytes. I didn't do any optimization and I'm a C++ noob. Python was 30 times slower.

It is generally true. For the same algorithm, C++ can be hundereds of times faster, but sometimes you can push computations down to the C code in which the most popular Python implementation is written.

A very general approach to optimizing Python code is to look at all your loops and ask yourself which ones you can replace with library calls.

https://wiki.python.org/moin/PythonSpeed/PerformanceTips

What would be a good book to start to learn high performance C++ code?

The reference manual is Stroustrup's The C++ Programming Language, however it's not a great read for newcomers to the language. If you are new, I would start with university lectures (many esteemed schools teach C++ intro classes) and move onto the Stroustrup book which will get more into the implementations of STL algorithms and data structures. Those implementations will give you a good understanding of which to use when, i.e. high performance.

Thanks, will do. And if I want to go even further and also learn about how the code interacts with the hardware on the lowest level? So that I for example know what code will have lots of cache misses?

What about PyPy? It generates native (JIT) code and run as fast as C.

PyPy is an amazing project, but if you're really writing performance sensitive code then relying on the heuristics of a JIT is a dangerous game. There are also a lot of things that PyPy's JIT just can't realistically optimize.

Just because something generates native code does not mean it "runs as fast as C". Semantics of a particular language can force it to do more job without any chance to optimize that away.

For example, if you modify C compiler to make integer operations clamp at min/max rather than overflowing, it will always be times slower than original at number crunching, and there would be no way to overcome that.

It's generally difficult to say one language is faster than another, but there are some significant differences between the languages and implementations of Python and C/C++ that have very real performance implications.

Python is a dynamically typed language. This means that the language will handle conversions between types depending on the context. For example, one context can yield a 64 bit integer, another a arbitrary precision integer, another a string. Keeping track of when to use one versus another, and converting between costs performance. The different data representations for each type have different performance implications as well. For example, a 64 bit integer can fit into a register, and it's generally only one cycle to perform any math on it. Arbitrary precision requires math and carry be performed for every digit in the value. With C++, types are explicit, which means there is only one type for a value, and the representation is generally the most efficient (eg 64 bit integer).

Python is also generally interpreted. This means that code can't be directly executed on the CPU. An intermediate layer, called the interpreter takes an intermediate representation of the Python code, and translates it into instructions that run on the CPU. This happens at runtime, which adds overhead for each intermediate instruction. The more instructions you need to do something, the more overhead you have. C/C++ is compiled directly into code that executes on the CPU which is typically faster. This also allows for higher levels of optimization in code, since there's an understanding of what a piece of C/C++ code will look like when it executes on the CPU. The compiler can also optimize the code further, since it knows the code (generally) won't change. It's also a lot easier to use native features of the CPU like stack allocation, which is drastically faster than heap allocation.

One of the other differences is that Python tends to provide higher levels of abstraction than C/C++ code. So, doing something like a set intersection using x.intersection(y) may not necessarily be the fastest way. Python may do a hashed compare, but sorting and using memcmp may be faster. It's a lot more code to write though. This is generally the tradeoff for Python vs. C/C++ (natively compiled code) in general.

If you're concerned with performance, but you like programming in Python, you may want to check out Haskell. It's provides a lot of the same higher level abstractions Python provides, but the language is strongly typed and it can be compiled to native code. A simple example... http://uxcn.blogspot.com/2011/11/algorithm-complexity.html.

> One of the other differences is that Python tends to provide higher levels of abstraction than C/C++ code. So, doing something like a set intersection using x.intersection(y) may not necessarily be the fastest way.

C++ provides `set_intersection` as well: http://en.cppreference.com/w/cpp/algorithm/set_intersection

And the algorithm version may or may not actually be faster than Python. Essentially, the more abstract and generic things are (like Python), the more you can use them to easily do complex things arcoss different domains quickly. However, the actual concrete implementation is ultimately what matters as far as performance.

So, for example, Python may have a better algorithm, but C++ may use the hardware more efficiently.

> Essentially, the more abstract and generic things are (like Python)

And in C++, it provides the same high-level expressiveness as in Python.

> the more you can use them to easily do complex things arcoss different domains quickly.

But the advantage of C++ is that those abstractions have almost no overhead.

> So, for example, Python may have a better algorithm

Actually, C++ has a complexity guarantee for all of its algorithms.

> but C++ may use the hardware more efficiently.

Well, the brilliance of what Stepanov did was to build general purpose algorithms with out taking away random access capabilities which is beneficial for hardware efficiency(even more so now with modern cpus).

Yes. Does it matter? It depends.

If you're writing a game in python, you're going to have a bad time. Yes, I know CCP does it, but from what I've heard their engine is C++, and even then it's been a long, uphill battle. You're just going to have a very hard time meeting soft-realtime performance constraints (e.g. 30ms or 15ms frames) if very much of your code is in python.

If you're doing a programming challenge, you'll probably be fine? I've never done a programming challenge, but my assumption is that getting a result is the goal, and the performance of the code that gets it isn't that big of a deal, so long as it runs in a reasonable amount of time.

Really, the point is that you aren't going to see algorithmic-level speed differences between C/C++ and python most of the time. There are cases where this is untrue (e.g. where the algorithm relies on low level memory control), but it's true enough. You'll see a constant factor speedup, ranging somewhere between small and massive. I've heard 100x is typical for code that runs mostly in python and isn't just calling out to C, C++, or Fortran.

That said, the 100x number could be way off. For compute intensive tasks, if you're using numpy, you'll see a much smaller speedup. If you're not using numpy, but are great at writing multicore and simd code, you could see a 100(num_vector_lanes)(num_cores), so on a recent quad-core intel chip, you might be able to get a 10084 = 3200x speedup. This would take a long time to write, only applies to problems that are both compute-bound and easily parallelizable, and could be overly optimistic, but you get the idea (I don't know where the 100x number comes from, and how well the C++ programs it was compared with were written -- if it's from Alioth, last I checked they tended to leave a lot of perf on the table, but are not too bad).

Also, cache friendliness can make a massive difference. I've seen 10x speedups in C++ programs by utilizing the cache better, and I've heard of people getting even more significant speedups. Python's implementation is extremely cache unfriendly, but writing cache friendly C++ programs is non-obvious to a lot of programmers (or they don't consider it, or something), so you might loose out here. Along these lines, if your memory allocation patterns in C++ are naive, your code won't perform very well, and a lot of C++ programmers fall victim to this.

So who knows. If you're great at C/C++, know your architecture, are excellent at parallization and SIMD, and have the right problem, the difference could be massive. Barring that, I'd guess you'd get something like a 10x-50x speed up for average code, which is a lot, but maybe not that significant

Sort of rambled there, hope that made sense.

P.S. A lot of this is only true for CPython. I hear PyPy is faster (still no simd, multicore, or memory allocation or layout control though, so I suspect you can still beat it a lot of the time).

If we load entire data into memory the difference is negligible.

This is actually likely to be the scenario in which the differences are most visible. If your data fits in memory then you're more likely to be compute-bound, at which point C or C++ will completely flatten Python.

If your data is too big to fit into memory, then you're likely to be I/O bound, at which point the cost of I/O operations is likely to erase performance differences between the languages.

Reply on news.ycombinator.com