I wish slashdotters would not respond to a technical article unless they understood what they were talking about.
The author fully understands the nature of the internet. He is limiting the scope of his study to "theoretical bandwidth limitations" because that provides an upper bound on scalability regardless of the underlying hardware network structure. Yeah, okay, you won't actually hit that upper bound, but that's not the point. You can't possibly *exceed* the upper bound. That's the point. Earlier papers attempted to prove much lower upper bounds, and this is a (quite good) refutation of them.
Most posters are also confused about the relationship between hardware and software network topologies. Yes, the Internet connection going into your college or whatever has a fixed limited network topology. Yes, that will cause a 20-cube to have less bandwidth utilization than the theoretical limit. But guess what... the current logical tree structure that gnutella uses *also* does not match the underlying hardware structure, and so suffers in the same way.
By discussing the differences between the Cayley tree and the hypercube, we can do things like quantify the *rate* at which each of them suffers due to a bottleneck like this.
This is how science is done. People who ignore the science and just say "I am going to hack some super l33t heuristics into the network so searches work better" are being fools. Any heuristic you implement over a poorly-performing topology is going to work much better on the well-performing topology.
You can install Linux on a 486, or you can install it on a 1GHz Athlon. The slashdotters dissing this paper are essentially saying "Well it's stupid to install Linux on the Athlon, it won't go any faster because you know, those instruction cycle counts for the Athlon are all theoretical and you will never hit that performance in the real world... there are going to be cache misses and FPU stalls and stuff. So let's stay with the 486! Yeah, it's slow, but if we just optimize our apps, they will run faster!" Well you can optimize your apps and fool yourself into thinking you are doing a good job. But if you then turn around and run the newly optimized apps on the Athlon (or put the same amount of effort into optimizing them differently for the different CPU architecture) you will ground the 486 into a pile of rubble.
I am a game programmer, with a fair number of years of experience at this point. And I think the OpenAL API is horrible.
I don't care at all about the preemptive multitasking part -- old versions of MacOS can bite me. But I do care that it is way, *way* harder to use OpenAL than it should be, and the reason why is that the guys who designed the API had a horrible sense of priorities.
Sound is fundamentally different than graphics; the paradigms that work well for outputting 3D graphics are inappropriate for audio. My biggest issue with OpenAL is that they took the OpenGL/Direct3D driver model of "download texture to the video card" and made their audio buffers work that way by necessity. Now, this is a feature that no game programmer will ever use, for various reasons (the most important of which being that it's just not necessary; sound consumes negligible bandwidth on modern computers, so why try to optimize that bandwidth?). But this feature that nobody with a clue will ever use, being at the core of the API, makes everything way more complicated than it should be. (And, consequently, more bug-prone).
People with 3D graphics experience will tell you that the texture downloading step in 3D graphics is the biggest pain in the ass, and that they'd rather have it not be there if they had the choice. (See e.g. Carmack's plan files of a couple of years ago regarding virtual-memory-style textures, the idea being that you keep them on the host CPU and never explicitly download them.) So the idea of thinking that downloadable textures are cool, and wanting to emulate that in a sound API, smacks of inexperience.
I suspect that part of the reason for this API lameness is that a large part of the development is being undertaken / organized by Creative Labs, who have the agenda of pushing many of their useless hardware acceleration features onto the market. When working on OpenAL, they want to support those features, not necessarily make the objectively best API. (I doubt that the engineers at Creative think their hardware buffer stuff is useless... but it is. Anyone with game experience will tell them so.)
[I was on the OpenAL dev mailing list for a while. I tried to make API suggestions but they were basically ignored.]
The 5k pulse wave you are talking about contains many many high-frequency sine waves. That is what makes it sound "clicky". Because you're a computer guy, you are used to thinking about square waves. But square waves are not a good way of thinking about these problems.
All I can say is, signal processing research has been going on for a very long time (over 100 years) and has been participated in by a lot of very smart people. So before you start calling its foundations "mostly crap" I'd recommend you do a bit of reading.
It's clear from your talk of "real-world frequencies" that you haven't even the slightest notion of signal processing, and furthermore you're not even reading the replies in this thread (there are at least two messages by other people explaining what's wrong with the "square wave" idea more thoroughly than I did).
If you want a simple illustration of why your basis of thought is faulty, here's a question for you: What is the frequency content of a single pulse in the midst of silence? That is, take your pulse wave of whatever period you want, and stretch it out and out until you just have one pulse. What is the frequency content there? You might say "zero" but this is not even close to correct. There is sound after all.
When we say "You can reproduce frequencies of up to 22050 Hz", we are talking about sine waves. The "square wave of 22050 Hz" that you are talking about is pretty much irrelevant. A 22050 square wave contains frequencies that are *much* higher than 22kHz. Most of these frequencies would be filtered out prior to any kind of processing (digital or analog).
So in a sense you're confusing the discussion. A square wave, in terms of the signal processing we're talking about, is not a pure "wave" any more than is the sound of someone coughing up a lung. You must first decompose the sound into its component frequencies before you can discuss signal processing and make any sense.
Trying to think in terms of a square wave, at all, puts you in the wrong position to think about this (unless you're talking about the Haar wavelet but that is a different subject entirely).
Sounds of up to half the sampling rate can be reproduced *exactly* by (ideal) audio equipment.
This is what the Nyquist theorem says. The thing you are saying about square waves is a misunderstanding on your part.
The frequencies we are talking about are all sine waves. So the shape to be reconstructed is predetermined and known clearly. There is no "interpolation". You may be familiar with the Fourier transform, which takes advantage of the fact that all sounds can be represented as compositions of sine waves.
All that said, I think that the idea of higher fidelity is a good one. Because there are two things that happen on CDs as they stand now:
(1) Companding
(2) Quantization
A brief and kinda-misleading explanation of "companding" is that the bottom hundred or so Hertz of music on a CD is chopped out. This is under the theory that the human ear can't hear this stuff, but lots of people say they can. And even if you can't consciously notice these tones in isolation, it's not much of a step to believe that they contribute to the "richness" of a sound when mixed in.
Quantization is another matter. Say you have 44,100 samples per second stored on a CD. Each of those samples represents the intensity of the sound at each point in time. That intensity is a real number (an analog value) and it's being stored as an integer (a digital value). In mapping from the analog to the digital value, you lose precision (think of rounding a float to an
int). The more bits you have to represent each value, the less distorted the sound is. Think
of the difference between 16-bit truecolor and 24-bit truecolor when viewing photographs and whatnot.
I think added resolution on disc-based music would be really nice. Whether it comes through audio DVD, or a different CD format, though, I don't really care. I think that DVD would be nicer for obvious reasons of storage capacity.
Okay, so everybody is bagging on Red Hat here. But here's a question I would like to pose to everybody:
Why is it acceptable for a process to be able to hose the operating system by opening file descriptors and not closing them?
The only answer I can think of is, "because that's the way it's always been". Well that is completely lame.
Think of it as being like protected memory. It is not acceptable for a process to kill the kernel by writing to a random memory location. So why should it be okay for a process to (effectively) kill the kernel (by preventing the proper spawning of new processes due to lack of fd's) by opening sockets?
Voxels are interesting because, once you get to a certain resolution using triangles, most of them project to be about 1 pixel large (or less) on the screen anyway. The idea is that using a cloud of points, for high density images you can get equal or nearly equal image quality with less data (it theoretically takes more data, and processing time, to handle a structured triangle mesh than it does a cloud of points).
At SIGGRAPH this year there were a number of papers about direct point rendering. (And also about lightfield rendering, which is about drawing scenes without using any geometry at all). Try digging up the proceedings if you are interested in this.
Hardware accelerated Bezier patches are a lot like hardware accelerated Phong shading: they sound like a great idea, the "obvious next step", unless you're trying to use them to do something real. Just as Phong shading is not a particularly interesting lighting model once you reach a certain level of sophistication, Bezier patches are not very interesting shapes. Yeah, they're curvy, but they are curvy *without surface detail at a higher resolution than the curve*, which is just not very interesting.
John Carmack had a.plan file 1.5 or 2 years ago about why he thinks Bezier patches are a bad idea and I pretty much agree with him. For the amount of data it takes you to create the shapes you want with Bezier patches, you can construct triangle meshes for the same shapes using less data and less headache.
Jonathan Blow
Game Research Scientist
Bolt Action Software
This isn't the impression Chris was trying to give in his lecture.
What you have to understand is that game developers are not raking in the $$$. Not at all. Game developers for the most part live hand-to-mouth, constantly in danger of going out of business. Once in a while you have a developer who is very profitable, but that is not the general picture. For the most part, retailers and publishers get all the money.
What he was saying was this: if somebody gives a developer $5 million to make a game with, then they are going to do whatever is in their power to ensure that they get that $5 million back with a nice bonus. Hardcore research is a *big* risk because it is not known in advance whether the problem is solvable, or how well it can be solved. Therefore people who are trying to make a game project get finished on time (or finished at all) will steer it away from this research because there is just too much money at stake.
Chris was not saying this was good. He was saying it sucks, and I agree with him. What we need is more innovation and research in the industry, not less. (And Chris' co-organizing of a game research day at siggraph was a step toward trying to increase the amount of research that gets done).
The only reason that I was able to do research that was presentable at that conference is that I am co-owner of my company, so I can to a large degree set my own agenda. If I were working for Activision, there would be one less terrain rendering algorithm in the world.
I don't use the two interchangeably. Maybe I worded the post unclearly.
Gauss invented the Fourier transform *and* the FFT before Fourier invented the Fourier transform. Fourier never figured out the FFT, as one poster has pointed out. If that was unclear from my original text, then sorry about that.
Gauss basically came up with the FFT out of necessity... he was processing a ton of planetary observation data by hand.
Anyway, you say you "don't know how much of my comment to believe", but that's why I included references, eh. The FFT has been invented many times in the 20th century, all of them rediscoveries of what Gauss did. Check any signal processing book that has historical notes.
(a) As someone has already pointed out, it is heavily biased toward numerical computation, fully ignoring the rest of the (very wide) field of algorithms.
(b) Items on the list are individually pretty ignorant. The Fortran optimizing compiler sticks out like a sore thumb, but even worse is the listing for "Fast Fourier Transform".
The FFT was actually invented by Gauss, before Fourier. Yes, Gauss actually invented the Fourier transform in 1805; he was afraid to publish it due to persecution. When Fourier published regarding the Fourier transform, he was indeed heavily ridiculed; the usefulness of the Fourier transform was not generally acknowledged until after Fourier's death. Gauss' document describing the FFT did not see the light of day until 1866 (this document was "Theoria Interpolationis Methodo Nova Tractata", which as you can see was written in Latin).
The "discovery" of the FFT that this list refers to is the paper by Cooley and Tukey written in 1965, "An Algorithm for the Machine Calculation of Complex Fourier Series". However, this was not even the first rediscovery of the FFT that happened in the 20th century. Several people rediscovered and published FFT algorithms between 1910 and 1965 but the Cooley and Tukey paper is the first one that was seized upon by computer science guys, so they get all the recognition.
Most books that go into depth about signal processing will have this information about the FFT; I am looking right now in my favorite, very accessible signal book, "A Digital Signal Processing Primer" by Ken Steiglitz. Not all the books go all the way back to the discovery by Gauss, but they all pretty much mention that the FFT has been rediscovered several times in the 20th century.
Now the web page in question says that this list was published in "Science", which makes me feel really bad for Science. I have not been around for very long (I'm 28) and I am not any kind of algorithms specialist (I'm a game programmer) but even I can tell that this list is bogus.
Now give me a "10 greatest algorithms" list written by Knuth and maybe I will take it seriously.
You forgot a few: Dave Taylor: started his game company crack dot com, that company went down. Now working at Transmeta. American McGee: Fired, or something. Designing a game called "Alice" for EA. Mike Wilson: Left to help start Ion Storm, bailed out of Ion Storm when it started looking lame. Now founder of G.O.D. Jay Wilbur, originator of the business card title "biz guy". Now at Activision (?).
Slashdot Mirror
I wish slashdotters would not respond to a technical article unless they understood what they were talking about.
The author fully understands the nature of the internet. He is limiting the scope of his study to "theoretical bandwidth limitations" because that provides an upper bound on scalability regardless of the underlying hardware network structure. Yeah, okay, you won't actually hit that upper bound, but that's not the point. You can't possibly *exceed* the upper bound. That's the point. Earlier papers attempted to prove much lower upper bounds, and this is a (quite good) refutation of them.
Most posters are also confused about the relationship between hardware and software network topologies. Yes, the Internet connection going into your college or whatever has a fixed limited network topology. Yes, that will cause a 20-cube to have less bandwidth utilization than the theoretical limit. But guess what... the current logical tree structure that gnutella uses *also* does not match the underlying hardware structure, and so suffers in the same way.
By discussing the differences between the Cayley tree and the hypercube, we can do things like quantify the *rate* at which each of them suffers due to a bottleneck like this.
This is how science is done. People who ignore the science and just say "I am going to hack some super l33t heuristics into the network so searches work better" are being fools. Any heuristic you implement over a poorly-performing topology is going to work much better on the well-performing topology.
You can install Linux on a 486, or you can install it on a 1GHz Athlon. The slashdotters dissing this paper are essentially saying "Well it's stupid to install Linux on the Athlon, it won't go any faster because you know, those instruction cycle counts for the Athlon are all theoretical and you will never hit that performance in the real world... there are going to be cache misses and FPU stalls and stuff. So let's stay with the 486! Yeah, it's slow, but if we just optimize our apps, they will run faster!" Well you can optimize your apps and fool yourself into thinking you are doing a good job. But if you then turn around and run the newly optimized apps on the Athlon (or put the same amount of effort into optimizing them differently for the different CPU architecture) you will ground the 486 into a pile of rubble.
-N.
I hate to say this, but you went to a crappy high school.
American Pie is about the plane crash that killed Buddy Holly, Ritchie Valens and the Big Bopper.
-N.
I am a game programmer, with a fair number of years of experience at this point. And I think the OpenAL API is horrible.
I don't care at all about the preemptive multitasking part -- old versions of MacOS can bite me. But I do care that it is way, *way* harder to use OpenAL than it should be, and the reason why is that the guys who designed the API had a horrible sense of priorities.
Sound is fundamentally different than graphics; the paradigms that work well for outputting 3D graphics are inappropriate for audio. My biggest issue with OpenAL is that they took the OpenGL/Direct3D driver model of "download texture to the video card" and made their audio buffers work that way by necessity. Now, this is a feature that no game programmer will ever use, for various reasons (the most important of which being that it's just not necessary; sound consumes negligible bandwidth on modern computers, so why try to optimize that bandwidth?). But this feature that nobody with a clue will ever use, being at the core of the API, makes everything way more complicated than it should be. (And, consequently, more bug-prone).
People with 3D graphics experience will tell you that the texture downloading step in 3D graphics is the biggest pain in the ass, and that they'd rather have it not be there if they had the choice. (See e.g. Carmack's plan files of a couple of years ago regarding virtual-memory-style textures, the idea being that you keep them on the host CPU and never explicitly download them.) So the idea of thinking that downloadable textures are cool, and wanting to emulate that in a sound API, smacks of inexperience.
I suspect that part of the reason for this API lameness is that a large part of the development is being undertaken / organized by Creative Labs, who have the agenda of pushing many of their useless hardware acceleration features onto the market. When working on OpenAL, they want to support those features, not necessarily make the objectively best API. (I doubt that the engineers at Creative think their hardware buffer stuff is useless... but it is. Anyone with game experience will tell them so.)
[I was on the OpenAL dev mailing list for a while. I tried to make API suggestions but they were basically ignored.]
I am a game programmer. What you are saying is not correct.
PC games that run at 200fps really are updating each frame with a delta-T of (1/200) and redrawing.
I have no idea why you would think otherwise.
-Jonathan.
Bolt Action Software
The 5k pulse wave you are talking about contains many many high-frequency sine waves. That is what makes it sound "clicky". Because you're a computer guy, you are used to thinking about square waves. But square waves are not a good way of thinking about these problems.
All I can say is, signal processing research has been going on for a very long time (over 100 years) and has been participated in by a lot of very smart people. So before you start calling its foundations "mostly crap" I'd recommend you do a bit of reading.
It's clear from your talk of "real-world frequencies" that you haven't even the slightest notion of signal processing, and furthermore you're not even reading the replies in this thread (there are at least two messages by other people explaining what's wrong with the "square wave" idea more thoroughly than I did).
If you want a simple illustration of why your basis of thought is faulty, here's a question for you: What is the frequency content of a single pulse in the midst of silence? That is, take your pulse wave of whatever period you want, and stretch it out and out until you just have one pulse. What is the frequency content there? You might say "zero" but this is not even close to correct. There is sound after all.
-Jonathan.
Okay okay....
When we say "You can reproduce frequencies of up to 22050 Hz", we are talking about sine waves. The "square wave of 22050 Hz" that you are talking about is pretty much irrelevant. A 22050 square wave contains frequencies that are *much* higher than 22kHz. Most of these frequencies would be filtered out prior to any kind of processing (digital or analog).
So in a sense you're confusing the discussion. A square wave, in terms of the signal processing we're talking about, is not a pure "wave" any more than is the sound of someone coughing up a lung. You must first decompose the sound into its component frequencies before you can discuss signal processing and make any sense.
Trying to think in terms of a square wave, at all, puts you in the wrong position to think about this (unless you're talking about the Haar wavelet but that is a different subject entirely).
Sounds of up to half the sampling rate can be reproduced *exactly* by (ideal) audio equipment.
This is what the Nyquist theorem says. The thing you are saying about square waves is a misunderstanding on your part.
The frequencies we are talking about are all sine waves. So the shape to be reconstructed is predetermined and known clearly. There is no "interpolation". You may be familiar with the Fourier transform, which takes advantage of the fact that all sounds can be represented as compositions of sine waves.
All that said, I think that the idea of higher fidelity is a good one. Because there are two things that happen on CDs as they stand now:
(1) Companding
(2) Quantization
A brief and kinda-misleading explanation of "companding" is that the bottom hundred or so Hertz of music on a CD is chopped out. This is under the theory that the human ear can't hear this stuff, but lots of people say they can. And even if you can't consciously notice these tones in isolation, it's not much of a step to believe that they contribute to the "richness" of a sound when mixed in.
Quantization is another matter. Say you have 44,100 samples per second stored on a CD. Each of those samples represents the intensity of the sound at each point in time. That intensity is a real number (an analog value) and it's being stored as an integer (a digital value). In mapping from the analog to the digital value, you lose precision (think of rounding a float to an
int). The more bits you have to represent each value, the less distorted the sound is. Think
of the difference between 16-bit truecolor and 24-bit truecolor when viewing photographs and whatnot.
I think added resolution on disc-based music would be really nice. Whether it comes through audio DVD, or a different CD format, though, I don't really care. I think that DVD would be nicer for obvious reasons of storage capacity.
-J.
Okay, so everybody is bagging on Red Hat here. But here's a question I would like to pose to everybody:
Why is it acceptable for a process to be able to hose the operating system by opening file descriptors and not closing them?
The only answer I can think of is, "because that's the way it's always been". Well that is completely lame.
Think of it as being like protected memory. It is not acceptable for a process to kill the kernel by writing to a random memory location. So why should it be okay for a process to (effectively) kill the kernel (by preventing the proper spawning of new processes due to lack of fd's) by opening sockets?
This should, like, be fixed.
Voxels are interesting because, once you get to a certain resolution using triangles, most of them project to be about 1 pixel large (or less) on the screen anyway. The idea is that using a cloud of points, for high density images you can get equal or nearly equal image quality with less data (it theoretically takes more data, and processing time, to handle a structured triangle mesh than it does a cloud of points).
.plan file 1.5 or 2 years ago about why he thinks Bezier patches are a bad idea and I pretty much agree with him. For the amount of data it takes you to create the shapes you want with Bezier patches, you can construct triangle meshes for the same shapes using less data and less headache.
At SIGGRAPH this year there were a number of papers about direct point rendering. (And also about lightfield rendering, which is about drawing scenes without using any geometry at all). Try digging up the proceedings if you are interested in this.
Hardware accelerated Bezier patches are a lot like hardware accelerated Phong shading: they sound like a great idea, the "obvious next step", unless you're trying to use them to do something real. Just as Phong shading is not a particularly interesting lighting model once you reach a certain level of sophistication, Bezier patches are not very interesting shapes. Yeah, they're curvy, but they are curvy *without surface detail at a higher resolution than the curve*, which is just not very interesting.
John Carmack had a
Jonathan Blow
Game Research Scientist
Bolt Action Software
This isn't the impression Chris was trying to give in his lecture.
What you have to understand is that game developers are not raking in the $$$. Not at all. Game developers for the most part live hand-to-mouth, constantly in danger of going out of business. Once in a while you have a developer who is very profitable, but that is not the general picture. For the most part, retailers and publishers get all the money.
What he was saying was this: if somebody gives a developer $5 million to make a game with, then they are going to do whatever is in their power to ensure that they get that $5 million back with a nice bonus. Hardcore research is a *big* risk because it is not known in advance whether the problem is solvable, or how well it can be solved. Therefore people who are trying to make a game project get finished on time (or finished at all) will steer it away from this research because there is just too much money at stake.
Chris was not saying this was good. He was saying it sucks, and I agree with him. What we need is more innovation and research in the industry, not less. (And Chris' co-organizing of a game research day at siggraph was a step toward trying to increase the amount of research that gets done).
The only reason that I was able to do research that was presentable at that conference is that I am co-owner of my company, so I can to a large degree set my own agenda. If I were working for Activision, there would be one less terrain rendering algorithm in the world.
Jonathan Blow
Bolt Action Software
I don't use the two interchangeably. Maybe I worded the post unclearly.
Gauss invented the Fourier transform *and* the FFT before Fourier invented the Fourier transform. Fourier never figured out the FFT, as one poster has pointed out. If that was unclear from my original text, then sorry about that.
Gauss basically came up with the FFT out of necessity... he was processing a ton of planetary observation data by hand.
Anyway, you say you "don't know how much of my comment to believe", but that's why I included references, eh. The FFT has been invented many times in the 20th century, all of them rediscoveries of what Gauss did. Check any signal processing book that has historical notes.
-N.
(a) As someone has already pointed out, it is heavily biased toward numerical computation, fully ignoring the rest of the (very wide) field of algorithms.
(b) Items on the list are individually pretty ignorant. The Fortran optimizing compiler sticks out like a sore thumb, but even worse is the listing for "Fast Fourier Transform".
The FFT was actually invented by Gauss, before Fourier. Yes, Gauss actually invented the Fourier transform in 1805; he was afraid to publish it due to persecution. When Fourier published regarding the Fourier transform, he was indeed heavily ridiculed; the usefulness of the Fourier transform was not generally acknowledged until after Fourier's death. Gauss' document describing the FFT did not see the light of day until 1866 (this document was "Theoria Interpolationis Methodo Nova Tractata", which as you can see was written in Latin).
The "discovery" of the FFT that this list refers to is the paper by Cooley and Tukey written in 1965, "An Algorithm for the Machine Calculation of Complex Fourier Series". However, this was not even the first rediscovery of the FFT that happened in the 20th century. Several people rediscovered and published FFT algorithms between 1910 and 1965 but the Cooley and Tukey paper is the first one that was seized upon by computer science guys, so they get all the recognition.
Most books that go into depth about signal processing will have this information about the FFT; I am looking right now in my favorite, very accessible signal book, "A Digital Signal Processing Primer" by Ken Steiglitz. Not all the books go all the way back to the discovery by Gauss, but they all pretty much mention that the FFT has been rediscovered several times in the 20th century.
Now the web page in question says that this list was published in "Science", which makes me feel really bad for Science. I have not been around for very long (I'm 28) and I am not any kind of algorithms specialist (I'm a game programmer) but even I can tell that this list is bogus.
Now give me a "10 greatest algorithms" list written by Knuth and maybe I will take it seriously.
That is all.
The entire country of Australia ("I come from a land Down Under, where the only band is a one-hit wonder)
Oh, you can't be serious.
Nick Cave and the Bad Seeds!
The Dirty Three!
Uhh.. Austrailia has some other really good bands. Really!
You forgot a few: Dave Taylor: started his game company crack dot com, that company went down. Now working at Transmeta. American McGee: Fired, or something. Designing a game called "Alice" for EA. Mike Wilson: Left to help start Ion Storm, bailed out of Ion Storm when it started looking lame. Now founder of G.O.D. Jay Wilbur, originator of the business card title "biz guy". Now at Activision (?).