Some very thoughtful analysis clearly went into this. It's well written up with explanations that hit the right balance of having the key technical details but focusing on the big picture of how to make applications run better under Linux. As a casual follower of kernel development, I now understand far more of the trade-off than I used to.
I always think that tests and write-ups like this are a great way that people can contribute to Linux development without having to hack the kernel directly. There's no substitute for a thorough testing to help you improve your designs and theories.
I've always seen "interesting" as distinct from "novel".
Yes, we all like to discover something new and jump on the latest bandwagon but it's a shame that the endless quest for novelty often obscures what is fundamentally important.
Until people (wider population, not just Slashdot) actually hear and understand Stallman's message I think he's perfectly right to continue sending it out.
The point about the random factor is that is doesn't matter what it is. Even if it were -3 as you mention, then it is *still* worth implementing Kyoto as you get a net result of -1 which is better than +2. All this is under the stated assumption that a degree less temperature is good of course.
Naturally I agree that this is a simplification, all the equations are seriously nonlinear, and extra warming might therefore be beneficial at some points on the curve.
My whole point was that the argument that combating global warming is unnecessary because other factors affect global temperature is invalid because you can find a simple counterexample.
We need more information on this issue before we can come to a definitive answer, in particular whether the global climate is self-correcting or potentially unstable. Given the risks involved, I actually think we're mad not to take more precautionary steps right now.
This argument really annoys me. Of course human activities are a partial effect. The climate is a very complex system.
But it's rubbish to use this as an argument (as many have tried to do) that the human impact is therefore less important. If anything, it just means that the research is more complex and requires more resources, and we need to live with wide error bars on our estimates.
Thought experiment to illustrate this point:
Assume that each degree increase in temperature is equally "bad". Imagine that the human impact of "current course" is +5 and "Kyoto targets" is +2.
Suppose the cost of a one degree increase is X, and the cost of implementing Kyoto targets is Y. Then the right course of action is to implement Kyoto if 3X is greater than Y.
Then imagine that there is a random factor R that varies between +N and -N degrees.
You now decide to implement Kyoto if 3X+RX is greater than Y+RX. I.e. the decision you should make is exactly the same. Note that the size of the random fluctuation is irrelevant in determining the correct decision. Hence using the existence of random flucation as an argument to do nothing is completely wrong.
The real model is of course more complex, non-linear etc. But the principle still holds - the key issue is to focus on the relative costs and benefits of the alternate approaches and argue around these, not some spurious waffle that fundamentally amounts to "it's been OK before so it will be OK in the future".
If you have a just cause, and no other way to obtain your goals, e.g. through being denied access to appropriate power or influence, then you either have to resort to violence or give up.
That applies equally to individuals, groups and nations. Notice that I'm not advocating violence at all. Just pointing out that it sometimes is necessary and even "The Right Thing".
The biggest danger of course is the stifling of debate and freedoms to the extent that resort to violence occurs. Alarmingly, this is a growing trend in the world today. I confidently predict an upswing in violence as a result.
Sure 128-bits is useful for SIMD, but of course you don't need a 128-bit chip to do this.
A few specialised 128-bit instructions don't come anywhere near having the full 128-bit addressing and general purpose registers that a true 128-bit chip would use.
I'm not convinced we'll ever get to a true 128-bit architecture except for research / novelty value. You won't need a 128-bit address space until long after we've done away with digital computers, and getting more performance will probably come from chaining lots of 16/32/64 bit chips together rather than making a single big one.
Not true. If you give the task a very low priority, it will only use cycles that are truly "spare" on most modern multitaking OSes.
When the user does anything interactive, the task will just get shoved to the back of the queue and won't get any cycles until the user had finished whatever they are doing. The user won't notice a thing.
Or.... you can subdivide the 128-bit pointer into two 64-bit chinks. Use one as the primary pointer, like you say we don't need 128-bit addressing for a while yet. And then use the *second* 64-bit pointer to implement some memory management technique. Rather like the car and cdr parts of a cons cell in LISP, or something like that.
If you could implement garbage collection in the hardware, the performance of complex systems would rocket. Could also be a tremendous boon to things like functional programming languages.
128-bit chips might just be able to facilitate this. Don't knock it 'till you've tried it. I certainly look forward to having a play with one in 10-15 years time.
Theoretically, you're right, and that's how it should work.
However, that's not to say that there won't be some subtle and ingenious way to escape the sandbox, and given the complexity of.NET I'd say you have to accept that as a possibility. So it's probably harsh to say that it's all FUD given that the technology is as yet unproven.
The existing VMs being developed are all well and good, but the whole point of Mono/dotGNU is to enable compatability with the.NET universe which is going to be very big, RSN.
And that doesn't just mean source portability - it means the ability to hook into the infrastructure, to share remote objects, execute mobile IL code and participate in.NET-based networks. If you can do that, open source has the potential to break into MS dominated areas. If not, then you can forget it for another ten years.
And it also means skills portability - a good.NET programmer may well become an extremely valuable open source contributor if they can develop open source.NET components for Mono etc. You don't want to exclude these people from the OS community. A Perl VM won't appeal to these folks, they will want to use their favourite tools which means C# and MSIL.
Basically, I think Mono/dotGNU is the best shot that the open source world has of breaking into MS-dominated areas. Aren't we meant to be *for* open standards and compatibility?.NET is a good technology, so let's use it.
The only risk is the tricks that MS might pull to break the standard. But this is tough - the.NET framework is much more transparent than the Windows APIs, so they can't get away with so much undocumented stuff, and it would be readily apparent if they did. Trying to lock up the standards is bad for them both in PR and antitrust terms, plus there's still a good few countries where software patents don't exist. Their only other route is to try and out-code us and implement features beyond the capability of the open source movement, but I think that is a race that most guys here would relish.....
And lets face it, even if they *did* manage to diverge the standard and ensure that Windows.NET programs couldn't be run on Linux unmodified, then we would still have a great development framework, access to.NET coding skills in the marketplace and a bunch of tools that would benefit the open source movement. Still not a bad deal.
You can have O(f(n)) where f(n) is pretty much any function of n.
Classifying algorithms this way is *extremely* useful for working out what will give good real-world performance.
In general, you want to stick to O(1) or O(log n) to have performance that scales in a reasonably effective way.
Quite a lot of algorithms are O(n) which is OK for small values of n but can get nasty when n becomes large. Inserting a value into a linked list is a typical O(n) algorithm - OK for small lists, bad for long ones as you have to run down the list to find the correct insertion point. (Tchnically you only have to go halfway down the list on average, which would make it O(0.5n), but by convention and for practicality purposes the notation drops and constant factors).
A large proportion of processor bottlenecks are due to getting stuck in O(n^2) or O(n.log n) tasks. Sorting algorithms tend to fall into this category, which explains why they are often slow and/or processor hungry.
Higher polynomial orders such as O(n^4) etc are possible, but generally less common. Sometimes writing a sort algorithm really badly will get you into this territory however:-)
Then there are the *really evil* algorithms that behave like O(2^n) or O(n!). These rapidly become intractable as n grows. Good examples would be the exhastive search of soloutions for the travelling salesman problem, or an exhaustive search of the tree of moves for a game like chess. When faced with this kind of problem, you are basically forced to either limit yourself to small values of n or choose an "approximate" algorithm, such as accepting the best solution found after a timeout period.
Hey I'm not an expert on Amiga OS internals but IIRC it had pre-emptive *multi-tasking* which is very different from a preemptible kernel.
The difference is in what gets preempted - in pre-emptive multitasking it is just user-mode programs that get interrupted, wheras with the pre-emptible kernel high priority tasks can interrupt the kernel itself.
So did the Amiga have a pre-emptible kernel, or was it just preemptive multi-tasking?
Or was it just a low-latency kernel, which gets you most of the benefits of kernel preemption from the point of view of multimedia apps?
If it was just multi-tasking/low latency, that's not exactly a big deal as most OSes have had that for years.....
You can get the same effect by wrapping up code in a bunch of objects and passing them around in a continuation-like manner if you want, but I guess that would be just re-inventing the functional langauge wheel in a very inefficient manner.
They did add some support for tail recursion though.
The JIT compiler performs a verification check on code marked as "safe". If it fails the verification check due to using any unsafe feature, it won't be allowed to run in a safe context.
So no, it's not possible to get round this system by just re-marking the IL code. The only way to run unsafe code is to give it sufficient permission to run.
Regarding why Ask Slashdot, it's mainly because I thought people might have some interesting opinions on the subject. I think I've been proved right. I never expected it to create the answer for me, but it's certainly given me some ideas.
I'm trying to avoid N-squared operations by making the subset of state communicated to each client relatively limited. Theoretically, it should scale linearly, with each player only recieving events from (on average) a small number of adjacent players. In practice there are some complexities, e.g. how to tune the algorithms to be efficient on a subset of a large map, but I think these can be nailed down to N log N at worst. It's a tough one though, since you have to make some pretty substantial architectural investments before you can test it out under load.
I went for C# for the following reasons, no particular order:
1.Something new to learn. It's actually a pretty easy transfer of skills from Java, so I'm having no trouble there.
2.Garbage collection is a godsend for games. Sure, you can hack it into C/C++ but it's a kludge.
3.Good networking tools and language fetaures, such as object graph serialization etc built in. Again, you can code these yourself if you want but I'd rather focus on the game itself. e.g. It's only a couple of lines of code to Serialize and transmit an arbitrary object graph. Stuff like that is a real PITA in C++.
4.The language itself is nice, pretty convenient to program with most of the best bits from Java and Delphi.
5.I'm not doing anything that really needs maximum processor speed, so I can live with a decent JIT compiler like C#. It's a strategy game, so no need for complex physics. The graphics stuff will mostly just be a few calls to native libraries. AI is far more about the algorithm than how much power you chuck at it. Ultimately, network bandwidth is far more likely to be a constraint on what I can do.
Yeah, the VM/CLR is one of the things that really interested me about C#. The language is nice, but the stuff underlying it is even more interesting.
One fetaure I've playing with is the possibility of producing self-modifying code through the IL layer. You can Emit() a bunch of bytecodes and let the JIT compile them on the fly, effectively allowing you to perform some dynamic optimisations. It seems to have potential for things like inner loops that you need to reconfigure dynamically.
Thanks for the interesting perspective on the the people inside the gaming industry. In case you hadn't guessed, I'm outside it;-).
I'm a little surprised things like C# are considered a joke though - I suspect people might not be giving the issue enough thought. There are a lot of advantages to C# (and Java too, for that matter) especially in terms of programmer productivity and flexibility, and I would have thought that these would have won out in the gaming industry sooner or later.
As every good coder knows, performance is 95% about choosing the right algorithm and architecture. I'm willing to bet a well-designed C# program would outperform a badly desined C++ program any day of the week. Ultimately, it's about choosing the right tools for the job, and that's what I *think* I've done on this project.
My suspicion is that once DirectX starts appearing on.NET and the relative advantages of C# become more apparent, we will see several game developers make the switch, and probably do very well out it.
Actually, asking on Slashdot is something to do from the point of view of getting some interesting opinions, not because it's my only (or even first..) port of call.
I certainly didn't need to "Ask Slashdot" in the sense that I have already read a lot of material, written some experimental code and am pretty confident in my ability to get this to work. But occasionally in a big debate some really novel ideas just pop out of the blue, and that was my primary motivation for sending in this story.
Plus, some people might just enjoy talking about an issue which is, after all, supposed to be fun......
Any why not make it a web service;-) ? Sounds like the right tool for certain kinds of jobs, e.g. publishing server metadata.
Slashdot Mirror
Some very thoughtful analysis clearly went into this. It's well written up with explanations that hit the right balance of having the key technical details but focusing on the big picture of how to make applications run better under Linux. As a casual follower of kernel development, I now understand far more of the trade-off than I used to.
I always think that tests and write-ups like this are a great way that people can contribute to Linux development without having to hack the kernel directly. There's no substitute for a thorough testing to help you improve your designs and theories.
Nice job!
Silly argument, but it's something of a distortion to classify murder and terrorist agendas as an "ideal", methinks?
I've always seen "interesting" as distinct from "novel".
Yes, we all like to discover something new and jump on the latest bandwagon but it's a shame that the endless quest for novelty often obscures what is fundamentally important.
Until people (wider population, not just Slashdot) actually hear and understand Stallman's message I think he's perfectly right to continue sending it out.
The point about the random factor is that is doesn't matter what it is. Even if it were -3 as you mention, then it is *still* worth implementing Kyoto as you get a net result of -1 which is better than +2. All this is under the stated assumption that a degree less temperature is good of course.
Naturally I agree that this is a simplification, all the equations are seriously nonlinear, and extra warming might therefore be beneficial at some points on the curve.
My whole point was that the argument that combating global warming is unnecessary because other factors affect global temperature is invalid because you can find a simple counterexample.
We need more information on this issue before we can come to a definitive answer, in particular whether the global climate is self-correcting or potentially unstable. Given the risks involved, I actually think we're mad not to take more precautionary steps right now.
This argument really annoys me. Of course human activities are a partial effect. The climate is a very complex system.
But it's rubbish to use this as an argument (as many have tried to do) that the human impact is therefore less important. If anything, it just means that the research is more complex and requires more resources, and we need to live with wide error bars on our estimates.
Thought experiment to illustrate this point:
Assume that each degree increase in temperature is equally "bad". Imagine that the human impact of "current course" is +5 and "Kyoto targets" is +2.
Suppose the cost of a one degree increase is X, and the cost of implementing Kyoto targets is Y. Then the right course of action is to implement Kyoto if 3X is greater than Y.
Then imagine that there is a random factor R that varies between +N and -N degrees.
You now decide to implement Kyoto if 3X+RX is greater than Y+RX. I.e. the decision you should make is exactly the same. Note that the size of the random fluctuation is irrelevant in determining the correct decision. Hence using the existence of random flucation as an argument to do nothing is completely wrong.
The real model is of course more complex, non-linear etc. But the principle still holds - the key issue is to focus on the relative costs and benefits of the alternate approaches and argue around these, not some spurious waffle that fundamentally amounts to "it's been OK before so it will be OK in the future".
Historically that may be true, but Brits generally use the 1 thousand million definition all the time now.
Statements containing "NEVER" are often wrong.
If you have a just cause, and no other way to obtain your goals, e.g. through being denied access to appropriate power or influence, then you either have to resort to violence or give up.
That applies equally to individuals, groups and nations. Notice that I'm not advocating violence at all. Just pointing out that it sometimes is necessary and even "The Right Thing".
The biggest danger of course is the stifling of debate and freedoms to the extent that resort to violence occurs. Alarmingly, this is a growing trend in the world today. I confidently predict an upswing in violence as a result.
Sure 128-bits is useful for SIMD, but of course you don't need a 128-bit chip to do this.
A few specialised 128-bit instructions don't come anywhere near having the full 128-bit addressing and general purpose registers that a true 128-bit chip would use.
I'm not convinced we'll ever get to a true 128-bit architecture except for research / novelty value. You won't need a 128-bit address space until long after we've done away with digital computers, and getting more performance will probably come from chaining lots of 16/32/64 bit chips together rather than making a single big one.
Not true. If you give the task a very low priority, it will only use cycles that are truly "spare" on most modern multitaking OSes.
When the user does anything interactive, the task will just get shoved to the back of the queue and won't get any cycles until the user had finished whatever they are doing. The user won't notice a thing.
Or.... you can subdivide the 128-bit pointer into two 64-bit chinks. Use one as the primary pointer, like you say we don't need 128-bit addressing for a while yet. And then use the *second* 64-bit pointer to implement some memory management technique. Rather like the car and cdr parts of a cons cell in LISP, or something like that.
If you could implement garbage collection in the hardware, the performance of complex systems would rocket. Could also be a tremendous boon to things like functional programming languages.
128-bit chips might just be able to facilitate this. Don't knock it 'till you've tried it. I certainly look forward to having a play with one in 10-15 years time.
OK, so it's kind of "preemptible everything".
Never knew that - thanks for the info!
I'd much rather that BT won.
It would be such a farcical result that the whole software/business mathod patent mess will be exposed for the shambles that it it is.
Then we can scrap the aforementioned dumb laws and get down to building an information economy built around competition rather than lawsuits....
Theoretically, you're right, and that's how it should work.
.NET I'd say you have to accept that as a possibility. So it's probably harsh to say that it's all FUD given that the technology is as yet unproven.
However, that's not to say that there won't be some subtle and ingenious way to escape the sandbox, and given the complexity of
The existing VMs being developed are all well and good, but the whole point of Mono/dotGNU is to enable compatability with the .NET universe which is going to be very big, RSN.
.NET-based networks. If you can do that, open source has the potential to break into MS dominated areas. If not, then you can forget it for another ten years.
.NET programmer may well become an extremely valuable open source contributor if they can develop open source .NET components for Mono etc. You don't want to exclude these people from the OS community. A Perl VM won't appeal to these folks, they will want to use their favourite tools which means C# and MSIL.
.NET is a good technology, so let's use it.
.NET framework is much more transparent than the Windows APIs, so they can't get away with so much undocumented stuff, and it would be readily apparent if they did. Trying to lock up the standards is bad for them both in PR and antitrust terms, plus there's still a good few countries where software patents don't exist. Their only other route is to try and out-code us and implement features beyond the capability of the open source movement, but I think that is a race that most guys here would relish.....
.NET programs couldn't be run on Linux unmodified, then we would still have a great development framework, access to .NET coding skills in the marketplace and a bunch of tools that would benefit the open source movement. Still not a bad deal.
And that doesn't just mean source portability - it means the ability to hook into the infrastructure, to share remote objects, execute mobile IL code and participate in
And it also means skills portability - a good
Basically, I think Mono/dotGNU is the best shot that the open source world has of breaking into MS-dominated areas. Aren't we meant to be *for* open standards and compatibility?
The only risk is the tricks that MS might pull to break the standard. But this is tough - the
And lets face it, even if they *did* manage to diverge the standard and ensure that Windows
You can have O(f(n)) where f(n) is pretty much any function of n.
:-)
Classifying algorithms this way is *extremely* useful for working out what will give good real-world performance.
In general, you want to stick to O(1) or O(log n) to have performance that scales in a reasonably effective way.
Quite a lot of algorithms are O(n) which is OK for small values of n but can get nasty when n becomes large. Inserting a value into a linked list is a typical O(n) algorithm - OK for small lists, bad for long ones as you have to run down the list to find the correct insertion point. (Tchnically you only have to go halfway down the list on average, which would make it O(0.5n), but by convention and for practicality purposes the notation drops and constant factors).
A large proportion of processor bottlenecks are due to getting stuck in O(n^2) or O(n.log n) tasks. Sorting algorithms tend to fall into this category, which explains why they are often slow and/or processor hungry.
Higher polynomial orders such as O(n^4) etc are possible, but generally less common. Sometimes writing a sort algorithm really badly will get you into this territory however
Then there are the *really evil* algorithms that behave like O(2^n) or O(n!). These rapidly become intractable as n grows. Good examples would be the exhastive search of soloutions for the travelling salesman problem, or an exhaustive search of the tree of moves for a game like chess. When faced with this kind of problem, you are basically forced to either limit yourself to small values of n or choose an "approximate" algorithm, such as accepting the best solution found after a timeout period.
Hey I'm not an expert on Amiga OS internals but IIRC it had pre-emptive *multi-tasking* which is very different from a preemptible kernel.
The difference is in what gets preempted - in pre-emptive multitasking it is just user-mode programs that get interrupted, wheras with the pre-emptible kernel high priority tasks can interrupt the kernel itself.
So did the Amiga have a pre-emptible kernel, or was it just preemptive multi-tasking?
Or was it just a low-latency kernel, which gets you most of the benefits of kernel preemption from the point of view of multimedia apps?
If it was just multi-tasking/low latency, that's not exactly a big deal as most OSes have had that for years.....
Nope. Not in a first-class sense anyway.
You can get the same effect by wrapping up code in a bunch of objects and passing them around in a continuation-like manner if you want, but I guess that would be just re-inventing the functional langauge wheel in a very inefficient manner.
They did add some support for tail recursion though.
The JIT compiler performs a verification check on code marked as "safe". If it fails the verification check due to using any unsafe feature, it won't be allowed to run in a safe context.
So no, it's not possible to get round this system by just re-marking the IL code. The only way to run unsafe code is to give it sufficient permission to run.
Having used .NET, one thing is true and that is that it *will* increase your productivity. C# is a solid language. It's looking to be a great plaform.
.NET. It will still be a great tool to have on Linux.
If fact, I don't think it even matters if Mono fails to achieve full compatibility with
Unless you program in a functional language of course. In which case you have nothing to worry about, since everyone else is still years behind....
In which case someone in a country where software patents aren't recognised might be interested in taking up maintainership.
Great example of how patents restrict innovation and competition BTW.....
Thanks for the interesting comments.
Regarding why Ask Slashdot, it's mainly because I thought people might have some interesting opinions on the subject. I think I've been proved right. I never expected it to create the answer for me, but it's certainly given me some ideas.
I'm trying to avoid N-squared operations by making the subset of state communicated to each client relatively limited. Theoretically, it should scale linearly, with each player only recieving events from (on average) a small number of adjacent players. In practice there are some complexities, e.g. how to tune the algorithms to be efficient on a subset of a large map, but I think these can be nailed down to N log N at worst. It's a tough one though, since you have to make some pretty substantial architectural investments before you can test it out under load.
I went for C# for the following reasons, no particular order:
1.Something new to learn. It's actually a pretty easy transfer of skills from Java, so I'm having no trouble there.
2.Garbage collection is a godsend for games. Sure, you can hack it into C/C++ but it's a kludge.
3.Good networking tools and language fetaures, such as object graph serialization etc built in. Again, you can code these yourself if you want but I'd rather focus on the game itself. e.g. It's only a couple of lines of code to Serialize and transmit an arbitrary object graph. Stuff like that is a real PITA in C++.
4.The language itself is nice, pretty convenient to program with most of the best bits from Java and Delphi.
5.I'm not doing anything that really needs maximum processor speed, so I can live with a decent JIT compiler like C#. It's a strategy game, so no need for complex physics. The graphics stuff will mostly just be a few calls to native libraries. AI is far more about the algorithm than how much power you chuck at it. Ultimately, network bandwidth is far more likely to be a constraint on what I can do.
Yeah, the VM/CLR is one of the things that really interested me about C#. The language is nice, but the stuff underlying it is even more interesting.
One fetaure I've playing with is the possibility of producing self-modifying code through the IL layer. You can Emit() a bunch of bytecodes and let the JIT compile them on the fly, effectively allowing you to perform some dynamic optimisations. It seems to have potential for things like inner loops that you need to reconfigure dynamically.
Thanks for the interesting perspective on the the people inside the gaming industry. In case you hadn't guessed, I'm outside it ;-).
.NET and the relative advantages of C# become more apparent, we will see several game developers make the switch, and probably do very well out it.
I'm a little surprised things like C# are considered a joke though - I suspect people might not be giving the issue enough thought. There are a lot of advantages to C# (and Java too, for that matter) especially in terms of programmer productivity and flexibility, and I would have thought that these would have won out in the gaming industry sooner or later.
As every good coder knows, performance is 95% about choosing the right algorithm and architecture. I'm willing to bet a well-designed C# program would outperform a badly desined C++ program any day of the week. Ultimately, it's about choosing the right tools for the job, and that's what I *think* I've done on this project.
My suspicion is that once DirectX starts appearing on
Actually, asking on Slashdot is something to do from the point of view of getting some interesting opinions, not because it's my only (or even first..) port of call.
;-) ? Sounds like the right tool for certain kinds of jobs, e.g. publishing server metadata.
I certainly didn't need to "Ask Slashdot" in the sense that I have already read a lot of material, written some experimental code and am pretty confident in my ability to get this to work. But occasionally in a big debate some really novel ideas just pop out of the blue, and that was my primary motivation for sending in this story.
Plus, some people might just enjoy talking about an issue which is, after all, supposed to be fun......
Any why not make it a web service
Yep - that's about how long I've had with C# and I'd say I'm quite far up the learning curve.
Most similarities with Java, although I have also noticed some nice Delphi-isms like properties.
Don't think picking up C# is the challenge in this case - it's much more about coming up with a decent network architecture.