OSDev.org

Posted: **Fri Feb 24, 2012 8:36 pm**

Java & outperforming... in the same sentence. I've seen it all.

Posted: **Fri Feb 24, 2012 9:31 pm**

Are you kidding me? Did you even read the "demeaning and insulting" posts aimed towards him, one of our most knowledgeable and valued members? I think this is enough to get anybody irritated:

It's one thing to know how, another to understand why. Functional programming theory is not "academic wank," it's central to some of our deepest insights about formal systems. It's called the Church-Turing thesis for a reason. Let's break it down: Brendan appears to understand Alan Turing's theoretical contribution to computing but completely derides the brilliant insight offered by Alonzo Church. Turing certainly thought the lambda calculus was valuable; I'm not surprised that Rusky (in particular) became irritated by his attitude.

Might be good to learn some computing theory.

Indeed, it might be good. I've always found theory to be quite useful

Java & outperforming... in the same sentence. I've seen it all.

First, bear in mind that I'm comparing apples to apples, Java code compiled down to machine code vs C++ code compiled down to machine code (ignore the JVM.)

consider the following C++:

Code: Select all

template <class any_t> array_fill(any_t * const ptr, const size_t size, const any_t value)
{
    for (size_t i = 0; i < size; i++) ptr[i] = value;
}

"but this isn't optimised, it would go faster with a pointer walk" you say. Not so. Any compiler worth it's salt will make the following deduction:

ptr + (i + x) == (ptr + i) + x

... and optimise the loop out to a pointer walk. Compilers are much better at making these sorts of optimisations than humans, they just do a brute force search and will spot anything within their search space.

The parse tree for a Java program has a lot more constraints on it than a parse tree for a C++ program; the space in which the object (the parse tree) is defined is richer, it has more structure. There are simply more axioms that can be applied that preserve the algorithm the tree expresses, ergo, the compiler can do a much more exhaustive search for possible optimisations.

This is why, with modern C++ compilers, it's so very important to write const correct code and avoid trying to manually optimise things that the compiler will deal with. It's better to avoid pointer arithmetic. Choosing quicksort over bubble sort is the kind of optimisation humans are for, unrolling loops, walking pointers, and inlining functions is what compilers are good at. Modern compilers even take cache prefetch and line size into account for every instruction they generate.

It also pays to consider the statistics involved. The probability that a given line of code will be executed is not uniform, indeed it is generally a long tailed distribution, that is, there is a small amount of code that is executed very frequently (the inner parts of loops) and a large amount that is executed infrequently (outer control and dispatch code.) This is why run-time bounds checking is nowhere near as expensive as old school C/C++ programmers assume, in 99% of cases the compiler can shunt the bounds check outside of any loops, and with dependent type analysis can often remove it entirely.

Posted: **Fri Feb 24, 2012 10:28 pm**

I edited away that part of my post, but since you apparently had the time to reply...

So if you do not agree that functional programming is the greatest, you need "to learn some computing theory." ? That is absurd.

You seem pretty hung up over his "academic wank" thing, maybe he would never had formulated it as such if the other guy didn't start out by insulting his knowledge just because he didn't agree?

Eh, Java can never outperform anything. Ever. I don't know about optimization for random code snippets, but unless your codebase is like 1-2gb of source (out weighting the libs and random bloat), it won't matter. Java is slow. Always have been. I'm not sure if this is because of the libs, JIT, whatever. It just eats CPU and RAM for breakfast, so whether or not it optimizes a for-loop better doesn't matter in the long run.

A quick look on file-size (combined - everything you need to run) tell you most of the story. Asm > C > C++ > Java.

Posted: **Fri Feb 24, 2012 10:39 pm**

So if you do not agree that functional programming is the greatest, you need "to learn some computing theory." ? That is absurd.

It's clear that Brendan doesn't understand at all what functional programming is about (nor do a lot of people in this thread to be honest.) Functional programming languages treat functions as first class objects, meaning functions can take functions as arguments and return functions. Brendan seems to think this is equivalent to C function pointers, it is not; a function pointer is a reference to a function, not a function. You can't compose a function in C. He refuses to even try to understand this point. Functional programming is about much more than just functions without side effects. He does need to learn some computing theory.

EDIT: for the record, I DON'T think "functional programming is the greatest" I just think it's very useful theoretically, I have a problem with people who think they know everything (I don't.) To be honest I rarely write much strictly functional code, at the moment I'm working entirely in x86 assembly, but my knowledge of computing theory colours the way I think about it.

For a good look at how interesting a formal approach to programming can be look up the curry-howard correspondence on wikipedia, truly mind bending stuff

Eh, Java can never outperform anything. Ever. I don't know about optimization for random code snippets, but unless your codebase is like 1-2gb of source (out weighting the libs and random bloat), it won't matter. Java is slow. Always have been. I'm not sure if this is because of the libs, JIT, whatever. It just eats CPU and RAM for breakfast, so whether or not it optimizes a for-loop better doesn't matter in the long run.

You clearly did not read my last post. Just In Time compilation (and the overhead implied) does not apply if you are compiling a Java program down to machine code; just a plain ordinary executable file. You'll find that if you compile a Java program with GCJ to run natively, and statically link it, it'll be about the same size as a statically linked C++ program that does the same thing, and run at least as fast.

Posted: **Fri Feb 24, 2012 11:23 pm**

Ok fine. But in my opinion he started with the bad tone, and Brendan has earned lots of respect on this forum for his knowledge in almost everything from languages, compilers, general os-dev, hardware..... When Rusky has been around for like 10 years or earned some more forum-cred he can start advising people to read up on theory.

(yes, I'll start a Brendan fan-club soon

)

About Java, I've never seen anything compiled natively, ever. So sure, you might be right. But the damage is done for my part. It took like 15 years for hardware to catch up to all it's bloat. And I know all to many fresh-from-uni Java "programmers" that barley know how to reinstall windows. It's like they learn the Java/OOP mantra by heart just to get a job, with no personal interest or prior computer knowledge at all. It makes me sick just to think about it. So Java is never going to be something I take seriously.

Posted: **Sat Feb 25, 2012 2:12 am**

childOfTechno wrote:I'm going to have a rant ...

Me too.

childOfTechno wrote:Anyway, this thread is dead Jim ...

Well, it was...

childOfTechno wrote:It's amazing how the uninformed can be so sure of themselves

Ignorance is bliss...

childOfTechno wrote:principle #1:
"Being able to prove things about a program has performance advantages."

Not really. For example, how would proving that a program performs poorly have performance advantages?

childOfTechno wrote:Code generated by a good Java compiler (for instance) will often outperform code for the same algorithm generated by an equally good C++ compiler. The simple fact is that it is a lot harder for the compiler to reason about a C/C++ program, which limits the optimisations it can do (primarily because of pointers.) By the way, I'm talking about compiling Java straight to machine code, not bytecode.

If we are assumming both compilers are equally good (Which I doubt, because I have yet to see a good Java-to-native compiler, whereas good compilers for C++ have been around for years) And we are comparing Java to C++, we still have 2 unknowns here. The actual performance of said compiled programs, and the programming skill of the 2 programmers (Even if its the same person, it's not likely that they are equally good with both languages.) If we assume equal programming skill in each program, C++ will out preform java in a vast majority of situations. This includes processing power, file size, RAM usage, etc. Java loses for file size automatically because of the Java run time. And I don't know why, but every Java program just eats RAM for breakfast.

childOfTechno wrote:an example:

In C++ "const" doesn't really mean "const". The compiler can't rely on a pointer/reference to a const variable not having it's constness cast away at some point: the assumption that when you pass a reference to a local const variable to some arbitrary function it's value won't change simply doesn't hold. (although it should, and you should assume that the compiler thinks this way.) In more strict languages const (or whatever it's equivalent is) means "bloody well immutable," so the compiler absolutely knows that no implicitly called function will modify the value of a variable referenced as such, and can optimise accordingly.

This would only happen for 2 reasons. Either an inexperienced or inattentive programmer failing to use their language properly, which, why would we be would about programmers like that? Or intentionally breaking this contract with the compiler, which generally shouldn't be done, but I'm sure there are instances when this is desired. Either way, the compiler DOES assume that the variable is constant, and optimizes it as such. If that breaks your code, well, you're doing it wrong.

childOfTechno wrote:principle #2:
"Being able to prove things about programs is sometimes absolutely required."

That statement is so vague, it actually means nothing. When defining a principle, you generally want to be a explicit as possible. 'Things' and 'sometimes' are not explicit.

childOfTechno wrote:The simple fact is: C/C++ is a pretty poor language if you want to formally prove anything about your code (automatically or otherwise.) This is why programs that absolutely have to work (fly-by-wire systems, control systems for nuclear power plants, etc) are almost never written in C/C++. Really, just about ANY language is better for formal verification methods!

This may be true, but programmers don't generally have to prove anything. They think, plan, implement, test, test, and test some more to be able to give a high likely-hood of success. The larger the project/code-base, the more true this statement becomes. And I will tell you, these systems are either written in ASM or very simple and custom languages that are specific to the task at hand. Java has never, and will never be used for these systems. (Since you seem to be a Java advocate here.)

childOfTechno wrote:A collection of functions with no side effects is amenable to mathematical analysis; ideally you can absolutely say how it will behave for ALL possible input values, not just those you think to test. Just because "it seems to work fine" is usually good enough for your daily coding needs doesn't mean that it's anywhere NEAR good enough for life critical systems.

I'm not sure where "life critical systems" can into this discussion, but its kind of a moot point. Given your temperament, I doubt you will ever work on said systems, and I certainly know I won't either. You also say "ideally you can...", and yes, ideally this would be true. But nothing is ever ideal, so this is also a moot point. Even ignoring that, it is very possible to describe how a function will behave for all inputs in C++. I won't bother giving an example, since it's impossible to prove a negative.

childOfTechno wrote:It's one thing to know how, another to understand why. Functional programming theory is not "academic wank," it's central to some of our deepest insights about formal systems. It's called the Church-Turing thesis for a reason. Let's break it down: Brendan appears to understand Alan Turing's theoretical contribution to computing but completely derides the brilliant insight offered by Alonzo Church. Turing certainly thought the lambda calculus was valuable; I'm not surprised that Rusky (in particular) became irritated by his attitude.

I find it interesting you call Turing's contribution "theoretical" and Church's "brilliant insight". Especially from my point of view (Which I give no guarantees of being correct, or the most well informed) that I have heard of Turing plenty of times, and yet never heard mention of Church...

childOfTechno wrote:The parse tree for a Java program has a lot more constraints on it than a parse tree for a C++ program; the space in which the object (the parse tree) is defined is richer, it has more structure. There are simply more axioms that can be applied that preserve the algorithm the tree expresses, ergo, the compiler can do a much more exhaustive search for possible optimisations.

More constraints means more accurate, but also more restrictive. Java has to have a richer tree just to match C++ in terms of actual applied optimizations. So without some factual numbers, this argument is moot.

childOfTechno wrote:This is why, with modern C++ compilers, it's so very important to write const correct code and avoid trying to manually optimise things that the compiler will deal with. It's better to avoid pointer arithmetic.

Why is it bad that the compiler assumes the programmer knows what they are doing? And why should pointer arithmetic be avoided? Pointer arithmetic, especially when talking domain knowledge, that only the programmer has, into account, can speed up computations immensely.

childOfTechno wrote:It also pays to consider the statistics involved. The probability that a given line of code will be executed is not uniform, indeed it is generally a long tailed distribution, that is, there is a small amount of code that is executed very frequently (the inner parts of loops) and a large amount that is executed infrequently (outer control and dispatch code.)

This is why static analysis is so important. And unfortunately, to date, partially manual static analysis is really required to see a worthwhile improvement.

childOfTechno wrote:This is why run-time bounds checking is nowhere near as expensive as old school C/C++ programmers assume, in 99% of cases the compiler can shunt the bounds check outside of any loops, and with dependent type analysis can often remove it entirely.

Except that "old school C/C++ programmers" that make this assumption also keep code that requires run time checking outside of loops whenever possible. And also, don't forget that just because code is not called frequently right now does not mean that it never will be. Espicially by a well-meaning, but lacking in knowledge future intern.

childOfTechno wrote:Functional programming languages treat functions as first class objects, meaning functions can take functions as arguments and return functions.

So .Net is a functional programming language? (See System.Reflection.MethodInfo and similar classes) And how is a function pointer not treating functions as a first class object? Because it doesn't have type info? So what? Just make a struct that holds that info (although I don't know why you would ever need it...) Or use typed function pointers (Which should be all the type info you need.)

childOfTechno wrote:You clearly did not read my last post. Just In Time compilation (and the overhead implied) does not apply if you are compiling a Java program down to machine code; just a plain ordinary executable file. You'll find that if you compile a Java program with GCJ to run natively, and statically link it, it'll be about the same size as a statically linked C++ program that does the same thing, and run at least as fast.

JIT is just part of the reason Java is slow. And compiling Java like this, you either lose a lot of the features that Java programmers take for granted, or still incur overhead everywhere from run-time checks. It's just the only way to support some of the higher level features Java uses.

childOfTechno wrote:...incredibly personal attack...

Seeing as you have 7 posts, and are attacking a mod like that (or anyone on this forum for that matter) I doubt you will be here for very long...

Posted: **Sat Feb 25, 2012 2:48 am**

I have worked on programs that maintain hospital databases written in java. These are indirectly life critical however they are neither functional programming, nor was java picked for any such reasons. it was picked because there are so many java programmers leaving uni here in the UK. they did not mathematically prove the system was stable, it was restricted by tons of red tape to ensure bugs did not endanger life, for example even restarting a jmx interface had to be prearranged a week in advance, forms filed, and approved by various levels of management.... So yes this is how it is really done

Posted: **Sat Feb 25, 2012 5:23 am**

It's good to know we have a new troll in the house.

Posted: **Sat Feb 25, 2012 5:30 am**

Combuster wrote:It's good to know we have a new troll in the house.

Just doin' my job

This thread was already a cesspit of vitriol when I arrived, when in rome. I'm actually a very nice person

Posted: **Sat Feb 25, 2012 6:31 am**

Could you shut up? Like, you've made yourself look madd stupid enough already. You owe it to yourself to shut up now, son.

Posted: **Sat Feb 25, 2012 8:33 am**

HOW TO BE A LANGUAGE RESEARCHER IN TEN EASY STEPS!

So, you want to be a language researcher do you? Here's how!

Step 1: Finding An Excuse

The first step will be finding some reason for doing research. Unfortunately most of the things that need research were already researched extensively back in the 1960s. Don't give up! Just find anything that some programmers might have trouble with to use an excuse! Don't forget that it doesn't need to be a sane excuse, but only needs to sound plausible to people who might give you a grant (because the entire point of research is to get grants, not to actually improve anything for anyone). Possible silly excuses include things like GOTO, memory management (malloc/free), pointers or state. For the purpose of this exercise I'm going to choose loops.

Step 2: Exaggerate The Problem

Next you have to exaggerate the problem as much as possible, to make your silly excuse sound less silly. Just google around for some statistics like "x% of projects fail" and "out of x lines of code there's an average of y bugs", and pretend that these statistics have something to do with your excuse (even when you know they don't). You could even do a dodgy survey if you like ("We asked the worlds 20 smartest horses if they can think of a reason why loops are needed and they all said "neigh"). I chose loops in the last step, so I could probably invent some rhetoric about the Halting Problem and pretend that lots of programmers everywhere are causing computers to go into infinite loops by accident. Would it be fair to blame global warming on the power consumed by unwanted looping? Of course it would - this is marketing not computer science!

Step 3: Try To Get A Grant

I know it's only step 3 and the whole point of the exercise is to get a grant, but if you can find a sucker early then it can make things a lot easier later. Even if you can't find a sucker at this step, a pre-emptive sales pitch can soften them up, so that later on when they hear your bullshit a second time they think "Hey, I've heard this before so it must be true!".

Step 4: Eliminate The "Problem"

In this step, you eliminate your fictitious problem. It's not complicated, you just rip it out. Instead of having languages with GOTO you have a language without GOTO, instead of having a language with explicit memory management you have a language with none, etc. For my example (loops) it would mean ripping out "for()", "do/while()", "while()", and backward branches (e.g. GOTO where the target is an earlier piece of code - GOTO where the target is later would be fine). Of course you'll notice that this will make programming anything larger than "Hello world" impractical. That's fine - it's not meant to make sense.

Step 5: Try To Get A Grant

I know it's only step 5 and there's more steps, but the sooner you can find a sucker the better. If you actually found a sucker in Step 2, then still do this step (there's no such thing as too many grants/suckers).

Step 6: Determine If You've Exhausted The Suckers

If you've bled all available suckers dry and don't think you can milk them for more $$$, there's no point continuing now. You could return to Step 1 and start the process again, or write a book about how great you are, or just spend a few years relaxing while you spend all the grant money on cheeseburgers. Don't worry about the stupidly broken language you built (everyone else already forgot about it, and it was never important anyway).

Step 7: Hacking Around The Mess You Caused

If you haven't conned enough suckers with your bullshit, you have to increase the believability of your bullshit. The problem is that your new language isn't actually useful for anything because you removed something important; and you need to provide some way of making the language useful again before you can con more suckers. This just means finding a way of adding what you removed back into the language. The hard part is adding it back in a way that looks different, so that the suckers don't realise it's all been a huge scam in the first place.

For my example I removed loops, so we need to add loops. The most obvious way is to misuse recursion. For example, instead of doing this:

Code: Select all

foo() {
    for(i = 0; i < 10; i++) {
        printf("%d\n", i);
    }
}

We'll just expect people to do this:

Code: Select all

foo1() {
    foo2(0);
}

foo2(int i) {
    printf("%d\n", i);
    i++;
    if(i < 10) foo2(i);
}

See, no loops!

Step 8: Hiding your tracks

Now that you've fixed your problem, you need to hide your fix so that people don't realise how stupid it is. The best way of doing this is to make up words to make it hard for people to notice that you're ripping them off. A great example of this is "monad" - it's actually short for "mono nad", which is quite clever given that it's a solution to a problem caused by removing something important.

For my example, I can't just call it recursion because that doesn't confuse people enough. Instead I'm going to call it "auto-reiteration". It doesn't really make sense to replace loops with something called "auto-reiteration" but that doesn't matter at all.

This is only the beginning of hiding your tracks though. You need to make source code look less familiar to programmers too. For my example, I'm going to invent an "auto-reiteration operator". The '@' character isn't used in C, so I'll use that for my new "auto-reiteration operator". The "for(i = 0; i < 10; i++)" example above would become:

Code: Select all

foo1() {
    foo2(0);
}

foo2(int i) {
    printf("%d\n", i);
    i++;
    @(i): i < 10
}

Notice how I put the arguments on the left and the condition on the right to make it harder for people to realise it's recursion? That's what you need to do!

Step 9: Polishing The Turd

If you've gone this far, you need to revise all your previous bullshit and make it more confusing - make up more terminology, use long words, write a research paper saying how excellent your stupid idea is. This is important, because Step 10 is your last chance of scamming cash out of suckers (and you know that you didn't fool enough people earlier).

Step 10: The Final Plea

This is it - the big marketing con. If you don't get a grant here you're stuck, and need to go back to Step 1 or get a real job. Good luck!

Cheers,

Brendan

Posted: **Sat Feb 25, 2012 9:04 am**

LOL. Great reading. Maybe not so great in the sense of keeping peace on the forum.

Posted: **Sat Feb 25, 2012 9:08 am**

Lol someone's got an axe to grind against some academics

but I laughed...

Posted: **Sun Feb 26, 2012 5:29 am**

Brendan, you're last post just gives the idea that you're completely oblivious to the gains of fundamental research (most of what you write can be transposed one to one to every other field of fundamental research out there) combined with a complete lack of respect.

Different languages, and especially those "limited" languages you refer to, give different insights into how code performs it's job. This in turn leads to different optimizations a compiler might use. In a lazy purely functional language it can use a lot more equational reasoning, and optimize memoization on it's own, instead of being unable to do it on the premise of being unable to prove that a function is non-mutable. The lessons learned from each of these languages helps both compiler makers create compilers that are capable of better optimizations (SSA form anyone) and may help programmers look at problems from multiple angles.

An example:
Consider the problem of having two strings (list of elements), and we want to find the longest common subsequence (common problem in generating of diffs). For making the code easier to work on (this won't change the problem significantly) let's say we just wan't to find the length of this subsequence.

We start with the following two programs, both of which are almost literal translations of the definition of the longest common subsequence:

Code: Select all

int lcs(char *a, char *b)
{
	// If one or the other is empty
	//  their lcs is the empty string
	//  which has length 0
	if (*a == 0 || *b == 0)
		return 0
	
	// If they match the lcs is the matching
	//  character plus the lcs of the
	//  remaining string, so length
	//  1 + remaining string
	if (*a == *b)
		return 1 + lcs(a+1, b+1);
	
	// What is the length if we ignore the
	//  first character of a
	int ignA = lcs(a+1, b);
	// What is the length if we ignore the
	//  first character of b
	int ignB = lcs(a, b+1);
	
	// Return the maximum of the previous two
	if (ignA > ignB)
		return ignA;
	else
		return ignB;
}

And in haskel:

Code: Select all

-- Empty strings dont have a common  substring with any string
lcs [] b = 0
lcs b [] = 0
-- The strings have a common head, then length is 1 + length of
--  the lcs of their tails
lcs [a:as] [a:bs] = 1 + lcs as bs
-- The strings dont have a common head, ignore the most head
--  which gives the highest result
lcs [a:as] [b:bs] = max (lcs a:as bs) (lcs as b:bs)

One of the first differences notable here is the fact that in the haskell version there is no explicit type definition. This is because haskell will deduce for us what the type of the function is, which is already quite usefull. The other thing is is that the C version doesn't allow the compiler much optimizations. It will remove a tail call in situation 1 but that's about it.

The haskell version on the other hand allows the compiler to do something very very usefull, it allows it to deduce that it is actually usefull to do memoization on the lcs function. This small change does do a lot to the performance of the program, it changes it's runtime from O(2^n) to O(n^2). It also can optimize the program quite easily to use multiple threads, as the different calls to lcs in the last line are trivialy independent. The fact is that these changes are made possible purely because of the fact that there is no mutability. All of these optimizations can be done in the C version, but the programmer has to implement them by hand, which takes both time and introduces aditional sources of errors.

That said, there are enough situations where the advantages of being able to do more and different optimizations with the compiler do not outweigh the disadvantages of having to work with immutable data, but that only illustrate that one should always think about which language is the right tool for the job at hand.

That said brendan, your posts in this thread do not give the impression that you have spend any decent ammount of time with languages other than C/C++. Whilst this is your choice, it might be refreshing to try and use some other languages, i would suggest something like haskell or lisp, and something like scheme or erlang. These are languages structured in radically different ways to C/C++ type languages, and working with them might teach new methods of approaching problems. If you've tried them and you felt they didn't work for you that's fine, but at the moment you give the impression that you haven't used them at all.'

EDIT: replaced all occurences of longest common substring with longest common subsequence, as that was what I intended to say

Posted: **Sun Feb 26, 2012 5:42 am**

brendan wrote:(elaborate joke that doubles as bait)

bubach's hypothesis wrote:Maybe not so great in the sense of keeping peace on the forum.

davidv1992 wrote:(bite)

Academics would say that qualifies as being empirically proven.

OSDev.org

Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)

Re: Functional Programming (was Pitfalls of lacking a MMU)