This semester, to fill up three units I needed for the good student discount on my car insurance, I took a basic introduction to linguistics class. For my third paper in the class, I wrote about the evolution of the English declension system, from Proto-Indo-European to modern Standard American English (the type used in things like text books, which is a bit more formal and "high" than everyday English, but not all that much different). Unfortunately, as the paper wasn't supposed to be more than three pages, all I could really do was give a brief overview of how the forms changed (and even then you can tell I basically ran out of space in the last paragraph, and attempted to very quickly conclude the paper). Had it been a term paper (something more like ten pages), I could have also included such information as why the changes occurred, as well as some of my predictions for the future of English based on what I see today. In this post (and possibly future ones, depending on how lengthy this turns out to be), I'll talk a bit about the latter topic: the future of English and current trends (although here I'll address more than just declension).
First, and most relevant to the paper, is what is happening with declension today. As I mentioned in my previous comparison and contrasting of case between languages, I mentioned that English currently has two cases for nouns (the general and possessive cases), and three for pronouns (subjective - 'I' - objective - 'me' - and possessive - 'my' or 'mine', depending on whether the pronoun is acting as a noun or an adjective).
However, in modern day colloquial English (the type you'd talk to your friends with), the line between the subjective and objective cases of the pronoun are becoming blurry. It's now very frequent for native speakers to use objective pronouns even in the subject position (e.g. "Me and Josh went to the supermarket"). This is done even by people such as me, who know that that is technically incorrect (should be 'I', instead of 'me').
So, where is this development going? Unfortunately, while this is growing in prominence, and is thus likely to shape tomorrow's English, it's not entirely clear what that shape will be. There are at least three possible ways this could go. First, as some have suggested, the subjective case may be lost, and English will be down to two cases for pronouns, just like nouns. This is clearly something English could take in stride. We already use syntax (word order) to differentiate between nouns being the subject or object of the sentence (in a manner outlined in my paper), so the two cases are really redundant.
However, it must be noted that no native speaker of standard American English (I can't speak for other dialects, as I don't know about them) would say something like "Me went to the supermarket"; it clearly sounds wrong. There are two alternate hypotheses that take this into account.
First, the application of the subjective case could be restricted. Rather than being used for the subject of the sentence, the rule could be altered, so that the subjective case is only used for the subject of the sentence when the subject is only composed of one noun/pronoun (as in the previous example), ignoring whether it's singular or plural. While the names subjective/objective make this sound counter-intuitive, you have to remember that the objective case already functions like an oblique case (which might, perhaps, be a better name for it) - a catch-all that includes everything but the subjective. Given this, this possibility doesn't sound so strange; of course, the subjective case could still stand a better name.
Finally, there's a third possibility. This one is particularly attractive to me, simply because it would be so unusual; specifically, that we are seeing the creation of a new, additional case: the conjunctive case - one used when there are a list of two or more nouns/pronouns in a group (note that the possessive case behaves fundamentally differently than the subjective or objective case as it is*, and so wouldn't follow this new rule). In this case (pun not intended), the form of the conjunctive case is identical to the objective case. I suppose the surest proof of this hypothesis would be if the conjunctive and objective forms diverge in the future, while the subjective case is retained.
Lastly, a footnote about the possessive case. There are actually two forms of the possessive case: the noun form (e.g. 'mine') and the adjective form (e.g. 'my'). The adjective form is clearly distinct in use from the subjective and objective cases, as it is an adjective and they are nouns. The noun form of the possessive, however, is also clearly distinct. The reason for this is that it refers to something completely different than the subjective or objective case. 'I' and 'me' both refer to exactly the same thing - me; 'mine', however, refers to something completely different - something that is obviously not me. Thus its not unreasonable to consider the possessive forms as behaving fundamentally differently from the subjective or objective cases, and not require them to follow the same rules.
Thursday, May 24, 2007
Friday, May 11, 2007
Reading Material & Stuff
No, no lengthy post, today; just some other stuff for you do read (and you should read them). From least to most specific:
Threading 3D Game Engine Basics
Real-World Case Studies: Threading Games for High Performance on Intel Processors
Multi-threaded Rendering and Physics Simulation
Designing and Building Parallel Programs
Also, got some interesting stuff going on with me, BZ, and multithreading, but I don't have time to go into that right now.
Threading 3D Game Engine Basics
Real-World Case Studies: Threading Games for High Performance on Intel Processors
Multi-threaded Rendering and Physics Simulation
Designing and Building Parallel Programs
Also, got some interesting stuff going on with me, BZ, and multithreading, but I don't have time to go into that right now.
Friday, May 04, 2007
I Didn't Actually Win
A ways back I posted about my great amount of amusement at one of the bugs that showed up on my list at work. Obviously I never got around to posting about what I found when I actually had a chance to investigate the bug.
It turned out to be a mixture of several problems. What turned out to be happening is that the program was crashing (a simple user-mode crash; nothing fancy). However, because a user-mode debugger wasn't installed on that computer, the crash launched the kernel debugger (don't ask my why there was a kernel debugger but not a user mode debugger; I don't know). This kernel debugger, in fact, would halt the entire system and stop at a breakpoint in kernel mode code; debugging could then be done by linking the computer to another computer (the one with the debugger client) with a serial cable. So, thanks to the kernel debugger getting invoked, a common crash got elevated to a complete system halt, complete with hosed hardware.
Annoyed, I installed WinDbg on the computer, and tried it again, with the hope of finding what was crashing. The cause immediately became clear, to my further annoyance: IsBadReadPtr was throwing an access violation. For those not familiar with this function, it consists of establishing a structured exception handling frame, then reading from the supplied pointer. Normally, the access violation is caught by the exception handler and the function merely returns true. But in this case, something was catching the exception before the handler.
That something was AppVerifier - a program offered by MS to perform very strict code checks on a program. While these checks tend to whine a lot about stuff that isn't really a problem, they're helpful in that they can catch things that would normally result in a crash, often in rare circumstances (making the crash very difficult to debug). In this case, AppVerifier was catching the exception too early, and making a fuss about something that couldn't possible have resulted in a crash anyway.
Unfortunately, that wasn't the end of the matter. A quick look at the stack revealed that IsBadReadPtr was being called from an internal Windows function. As this was probably the function checking for an invalid parameter passed to an API function (and thus could potentially mean that my program was passing an invalid parameter to an API function - bad), this meant that I couldn't ignore it.
It turned out to be a bug in the GUI library our company wrote and uses (the author of that library is my arch-nemesis). The list view class contains two image list classes used for checkbox and other icons. What was happening is that, because of the poor architecture of this library (which I fight with regularly), the list view class was being destructed before the list view window itself (actually all windows are like that, in this library). This meant the destruction of all child classes, including the two image lists. Unfortunately, that list view was still USING those image lists, as the class did not unselect them from the list view window before destructing. When the dialog was closed, the list view window was destroyed, and the window attempted to free the image lists (this is the default behavior for list view windows; you can set an option to not automatically free them), and of course the image list pointers were now invalid.
Another day, another fixed bug, another few hundred calories burned laughing.
It turned out to be a mixture of several problems. What turned out to be happening is that the program was crashing (a simple user-mode crash; nothing fancy). However, because a user-mode debugger wasn't installed on that computer, the crash launched the kernel debugger (don't ask my why there was a kernel debugger but not a user mode debugger; I don't know). This kernel debugger, in fact, would halt the entire system and stop at a breakpoint in kernel mode code; debugging could then be done by linking the computer to another computer (the one with the debugger client) with a serial cable. So, thanks to the kernel debugger getting invoked, a common crash got elevated to a complete system halt, complete with hosed hardware.
Annoyed, I installed WinDbg on the computer, and tried it again, with the hope of finding what was crashing. The cause immediately became clear, to my further annoyance: IsBadReadPtr was throwing an access violation. For those not familiar with this function, it consists of establishing a structured exception handling frame, then reading from the supplied pointer. Normally, the access violation is caught by the exception handler and the function merely returns true. But in this case, something was catching the exception before the handler.
That something was AppVerifier - a program offered by MS to perform very strict code checks on a program. While these checks tend to whine a lot about stuff that isn't really a problem, they're helpful in that they can catch things that would normally result in a crash, often in rare circumstances (making the crash very difficult to debug). In this case, AppVerifier was catching the exception too early, and making a fuss about something that couldn't possible have resulted in a crash anyway.
Unfortunately, that wasn't the end of the matter. A quick look at the stack revealed that IsBadReadPtr was being called from an internal Windows function. As this was probably the function checking for an invalid parameter passed to an API function (and thus could potentially mean that my program was passing an invalid parameter to an API function - bad), this meant that I couldn't ignore it.
It turned out to be a bug in the GUI library our company wrote and uses (the author of that library is my arch-nemesis). The list view class contains two image list classes used for checkbox and other icons. What was happening is that, because of the poor architecture of this library (which I fight with regularly), the list view class was being destructed before the list view window itself (actually all windows are like that, in this library). This meant the destruction of all child classes, including the two image lists. Unfortunately, that list view was still USING those image lists, as the class did not unselect them from the list view window before destructing. When the dialog was closed, the list view window was destroyed, and the window attempted to free the image lists (this is the default behavior for list view windows; you can set an option to not automatically free them), and of course the image list pointers were now invalid.
Another day, another fixed bug, another few hundred calories burned laughing.
Campaign Finance Data
Thursday, May 03, 2007
Now What?
For those of you who haven't been watching this unfold in real time, something absolutely unprecedented is happening, right now. Several days ago, Digg.com censored several stories which referred to the AACS (the copy protection system used by HD-DVD and I believe Blu-Ray) master encryption key, which can be used to decrypt any currently available movie.
This move was in response to a cease and desist order they received from the AACS forum, threatening prosecution under the DMCA anti-circumvention clause. As this was quite a serious threat (and has a much better chance of succeeding than the RIAA suits), Digg removed all of the posts referencing the key, without acknowledging or justifying the action to users. It even went so far as to ban users who repeatedly tried to submit those stories.
This caused a massive outrage (some might call it a temper-tantrum), where users submitted thousands of stories to Digg containing the key. Some consider it an act of civil disobedience, though in this case it's the Digg operators who stand to get sued, not the people actually disobeying the DMCA, so some would consider this worse than civil disobedience. After receiving many more submissions than the Digg operators could censor, they gave in, and promised not to remove any more posts containing the key.
As a side-effect of the outrage on Digg, hundreds of thousands of web sites have been created containing the key, either in its raw form or some manner of trivial encrypted form (so that anyone who wanted to could decrypt it). This thing has blown up to such a degree that offline news sources are covering it. BBC, the New York Times, and Forbes all have stories on the Digg incident, and likely many more will follow.
This is a completely unprecedented legal situation. No one's been in the position of the AACS forum before, and nobody really knows what to do next. They could issue hundreds of thousands of cease and desist orders, followed by many law suits (for those that don't comply). While they do have a very strong case, based on the DMCA, the best they could hope for is that a few law suits could induce enough fear that all the others will take the key down before they're sued; a technique that hasn't worked so well for the RIAA. Of course it's likely that many countries wouldn't allow suits from the US based on US laws, so it's likely the key sites would just migrate out of country.
Suing Google and other search engines (which I believe they're already planning on doing) might work to a limited extent, but that would only make the key harder to find, not actually get rid of it. What's least likely, unfortunately, is that they'll roll over and die, in the face of an enemy they can only hope to impede (not defeat). They'll probably push for stronger laws, and DMCA-like laws in other countries, but that's both a very long-term strategy, and a not wholly effective one.
We'll see.
This move was in response to a cease and desist order they received from the AACS forum, threatening prosecution under the DMCA anti-circumvention clause. As this was quite a serious threat (and has a much better chance of succeeding than the RIAA suits), Digg removed all of the posts referencing the key, without acknowledging or justifying the action to users. It even went so far as to ban users who repeatedly tried to submit those stories.
This caused a massive outrage (some might call it a temper-tantrum), where users submitted thousands of stories to Digg containing the key. Some consider it an act of civil disobedience, though in this case it's the Digg operators who stand to get sued, not the people actually disobeying the DMCA, so some would consider this worse than civil disobedience. After receiving many more submissions than the Digg operators could censor, they gave in, and promised not to remove any more posts containing the key.
As a side-effect of the outrage on Digg, hundreds of thousands of web sites have been created containing the key, either in its raw form or some manner of trivial encrypted form (so that anyone who wanted to could decrypt it). This thing has blown up to such a degree that offline news sources are covering it. BBC, the New York Times, and Forbes all have stories on the Digg incident, and likely many more will follow.
This is a completely unprecedented legal situation. No one's been in the position of the AACS forum before, and nobody really knows what to do next. They could issue hundreds of thousands of cease and desist orders, followed by many law suits (for those that don't comply). While they do have a very strong case, based on the DMCA, the best they could hope for is that a few law suits could induce enough fear that all the others will take the key down before they're sued; a technique that hasn't worked so well for the RIAA. Of course it's likely that many countries wouldn't allow suits from the US based on US laws, so it's likely the key sites would just migrate out of country.
Suing Google and other search engines (which I believe they're already planning on doing) might work to a limited extent, but that would only make the key harder to find, not actually get rid of it. What's least likely, unfortunately, is that they'll roll over and die, in the face of an enemy they can only hope to impede (not defeat). They'll probably push for stronger laws, and DMCA-like laws in other countries, but that's both a very long-term strategy, and a not wholly effective one.
We'll see.
Wednesday, May 02, 2007
Transition
So, for the last year or so, I've been planning to get a new computer (maybe someday it'll actually happen...). Something close enough to top of the line that I won't need to buy another one for several years. I first got this computer I have now back in 2001, when Warcraft III was going into beta (boy, did that chew up a lot of time; kinda like when World of Warcraft came out...). At the time it had an Athlon XP 1700+ (1.47 Ghz), 512 megs PC133 RAM, and a GeForce 2 video card. I had to upgrade to 1 gig RAM for World of Warcraft, the CPU to an Athlon XP 2200+ (1.8 Ghz) when my CPU fried (thanks to the heat sink fan failing), and a friend just happened to have a GeForce 3 he didn't need anymore (and wasn't going to try to sell). With upgrades, that makes this maybe a 2002 or 2003 or so computer, which makes it about due for an upgrade (particularly considering it's a "gaming" computer). With the improved graphics in Burning Crusade (the World of Warcraft expansion pack), the average frame rate I get is about 13 FPS (down from 17 before the XP).
What I'm currently considering getting (though if I don't get a new computer till after summer, I could probably get more for the same price) is a Dual Core 2 E6600 (2.4 Ghz), 2 gigs DDR2 memory, and either a GeForce 7900 GS, Radeon X1950 PRO, or Radeon X1950 XT. In terms of raw clock rate, that CPU would be 2.67x as fast as my current one, and improvements to instruction performance (cycles per instruction) would make the number even larger. But there's a problem: I'd really only see about half of that performance (1.33x my current performance, plus instruction performance improvements). Why? Because nobody is very good at multithreading, yet.
We're currently in a transition period. We're rapidly approaching the physical cap of clock speed (it's my personal prediction that we won't see clock rates go past 5 Ghz or so, twice current speed, using transistor technology). Already it's much more practical to increase the number of cores/ALUs than increase the clock speed. That's why dual cores have become almost standard, and quad cores will become standard in the next 5 years or so (though honestly, most people - those that don't do anything CPU intensive - don't NEED a multi-core CPU).
Yet programmers aren't keeping up. This move to parallelization is recent enough that still very few programmers have the skills needed to write effective multithreaded code. That's why the Cell, with its 8 cores, is such a terror to program (and the XBox 360 CPU, with 3 cores, to a lesser extent). Some things, like web servers, where you're dealing with a lot of short, independent tasks are easy to split among many threads (not that you'd need a lot of CPU power for a web server; maybe it's a digital signature verification server or something). But can you imagine trying to split your core game logic equally into 8 threads? "Nontrivial" would be a rather dramatic understatement.
Current PC games, such as World of Warcraft (the only game I play, at the moment), are still primarily single-threaded. They may have some helper threads that do various things (a music streaming thread is an easy helper thread to make), but those threads use up very little CPU, compared to the main (single) game logic thread.
I can only hope that this will get better with time. My prediction is that in 5-10 years, the ability to break down complex tasks equally into multiple threads will become mandatory for programming positions in every company producing programs that use a significant amount of CPU (e.g. games). Unfortunately, that doesn't help me now.
Of course, to be fair, multi-core CPUs still have their uses right now. Anything that uses large numbers of threads, including several potentially CPU intensive ones, can benefit from multiple cores (assuming you don't have a gay driver that disables all but one of them; I'm looking at you, Creative!). Our company just got a dual quad-core system (8 cores in all) for its VM server (hosting many VMs). That's an excellent use, because for the most part individual threads will not consume that much CPU, and can be load-balanced well. And, of course, you'll see noticeable performance improvement if you typically run something that consumes a moderate amount of CPU in the background while you play a game (or run a second CPU-intensive program). But again, neither of those helps me :P
Finally, a recommendation. If your school offers a course on multithreading optimization, take it. Better to learn now than later, and hopefully accelerate this transition.
What I'm currently considering getting (though if I don't get a new computer till after summer, I could probably get more for the same price) is a Dual Core 2 E6600 (2.4 Ghz), 2 gigs DDR2 memory, and either a GeForce 7900 GS, Radeon X1950 PRO, or Radeon X1950 XT. In terms of raw clock rate, that CPU would be 2.67x as fast as my current one, and improvements to instruction performance (cycles per instruction) would make the number even larger. But there's a problem: I'd really only see about half of that performance (1.33x my current performance, plus instruction performance improvements). Why? Because nobody is very good at multithreading, yet.
We're currently in a transition period. We're rapidly approaching the physical cap of clock speed (it's my personal prediction that we won't see clock rates go past 5 Ghz or so, twice current speed, using transistor technology). Already it's much more practical to increase the number of cores/ALUs than increase the clock speed. That's why dual cores have become almost standard, and quad cores will become standard in the next 5 years or so (though honestly, most people - those that don't do anything CPU intensive - don't NEED a multi-core CPU).
Yet programmers aren't keeping up. This move to parallelization is recent enough that still very few programmers have the skills needed to write effective multithreaded code. That's why the Cell, with its 8 cores, is such a terror to program (and the XBox 360 CPU, with 3 cores, to a lesser extent). Some things, like web servers, where you're dealing with a lot of short, independent tasks are easy to split among many threads (not that you'd need a lot of CPU power for a web server; maybe it's a digital signature verification server or something). But can you imagine trying to split your core game logic equally into 8 threads? "Nontrivial" would be a rather dramatic understatement.
Current PC games, such as World of Warcraft (the only game I play, at the moment), are still primarily single-threaded. They may have some helper threads that do various things (a music streaming thread is an easy helper thread to make), but those threads use up very little CPU, compared to the main (single) game logic thread.
I can only hope that this will get better with time. My prediction is that in 5-10 years, the ability to break down complex tasks equally into multiple threads will become mandatory for programming positions in every company producing programs that use a significant amount of CPU (e.g. games). Unfortunately, that doesn't help me now.
Of course, to be fair, multi-core CPUs still have their uses right now. Anything that uses large numbers of threads, including several potentially CPU intensive ones, can benefit from multiple cores (assuming you don't have a gay driver that disables all but one of them; I'm looking at you, Creative!). Our company just got a dual quad-core system (8 cores in all) for its VM server (hosting many VMs). That's an excellent use, because for the most part individual threads will not consume that much CPU, and can be load-balanced well. And, of course, you'll see noticeable performance improvement if you typically run something that consumes a moderate amount of CPU in the background while you play a game (or run a second CPU-intensive program). But again, neither of those helps me :P
Finally, a recommendation. If your school offers a course on multithreading optimization, take it. Better to learn now than later, and hopefully accelerate this transition.
Tuesday, May 01, 2007
Public Service Announcement
9 hackers looking into poor security,
249 MPAA lawyers browsing porn in the silence before the storm.
17 sites spreading the news,
2 sites surviving the mass visits.
157 drops of sweat down the AACS team's cheeks,
116 frantic phone calls buzzing in the offices.
227 lawyers starting up Plan B,
There's now 91 sites to shut down.
$216 sent as bribe for the Digg staff,
still 65 sites still up and running.
86 shutdown reasons discovered by abusing the DMCA,
197 prayers one will work.
99 sites now publishing the keys... oh wait!
86 managers finding the case is slipping out of control.
136 confused MPAA members mumbling about HD-DVD keys,
192 reasons found to keep trying to stifle sales
- Jugalator
One Key to rule them all, One Key to find them, One Key to bring them all and in the darkness bind them.
- addendum by ClamIAm
249 MPAA lawyers browsing porn in the silence before the storm.
17 sites spreading the news,
2 sites surviving the mass visits.
157 drops of sweat down the AACS team's cheeks,
116 frantic phone calls buzzing in the offices.
227 lawyers starting up Plan B,
There's now 91 sites to shut down.
$216 sent as bribe for the Digg staff,
still 65 sites still up and running.
86 shutdown reasons discovered by abusing the DMCA,
197 prayers one will work.
99 sites now publishing the keys... oh wait!
86 managers finding the case is slipping out of control.
136 confused MPAA members mumbling about HD-DVD keys,
192 reasons found to keep trying to stifle sales
- Jugalator
One Key to rule them all, One Key to find them, One Key to bring them all and in the darkness bind them.
- addendum by ClamIAm
Wednesday, April 25, 2007
OS-tans
So, today I first encountered something... odd. An interesting little bit of culture (or perhaps cultural train wreck) that you really need to see for yourself (descriptions don't do it justice).
http://upload.wikimedia.org/wikipedia/en/b/b6/Ostans.jpg
http://www.wired.com/culture/design/multimedia/2007/04/gallery_mascots?slide=10&slideView=2
http://en.wikipedia.org/wiki/Os-tans
What one person has to say about things like this: http://www.doitlater.com/pic.php?121
http://upload.wikimedia.org/wikipedia/en/b/b6/Ostans.jpg
http://www.wired.com/culture/design/multimedia/2007/04/gallery_mascots?slide=10&slideView=2
http://en.wikipedia.org/wiki/Os-tans
What one person has to say about things like this: http://www.doitlater.com/pic.php?121
Friday, April 20, 2007
The Lord's Prayer - Trique
Here is the version of the Lord's Prayer in Chicahuaxtla Trique, a Mexican indian language only spoken by a couple thousand now (and may be extinct soon, as Spanish is adopted), from a 1966 Trique Bible. I've added a couple annotations indicating what some words are, but I know very little of the language, and everything I do know has come from studying this Trique Bible "studying" for a few hours) and asking my grandpa questions. Those numbers indicate tones (there are five tones in Trique, and syllables can be glides from one tone to another).
Drej3 [father of] nej3 yunj2 [us] huuin2 re'5 [you are] nne2 re'5 [you sit] xata'4a [heaven].
Ni4 [and] ga'mi4 [will speak] nej3 yunj2 [us] sisi4 [if] hua34 sa'5 [be good] nï'5 man'an2 re'5 [your body].
Ni4 [and] ga'na'5 [will arrive] re'5 [you] gui4nicaj34 re'5 son34 rian34 [on?] nej3 yunj2 [us] ruhua23 nej3 yunj2 [us].
Ni4 [and] gui4'yaj3 [will do] nej3 yunj2 [us] si3 [him?] garan'5 ruhua23 re'5 gui4'yaj3 nej3 yunj2.
Ro'2 'yaj3 nej3 si1 nne3 xata'4a hue2 daj4 gui4'yaj3 [will do] nej3 yunj2 [us] ruhua23 xumigüi5 nanj3.
Ni4 yyaj54 a'yoj3 riqui4 re'5 si3 xa23 nej3 yunj2 nda'43 ngo'ngo4 güi3.
Ni4 nicaj5 re'5 'ngo4 niman23 nico3 nga4 rian34 si-gaquïn'4 nej3 yunj2.
Dadin'34 si3 hue2 daj4 nicaj34 nej3 yunj2 'ngo4 niman23 nico3 nga4 rian34 nej3 si1 'yaj3 gaquïn'4in rian34 nej3 yunj2.
Ni4 si4 ga'ui'2 re'5 permiso si3 gadsïj3 siche3 niman23 nej3 yunj2.
Sani4 nacaj4 re'5 nej3 yunj2 rian34 si1 danj3.
Dadin'34 [because] nicaj34 niganj5 nï'5 re'5 son34.
Ni4 hua34 [there is] nucua1 re'5 [you are strong] nej3 [also].
Ni4 hua34 [there is] hue'e2 [be good] nï'5 re'5 nej3 [also].
Ni4 hue2 [yes] daj4 gahuin2 re'5 [you were] niganj5 nï'5.
Amén.
Wednesday, April 18, 2007
Super Shiny!
Well, Q has a new shiny thing to show off, and this one's a whopper (at least if you're a linguist): http://www.prayer.su/. It's a database of the Lord's Prayer in what looks like a couple hundred different languages. Some interesting samples for those not that interested in linguistics:
Classical Arabic (font required); also Arabic in Roman alphabet
Classical Armenian (font required)
Greek (font required); also Greek in Roman alphabet
Latin
Classical Chinese (font required)
Georgian (font required)
German
Hindi (font required)
Japanese (font required); also Japanese in Roman alphabet
Korean (font required)
Telugu (someone at our company speaks this; font required)
Klingon (different site)
Quenya in Roman alphabet
Sindarin in Roman alphabet
ce1000 AD Old English (not sure about font)
1384 AD Middle English
1559 AD Early Modern English
I don't really see a version of the prayer in Modern English that sounds exactly like how we actually talk. The 1963 version seems the best of the ones on that site. I'd probably write it like this:
Our Father in heaven
May Your name be honored
May Your kingdom be established
May Your will be done
On Earth as in heaven
Give us what we need for now
And forgive our sins as we forgive those who sin against us
Do not test our faith, but protect us from evil
For the kingdom, and the power, and the glory are Yours (this line was actually not present in the original version of the prayer; it was added later on)
I'm working on getting a Trique version from my grandpa, and I should be able to write a Tengwar (elven alphabet) version of the Quenya and Sindarin language versions on the site. Does anyone know Finnish? :P
Classical Arabic (font required); also Arabic in Roman alphabet
Classical Armenian (font required)
Greek (font required); also Greek in Roman alphabet
Latin
Classical Chinese (font required)
Georgian (font required)
German
Hindi (font required)
Japanese (font required); also Japanese in Roman alphabet
Korean (font required)
Telugu (someone at our company speaks this; font required)
Klingon (different site)
Quenya in Roman alphabet
Sindarin in Roman alphabet
ce1000 AD Old English (not sure about font)
1384 AD Middle English
1559 AD Early Modern English
I don't really see a version of the prayer in Modern English that sounds exactly like how we actually talk. The 1963 version seems the best of the ones on that site. I'd probably write it like this:
Our Father in heaven
May Your name be honored
May Your kingdom be established
May Your will be done
On Earth as in heaven
Give us what we need for now
And forgive our sins as we forgive those who sin against us
Do not test our faith, but protect us from evil
For the kingdom, and the power, and the glory are Yours (this line was actually not present in the original version of the prayer; it was added later on)
I'm working on getting a Trique version from my grandpa, and I should be able to write a Tengwar (elven alphabet) version of the Quenya and Sindarin language versions on the site. Does anyone know Finnish? :P
Sunday, April 15, 2007
Incompetence Weekend Extravaganza!
Well, it was a relatively uneventful weekend. Too little work, too little school, too little World of Warcraft. But there was plenty of incompetence to go around.
It's been a couple weeks since my program at work shipped (I'm a contract worker), and I haven't logged onto the company VPN after that until yesterday. I have a new project to work on, so it's about time I get started on it. I put in my user name and password into the VPN client; several seconds later, my cell phone begins to ring. It's an out of state number, although I recognized the area code as being the same area as my work. I answered it, and got a recording saying something like "please enter your PIN". The fact that my VPN login failed immediately after I hung up (having no idea what PIN they were talking about, or why I was supposed to enter it) made it seem likely that my work had switched to two-factor authentication; that is, after you enter your password, it calls your phone and asks for a second password.
So, I go into the company IRC channel (yes, it is a private, encrypted channel) and start bitching; you know, stuff like "What the **** is this PIN I'm supposed to be entering?" The reply was just as disturbing as the fact that I'd never set, nor been told, my PIN: it was e-mailed to me (in fact, it was the same for everybody)... through the company e-mail system, which is only accessible from the building or through the VPN. Brilliant, Einstein.
The solution ended up being simple and easy, though just as depressing: it appears that everyone in the company had the same default PIN (a trivial number), so it was trivial to find somebody to tell me what theirs is, and get back on the VPN. So, I log on to the VPN, and try to get to work, only to find that the VPN is totally not working, and back to World of Warcraft I went.
So today, I try again. After some more bitching in the IRC channel, Skywing helps me debug the problem. The specific problem was that the routes to the company resources were missing from my computer. Further investigation on my computer and by Skywing on the backend reveal that somebody or something (it actually turned out to be a misbehaving SQL script) had wiped the routes settings for a significant number of people (including all of the development team) on the pre-production server (the one the company uses for testing new versions not yet released to customers), which would have been propagated in turn to the computers of VPN users.
So, Skywing fixed that, and for the first time in a couple weeks I update my CVS checkout and start coding. My latest project relies on a certain third-party library which deals with routers, so I spent quite some time playing with the thing to figure out all the stuff I needed to know that wasn't in the SDK. One of the more puzzling things (when I was first starting out) was that most functions took an "encryption password" parameter. I supposed that that was the key to encrypt the router data it stores in the registry, but at the time it seemed unimportant, as the default value was NULL (suggesting it was optional).
The very first function I called returned an error code indicating invalid key. After some time of tweaking the parameters, trying to fix a variety of things that had the highest probability of being what the error was referring to, I had no luck. Naturally, the next thing I did was get out a debugger and disassembler, and started looking for the cause of the problem in the library. A number of calls to Microsoft CryptoAPI, revolving around that very encryption password, and ultimately resulting in failure, let me to the (correct) conclusion that that value was actually a password to use the library at all. While I haven't spent the time to investigate to certainty, it appears that this password is hard-coded into the library, and the library functions will fail if the proper password is not supplied. As far as I can tell, this password is unique to the copy of the library given to each company that licenses the library. That's pretty much a textbook case of putting a vault door on a straw hut, right there.
I periodically check Slashdot throughout the day, and today was no exception. Much to my continuing dismay, I find Sony doing something so phenomenally stupid that it just blows away any dumb things they've done before (rootkits, anyone?). Of course I'm talking about Sony Strikes Again. In short, Sony has rolled out a new form of DVD DRM that requires old players to receive upgraded firmware to be able to play it; of course, Sony won't have updated firmware for their own players for a few weeks after the new DVDs have already hit stores. I don't know about the real people, but if I were the CEO of Sony, I'd find the person responsible for shipping DVDs that my own players won't be able to play for weeks, fire him, and then call every single media company in Japan to tell them what he had done, ensuring that he would never work in that industry ever again.
My final piece of stupidity, if no further incidents appear while I'm writing this post (it's already happened once today - this very incident occurred while I was telling someone about the Sony incident), involved my further work with the third-party library. To it's credit, however, this wasn't a problem with the library; I merely discovered this while observing it map ports in my router. That is, I discovered that I can view ports mapped with UPnP in the web interface to my router, as well as what programs opened them. This discovery showed me that Windows Live Messenger, for the purpose of direct file sends (of which I've not made any since Messenger was started today), had mapped 39,538 ports to my computer, and was holding them until it was closed. I think that really speaks for itself, so I won't comment additionally on it.
It's been a couple weeks since my program at work shipped (I'm a contract worker), and I haven't logged onto the company VPN after that until yesterday. I have a new project to work on, so it's about time I get started on it. I put in my user name and password into the VPN client; several seconds later, my cell phone begins to ring. It's an out of state number, although I recognized the area code as being the same area as my work. I answered it, and got a recording saying something like "please enter your PIN". The fact that my VPN login failed immediately after I hung up (having no idea what PIN they were talking about, or why I was supposed to enter it) made it seem likely that my work had switched to two-factor authentication; that is, after you enter your password, it calls your phone and asks for a second password.
So, I go into the company IRC channel (yes, it is a private, encrypted channel) and start bitching; you know, stuff like "What the **** is this PIN I'm supposed to be entering?" The reply was just as disturbing as the fact that I'd never set, nor been told, my PIN: it was e-mailed to me (in fact, it was the same for everybody)... through the company e-mail system, which is only accessible from the building or through the VPN. Brilliant, Einstein.
The solution ended up being simple and easy, though just as depressing: it appears that everyone in the company had the same default PIN (a trivial number), so it was trivial to find somebody to tell me what theirs is, and get back on the VPN. So, I log on to the VPN, and try to get to work, only to find that the VPN is totally not working, and back to World of Warcraft I went.
So today, I try again. After some more bitching in the IRC channel, Skywing helps me debug the problem. The specific problem was that the routes to the company resources were missing from my computer. Further investigation on my computer and by Skywing on the backend reveal that somebody or something (it actually turned out to be a misbehaving SQL script) had wiped the routes settings for a significant number of people (including all of the development team) on the pre-production server (the one the company uses for testing new versions not yet released to customers), which would have been propagated in turn to the computers of VPN users.
So, Skywing fixed that, and for the first time in a couple weeks I update my CVS checkout and start coding. My latest project relies on a certain third-party library which deals with routers, so I spent quite some time playing with the thing to figure out all the stuff I needed to know that wasn't in the SDK. One of the more puzzling things (when I was first starting out) was that most functions took an "encryption password" parameter. I supposed that that was the key to encrypt the router data it stores in the registry, but at the time it seemed unimportant, as the default value was NULL (suggesting it was optional).
The very first function I called returned an error code indicating invalid key. After some time of tweaking the parameters, trying to fix a variety of things that had the highest probability of being what the error was referring to, I had no luck. Naturally, the next thing I did was get out a debugger and disassembler, and started looking for the cause of the problem in the library. A number of calls to Microsoft CryptoAPI, revolving around that very encryption password, and ultimately resulting in failure, let me to the (correct) conclusion that that value was actually a password to use the library at all. While I haven't spent the time to investigate to certainty, it appears that this password is hard-coded into the library, and the library functions will fail if the proper password is not supplied. As far as I can tell, this password is unique to the copy of the library given to each company that licenses the library. That's pretty much a textbook case of putting a vault door on a straw hut, right there.
I periodically check Slashdot throughout the day, and today was no exception. Much to my continuing dismay, I find Sony doing something so phenomenally stupid that it just blows away any dumb things they've done before (rootkits, anyone?). Of course I'm talking about Sony Strikes Again. In short, Sony has rolled out a new form of DVD DRM that requires old players to receive upgraded firmware to be able to play it; of course, Sony won't have updated firmware for their own players for a few weeks after the new DVDs have already hit stores. I don't know about the real people, but if I were the CEO of Sony, I'd find the person responsible for shipping DVDs that my own players won't be able to play for weeks, fire him, and then call every single media company in Japan to tell them what he had done, ensuring that he would never work in that industry ever again.
My final piece of stupidity, if no further incidents appear while I'm writing this post (it's already happened once today - this very incident occurred while I was telling someone about the Sony incident), involved my further work with the third-party library. To it's credit, however, this wasn't a problem with the library; I merely discovered this while observing it map ports in my router. That is, I discovered that I can view ports mapped with UPnP in the web interface to my router, as well as what programs opened them. This discovery showed me that Windows Live Messenger, for the purpose of direct file sends (of which I've not made any since Messenger was started today), had mapped 39,538 ports to my computer, and was holding them until it was closed. I think that really speaks for itself, so I won't comment additionally on it.
Friday, April 06, 2007
Why CDDL?
So, for those of you who aren't on the modding community sites I used to frequent (and now visit every so often), I've decided to open-source the legendary MPQDraft (yes, it was an April Fools' prank - that nobody would believe it when they saw the announcement). This will require that I get the whole thing cleaned up and commented, so that I can get it uploaded to SourceForge. After that I really should finish the rather large changes I'm in the middle of making to LibQ, and put it up on SourceForge, as well. Both of these are/will be licensed under the Sun Common Development and Distribution License, so I thought I should explain why I chose this license, as opposed to the more common ones.
There are really only two rules motivating my selection of license. First, as I'm making my code available for public use and reuse, I want to make it available and useful to as many people as possible. Obviously, this means placing as few restrictions on use as possible. I didn't want to limit it to eyes only or noncommercial use only projects. I want people to be able to use the code in open source, closed source, and commercial programs alike.
However, it also implies something else. By open-sourcing my code I can ensure that other people have access to that code. But what if somebody takes my code and improves it? Of course, I'd want others to be able to make use of those improvements as well, or perhaps even merge it back into my original project. This means that, regardless of what programs people use my code in, they have to play by the rules of the code itself. I want a guarantee that any improvements or modifications people make to my open source code are also released as open source. This covers just my code and any additions/modifications that are a functional part of the code I wrote; it doesn't have anything to do with any code developed entirely separately, which just happens to be compiled along with my code in the same program.
Second, I want credit to be given for the use of my code. If not to me, then at least to the project itself. Besides the obvious reason of attribution, this serves to promote the project and increase exposure to it, bringing more potential users. This connects back to wanting as many people as possible to be able to benefit from my code. And, importantly, this is an entirely unrestrictive requirement (can you imagine somebody who would rather not use something that would be useful to them than to put one line in the credits?)
So, those are the basic principles. Next, let me point out why I didn't choose some of the more common licenses. First up is the Do What the Fuck You Want To Public License. It should be obvious why this one fails: it meets neither of my two objectives. There is no guarantee that credit will be given for the use of the code, or that changes will be made available to the public. I actually had never heard of this license (which might as well not be a license at all) before today; I'm just mentioning it because it illustrates why I wanted a license :P
Next is the overly popular General Public License. In my opinion, this is a rather obnoxious license, for the reason that it's as much about politics as it is about legality. While it guarantees that the code will remain free for use, it also guarantees that any programs using the code be free, and publicly available under the GPL itself. This is obnoxious because it means that only free/open source software (FOSS) may make use of GPL code. However, for a rather intimidating majority of the market, FOSS is not a feasible business model, and as such a majority of potential users are promptly excluded. This makes the GPL an extremely restrictive license, and completely at odds with my goals.
Next up is the Lesser General Public License (LGPL). This one came pretty close to meeting my requirements, but not quite close enough. The LGPL lacks the more draconian of restrictions in the GPL, allowing you to link it to code not licensed under the LGPL. While this might leave hope for it being useful to commercial software writers, there were two specific clauses that prompted me to reject it. First, some restrictions on linking to LGPL code make it impractical for closed source programs (and commercial programs even more so) to use LGPL code, if the LGPL code is not completely self-contained (e.g. a DLL that the program links to). This means that the LGPL only could satisfy my requirements if I were releasing a stand-alone library, and not an executable, as I am with MPQDraft.
Second, the LGPL allows modifications to the code to be released not under the LGPL, but under the GPL itself, which would further restrict the use of the code. This means that someone modifying my code would be able prevent people who can use my code from using their modifications to my code. This directly contradicts my ideal of maximum collective benefit from my code.
Finally, there's the BSD license. While this license guarantees attribution (if perhaps to a controversially strong degree) and allows anyone to use my code, it offers no guarantee that modifications or improvements to my code will also be made publicly available. As such, it violates my principle of maximum collective benefit in exactly the opposite way the GPL does; just the same, the BSD license is out.
Lastly, let me give a brief summary of the CDDL, as I intend it:
- You may use the licensed code in whole (the entire program) or in part (individual source files, functions, or methods) in any program you desire, regardless of the license of the program as a whole (or rather, as excluding the code you are borrowing). The program itself may be open or closed source, free or commercial.
- However, in all cases, any modifications, improvements, or additions to the CDDL code (any code that is referenced in direct modifications to the CDDL code is considered an addition to the CDDL code, and so is bound by this requirement; e.g. a modification of a math function to use a fast lookup table makes that table itself an addition to the CDDL code, regardless of whether it's in a source code file of its own) must be made publicly and freely available in source, under the CDDL license itself.
- In any program (source or binary) that uses CDDL code, recognition must be given to the source (either project or author) of the CDDL code. As well, modifications to the CDDL code (which must be distributed as source) may not remove notices indicating the ancestry of the code.
Man that turned out to be a long post.
There are really only two rules motivating my selection of license. First, as I'm making my code available for public use and reuse, I want to make it available and useful to as many people as possible. Obviously, this means placing as few restrictions on use as possible. I didn't want to limit it to eyes only or noncommercial use only projects. I want people to be able to use the code in open source, closed source, and commercial programs alike.
However, it also implies something else. By open-sourcing my code I can ensure that other people have access to that code. But what if somebody takes my code and improves it? Of course, I'd want others to be able to make use of those improvements as well, or perhaps even merge it back into my original project. This means that, regardless of what programs people use my code in, they have to play by the rules of the code itself. I want a guarantee that any improvements or modifications people make to my open source code are also released as open source. This covers just my code and any additions/modifications that are a functional part of the code I wrote; it doesn't have anything to do with any code developed entirely separately, which just happens to be compiled along with my code in the same program.
Second, I want credit to be given for the use of my code. If not to me, then at least to the project itself. Besides the obvious reason of attribution, this serves to promote the project and increase exposure to it, bringing more potential users. This connects back to wanting as many people as possible to be able to benefit from my code. And, importantly, this is an entirely unrestrictive requirement (can you imagine somebody who would rather not use something that would be useful to them than to put one line in the credits?)
So, those are the basic principles. Next, let me point out why I didn't choose some of the more common licenses. First up is the Do What the Fuck You Want To Public License. It should be obvious why this one fails: it meets neither of my two objectives. There is no guarantee that credit will be given for the use of the code, or that changes will be made available to the public. I actually had never heard of this license (which might as well not be a license at all) before today; I'm just mentioning it because it illustrates why I wanted a license :P
Next is the overly popular General Public License. In my opinion, this is a rather obnoxious license, for the reason that it's as much about politics as it is about legality. While it guarantees that the code will remain free for use, it also guarantees that any programs using the code be free, and publicly available under the GPL itself. This is obnoxious because it means that only free/open source software (FOSS) may make use of GPL code. However, for a rather intimidating majority of the market, FOSS is not a feasible business model, and as such a majority of potential users are promptly excluded. This makes the GPL an extremely restrictive license, and completely at odds with my goals.
Next up is the Lesser General Public License (LGPL). This one came pretty close to meeting my requirements, but not quite close enough. The LGPL lacks the more draconian of restrictions in the GPL, allowing you to link it to code not licensed under the LGPL. While this might leave hope for it being useful to commercial software writers, there were two specific clauses that prompted me to reject it. First, some restrictions on linking to LGPL code make it impractical for closed source programs (and commercial programs even more so) to use LGPL code, if the LGPL code is not completely self-contained (e.g. a DLL that the program links to). This means that the LGPL only could satisfy my requirements if I were releasing a stand-alone library, and not an executable, as I am with MPQDraft.
Second, the LGPL allows modifications to the code to be released not under the LGPL, but under the GPL itself, which would further restrict the use of the code. This means that someone modifying my code would be able prevent people who can use my code from using their modifications to my code. This directly contradicts my ideal of maximum collective benefit from my code.
Finally, there's the BSD license. While this license guarantees attribution (if perhaps to a controversially strong degree) and allows anyone to use my code, it offers no guarantee that modifications or improvements to my code will also be made publicly available. As such, it violates my principle of maximum collective benefit in exactly the opposite way the GPL does; just the same, the BSD license is out.
Lastly, let me give a brief summary of the CDDL, as I intend it:
- You may use the licensed code in whole (the entire program) or in part (individual source files, functions, or methods) in any program you desire, regardless of the license of the program as a whole (or rather, as excluding the code you are borrowing). The program itself may be open or closed source, free or commercial.
- However, in all cases, any modifications, improvements, or additions to the CDDL code (any code that is referenced in direct modifications to the CDDL code is considered an addition to the CDDL code, and so is bound by this requirement; e.g. a modification of a math function to use a fast lookup table makes that table itself an addition to the CDDL code, regardless of whether it's in a source code file of its own) must be made publicly and freely available in source, under the CDDL license itself.
- In any program (source or binary) that uses CDDL code, recognition must be given to the source (either project or author) of the CDDL code. As well, modifications to the CDDL code (which must be distributed as source) may not remove notices indicating the ancestry of the code.
Man that turned out to be a long post.
Tuesday, March 06, 2007
Work, Work
Well, I appear to be in the fairly enviable position of having too many job offers (all but one of which being unsolicited - kind of) for the summer (and beyond). There are (if no more drop in by then) four "possibilities" (loose usage of the word).
The first of which is a summer internship at City of Hope. This would make a great resume-buff-upper, and may be educational, doing real research at a real medical research facility. However, I'm betting it wouldn't at all be like some of the classes I actually enjoyed going to at school (microbiology and immunology come readily to mind; I actually would enjoy being in class, though not so much the labs, homework, and tests), and I suspect it'd probably be nothing more than some mind-numbingly boring thing like running gels all day long for somebody or other's experiment (a typical entry-level biology job). Ultimately, I decided against this, based on the presence of more interesting possibilities, and the fact that, unlike all the others, I'd actually have to formally apply (and competition is fierce - only like 1 in 50 applicants get internships).
Next is the company I worked for last summer, and have been working a little bit for over the school year. As far as I'm aware, they still want me back, next summer and/or full time in the future. It's a really nice place to work for, though it's either the #2 or #3 spot on the list for most interesting/appealing work.
Next is... let's call them Company X (saying which would only incite replies of "WTF liar!" and "Bastard, I want to work there!"). As that implies, this is undoubtedly the most interesting and potentially fun job prospect (although I have no idea what the work environment is like). Last summer I got an "invitation" to work for this company, when I was sending my semi-regular research to a friend there, who is a programmer (thus, it wasn't a formal invitation, though as he has some sway, I would surely have a much better chance of getting hired than the average applicant). Unfortunately, it took almost a month to get an interview set up for me (it's not his fault, either. I sent him ping e-mails once or twice a week, and all he could tell me was that they haven't responded to him yet), and by that time I'd given up waiting, and was already in Kansas, working for my current company (the main reason I didn't wait longer was because I'd already told my company that I'd work for them, if the thing with Company X didn't work out, and I didn't want to make them wait any longer than I already had). This is probably my #1 consideration for what to do when I finish college; however, I'll probably put off trying again until I finish college, and just apply for a full-time position (rather than just summer work).
Finally, tonight my computer architecture II (senior-level class) teacher scouted me out for a future project somehow relating to him. He hasn't told me much yet, just that it involves something about computer simulation of neuro-something or other (maybe neural networks, or some such). This one could really disturb my plans of going back to Kansas this summer, if the project turns out to be interesting (when I learn more about it) and there's a monetary advantage to doing it, instead (since I wouldn't need to pay rent out of my earnings, like I would in Kansas).
So... I'm not at all sure what I'm gonna do this summer. As of right now I'm planning on going back to Kansas; but if there's a monetary advantage to taking the job with my teacher (and the job is interesting), I might be inclined to do that, instead. Time will tell...
The first of which is a summer internship at City of Hope. This would make a great resume-buff-upper, and may be educational, doing real research at a real medical research facility. However, I'm betting it wouldn't at all be like some of the classes I actually enjoyed going to at school (microbiology and immunology come readily to mind; I actually would enjoy being in class, though not so much the labs, homework, and tests), and I suspect it'd probably be nothing more than some mind-numbingly boring thing like running gels all day long for somebody or other's experiment (a typical entry-level biology job). Ultimately, I decided against this, based on the presence of more interesting possibilities, and the fact that, unlike all the others, I'd actually have to formally apply (and competition is fierce - only like 1 in 50 applicants get internships).
Next is the company I worked for last summer, and have been working a little bit for over the school year. As far as I'm aware, they still want me back, next summer and/or full time in the future. It's a really nice place to work for, though it's either the #2 or #3 spot on the list for most interesting/appealing work.
Next is... let's call them Company X (saying which would only incite replies of "WTF liar!" and "Bastard, I want to work there!"). As that implies, this is undoubtedly the most interesting and potentially fun job prospect (although I have no idea what the work environment is like). Last summer I got an "invitation" to work for this company, when I was sending my semi-regular research to a friend there, who is a programmer (thus, it wasn't a formal invitation, though as he has some sway, I would surely have a much better chance of getting hired than the average applicant). Unfortunately, it took almost a month to get an interview set up for me (it's not his fault, either. I sent him ping e-mails once or twice a week, and all he could tell me was that they haven't responded to him yet), and by that time I'd given up waiting, and was already in Kansas, working for my current company (the main reason I didn't wait longer was because I'd already told my company that I'd work for them, if the thing with Company X didn't work out, and I didn't want to make them wait any longer than I already had). This is probably my #1 consideration for what to do when I finish college; however, I'll probably put off trying again until I finish college, and just apply for a full-time position (rather than just summer work).
Finally, tonight my computer architecture II (senior-level class) teacher scouted me out for a future project somehow relating to him. He hasn't told me much yet, just that it involves something about computer simulation of neuro-something or other (maybe neural networks, or some such). This one could really disturb my plans of going back to Kansas this summer, if the project turns out to be interesting (when I learn more about it) and there's a monetary advantage to doing it, instead (since I wouldn't need to pay rent out of my earnings, like I would in Kansas).
So... I'm not at all sure what I'm gonna do this summer. As of right now I'm planning on going back to Kansas; but if there's a monetary advantage to taking the job with my teacher (and the job is interesting), I might be inclined to do that, instead. Time will tell...
Monday, January 22, 2007
Identity Theft?
This is a bit disturbing. I just received a registered survey from the Democratic National Committee. A few assorted lines from the thing:
"You have been selected to represent your city in the 2007 Grassroots Survey of Democratic Leaders. Survey documents registered in your name are enclosed."
"Dear Fellow Democrat,
...
I am asking you to take part in this survey because, as a Democratic leader in your community, your insights about the critical issues facing our nation are important to us."
This is disturbing because, in fact, I am not registered with any party, am not a political leader of any kind, and am not even registered to vote right now. It makes me wonder who's been voting under my name...
"You have been selected to represent your city in the 2007 Grassroots Survey of Democratic Leaders. Survey documents registered in your name are enclosed."
"Dear Fellow Democrat,
...
I am asking you to take part in this survey because, as a Democratic leader in your community, your insights about the critical issues facing our nation are important to us."
This is disturbing because, in fact, I am not registered with any party, am not a political leader of any kind, and am not even registered to vote right now. It makes me wonder who's been voting under my name...
Sunday, January 14, 2007
The Rules of Slashdot
Saw this post on Slashdot, and thought it was humorous:
1. We love Apple (especially when they do something just like Microsoft, and even more if their product is vaporware).
2. We hate Microsoft (especially when they do something just like Apple, and even more when their product is vaporware).
3. Steve Jobs can do no wrong (especially when he does the same as Bill Gates).
4. Bill Gates can do no right (especially when he does the same as Steve Jobs).
5. Any story that is positive about Bill Gates or Microsoft will get tagged "fud" or "troll".
6. Any story that is negative about Steve Jobs or Apple will get tagged "fud" or "troll".
7. "One Laptop Per Child" is the second coming of Christ.
8. Nicholas Negroponte is Christ.
9. We ignore Sun (especially when they dominate any specific industry).
10. We adore Java (even though it was developed by Sun).
11. It has been "The Year That Linux Takes Over the Desktop" for about 8 years.
12. It has been "The Year That Microsoft Dies" for about 15 years.
13. It has been "The Year That Apple Overtakes Microsoft" for about 10 years.
14. Ubuntu is God's chosen Linux distribution.
15. All other distributions of Linux are wannabes...especially the ones that have been around longer than Ubuntu.
Friday, January 12, 2007
I Win
So, yesterday my program at work (a configuration tool for their server product) went into official Q/A, and I've acquired a list of bugs (six so far). Some of these are absolutely hysterical. Take this one, for instance:
I was laughing out loud for about 20 minutes straight after I read that bug report. Besides the obvious hilarity of a single computer downing an entire subnet, my program runs entirely in user mode, and it would be a huge security hole in the OS if a user-mode program could wreck this kind of havoc. I suspect this is actually a bug in the server (which has a driver component) or the backend (which feeds instructions to the server), though I haven't started investigating, yet.
On two of the different servers we were setting up for our test networks, the computers froze after clicking finish with the connect now checkbox checked. This happened on both servers that made it that far.
One of the servers that froze seems to have completely screwed up the subnet it was on until it was unplugged from that router. In other words, workstations on the same subnet could not pass traffic through the router or renew their IP address from the dhcp server until the computer was unplugged from the router.
I was laughing out loud for about 20 minutes straight after I read that bug report. Besides the obvious hilarity of a single computer downing an entire subnet, my program runs entirely in user mode, and it would be a huge security hole in the OS if a user-mode program could wreck this kind of havoc. I suspect this is actually a bug in the server (which has a driver component) or the backend (which feeds instructions to the server), though I haven't started investigating, yet.
Tricks of the Trade - Collocation
Way, way back I explained what "fast" is, with regards to synchronization objects. Briefly, a fast object is one that executes entirely in user mode, save for two times: when a thread needs to go to sleep, and when a thread needs to be woken up.
But that isn't fast enough for some people. As discussed previously, fast objects work by using atomic instructions and/or memory barriers. While atomic instructions in and of themselves aren't THAT bad, speed-wise (in the best case taking only about 20 cycles), on some architectures (like x86) they imply either a write barrier or a full barrier. By definition these are constriction points, which bring the various parts of the system into sync, and require waiting for all pending writes/operations to complete. In the best case (no queued I/O) this may be almost instant. In the worst case (many queued I/O accesses), it may take hundreds of cycles. Even though this only applies to one CPU/core, that's a pretty large amount of dead time (for example, you might be able to call malloc in that time).
But is it possible to avoid the use of atomic operations altogether? Well, yes and no. It's impossible to have a multiprocessing system that shares resources completely without atomic operations (well, I suppose you could, but it would be hideously ugly and slow). There must be some way to synchronize code or data between threads and processors - atomic operations provide this ability.
However, in very specialized circumstances (and only from some threads), we can get around using atomic operations. One way to achieve this is called collocation. Collocation is the storage of two (or more) pieces of data - one accessed by one thread, the other accessed by another thread - inside a single word. The thread's data is written to using a small write, then the entire word is read at once.
Collocation relies on data dependency to cause a partial processor stall without the need to perform a full memory barrier. Most processors are always self-consistent and have instruction ordering rules that state that a write to a memory location smaller than a word must be committed to memory (actually, cache, but CPU caches are typically coherent, meaning all CPUs will see modifications to the cache of one CPU) before a larger read from that same location. This can be done using nonatomic operations, and does not require a memory barrier - it forces ordering only on two instructions, while allowing the processor to optimally reorder and buffer all other instructions. In the worst case, this causes a full pipeline flush (20-30 cycles), and may take less - significantly faster than a full memory barrier, in the worst case.
However, this method is not an exact substitute for atomic instructions. It only ensures that both writing and reading threads will see the writes made by each other - it does not provide a way for either thread to know in what order the writes occurred, the way atomic instructions can. So, what use is it? Well, if you apply some creativity, it's still useful in some cases. To be able to take advantage of collocation, the threads sharing data must be fundamentally asymmetric - each thread must write to a separate fields in the word, and only one thread may use collocation to avoid atomic operations (the other threads must use atomic operations). This implies where collocation is useful: when one thread performs a large portion of the writes, and other threads only make occasional writes.
This is just an introduction to collocation as a lock-free structure tool; the posts on super-fast mutexes and condition variables with timeout will give some real-world examples of how atomic operations can be avoided using collocation.
But that isn't fast enough for some people. As discussed previously, fast objects work by using atomic instructions and/or memory barriers. While atomic instructions in and of themselves aren't THAT bad, speed-wise (in the best case taking only about 20 cycles), on some architectures (like x86) they imply either a write barrier or a full barrier. By definition these are constriction points, which bring the various parts of the system into sync, and require waiting for all pending writes/operations to complete. In the best case (no queued I/O) this may be almost instant. In the worst case (many queued I/O accesses), it may take hundreds of cycles. Even though this only applies to one CPU/core, that's a pretty large amount of dead time (for example, you might be able to call malloc in that time).
But is it possible to avoid the use of atomic operations altogether? Well, yes and no. It's impossible to have a multiprocessing system that shares resources completely without atomic operations (well, I suppose you could, but it would be hideously ugly and slow). There must be some way to synchronize code or data between threads and processors - atomic operations provide this ability.
However, in very specialized circumstances (and only from some threads), we can get around using atomic operations. One way to achieve this is called collocation. Collocation is the storage of two (or more) pieces of data - one accessed by one thread, the other accessed by another thread - inside a single word. The thread's data is written to using a small write, then the entire word is read at once.
Collocation relies on data dependency to cause a partial processor stall without the need to perform a full memory barrier. Most processors are always self-consistent and have instruction ordering rules that state that a write to a memory location smaller than a word must be committed to memory (actually, cache, but CPU caches are typically coherent, meaning all CPUs will see modifications to the cache of one CPU) before a larger read from that same location. This can be done using nonatomic operations, and does not require a memory barrier - it forces ordering only on two instructions, while allowing the processor to optimally reorder and buffer all other instructions. In the worst case, this causes a full pipeline flush (20-30 cycles), and may take less - significantly faster than a full memory barrier, in the worst case.
However, this method is not an exact substitute for atomic instructions. It only ensures that both writing and reading threads will see the writes made by each other - it does not provide a way for either thread to know in what order the writes occurred, the way atomic instructions can. So, what use is it? Well, if you apply some creativity, it's still useful in some cases. To be able to take advantage of collocation, the threads sharing data must be fundamentally asymmetric - each thread must write to a separate fields in the word, and only one thread may use collocation to avoid atomic operations (the other threads must use atomic operations). This implies where collocation is useful: when one thread performs a large portion of the writes, and other threads only make occasional writes.
This is just an introduction to collocation as a lock-free structure tool; the posts on super-fast mutexes and condition variables with timeout will give some real-world examples of how atomic operations can be avoided using collocation.
Monday, January 08, 2007
Tools of the Trade - Atomic Primitives
In the wake of the recent memory barriers series, today we continue looking at topics related to multiprogramming, by taking a survey of the various atomic primitives. This particular topic is more for informational value than practical use (at least as far as LibQ is concerned, which does not support all of theseso you do not need to know the differences).
Atomic primitives are arguably the most important tool in programming that requires coordination between multiple threads and/or processors/cores. There are four basic types of atomic primitives: swap, fetch and phi, compare and swap, and load linked/store conditional. Usually these operations are performed on values the same size as or smaller than a word (the size of the processor's registers), though sometimes consecutive (single address) multiword versions are provided.
The most primitive (pun not intended) is the swap operation. This operation exchanges a value in memory with a value in a register, atomically setting the value in memory and returning the original value in memory. This is not actually very useful, in terms of multiprogramming, with only a single practical use: the construction of test and set (TAS; or test and test and set - TATAS) spinlocks. In these spinlocks, each thread attempting to enter the spinlock spins, exchanging 1 into the spinlock value in each iteration. If 0 is returned, the spinlock was free, and the thread now owns the spinlock; if 1 is returned, the spinlock was already owned by another thread, and the thread attempting to enter the spinlock must keep spinning. Ultimately, the owning thread leaves the spinlock by setting the spinlock value to 0.
This makes for an extremely crude spinlock. The fact that there is only a single value all threads share means that spinning can create a lot of cache coherency traffic, as all spinning processors will be writing to the same address, continually invalidating each other's caches. Furthermore, this mechanism precludes any kind of order preservation, as it's impossible to distinguish when a given thread began waiting; threads may enter the spinlock in any order, regardless of how long any thread has been waiting to enter the spinlock.
Next up the power scale is the fetch and phi family. All members of this family follow the same basic process: a value is atomically read from memory, modified by the processor, and written back, with the original value returned to the program. The modification performed can be almost anything; one of the most useful modifications is the add operation (in this case it's called fetch and add). The fetch and add operation is notably more useful than the swap operation, but is still less than ideal; in addition to test and set spinlocks, fetch and add can be used to create thread-safe counters, and spinlocks that both preserve order and (potentially) greatly reduce cache coherency traffic.
Another universal atomic primitive is the load linked/store conditional (LL/SC) pair of instructions. In this model, when a value is loaded linked into a register, a reservation is placed on that memory address. If that reservation still exists when the store conditional operation is performed, the store will be performed. If another thread writes to the memory location between a load linked and store conditional, the reservation is cleared, and any other threads will fail their store conditional (resulting in skipping the store altogether). If the store conditional fails, the program must loop back and try the operation again, beginning with the load linked.
In theory, the load linked/store conditional primitive is superior to the compare and swap operation. As any access to the memory address will clear the reservations of other processors, the total number of reads is 1, in contrast to the 2 reads with compare and swap (1 read to get the value initially, and a second read to verify the value is unchanged). Furthermore, the LL/SC operation may distinguish whether a write has occurred, regardless of whether the value was changed by the write (we'll come back to why this is a good thing when we discuss hazard pointers). Unfortunately, my research indicates that most implementations of LL/SC do not guarantee that a write will be distinguished if the written value is the same as the value at the time of the reserve.
Finally, the wild card: the double compare and swap (DCAS). In a double compare and swap, the compare and swap operation is performed simultaneously on the values in two memory addresses. Obviously this provides dramatically more power than any previous operation, which only operate on single addresses. Unfortunately, support for this primitive is extremely rare in real-world processors, and it is typically only used by lock-free algorithm designers that are unable to reduce their algorithm to single-address compare and swap operations.
Atomic primitives are arguably the most important tool in programming that requires coordination between multiple threads and/or processors/cores. There are four basic types of atomic primitives: swap, fetch and phi, compare and swap, and load linked/store conditional. Usually these operations are performed on values the same size as or smaller than a word (the size of the processor's registers), though sometimes consecutive (single address) multiword versions are provided.
The most primitive (pun not intended) is the swap operation. This operation exchanges a value in memory with a value in a register, atomically setting the value in memory and returning the original value in memory. This is not actually very useful, in terms of multiprogramming, with only a single practical use: the construction of test and set (TAS; or test and test and set - TATAS) spinlocks. In these spinlocks, each thread attempting to enter the spinlock spins, exchanging 1 into the spinlock value in each iteration. If 0 is returned, the spinlock was free, and the thread now owns the spinlock; if 1 is returned, the spinlock was already owned by another thread, and the thread attempting to enter the spinlock must keep spinning. Ultimately, the owning thread leaves the spinlock by setting the spinlock value to 0.
This makes for an extremely crude spinlock. The fact that there is only a single value all threads share means that spinning can create a lot of cache coherency traffic, as all spinning processors will be writing to the same address, continually invalidating each other's caches. Furthermore, this mechanism precludes any kind of order preservation, as it's impossible to distinguish when a given thread began waiting; threads may enter the spinlock in any order, regardless of how long any thread has been waiting to enter the spinlock.
Next up the power scale is the fetch and phi family. All members of this family follow the same basic process: a value is atomically read from memory, modified by the processor, and written back, with the original value returned to the program. The modification performed can be almost anything; one of the most useful modifications is the add operation (in this case it's called fetch and add). The fetch and add operation is notably more useful than the swap operation, but is still less than ideal; in addition to test and set spinlocks, fetch and add can be used to create thread-safe counters, and spinlocks that both preserve order and (potentially) greatly reduce cache coherency traffic.
- ATOMIC word fetch_and_add(volatile word &value, word addend)
- {
- word oldValue = value;
- value += addend;
- return oldValue;
- }
- void EnterSpinlock (volatile word &seq, volatile word &cur)
- {
- word mySeq = fetch_and_add(seq, 1);
- while (cur != mySeq) {}
- }
- void LeaveSpinlock(volatile word &cur)
- {
- cur++;
- }
- ATOMIC word compare_and_swap(volatile word &value, word newValue, word comparand)
- {
- word oldValue = value;
- if (oldValue == comparand)
- value = newValue;
- return oldValue;
- }
Another universal atomic primitive is the load linked/store conditional (LL/SC) pair of instructions. In this model, when a value is loaded linked into a register, a reservation is placed on that memory address. If that reservation still exists when the store conditional operation is performed, the store will be performed. If another thread writes to the memory location between a load linked and store conditional, the reservation is cleared, and any other threads will fail their store conditional (resulting in skipping the store altogether). If the store conditional fails, the program must loop back and try the operation again, beginning with the load linked.
In theory, the load linked/store conditional primitive is superior to the compare and swap operation. As any access to the memory address will clear the reservations of other processors, the total number of reads is 1, in contrast to the 2 reads with compare and swap (1 read to get the value initially, and a second read to verify the value is unchanged). Furthermore, the LL/SC operation may distinguish whether a write has occurred, regardless of whether the value was changed by the write (we'll come back to why this is a good thing when we discuss hazard pointers). Unfortunately, my research indicates that most implementations of LL/SC do not guarantee that a write will be distinguished if the written value is the same as the value at the time of the reserve.
Finally, the wild card: the double compare and swap (DCAS). In a double compare and swap, the compare and swap operation is performed simultaneously on the values in two memory addresses. Obviously this provides dramatically more power than any previous operation, which only operate on single addresses. Unfortunately, support for this primitive is extremely rare in real-world processors, and it is typically only used by lock-free algorithm designers that are unable to reduce their algorithm to single-address compare and swap operations.
- ATOMIC void double_compare_and_swap(volatile word &value1, word newValue1, word comparand1, word &oldValue1, volatile word &value2, word newValue2, word comparand2, word &oldValue2)
- {
- oldValue1 = value1;
- oldValue2 = value2;
- if (oldValue1 == comparand1 && oldValue2 == comparand2)
- {
- value1 = newValue1;
- value2 = newValue2;
- }
- }
Thursday, January 04, 2007
Philosophers at a Table
Creating a deadlock-free semaphore-based implementation of the dining philosopher problem isn't particularly difficult. All you need to do is implement a chopstick pickup order that does not allow deadlock. The method we used (although you could just as easily do the opposite) is to have each philosopher pick up their even-numbered chopstick first, then their odd-numbered chopstick afterwards. This guarantees that, regardless of the number of philosophers n at the table (as long as there're two chopsticks, smartass), at least one will be able to eat at any point, with a maximum of n / 2 (rounded down) being able to eat at once.
I initially thought (and indeed said in my report) that the condition we were seeing, where only one of five philosophers was able to eat, was a consequence of there being an odd number of philosophers. While I was correct that the odd number had an important part in what we were seeing, the problem was more general than I thought. This diagram of an eight-philosopher table shows the worst case scenario for an even number of philosophers:
What's happening here is as follows:
1. Philosopher 0 picks up chopsticks 0 and 1, and begins eating
2. Philosopher 1 picks up chopstick 2, and blocks on chopstick 1
3. Philosopher 2 blocks on chopstick 2
4. Philosopher 7 blocks on chopstick 0
In this order (or a few variations of it), one philosopher has managed to prevent three others in a cluster from eating. The exact same method can be used to block three others, while a total of two philosophers eat; this is the worst-case scenario for this table.
You can draw it out for yourself (I drew it on paper, along with several other sizes, but don't feel like making more diagrams online) and prove that it's possible for a minimum of two philosophers to eat at a table with only six philosophers. This is logical: one philosopher can only block three others, leaving three chopsticks available; one of the last two philosophers will be able to eat.
So, four philosophers is too few (for two philosophers to eat), six is enough, but what about five? This was the classic case, and the one we implemented. What happened is this, shown in words and figure:
1. Philosopher 1 picks up chopsticks 2 and 1, and begins eating
2. Philosopher 2 blocks on chopstick 2
3. Philosopher 0 picks up chopstick 0, and blocks on chopstick 1
4. Philosopher 4 picks up chopstick 4, and blocks on chopstick 0
5. Philosopher 3 blocks on chopstick 4
As you can see, the problem is that one philosopher (#4) has two even-numbered chopsticks (#4 and #0), meaning that regardless of the order in which he tries to pick them up, it's gonna screw up the ordering. In fact, what happens is that this allows an additional philosopher to block on one eating philosopher, bringing the total in the cluster to five - the number of philosophers at the table.
Oh, and for those keeping score, the minimum number of philosophers that are able to eat at any time appears to be (n + 2) / 4.
I initially thought (and indeed said in my report) that the condition we were seeing, where only one of five philosophers was able to eat, was a consequence of there being an odd number of philosophers. While I was correct that the odd number had an important part in what we were seeing, the problem was more general than I thought. This diagram of an eight-philosopher table shows the worst case scenario for an even number of philosophers:
What's happening here is as follows:
1. Philosopher 0 picks up chopsticks 0 and 1, and begins eating
2. Philosopher 1 picks up chopstick 2, and blocks on chopstick 1
3. Philosopher 2 blocks on chopstick 2
4. Philosopher 7 blocks on chopstick 0
In this order (or a few variations of it), one philosopher has managed to prevent three others in a cluster from eating. The exact same method can be used to block three others, while a total of two philosophers eat; this is the worst-case scenario for this table.
You can draw it out for yourself (I drew it on paper, along with several other sizes, but don't feel like making more diagrams online) and prove that it's possible for a minimum of two philosophers to eat at a table with only six philosophers. This is logical: one philosopher can only block three others, leaving three chopsticks available; one of the last two philosophers will be able to eat.
So, four philosophers is too few (for two philosophers to eat), six is enough, but what about five? This was the classic case, and the one we implemented. What happened is this, shown in words and figure:
1. Philosopher 1 picks up chopsticks 2 and 1, and begins eating
2. Philosopher 2 blocks on chopstick 2
3. Philosopher 0 picks up chopstick 0, and blocks on chopstick 1
4. Philosopher 4 picks up chopstick 4, and blocks on chopstick 0
5. Philosopher 3 blocks on chopstick 4
As you can see, the problem is that one philosopher (#4) has two even-numbered chopsticks (#4 and #0), meaning that regardless of the order in which he tries to pick them up, it's gonna screw up the ordering. In fact, what happens is that this allows an additional philosopher to block on one eating philosopher, bringing the total in the cluster to five - the number of philosophers at the table.
Oh, and for those keeping score, the minimum number of philosophers that are able to eat at any time appears to be (n + 2) / 4.
Sunday, December 31, 2006
Moshikashite Kore Sugoku Warui
Be afraid. Be very afraid. Q has just learned about Starfish. Even if it's old as dirt, this can't possibly be a good thing. Some of the stuff it generated:
Oh, and for the curious, that phrase is from Azumanga Daioh, one of my favorite mangas. Naturally translated, it means "This could be really bad": もしかして [possibly] これ [this] 凄く [terribly] 悪い [is bad].
Oh, and for the curious, that phrase is from Azumanga Daioh, one of my favorite mangas. Naturally translated, it means "This could be really bad": もしかして [possibly] これ [this] 凄く [terribly] 悪い [is bad].
Subscribe to:
Posts (Atom)
Posts
