http://c2.com/cgi/wiki?AsFastAsCee

My God... the cacophony of bickering voices!

Post a reply to this message

Invisible wrote:
> http://c2.com/cgi/wiki?AsFastAsCee
> 
> My God... the cacophony of bickering voices!

Einstein already said you can't go faster than c...

Post a reply to this message

Nicolas Alvarez wrote:

> Einstein already said you can't go faster than c...

Best. Quote. Ever.


25 points to Nicolas!!

Post a reply to this message

Invisible wrote:
> http://c2.com/cgi/wiki?AsFastAsCee
> 
> My God... the cacophony of bickering voices!

It isn't just the programming language, it's how you write in the 
programming language.

Simply changing the order you list your commands can make a big 
difference in speed.

On some processors counting down to zero is faster than counting up to a 
specific number.

Post a reply to this message

Tom Austin wrote:

> It isn't just the programming language, it's how you write in the 
> programming language.

It isn't just the language. It's the interpretter or compiler. It's the 
libraries. It's the runtime system (e.g., the garbage collector, the I/O 
subsystem, the concurrency implementation).

But yes, some languages make it more awkward to do things in certain 
ways, and easier to do things in certain other ways. Which may help or 
hinder performance. Also, the limitations of the language may make the 
compiler's job harder or easier.

> Simply changing the order you list your commands can make a big 
> difference in speed.
> 
> On some processors counting down to zero is faster than counting up to a 
> specific number.

If you're comparing JIT-compiled Java to purely interpretted Lisp, I 
guarantee you it makes no measurable difference. The overhead of 
everything else outweighs it manytimes over.

Post a reply to this message

>> On some processors counting down to zero is faster than counting up to a 
>> specific number.
>
> If you're comparing JIT-compiled Java to purely interpretted Lisp, I 
> guarantee you it makes no measurable difference. The overhead of 
> everything else outweighs it manytimes over.

Sure, but there are circumstances when it is measureable, like if you are 
writing the row-copy code to draw part of a sprite onto the screen.

Actually I remember on my 32bit ARM CPU, if you want to copy a large number 
of bytes from a word (32-bit) aligned address to a non-word-aligned address 
there were two ways to do it.  The first was to just use the load-byte and 
store-byte commands, but a way faster method was to load and store words at 
a time with some clever bit shifting and masking.  Even though the code 
looked uglier and longer, it was much faster.  Similarly, counting down to 
zero saved one clock cycle per loop, and when your loop is only a few clock 
cycles and your game is limited by the speed of drawing sprites on the 
screen it makes a big difference.

Post a reply to this message

scott wrote:
>>> On some processors counting down to zero is faster than counting up 
>>> to a specific number.
>>
>> If you're comparing JIT-compiled Java to purely interpretted Lisp, I 
>> guarantee you it makes no measurable difference. The overhead of 
>> everything else outweighs it manytimes over.
> 
> Sure, but there are circumstances when it is measureable.

I'm sure there are. I'm saying that in very high-level languages (e.g., 
Perl, VB, etc.) there are much bigger influences to worry about fist.

> Actually I remember on my 32bit ARM CPU, if you want to copy a large 
> number of bytes from a word (32-bit) aligned address to a 
> non-word-aligned address there were two ways to do it.  The first was to 
> just use the load-byte and store-byte commands, but a way faster method 
> was to load and store words at a time with some clever bit shifting and 
> masking.  Even though the code looked uglier and longer, it was much 
> faster.  Similarly, counting down to zero saved one clock cycle per 
> loop, and when your loop is only a few clock cycles and your game is 
> limited by the speed of drawing sprites on the screen it makes a big 
> difference.

Now, see, as I understand it, computer technology has now reached the 
point were saving a few cycles makes *no difference* at all, and the 
_only_ thing that matters is cache hit ratios.

If you use a faster addressing mode, maybe your program will complete a 
few microseconds faster. If you have a pipeline stall, your program will 
halt for a dozen cycles, and if there's a miss in the L2 cache, the CPU 
will basically shut down and do nothing for several thousand cycles.

It's got so bad that theoretically "inferior" algorithms can actually be 
faster due to cache behaviour, even though they take "more operations" 
to do.

Personally, I find that sad...

Post a reply to this message

> It's got so bad that theoretically "inferior" algorithms can actually be 
> faster due to cache behaviour, even though they take "more operations" to 
> do.

Only "inferior" if you assume they run on a machine that can access every 
single data location and process every single instruction at a constant 
speed.

As you pointed out, this certainly isn't the case and things are much more 
complex now, but that shouldn't put you off trying to optimise your code, 
you should just optimise it to work with the cache first rather than with 
the ALU.

Post a reply to this message

scott wrote:
>> It's got so bad that theoretically "inferior" algorithms can actually 
>> be faster due to cache behaviour, even though they take "more 
>> operations" to do.
> 
> Only "inferior" if you assume they run on a machine that can access 
> every single data location and process every single instruction at a 
> constant speed.

Or rather, if you assume that every possible "operation" takes the same 
amount of time - a highly useful simplification if you're trying to 
compare several different algorithms.

> As you pointed out, this certainly isn't the case and things are much 
> more complex now, but that shouldn't put you off trying to optimise your 
> code, you should just optimise it to work with the cache first rather 
> than with the ALU.

What this means is that any programming language that features automatic 
memory management is instantly many hundred times slower than a language 
using manual memory management, and there's nothing you can do about it.

I find that sad.

Post a reply to this message

Invisible escreveu:
> Nicolas Alvarez wrote:
> 
>> Einstein already said you can't go faster than c...
> 
> Best. Quote. Ever.
> 
> 
> 25 points to Nicolas!!

Indeed!  Insightful +5! :D

Post a reply to this message

> What this means is that any programming language that features automatic 
> memory management is instantly many hundred times slower than a language 
> using manual memory management, and there's nothing you can do about it.
>
> I find that sad.

What's sad is if the authors of such languages have not thought about cache 
usage when designing the compiler.

I don't see how it's any different to people using BASIC complaining that 
they can't benefit from the "count down to zero" loop because BASIC won't 
let them remove the extra compare instruction.

As always, if you want complete control over the CPU use assembler, if you 
want a little less control use a language like C.  You use higher level 
languages to make writing the code easier, but you lose direct control of 
the CPU.

Post a reply to this message

scott wrote:

> What's sad is if the authors of such languages have not thought about 
> cache usage when designing the compiler.

What's sad is that a cache need to exist in the first place. It means 
that whole classes of highly efficient algorithms aren't efficient any 
more. It means you have to mutilate your program designs just to keep 
the cache happy.

But still, there's nothing that anybody can ever do about it, so I guess 
there's no point worrying about it...

> As always, if you want complete control over the CPU use assembler, if 
> you want a little less control use a language like C.  You use higher 
> level languages to make writing the code easier, but you lose direct 
> control of the CPU.

I don't *want* low-level control over the CPU - the sad thing is that 
with current designs, it's completely necessary if you want any 
semblance of performance. With current designs, it seems that basically 
any attempt to use any language higher than assembly is doomed to abject 
failure, performance-wise. And this saddens me.

Post a reply to this message

> What's sad is that a cache need to exist in the first place. It means that 
> whole classes of highly efficient algorithms aren't efficient any more. It 
> means you have to mutilate your program designs just to keep the cache 
> happy.

Ermm, caches make things faster and more efficeint to varying degrees, not 
slower.

Post a reply to this message

scott wrote:

> Ermm, caches make things faster and more efficeint to varying degrees, 
> not slower.

Caches make _some_ things faster. Other things stay laughably slow. :-(

Post a reply to this message

>> Ermm, caches make things faster and more efficeint to varying degrees, 
>> not slower.
>
> Caches make _some_ things faster. Other things stay laughably slow. :-(

So what's the problem then?  Some things are faster, others stay the same 
speed.

Unless, of course, you could afford to have 8GB of on-die RAM at the same 
speed as the L1 cache :-)

Caches are just a very cost effective way of speeding most things up, do you 
have a better suggestion?

Post a reply to this message

Invisible wrote:
> What this means is that any programming language that features automatic 
> memory management is instantly many hundred times slower than a language 
> using manual memory management, and there's nothing you can do about it.

Huh? Where did you come up with this factoid? GC can actually help improve 
cache hits, while manual memory management requires you to touch all kinds 
of pages at times when it might not be beneficial. For example, if you need 
to free the root of a large tree on the heap, using manual memory 
management, you now have to run through the whole tree, touching every page 
where there's a leaf, and cleaning it up. If 50 instructions later you free 
another tree, you have to do that all again, even if it's all in the same 
pages as the first tree.

Of course, the higher level the language is, the more opportunity for 
optimizations. For example, the talk on that page about what the .NET system 
does is incorrect. That's the .NET that was around when they wrote that 
sentence. You can (and always could), of course, precompile an entire 
assembly, rather than waiting for JIT - of course the data structure 
libraries don't get recompiled every time you run the program. And later 
compilers will do all kinds of cross-assembly optimizations if you want, in 
a way that would be very difficult for a C compiler to manage (like taking 
unused slots out of a struct to save memory).

> But still, there's nothing that anybody can ever do about it, so I guess there's no
point worrying about it...

Sure there is. Slow your CPU down a whole bunch. Happy now?

-- 
   Darren New, San Diego CA, USA (PST)
   The NFL should go international. I'd pay to
   see the Detroit Lions vs the Roman Catholics.

Post a reply to this message

scott wrote:
> Actually I remember on my 32bit ARM CPU

Woohoo snap :) Genius.

Post a reply to this message

Nicolas Alvarez wrote:
> 
> Einstein already said you can't go faster than c...
> 

LOL, good one in deed :-D

Post a reply to this message

My personal opinion:
As you know I don't know much of programming but for I've seen C (ANSI 
C, C++, C# and al the variants) is the King Language, if it keeps 
evolving in its abstractions/implementations to cover more needs it will 
be there for ever or at least until a better language come along, if so, 
I'm sure will have to be based on C at least conceptually.

C I believe is a reference for the other languages, like the Grandfather 
of programming languages.

FWIW I believe C should have a kind of optimizer/distiller that gives 
the assembler-level optimized (speed and/or size) .exe image, for every 
hardware platform, so the programmer doesn't have to worry about 
low-level tricks and concentrate more in the program abstract idea and 
its implementation. I think the compiler gives optimizations only by 
changing the order of the statements because it's partially optimized 
according to certain statement criteria it recognizes but not fully 
optimized for the assembly language level.

Cheers.

Post a reply to this message