Monthly Archives: July 2004

Mmm.. Impressionism

Impressionist harmonies are fun to improvise on. Try giving yourself a B bass, and improvising on the black keys in an impressionist style (complete chords — 9th and 13th harmony). Then swich the bass to E and do the same thing. Back and forth: awesome.

After repeating that a couple times I closed it off with the super nifty cadence G#, C#m7, D#7.

Words are tangled

I was thinking about some neat linguistics stuff. Doubtlessly this has been studied, but I don’t know much about lingusitics yet, so I’ll study it again.

I’m thinking that words are tangled structure. In Quantum terms, they’re a composite state, made up of two base states: Meaning and Role. Take the word “ran”, for instance. This word is inflected, so it’s clearly not basic, but what are it’s components? The fundamental unit of meaning, “run”, which has no category (stop thinking about “run” the verb, and think about all things “run” represents: a run, to run, running (the adjective), running (the gerund), etc.) and the past tense verb role.

For purpose of study, let’s consider a English-like language where each word that contains meaning is written «meaning role». For instance, “I ran yesterday” would be written I «run past-verb» «yesterday adv» . (“I” doesn’t get a role, because it is a structural word that has no meaning. On the other hand, it may be «self nom-pron».)

How about this one: I «like pres-verb» «run noun». That seams to mean “I like running” or “I like to run.” Of course, these things must not be entirely orthogonal, since you get weird things like I «yesterday past-verb» «like noun», which is something like “I yesterdayed to like.” But the construction of nonsense is never something to hold back a language.

Et similia

I just watched Castle in The Sky, only the second Mayazaki film I’ve seen. The storyline was very Final Fantasyesque, and the music was top notch (to be expected from Hisaishi). The movie itself would have been excellent, once you get past of the blantancies of anime, if it weren’t for the all-around happy ending. The climax was bittersweet, and I don’t know why he had to turn it around and make it Hollywood happy. But it’s a great movie nonetheless, if you’re in to anime epics.

My Glop talk isn’t coming along as quickly as I’d like it to. I have the main points outlined, but none of the details are there yet, and I ought to really get cranking if I want a chance to practice before I speak. Glop itself is pretty neat so far, though. I feel like I’m back in the days of QBasic’s “what if I…” graphical programming, except it’s a lot faster.

Oh, and I’m now officially on the Perl 6 design team. I’m proud, though I’m not sure this changes anything. I didn’t get selected as pumpking, but that’s okay—more time for school (I was worried about that).

Speeding up OpenGL calls

A game with decent graphics (not even “good” by today’s standards) will crank through something to the order of 50,000 OpenGL calls per frame. Maintaining a 30 FPS framerate, then, would require 1,500,000 calls per second. According to my benchmark, on my box, perl is capable of making 2,100,000 do-nothing sub calls per second (regardless of whether it’s to perl or C code). So in a program like that, 71% of the processing power will be spent simply making the OpenGL calls.. That leaves 29% for everything else, including whatever processing OpenGL does within its functions on the main CPU, which simply won’t do.

So I’ve been thinking about ways to speed these up. Display lists are clearly one solution, but they’re not versatile enough. What if you wanted to cycle the colors or textures on a large structure you’re building (something a friend of mine turns out to be doing)?. You can’t use a display list, since you need to set the colors in between the calls.

What we’re battling here is the symbol table lookup and the pure op dispatch speed. We can’t get away from the symbol table lookup as long as we’re in Perl code1. It’s possible to get op dispatch overhead really low, as Parrot has so kindly pointed out. So I was thinking about a pipeline display list structure. Let me explain by example:

    my $list = pipeline {
        glcall qw{glPushMatrix};
        glcall qw{glTranslate 1, 0, 0};
        glcall qw{glColor $ $ $}; # extract three numbers from the pipeline
        prism_pipeline();         # might extract more numbers
        glcall qw{glPopMatrix};
    };
    my ($r, $g, $b) = @_;
    while (1) {
        $r += STEP * 0.1;
        $g += STEP * 0.3;
        $b += STEP * 0.7;
        $list->call;
        feed sin $r, sin $g, sin $b;
        prism_feed();   # generate the numbers that prism_pipeline asked for
    }

We’ve turned four calls into two, and with a more complex figures, who-knows-how-many into who-knows-how-few. The pipeline code would be compiled into a quick CGP loop like Parrot uses (verging on the speed of a JIT), and it would just pull numbers out of the pipeline as it needed them. Perhaps we could even build in some simple branching instructions, and, well, maybe just use Parrot, but use a Parrot that’s ready for production.

But that’s the beauty of the interface. When Parrot does become available for production, we could just slap it in place of the original CGP loop, and then we have all of parrot’s neato stuff along with it.

Now, one problem with the interface I just showed is that it lexically separates the pipeline creation and the pipeline feed — a maintenance nightmare for sure. I wonder if I could stick it in a heredoc and actually parse out the piped bits (or hey, maybe even a source filter…). Naturally, making an OpenGL call when there’s no pipeline in scope would just call it, rather than compiling anything. But I wonder if that would give people the impression that they could do more than they actually could. Perhaps I could make one conditional call like:

    if ($BUILDING) {
        glcall qw{glPushMatrix};
        # ...
    }
    else {
        feed $r, $g, $b;
    }

And that would just become an idiom. I could call if ($BUILDING) something else to make it less confusing, like:

    draw {
        glcall qw{glPushMatrix};
        # ...
    }
    with {
        feed $r, $g, $b;
    }

And the more you separate those, the more speed you get (I of course don’t want it that way, but o/~ you can’t always get what you want o/~). Then instead of making draw and with sub(&)s, I could source filter them out into the if structure above, since it’s faster (you see that Perl’s speed becomes a pain here). Of course, there’s another advantage to that, which is that I can just dynamically redefine the regular OpenGL names so it looks like regular GL code, instead of that glcall qw{} encantation.

Ideas? I don’t want to have to use Inline::C in my games just to get them to draw fast.

1Sure, I could use a source filter and turn the function calls into, say, opcode numbers, but then you still have to do the lookup on whatever function you’re using to send the numbers.

Reversing Play

Poker night tonight. We’re all coming to the point where we’re considering what each other player is thinking (including myself). I thought that we had reached this point a long time ago, but now that I bring it up honestly, it seems that’s not the case. We managed to get to a fairly advanced level of strategy without it, but now that we’re here, things are going to get very interesting.

For some reason this technique never occurred to me before: reversing the slow/fast play. Let’s take the fairly common case of a flop like A66. Now, the usual thing to do for an adept player is to bet if you’ve got the ace (to keep draws out), and wait until the turn to bet if you’ve got the 6. Now, the latter play is meant as deception anyway, but if everybody does it, it’s certainly losing its deceptive quality. So why not check raise if you’ve got the Ace (careful about reading for the 6, though)? And why not bet out immediately if you’ve got the 6?

If you bet out immediately, anyone who’s half-way active will think you don’t have it (the totally passive players may just get scared off and fold), and raise you with, say, the Ace. Second, a check raise always makes people think twice about what you might have. So if you check raise with the Ace, you can be pretty sure whether you’re ahead or behind after the opponent acts, and get out before you have to guess at the turn with high pair.

Of course, this strategy must be mixed up with the “usual” way to do it. Especially with the check-raise, you become very trappable, so you must keep your opponent guessing. Is this not the story of poker?

This took me so long to figure out, and now it seems obvious.

Chaotic System

I’ve found a really interesting chaotic system. The canonical, textbook example of a chaotic system is:

 A[n+1] = fpart(2*A[n]) 

Which keeps getting data down from successive binary digits. Start that with a number like π, and you’ll get (almost) random behavior forever. Its behavior is orderly only when it reaches a number either very close to zero or very close to one, in which case it slowly launches itself away from there, until it gets to some threshold and becomes chaotic again.

Anyway, my system is the same idea, but cooler because it has connections to continued fractions.

 A[n+1] = 1/fpart(k A[n]) 

If you look at the behavior for the initial condition π (and parameter k=1), you’ll see something not unlike the first system. But start it at e for various parameters. Here’s e at k=1:

Chaotic System k=1

At k=2:

Chaotic System k=2

At k=3:

Chaotic System k=3

Pretty cool, huh? I’m going to sit down with mathematica and explore some of those properties.

Identity Authority—WTF?

For those who haven’t been following the ID theft scene, there’s this new campaign to launch a giant server which stores everyone’s public information. It’s being launched under the guise of “identity theft protection,” and is thus being called an “identity authority.” Theoretically, it would store all transactions done by a particular consumer in the effort to monitor whether someone’s been the victim of identity theft, and to authorize them as the proper owner of their own identity.

This is the brute force solution to identity theft. As we know from software, the brute force solution is seldom a good one. In the case of monitary transactions, at least, there is a much more elegant (but still obvious) solution involving public key cryptography, a field whose implications I’ve become more and more interested in recently. For the ignorant, public key cryptography involves two critical pieces of data: a public “key”, which you publish everywhere, and a private key, which you keep to yourself. You can encrypt data with one, and decrypt it only with the other. So say I have some secret information for my friend. I encrypt the data with my friend’s public key (which everyone can see), send the encrypted data to him, to have him decrypt it with his private key. You can transfer this over any public medium, as no one can tell what it says except the holder of his private key. Okay, most of you probably knew all of that. You’ll probably know this, too:

You can use this to make stealing credit cards much, much harder. What we need is a new style of credit card. In the current situation, you pass credit card numbers around like currency. Oh, I want that piece of furniture; here’s my credit card number. Anyone with the credit card number can charge things to it. If you work at Baskin Robbins, all you have to do to steal it is take it into the back room and copy it down while you’re charging something to it. This is clearly a very insecure means of transfer.

So you make a new kind of card. This one has a computer chip in it (what doesn’t these days), supposedly one whose procedure you trust; its operation is no secret and should be easily verifiable. The chip has your private key on it, and the bank has your public key (and will readily give it to anyone who asks). The chip should be able to generate a message encrypted (or even just signed) with your private key that looks something like:

    Charge USD 3.50 to Baskin Robbins on 2004-7-7 07:06GMT
    from acct. 29348516 (Luke Palmer)

This message would be sent to your bank (again, anyone’s allowed to see it on the way) where the bank carries out the transaction. They know it’s you who issued it because your public key is the only one that correctly decrypted it. Since the message is public, you could keep one for your file and show in court that it matches your key should any funny business be carried out by your bank.

Note here that there’s no “authority.” The bank is the closest thing to it, and it doesn’t have any information everyone else doesn’t have. There’s also your card, which has the most important bit of information on it: your private key. But since the card itself generates the transaction signatures, you can’t see the key on its way out, and you’d have to be in physical possesion of the card to use it. And these things can be canelled, just like they can now.

The only need I see for an “identity authority” is so Microsoft can do free comprehensive market research. :-)