There is a pretty easy way to pick out the median in linear time. But the deterministic quicksort goes like this: divide array into five-element lists, find the median of each of those lists == O(n) time, recurse
But the only advantage quicksort has over, say, heapsort, is a better K. They are both O(NlogN). Doesn't this affect K?
Linux isn't going to be very commercially viable unless the "idiots" can set it up and use it.
Well, you know, I'm an idiot too, before I've had my first cup of coffee and any time I'm not paying close attention:-) Also, there are always parts of the system I've never delved in to and where I really do like to be held by the hand, even if the second time I do it I do it the manly way. The thing I like about linuxconf is, it really does tell you a lot about how the system is structured, and how it goes about doing the stuff it does. That's wonderful: linuxconf is a learning tool, for newbies, admins and hackers alike.
When creating these new tools let's never forget that they're not just for newbies - they're going to be used by professionals as well, so let's design them according.
Quicksort is not that great of an algorithm. At least the normal quicksort...it can be as bad as insertion sort in some cases. Deterministic quicksort is as good as you can get...
Are you sure about that? Last time I looked into this (many years ago) I looked at Knuth's analysis in the Art of Computer Programming where he convinces himself that there is no efficient algorithm for picking medians such that the worst case does not degenerate to O(n^2), albeit with vanishingly low probability. It was enough to convince me to use some other algorithm in any system where the worst case result could possibly be harmful. Note that merge sort has the same performance as qucksort, though it operates on lists, not arrays.
And before you call that a knee-jerk reaction, consdier that the original purpose of the patent law was to encourage inventors ro disseminate their techniques widely instead of keeping them as trade secrets. We never had that problem in mathemetics, computers science or any number of other scientifici disciplines to which patent law is now being implied. In other words, in these areas, the law is fixing something that wasn't broken.
In fact, the patent laws are doing a lot of damage to society in general. As we all know, there is more than one way to get rich, and trying to get rich by hording the rights to mathematical and scientific techniques that are rightfully the property of the humanity is just plain wrong.
The patent system has become a mockery of its former self, has outlived its usefulness, and now needs to undergo some major surgery. We must modify it so that it distinguish between intellectual property belonging to humanity in general, and intellectual property that has been genuinely created, and thus can be owned, for a time, by an individual. If I "find" your wallet on the ground, does that make it mine? No, and if I take it I'm a thief. A government that would enact a law to make finders of wallets the rightful new owners of said wallets would only be acting in the interests of thieves, and it's actions would have to be corrected by right-thinking citizens. If I "find" a mathematical truth, it's not mine either - it belongs to the world, and I'll get my reward by being respected as it's discoverer, not hated as the man who sat on the thing, milked it, and kept it from being widely used and benefiting society for 17 years.
For anybody running laptops, the big deal with the more recent 2.3 kernels is the built-in PCMCIA support. In the 2.2 series if you want to configure your kernel at all you have to get not only the kernel source but the (big) PCMCIA patch and compile it separately, and there's a somewhat intimidating series of questions you have to answer in the config. It's anything but seamless, and you have to mess around with it every time you upgrade the kernel. In 2.3 it's just one more checkbox item in make xconfig.:-) Progress marches on.
The floodgates are pretty much opening right now, for "big boy" games for Linux, and *everybody* will soon be jumping on. When Electronic Arts jumps in... well, it's going to happen any time./ Chances are they're working on a few ports already just to assess the technology.
That's coming nicely I'd say. Now we have to start thinking beyond that: lots of people aren't going to put Windows away for good until their children can play games, especially educational games on dad's computer. That's the new frontier.
recall that the only way to efficiently use non-blocking I/O is to select the file descriptors to wait on. This is tricky enough that making threading easier was probably the right thing to do.
Providing an efficient, easy means of handling non-blocking I/O is no more difficult than handling any other kind of ansychonous event, such as a mouse click. The user program can register a handler, and each time an I/O is done the VM calls the handler. I don't see that as being hard, either in implementation or usage.
Even assuming that on a thread switch, since you're dealing with the same data as the previous thread was using, the TLB and code/data caches remain useful (on a process switch in general they don't, and refilling the caches is very expensive), you still have to store a whole bunch of stuff to memory for the old thread and bring a whole bunch of stuff of stuff out of memory for the new thread. And you've got to leave userland for a bit to do that. Slow slow slow slow.
Why? I don't see that. To switch threads in user space you push all the registers onto the stack, save the stack pointer, load the stack pointer of the next thread and pop its registers from the stack. It's just a few cycles, maybe 20 or so. If your thread is using floating point you've got more work to do - you have to save the FP context if another task was using it and load the FP context of the new thread. This isn't expensive because it doesn't happen often. (You do need to do some fancy dancing to detect automatically which threads are using FP and which aren't) You don't have to enter the kernel anywhere in this process, and that's a huge win. To make the user space task switches happen you sprinkle calls to a yield() function throughout the code, and at I/O points. This just doesn't eat much CPU time, compared to the enormous, odious cost of crossing into the kernel, killing the cache at a cost of several hundred cycles. And again when you cross back out. For Java, this approach is ideal because the VM has complete control of the code that gets executed - at load time it can insert the required yields as it sees fit.
I really can't think of enough good things to say about IBM's open-source efforts. They're spending real money, and throwing good people at it. IBM has always known what quality control is about, and they're bringing that to the party. They're putting in whole products like Jikes and (more importantly from my point of the view) the Jikes parser generator. They're doing it without taking a holier-than-thou attitude, and without "cute" licenses like the SCSL. It's really hard to believe the old T.Rex of yore has turned cuddly.
Because if they did they would at least have made a token effort to clean up the form, after the flood of negative comments it inspired last time. This time, I just went into the site and checked out the form first before looking any further. Hasn't changed much, if at all. Sorry, I haven't got time for that. There are about 36 mandatory fields - it's just too much, and then you're only getting a chance being picked. Plus, I'm just a little reluctant to give them my telephone number. At least they didn't ask for my credit card.
Corel's goal should be to qualify their beta testers without annoying people. They certainly haven't achieved that. Now, I'd be most impressed if somebody from Corel showed up on the thread and asked us how the form could be better, since it's obviously widely hated.
In all the reports I've seen so far the 5400 has been described as a "windows chip", and nothing is said about Linux. Naturally I assume that anything that can run Windows can run Linux too.
because the Java language lacks an interface for non-blocking I/O threads are especially necessary in constructing communications intensive applications in Java
Wouldn't it be easier to add an interface for non-blocking I/O to Java??? Err - isn't it supposed to be an inherently multitasking language? Sheesh. This is an excellent example what's wrong with Sun's dog-in-the-manger attitude to the Java spec. "We already defined that, it can't be changed, fix it some other way! No, we're too busy defining new multimedia api's to take a look at it"
They have contributed a lot of Open Source code, and it really should not come as a surprise that they are being cautious about their flagship products.
I agree with this 100%, and I think we ought to excercise some discretion as far a putting a lot of pressure on Corel goes. On the other hand, I'd like to add my argument that if, for example, the wp8 source was released we could fix the crappy MS-Word filters, I think pretty fast too. And exactly how would that hurt sales? I think the basic equation is - sales are not lost to people who download free software. (1) They'll recommend the software to other people, if it's good (and we'll make sure it's good) - most of those people would probably just grab the box for $50 than spend the time downloading it, plus they get a manual and who knows what else - free penquin mouse pad?:-) (2) They probably wouldn't have bought it anyway or (3) they'll be impressed enough to buy the boxed product or (4) recommend it at work. How can you lose?
On our project, we have written XSL to transform our XML data into binary outputs. The stylesheets used ran into tens of thousands of lines!
This is supposed to be good? Something is horribly broken. Perhaps a different tool would be more appropriate? How about a parser generator? (see Jikes)
It's just a trick of course. Does anyone really believe that Gates won't continue to run the show? Really all they're doing is trying to shuffle the deck and say "here, see? Different deck!".
Another way of putting it is they're desperately trying to show that something has changed at Microsoft and that further remedies aren't needed. This is bullshit, and nobody should be fooled by it.
All of you giggling and postulating about Bill Gates being wary of a Microsoft breakup should be aware that he may be laughing all the way to the bank in the near future.
No, he won't, see below
The government might split Microsoft into 3 (or so) entities, but it can't strip Bill Gates of what will be his large ownership in all 3 companies.
The conventional wisdom is that the value of the separated entities will rise higher than the value of the original entity, as happened with the Standard Oil breakup. This is just false. What will happen is the bottom will fall out of the stock price - faced with competition from free software, and no longer having the means of forcibly maintaining the existing monopoly, the Baby Bills revenue can go nowhere but down.
Microsoft's current annualized revenue is about $25 billion (being generous); its market capitalization is about $500 billion. That's a 20 times multiple on earnings whereas a mature, stable business with stable revenue would normally have something more like 2x. Microsoft's valuation is based on one thing: expectation of continued exponential earnings growth. That just ain't gonna happen. In fact, the baby Bills are going to have to dance like crazy just to avoid having their earnings decimated by the need to compete with free software and unshackled industry competitors. In short: end of exponentional earnings growth == goodbye 20x multiple on revenue. Hello 2x multiple, and maybe worse. Shareholders aren't so clueless that they can't see that as well as anybody else can; neither are the professional short sellers.
Hooboy, that means Microsoft's stock will fall like a lead balloon.
I mean, look what happens when cell phones fall into the hands of *Drug Dealers*. Plus, many men are using telephones with the intention of *getting women to have sex with them*. People *swear* on telephones, and talk about *bad things they shouldn't. Telephones are polluting the minds of our sons and daughters, something has to be done.
While none of this evidence is directly usable for any other action I can think of, it could (and would) be entered into evidence as part of the process of "establishing a pattern of behavior" in any similar case against Microsoft. Not that I can think of such a case at the moment...
Oh, I can. Does the phrase "Dos isn't done until Lotus won't run" mean anything to you? I supposed IBM might just be a little interested in the way things are going. What do you think the chances are that noone else had problems this way? Why would Apple not now launch its own suit over apparent breakages of, hmm, Quicktime I think it was?
Microsoft's been on good behavior the last couple of years...
As far as anyone other than Microsoft and Caldera is concerned, this case just went "poof" and disappeared.
IANAL, but I don't think that's correct. The facts are still there, and Caldera could be subpoened to testify in any other case to which the evidence might be relevant, to help establish a pattern of condut. That would include anybody else with a similar axe to grind with Microsoft, or could even include the government since the issues in Caldera's case weren't even touched on in the current anti-trust action. If somebody hires David Boise to go after Microsoft with their own complaint, do you think he'll ignore Caldera's evidence and just let it sit there?
My response is, what the HELL? we settled over that!!! Especially when I ruminate over the fact that it only appears in a single beta, never saw a shipping customer, doesn't mention DR-DOS, AND allows you to continue unhindered
I remember a chain of events that resulted in an expose in the pages of Doctor Dobbs re code that was encrypted in shipping versions of Win3.1, having to do with detection of Non-MS Dos. I remember Brad Chase blandly and patronizingly denying that anyone should read anyone into this. I don't really think anyone bought that line. Does anyone have more details on this?
Where there's smoke there's fire. When you see 1 roach, you know there's 100 more you didn't see. I don't think that was the end of it.
hell, I think the X video driver that whoever wrote for the Neomagic in the Dell is better than the Windows driver.
Mine (on a Viao) suffers from scramblitus when the destination of full width bit block move is exactly the edge of the screen. Does yours? I've been meaning to track this down - surely I can't be the only one. Is it a hardware, firmware or driver bug? No clue yet.
Slashdot Mirror
There is a pretty easy way to pick out the median in linear time. But the deterministic quicksort goes like this: divide array into five-element lists, find the median of each of those lists == O(n) time, recurse
But the only advantage quicksort has over, say, heapsort, is a better K. They are both O(NlogN). Doesn't this affect K?
If Linux offered better performance over NT on most of the things I use it for, then I'd have cause to switch but as it stands Win NT suffices.
:-)
Methinks we very nearly have a convert
Linux isn't going to be very commercially viable unless the "idiots" can set it up and use it.
:-) Also, there are always parts of the system I've never delved in to and where I really do like to be held by the hand, even if the second time I do it I do it the manly way. The thing I like about linuxconf is, it really does tell you a lot about how the system is structured, and how it goes about doing the stuff it does. That's wonderful: linuxconf is a learning tool, for newbies, admins and hackers alike.
Well, you know, I'm an idiot too, before I've had my first cup of coffee and any time I'm not paying close attention
When creating these new tools let's never forget that they're not just for newbies - they're going to be used by professionals as well, so let's design them according.
Quicksort is not that great of an algorithm. At least the normal quicksort...it can be as bad as insertion sort in some cases. Deterministic quicksort is as good as you can get...
Are you sure about that? Last time I looked into this (many years ago) I looked at Knuth's analysis in the Art of Computer Programming where he convinces himself that there is no efficient algorithm for picking medians such that the worst case does not degenerate to O(n^2), albeit with vanishingly low probability. It was enough to convince me to use some other algorithm in any system where the worst case result could possibly be harmful. Note that merge sort has the same performance as qucksort, though it operates on lists, not arrays.
And before you call that a knee-jerk reaction, consdier that the original purpose of the patent law was to encourage inventors ro disseminate their techniques widely instead of keeping them as trade secrets. We never had that problem in mathemetics, computers science or any number of other scientifici disciplines to which patent law is now being implied. In other words, in these areas, the law is fixing something that wasn't broken.
In fact, the patent laws are doing a lot of damage to society in general. As we all know, there is more than one way to get rich, and trying to get rich by hording the rights to mathematical and scientific techniques that are rightfully the property of the humanity is just plain wrong.
The patent system has become a mockery of its former self, has outlived its usefulness, and now needs to undergo some major surgery. We must modify it so that it distinguish between intellectual property belonging to humanity in general, and intellectual property that has been genuinely created, and thus can be owned, for a time, by an individual. If I "find" your wallet on the ground, does that make it mine? No, and if I take it I'm a thief. A government that would enact a law to make finders of wallets the rightful new owners of said wallets would only be acting in the interests of thieves, and it's actions would have to be corrected by right-thinking citizens. If I "find" a mathematical truth, it's not mine either - it belongs to the world, and I'll get my reward by being respected as it's discoverer, not hated as the man who sat on the thing, milked it, and kept it from being widely used and benefiting society for 17 years.
For anybody running laptops, the big deal with the more recent 2.3 kernels is the built-in PCMCIA support. In the 2.2 series if you want to configure your kernel at all you have to get not only the kernel source but the (big) PCMCIA patch and compile it separately, and there's a somewhat intimidating series of questions you have to answer in the config. It's anything but seamless, and you have to mess around with it every time you upgrade the kernel. In 2.3 it's just one more checkbox item in make xconfig. :-) Progress marches on.
The floodgates are pretty much opening right now, for "big boy" games for Linux, and *everybody* will soon be jumping on. When Electronic Arts jumps in... well, it's going to happen any time./ Chances are they're working on a few ports already just to assess the technology.
That's coming nicely I'd say. Now we have to start thinking beyond that: lots of people aren't going to put Windows away for good until their children can play games, especially educational games on dad's computer. That's the new frontier.
recall that the only way to efficiently use non-blocking I/O is to select the file descriptors to wait on. This is tricky enough that making threading easier was probably the right thing to do.
Providing an efficient, easy means of handling non-blocking I/O is no more difficult than handling any other kind of ansychonous event, such as a mouse click. The user program can register a handler, and each time an I/O is done the VM calls the handler. I don't see that as being hard, either in implementation or usage.
Even assuming that on a thread switch, since you're dealing with the same data as the previous thread was using, the TLB and code/data caches remain useful (on a process switch in general they don't, and refilling the caches is very expensive), you still have to store a whole bunch of stuff to memory for the old thread and bring a whole bunch of stuff of stuff out of memory for the new thread. And you've got to leave userland for a bit to do that. Slow slow slow slow.
Why? I don't see that. To switch threads in user space you push all the registers onto the stack, save the stack pointer, load the stack pointer of the next thread and pop its registers from the stack. It's just a few cycles, maybe 20 or so. If your thread is using floating point you've got more work to do - you have to save the FP context if another task was using it and load the FP context of the new thread. This isn't expensive because it doesn't happen often. (You do need to do some fancy dancing to detect automatically which threads are using FP and which aren't) You don't have to enter the kernel anywhere in this process, and that's a huge win. To make the user space task switches happen you sprinkle calls to a yield() function throughout the code, and at I/O points. This just doesn't eat much CPU time, compared to the enormous, odious cost of crossing into the kernel, killing the cache at a cost of several hundred cycles. And again when you cross back out. For Java, this approach is ideal because the VM has complete control of the code that gets executed - at load time it can insert the required yields as it sees fit.
I really can't think of enough good things to say about IBM's open-source efforts. They're spending real money, and throwing good people at it. IBM has always known what quality control is about, and they're bringing that to the party. They're putting in whole products like Jikes and (more importantly from my point of the view) the Jikes parser generator. They're doing it without taking a holier-than-thou attitude, and without "cute" licenses like the SCSL. It's really hard to believe the old T.Rex of yore has turned cuddly.
Because if they did they would at least have made a token effort to clean up the form, after the flood of negative comments it inspired last time. This time, I just went into the site and checked out the form first before looking any further. Hasn't changed much, if at all. Sorry, I haven't got time for that. There are about 36 mandatory fields - it's just too much, and then you're only getting a chance being picked. Plus, I'm just a little reluctant to give them my telephone number. At least they didn't ask for my credit card.
Corel's goal should be to qualify their beta testers without annoying people. They certainly haven't achieved that. Now, I'd be most impressed if somebody from Corel showed up on the thread and asked us how the form could be better, since it's obviously widely hated.
In all the reports I've seen so far the 5400 has been described as a "windows chip", and nothing is said about Linux. Naturally I assume that anything that can run Windows can run Linux too.
because the Java language lacks an interface for non-blocking I/O threads are especially necessary in constructing communications intensive applications in Java
Wouldn't it be easier to add an interface for non-blocking I/O to Java??? Err - isn't it supposed to be an inherently multitasking language? Sheesh. This is an excellent example what's wrong with Sun's dog-in-the-manger attitude to the Java spec. "We already defined that, it can't be changed, fix it some other way! No, we're too busy defining new multimedia api's to take a look at it"
They have contributed a lot of Open Source code, and it really should not come as a surprise that they are being cautious about their flagship products.
:-) (2) They probably wouldn't have bought it anyway or (3) they'll be impressed enough to buy the boxed product or (4) recommend it at work. How can you lose?
I agree with this 100%, and I think we ought to excercise some discretion as far a putting a lot of pressure on Corel goes. On the other hand, I'd like to add my argument that if, for example, the wp8 source was released we could fix the crappy MS-Word filters, I think pretty fast too. And exactly how would that hurt sales? I think the basic equation is - sales are not lost to people who download free software. (1) They'll recommend the software to other people, if it's good (and we'll make sure it's good) - most of those people would probably just grab the box for $50 than spend the time downloading it, plus they get a manual and who knows what else - free penquin mouse pad?
On our project, we have written XSL to transform our XML data into binary outputs. The stylesheets used ran into tens of thousands of lines!
This is supposed to be good? Something is horribly broken. Perhaps a different tool would be more appropriate? How about a parser generator? (see Jikes)
Don't you remember CmdrTaco saying in the recnt interview that everytime someone asks about it, he's going to delay the slash release by 24 hrs?
Yes, I perceived that as arrogant and hypocritical, and I wasn't impressed.
Addendum to my own post: I should have said "sales" everywhere I said earnings or revenue.
It's just a trick of course. Does anyone really believe that Gates won't continue to run the show? Really all they're doing is trying to shuffle the deck and say "here, see? Different deck!".
Another way of putting it is they're desperately trying to show that something has changed at Microsoft and that further remedies aren't needed. This is bullshit, and nobody should be fooled by it.
All of you giggling and postulating about Bill Gates being wary of a Microsoft breakup should be aware that he may be laughing all the way to the bank in the near future.
No, he won't, see below
The government might split Microsoft into 3 (or so) entities, but it can't strip Bill Gates of what will be his large ownership in all 3 companies.
The conventional wisdom is that the value of the separated entities will rise higher than the value of the original entity, as happened with the Standard Oil breakup. This is just false. What will happen is the bottom will fall out of the stock price - faced with competition from free software, and no longer having the means of forcibly maintaining the existing monopoly, the Baby Bills revenue can go nowhere but down.
Microsoft's current annualized revenue is about $25 billion (being generous); its market capitalization is about $500 billion. That's a 20 times multiple on earnings whereas a mature, stable business with stable revenue would normally have something more like 2x. Microsoft's valuation is based on one thing: expectation of continued exponential earnings growth. That just ain't gonna happen. In fact, the baby Bills are going to have to dance like crazy just to avoid having their earnings decimated by the need to compete with free software and unshackled industry competitors. In short: end of exponentional earnings growth == goodbye 20x multiple on revenue. Hello 2x multiple, and maybe worse. Shareholders aren't so clueless that they can't see that as well as anybody else can; neither are the professional short sellers.
Hooboy, that means Microsoft's stock will fall like a lead balloon.
I mean, look what happens when cell phones fall into the hands of *Drug Dealers*. Plus, many men are using telephones with the intention of *getting women to have sex with them*. People *swear* on telephones, and talk about *bad things they shouldn't. Telephones are polluting the minds of our sons and daughters, something has to be done.
While none of this evidence is directly usable for any other action I can think of, it could (and would) be entered into evidence as part of the process of "establishing a pattern of behavior" in any similar case against Microsoft. Not that I can think of such a case at the moment...
Oh, I can. Does the phrase "Dos isn't done until Lotus won't run" mean anything to you? I supposed IBM might just be a little interested in the way things are going. What do you think the chances are that noone else had problems this way? Why would Apple not now launch its own suit over apparent breakages of, hmm, Quicktime I think it was?
Microsoft's been on good behavior the last couple of years...
Do you really thing so? Old habits die hard.
As far as anyone other than Microsoft and Caldera is concerned, this case just went "poof" and disappeared.
IANAL, but I don't think that's correct. The facts are still there, and Caldera could be subpoened to testify in any other case to which the evidence might be relevant, to help establish a pattern of condut. That would include anybody else with a similar axe to grind with Microsoft, or could even include the government since the issues in Caldera's case weren't even touched on in the current anti-trust action. If somebody hires David Boise to go after Microsoft with their own complaint, do you think he'll ignore Caldera's evidence and just let it sit there?
My response is, what the HELL? we settled over that!!! Especially when I ruminate over the fact that it only appears in a single beta, never saw a shipping customer, doesn't mention DR-DOS, AND allows you to continue unhindered
I remember a chain of events that resulted in an expose in the pages of Doctor Dobbs re code that was encrypted in shipping versions of Win3.1, having to do with detection of Non-MS Dos. I remember Brad Chase blandly and patronizingly denying that anyone should read anyone into this. I don't really think anyone bought that line. Does anyone have more details on this?
Where there's smoke there's fire. When you see 1 roach, you know there's 100 more you didn't see. I don't think that was the end of it.
I'm going to blow my cover, such as it is, and state flat-out that I'm a Microsoft employee.
That has always been obvious. Just one question: do you use Linux?
hell, I think the X video driver that whoever wrote for the Neomagic in the Dell is better than the Windows driver.
Mine (on a Viao) suffers from scramblitus when the destination of full width bit block move is exactly the edge of the screen. Does yours? I've been meaning to track this down - surely I can't be the only one. Is it a hardware, firmware or driver bug? No clue yet.
It's ****fast**** though.