jlm-blog
~jlm

17-Dec-2006

Hectic holidays

Filed under: misc — jlm @ 16:37

A friend of mine called this time of year the “hectic holidays”, and it’s absolutely correct.
I love the getting together with my family, the Christmas feast, the time off… But the gifting is very stressful. It’s hard to pick out gifts for people, it’s hard to ask for gifts, and shopping is a huge pain: Even when you know what you want to buy, going to retail stores right now is an exercise in frustration. And then the effort is wasted because they’re out of stock!
How many people can we get together under the idea that Christmas is better off without the gifts, so we can focus on nobler ideals. Can we make Christmas a holiday that’s not about commerce, but a celebration of our brotherhood with our fellow man?

16-Dec-2006

The C aliasing rules

Filed under: programming — jlm @ 11:49

A lot of people are confused by the pointer aliasing rules introduced by C99. (Sometimes called “strict aliasing”.) First, what is aliasing? When two pointers refer to the same location, they’re called “aliases”.
void fcn(int *p) { int *q = p; ... }
Here p and q are aliases. The general rule is that pointers to the same type are allowed to alias, and pointers to different types are not. (Differences like signed/unsigned and const/non-const aren’t considered significant here– they’re all in the same “aliasing class”.)
void fcn(float *p) { int *q = (int *) p; ... }
This is illegal, because p and q are aliases, but one points to float while the other points to int. In practical terms, the optimizer will reorder accesses to *p and *q across each other, or optimize out writing/reading the value back into/from memory, because they’re in different alias classes, and you’ll get mysterious bugs.
There are two exceptions to this rule: void * and char *. Pointers of these two types are allowed to alias any kind of pointer. void * can be assigned from and to any pointer without a cast, but you’re only allowed to assign it to a type which reflects the original pointer (or char *).
void intfcn(void *p) { int *q = p; ... }
void floatfcn(void *p) { float *q = p; ... }
void fcn(void) {
  int i;
  intfcn(&i);  /*  OK: int * -> void * -> int *  */
  floatfnc(&i);  /*  Bad: int * -> void * -> float *  */
}

This style is used a lot in callbacks, where it’ll look something like:
void callsoon(void (*fcn)(void *), void *arg);  /* Call fcn(arg) in one second */
void fcn(void) {
  static int i = 1;
  static float f = 0.1;
  callsoon(intfcn, &i);
  callsoon(floatfcn, &f);
}

The compiler is still assuming your int * and float * pointers won’t alias here: It’s up to you to ensure that the void * which got a float * doesn’t get turned into an int * and vice-versa. The void * is telling the compiler “I can ensure non-aliasing on my own, without you checking”. You should not use it to silence aliasing warnings, because you get those warnings in situations where the compiler is going to re-order accesses, and the void * gives it free license to do so silently!
What do you do when you really need to alias across types? First, don’t do a straight pointer typecast or go through a void * typecast for the reasons above:
void fcn(float *p) { int *q = (void *)p; ... }
void fcn(float f) { int i = *(int *)&f; ... }
void fcn(float f) { int i = *(int *)(void *)&f; ... }  /* All illegal aliasing */

Another common but illegal technique is to go through a union:
union { int i; float f; } x; x.f = f; i = x.i;  /* Illegal: unions can only be read from the last type assigned to them */
So, what do you do? One of the most common use cases is for transferring byte representations, and memcpy() works fine for this (any modern compiler will optimize it into stores).
void fcn(float *p) { int i; memcpy(&i, p, sizeof(i)); ... }  /* Safe if sizeof(int) == sizeof(float) */
void fcn(float f) { int i; memcpy(&i, &f, sizeof(i)); ... }  /* Ditto */

void fcn(float *p) { int *q; memcpy(&q, &p, sizeof(q)); ... }  /* Illegal: just a fancy way of writing q = (int *)p */
If you need fine-grained access, this is where char * comes in. It’s allowed to alias any other pointer, so the compiler can’t re-order pointer accesses across char * accesses unless it can ensure non-aliasing by other means.
void fcn(float *p) { char *q = (char *)p; ... }  /* Safe */
Note that just going though a char * on your way to an illegal alias doesn’t make it legal:
void fcn(float *p) {
  char *q = (char *)p;  /* q now validly aliases p */
  int *r = (int *)q;  /* r now validly aliases q, but p and r are still in different alias classes and *p and *r can be re-ordered across each other */
  ...
}

void fcn(float *p) { int *q = (int *)(char *)p; ... }  /* Illegal aliasing of p and q, same as q = (int *)p */
char * is safe, as long as you do your references through it, as chars (bytes), but just having a char * there doesn’t make non-char * references legal.

7-Nov-2006

What’s wrong with my sound?

Filed under: linux — jlm @ 13:03

The sound on my Ubuntu box stopped working this morning.
I was getting a ton of messages “ALSA lib pcm_dmix.c:819:(snd_pcm_dmix_open) unable to open slave”. I bounced artsd, and it said that very message on startup. After the usual futzing around, such as looking in syslog and finding nothing, I straced it, and searching for dev files noticed:
open("/dev/snd/pcmC0D0p", O_RDWR|O_NONBLOCK) = -1 EBUSY (Device or resource busy)
Well, that certainly looks like a culprit, would have been nice if artsd could have actually reported that as an error.
Now, let’s fuser /dev/snd/pcmC0D0p — huh, the two xpdf’s I’m running have it open. (WTF is xpdf permanently grabbing my pcm device?) Kill the xpdf’s, now artsd can start cleanly, and I have working sound again.
I have no idea how normal users (Ubuntu’s alleged target market) are supposed to handle this. Reboot, most likely. Works for Microsoft.

10-Oct-2006

North Korea

Filed under: misc — jlm @ 17:09

I’ve gotten some inquiries re the song from last night, so here are the lyrics.

Your technicians drilled the bore
You lit the fuse, it shook the floor
You wanted into the nuclear club if it killed ya
I’ve seen your statue below the marble arch
But listen Kim, before you start a victory march
Your country’s a poor and very hungry North Kore-a

My seismometers let me know
What really went on below
You want to pretend it was not a dud, do ya?
But remember yeah we did testing too
Vaporized part of Eniwetok Atoll like the morning dew
And the Marshalls weren’t that far from North Kore-a

Maybe push will come to shove
But remember when we took off the glove
And pushed you back from Pusan to Seoul, ha
Even the Chinese want your ear tonight
They’re not laughing now that you’ve made the Sun’s light
No it’s a close and a very pissed off Chin-a

Our talks didn’t work; they weren’t much
But you couldn’t talk so you decided to punch
I fooled my people I bet I can also fool ya
Yeah and even if it all goes wrong
I believe Armageddon won’t be long
With my hands lifted for a Hallelujah

Apologies to Leonard Cohen.

18-Sep-2006

Peeve

Filed under: misc — jlm @ 16:25

I hate in when I look up foo in the dictionary and it says “not bar”. Thanks, now I’ve gone from having to look up a word to know what it means, to having to look up another word to know what the first means, you’ve been a big help there.

26-Jul-2006

Haskell vs. C readability stawman

Filed under: programming — jlm @ 17:03

Every time I think about learning Haskell, I head over to haskell.org, read the Introduction link, and am offended by the astoundingly absurd quicksort example they provide for its superiority over C and leave in disgust.

First, let’s take a look at their Haskell implementation of quicksort:

    qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Wait one second here! Something’s fishy. At the bottom, the basic operation quicksort does is a swap. Where’re the swaps? I don’t see any swapping. I do see splicing though; quicksort doesn’t splice. This isn’t quicksort; quicksort is an in-place sort, this thing here is a list sort. This is not just an implementation detail, it’s fundamental to what quicksort is. It doesn’t splice, it makes swaps. If you have some linked lists, you sort them with something like mergesort. But for arrays, you can’t beat quicksort.

Now, we can start on the C implementation they provide…

    qsort( a, lo, hi ) int a[], hi, lo;

Huh?

If you’re a C programmer, your first impression is to boggle at this syntax. It’s been deprecated for 17 years, and most C programmers nowadays probably don’t even recognize it. What moth-eaten tome did they dig this out of? Variables of hi and lo and h and l? l+1 and l-1 as expressions? That’s the kind of thing you see at the IOCCC. Let’s choose an actual decent example of quicksort for a more honest comparison, like the one from K&R2:


/* qsort:  sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
    int i, last;
    void swap(int v[], int i, int j);

    if (left >= right)    /* do nothing if array contains */
        return;           /* fewer than two elements */
    swap(v, left, (left + right)/2); /* move partition elem */
    last = left;                     /* to v[0] */
    for (i = left+1; i <= right; i++)   /* partition */
        if (v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last);        /* restore partition elem */
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

Much more readable than that strawman example they have on the Haskell intro page!
But it’s still an apples-to-oranges comparison, because the C implementation is doing a real quicksort, and the Haskell is doing a list sort. Show me a real in-place quicksort in Haskell: It’ll turn out looking almost like the implementation in K&R, I wager.

Now, Haskell was written by people who know their computer science. They know all about quicksort, they know their example is comparing different algorithms, and they can write better C code than what they use. Why do they have to be dishonest when promoting the virtues of Haskell, hmm?

19-Jul-2006

Latest thoughts

Filed under: philosophy — jlm @ 13:37

Why is it that things we find very easy to do in our minds (process language, identify people, etc.) are things we can’t get machines to do, but things we find very cumbersome (arithmetic, data manipulation, etc.) we can make machines to do extremely well?

This dilemma, that stuff we can do easily doesn’t imply easy automatability, leads to all kinds of optimism on how human-like computers and other machines are. So what’s the root of it? I think it’s because we don’t know how to understand language, identify faces, etc. We do it, but we don’t know how! For all of recorded history, we’ve been refining mathematics, improving manufacturing processes, so we know in fine detail how to do arithmetic, how to weave cloth, etc. and we teach it to the next generation, write it down in books — whereas we don’t teach our children how to understand language, how to identify their parents and friends, these are mysteries that our brains do for us without being taught, processes which we have no visibility into the internals of. We can make a step by step guide to how to multiply numbers, and make a machine to do it. But we don’t have step-by-step guides to language. The steps are inside our brains and we get only the output. We don’t understand how we understand language, and so find it impossible to make a machine that does it.


Update: For the ~0 of you who’ll read this, I’ve just learned that this is called Moravec’s paradox.

20-Jun-2006

Pasadena Chalk Festival

Filed under: so. cal — jlm @ 09:01

Pasadena had its chalk art festival this last weekend, so what better way to give my brand new camera (a Canon PowerShot A540) a spin?
Photos here. The last photos taken by my old camera (an Olympus D-340L) in Turkey before it died are here.

3-Apr-2006

I’m back

Filed under: travel — jlm @ 11:19

I’m back home. I’ve written a lot into a travel journal, I’ll be putting it up online soon.

22-Mar-2006

Türkiye’ye gitim.

Filed under: travel — jlm @ 14:12

(“I’m off to Turkey.”)

[Flag of Turkey]

Report once I get back.

Powered by WordPress