When SimCity 4 was released, I was very disappointed by the broken transportation model, the assumptions built into underlying economic model that resulted in all cities looking like California, and the weird game design that assumed I was more interested in building stories about Sims than about building stories about the city itself. Since then, I became interested in figuring out how the simulations in these games work, but I always got hung up on a small mathematical detail. I finally figured out the problem a couple of weeks ago. Some simple grade 11 math is all you need, but I just couldn't see it until now.
The most intuitive scale to model these simulations at is at the level of individual people. So for each "person" in the city, you code up a model for the person's preferences and behaviour, and you then "run" this model and record what happens. So if a person wants to drive along a road from one building to another, you then increment the traffic on that road segment to account for the person's car. If you simulate enough people, you can figure out the traffic along each street, resulting in a simulation for the entire city.
The problem is that the city is constantly changing and the people being simulated will change their behaviours, so you want to have the simulation running constantly to take these changes into account. This makes the simulation complicated. If your simulator decides that a person will take an alternate route to get to a destination, the simulator needs to reduce the traffic along the old route of the person (since the person no longer drives on those roads) and increase the traffic along the new route. Keeping track of the routes of all these people is complicated, memory-intensive, and slow. If you don't remove the person's traffic from the old route though, then the traffic along the old route will keep on increasing (since there's no way for the traffic to go down to reflect the fact that fewer people are using it).
One solution is to divide your simulation into rounds. In each round, you simulate the actions of all the people in the city once, record the result, and update the UI with these results. Then you start a new round by discarding all the results (i.e. set the traffic of all roads to zero) and running a complete cycle of the simulation again. This approach isn't satisfactory because one cycle of the simulator might take several minutes to complete. So if you change something in the city, it might take several minutes to see the effect of these changes in the simulator because the UI won't be updated until the next simulation cycle.
We want to constantly update the traffic values, but this results in traffic growing without bounds. Resetting the traffic to zero is not practical because we want to be able to display the simulation values as they are updated. What we need is some way to "decay" the traffic along road segments over time. As a result, the traffic along each road segment will constantly decrease, but as you simulate the actions of different people, the traffic along each road segment will increase again. For this to work though, the speed of the decay must be balanced out the speed at which you add new traffic, so that the simulation converges to reflect the correct traffic along a certain road. But I could never figure out the math for this problem. If traffic decays too quickly, then the traffic will be close to zero in most places, but will spike up randomly in places where the new routes of people are being simulated. If traffic decays too slowly, then the total traffic along each road will increase without bound.
Simulating transportation always results in new traffic being accumulated in an additive fashion. i.e. As you simulate the route of one person, the traffic along the route will be incremented by a constant to reflect the traffic of this one person. But the decay must be in the form of a rate. The traffic along a route cannot be decreased by a constant all the time, but by a percentage of its existing traffic (because heavily trafficked routes should have their traffic decreased by a larger amount than lightly-trafficked routes--otherwise the traffic on light routes will fall to zero while the traffic on the heavier routes will increase without bound). Previously, I tried to think of things as being like a physics simulator where the simulator would try to balance things out so that the amount of traffic added by the simulator will be counter-balanced by removing an equivalent amount of traffic due to decay or something like that, but this isn't quite the right thing to do.
In fact, the solution is the geometric series. For example, assume that you don't change your city at all, so that the simulation should converge to a steady-state. So if you simulate all the people in the city, the same amount of traffic will be added will be added to a particular road segment (say, a). If you decay the traffic on any particular road segment by a rate r (let's assume you apply the decay once every time you do a complete simulation cycle of all the people in the city), then over time, this results in a geometric series. Geometric series will converge to a/(1-r). This is exactly what we need! We don't have to fiddle with balancing the rate of new traffic with old traffic or whatever--the geometric series shows that the simulation will converge to nice stable values. And we can then scale a and r to get the convergence rate and overall stability that we want. It all becomes nicely straight-forward.
Saturday, March 20, 2010
Wednesday, February 17, 2010
Background Music in JavaScript without Flash
So for the last half a year, I've been playing a bit with making larger and more complicated games in JavaScript. I've found a few neat new tricks, but I haven't gotten around to writing about them until now. One thing I figured out is how to play background music in modern browsers without using Flash. This is useful for JavaScript games where you need some music to help set the mood in a game.
So for non-IE browsers, you can use HTML5. Although the APIs seem to work reasonably well, I'm not sure how stable the specification is. There's some occasional weird things in the specification that suggest that the specification is immature. For example, the audio specification makes use of a lot of "boolean attributes" which are HTML attributes that can be defined or not defined instead of simply being true or false (so setting the attribute to false is equivalent to defining it as true). This sort of bizarre, unnecessarily complex, probably XML-incompatible stuff suggests that the specification still contains idiosyncrasies and pet projects of individual developers instead of being polished into a consistent spec. I'd be concerned of a problem like with ECMAScript 4 where once Microsoft and Yahoo! applied some common sense to the specification, a lot of things might end up changing. So I suggest using HTML5 with caution--you should always check to make sure that every method and field that you want to use is supported by your browser before relying on their existence.
Well, anyways, for HTML5 audio, you first need to check if it's supported:
Every browser supports different audio formats, so you need to make an MP3 version of your files (you can use iTunes for that) for Safari/Chrome and an OGG version (you can use Audacity for that) for Firefox/Chrome. For some reason, the Chrome browser doesn't support WAV files because they claim the files are "too large," and I think this is a clear example of the immaturity surrounding the HTML5 specification in general. There are many good reasons for supporting WAV files in browsers, and for short sound effects, WAV files can even be smaller than OGG or MP3 files. The reason for not including WAV support in Chrome is simply the result of bias and ignorant opinions as opposed to a mature approach to the problem. So anyways, you need to test which background music file to load depending on which formats are supported.
And from there, playing the file is easy (though Firefox 3.5 doesn't support looping music, so you need to do that manually).
For Internet Explorer, you can use Windows Media Player to play music. First, you have to check to see if Windows Media Player is available using ActiveX:
For some reason, when you create the ActiveX object, it isn't bound to your web page properly, so you can't use relative URLs to refer to music files. If you do want to use relative URLs, you actually have to create the player object as an HTML object in your document.
From there, playing an mp3 file is easy:
Update 2010-5-3: Apparently, using MP3 files on a web page or in a game requires an mp3 license. In the future, I guess I will only support Ogg Vorbis and let users of Safari and IE endure the silence.
So for non-IE browsers, you can use HTML5. Although the APIs seem to work reasonably well, I'm not sure how stable the specification is. There's some occasional weird things in the specification that suggest that the specification is immature. For example, the audio specification makes use of a lot of "boolean attributes" which are HTML attributes that can be defined or not defined instead of simply being true or false (so setting the attribute to false is equivalent to defining it as true). This sort of bizarre, unnecessarily complex, probably XML-incompatible stuff suggests that the specification still contains idiosyncrasies and pet projects of individual developers instead of being polished into a consistent spec. I'd be concerned of a problem like with ECMAScript 4 where once Microsoft and Yahoo! applied some common sense to the specification, a lot of things might end up changing. So I suggest using HTML5 with caution--you should always check to make sure that every method and field that you want to use is supported by your browser before relying on their existence.
Well, anyways, for HTML5 audio, you first need to check if it's supported:
var hasAudio = true;
try {
var audiotest = new Audio();
if (!audiotest.canPlayType) hasAudio = false;
} catch (e) { hasAudio = false; }
Every browser supports different audio formats, so you need to make an MP3 version of your files (you can use iTunes for that) for Safari/Chrome and an OGG version (you can use Audacity for that) for Firefox/Chrome. For some reason, the Chrome browser doesn't support WAV files because they claim the files are "too large," and I think this is a clear example of the immaturity surrounding the HTML5 specification in general. There are many good reasons for supporting WAV files in browsers, and for short sound effects, WAV files can even be smaller than OGG or MP3 files. The reason for not including WAV support in Chrome is simply the result of bias and ignorant opinions as opposed to a mature approach to the problem. So anyways, you need to test which background music file to load depending on which formats are supported.
var clip = new Audio();
clip.autoplay = false;
clip.autobuffer = true;
var canOgg = clip.canPlayType("audio/ogg");
var canMp3 = clip.canPlayType("audio/mpeg");
var canMp3Alt = clip.canPlayType("audio/mp3");
var canWav = clip.canPlayType("audio/wav");
if (canMp3 != "" && canMp3 != "no")
clip.src = mp3File;
else if (canMp3Alt != "" && canMp3Alt != "no")
clip.src = mp3File;
else if (canOgg != "" && canOgg != "no")
clip.src = oggFile;
else if (canWav != "" && canWav != "no")
clip.src = wavFile;
And from there, playing the file is easy (though Firefox 3.5 doesn't support looping music, so you need to do that manually).
clip.addEventListener("ended", function() {
// I'm not sure if this setTimeout() thing is necessary
window.setTimeout(function() {clip.play();}, 1);});
clip.play();For Internet Explorer, you can use Windows Media Player to play music. First, you have to check to see if Windows Media Player is available using ActiveX:
var hasWmp = true;
try {
var player = new ActiveXObject("WMPlayer.OCX.7");
} catch (e) {hasWmp = false;
For some reason, when you create the ActiveX object, it isn't bound to your web page properly, so you can't use relative URLs to refer to music files. If you do want to use relative URLs, you actually have to create the player object as an HTML object in your document.
var tmp = document.createElement('div');
tmp.innerHTML = '<OBJECT CLASSID="CLSID:6BF52A52-394A-11d3-B153-00C04F79FAA6"></OBJECT>';
player = tmp.getElementsByTagName('OBJECT')[0];
tmp = null;
if (!player || !player.versionInfo) hasWmp = false;From there, playing an mp3 file is easy:
player.settings.setMode("loop", true);
player.URL = mp3File;
player.controls.play();Update 2010-5-3: Apparently, using MP3 files on a web page or in a game requires an mp3 license. In the future, I guess I will only support Ogg Vorbis and let users of Safari and IE endure the silence.
Friday, January 22, 2010
We're Currently in a Golden Age of Literacy, and It's All Downhill from Here
During the past few months, I've slowly started to notice that a lot of the things that I used to enjoy reading about, I know prefer watching videos about instead. For example, I used to enjoy reading reviews about video games on the web, but recently I'll search for video reviews first, and I'll only fall back to text reviews if I can't find any videos. I'm also starting to do the same for educated political commentary and satire. In fact, if there was enough video content on my favourite topics, I might prefer watching videos to web browsing entirely.
The logical conclusion of all this is that this signals the end of literacy as we know it. Sure, we might now complain about the poor literacy skills of our kids, we decry their unintelligible text messages, and we bemoan their incoherent essays, but ten years from now, we're going to look back on 2010 as a golden age of literacy. It will be considered the pinnacle of literacy in the world--people all over the world actually had to type words in order to find information! People were required to read information and instructions! Children preferred sending messages to each other in the form of text! In between the television age of the 1980s and the Internet video age of the 2020s, the period around 2010 will be considered a renaissance of literacy where people actually had to know how to read and write text to survive in the world!
In ten to twenty years, there will no longer be a need to read and write information; everyone will use video. Instead of web pages, there will be videos. Instead of SMS and tweets, kids will send videos to each other. Instead of textbooks, there will be slides and accompanying video. Society will complain about how kids can't form well-thought out text any more, preferring stream-of-consciousness videos. Kids might now even write text any more but simply make videos, edit it together somehow, and then dump the text out. Similar to how people ignore people talking to themselves in the street (they assume that the person is using a hands-free cellphone) and ignore people checking e-mail during conversations, I think in the future, people will simply get used to the idea of people quietly making short video messages to others in the middle of a meeting (of course, it will seem extremely disruptive to us, but I imagine it's something that future generations will simply get used to).
There are a few weaknesses of video--because it is a linear medium, it's hard to scan through it quickly, so there will still be some text that people will read. This text will mostly be in the form of "headlines," "search results," and "transcripts." When we want to find videos to watch, we'll tell our computer what videos we want to watch (through a webcam, of course!), and the computer will show various video clips with meaningful text headings that we can scan through quickly to find what we want. And every video will have an accompanying transcript (in both text and screencap form) that people can use to quickly jump around to the parts of videos that they're interested in.
I see two impediments to this video future:
The main barrier to this future right now are patents on video technology. These patents inhibit standardization (so no two companies can agree on a video e-mail standard or a webcam standard, for example), which prevents a network effect from starting around video technology. The cost and licensing difficulty of patents also inhibit innovation and entrepreneurship in this area. New companies and researchers don't want to develop new ideas in this space because it's too complicated and too expensive to license technology in this area, so the potential rewards (with Internet technology, most of this consumer technology has zero revenue) aren't profitable. I believe this patent issue will work itself out once patents expire or once storage and bandwidth becomes so cheap that we'll just use raw video for everything. The day after a useful video patent expires, a standard for video e-mail will be made (or perhaps there will be some sort of proprietary Facebook thing that comes out before then that everyone will use--unfortunately, it will be a bit of a kludge getting it to work with cellphones and other devices).
The other barrier is the lack of accurate video transcription technology. As I mentioned before, video is a linear medium, so we need a way to search it and to scan through it. The minimum technology we need for this to be practical is automatic video transcription. Currently, speech recognition isn't quite at the point where this is possible, but I imagine this technology will be ready by 2020, perhaps even by 2015 (there might be patent issues on this technology that will delay its widespread use for a few more years).
It's sort of weird knowing that despite all the complaints that people have about literacy in 2010, this is actually the best it's going to get. I'm not sure about the ultimate implications and ramifications of the future age of video on society, but I think it's inevitable, so we might as well start preparing for it now. I suppose other people have also been evangelizing that video is the future, so my musings are perhaps not the most original, but they never tell you that the trade-off is the end of literacy.
The logical conclusion of all this is that this signals the end of literacy as we know it. Sure, we might now complain about the poor literacy skills of our kids, we decry their unintelligible text messages, and we bemoan their incoherent essays, but ten years from now, we're going to look back on 2010 as a golden age of literacy. It will be considered the pinnacle of literacy in the world--people all over the world actually had to type words in order to find information! People were required to read information and instructions! Children preferred sending messages to each other in the form of text! In between the television age of the 1980s and the Internet video age of the 2020s, the period around 2010 will be considered a renaissance of literacy where people actually had to know how to read and write text to survive in the world!
In ten to twenty years, there will no longer be a need to read and write information; everyone will use video. Instead of web pages, there will be videos. Instead of SMS and tweets, kids will send videos to each other. Instead of textbooks, there will be slides and accompanying video. Society will complain about how kids can't form well-thought out text any more, preferring stream-of-consciousness videos. Kids might now even write text any more but simply make videos, edit it together somehow, and then dump the text out. Similar to how people ignore people talking to themselves in the street (they assume that the person is using a hands-free cellphone) and ignore people checking e-mail during conversations, I think in the future, people will simply get used to the idea of people quietly making short video messages to others in the middle of a meeting (of course, it will seem extremely disruptive to us, but I imagine it's something that future generations will simply get used to).
There are a few weaknesses of video--because it is a linear medium, it's hard to scan through it quickly, so there will still be some text that people will read. This text will mostly be in the form of "headlines," "search results," and "transcripts." When we want to find videos to watch, we'll tell our computer what videos we want to watch (through a webcam, of course!), and the computer will show various video clips with meaningful text headings that we can scan through quickly to find what we want. And every video will have an accompanying transcript (in both text and screencap form) that people can use to quickly jump around to the parts of videos that they're interested in.
I see two impediments to this video future:
- patents
- speech recognition (specifically video transcription) technology
The main barrier to this future right now are patents on video technology. These patents inhibit standardization (so no two companies can agree on a video e-mail standard or a webcam standard, for example), which prevents a network effect from starting around video technology. The cost and licensing difficulty of patents also inhibit innovation and entrepreneurship in this area. New companies and researchers don't want to develop new ideas in this space because it's too complicated and too expensive to license technology in this area, so the potential rewards (with Internet technology, most of this consumer technology has zero revenue) aren't profitable. I believe this patent issue will work itself out once patents expire or once storage and bandwidth becomes so cheap that we'll just use raw video for everything. The day after a useful video patent expires, a standard for video e-mail will be made (or perhaps there will be some sort of proprietary Facebook thing that comes out before then that everyone will use--unfortunately, it will be a bit of a kludge getting it to work with cellphones and other devices).
The other barrier is the lack of accurate video transcription technology. As I mentioned before, video is a linear medium, so we need a way to search it and to scan through it. The minimum technology we need for this to be practical is automatic video transcription. Currently, speech recognition isn't quite at the point where this is possible, but I imagine this technology will be ready by 2020, perhaps even by 2015 (there might be patent issues on this technology that will delay its widespread use for a few more years).
It's sort of weird knowing that despite all the complaints that people have about literacy in 2010, this is actually the best it's going to get. I'm not sure about the ultimate implications and ramifications of the future age of video on society, but I think it's inevitable, so we might as well start preparing for it now. I suppose other people have also been evangelizing that video is the future, so my musings are perhaps not the most original, but they never tell you that the trade-off is the end of literacy.
Sunday, August 30, 2009
Stitching Together Scanned Images
Recently, I was scanning a lot of legal sized documents, but my scanner could only scan A4 sized paper. So I had to scan each document in parts and then stitch them together afterwards.
There is lots of software available for stitching together photos into a panorama, but surprisingly, I had trouble finding software for stitching together flat images (or for creating a "linear panorama" as some people call it) even though this task would supposedly be a little bit easier than making panoramas. Of course, it's possible to manually load up the images into a paint program and manually align them and blend them, but I had to stitch together a lot of documents, so this was too time-consuming for me.
In the past, I've used software like Hugin, Panotools, or Autostitch for stitching together photos, but I could never quite get the various tutorials on how to handle linear panoramas to work quite right.
I own a copy of Photoshop Elements 6.0, which does contain algorithms for this sort of stitching (under File...New...Photomerge Panorama). Initially, I was quite pleased with the results, but after inspecting the final stitched images more carefully, I began to realize that the algorithm had lots of problems rotating images in order to get good alignment between them. If you only superficially inspect the final result, everything seems fine because Adobe seems to use some sort of fancy blending algorithm (something like Enblend) that hides a lot of these imperfections. Unfortunately, the blending algorithm can't hide the fact that because of poor alignment, lines that should be straight aren't. Even when you manually rotate the images to help the alignment algorithm, Photoshop Elements doesn't help you try to fine-tune the rotation or positioning afterwards, so it's hard to get things aligned quite right (I was hoping that if I could get things close to alignment, the algorithm would "snap" things to the best position). Adobe is always tweaking their algorithms, so it's possible that later versions of Photoshop Elements give better results though.
In the end, I actually found a research tool from Microsoft that provided excellent automated results. Even better, Microsoft's Image Composition Editor was very fast and very easy to use, so I highly recommend this program. Eventually, I hope to figure out what I was doing wrong with Hugin because it's always useful to have an alternative that supports a lot of manual tweaking, but so far the results of the Image Composition Editor have been so good that I've only needed to resort to alternate tools (i.e. Adobe Photoshop Elements) only once, which occurred when I was stitching four images together that had only a small amount of overlap.
There is lots of software available for stitching together photos into a panorama, but surprisingly, I had trouble finding software for stitching together flat images (or for creating a "linear panorama" as some people call it) even though this task would supposedly be a little bit easier than making panoramas. Of course, it's possible to manually load up the images into a paint program and manually align them and blend them, but I had to stitch together a lot of documents, so this was too time-consuming for me.
In the past, I've used software like Hugin, Panotools, or Autostitch for stitching together photos, but I could never quite get the various tutorials on how to handle linear panoramas to work quite right.
I own a copy of Photoshop Elements 6.0, which does contain algorithms for this sort of stitching (under File...New...Photomerge Panorama). Initially, I was quite pleased with the results, but after inspecting the final stitched images more carefully, I began to realize that the algorithm had lots of problems rotating images in order to get good alignment between them. If you only superficially inspect the final result, everything seems fine because Adobe seems to use some sort of fancy blending algorithm (something like Enblend) that hides a lot of these imperfections. Unfortunately, the blending algorithm can't hide the fact that because of poor alignment, lines that should be straight aren't. Even when you manually rotate the images to help the alignment algorithm, Photoshop Elements doesn't help you try to fine-tune the rotation or positioning afterwards, so it's hard to get things aligned quite right (I was hoping that if I could get things close to alignment, the algorithm would "snap" things to the best position). Adobe is always tweaking their algorithms, so it's possible that later versions of Photoshop Elements give better results though.
In the end, I actually found a research tool from Microsoft that provided excellent automated results. Even better, Microsoft's Image Composition Editor was very fast and very easy to use, so I highly recommend this program. Eventually, I hope to figure out what I was doing wrong with Hugin because it's always useful to have an alternative that supports a lot of manual tweaking, but so far the results of the Image Composition Editor have been so good that I've only needed to resort to alternate tools (i.e. Adobe Photoshop Elements) only once, which occurred when I was stitching four images together that had only a small amount of overlap.
Saturday, June 06, 2009
Vista Service Pack Installation Problems
I recently installed Windows Vista SP2, and like Vista SP1, I seemed to have problems getting it installed properly. It would spend a huge amount of time installing itself, reboot, and then fail during its third stage, and then spend a lot of time reverting the install. Windows Update would show Code 80004005 in the error details field for why the update failed.
Fortunately, after browsing the web, I found a forum post (I no longer remember where it is), where people mentioned that the problem comes up with dual-boot machines. My machine has both Linux and Windows installed, and Vista apparently fails its TPM security checks or something like that if the GRUB boot manager starts up in-between the computer starting and Vista starting. Fortunately, I installed GRUB on my Linux partition instead of my MBR, so I could simply change my active/boot partition to boot directly into Windows. Afterwards, the service pack could apply itself, and then I could boot on a Linux live CD to reset the active/boot partition back to the Linux partition.
Personally, I find this sort of annoying. It would be nice if Windows wouldn't die on dual-boot machines or give users a prompt to allow then to ignore TPM problems during the boot process or, at the very least, give more useful error messages.
Fortunately, after browsing the web, I found a forum post (I no longer remember where it is), where people mentioned that the problem comes up with dual-boot machines. My machine has both Linux and Windows installed, and Vista apparently fails its TPM security checks or something like that if the GRUB boot manager starts up in-between the computer starting and Vista starting. Fortunately, I installed GRUB on my Linux partition instead of my MBR, so I could simply change my active/boot partition to boot directly into Windows. Afterwards, the service pack could apply itself, and then I could boot on a Linux live CD to reset the active/boot partition back to the Linux partition.
Personally, I find this sort of annoying. It would be nice if Windows wouldn't die on dual-boot machines or give users a prompt to allow then to ignore TPM problems during the boot process or, at the very least, give more useful error messages.
Saturday, January 24, 2009
MTU Problems When Using Vista Internet Connection Sharing (ICS) with an XBox 360
So like other people, I don't really like the idea of paying $100 for an XBox 360 wifi adapter, so I'm using Internet Connection Sharing through my laptop to get my XBox connected to a wireless access point (yes, there are easier ways of doing this, but like usual, I'm doing something strange).
But when I did this, the XBox kept complaining that my MTU was set too low since it needed an MTU of 1364. This is a little silly since a proper IP stack should automatically fragment its packets to accomodate the MTU, but whatever.
I ran the command netsh interface ipv4 show interfaces to find out what the MTUs on my Vista laptop were, and they were all set to 1300. This seemed a little strange because 1300 is oddly low and also a nice round number that a human must have decided on. But I certainly hadn't set my MTU to 1300, so I'm not sure why it was set to that.
I spent a while browsing around, but finally I figured it out. It was that annoying Cisco VPN client on my laptop. I have no idea why they set the MTU so low (what sort of intermediate router would use 200 bytes of overhead per packet? It's silly to reserve so much), but the VPN Client comes with a Set MTU program that I was able to use to set everything back to normal, and then my XBox stopped complaining.
But when I did this, the XBox kept complaining that my MTU was set too low since it needed an MTU of 1364. This is a little silly since a proper IP stack should automatically fragment its packets to accomodate the MTU, but whatever.
I ran the command netsh interface ipv4 show interfaces to find out what the MTUs on my Vista laptop were, and they were all set to 1300. This seemed a little strange because 1300 is oddly low and also a nice round number that a human must have decided on. But I certainly hadn't set my MTU to 1300, so I'm not sure why it was set to that.
I spent a while browsing around, but finally I figured it out. It was that annoying Cisco VPN client on my laptop. I have no idea why they set the MTU so low (what sort of intermediate router would use 200 bytes of overhead per packet? It's silly to reserve so much), but the VPN Client comes with a Set MTU program that I was able to use to set everything back to normal, and then my XBox stopped complaining.
Friday, January 16, 2009
Running TPC-H Queries on MySQL
Getting the TPC-H queries to work on MySQL isn't too hard, but it isn't always clear what to do. I took the instructions from here and converted them to work with MySQL.
Once TPC-H is started, you can create a database and tpch account:
mysql -u root -p
mysql> CREATE USER 'tpch'@'%' IDENTIFIED BY 'password';
mysql> CREATE DATABASE tpch;
mysql> GRANT ALL ON tpch.* to 'tpch'@'%';
mysql> USE tpch;
mysql> \. tpch/gen/dss.ddl
Then, in the gen directories, you can modify the query generator to generate queries that are as close as possible to what you need:
cp makefile.suite makefile
#Modify makefile to use
# CC = gcc, DATABASE=SQLSERVER, MACHINE=LINUX, WORKLOAD=TPCH
#In tpcd.h, SQLSERVER section:
# change #define SET_DBASE "use %s;\n"
# change #define SET_ROWCOUNT "limit %d;\n\n"
# change #define START_TRAN "BEGIN WORK;"
# change #define END_TRAN "COMMIT WORK;"
make
Then you can start generating database data at the right scale factor
./dbgen -s 1
And also modify the constraints/indices file so that it's compatible with mysql:
# Modify dss.ri
# use a search and replace in order to remove "CONNECT TO TPCD", remove references to "TPCD." and remove the lines "COMMIT WORK;"
Then you can load all the data into the databases with
mysql -u tpch -p
mysql> use tpch;
mysql> LOAD DATA LOCAL INFILE 'customer.tbl' INTO TABLE CUSTOMER FIELDS TERMINATED BY '|';
# Same with orders, lineitem, nation, partsupp, part, region, supplier
mysql> \. dss.ri
You then need to change the case of the table names because the queries use lower-case table names I think whereas the dss.ddl uses upper-case names for the tables:
mysql> alter table NATION rename nation;
# Ditto for supplier, region, partsupp, part, orders, lineitem, customer
Finally, you can test some of the queries
cp dists.dss queries
cd queries
../qgen -c tpch -s 1 1
I think the queries still need to be modified a bit to be compatible. I think queries with a limit may need the semi-colon moved around, the precision indicator during date arithmetic in query 1 may need to be removed, and the method for naming columns in query 13 might need changing.
Once TPC-H is started, you can create a database and tpch account:
mysql -u root -p
mysql> CREATE USER 'tpch'@'%' IDENTIFIED BY 'password';
mysql> CREATE DATABASE tpch;
mysql> GRANT ALL ON tpch.* to 'tpch'@'%';
mysql> USE tpch;
mysql> \. tpch/gen/dss.ddl
Then, in the gen directories, you can modify the query generator to generate queries that are as close as possible to what you need:
cp makefile.suite makefile
#Modify makefile to use
# CC = gcc, DATABASE=SQLSERVER, MACHINE=LINUX, WORKLOAD=TPCH
#In tpcd.h, SQLSERVER section:
# change #define SET_DBASE "use %s;\n"
# change #define SET_ROWCOUNT "limit %d;\n\n"
# change #define START_TRAN "BEGIN WORK;"
# change #define END_TRAN "COMMIT WORK;"
make
Then you can start generating database data at the right scale factor
./dbgen -s 1
And also modify the constraints/indices file so that it's compatible with mysql:
# Modify dss.ri
# use a search and replace in order to remove "CONNECT TO TPCD", remove references to "TPCD." and remove the lines "COMMIT WORK;"
Then you can load all the data into the databases with
mysql -u tpch -p
mysql> use tpch;
mysql> LOAD DATA LOCAL INFILE 'customer.tbl' INTO TABLE CUSTOMER FIELDS TERMINATED BY '|';
# Same with orders, lineitem, nation, partsupp, part, region, supplier
mysql> \. dss.ri
You then need to change the case of the table names because the queries use lower-case table names I think whereas the dss.ddl uses upper-case names for the tables:
mysql> alter table NATION rename nation;
# Ditto for supplier, region, partsupp, part, orders, lineitem, customer
Finally, you can test some of the queries
cp dists.dss queries
cd queries
../qgen -c tpch -s 1 1
I think the queries still need to be modified a bit to be compatible. I think queries with a limit may need the semi-colon moved around, the precision indicator during date arithmetic in query 1 may need to be removed, and the method for naming columns in query 13 might need changing.
Thursday, August 14, 2008
Chinese Handwriting Recognition in Windows XP
If you want to write Chinese characters in Windows XP, there are lots of options available like Google's IME, but a lot of these options aren't practical if you don't know any Mandarin. There are websites for inputting Chinese in Cantonese, but still it isn't ideal.
Apparently, the IME in Windows XP can be upgraded to support limited hand-writing recognition in Chinese, but Microsoft conveniently hides the IME upgrades on its websites. Fortunately, I found a forum, which describes how to download these upgrades from the MS Office website. Once I installed these upgrades, I could then use the IMEPad to write Chinese characters using a mouse or tablet. In fact, the IMEPad option was available in my plain version of Windows XP, but clicking on the IMEPad button did not result in anything happening.
Apparently, the IME in Windows XP can be upgraded to support limited hand-writing recognition in Chinese, but Microsoft conveniently hides the IME upgrades on its websites. Fortunately, I found a forum, which describes how to download these upgrades from the MS Office website. Once I installed these upgrades, I could then use the IMEPad to write Chinese characters using a mouse or tablet. In fact, the IMEPad option was available in my plain version of Windows XP, but clicking on the IMEPad button did not result in anything happening.
Wednesday, March 26, 2008
IE7 Erases .XML Files
So I had spent a few days writing a long .xml file with a corresponding .xsl stylesheet. I was using IE7 to look at the generated html. At one point, I chose Page, then Save As. Then I chose Cancel.
Poof.
IE7 erased my .xml document. Well, I guess I didn't really need the document that badly after all.
Poof.
IE7 erased my .xml document. Well, I guess I didn't really need the document that badly after all.
Monday, December 03, 2007
Tiles Don't Generalize
For a couple months, I've been experimenting a bit with SVG during my free time to get a feel for how to use it cleanly on the web. In particular, I've been playing around with trying to create a little tile-based game using SVG and JavaScript.
The nice properties of grid-based tiles using an isometric or 3/4 perspective are well-known. As long as every object in the game fits exactly in a 1x1 grid cell, then everything works great. It's easy to figure out an order to draw the objects in order to ensure that nearer objects properly occlude further objects. You can stack objects within a grid and do other nice stuff too.
After seeing all those isometric-perspective computer games with characters running in-between grid tiles and with all manner of odd-shaped objects though, I assumed that the algorithms for choosing the order to draw objects in the isometric perspective generalized in some nice way. Of course, I realized that things couldn't generalize arbitrarily. If you allowed for arbitrary objects in arbitrary poses, then you'd end up with an arbitrary 3d scene drawn from an orthographic perspective. Then you'd need the full painter's algorithm with polygon chopping etc.
But, I assumed that if all objects were in non-overlapping axis-aligned bounding boxes, then I could figure out some way to order the objects without needing to chop any of them (since you can't really do this is SVG). In particular, I wanted the floor tiles and the objects to be all mixed up in the rendering code. But for the isometric perspective, it is possible to create degenerate examples where objects mutually occlude each other. So you can't generalize algorithms for the isometric perspective this way. In particular, my plan of having floor tiles and wall tiles, plus arbitrarily sized objects sitting on the floor tiles just wouldn't work.
In fact, the same thing happens with the three-quarter perspective as well (I've shifted the perspective a bit so that it's easier to see the depth of the objects).
So having arbitrarily sized objects that can stack on top of each other arbitrarily won't work. Having objects in non-overlapping axis-aligned bounding boxes where all the bounding boxes sit on the same plane, that seems to work ok. With the isometric perspective, it seems like it might be a little bit hard to get the right ordering of objects during drawing, but it seems doable at least. With the 3/4 perspective, everything works out well in that particular situation.
So basically, one way to get around this problem is to have a flat floor and use tiles to cover the floor as one layer, then on a second layer, you can have objects and walls and stuff that you can order separately. I imagine there are other cases that lead to an easy ordering of objects (perhaps if everything has a fixed height? or maybe in the 3/4 perspective, if you allow for only two levels: one for arbitrary height terrain and then another for things on top?), but I haven't really figured it out yet. Perhaps in reality, degenerate cases never really end up occuring, so you can just sort of hack in lots of special cases in the rendering engine to make sure all the objects are rendered in the right order.
Well, in any case, the point of this post is to show that tiles are trickier than I thought. They really don't generalize nicely, so you have to put a lot of thought into how to handle things once you allow for objects that don't fall exactly within grid boundaries.
The nice properties of grid-based tiles using an isometric or 3/4 perspective are well-known. As long as every object in the game fits exactly in a 1x1 grid cell, then everything works great. It's easy to figure out an order to draw the objects in order to ensure that nearer objects properly occlude further objects. You can stack objects within a grid and do other nice stuff too.
After seeing all those isometric-perspective computer games with characters running in-between grid tiles and with all manner of odd-shaped objects though, I assumed that the algorithms for choosing the order to draw objects in the isometric perspective generalized in some nice way. Of course, I realized that things couldn't generalize arbitrarily. If you allowed for arbitrary objects in arbitrary poses, then you'd end up with an arbitrary 3d scene drawn from an orthographic perspective. Then you'd need the full painter's algorithm with polygon chopping etc.
But, I assumed that if all objects were in non-overlapping axis-aligned bounding boxes, then I could figure out some way to order the objects without needing to chop any of them (since you can't really do this is SVG). In particular, I wanted the floor tiles and the objects to be all mixed up in the rendering code. But for the isometric perspective, it is possible to create degenerate examples where objects mutually occlude each other. So you can't generalize algorithms for the isometric perspective this way. In particular, my plan of having floor tiles and wall tiles, plus arbitrarily sized objects sitting on the floor tiles just wouldn't work.
In fact, the same thing happens with the three-quarter perspective as well (I've shifted the perspective a bit so that it's easier to see the depth of the objects).
So having arbitrarily sized objects that can stack on top of each other arbitrarily won't work. Having objects in non-overlapping axis-aligned bounding boxes where all the bounding boxes sit on the same plane, that seems to work ok. With the isometric perspective, it seems like it might be a little bit hard to get the right ordering of objects during drawing, but it seems doable at least. With the 3/4 perspective, everything works out well in that particular situation.
So basically, one way to get around this problem is to have a flat floor and use tiles to cover the floor as one layer, then on a second layer, you can have objects and walls and stuff that you can order separately. I imagine there are other cases that lead to an easy ordering of objects (perhaps if everything has a fixed height? or maybe in the 3/4 perspective, if you allow for only two levels: one for arbitrary height terrain and then another for things on top?), but I haven't really figured it out yet. Perhaps in reality, degenerate cases never really end up occuring, so you can just sort of hack in lots of special cases in the rendering engine to make sure all the objects are rendered in the right order.
Well, in any case, the point of this post is to show that tiles are trickier than I thought. They really don't generalize nicely, so you have to put a lot of thought into how to handle things once you allow for objects that don't fall exactly within grid boundaries.
Friday, September 14, 2007
Resolution Independence in Vista
I recently got a Thinkpad notebook that crams a 1400x1050 resolution onto a tiny screen. It's a great screen, but unfortunately everything ends up being a bit too small. If you have resolution independent applications, the increased resolution can be a real joy though because the text becomes so clear and easy on the eyes. Although previous versions of Windows had very limited support for resolution independence, things supposedly had improved quite a bit in Vista.
Unfortunately, things don't quite fit together that well. Just like earlier versions of Windows, you can increase the default font size in Vista. Unfortunately, this causes various glitches in things. For example, text no longer fits in the dialog boxes of Windows Media Player (I suspect that the Windows Media Player people must have written some custom dialog box code because I'm pretty sure the default dialog box code scaled things correctly even back during the Windows 95 days). And lots of fonts on web pages are specified in terms of pixel sizes, and their sizes don't get adjusted, so the text ends up being too small to see. Internet Explorer does have a zoom capability that redefines pixel sizes, but it also increases the size of the default font, which has already been increased, making things look too big.
Vista also has the option of simply scaling up all pixels to a larger size. Basically, Windows will fool legacy applications into thinking that the screen has a lower resolution, so that the applications render at a smaller size. This render is then scaled up to fill the larger resolution. Resolution independent applications, however, can render at the full resolution. Unfortunately, Adobe (Acrobat) Reader is considered a legacy application. Being able to read .pdf documents with crisper text is one of the main reasons I chose the high resolution screen, and you lose all those benefits if you render everything to a lower resolution and then scale it up. I imagine the same problem crops up in other applications as well. For example, Internet Explorer doesn't have strong support for vector drawing formats like SVG, so it's not possible to get high resolution graphics on web pages, so you have to live with scaled up versions of bitmaps instead.
Based on this experience, I imagine it will take another few years before it becomes practical to use Windows comfortably on a high resolution display. The new version of MacOS will supposedly have strong support for resolution independence, but I doubt that they've actually managed to solve the problem in a comprehensive manner. I think that doing resolution indepence right probably requires a larger rethinking of UI widgets and layout managers (basically, it will be the same technology needed to layout a single UI design on both tiny mobile device screens and large LCD monitors with needing lots of manual tweaking), but I haven't really heard much about research into that area by Apple, so I doubt they've hit the final solution yet.
Unfortunately, things don't quite fit together that well. Just like earlier versions of Windows, you can increase the default font size in Vista. Unfortunately, this causes various glitches in things. For example, text no longer fits in the dialog boxes of Windows Media Player (I suspect that the Windows Media Player people must have written some custom dialog box code because I'm pretty sure the default dialog box code scaled things correctly even back during the Windows 95 days). And lots of fonts on web pages are specified in terms of pixel sizes, and their sizes don't get adjusted, so the text ends up being too small to see. Internet Explorer does have a zoom capability that redefines pixel sizes, but it also increases the size of the default font, which has already been increased, making things look too big.
Vista also has the option of simply scaling up all pixels to a larger size. Basically, Windows will fool legacy applications into thinking that the screen has a lower resolution, so that the applications render at a smaller size. This render is then scaled up to fill the larger resolution. Resolution independent applications, however, can render at the full resolution. Unfortunately, Adobe (Acrobat) Reader is considered a legacy application. Being able to read .pdf documents with crisper text is one of the main reasons I chose the high resolution screen, and you lose all those benefits if you render everything to a lower resolution and then scale it up. I imagine the same problem crops up in other applications as well. For example, Internet Explorer doesn't have strong support for vector drawing formats like SVG, so it's not possible to get high resolution graphics on web pages, so you have to live with scaled up versions of bitmaps instead.
Based on this experience, I imagine it will take another few years before it becomes practical to use Windows comfortably on a high resolution display. The new version of MacOS will supposedly have strong support for resolution independence, but I doubt that they've actually managed to solve the problem in a comprehensive manner. I think that doing resolution indepence right probably requires a larger rethinking of UI widgets and layout managers (basically, it will be the same technology needed to layout a single UI design on both tiny mobile device screens and large LCD monitors with needing lots of manual tweaking), but I haven't really heard much about research into that area by Apple, so I doubt they've hit the final solution yet.
Saturday, February 17, 2007
Serializing Signals without Atomic Compare and Swap
So basically, the problem with event handlers in IE6 is that they might become interrupted by other event handlers, making synchronization difficult. What you want is a more traditional event driven model where only one event handler can execute at a time. Essentially, you want a scheme that serializes signals so that the event handlers execute sequentially. Unfortunately, since JavaScript comes with no synchronization primitives like atomic compare and swap, so doing this is messy.
So I think I've come up with a scheme that lets you wrap event handlers in a function that will test if other event handlers are executing at the same time. If they are, it will add itself to a queue to be executed later. There's various annoying synchronization issues involved though, so this is not as simple as it sounds.
Here's the pseudocode for the event wrapper function:
So I think I've come up with a scheme that lets you wrap event handlers in a function that will test if other event handlers are executing at the same time. If they are, it will add itself to a queue to be executed later. There's various annoying synchronization issues involved though, so this is not as simple as it sounds.
Here's the pseudocode for the event wrapper function:
And here's the pseudocode for the queue methods:
globals root, queue
if root == null
root := true
execute own handler
root := null
while !queue.empty()
root := true
queue.dispatch()
root := null
else
queue.add(self)
And here's how you could code it up in JavaScript. Basically, I define a handler function. You can then use the handler function to wrap your own event handlers before setting them to listen for events:
queue.add(fn)
globals end, isClaims[], handlers[], queueLength
myend := end
while(true)
if isClaimed[myend] != null
myend++
if myend >= queueLength
myend := 0
if myend == start
error!
continue
isClaimed[myend] := true
if handlers[myend] != null
continue
handlers[myend] := fn
break
end := myend
queue.empty()
globals isClaimed[], start
return isClaimed[start]==null
queue.dispatch()
globals isClaimed[], handlers[], start, end, queueLength
if isClaimed[start] != null
myend := end
if myend == start
myend++
if myend >= queueLength
myend := 0
end := myend
execute handlers[start]
handlers[start] := null
isClaimed[start] := null
start ++
if start >= queueLength
start := 0
<script>
// Initialization script that creates the "handler" function for wrapping
// handlers
(function () {
var SIZE = 100; // max number of simultaneous events
var root = false; // boolean, indicating whether
// event handler is the first one in a
// chain or not
var queue = new Array(SIZE); // Event handlers to be executed later
var thisQueue = new Array(SIZE); // Corresponding this objects
var isClaimed = new Array(SIZE); // reserves a spot in queue
var start = 0; // position in queue circular buffer
var end = 0;
// Define the global handler wrapper function
handler = function(eventHandler)
{
return function() {
if (root == false) {
root = true;
eventHandler.call(this);
root = false;
while (isClaimed[start] != null)
{
root = true;
if (isClaimed[start] != null) {
var myend = end;
if (myend == start) {
myend++;
if (myend >= SIZE) myend = 0;
end = myend;
}
queue[start].call(thisQueue[start]);
queue[start] = null;
thisQueue[start] = null;
isClaimed[start] = null;
start++;
if (start >= SIZE) start = 0;
}
root = false;
}
} else {
var myend = end;
while (true) {
if (isClaimed[myend] != null) {
myend++;
if (myend >= SIZE) myend = 0;
continue;
}
isClaimed[myend] = true;
if (queue[myend] != null) continue;
queue[myend] = eventHandler;
thisQueue[myend] = this;
break;
}
end = myend;
}
};
}
})(); // Execute the initialization code
function loaded()
{
alert('loaded ' + this.src);
}
var img1 = new Image();
var img2 = new Image();
img1.onload = handler(loaded);
img2.onload = handler(loaded);
img1.src = "test1.png";
img2.src = "test2.png";
alert('done')
</script>
Asynchronous Callbacks in IE6 JavaScript
Well, back in October, I noticed that Internet Explorer 6 had a few quirks with its usage of event handlers. JavaScript is single-threaded and does not contain any synchronization primitives. As a result, when JavaScript is embedded in a web browser, it is supposed to use an event-driven model: as events occur, they are put into a queue, and then a single thread removes events from the queue and executes handlers for them. Unfortunately, IE6 does not rigorously follow this model. Some of their callbacks follow a model used for interrupts or UNIX signals. Even if another piece of JavaScript code is being executed, the code can be interrupted by an asynchronous event, and the callback for that event will be run. When the event ends, the original code will resume. Unlike signals or interrupts though, IE6 allows these callbacks to interrupt other callbacks.
So, if you put the following code in a web page and run it in IE6, you will get three different dialog boxes showing up simultaneously:
In any case, I think I came up with a solution for this problem back in November, but I never got around to testing it until now. I'll put the code up in my next post.
So, if you put the following code in a web page and run it in IE6, you will get three different dialog boxes showing up simultaneously:
<script>I believe this problem was corrected in Internet Explorer 7 because if you run the same code in IE7, you only get one dialog box showing up at a time.
function loaded()
{
alert('loaded ' + this.src);
}
var img1 = new Image();
var img2 = new Image();
img1.onload = loaded;
img2.onload = loaded;
img1.src = "test1.png";
img2.src = "test2.png";
alert('done')
</script>
In any case, I think I came up with a solution for this problem back in November, but I never got around to testing it until now. I'll put the code up in my next post.
Wednesday, October 25, 2006
JavaScript in IE is not Multithreaded
After coding up my mutex and experimenting with it, I've discovered that Internet Explorer isn't multi-threaded. Instead, it has something worse. Much, much worse.
In any case, here's my mutex code:
So if you look at this chunk of JavaScript code
In any case, here's my mutex code:
function Mutex(maxThreads)So back to the original point. In the end, JavaScript in Internet Explorer isn't multi-threaded. There's only one thread, but it can be interrupted by callbacks or signals, and the thread won't regain control until after the signal/callback handler completes.
{
// This mutex is based on the paper "Tight Bounds for Shared Memory Symmetric
// Mutual Exclusion Problems" by Eugene Styer and Gary L. Peterson.
if (maxThreads < 2)
alert('Mutex is configured incorrectly');
this.waiting = new Array(maxThreads);
this.locks = new Array(maxThreads);
for (var n = 0; n < maxThreads; n++)
{
this.waiting[n] = null;
this.locks[n] = null;
}
this.maxThreads = maxThreads;
this.whoInCriticalSection = null;
this.turn = null;
this.get_visible = function(level, retry, me) { // This is private
if (level == -1)
{
this.waiting[0] = me;
level = 0;
retry = true;
}
else if (this.waiting[level] != me)
{
// Don't write if we can make progress
if (this.turn != me)
{
if (retry)
{
// Assume mistake, once
retry = false;
}
else
{
level = level + 1;
retry = true;
}
// Make visible again
this.waiting[level] = me;
}
}
return [level, retry];
}
this.enter = function() {
var me = new Object(); // generate a unique id for this thread
var level = -1;
var retry = false;
while (true)
{
// See if lock is available, or if it assigned to me
while (this.turn != null && this.turn != me)
{
var ret = this.get_visible(level, retry, me);
level = ret[0];
retry = ret[1];
}
this.turn = me;
var locked;
while (true)
{
// Try to get all locks
for (var pos = 0; pos < this.maxThreads; pos++)
{
if (this.locks[pos] == null)
this.locks[pos] = me;
}
// Do we have all the locks?
locked = true;
for (var pos = 0; pos < this.maxThreads; pos++)
{
if (this.locks[pos] != me)
locked = false;
}
if (this.turn != me locked) break;
}
if (this.turn != me)
{
// Lost, release locks
for (var pos = 0; pos < this.maxThreads; pos++)
{
if (this.locks[pos] == me)
this.locks[pos] = null;
}
var ret = this.get_visible(level, retry, me);
level = ret[0];
retry = ret[1];
}
else
{
break;
}
}
// Acquired lock
if (this.level > -1 && this.waiting[this.level] == me)
this.waiting[this.level] = null;
this.whoInCriticalSection = me; // Save our id for later
}
this.leave = function() {
var me = this.whoInCriticalSection; // Get our saved id
this.whoInCriticalSection = null;
// Find ID of top waitier or 0 if nobody
var next = null;
for (var pos = this.maxThreads - 1; pos >= 0; pos--)
{
if (this.waiting[pos] != null) {
alert('handoff');
next = this.waiting[pos];
break;
}
}
// Let them continue, release locks
this.turn = next;
for (var pos = 0; pos < this.maxThreads; pos++)
{
if (this.locks[pos] == me)
this.locks[pos] = null;
}
}
}
So if you look at this chunk of JavaScript code
var image = new Image();
image.onload = function() {
alert('a0');
alert('a1');
};
image.src = 'blank.gif';
alert('0');
alert('1');
you'll notice that the alerts you get are for a0, a1, 0, and then 1. The onload callback does not give up control back to the main thread until after it finishes giving its two alerts. This means that mutexes and critical sections can't be used in JavaScript because if one thread is inside a critical section and becomes interrupted, the other thread cannot yield to the other thread to let it exit its critical section. So basically, you can't use locks or critical sections or other standard programming techniques to protect important parts of code.
I don't know what the best way to fix this is. It's just messy...very, very messy.
Monday, October 23, 2006
JavaScript Mutexes 2
Actually, I started thinking some more about symmetric mutual exclusion, and I realize that I was actually mistaken. You don't actually need to use any randomization. Although in a real system, the only way to generate unique thread ids would be to use randomization, JavaScript does have one operation that is guaranteed to generate unique keys--just use new to create a new Object since new is atomic. You can then use this object as your thread id. And since it's an object, JavaScript will automatically take care of cleaning it away once you're finished with it.
So, in conclusion, JavaScript mutexes are possible if you use a shared memory symmetric mutual exclusion algorithm and if you are able to put a bound on the number of threads that may attempt to enter a mutex at any one time. This is the best approach to the problem. There are no unacceptable trade-offs that need to be taken into account (beyond the whole messiness of needing to implement your own mutexes in JavaScript in the first place).
So, in conclusion, JavaScript mutexes are possible if you use a shared memory symmetric mutual exclusion algorithm and if you are able to put a bound on the number of threads that may attempt to enter a mutex at any one time. This is the best approach to the problem. There are no unacceptable trade-offs that need to be taken into account (beyond the whole messiness of needing to implement your own mutexes in JavaScript in the first place).
Mutual Exclusion in JavaScript
I started reading up on some papers, and I've found that the type of mutual exclusion being attempted by Wallace in JavaScript is actually impossible. Totally anonymous mutual exclusion using atomic RW registers cannot be done.
That leaves two choice:
1. One can hand-out thread ids in advance (i.e. assign one to each possible callback) during a stage when one knows the code will have only one thread running
2. Use randomized mutual exclusion algorithms
Personally, I think option #1 is very hard to implement correctly, so option #2 is probably the most feasible. Basically, you randomly generate a thread id for yourself at any time (in fact, you can randomly generate a thread id every time you want to enter a mutex). Then, you can run a symmetric mutual exclusion protocol using atomic RW registers.
I found a paper that seems to give one such algorithm:
"Tight Bounds for Shared Memory Symmetric Mutual Exclusion Problems" by Eugene Styer and Gary L. Peterson.
That leaves two choice:
1. One can hand-out thread ids in advance (i.e. assign one to each possible callback) during a stage when one knows the code will have only one thread running
2. Use randomized mutual exclusion algorithms
Personally, I think option #1 is very hard to implement correctly, so option #2 is probably the most feasible. Basically, you randomly generate a thread id for yourself at any time (in fact, you can randomly generate a thread id every time you want to enter a mutex). Then, you can run a symmetric mutual exclusion protocol using atomic RW registers.
I found a paper that seems to give one such algorithm:
"Tight Bounds for Shared Memory Symmetric Mutual Exclusion Problems" by Eugene Styer and Gary L. Peterson.
Thursday, October 19, 2006
JavaScript is Multi-Threaded
I was doing some JavaScript programming where I hooked a bunch of image onload() callbacks with functions that would generate alerts, when I noticed that various alerts were firing before I had finished hooking up all my callbacks. This caused me a lot of consternation. JavaScript does not come with any threading primitives. As such, it's very hard to do any synchronization. Yet clearly, my version of Internet Explorer was triggering these callbacks asynchronously, in threads other than my main thread, resulting in various race conditions in my code.
Firefox seems to use a more sensible model. It seems like it has only one JavaScript thread (much like the single UI thread in most GUI systems), and asynchronous events queue up and are only fired when your JavaScript thread isn't doing anything (of course, that's brings up the other problem of the fact that Firefox seems to discard events if too many get queued up--but at least that's easier to handle than race conditions).
I went looking around for various mutex code to solve this problem, but nothing seems quite right. Some Bruce Wallace person created a JavaScript version of mutex, but I don't have much confidence in it. First of all, he replaced a fixed size array from Lamport's Bakery algorithm with a Map. The whole point of the fixed size array was that you could perform atomic reads and writes on it--a reasonable assumption. Once you use a Map, you're assuming atomic adds, atomic removes, and atomic iteration, which are much larger assumptions. In any case, if you had an atomic add operation, then you wouldn't need to implement the Bakery algorithm because you could use atomic add to create a mutex. His assignment of thread ids also has a race condition in it. I suppose I could just assign a separate thread id to each callback in advance, thereby avoiding the race condition, but if I did that, then I wouldn't need this Map nonsense and I could use a fixed size array because I would know how many threads there are in advance.
Instead, I simply reshaped my code so as to minimize the race condition to an atomic increment instruction. It seems unsatisfactory though. Personally, I think JavaScript should not be multi-threaded, but if it is multi-threaded, they should at least supply something like Array atomic_add() and atomic_remove() methods so that users at least have the proper primitives available for building synchronization primitives. And I'm not sure whether JavaScript engines are themselves thread-safe. I know that Mozilla's Rhino claims that it is thread-safe (I vaguely remember them stating that get and put operations were atomic), but I don't know about the engines in FireFox and IE.
Update 2011-3-31: I was going through my blog stats for the first time, and I noticed that people seem to read this post occasionally. This is an old blog post, and I explore the situation in more detail in later blog posts. Actually, JavaScript is NOT multi-threaded. In IE6, you do get some weird non-sequential behaviour, but that's due to nested asynchronous callbacks.
Firefox seems to use a more sensible model. It seems like it has only one JavaScript thread (much like the single UI thread in most GUI systems), and asynchronous events queue up and are only fired when your JavaScript thread isn't doing anything (of course, that's brings up the other problem of the fact that Firefox seems to discard events if too many get queued up--but at least that's easier to handle than race conditions).
I went looking around for various mutex code to solve this problem, but nothing seems quite right. Some Bruce Wallace person created a JavaScript version of mutex, but I don't have much confidence in it. First of all, he replaced a fixed size array from Lamport's Bakery algorithm with a Map. The whole point of the fixed size array was that you could perform atomic reads and writes on it--a reasonable assumption. Once you use a Map, you're assuming atomic adds, atomic removes, and atomic iteration, which are much larger assumptions. In any case, if you had an atomic add operation, then you wouldn't need to implement the Bakery algorithm because you could use atomic add to create a mutex. His assignment of thread ids also has a race condition in it. I suppose I could just assign a separate thread id to each callback in advance, thereby avoiding the race condition, but if I did that, then I wouldn't need this Map nonsense and I could use a fixed size array because I would know how many threads there are in advance.
Instead, I simply reshaped my code so as to minimize the race condition to an atomic increment instruction. It seems unsatisfactory though. Personally, I think JavaScript should not be multi-threaded, but if it is multi-threaded, they should at least supply something like Array atomic_add() and atomic_remove() methods so that users at least have the proper primitives available for building synchronization primitives. And I'm not sure whether JavaScript engines are themselves thread-safe. I know that Mozilla's Rhino claims that it is thread-safe (I vaguely remember them stating that get and put operations were atomic), but I don't know about the engines in FireFox and IE.
Update 2011-3-31: I was going through my blog stats for the first time, and I noticed that people seem to read this post occasionally. This is an old blog post, and I explore the situation in more detail in later blog posts. Actually, JavaScript is NOT multi-threaded. In IE6, you do get some weird non-sequential behaviour, but that's due to nested asynchronous callbacks.
Thursday, May 18, 2006
Getting an SVG Bounding Box out of Batik
I was using CorelDRAW to create some GIFs using a script, but CorelDRAW 11 has a lousy GIF exporter, so I couldn't really get the output that I wanted. So, I thought I would export my CorelDRAW data to SVG, and use the Batik SVG libraries to export the data I wanted to GIF (using the GIF exporter I described in the previous post).
I did encounter a problem though in that CorelDRAW defined a page size on the SVG document, and the Batik transcoders always exported the entire page (instead of just the parts of the page that contained my image). If I removed the page information from the SVG document, then Batik would just export an image with a default size. What I needed was a way to get a bounding box on my image, which I could then pass to Batik as the export size.
When I searched on Google, all the information that I could find about creating bounding boxes involved creating UI objects to render into, which triggers Batik to calculate bounding box information. This seemed a little bit overly heavy to me, but by looking at how the Batik transcoders render their images, I was able to just reuse their rendering code to trigger a bounding box calculation without actually rendering to a UI.
The first step is to remove the page sizing information from the SVG document (otherwise, Batik will just use the page size as the bounding box). Just run this XSLT filter over it:
<?xml:namespace prefix = xsl />
<xsl:stylesheet version="1.0" svgns="http://www.w3.org/2000/svg" xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml">
<xsl:template match="@*node()">
<xsl:copy>
<xsl:apply-templates select="@*node()">
</xsl:copy>
</xsl:template>
<!-- Remove width, height, and viewBox attributes (substitute different things in later on when we've calculated a bounding box) -->
<xsl:template match="svgns:svg/@height"></xsl:template>
<xsl:template match="svgns:svg/@width"></xsl:template>
<xsl:template match="svgns:svg/@viewBox"></xsl:template>
</xsl:stylesheet>
Then, you can take the resulting SVG code and feed it into Batik to calculate a bounding box like so:
String parser = XMLResourceDescriptor.getXMLParserClassName();
SAXSVGDocumentFactory f = new SAXSVGDocumentFactory(parser);
SVGDocument doc = (SVGDocument)f.createDocument(svg);
GVTBuilder builder = new GVTBuilder();
BridgeContext ctx;
ctx = new BridgeContext(new UserAgentAdapter());
GraphicsNode gvtRoot = builder.build(ctx, doc);
return gvtRoot.getSensitiveBounds();
You can then use the returned information to set the "viewBox," "height," and "width" attributes on the svg tag of the SVG file. When you then run the transformed SVG file through Batik, Batik will export the image with the bounding box set tightly around the contents.
-Ming
I did encounter a problem though in that CorelDRAW defined a page size on the SVG document, and the Batik transcoders always exported the entire page (instead of just the parts of the page that contained my image). If I removed the page information from the SVG document, then Batik would just export an image with a default size. What I needed was a way to get a bounding box on my image, which I could then pass to Batik as the export size.
When I searched on Google, all the information that I could find about creating bounding boxes involved creating UI objects to render into, which triggers Batik to calculate bounding box information. This seemed a little bit overly heavy to me, but by looking at how the Batik transcoders render their images, I was able to just reuse their rendering code to trigger a bounding box calculation without actually rendering to a UI.
The first step is to remove the page sizing information from the SVG document (otherwise, Batik will just use the page size as the bounding box). Just run this XSLT filter over it:
<?xml:namespace prefix = xsl />
<xsl:stylesheet version="1.0" svgns="http://www.w3.org/2000/svg" xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml">
<xsl:template match="@*node()">
<xsl:copy>
<xsl:apply-templates select="@*node()">
</xsl:copy>
</xsl:template>
<!-- Remove width, height, and viewBox attributes (substitute different things in later on when we've calculated a bounding box) -->
<xsl:template match="svgns:svg/@height"></xsl:template>
<xsl:template match="svgns:svg/@width"></xsl:template>
<xsl:template match="svgns:svg/@viewBox"></xsl:template>
</xsl:stylesheet>
Then, you can take the resulting SVG code and feed it into Batik to calculate a bounding box like so:
String parser = XMLResourceDescriptor.getXMLParserClassName();
SAXSVGDocumentFactory f = new SAXSVGDocumentFactory(parser);
SVGDocument doc = (SVGDocument)f.createDocument(svg);
GVTBuilder builder = new GVTBuilder();
BridgeContext ctx;
ctx = new BridgeContext(new UserAgentAdapter());
GraphicsNode gvtRoot = builder.build(ctx, doc);
return gvtRoot.getSensitiveBounds();
You can then use the returned information to set the "viewBox," "height," and "width" attributes on the svg tag of the SVG file. When you then run the transformed SVG file through Batik, Batik will export the image with the bounding box set tightly around the contents.
-Ming
Exporting Transparent GIFs from Java
After spending a while trying to create paletted PNG files with transparency that work in Internet Explorer (after much trying, I couldn't coax ImageMagick to create such a file, though I was able to use GIMP to do it), I decided that GIFs were the only practical file format to be used. But it's hard to get a Java program to output GIF files.
Because of the whole patent licensing issue, there aren't really any good, full-featured, unencumbered GIF exporters for Java. But there are various good bits and pieces on the 'net, which can be pieced together to make something reasonable.
First, you need some code that can actually encode the GIF file. The US government has some code that can do this (offered as part of NIH's ImageJ). All you have to do is download ImageJ and grab their ij.io.GifEncoder class.
The ImageJ code only accepts paletted data as input though. Since most images are in 24-bit colour, you need to perform a colour reduction somehow. Fortunately, someone went and took the colour quantizer used in ImageMagick and rewrote it for use in Java. It uses an octree for its colour quantization, which is a technique described in much detail elsewhere on the Internet. The quantization code needs to be reworked a bit to properly handle transparent pixels, but fixing that isn't too much work. A more important fix though is that the code performs an unnecessary optimization to save memory, which results in poor quality quantization. In the constructor for Cube, it sets the tree depth to log_4 of max_colors. Instead, the tree depth should just be set to the maximum depth of 8. Although the original ImageMagick did limit the tree depth to log_4 of max_colors, they used another optimization elsewhere in the code to reduce the effect of that limitation.
Once you combine these two pieces of code together (you have to change some of the APIs to handle transparency and other things), then you end up with a very reasonable GIF exporter.
Because of the whole patent licensing issue, there aren't really any good, full-featured, unencumbered GIF exporters for Java. But there are various good bits and pieces on the 'net, which can be pieced together to make something reasonable.
First, you need some code that can actually encode the GIF file. The US government has some code that can do this (offered as part of NIH's ImageJ). All you have to do is download ImageJ and grab their ij.io.GifEncoder class.
The ImageJ code only accepts paletted data as input though. Since most images are in 24-bit colour, you need to perform a colour reduction somehow. Fortunately, someone went and took the colour quantizer used in ImageMagick and rewrote it for use in Java. It uses an octree for its colour quantization, which is a technique described in much detail elsewhere on the Internet. The quantization code needs to be reworked a bit to properly handle transparent pixels, but fixing that isn't too much work. A more important fix though is that the code performs an unnecessary optimization to save memory, which results in poor quality quantization. In the constructor for Cube, it sets the tree depth to log_4 of max_colors. Instead, the tree depth should just be set to the maximum depth of 8. Although the original ImageMagick did limit the tree depth to log_4 of max_colors, they used another optimization elsewhere in the code to reduce the effect of that limitation.
Once you combine these two pieces of code together (you have to change some of the APIs to handle transparency and other things), then you end up with a very reasonable GIF exporter.
Monday, March 13, 2006
Firefox Should Stop Being So Smug About It's CSS Support
Because, honestly, Firefox is missing some fairly major CSS features. Notably, it's missing support for "inline-block." This problem has been known since 1999 (7 years ago!) and is listed as bug 9458, but the Mozilla people haven't been particularly inclined to fix it.
I think the problem is fairly important because it's the one CSS feature that allows for arbitrary nesting of inlines and blocks. Usually, you can put inlines in blocks and blocks in other blocks. Inline-block is the feature that lets you put blocks in inlines. This opens up a certain class of layouts that aren't otherwise possible.
Reading the bug description in bugzilla, it seems like Mozilla's Gecko rendering engine is fundamentally flawed and can't really handle this feature without a major rewrite. Internet Explorer handles inline-block well, so, in my opinion, IE has superior CSS compliance than Firefox.
I think the problem is fairly important because it's the one CSS feature that allows for arbitrary nesting of inlines and blocks. Usually, you can put inlines in blocks and blocks in other blocks. Inline-block is the feature that lets you put blocks in inlines. This opens up a certain class of layouts that aren't otherwise possible.
Reading the bug description in bugzilla, it seems like Mozilla's Gecko rendering engine is fundamentally flawed and can't really handle this feature without a major rewrite. Internet Explorer handles inline-block well, so, in my opinion, IE has superior CSS compliance than Firefox.
Subscribe to:
Posts (Atom)