Code Snippet Licensing

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

Monday, October 31, 2011

So you think that money is the root of all evil?

Have you ever asked what is the root of money? Money is a tool of exchange, which can't exist unless there are goods produced and men able to produce them. Money is the material shape of the principle that men who wish to deal with one another must deal by trade and give value for value. Money is not the tool of the moochers, who claim your product by tears, or of the looters, who take it from you by force. Money is made possible only by the men who produce. Is this what you consider evil?

When you accept money in payment for your effort, you do so only on the conviction that you will exchange it for the product of the effort of others. It is not the moochers or the looters who give value to money. Not an ocean of tears not all the guns in the world can transform those pieces of paper in your wallet into the bread you will need to survive tomorrow. Those pieces of paper, which should have been gold, are a token of honor--your claim upon the energy of the men who produce. Your wallet is your statement of hope that somewhere in the world around you there are men who will not default on that moral principle which is the root of money. Is this what you consider evil?

Have you ever looked for the root of production? Take a look at an electric generator and dare tell yourself that it was created by the muscular effort of unthinking brutes. Try to grow a seed of wheat without the knowledge left to you by men who had to discover it for the first time. Try to obtain your food by means of nothing but physical motions--and you'll learn that man's mind is the root of all the goods produced and of all the wealth that has ever existed on earth.

But you say that money is made by the strong at the expense of the weak? What strength do you mean? It is not the strength of guns or muscles. Wealth is the product of man's capacity to think. Then is money made by the man who invents a motor at the expense of those who did not invent it? Is money made by the intelligent at the expense of the fools? By the able at the expense of the incompetent? By the ambitious at the expense of the lazy? Money is made--before it can be looted or mooched--made by the effort of every honest man, each to the extent of his ability. An honest man is one who knows that he can't consume more than he has produced.

To trade by means of money is the code of the men of good will. Money rests on the axiom that every man is the owner of his mind and his effort. Money allows no power to prescribe the value of your effort except the voluntary choice of the man who is willing to trade you his effort in return. Money permits you to obtain for your goods and your labor that which they are worth to the men who buy them, but no more. Money permits no deals except those to mutual benefit by the unforced judgment of the traders. Money demands of you the recognition that men must work for their own benefit, not for their own injury, for their gain, not their loss--the recognition that they are not beasts of burden, born to carry the weight of your misery--that you must offer them values, not wounds--that the common bond among men is not the exchange of suffering, but the exchange of goods. Money demands that you sell, not your weakness to men's stupidity, but your talent to their reason; it demands that you buy, not the shoddiest they offer, but the best that your money can find. And when men live by trade--with reason, not force, as their final arbiter--it is the best product that wins, the best performance, the man of best judgment and highest ability--and the degree of a man's productiveness is the degree of his reward. This is the code of existence whose tool and symbol is money. Is this what you consider evil?

But money is only a tool. It will take you wherever you wish, but it will not replace you as the driver. It will give you the means for the satisfaction of your desires, but it will not provide you with desires. Money is the scourge of the men who attempt to reverse the law of causality--the men who seek to replace the mind by seizing the products of the mind.

Money will not purchase happiness for the man who has no concept of what he wants: money will not give him a code of values, if he's evaded the knowledge of what to value, and it will not provide him with a purpose, if he's evaded the choice of what to seek. Money will not buy intelligence for the fool, or admiration for the coward, or respect for the incompetent. The man who attempts to purchase the brains of his superiors to serve him, with his money replacing his judgment, ends up by becoming the victim of his inferiors. The men of intelligence desert him, but the cheats and the frauds come flocking to him, drawn by a law which he has not discovered: that no man may be smaller than his money. Is this the reason why you call it evil?

Only the man who does not need it, is fit to inherit wealth--the man who would make his own fortune no matter where he started. If an heir is equal to his money, it serves him; if not, it destroys him. But you look on and you cry that money corrupted him. Did it? Or did he corrupt his money? Do not envy a worthless heir; his wealth is not yours and you would have done no better with it. Do not think that it should have been distributed among you; loading the world with fifty parasites instead of one, would not bring back the dead virtue which was the fortune. Money is a living power that dies without its root. Money will not serve the mind that cannot match it. Is this the reason why you call it evil?

Money is your means of survival. The verdict you pronounce upon the source of your livelihood is the verdict you pronounce upon your life. If the source is corrupt, you have damned your own existence. Did you get your money by fraud? By pandering to men's vices or men's stupidity? By catering to fools, in the hope of getting more than your ability deserves? By lowering your standards? By doing work you despise for purchasers you scorn? If so, then your money will not give you a moment's or a penny's worth of joy. Then all the things you buy will become, not a tribute to you, but a reproach; not an achievement, but a reminder of shame. Then you'll scream that money is evil. Evil, because it would not pinch-hit for your self-respect? Evil, because it would not let you enjoy your depravity? Is this the root of your hatred of money?

Money will always remain an effect and refuse to replace you as the cause. Money is the product of virtue, but it will not give you virtue and it will not redeem your vices. Money will not give you the unearned, neither in matter nor in spirit. Is this the root of your hatred of money?

Or did you say it's the love of money that's the root of all evil? To love a thing is to know and love its nature. To love money is to know and love the fact that money is the creation of the best power within you, and your passkey to trade your effort for the effort of the best among men. It's the person who would sell his soul for a nickel, who is loudest in proclaiming his hatred of money--and he has good reason to hate it. The lovers of money are willing to work for it. They know they are able to deserve it.

Let me give you a tip on a clue to men's characters: the man who damns money has obtained it dishonorably; the man who respects it has earned it.

Run for your life from any man who tells you that money is evil. That sentence is the leper's bell of an approaching looter. So long as men live together on earth and need means to deal with one another--their only substitute, if they abandon money, is the muzzle of a gun.

But money demands of you the highest virtues, if you wish to make it or to keep it. Men who have no courage, pride or self-esteem, men who have no moral sense of their right to their money and are not willing to defend it as they defend their life, men who apologize for being rich--will not remain rich for long. They are the natural bait for the swarms of looters that stay under rocks for centuries, but come crawling out at the first smell of a man who begs to be forgiven for the guilt of owning wealth. They will hasten to relieve him of the guilt--and of his life, as he deserves.

Then you will see the rise of the men of the double standard--the men who live by force, yet count on those who live by trade to create the value of their looted money--the men who are the hitchhikers of virtue. In a moral society, these are the criminals, and the statutes are written to protect you against them. But when a society establishes criminals-by-right and looters-by-law--men who use force to seize the wealth of disarmed victims--then money becomes its creators' avenger. Such looters believe it safe to rob defenseless men, once they've passed a law to disarm them. But their loot becomes the magnet for other looters, who get it from them as they got it. Then the race goes, not to the ablest at production, but to those most ruthless at brutality. When force is the standard, the murderer wins over the pickpocket. And then that society vanishes, in a spread of ruins and slaughter.

Do you wish to know whether that day is coming? Watch money. Money is the barometer of a society's virtue. When you see that trading is done, not by consent, but by compulsion--when you see that in order to produce, you need to obtain permission from men who produce nothing--when you see that money is flowing to those who deal, not in goods, but in favors--when you see that men get richer by graft and by pull than by work, and your laws don't protect you against them, but protect them against you--when you see corruption being rewarded and honesty becoming a self-sacrifice--you may know that your society is doomed. Money is so noble a medium that it does not compete with guns and it does not make terms with brutality. It will not permit a country to survive as half-property, half-loot.

Whenever destroyers appear among men, they start by destroying money, for money is men's protection and the base of a moral existence. Destroyers seize gold and leave to its owners a counterfeit pile of paper. This kills all objective standards and delivers men into the arbitrary power of an arbitrary setter of values. Gold was an objective value, an equivalent of wealth produced. Paper is a mortgage on wealth that does not exist, backed by a gun aimed at those who are expected to produce it. Paper is a check drawn by legal looters upon an account which is not theirs: upon the virtue of the victims. Watch for the day when it bounces, marked, "Account overdrawn."

When you have made evil the means of survival, do not expect men to remain good. Do not expect them to stay moral and lose their lives for the purpose of becoming the fodder of the immoral. Do not expect them to produce, when production is punished and looting rewarded. Do not ask, "Who is destroying the world?" You are.

You stand in the midst of the greatest achievements of the greatest productive civilization and you wonder why it's crumbling around you, while you're damning its life-blood--money. You look upon money as the savages did before you, and you wonder why the jungle is creeping back to the edge of your cities. Throughout men's history, money was always seized by looters of one brand or another, whose names changed, but whose method remained the same: to seize wealth by force and to keep the producers bound, demeaned, defamed, deprived of honor. That phrase about the evil of money, which you mouth with such righteous recklessness, comes from a time when wealth was produced by the labor of slaves--slaves who repeated the motions once discovered by somebody's mind and left unimproved for centuries. So long as production was ruled by force, and wealth was obtained by conquest, there was little to conquer, Yet through all the centuries of stagnation and starvation, men exalted the looters, as aristocrats of the sword, as aristocrats of birth, as aristocrats of the bureau, and despised the producers, as slaves, as traders, as shopkeepers--as industrialists.

To the glory of mankind, there was, for the first and only time in history, a country of money--and I have no higher, more reverent tribute to pay to America, for this means: a country of reason, justice, freedom, production, achievement. For the first time, man's mind and money were set free, and there were no fortunes-by-conquest, but only fortunes-by-work, and instead of swordsmen and slaves, there appeared the real maker of wealth, the greatest worker, the highest type of human being--the self-made man--the American industrialist.

If you ask me to name the proudest distinction of Americans, I would choose--because it contains all the others--the fact that they were the people who created the phrase "to make money." No other language or nation had ever used these words before; men had always thought of wealth as a static quantity--to be seized, begged, inherited, shared, looted or obtained as a favor. Americans were the first to understand that wealth has to be created. The words "to make money" hold the essence of human morality.

Yet these were the words for which Americans were denounced by the rotted cultures of the looters' continents. Now the looters' credo has brought you to regard your proudest achievements as a hallmark of shame, your prosperity as guilt, your greatest men, the industrialists, as blackguards, and your magnificent factories as the product and property of muscular labor, the labor of whip-driven slaves, like the pyramids of Egypt. The rotter who simpers that he sees no difference between the power of the dollar and the power of the whip, ought to learn the difference on his own hide-- as, I think, he will.

Until and unless you discover that money is the root of all good, you ask for your own destruction. When money ceases to be the tool by which men deal with one another, then men become the tools of men. Blood, whips and guns--or dollars. Take your choice--there is no other--and your time is running out.

-- Francisco d'Anconia
Atlas Shrugged by Ayn Rand

Thursday, September 15, 2011

MonoTouch Tips & Tricks: Updating the Location of an MKAnnotation

I just spent a day figuring this out, so figured I'd share it with the world because I'm sure other people are going to want to know how to do this...

So the question is,

How can I get my MKMapView to respond to coordinate changes in my custom MKAnnotations?

As it turns out, this is incredibly simple. In your MKAnnotation subclass, whenever you want to change your Coordinate property value, you need to do the following:

void UpdateCoordinate (CLLocationCoordinate2D newCoordinate)
{
    this.WillChangeValue ("coordinate");
    this.Coordinate = newCoordinate;
    this.DidChangeValue ("coordinate");
}

That's it! It really is that simple...

The reason this works is because MKMapView observes changes in its list of MKAnnotations, you just need to signal to it that changes are about to happen (and did happen).

Happy hacking!

Sunday, August 14, 2011

GMime 2.5.10: A Call For Testers

I've just released GMime 2.5.10 which I hope to be the last of the 2.5 releases before I release 2.6.0. I feel that I've stretched the development of 2.6.0 out for far too long (2.5 development began at the end of April, 2009) and even though I didn't get around to doing everything I had hoped to do, I feel that the latest 2.5.x releases are such an improvement over 2.4.x that I just want to get it out there for developers to start using. But before I make a 2.6.0 release, I'm hoping to get some feedback and some testing.

What's new?

New for the release of 2.5.10 is GMimePartIter which replaces the need for g_mime_object_foreach()and its awkward callback requirement, instead allowing you to take the far nicer iterator approach that is popular in the C# and Java worlds (known as IEnumerator in C#). This new iterator, like the foreach function it replaces, iterates over the MIME tree structure in depth-first order.

Inspired by IMAP's FETCH body part-specifier syntax, I've implemented a method allowing you to jump to a part based on a part-specifier string (aka a path): g_mime_part_iter_jump_to(). Also implemented is a function called g_mime_part_iter_get_path(), which can be used to tell you the current part-specifier path of the iterator.

For example, if you had the following MIME message structure:

multipart/related
  multipart/alternative
    text/plain
    text/html
  image/jpeg

The body part-specifier paths would be:

1    multipart/alternative
1.1  text/plain
1.2  text/html
2    image/jpeg

This means that g_mime_part_iter_jump_to(iter, "1.2") would jump to the part specified by the path "1.2" which, as we can see above, would be the text/html part. Calling g_mime_part_iter_next(iter) would iterate to the next part, being the image/jpeg, while calling g_mime_part_iter_prev(iter) would iterate backwards to the text/plain part and calling it again would iterate backwards to the multipart/alternative.

What I Need From Testers

My feeling is that developers will want to use this cool new body part-specifier path functionality for aiding them in implementing IMAP servers and/or clients. Because of this, it would be great if GMime's implementation matched IMAP's specification exactly. The problem is that I don't have the time or energy to verify that the paths work out to be identical in all cases. So... if you are one of those developers who is interested in using this functionality and need it to be identical to IMAP's syntax (or would really like it to be), I'm hoping that you could test it out and make sure that it matches. Especially worthwhile of testing, I'd imagine, is having message/rfc822 parts in the tree. I suspect that, if anywhere, this is where differences may be.

If body part-specifier paths aren't something you care about, don't fret; the rest of the iterator API needs testing as well and if you have no interest in the iterator API at all, perhaps you'd be willing to test the S/MIME functionality (especially since I haven't figured out how to test it myself, given that I don't have an S/MIME cert nor have I figured out how to generate one or add one to my gpgsm keyring).

Your help will be greatly appreciated.

Wednesday, August 3, 2011

Debugging Your MonoTouch Apps: The Future

One of the "paper cuts" developers have been having with developing their MonoTouch 4.0.x (and earlier) applications is that for some networking setups, the IP of the developer's workstation detected by MonoDevelop and given to the iPhone or iPad device for debugging purposes is not correct. This often happens if the WiFi is a different network than the network that the developer's machine is connected to (although there are other scenarios as well).

Since it does not seem to be widely known about, allow me to point out that current versions of MonoTouch allow developers to modify the IP that the runtime should connect to for debugging via the iOS Settings app found on any iPhone or iPad (or Simulator). You can see a screenshot of this per-App Settings page in the screenshot to the left. Each of these fields are editable, allowing you to override the defaults filled-in by MonoDevelop.

For our upcoming 4.1 release, Rolf Kvinge and I (but mostly Rolf) have been working on improving this. Rolf has modified the code to check the value of the IP provided in the per-App Settings and if it is set to nil or "automatic", the debugger falls back to checking for a file bundled with the app called MonoTouchDebugConfiguration.txt which can list any number of IP's to try and connect to, each one being on a separate line prefixed with "IP: ". For example:

IP: 10.0.1.31
IP: 192.168.1.31
IP: 204.11.102.79

The runtime will then attempt to connect to each of these IPs asynchronously until it establishes a connection to one of them (at which point it aborts the other waiting connections). This config file solution will hopefully help simplify things for developers a bit by allowing them to pre-configure which IPs to try for their local network configuration w/o having to manually override the iPhone debug settings on the device or simulator.

For Phase 2 of our plan for World Domination, Rolf is hard at work adding support to MonoDevelop and the runtime to allow for USB debugging which will obsolete the above functionality in future versions where the developer has a MonoDevelop which supports USB debugging. For developers stuck on an older MonoDevelop (like 2.4), the solution illustrated above requires no changes to MonoDevelop and so will be available for use.

Thursday, April 14, 2011

Moonlight on Android

For the past week, the Moonlight team has been busy porting Moonlight to Android devices and today, showed it off at Mix 11.

The video shows Moonlight running on both a Motorola Xoom tablet and a Nexus S phone.

Keep in mind that we're still in the early phases of porting and there's still a lot of work left to do before we can ship a product, but it's still exciting!

Update: For those of you reading my blog from Planet GNOME (or some other planet that doesn't show the video above), you can find it here, on YouTube.

Update: Now you can see Moonlight rendering video with 3D transforms, too!

Thursday, April 7, 2011

Optimizing Merge Sort

A number of years ago I wrote about the Merge Sort algorithm. One of the advantages of Merge Sort is that it is a stable sort, meaning that elements that compare as being equal remain in their original order after being sorted.

Well, today I had need of employing a stable sorting routine for sorting elements by a ZIndex in Moonlight. Up until today, we had been using qsort() which, while not guaranteed to be a stable sort on any platform, happens to be implemented in glibc as a stable sort except in out-of-memory conditions. Since we'd like Moonlight to work on platforms other than Linux+glibc (such as Mac OS or BSD), it has become important enough to implement properly.

To start, I dusted off my generic MergeSort() implementation from years ago when I was writing articles about various sorting algorithms. This is what I had to start with:

#define MID(lo, hi) (lo + ((hi - lo) >> 1))

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int (* compare) (const void *, const void *))
{
    register char *lo, *hi, *b;
    char *al, *am, *ah;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    while (lo < am && hi < ah) {
        if (compare (lo, hi) <= 0) {
            memcpy (b, lo, size);
            lo += size;
        } else {
            memcpy (b, hi, size);
            hi += size;
        }
        
        b += size;
    }
    
    if (lo < am)
        memcpy (b, lo, am - lo);
    else if (hi < ah)
        memcpy (b, hi, (ah + size) - hi);
    
    memcpy (al, buf, ah - al);
}

int
MergeSort (void *base, size_t nmemb, size_t size,
           int (* compare) (const void *, const void *))
{
    void *tmp;
    
    if (nmemb < 2)
        return 0;
    
    if (!(tmp = malloc (nmemb * size))) {
        errno = ENOMEM;
        return -1;
    }
    
    msort (base, tmp, 0, nmemb - 1, size, compare);
    
    free (tmp);
    
    return 0;
}

Since performance is very important, I clocked this implementation against qsort() and got the following results on my Intel Core2 Quad Q6600 2.4 GHz machine using arrays of 10 million ints:

  • Randomized input: 14.13s vs qsort()'s 6.77s
  • Sorted input: 4.41s vs qsort()'s 1.54s
  • Reversed input: 4.26s vs qsort()'s 1.90s

Clearly the above MergeSort() implementation did not fare well against glibc's qsort() on my system, so it was time to look at what I could do to improve the performance.

The most obvious optimization I could see was to try and batch my memcpy() calls. In other words, instead of calling memcpy() to copy each and every element into our temporary buffer, it'd be more efficient to copy blocks of elements at a time:

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int (* compare) (const void *, const void *))
{
    char *al, *am, *ah, *ls, *hs, *lo, *hi, *b;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    do {
        ls = lo;
        hs = hi;
        
        if (lo > al || hi > am) {
            /* our last loop already compared lo & hi and found lo <= hi */
            lo += size;
        }
        
        while (lo < am && compare (lo, hi) <= 0)
            lo += size;
 
        if (lo > ls) {
            memcpy (b, ls, lo - ls);
            b += (lo - ls);
        }
 
        if (lo < am) {
            /* our last compare tells us hi < lo */
            hi += size;
            
            while (hi < ah && compare (hi, lo) < 0)
                hi += size;
            
            memcpy (b, hs, hi - hs);
            b += (hi - hs);
        }
    } while (lo < am && hi < ah);
    
    if (lo < am)
        memcpy (b, lo, am - lo);
    else if (hi < ah)
        memcpy (b, hi, ah - hi);
    
    memcpy (al, buf, ah - al);
}

The results were promising. For the exact same inputs (including the exact same random array), we now get:

  • Randomized input: 10.45s
  • Sorted input: 2.08s
  • Reversed input: 2.03s

The only other way that we can reduce the number of memcpy() calls we make is to avoid copying leading and trailing elements into our temporary buffer if it's not necessary to merge them. Here's the solution I came up with:

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int (* compare) (const void *, const void *))
{
    char *a1, *al, *am, *ah, *ls, *hs, *lo, *hi, *b;
    size_t copied = 0;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    a1 = al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    do {
        ls = lo;
        hs = hi;
        
        if (lo > al || hi > am) {
            /* our last loop already compared lo & hi and found lo <= hi */
            lo += size;
        }
        
        while (lo < am && compare (lo, hi) <= 0)
            lo += size;
        
        if (lo < am) {
            if (copied == 0) {
                /* avoid copying the leading items */
                a1 = lo;
                ls = lo;
            }
            
            /* our last compare tells us hi < lo */
            hi += size;
            
            while (hi < ah && compare (hi, lo) < 0)
                hi += size;
            
            if (lo > ls) {
                memcpy (b, ls, lo - ls);
                copied += (lo - ls);
                b += (lo - ls);
            }
            
            memcpy (b, hs, hi - hs);
            copied += (hi - hs);
            b += (hi - hs);
        } else if (copied) {
            memcpy (b, ls, lo - ls);
            copied += (lo - ls);
            b += (lo - ls);
            
            /* copy everything we needed to re-order back into array */
            memcpy (a1, buf, copied);
            return;
        } else {
            /* everything already in order */
            return;
        }
    } while (hi < ah);
    
    if (lo < am) {
        memcpy (b, lo, am - lo);
        copied += (am - lo);
    }
    
    memcpy (a1, buf, copied);
}

Once again, reducing the amount of copying paid off:

  • Randomized input: 9.80s
  • Sorted input: 0.95s
  • Reversed input: 2.05s

Update 2011-05-18: One final optimization that can be tried is pre-calculating the optimum way to copy elements between buffers. This calculation, while not terribly expensive itself, adds up with every call to memcpy(). Let's start off by writing some handy macros:

#define COPYBY(TYPE, a, b, n) {         \
    long __n = (n) / sizeof (TYPE);     \
    register TYPE *__a = (TYPE *) (a);  \
    register TYPE *__b = (TYPE *) (b);  \
                                        \
    do {                                \
        *__a++ = *__b++;                \
    } while (--__n > 0);                \
}

#define MEMCOPY(dest, src, n) {                 \
    switch (copy_mode) {                        \
    case 1: COPYBY (long, dest, src, n); break; \
    case 2: COPYBY (int, dest, src, n); break;  \
    default: memcpy (dest, src, n);             \
    }                                           \
}

Now that these handy macros are written, we can plug them into our Merge Sort implementation:

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int copy_mode, int (* compare) (const void *, const void *))
{
    char *a1, *al, *am, *ah, *ls, *hs, *lo, *hi, *b;
    size_t copied = 0;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    a1 = al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    do {
        ls = lo;
        hs = hi;
        
        if (lo > al || hi > am) {
            /* our last loop already compared lo & hi and found lo <= hi */
            lo += size;
        }
        
        while (lo < am && compare (lo, hi) <= 0)
            lo += size;
        
        if (lo < am) {
            if (copied == 0) {
                /* avoid copying the leading items */
                a1 = lo;
                ls = lo;
            }
            
            /* our last compare tells us hi < lo */
            hi += size;
            
            while (hi < ah && compare (hi, lo) < 0)
                hi += size;
            
            if (lo > ls) {
                MEMCOPY (b, ls, lo - ls);
                copied += (lo - ls);
                b += (lo - ls);
            }
            
            MEMCOPY (b, hs, hi - hs);
            copied += (hi - hs);
            b += (hi - hs);
        } else if (copied) {
            MEMCOPY (b, ls, lo - ls);
            copied += (lo - ls);
            b += (lo - ls);
            
            /* copy everything we needed to re-order back into array */
            MEMCOPY (a1, buf, copied);
            return;
        } else {
            /* everything already in order */
            return;
        }
    } while (hi < ah);
    
    if (lo < am) {
        MEMCOPY (b, lo, am - lo);
        copied += (am - lo);
    }
    
    MEMCOPY (a1, buf, copied);
}

int
MergeSort (void *base, size_t nmemb, size_t size,
           int (* compare) (const void *, const void *))
{
    int copy_mode;
    void *tmp;
    
    if (nmemb < 2)
        return 0;
    
    if (!(tmp = malloc (nmemb * size))) {
        errno = ENOMEM;
        return -1;
    }
    
    if ((((char *) base) - ((char *) 0)) % sizeof (long) == 0 && (size % sizeof (long)) == 0)
        copy_mode = 1;
    else if ((((char *) base) - ((char *) 0)) % sizeof (int) == 0 && (size % sizeof (int)) == 0)
        copy_mode = 2;
    else
        copy_mode = 0;
    
    msort (base, tmp, 0, nmemb - 1, size, copy_mode, compare);
    
    free (tmp);
    
    return 0;
}

This handy trick seems to have worked out rather well:

  • Randomized input: 7.79s
  • Sorted input: 0.99s
  • Reversed input: 1.69s

At this point, I can't think of any other obvious optimizations so I'm going to call it a day.

For a recap, here are the results of all 4 implementations compared side-by-side with the results from qsort():

qsort()msort() v1msort() v2msort() v3msort() v4
random:6.7714.1310.459.807.79
sorted:1.544.412.080.950.99
reversed:1.904.262.032.051.69

Sunday, April 3, 2011

Low-Fat Turkey Sausage Recipe

Just made my own home-made turkey sausage and figured I'd share my recipe with my fellow hackers.

What you'll need:

  • 1.3 lbs ground turkey (I use 93/7)
  • 1 teaspoon ground black pepper
  • 1/4 teaspoon cayenne pepper
  • 1/2 teaspoon salt
  • 1/2 teaspoon ground ginger
  • 1/2 teaspoon dried sage

Mix it all up real good and make a bunch of patties and brown in a frying pan at medium heat, over the grille, or where ever and you are done.

The result is very tasty and low fat.