 |
|
| |
|
|
|
|
|
|
|
Awhile back, I wrote a program that was trying to solve a design verification problem. It was trying to find a compact set of tests that moved the design through as much coverage space as possible. It used a searching algorithm to try to find low-cost ways to reach each state. Most importantly, it built tests incrementally, taking existing "proto-tests", and extending them in various ways. To keep the searcher from going in circles, I needed to filter out redundant states. Consider the following two code snippets: // Snippet 1
x = 1;
x = x + 3;
// Snippet 2
x = 2;
x = x + 2; Both of these snippets do different things, but end up at the same final state. So, while it might be important to run both of these tests, it is not necessarily useful to try to extend both. I do need to test that I can add 1 to 3 and that I can add 2 to 2, and that both leave x set to 4. I only need to extend one of these, though, while building up my database. For my particular problem, I had an absolutely gigantic state space to deal with—several billion states. That's large enough that I couldn't put together a full bitmap that could answer the question "Is this state redundant?" precisely. That's when inspiration struck. I didn't need a precise answer to "is this redundant?" For what I was doing, a "pretty good" answer was good enough. Instead of a single full bitmap, I could instead use a hash function on the state information to compress the large state number (a number between 0 and about 25 billion) into something more manageable. But what about hash collisions? To mitigate those, I reasoned, it should be possible to hash the state number with multiple, distinct hashes, and do parallel lookups on multiple bitmaps. When setting a bit (ie. marking a state as 'visited'), I set the bit in all the bitmaps. When testing to see if a state was visited, all of the bitmaps would need to say "yes" before I'd treat it as a yes. In my final code I used four bitmaps. For light to moderate "loading levels", I figured that this would reduce my likelihood of a successful collision down into the noise. For example, let's say 1% of the bits are set in my bitmap. Testing an arbitrary index against that bitmap has a 1 in 100 chance of hitting a set bit. Now let's say I have four such bitmaps, each based on a different hash of the index. Testing an arbitrary index against all four will give a hit on all four approximately 1 in 100 4 times. That's a 1000000x improvement. Or, at least, that was my reasoning. It turns out that I was just a hair off from something called a Bloom filter. The Bloom filter works on pretty much the same principle. It goes a step further and says "Why bother having separate bitmaps? Just throw everything in one big bitmap." That simplifies things a bit from what I was doing, and it should perform slightly better for the same amount of storage. At any rate, it's a nifty data structure, and I thought I'd share it. Tags: programming, things that do not suck
Current Location: insaniTI World Headquarters, Dallas, TX
Current Mood:  accomplished
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
"Every facet, every department of your mind is to be programmed by you, and unless you assume the rightful responsibility and begin to program your own mind, the world will program it for you." —Unknown, sampled on Crystal Method's "Evil 9 / Cake Hole." "S--t, if this gonna be that kinda party I'm gonna stick my d--k in the mashed potatoes!" —Unknown, sampled on Beastie Boys' "B-Boys Makin' With The Freak Freak." "My hovercraft is full of eels." —John Cleese, Monty Python's Flying Circus "I could feel that way too!" "I bet you will someday." —apparently sampled from the musical Showboat, in the NIN track "Fist F--k".
Maybe I need sleep? NAH! Tags: humor
Current Location: Left Turn Only World Headquarters, Arlington, TX
Current Mood:  exhausted
Current Music: Orbital / Funny Break (One Is Enough - Plump DJ's Mix) - The Crystal Method
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
jzIntv has driven me nuts whenever I go to debug a game. If I leave jzIntv paused for too long, the sound gets corrupted. I think I finally traced the bug back to this nearly decade-old bug: 1.4 (im14u2c 30-Aug-99): /* -------------------------------------------------------------------- */
1.4 (im14u2c 30-Aug-99): /* Step through all of the sound sources' dirty buffers and determine */
1.4 (im14u2c 30-Aug-99): /* how many additional buffers we'll be dropping. Move them to the */
1.4 (im14u2c 30-Aug-99): /* front. */
1.4 (im14u2c 30-Aug-99): /* -------------------------------------------------------------------- */
1.4 (im14u2c 30-Aug-99): will_drop = 0;
1.4 (im14u2c 30-Aug-99): for (i = 0; i < snd->src_cnt; i++)
1.4 (im14u2c 30-Aug-99): {
1.4 (im14u2c 30-Aug-99): if (snd->src[i]->drop > will_drop)
1.4 (im14u2c 30-Aug-99): will_drop = snd->src[i]->drop;
1.4 (im14u2c 30-Aug-99): snd->src[i]->tot_drop += snd->src[i]->drop;
1.4 (im14u2c 30-Aug-99): snd->src[i]->drop = 0;
1.4 (im14u2c 30-Aug-99): }
1.4 (im14u2c 30-Aug-99):
1.4 (im14u2c 30-Aug-99): drop += will_drop;See the bug? Maybe seeing the fix will help: will_drop = 0;
for (i = 0; i < snd->src_cnt; i++)
{
if (snd->src[i]->drop > will_drop)
will_drop = snd->src[i]->drop;
}
for (i = 0; i < snd->src_cnt; i++)
{
snd->src[i]->tot_drop += will_drop;
snd->src[i]->drop = 0;
}
drop += will_drop;Apparently, under certain circumstances, I would tell a sound source that I was going to drop exactly as many buffers as it asked, but then proceed to drop more than that, thereby putting my sound sources out of sync. See, in my sound architecture, each sound source can request a certain number of buffers be dropped, and I always drop the "max" across all sources. To make it all work, though, every sound source needs to know how many buffers got dropped. Hence the bug: Sometimes different sound sources would have different notions of how many buffers got dropped. How did I miss this for a decade? I *know* I've looked this code over multiple times in the last 10 years.
Edit: Well, I left it open over night, and no, this didn't fix the bug. :-( But, I'm convinced I did fix a bug. Grrrrr....
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
Is it just me or has FedEx completely lost it in terms of being a reliable overnight courier? At the very least, they don't seem to be able to deliver on services they charge extra for. Two of the last three things I've had shipped FedEx failed to live up to what I paid extra for. I paid extra for Saturday delivery on one item. FedEx didn't even put it on the truck because their computer said "Oh, it's a business and it's closed on Saturday." Except, it wasn't a business, it was a residence. And when I called FedEx's central number, they called the distribution branch, and guess what? They said "Oh, yeah, we know about that." What???? The delivery was then going to be delayed until Monday, or we could go to the distribution center to get the package. Great way to ship perishables. Most recently, I paid extra for guaranteed morning delivery on an item today. I see here it arrived at FedEx yesterday in plenty of time (3PM yesterday), but didn't depart California until, oh, 7:20AM California time this morning. That's a 9:20AM in this time zone. It's around a 4hr direct flight. So much for guaranteed morning delivery. I guess they figure "It's always morning somewhere." If I wanted it to arrive this afternoon, I wouldn't have paid extra for guaranteed morning delivery, now would I? Edit: Here's a screencap.FAIL. Edit 2: At 1:34PM, the guaranteed morning delivery arrived on the ground about 4 hours drive away from its final destination. FAIL 2Tags: things that suck
Current Mood:  annoyed
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
During this economic meltdown, many of us have been pouring over graphs, trying to put the situation into historical context based on the statistics. One fun game is to try to scale the numbers based on inflation. That is, if real growth in the economy follows a long term trend line (where "real" means scaling GDP by inflation), then any bubbles and hiccups are just deviations from this trend line. Seeing how close or far we are from this line gives us an idea of what to expect in the future since past and future are scaled roughly to the same units. Except for one thing: They keep changing the ruler. Specifically, the US government has tinkered with the Consumer Price Index a few times. ShadowStats.com tracks the CPI based on the older formulas and compares it to the newer data. It's easy to see that the newer formulas consistently give lower inflation numbers than the older formulas. Tada! Inflation is magically controlled! If you look at some of the alarming graphs, they show the Dow or S&P 500 (or what have you) strangely inflated and well above the trend line the last 15+ years. Those graphs normalize to the official CPI, though. If inflation is under-called, then growth is over-stated. If you look at the S&P 500 graph normalized against the alternate CPI for recent years, though, we weren't so far off the trend-line, and the recent decline in the markets looks like most other big dips. If that's the case, that's good news in a way—that means there isn't much further to fall if we're that far below the historical trend-line already, if our current situation plays out like previous sharp declines. (Note that that doesn't mean we'll be back on the trend-line any time soon. If you look at the post-1929-crash data in that graph, it took 24 years to come back to the trend-line.) That still raises another important question though: If we truly have been undercalling inflation systematically for 20 - 30 years (and Paul Volcker is among those who argue we have), then it's probably also true that we've been making systematically bad policy decisions based on that artificially low inflation rate for a very long time. For example, the Fed has kept interest rates too low for too long. It also helps explain the growing wealth gaps between the richest and the poorest. There are many programs that get indexed to the CPI. If the CPI is artificially low, then Social Security payments don't increase as much as they should, increases in minimum wage get pushed out, and so on. It becomes easier to justify smaller raises for employees to "keep pace with inflation," without actually keeping pace with inflation. If the inflation rate is really as high as ShadowStats.com says it is, then no wonder I don't feel like my standard of living is as dramatically higher than when I hired in at TI as the numbers might suggest it should be. I think ShadowStats may overcall some of the numbers, but I think CPI probably undercalls them.
Edit: And then there's today's XKCD: 
Edit 2: I *know* I remember seeing a quote from Volcker saying that if we measured inflation the way we did in the 70s, that the actual inflation rate would be much higher than we report. But, I can't find it. Can Dear Lazyweb help me?. Tags: economics, politics, things that suck, we're doomed
Current Mood:  drained
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
First, an apology: I haven't updated here in awhile, and I really ought to more often. Facebook has become the latest shiny bauble in my life, but I don't actually journal anything there. I just use it as a pseudo-Twitter-ish thing with a photo album. *shrug* Anyway, onto the topic of this post. I posted the comment below in response to this blog post, and I thought it stood well enough on its own, as flawed as it is, that it was worth turning into a post of my own. For awhile I've been trying to put my "we're doomed" vibe into words, and this cuts a slice of it into words.
I'm not sure it's that simple. I'm running on little sleep, so I apologize that I'm about to jot down something that seems half-formed. I think we may be reaching a point where the global standard of living plateaus, and then begins a long decline. Wage pressures are only a piece of the puzzle, and really only a symptom. I'd argue that outsourcing for wage reasons is a form of arbitrage that's successful only because it takes time for an economy to close certain gaps. The value of a dollar isn't a fixed quantity. That's why we have a notion of inflation (or deflation) as a ruler for comparing the cost of something at time X against the cost of something at time Y. If you look at wages over time, "real wages" (ie. adjusted for inflation) have been dropping for some time. It makes sense that that should happen, too: The labor pool continues to grow, but the total resources available to humans doesn't. Supply and demand says that the value of labor relative to resources should decline. Now, the pool of resources that we can actually get to does grow to a point thanks to new discoveries and advances in technology—we make more efficient farming methods, we develop new techniques for extracting petroleum from rocks, we discover new mineral deposits, and so on. Also, there are some resources that we still have an abundance 1 of, though their numbers are dwindling. For both of those reasons, the effect isn't as large as it could be. Combine that with sheer technological advances that allow us to use resources more efficiently and in ways never before dreamed, and we still enjoy an increasing standard of living. The increasing standard of living illusory in some ways. We end up in what some have called a "Tchotchki Economy" where everyone can afford gewgaws and doodads, but health care, education and other basic needs are priced out of reach and continually getting more expensive compared to wages. At some point, we start hitting real boundaries. We can only take so many fish from the sea before we collapse a fishery. We can only take so much oil from the ground before it becomes too expensive to do so. At some point we exceed the ability of increasing efficiency and ever more capable technology to outrun what amounts to fundamental limits in available resources. I think we're entering that correction now, or at least will enter it soon.
1I define abundance as "way more than we need right now." There's plenty of sand in the desert. Anyone need sand? I doubt we'll have a sand shortage any time soon. Unrefined desert sand is an abundant resource.Tags: economics, we're doomed
Current Location: Left Turn Only World Headquarters, Arlington, TX
Current Mood:  thoughtful
|
|
|
|
|
|
|
|
|
|
|
|
![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small}
mr_z's journal
impressed
3 (75.0%)
disappointed
Previous
