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

The "C is Efficient" Language Fallacy

scienceblogs.com

Post reply on HN
Print view View original

61–70 of 127 posts

Re: The "C is Efficient" Language Fallacy

#61

Post by jjs »

tptacek wrote: post #36
jjs wrote: post #31

Earlier quoted context omitted.

> First, cite sources for specific cases where a mainstream malloc() is "a lot slower" than a specific GC'd allocation in a mainstream HLL. This rings more truthy than true to me. > Second, fixing malloc slowness is among the easiest and fastest optimizations you can make in a C program (in most cases, a pool and freelist will get you 90% of the way there), and no GC'd allocator is faster than pool and arena allocati…

You're not counting the cost of deallocation.

In the collectors I mentioned, deallocation is a matter of moving the live objects to the other semispace, and considering the "current" semispace to be garbage.

If you're allocating a lot of short-lived objects, then explicitly keeping the live objects is much more efficient than explicitly culling the dead objects.

Re: The "C is Efficient" Language Fallacy

#62

Post by brl »

lallysingh wrote: post #49
tptacek wrote: post #36

Earlier quoted context omitted.

You're not counting the cost of deallocation.

Not an easy thing to count globally. Your GC cost (at least in mark-sweep) is dependent on the number of objects you're not deallocating. The rest are implicitly destroyed.

In the case of a minor collection, you don't do a full mark-sweep. You only look at a small fraction of the live objects. Generally you only need to trace objects in the youngest generation which are reachable from GC roots. Since you expect most young generation objects to be eligible for collection, this is extremely fast.

It is unusual for a lot of references to exist from older generations to the youngest generation, but when this occurs there are data structures for detecting and resolving these references very efficiently.

Re: The "C is Efficient" Language Fallacy

#63

Post by jrockway »

Oxryly wrote: post #53
jrockway wrote: post #50

Earlier quoted context omitted.

Some quick googling suggests you are wrong: http://www.cas.mcmaster.ca/~kahl/Publications/TR/Anand-Kahl-... http://wwwlasmea.univ-bpclermont.fr/Personnel/Jocelyn.Serot/... http://tirania.org/blog/archive/2008/Nov-03.html etc.

I would suggest taking a closer look at those links. They bring up another point in that you'll only find current, usable, robust support for SIMD in C++: The first link is just a paper; the second is a 1.0 release that is seven years old, it only supports SSE, and it's all in French; the third is only for Mono, it only supports SSE and its SSE support is old and incomplete. On the other hand, if you try to use SIMD…

(I'd love to use a current and comprehensive version of Haskell SIMD, but its just not ready for prime time.)

Since you're obviously an expert in the area, why aren't you helping make it ready for prime time?

Re: The "C is Efficient" Language Fallacy

#64

Post by brl »

jdvh wrote: post #45
jjs wrote: post #31

Earlier quoted context omitted.

> First, cite sources for specific cases where a mainstream malloc() is "a lot slower" than a specific GC'd allocation in a mainstream HLL. This rings more truthy than true to me. > Second, fixing malloc slowness is among the easiest and fastest optimizations you can make in a C program (in most cases, a pool and freelist will get you 90% of the way there), and no GC'd allocator is faster than pool and arena allocati…

> just bumping a pointer If only. You have to check for out-of-memory, and throw an exception if so. (This check can sometimes be optimized away, though). You also have to mark the size of the allocated block, so the garbage collector knows how many bytes to copy during the sweep phase. Also, garbage collectors usually allocate from a shared memory pool, so every allocation also involves some mutex operations. Alloca…

> You have to check for out-of-memory, and throw an exception if so.

You have to check if there is space for the allocation in the current space. This is two native instructions, a compare and a conditional branch. If the allocation fails, you don't throw an exception, you launch a minor collection.

> You also have to mark the size of the allocated block

Yes and no. When an object is initialized, type information is recorded that contains the size. I don't think that the Java VM explicitly stores the size of the allocation somewhere. It certainly doesn't need to since the same information is available by just looking at the object itself.

> Also, garbage collectors usually allocate from a shared memory pool, so every allocation also involves some mutex operations.

In the Java VM this problem is addressed by dividing the Eden space into chunks where each chunk is private to a single thread.

> Allocation is bumping a pointer in theory only.

An object allocation in Java is around 10 assembly instructions. More than just 'bumping a pointer' but not a lot more.

Re: The "C is Efficient" Language Fallacy

#65

Post by jjs »

tptacek wrote: post #60
lallysingh wrote: post #49

Earlier quoted context omitted.

Not an easy thing to count globally. Your GC cost (at least in mark-sweep) is dependent on the number of objects you're not deallocating. The rest are implicitly destroyed.

You can't decouple the cost of malloc() from the cost of free(); if malloc has to do any more work than simply bumping a pointer (or, in the general case, grabbing a mutex and then bumping a pointer), it's a concession to free() (or to defragmentation, a side effect of free).

Semispace (and generational) collectors do decouple the cost of allocation from the cost of collection by only considering the set of live objects. They also compact (defragment) as a side effect of collection.

Re: The "C is Efficient" Language Fallacy

#66

Post by scott_s »

Aron wrote: post #42
chancho wrote: post #29

Fortran's (alleged) dominance in scientific is probably attributable to tradition (they still teach it to undergrads in non-CS departments) but the native multidimensional arrays have a much bigger impact than aliasing. In Fortran you just index your array like A(i,j,k) and the compiler will compute (and optimize) the addressing for you. In C, a typical (non-computer) scientist who doesn't really focus on mundane shi…

This looks like a lot of calcs for the inner loop but is quite easily optimized. The compiler knows that (j * ni + i) is constant in the k loop and that ni * nj is constant. Check the assembly output. But it is probably better to reorder the loops and traverse linearly through memory so that each cache line brought down is fully consumed in order.

The point of that code example is not the calculations, but accessing memory in a cache-friendly way.

Re: The "C is Efficient" Language Fallacy

#67

Post by scott_s »

jrockway wrote: post #63
Oxryly wrote: post #53

Earlier quoted context omitted.

I would suggest taking a closer look at those links. They bring up another point in that you'll only find current, usable, robust support for SIMD in C++: The first link is just a paper; the second is a 1.0 release that is seven years old, it only supports SSE, and it's all in French; the third is only for Mono, it only supports SSE and its SSE support is old and incomplete. On the other hand, if you try to use SIMD…

(I'd love to use a current and comprehensive version of Haskell SIMD, but its just not ready for prime time.) Since you're obviously an expert in the area, why aren't you helping make it ready for prime time?

That's really not fair. I know of many things in and outside of my area of research that need improvement, as does any researcher. But we can only work on one thing at a time.

Re: The "C is Efficient" Language Fallacy

#68

Post by viraptor »

tptacek wrote: post #25
lallysingh wrote: post #21

Earlier quoted context omitted.

Small C programs start up faster than HLL programs. Small C programs run faster. When they get bigger, they quickly bloat up to compensate for how hard C makes it to write large-scale software. Oh, and it takes a lot longer to modify those C programs, for the same reasons. C's malloc() time is also a lot slower than GC'd languages. For them, a memory allocation isn't much more than a subtraction.

First, cite sources for specific cases where a mainstream malloc() is "a lot slower" than a specific GC'd allocation in a mainstream HLL. This rings more truthy than true to me. Second, fixing malloc slowness is among the easiest and fastest optimizations you can make in a C program (in most cases, a pool and freelist will get you 90% of the way there), and no GC'd allocator is faster than pool and arena allocation (…

Actually firefox is a large hll program. It's a javascript / xul engine in a large part. The frontend of firefox is actually javascript AFAIK. Maybe someone has more precise information?

1 and 2 were already commented on, so I'll just add that, there was a proof that a copying gc with enough memory can be faster than manual allocation. http://www.cs.umass.edu/~emery/pubs/04-17.pdf

Re: The "C is Efficient" Language Fallacy

#69

Post by chancho »

scott_s wrote: post #66
Aron wrote: post #42

Earlier quoted context omitted.

This looks like a lot of calcs for the inner loop but is quite easily optimized. The compiler knows that (j * ni + i) is constant in the k loop and that ni * nj is constant. Check the assembly output. But it is probably better to reorder the loops and traverse linearly through memory so that each cache line brought down is fully consumed in order.

The point of that code example is not the calculations, but accessing memory in a cache-friendly way.

Well, yeah, but since Fortran stores things in column-major that's not really an issue. My broader point was that all of these details are hidden from programmers, so there's less for the programmer to screw up and more room for the compiler to work within.

Re: The "C is Efficient" Language Fallacy

#70

Post by kmavm »

I worked on VMware's virtual machine monitor from 2000 until June. Overcoming customers' performance fears was a major impediment in the early years. Every fraction of a percent we gave up relative to native ruled out whole classes of applications. Nothing other than C would have been conceivable. Even C++ would have been wildly inappropriate, as it is for most kernels, because so much invisible code can hide behind a close-brace.

The mapping from source to machine representation in C is relatively trivial, which is the source of all C's ups and downs. If you ever plan to count microseconds, cache misses, TLB misses, mispredicted branches, etc., you had better start with a toolchain whose machine-level output is grokable from the source.

Post reply on HN