Wednesday, June 25, 2008

Ohloh Stats

So, I was told this morning that I'm on Ohloh.net's top 15 "Most Experienced C Programmers" list.

Sure enough, there I am:


Updated: Turns out, after I had consolidated my accounts, I'm now #9 on the list.

PulseAudio: A Solution In Search of a Problem

I upgraded the Linux OS on my laptop yesterday so that I had a more up-to-date GNOME installation such that I could actually build Evolution from SVN and hack it a bit to solve some annoyances I've been having. However, this is for another blog post.

So... PulseAudio. W. T. F.

All day yesterday I'd been wondering why my sound volume was so low even though I had cranked it all the way up to 100%. Since I was mostly focused getting work done yesterday, I didn't spend any time investigating until last night when I was forced to do so.

I don't remember the exact order of things, but I did watch an episode of Harsh Realm in Xine while also IM'ing some friends in Pidgin, but the sound was so low I could barely hear anything. So a friend on IRC suggested I kill pulseaudio and restart it as this supposedly would help fix the "wonkyness" (evidently I'm not the only one with PulseAudio problems).

This worked for a while, long enough to play the DVD iirc, but afterward I had no sound. So I thought "well, I guess this is just more PulseAudio 'wonkyness', so let me kill pulseaudio again". This time when I killed it, my sound card got flooded with every audio event that had happened over the hour or so I was running Xine. Yay. (that was a sarcastic yay in case you couldn't tell)

Audio worked again for a bit. At one point, a friend IM's me a link so I clicked it and no browser started up (which seemed a bit odd). Tried it again, still nothing. So I figured "ok, I'll just launch firefox from my gnome-terminal and see if that prints any errors". No errors, but it did just hang. Oh goodie. Ctrl-C'd and killed pulseaudio again. At this point my friend IM'd me again which made Pidgin completely lock up:

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
26422 fejj      20   0 3054m 1.3g  27m D  198 33.2  18:55.68 pidgin

So the issues of memory usage are perfect for another rant blog post, but the point is that pidgin is completely locked. I can't even kill -9 it (I tried multiple times).

I had to Ctrl+Alt+F1, login as root, and `init 3`

At this point I was so frustrated that I uninstalled each and every package with pulseaudio in the name before going back to X.

Low and behold, after that my audio works flawlessly (well, the Pidgin IM audio events make some crackling which I don't recall happening before I reinstalled, but I can live with it - especially since other audio seems crisp).

So yea... the stuff that the Linux Hater says is all true. He even complained about audio under Linux a while back (couldn't remember which entry it was with a quick look over the entry names).

The point of this story is that PulseAudio appears to be a solution in search of a problem (quite common in the land of Linux afaict).

As I was bitching about this to a hacker friend of mine, he asked me "isn't PulseAudio for sound mixing or something? So multiple programs can all play audio at the same time?".

Nope, because ALSA seemed to do mixing just fine for me in the past.

A quick Google search for PulseAudio reveals that it is supposed to allow fancy stuff like redirecting sound to another host machine for playing.

...just as I suspected: a solution in search of a problem.

Seriously though, who the hell needs that feature on their desktop/laptop machines? No one, that's who. The only people who might need that are thin clients - so why install it by default? Why not just have the sysadmins for those thin-client networks set this up?

PulseAudio is a clusterfuck for basic desktop audio needs afaict.

Sigh.

Update: Apparently I offended the PulseAudio developer with my "it's a solution in search of a problem" statement. For that, I apologize. A number of people have explained what exactly it is supposed to be solving. Unfortunately, none of the problems it is solving seem to be problems I need solved (maybe my sound cards in all my machines have hardware mixing support? I don't know. Or maybe dmix is plenty good enough for me).

However, I still get the feeling that PA is not quite ready for wide desktop adoption because people on other distros are having some of the same problems I had and this is not good.

I'd expect a similar rant from people if Evolution's current IMAP provider was replaced with my IMAP4 provider. As nice as my IMAP4 provider replacement is for my usage, there are no doubt new problems that it might currently have over the old implementation that would break things for some people. (Hence why I have not pushed for it to replace the old IMAP provider until I'm sure it is ready.)

Also, this was tagged as a rant. I had every right to be frustrated because things weren't working like they have worked Just Fine(tm) for me for years. I've had to put up with far worse personal attacks on myself and software I've been involved with over the years than anything I said on this blog (and lets face it, this was not a personal attack aimed at the PA devs - it was just me venting my frustration with a piece of software), so I think some people took this post way too personally.

Friday, June 20, 2008

It's a Beautiful Evening...


A Rainbow Over the Church, originally uploaded by jstedfast.

Looked up just after a thunderstorm tonight and caught this rainbow - just had to take a picture of it ;-)

Saturday, June 14, 2008

Calculating the Nearest Power of 2

The typical implementation for finding the nearest power of 2 for a given value is as follows:

static uint32_t
nearest_pow (uint32_t num)
{
    uint32_t n = 1;

    while (n < num)
        n <<= 1;

    return n;
}

This implementation's performance, unfortunately, suffers as the value of num increases. Luckily there is another approach that takes a constant time no matter how large the value:

static uint32_t
nearest_pow (uint32_t num)
{
    uint32_t n = num > 0 ? num - 1 : 0;

    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;

    return n;
}

A simple performance test might be:

int main (int argc, char **argv)
{
    uint32_t i, n = 0;

    for (i = 0; i < INT_MAX / 10; i++)
        n += nearest_pow (i);

    return n > 0 ? 1 : 0;
}

The run-time difference between the two implementations on my AMD Athlon (/proc/cpuinfo reports AMD Athlon(TM) XP 3200+ @ 2200.141 MHz) is impressive. For performance testing, I compiled with gcc -O2 which I figure is the typical default for most packaged software on Linux distributions.

The brain-dead approach has the following results:

[fejj@serenity cvs]$ time ./pow

real 0m12.034s
user 0m11.809s
sys 0m0.032s

The bitwise implementation is insanely fast:

[fejj@serenity cvs]$ time ./pow2

real 0m1.361s
user 0m1.304s
sys 0m0.008s

Now... to be fair, the if you are using small values for num, then it's possible that the brain-dead approach might be faster. Let's try the same main() for-loop again, but this time let's request nearest_pow() with a value of 1 each time. Since it is likely that the results will be far too fast to really compare, let's also bump up the number of iterations to UINT_MAX.

[fejj@serenity cvs]$ time ./pow

real 0m0.003s
user 0m0.000s
sys 0m0.004s
[fejj@serenity cvs]$ time ./pow2

real 0m0.002s
user 0m0.000s
sys 0m0.000s

Unfortunately, both are still far too fast to really compare performance. Let's try bumping up the value of num to see if we can find the point at which the while-loop approach starts to fall behind the bitwise approach. To start, let's try passing the value of 2 as the num argument:

[fejj@serenity cvs]$ time ./pow

real 0m0.002s
user 0m0.000s
sys 0m0.004s
[fejj@serenity cvs]$ time ./pow2

real 0m0.002s
user 0m0.000s
sys 0m0.000s

It looks like the bitwise approach may be faster than the while-loop approach for the value of 2, but it's a bit hard to tell for sure with only UINT_MAX loops. We'd have to switch to using a 64bit i to know for sure and I'm not sure it's that important. Let's try 3 and see what we get:

[fejj@serenity cvs]$ time ./pow

real 0m6.053s
user 0m5.968s
sys 0m0.004s
[fejj@serenity cvs]$ time ./pow2

real 0m0.003s
user 0m0.000s
sys 0m0.004s

Well, hot diggity... I think we have ourselves a winner. This suggests that for all values of num larger than 2, the performance of the while-loop approach will be outmatched by the bitwise approach and that for values less-than-or-equal to 2, the performance is nearly identical.

Update: Thanks to the anonymous commenter that noticed that my original main() program was allowing the compiler to optimize out the call to nearest_pow() in the bitwise implementation. As suggested, I updated the for-loop to accumulate the output and then used it after the loop to avoid this problem. It only seemed to change the results for the bitwise implementation in the first test, however (before the change, it reported 0.002s). Still, on my machine it is approx. 10x faster for the first test case and seems to lose no performance even in the optimal conditions for the while-loop implementation.

Update2: I was just pointed to the Linux kernel's fls() implementation for x86. Here is a new implementation using inline assembler for x86:

static uint32_t
nearest_pow (uint32_t num)
{
    int bit;

    __asm__("bsrl %1,%0\n\t"
            "jnz 1f\n\t"
            "movl $-1,%0\n"
            "1:" : "=r" (bit) : "rm" (num));

    return (1 << (bit + 1));
}

The results for the original INT_MAX / 10 iterations using i as the num argument yields the following results:

[fejj@serenity cvs]$ time ./pow3

real 0m1.335s
user 0m1.296s
sys 0m0.004s

The results seem negligibly faster than the C bitwise implementation and obviously less portable :(

Update3: A friend of mine, Stephane Delcroix, has just pointed me at a solution to this problem that he came up the other day:

static uint32_t
nearest_pow (uint32_t num)
{
    uint32_t j, k;
    (j = num & 0xFFFF0000) || (j = num);
    (k = j & 0xFF00FF00) || (k = j);
    (j = k & 0xF0F0F0F0) || (j = k);
    (k = j & 0xCCCCCCCC) || (k = j);
    (j = k & 0xAAAAAAAA) || (j = k);
    return j << 1;
}

The results of this implementation are as follows:

[fejj@serenity cvs]$ time ./pow4

real 0m1.249s
user 0m1.204s
sys 0m0.004s

This is actually faster than both the bitwise and the assembler implementations above!

There are two things to be aware of, though:

  • When num is 0, the value of 0 is returned (which may not be desirable depending on what you are doing with it)
  • If num is a power of 2, then instead of returning num, this implementation will return the next higher power of 2

Friday, June 13, 2008

Linux Haters

Okay, I have to join in and say that I, too, have been enjoying Linux Hater's Blog these past few days.

He makes a lot of good points and I like his humor ;-)

Saturday, June 7, 2008

GMime 2.3.2

Just released GMime 2.3.2 last night which took some comments about the GMimeHeaderIter API into consideration (like allowing iters to be on the stack).

It also now has support for multipart/encrypted PGP/MIME parts that have been both signed and encrypted in a single pass (support for this exists for both encrypting and decrypting).

Many more .NET API improvements as well.

Check it out!

Updated: Just released 2.3.3 after a weekend of hacking.

Wednesday, June 4, 2008

Netscape Plugin Tips & Tricks

If your Firefox plugin is scriptable, you should probably be validating the NPVariant arguments that you are passed in your invoke() callback. Unfortunately, this gets tedious and error-prone if you allow arguments to your methods to be of more than a single type (e.g. you accept a date as either a string or integer) or if you have optional arguments.

As I was debugging a crash in Moonlight, I discovered that we weren't properly checking argument-types properly in all cases (this particular bug was caused because the javascript had passed a bad argument to one of our methods which accepted either a string or null). To protect against this in a more robust way, I came up with the following helper functions:

typedef enum {
    MethodArgTypeNone   = (0),
    MethodArgTypeVoid   = (1 << NPVariantType_Void),
    MethodArgTypeNull   = (1 << NPVariantType_Null),
    MethodArgTypeBool   = (1 << NPVariantType_Bool),
    MethodArgTypeInt32  = (1 << NPVariantType_Int32),
    MethodArgTypeDouble = (1 << NPVariantType_Double),
    MethodArgTypeString = (1 << NPVariantType_String),
    MethodArgTypeObject = (1 << NPVariantType_Object),
    MethodArgTypeAny    = (0xff)
} MethodArgType;

static MethodArgType
decode_arg_ctype (char c)
{
    switch (c) {
    case 'v': return MethodArgTypeVoid;
    case 'n': return MethodArgTypeNull;
    case 'b': return MethodArgTypeBool;
    case 'i': return MethodArgTypeInt32;
    case 'd': return MethodArgTypeDouble;
    case 's': return MethodArgTypeString;
    case 'o': return MethodArgTypeObject;
    case '*': return MethodArgTypeAny;
    default:
        return MethodArgTypeNone;
    }
}

static MethodArgType
decode_arg_type (const char **in)
{
    MethodArgType type = MethodArgTypeNone;
    register const char *inptr = *in;
    
    if (*inptr == '(') {
        inptr++;
        while (*inptr && *inptr != ')') {
            type |= decode_arg_ctype (*inptr);
            inptr++;
        }
    } else {
        type = decode_arg_ctype (*inptr);
    }
    
    inptr++;
    *in = inptr;
    
    return type;
}

/**
 * check_arg_list:
 * @arglist: a string representing an arg-list token (see grammar below)
 * @args: NPVariant argument count
 * @argv: NPVariant argument vector
 *
 * Checks that the NPVariant arguments satisfy the argument count and
 * types expected (provided via @typestr).
 *
 * The @typestr argument should follow the following syntax:
 *
 * simple-arg-type ::= "v" / "n" / "b" / "i" / "d" / "s" / "o" / "*"
 *                     ; each char represents one of the following
 *                     ; NPVariant types: Void, Null, Bool, Int32,
 *                     ; Double, String, Object and wildcard
 *
 * arg-type        ::= simple-arg-type / "(" 1*(simple-arg-type) ")"
 *
 * optional-args   ::= "[" *(arg-type) "]"
 *
 * arg-list        ::= *(arg-type) (optional-args)
 *
 *
 * Returns: %true if @argv matches the arg-list criteria specified in
 * @arglist or %false otherwise.
 **/
static bool
check_arg_list (const char *arglist, uint32_t argc, const NPVariant *argv)
{
    const char *inptr = arglist;
    MethodArgType mask;
    uint32_t i = 0;
    
    /* check all of the required arguments */
    while (*inptr && *inptr != '[' && i < argc) {
        mask = decode_arg_type (&inptr);
        if (!(mask & (1 << argv[i].type))) {
            /* argv[i] does not match any of the expected types */
            return false;
        }
        
        i++;
    }
    
    if (*inptr && *inptr != '[' && i < argc) {
        /* we were not provided enough arguments */
        return false;
    }
    
    /* now check all of the optional arguments */
    inptr++;
    while (*inptr && *inptr != ']' && i < argc) {
        mask = decode_arg_type (&inptr);
        if (!(mask & (1 << argv[i].type))) {
            // argv[i] does not match any of the expected types
            return false;
        }
        
        i++;
    }
    
    if (i < argc) {
        /* we were provided too many arguments */
        return false;
    }
    
    return true;
}

An example usage might be check_arg_list ("(so)i(nso)[bb]", argc, argv). In this example, the first argument is expected to be either a string or object. The second argument would be an int32. The third argument would be null, a string, or an object. The 4th and 5th arguments are both of type bool if they are present.

Since the NPVariant struct is a widely-used concept in C programming, you might find my hack useful for other projects as well.

Enjoy!

Sunday, June 1, 2008

How To Survive Poisonous People

This is an interesting Google Tech Talk about how to survive poisonous people in F/LOSS communities. I probably find it interesting at least in part because there are a couple of very loud poisonous people constantly attacking the GNOME and Mono projects (both of which I'm involved with), but it's a great talk to listen to anyway.

I personally love the "Hostility" slide at around 29 minutes into the talk:

Hostility
  • Insults the status quo
  • Angrily demands help
  • Attempts to blackmail
  • Attempts to deliberately rile
  • Makes accusations of conspiracy (paranoia)

The bold/italic bit is a big hint-hint to the handful of people (not that they aren't also guilty of some of the others points) I'm referring to as the poisonous people around GNOME and Mono ;)

Code Snippet Licensing

All code posted to this blog is licensed under the MIT/X11 license unless otherwise stated in the post itself.