What I'm discussing is what can and cannot be concluded from big-O asymptotic complexity.
..and what I'm discussing is the reality of rendering engines as they are today and the near future.. you know, like the fucking article and interview.
I thought it was interesting that he said hes spent the last 1.5 years working on raytracers. Carmack is very much a research guy now, not a developer. He pays others to develop.
Yeah, not to mention that with full ray-tracing, as you add more lights to a scene, it increases the overall complexity per pixel per ray bounce linearly as well. That's why doing deferred shading is so nice because it unbuckles the lighting from the rasterization or ray-casting/tracing step and lets you scale up the number of lightings independently with a fixed amount of overhead and linear cost per light for the entire scene, instead of per pixel or per ray or per polygon.
I highlighted the key thing that you overlooked. They are both linear to the number of lights.
Everything you wrote is mathematically accurate, yet the actually interesting thing is exactly how big N has to get.
You know that this very question has been researched, right? I am amazed that you are intent to discuss this issue without having actually done any research in this matter.
You might want to start with this 2005 paper from Intel where they do some performance comparison for both hardware rasterization and software raytracing for various scene complexities.
That paper in particular illustrates how close we are. We are approaching the crossover point with the number of on-screen primitives right now. GPU's have done a lot to decrease the need for more primitives since then (hacks like parallax mapping and so forth,) but they are doing those things precisely because the demand for more scene detail is outpacing the ability to deliver higher primitive counts on GPU's. Piling on shaders (stream processors these days) only goes so far in delivering higher primitive counts, because their real choice is latency or bandwidth.. pick only one, even though you need both.
Unfortunately, many non-programmers such as yourself dont understand algorithmic complexity and as such fail to realize that O(P log N) will eventually beat O(PN) once N is large enough, even though the constants in the first are much larger than the constants in the second.
Carmack knows that raytracing will eventually be superior in performance to rasterization because it is inevitable.
The thing is that when the critical N is reached, O(P log N) isnt just going to be slightly better, its going to be enormously better from then on out. It is similar to how for small N that Bubble Sort beats Quick Sort but once the critical N is reached, Bubble Sort is left in the dust with absolutely no hope of beating the better-scaling algorithms.
Outside of benchmarking, what are consumers doing with 500+ MB/sec of sustained transfers from a single drive ?
Obviously you think that consumers only deal with small datasets.
Perhaps you are unaware that people play video games, and that the latest video games are many gigabytes (GTA 4 is 14GB), that even single maps sometimes use many gigabytes of data?
I guess you like loading screens and progress bars. Do they turn you on?
I also question the necessity of a faster interconnect. Are drives really sustaining those kinds of speeds?
The first SSD maker to stress SSD performance was MTRON in late 2007. The market prior to this point was playing the "lets get bigger" game while only pushing around 20MB/sec, until MTRON's 16 GB drive turned the entire market upside down with its 100+MB/sec sustained reads. But at this point even MTRON wasn't improving write performance.
By 2009, SSD's had been effectively saturating the SATA 2.0 link with 250MB+/sec sustained read speeds, with write speeds breaking 100+MB/sec themselves.
SATA 2.0 wasn't even really considered universally adopted by consumers until early 2010, a year after SATA 3.0's ratification.
Now its mid-2011, and SSD's are effectively saturating SATA 3.0 with sustained 500+MB/sec on both reads and writes, while most consumers still have only SATA 2.0 support.
SATA is so inadequate that manufacturers are bringing back the return of the Hardcards's.
From what I've seen, monopolistic price gouging is Retardican behavior all the time.
Price gouging has not been demonstrated. All that has been claimed is that people that use 2000 gallons/month pay 3 times as much as those than use 1000 gallons.month. For all we know, thats $3 and $1 respectively... the exact opposite of price gouging.
Why should the "1000" rate have anything to do with the average monthly usage? You are just trying to detract from the meaningful issue here.
If its gouging you so badly, then why would you be afraid to tell us what that rate actually is?
The rate is a dollar amount per gallon for a specific usage. You have not given any dollar amounts yet, therefore you have just waved your hands about like a jealous and angry little boy.
"wah wah! if I used 33% of what I use now, I would pay a lot less per gallon! wah wah!"
My guess is that you are somewhere in the 2000-4000 gallon bracket and pay around $25/month, significantly less than a hell of a lot of people, for that same amount of water. I have to guess because you refuse to say anything fucking meaningful.
I'm very good with reading comprehension, even if he isn't. I noticed that not once was it demonstrated in this discussion that the rates themselves were unreasonable.
My guess is that the majority of users pay less because of the rate graduated system, that the heaviest users bare the brunt of the system... a concept right out of Democrat playbooks.
We all KNOW that raising taxes alone won't solve the problem. So why do you people keep writing up these long-winded posts about how taxing the rich is a waste of time? You are tilting at a strawman.
If you know that its not going to fix the problem, then provide a different justification for doing it instead of pretending that it will fix the problem (note that "fixing the problem" is exactly what the grandparent thought was achievable by "raising taxes on the rich.")
We are talking about people that already pay far more in taxes, both in tax rate and in absolute total dollars, than everyone else. Provide a real good justification for raising their taxes even higher, and do so while not sounding like a jealous asshat.
The top 1% pay most of the tax burden because they have by far most of the wealth in this country and benefit the most, directly or indirectly, from government services.
The people that benefit the most from government services are those that literally have nothing. People that wouldnt have food or shelter without government services clearly benefit more than someone who takes advantage of infrastructure and sector-bound subsidies like for aviation and agriculture. Your jealousy has stolen your perspective from you.
If you sort all the spending, as line items, according to some subjective net benefit measure, the top of the list will be great stuff but there will of course be steep diminishing returns as you go down the list. Both Liberals and Conservatives can agree on this simple idea, but of course will disagree to some extent on the order the list should be in. I think we can also all agree that not everything on the list is a net benefit, that the stuff way at the bottom of both lists clearly goes so far into diminishing returns that they actually have negative returns.
The crappy spending need not necessarily be cut from the budget, but instead simply spent elsewhere where it would have greater returns. Some of the shit we are spending we decided on 80 years ago (for example, we decided to subsidize agriculture when 25% of the population literally *lived* on farms, but now only 2% live on farms.)
Its simply not fair to continue throwing money down the toilet while demanding that [subset of people] to pay more to cover the waste. Its completely asinine to do that. First cut the shit off the budget. Then, if you have better ways of spending that same money, raise taxes to cover it.
But how do we get there? Its called the Line Item Veto. Each President in turn (both Republican and Democrat) would say "no fucking way!" to some spending, cuts which could then only be over-ruled by much more than a simple majority in the Senate. Only the intersect between the two parties ideologies would be safe from the axe, and thats probably right where we should be.
Instead of:
Not Intelligent, Not Intelligent, Not Intelligent, Not Intelligent, Not Intelligent, Not Intelligent,...
If you are going to analyze the data, then why on earth would you not try to classify and database as much as possible? Seems like a big waste of resources.
Out here in Middle of Nowhere, West Virginia, the poverty margin is 80% of all households
You will believe anything "they" tell you, wont you?
If you stop LISTENING to them, and instead start WATCHING them.. you will enlighten yourself to the actual real-deal situation.
Nobody in the media has a vested interest in the truth, and investigative journalism died 30 years ago. Everyone in government has a reason to mislead you, and the media just reports what those misleading fucks in the government are saying (when they arent manufacturing news themselves.) You can go on about FoxNews or MSNBC, but these are just two sides of the same coin. They have divided up the market, one settling for conservative eyes the other settling for liberal eyes. Neither has a vested interest in telling you what the truth is.
Stop listening to what the people in government are saying. Start watching what they are doing.
You will find that the Democrats have been especially bad these past 30 years.. telling you one thing but doing exactly the opposite of what they say. The Democrats had the House, the Senate, and the Oval Office starting in 2008 with such a majority that they never needed a single Republican vote for anything (the Health Care Bill got exactly 1 (unnecessary!) Republican vote in both House and Senate combined.) What did they *do* during this period of Democrat dominance? and compare that to what they *said* during this period.
They did things that are pretty much the exact opposite of what they are always saying. They never raised taxes. They increased spending at the fastest rate ever. They gave Wall Street trillions of dollars. They gave the insurance companies the biggest gift ever given to any industry in the history of the world. They continued the Wars. They strengthened and renewed The Patriot Act. They gave the RIAA and MPAA a front-stage pass to legislation... we can go on and on about what the Democrats did with their dominance of the House, Senate, and Oval Office.
When you compare what they did to what they said, you cannot conclude that the Democrats have the solution. They are the biggest part of the problem.
We know for certain that OS/X is not secure, that there are in fact (A) unpatched local privilege escalation vulnerabilities, and (B) Safari is vulnerable to drive by code execution initiated by simply loading a web page.
Combine these two, and the conclusion that "Macs are only secure because they are less popular" is most certainly true.
Going further, Apple is also incapable of protecting iOS in spite of their extensive efforts to lock it down, that it too is vulnerable to drive-byes that will entirely root the thing (considered a feature by many, since they hate the Apple lock-down)
A citation for (A) is here and a quick search reveals that this vulnerability was known at least 5 years ago yet is still unpatched.
A citation for (B) isnt needed. The latest patch for Safari fixed 47 known drive-by remote code execution exploits, the patch before that fixed 57 known drive-by remote code execution exploits.
Windows isn't a real-time OS, so not using.NET but continuing with C++ on Windows is still horribly contradictory to your claims of real-time applications.
You would need to target an OS like VxWorks or the RTLinux distribution (nearly all Linux distributions are NOT real-time OS's).. until you are doing that, you simply are not designing real-time applications.
Do you even know what a real-time application actually is?
Its not the rest of the worlds fault that C programmers decided that a String is an array of Character. The Character part is one of the problems.. and is contrary to what was considered a String prior to C.
If you're traversing a string anyway, what happens is that when you load the data into your register (which you'll be doing anyway, for whatever reason you're traversing the string), you get a status flag set "for free" if it's zero
The most popular architecture with flags is the x86 line, and it most certainly does NOT do what you are claiming. None of the memory copying instructions (mem to mem, mem to reg, reg to mem, or even reg to reg) alter the flags at all, ever, and thats by design.
Which architecture does what you claim? Seriously. I know it isn't PDP-11, x86, 6502, or 65816.
You do realize that pascal strings can be copied with a single x86 assembler instruction, right?
rep movsb
Your argument doesnt sound like you know that tho. You seem to think that it takes more assembler instructions than the C code. The absolute smallest implementation of that C code's loop on x86 would 4 instruction:
copyloop:
lodsb
stosb
cmp al, 0
jnz copyloop
I assure you that this is significantly slower than the pascal version too.
Just wish to point out that Ritchie is citing Kernighan here with regards to Pascal's strings, which is akin to Ballmer citing Gates with regards to Macintosh.
On x86 you dont need the temp register that the ascii 0 strings need if you are dealing with a counted string.
..and as another poster pointed out, the CPU's string instructions require an up-front count.
Furthermore, thats a naive implementation of an ascii 0 string copy routine. A decent implementation would use a pointer, a static displacement (stored in a register, of course), and the temp. This requires only one pointer increment instead of two, at the cost of only a single subtraction (disp = dest - src) before the copy loop begins.
Do you still want to let implementation details drive your argument? I'm guessing that no, you actually dont want the implementation details to be a part of this discussion since they do not actually support your argument.
However, to be technically correct, strings should contain text, and text should not contain a 0-byte.
Why not?
These C "strings" are precisely the reason that ascii 0 is treated as special, and not the other way around.
C doesnt have a string type, so programmers hacked up something dirt-simple to implement them. Now people like you think that a byte with a value of 0 actually SHOULD be special, even though its yet one more value for the byte to take on.
Would you defend a file system that did not accurately store the length of files, that instead used an end of file marker? Before you respond too quickly, note that history is littered with those file systems. Nobody uses them anymore because they were, like C's "strings", just something hacked up to be "simple."
Every language that has ever taken strings seriously has opted for the minimum of a length + pointer structure. That tells us that ascii 0 is not special as you suggest. Not at all.
You have repeated this at least 3 times in this thread, but I have yet to see you actually given evidence of it. Linking to videos that do something kinda-maybe-similar but only for a small object is not evidence.
Slashdot Mirror
What I'm discussing is what can and cannot be concluded from big-O asymptotic complexity.
I thought it was interesting that he said hes spent the last 1.5 years working on raytracers. Carmack is very much a research guy now, not a developer. He pays others to develop.
Yeah, not to mention that with full ray-tracing, as you add more lights to a scene, it increases the overall complexity per pixel per ray bounce linearly as well. That's why doing deferred shading is so nice because it unbuckles the lighting from the rasterization or ray-casting/tracing step and lets you scale up the number of lightings independently with a fixed amount of overhead and linear cost per light for the entire scene, instead of per pixel or per ray or per polygon.
I highlighted the key thing that you overlooked. They are both linear to the number of lights.
Everything you wrote is mathematically accurate, yet the actually interesting thing is exactly how big N has to get.
You know that this very question has been researched, right? I am amazed that you are intent to discuss this issue without having actually done any research in this matter.
You might want to start with this 2005 paper from Intel where they do some performance comparison for both hardware rasterization and software raytracing for various scene complexities.
That paper in particular illustrates how close we are. We are approaching the crossover point with the number of on-screen primitives right now. GPU's have done a lot to decrease the need for more primitives since then (hacks like parallax mapping and so forth,) but they are doing those things precisely because the demand for more scene detail is outpacing the ability to deliver higher primitive counts on GPU's. Piling on shaders (stream processors these days) only goes so far in delivering higher primitive counts, because their real choice is latency or bandwidth.. pick only one, even though you need both.
Unfortunately, many non-programmers such as yourself dont understand algorithmic complexity and as such fail to realize that O(P log N) will eventually beat O(PN) once N is large enough, even though the constants in the first are much larger than the constants in the second.
Carmack knows that raytracing will eventually be superior in performance to rasterization because it is inevitable.
The thing is that when the critical N is reached, O(P log N) isnt just going to be slightly better, its going to be enormously better from then on out. It is similar to how for small N that Bubble Sort beats Quick Sort but once the critical N is reached, Bubble Sort is left in the dust with absolutely no hope of beating the better-scaling algorithms.
Outside of benchmarking, what are consumers doing with 500+ MB/sec of sustained transfers from a single drive ?
Obviously you think that consumers only deal with small datasets.
Perhaps you are unaware that people play video games, and that the latest video games are many gigabytes (GTA 4 is 14GB), that even single maps sometimes use many gigabytes of data?
I guess you like loading screens and progress bars. Do they turn you on?
I also question the necessity of a faster interconnect. Are drives really sustaining those kinds of speeds?
The first SSD maker to stress SSD performance was MTRON in late 2007. The market prior to this point was playing the "lets get bigger" game while only pushing around 20MB/sec, until MTRON's 16 GB drive turned the entire market upside down with its 100+MB/sec sustained reads. But at this point even MTRON wasn't improving write performance.
By 2009, SSD's had been effectively saturating the SATA 2.0 link with 250MB+/sec sustained read speeds, with write speeds breaking 100+MB/sec themselves.
SATA 2.0 wasn't even really considered universally adopted by consumers until early 2010, a year after SATA 3.0's ratification.
Now its mid-2011, and SSD's are effectively saturating SATA 3.0 with sustained 500+MB/sec on both reads and writes, while most consumers still have only SATA 2.0 support.
SATA is so inadequate that manufacturers are bringing back the return of the Hardcards's.
Porn.
From what I've seen, monopolistic price gouging is Retardican behavior all the time.
Price gouging has not been demonstrated. All that has been claimed is that people that use 2000 gallons/month pay 3 times as much as those than use 1000 gallons.month. For all we know, thats $3 and $1 respectively... the exact opposite of price gouging.
Why should the "1000" rate have anything to do with the average monthly usage? You are just trying to detract from the meaningful issue here.
If its gouging you so badly, then why would you be afraid to tell us what that rate actually is?
The rate is a dollar amount per gallon for a specific usage. You have not given any dollar amounts yet, therefore you have just waved your hands about like a jealous and angry little boy.
"wah wah! if I used 33% of what I use now, I would pay a lot less per gallon! wah wah!"
My guess is that you are somewhere in the 2000-4000 gallon bracket and pay around $25/month, significantly less than a hell of a lot of people, for that same amount of water. I have to guess because you refuse to say anything fucking meaningful.
I'm very good with reading comprehension, even if he isn't. I noticed that not once was it demonstrated in this discussion that the rates themselves were unreasonable.
My guess is that the majority of users pay less because of the rate graduated system, that the heaviest users bare the brunt of the system... a concept right out of Democrat playbooks.
We all KNOW that raising taxes alone won't solve the problem. So why do you people keep writing up these long-winded posts about how taxing the rich is a waste of time? You are tilting at a strawman.
If you know that its not going to fix the problem, then provide a different justification for doing it instead of pretending that it will fix the problem (note that "fixing the problem" is exactly what the grandparent thought was achievable by "raising taxes on the rich.")
We are talking about people that already pay far more in taxes, both in tax rate and in absolute total dollars, than everyone else. Provide a real good justification for raising their taxes even higher, and do so while not sounding like a jealous asshat.
The top 1% pay most of the tax burden because they have by far most of the wealth in this country and benefit the most, directly or indirectly, from government services.
The people that benefit the most from government services are those that literally have nothing. People that wouldnt have food or shelter without government services clearly benefit more than someone who takes advantage of infrastructure and sector-bound subsidies like for aviation and agriculture. Your jealousy has stolen your perspective from you.
If you sort all the spending, as line items, according to some subjective net benefit measure, the top of the list will be great stuff but there will of course be steep diminishing returns as you go down the list. Both Liberals and Conservatives can agree on this simple idea, but of course will disagree to some extent on the order the list should be in. I think we can also all agree that not everything on the list is a net benefit, that the stuff way at the bottom of both lists clearly goes so far into diminishing returns that they actually have negative returns.
The crappy spending need not necessarily be cut from the budget, but instead simply spent elsewhere where it would have greater returns. Some of the shit we are spending we decided on 80 years ago (for example, we decided to subsidize agriculture when 25% of the population literally *lived* on farms, but now only 2% live on farms.)
Its simply not fair to continue throwing money down the toilet while demanding that [subset of people] to pay more to cover the waste. Its completely asinine to do that. First cut the shit off the budget. Then, if you have better ways of spending that same money, raise taxes to cover it.
But how do we get there? Its called the Line Item Veto. Each President in turn (both Republican and Democrat) would say "no fucking way!" to some spending, cuts which could then only be over-ruled by much more than a simple majority in the Senate. Only the intersect between the two parties ideologies would be safe from the axe, and thats probably right where we should be.
It is still science though - however useless it is, not science fiction.
I wonder.. has SETI found anything at all that is the least bit scientifically interesting?
...
...
You would think that it would be the Search for Extra Terrestrial Unexpecteds, instead of Intelligence.
This:
Noise, Noise, Quasar, Noise, M-Class Star, Noise, Unknown, Noise,
Instead of:
Not Intelligent, Not Intelligent, Not Intelligent, Not Intelligent, Not Intelligent, Not Intelligent,
If you are going to analyze the data, then why on earth would you not try to classify and database as much as possible? Seems like a big waste of resources.
They are using money that they print specifically to buy those treasuries. to buy those treasuries. In other words, its a no-brainer.
"oh look! free money!"
Out here in Middle of Nowhere, West Virginia, the poverty margin is 80% of all households
You will believe anything "they" tell you, wont you?
If you stop LISTENING to them, and instead start WATCHING them.. you will enlighten yourself to the actual real-deal situation.
Nobody in the media has a vested interest in the truth, and investigative journalism died 30 years ago. Everyone in government has a reason to mislead you, and the media just reports what those misleading fucks in the government are saying (when they arent manufacturing news themselves.) You can go on about FoxNews or MSNBC, but these are just two sides of the same coin. They have divided up the market, one settling for conservative eyes the other settling for liberal eyes. Neither has a vested interest in telling you what the truth is.
Stop listening to what the people in government are saying. Start watching what they are doing.
You will find that the Democrats have been especially bad these past 30 years.. telling you one thing but doing exactly the opposite of what they say. The Democrats had the House, the Senate, and the Oval Office starting in 2008 with such a majority that they never needed a single Republican vote for anything (the Health Care Bill got exactly 1 (unnecessary!) Republican vote in both House and Senate combined.) What did they *do* during this period of Democrat dominance? and compare that to what they *said* during this period.
They did things that are pretty much the exact opposite of what they are always saying. They never raised taxes. They increased spending at the fastest rate ever. They gave Wall Street trillions of dollars. They gave the insurance companies the biggest gift ever given to any industry in the history of the world. They continued the Wars. They strengthened and renewed The Patriot Act. They gave the RIAA and MPAA a front-stage pass to legislation... we can go on and on about what the Democrats did with their dominance of the House, Senate, and Oval Office.
When you compare what they did to what they said, you cannot conclude that the Democrats have the solution. They are the biggest part of the problem.
Apparently there is a Router/Modem Botnet that you are fucking clueless about.
Clueless people should not open their mouths about the very subjects that they are clueless about.
We know for certain that OS/X is not secure, that there are in fact (A) unpatched local privilege escalation vulnerabilities, and (B) Safari is vulnerable to drive by code execution initiated by simply loading a web page.
Combine these two, and the conclusion that "Macs are only secure because they are less popular" is most certainly true.
Going further, Apple is also incapable of protecting iOS in spite of their extensive efforts to lock it down, that it too is vulnerable to drive-byes that will entirely root the thing (considered a feature by many, since they hate the Apple lock-down)
A citation for (A) is here and a quick search reveals that this vulnerability was known at least 5 years ago yet is still unpatched.
A citation for (B) isnt needed. The latest patch for Safari fixed 47 known drive-by remote code execution exploits, the patch before that fixed 57 known drive-by remote code execution exploits.
Windows isn't a real-time OS, so not using .NET but continuing with C++ on Windows is still horribly contradictory to your claims of real-time applications.
.. until you are doing that, you simply are not designing real-time applications.
You would need to target an OS like VxWorks or the RTLinux distribution (nearly all Linux distributions are NOT real-time OS's)
Do you even know what a real-time application actually is?
You are confusing a String type with a Text type.
Its not the rest of the worlds fault that C programmers decided that a String is an array of Character. The Character part is one of the problems.. and is contrary to what was considered a String prior to C.
If you're traversing a string anyway, what happens is that when you load the data into your register (which you'll be doing anyway, for whatever reason you're traversing the string), you get a status flag set "for free" if it's zero
The most popular architecture with flags is the x86 line, and it most certainly does NOT do what you are claiming. None of the memory copying instructions (mem to mem, mem to reg, reg to mem, or even reg to reg) alter the flags at all, ever, and thats by design.
Which architecture does what you claim? Seriously. I know it isn't PDP-11, x86, 6502, or 65816.
Please tell us.
You do realize that pascal strings can be copied with a single x86 assembler instruction, right?
rep movsb
Your argument doesnt sound like you know that tho. You seem to think that it takes more assembler instructions than the C code. The absolute smallest implementation of that C code's loop on x86 would 4 instruction:
copyloop:
lodsb
stosb
cmp al, 0
jnz copyloop
I assure you that this is significantly slower than the pascal version too.
Just wish to point out that Ritchie is citing Kernighan here with regards to Pascal's strings, which is akin to Ballmer citing Gates with regards to Macintosh.
On x86 you dont need the temp register that the ascii 0 strings need if you are dealing with a counted string.
..and as another poster pointed out, the CPU's string instructions require an up-front count.
Furthermore, thats a naive implementation of an ascii 0 string copy routine. A decent implementation would use a pointer, a static displacement (stored in a register, of course), and the temp. This requires only one pointer increment instead of two, at the cost of only a single subtraction (disp = dest - src) before the copy loop begins.
Do you still want to let implementation details drive your argument? I'm guessing that no, you actually dont want the implementation details to be a part of this discussion since they do not actually support your argument.
However, to be technically correct, strings should contain text, and text should not contain a 0-byte.
Why not?
These C "strings" are precisely the reason that ascii 0 is treated as special, and not the other way around.
C doesnt have a string type, so programmers hacked up something dirt-simple to implement them. Now people like you think that a byte with a value of 0 actually SHOULD be special, even though its yet one more value for the byte to take on.
Would you defend a file system that did not accurately store the length of files, that instead used an end of file marker? Before you respond too quickly, note that history is littered with those file systems. Nobody uses them anymore because they were, like C's "strings", just something hacked up to be "simple."
Every language that has ever taken strings seriously has opted for the minimum of a length + pointer structure. That tells us that ascii 0 is not special as you suggest. Not at all.
You have repeated this at least 3 times in this thread, but I have yet to see you actually given evidence of it. Linking to videos that do something kinda-maybe-similar but only for a small object is not evidence.