It’s Faster Because It’s C • Hacker News Board

Re: It’s Faster Because It’s C

#71

Post by JoeAltmaier » Tue, Jul 13, 2010, 7:24 PM UTC

_delirium wrote: post #27

JoeAltmaier wrote: post #14

Java leads the programmer into using bloated libraries, which absolutely litter the Java landscape. Its very hard to measure or even predict what effect a Java interface will have on your solution. I agree with the author, the language has no intrinsic slowness, its the tendency to use a triply-nested abstraction for every trivial purpose (a hash table of objects containing references to a database API...) instead of…

Compared to C that's true, but bloated libraries aren't exactly absent in the C++ world (one of many reasons that "C/C++" is usually a weird generalization). Nested templates of templates are all over the place, and as for pointers, it's common to wrap those too using one of the various smart-pointer classes. C often leads to bad algorithms, though, for the same reason it often leads to lean code tuned to the specifi…

Good analysis. I would amend: templates usually improve code efficiency, because the compiler can see through abstractions and generate (larger but) much faster code.

Re: It’s Faster Because It’s C

#72

Post by JoeAltmaier » Tue, Jul 13, 2010, 7:24 PM UTC

mfukar wrote: post #57

btilly wrote: post #53

Earlier quoted context omitted.

Yes. On the same hardware. And I'm sure that a specific example was thought of. To give one of several likely causes, CPU pipelines have grown much longer. As a result it is more important to avoid stalls these days. Naive code compiled with a modern compiler knows about the importance of this. For instance the compiler will know it can avoid a stall in certain cases by making sure that a read from memory that happen…

Well, if we're talking about different hardware, this whole discussion is moot - CPU (not C-entral anymore..) architecture changes render "old" optimization techniques only situational today. At any rate, the same is true for all languages, and _delirium's point is spot on: it's not the language that matters, it's the fact that bad (or slow, or inefficient, call it what you will) code is encountered regardless. It's…

Agreed. Its like my yellow framing hammer; useful for one job, but I have other hammers. (said this before)

Re: It’s Faster Because It’s C

#73

Post by kevingadd » Tue, Jul 13, 2010, 7:26 PM UTC

lemming wrote: post #13

There are a couple of excellent mailing list posts discussing the relative speed of JGit and Git, which are excellent reading: http://article.gmane.org/gmane.comp.version-control.git/1180... http://article.gmane.org/gmane.comp.version-control.git/1180... That said, there are probably very few applications that have been this heavily hand-optimised, and probably equally few where you actually need it. Where C really s…

I find those posts particularly interesting because they are not the typical criticisms levelled at high level languages; for the most part those posts read as a detailed list of design mistakes in Java: no unsigned types, no 'struct'-style types, reliance on boxing for generic containers, no way to 'reinterpret' blocks of memory C-style, etc. When people complain about using java to write software you often hear these individual design decisions come up.

it's also interesting to note that there are usable HLLs that suffer from few of the problems noted in those posts: both D and C# (though the latter required a second version to get some of it right) provide a garbage collected, object oriented environment like Java, but also provide a lot of the primitives needed for the kind of optimization discussed: pointers, structures, unboxed types, reinterpretation, and unsigned values.

I think this suggests that the problem is less 'hig level' languages and more 'immature' ones: C is a very mature language, descended from other mature languages, while Java was one of the first mainstream languages to make many of its decisions and as a result even now some of the larger mistakes have yet to be corrected (lack of function types and checked exceptions being two examples). Younger languages like D get to benefit from those lessons in the same way that C/C++ benefited from the mistakes of their predecessors.

Re: It’s Faster Because It’s C

#74

Post by barrkel » Tue, Jul 13, 2010, 8:38 PM UTC

tptacek wrote: post #22

No. C programs have fine-grained control over the memory layout of all their data, and thus are far better positioned to exploit caching in general and optimize for locality in particular. It's an attractive fallacy to suggest that most programs are I/O bound and thus are equally performant in Java and in C; while that statement does bode well for async code and poorly for threads, it's not as relevant for language c…

You overstate the degree to which large applications written in C have policy discretion over all memory allocations, to take your specific example. Compacting GC, by bringing together memory allocated close together in time, arguably has higher benefits for caching. The bigger problem is avoiding indirection, and that's a place where Java is weak in comparison to e.g. C#, as C# has value types. You can go further with some tricks in C, such as e.g. allocating string storage associated with a structure past the end of the structure's allocation itself, but here you're often just trying to regain what you lost by lack of GC.

OO-itis is something which definitely will sap performance if left unchecked, but it's true whether you're using C or Smalltalk. Much like denormalizing relational databases, careful placement of data members can reduce cache misses, and avoiding long chains of dereference for data commonly accessed together is important.

Re: It’s Faster Because It’s C

#75

Post by tptacek » Tue, Jul 13, 2010, 8:41 PM UTC

barrkel wrote: post #74

tptacek wrote: post #22

No. C programs have fine-grained control over the memory layout of all their data, and thus are far better positioned to exploit caching in general and optimize for locality in particular. It's an attractive fallacy to suggest that most programs are I/O bound and thus are equally performant in Java and in C; while that statement does bode well for async code and poorly for threads, it's not as relevant for language c…

You overstate the degree to which large applications written in C have policy discretion over all memory allocations, to take your specific example. Compacting GC, by bringing together memory allocated close together in time, arguably has higher benefits for caching. The bigger problem is avoiding indirection, and that's a place where Java is weak in comparison to e.g. C#, as C# has value types. You can go further wi…

I don't understand your argument. In terms of effort vs. reward, the one-line change of swapping malloc() with a pool allocator is probably the most effective optimization available to any software in any language.

The idea that C# (or for that matter any GC'd language) is going to beat an allocator in which alloc is amortized to a single load, constant add, and store seems... I don't know, fill in the blank.

You seem to think I'm advocating C over GC'd languages. I'm not. I write in Ruby by default, a language that is not only GC'd but badly GC'd. I just do so with my eyes wide open on performance.

Re: It’s Faster Because It’s C

#76

Post by tptacek » Tue, Jul 13, 2010, 8:42 PM UTC

silvestrov wrote: post #62

tptacek wrote: post #22

No. C programs have fine-grained control over the memory layout of all their data, and thus are far better positioned to exploit caching in general and optimize for locality in particular. It's an attractive fallacy to suggest that most programs are I/O bound and thus are equally performant in Java and in C; while that statement does bode well for async code and poorly for threads, it's not as relevant for language c…

A lot of average C programmers write high-performance linked-lists in C, while they could have used high-performance hashtables in Python/Ruby/Java with the same programming effort. (and no programs are high-performance if they have a pointer bug that makes the program crash). "The difference between theory and practice is small in theory and large in practice..."

Who writes high-performance code using linked lists? Linked lists are awful for performance. Every --- every --- large C project I've been involved in has a good generic hash table and a vector-style resizeable array.

Re: It’s Faster Because It’s C

#77

Post by barrkel » Tue, Jul 13, 2010, 8:47 PM UTC

tptacek wrote: post #75

barrkel wrote: post #74

Earlier quoted context omitted.

You overstate the degree to which large applications written in C have policy discretion over all memory allocations, to take your specific example. Compacting GC, by bringing together memory allocated close together in time, arguably has higher benefits for caching. The bigger problem is avoiding indirection, and that's a place where Java is weak in comparison to e.g. C#, as C# has value types. You can go further wi…

I don't understand your argument. In terms of effort vs. reward, the one-line change of swapping malloc() with a pool allocator is probably the most effective optimization available to any software in any language. The idea that C# (or for that matter any GC'd language) is going to beat an allocator in which alloc is amortized to a single load, constant add, and store seems... I don't know, fill in the blank. You see…

A pool allocator is great, so long as the lifetime of the pool meshes well with the allocations out of it. But the larger your application, the less likely that's going to be true. Different libraries will do their own allocations, and it's often hard to pass the right pool through enough layers of abstraction to be sure that e.g. that string got allocated in the right pool for where it's going to get plugged in when it comes back.

I'm not saying you're advocating C over GC'd languages. I'm specifically disagreeing with the idea that in practice, in large applications written in C, that the application author actually has discretion over allocation policy. I'm saying that you couldn't in practice use a pool allocator much of the time, even if you wanted to, unless your application is very self-contained.

The Delphi compiler I work on is written in C and uses pool allocators to great effect. There's a heap allocator which can be marked and shrunk, there's a pool for every unit, there's a pool for expressions, there's a pool for constants, etc. You've got to keep track of what got allocated where, make sure you don't pollute one pool with references to another, and sometimes do a bunch of copying to ensure that. Pooled allocation isn't a panacea, even for something as self-contained as a compiler, albeit a compiler which can be hosted by the IDE, so it needs to be long-lived, manage memory across debugging sessions, multiple compiles, etc.

Re: It’s Faster Because It’s C

#78

Post by tptacek » Tue, Jul 13, 2010, 8:52 PM UTC

barrkel wrote: post #77

tptacek wrote: post #75

Earlier quoted context omitted.

I don't understand your argument. In terms of effort vs. reward, the one-line change of swapping malloc() with a pool allocator is probably the most effective optimization available to any software in any language. The idea that C# (or for that matter any GC'd language) is going to beat an allocator in which alloc is amortized to a single load, constant add, and store seems... I don't know, fill in the blank. You see…

A pool allocator is great, so long as the lifetime of the pool meshes well with the allocations out of it. But the larger your application, the less likely that's going to be true. Different libraries will do their own allocations, and it's often hard to pass the right pool through enough layers of abstraction to be sure that e.g. that string got allocated in the right pool for where it's going to get plugged in when…

This is like saying "there will always be some code you can't optimize, so this optimization doesn't matter". I know you know that isn't true.

Real library code either owns object lifetimes (and can use pools internally because the library's own _release() function is the only thing that can free its state), or keeps its hands completely off allocation. The few counterexamples, where for instance a library malloc()'s something and expects you to free it, tend to be notorious examples of error-prone and evil interfaces.

Meanwhile, just because everything isn't amenable to pool allocation (or, even better, arena allocation, where there is zero memory management overhead at all ever) doesn't mean you don't win huge on the places that are amenable.

You are raising the boogeyman of a hypothetical library that is going to take a pointer that I pool allocated and call free() on it, blowing up the program. I assert that any real example of such a library is going to be easy to shoot down as "an incredibly crappy library".

Re: It’s Faster Because It’s C

#79

Post by btilly » Tue, Jul 13, 2010, 8:53 PM UTC

mfukar wrote: post #57

btilly wrote: post #53

Earlier quoted context omitted.

Yes. On the same hardware. And I'm sure that a specific example was thought of. To give one of several likely causes, CPU pipelines have grown much longer. As a result it is more important to avoid stalls these days. Naive code compiled with a modern compiler knows about the importance of this. For instance the compiler will know it can avoid a stall in certain cases by making sure that a read from memory that happen…

Well, if we're talking about different hardware, this whole discussion is moot - CPU (not C-entral anymore..) architecture changes render "old" optimization techniques only situational today. At any rate, the same is true for all languages, and _delirium's point is spot on: it's not the language that matters, it's the fact that bad (or slow, or inefficient, call it what you will) code is encountered regardless. It's…

The discussion is only moot to the extent that the complaint is inaccurate. It is true that code, once optimized, is frequently hard to unoptimize. It is further true that what you optimize for at one point does not match what you optimize for at another. It is also true that there is a lot of C that is now optimized for the wrong thing. And finally it is true that people who write C because they are trying to squeeze performance are more generally prone to create more of it.

As long as those facts remain true, it is fair to complain about this tendency in C code in the wild. Even though the problem clearly lies with some of the programmers the language attracts rather than with the language.

Re: It’s Faster Because It’s C

#80

Post by barrkel » Tue, Jul 13, 2010, 8:57 PM UTC

tptacek wrote: post #78

barrkel wrote: post #77

Earlier quoted context omitted.

A pool allocator is great, so long as the lifetime of the pool meshes well with the allocations out of it. But the larger your application, the less likely that's going to be true. Different libraries will do their own allocations, and it's often hard to pass the right pool through enough layers of abstraction to be sure that e.g. that string got allocated in the right pool for where it's going to get plugged in when…

This is like saying "there will always be some code you can't optimize, so this optimization doesn't matter". I know you know that isn't true. Real library code either owns object lifetimes (and can use pools internally because the library's own _release() function is the only thing that can free its state), or keeps its hands completely off allocation. The few counterexamples, where for instance a library malloc()'s…

That's a complete straw man, and you know it. I'm saying that the specific optimization you mentioned is hard if you don't control all the pieces.

The primary advantage of a pooled allocator isn't in allocation - though that's nice - it's that you don't have the cost of iterating through each object to free it. But if you have external libraries, they'll abstract their allocations into handles (say), and now you have the problem of running what amount to destructors.