How would you solve this programming problem?

This was homework (well, is homework, but I’m done and while I technically still change it, I have neither the will nor the motivation to make your ideas work in MIPS right now so it’s not homework help), and since I’ve done it it’s not really GQ, so I thought I’d try IMHO. Why am I asking? Curious mostly, I also get this sinking feeling that this could have been done much better than how I resorted to and I’m trying to figure out exactly how.

The problem essentially is: given a signed 32-bit integer, print the binary value (twos complement) and calculate the parity bit (using even parity, an odd number of 1’s yields a 1, an even number a 0). there’s slightly more to the problem, but that mostly has to do with the spacing (a space after every 4 bits), but that’s trivial so don’t worry about it.

I did it in MIPS, I’m sure there’s much easier solutions in higher level languages, you can go ahead and use those easier ones assuming it’s not just printBinary(int).

My solution came down to:
Do a logical AND on the int with a mask of 0x80000000 (a 1 in the leftmost bit).

If the resulting value equals the mask, print a 1 and if the parity was 0, add 1, if it was 1, subtract 1*, else print a zero and move on.

Shift left one bit and loop until you’ve done all the bits (like a for loop until i = 31)

My original solution involved continuous division by 2 and using the remainder but it failed for a few reasons:

  1. It required going all the way to the end of the output string and altering it backwards and THEN printing, instead of just printing one by one.

  2. Since it’s twos complement, the matter of a negative number was annoying. I basically would have had to find a way to do a logical NOT on a string (not too hard) and then find a way to add 1 to it (not too difficult I suppose, but unnecessary and tedious at best), so to speak.

Anyway, I’m just rambling now, is there any better way you can think of to do this? As I said, I’m already done with it so this isn’t help, just idle curiosity.

  • I could have just used a counter and then divided by 2 and used the remainder, I suppose, but this seemed easier and allowed me to avoid the stupid division function in MIPS, which I hate, not to mention it came out to a couple less lines of code.

I think that’s pretty much the “text book” solution.

I might be misinterpreting what was asked of you, but here are my thoughts.

By “print the binary value (twos complement)”, do you mean print the number as binary, with a possible minus sign out front (when the number is negative), and with any leading zeros omitted? If not, then I’m not clear on what they’re asking of you.

To calculate the parity, you just need to XOR all the bits with each other. You could do this in a loop with 32 iterations (shift and XOR for each step), but you can also use a divide-and-conquer approach. Putting it in pseudo machine language that looks like C, I mean something like this:



a ^= (a >> 16);
a ^= (a >> 8);
a ^= (a >> 4);
a ^= (a >> 2);
a ^= (a >> 1);
a &= 1;


Hope this is helpful so far.

[Edit]oops, didnt read Bytegeist’s post. [Edit]

Is the question to convert a number to two’s complement, if so what format is it stored in already?

This is assuming the language stores integers in two’s compliment already.

int val = (some number);
int parity =0;
String result ="";
for(int i=0;i<sizeof(int);i++){
int lsb = temp & 0x1;
parity = parity ^ lsb;
result= lsb + result;
temp = temp >> 1;
}

Okay that post was worded badly, apparently, clarification below:

The problem is basically to take an integer from −2,147,483,648 to +2,147,483,647 and print out its value in the form of a twos complement binary number, preserving any leading zeroes. In MIPS the value of a signed integer is already twos complement, but feel free to use whatever way its stored in <your favourite language>, there shouldn’t be much difference (though it may affect the viability of some methods).

I mean print the (previously decimal) integer as a 32-bit twos complement binary value, no leading zeroes omitted. Meaning -1 would be represented as
1111 1111 1111 1111 1111 1111 1111 1111
not
1000 0000 0000 0000 0000 0000 0000 0001 (vanilla sign bit notation)
or
1111 1111 1111 1111 1111 1111 1111 1110 (ones complement)
or
-1 (or -10 for -2 to make that more clear)

Divide and Conquer would probably work well, and probably be faster given that the way I did it (essentially a toggle for every 1 I encounter) gets visited every one of the 32 steps, so it adds 64-92(ish) instructions (counting the branch and jumps) depending on how many bits were 1 or 0. Probably not much difference in practice, but I’ll keep that method in mind, thanks.

The line I wrote in my OP was a little confusing, it essentially reads like:


If (bit == 1){
    if(currentParity == 1){
        currentParity = 0; // Toggle parity to 0 because it is now even
    }
    else{
        currentParity = 1; // Toggle parity to 1 because it is now odd
    }
    System.out.print("1");
}


It is stored as two’s complement. Your solution isn’t quite as nice in assembly because of the hassle involved in composing strings, so you have to do it “backwards,” i.e. start with the MSB and do a left shift, but otherwise that’s pretty much what I did. Thanks.

Cool, I was afraid I managed something terribly inefficient and wanted to make sure. The 32 step loop (which was fine until I started imagining printing, say, an imaginary 1024-bit number on a magical 1024-bit architecture and thought there had to be a better algorithm for it) was the thing that made me doubt my method.

Also, you’d think “print binary” and “print hex” would be good syscall function-printy… thingies to have, but I guess I’m wrong.

XOR toggles bits.

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 0 = 0

I can’t find my copy of Hacker’s Delight (THE book for pointless bit twiddling), or I’d be able to offer more on the topic.

Here’s some non-tested, not-even-test-compiled code:



#include <limits.h>
#define INT_BIT_COUNT (sizeof(int) * CHAR_BIT) // bytes per int times bits per byte

int do_stuff(int i) { // prints binary, returns parity of lower 31 bits (0 == even, 1 == odd)
    int parity = 0;
    unsigned int bit = 0x1 << (INT_BIT_COUNT - 1);

    int bPos = 0;
    char buffer[INT_BIT_COUNT + 1]; // Plus one for null byte
    buffer[INT_BIT_COUNT] = '\0';

    bit &= i;
    bit >>= (INT_BIT_COUNT - 1);
    buffer[bPos] = '0' + bit;  // assuming ASCII, '1' will be '0' + 1;

    for (int L = (INT_BIT_COUNT - 2); L >= 0; L--, ++bPos) {
        bit = 0x1 << L;
        bit &= i;
        bit >>= L;

        parity ^= bit;
        buffer[bPos] = '0' + bit;
    }
    printf(buffer);

    return parity;
}

I don’t know MIPS, but I would expect that either the numeric is defined to a be a certain length, or there’s a way to determine how many bytes/bits are in it. The above code demonstrates how to do it in C.

I gave it a little thought and if you want to use arbitrary bit numbers to do the same thing, i found that using the least significant bit and building the string on the stack then printing from the stack pointer to be a workable solution.

I have nothing to add, but I wanted to ask: You keep saying “in MIPS” - do you mean MIPS assembly? If so, for the love of God WHY??

I realized my reading of parity was slightly off. I should have included the top bit.

To do that, just reroll the first iteration into the loop.

Here’s a version that doesn’t have special handling for the top bit. You can speed things up a bit, while still preserving the variable int size (so long as you assume that the int size will be divisible by 4, which is pretty safe since the size of a byte has been standardized).


#include <limits.h>
#define INT_BIT_COUNT (sizeof(int) * CHAR_BIT) // bytes per int times bits per byte
#define LOOP_COUNT (INT_BIT_COUNT / 4)

int do_stuff(int i) { // prints binary, returns parity
    char* print_data[16] = { // The printout of a nibble
        "0000", "0001", "0010", "0011",
        "0100", "0101", "0110", "0111",
        "1000", "1001", "1010", "1011",
        "1100", "1101", "1110", "1111"
    };
    unsigned int parity_data[16] = { // conglomerate parity of a nibble
        0, 1, 1, 0,
        1, 0, 0, 1,
        1, 0, 0, 1
        0, 1, 1, 0
    };

    int parity = 0;
    char buffer[INT_BIT_COUNT + 1]; // Plus one for null byte
    buffer[INT_BIT_COUNT] = '\0';

    unsigned int mask = 0xf << (INT_BIT_COUNT - 4);
    for (int L = 0; L < LOOP_COUNT; L++) {
        unsigned int l_mask = mask;
        l_mask &= i;
        l_mask >>= INT_BIT_COUNT - (4 * (L + 1));

        parity ^= parity_data[l_mask];
        memcpy(buffer, print_data[l_mask], 4);
        
        mask >>= 4;
    }
    printf(buffer);
    
    return parity;
}

Assuming you were doing this in assembler, you’re final answer is probably the best. Logical operations like you used are far better than the arithmetic ones that people centered around HLLs are used to.

Because it is nice that at least some people who claim they are computer scientists know what is going on at the machine language level. Though as someone who did his graduate work in microprogramming, assembly language is an HLL as far as I’m concerned.

If I handed out a reasonably straightforward assignment & a student turned in something written in an obscure assembly with a “sinking feeling that this could have been done much better” I wouldn’t be inclined to give out high marks. But I guess when you consider assembly a high level language such mundane concepts as “getting it to work” aren’t as important. I guess I’m just not worthy, or something. :rolleyes:

I can only assume that Jragon is taking a course in assembly.

No, just too young. MIPS is an early RISC machine, which was a company for a while. The tools for it are widely available, so when Jragon said MIPS lots of us figured he was working in assembler. Plus, the assignment is one which is reasonable in an assembly language class.

Getting it to work is just as important in assembler, and structured programming is even more important, since you can get more confused. In the PDP-11 assembler class I TAed for, the first assignment was a simple word processor which they wrote in Pascal. (This was about the time C was being created.) We graded the hell out of it, (and later dropped the score) since if they wrote spaghetti Pascal their assembler was going to be a real mess. It worked pretty well.

Though I doubt very much anyone would turn in an assembly language program in an HLL course, if someone did he’d be wanted to help write diags at Intel, AMD and Sun.

To understand what I mean about assembler being a high level language, look up microprogramming some day.

Huh? Why would anyone in their right mind turn in assembly language in a course that allows higher level languages (barring discrete chunks to do secret forbidden magic on the rare occasion), between lack of portability and the hair pulling madness that can result from some of the debugging? Actually, this was the easiest program for me so far, the one before that where we had to write a parse int function was significantly more annoying, if for no reason other than the fact that negatives allow one larger than positives so the overflow detection check was a bitch.

The course is Computer Architecture and Organization, it’s mostly how the CPU operates (ALUs, clock cycles, data hazards and the like), along with a little bit near the tail end about RAM and hard drives and other non-CPU memory. The MIPS is more of a tool to help us understand how the stuff works, as well as a reference point for explaining stuff (it gets difficult to understand pipelining without instructions to diagram with). MIPS was chosen because of the easy availability of MIPS simulators (SPIM, specifically) and because as far as assembly languages go, it’s pretty friendly (from what I’ve heard, IBM Power PC assembler is positively Lovecraftian in comparison).

The reason I had a sinking feeling it could have been done better is because I haven’t taken my Algorithms course yet so I tend to get scared that I’m doing something wrong if it’s O(n) or worse, since I haven’t really learned how to be able to tell when that’s acceptable or the best you can do yet. They don’t really grade the lower level courses on efficiency (well, I think the course I’m taking in fall might, not sure), but I hear so many stories about inefficient code and the well-meaning yokels who “should be fired and never, ever program again” that wrote them I tend to freak out when something looks even the tiniest bit longer than it should be.

Are you using Hennessey and Patterson for a text? Hennessey was an inventor of the MIPS architecture, so its not surprising you use it. Its one of the simplest - and most easily available - architectures out there now, so its a good choice.

Now that optimizing compilers are smarter than we are, most assembly code you will have to write (if any) will be pretty simple. Not that you can’t do complex assembly code - when I was teaching I once wound up writing a recursive assembly language program from scratch on the board. Nothing fancy, just a factorial program, but fun.

Generally, slow code is long, fast code is longer, day-to-day code is short. The first happens because the person doesn’t know what they’re doing and fumbles about. The second happens, generally, because you’re unrolling loops and setting up caches, and making code that acts more intelligently.

But in the end, code length is unrelated to code speed.

More importantly, code speed is generally unrelated to algorithm. Most of what slows you down is system calls. Knowing what all sorts of algorithms/data structures exist is certainly a good thing, but focus on writing “simple” code and worry about making it cool later.

Included below is a tutorial on optimization:


Running a profiler, of course, doesn’t hurt but there are some problems as well:

  1. Profilers often don’t display time that is spent in library/system code.
  2. Once you know where the slow spot is, that still might not tell you why it is slow if you don’t understand what is happening at a lower level.
  3. Not all languages/environments have an available profiler.
  4. Oftentimes, optimal solutions require fairly high level changes. Optimizing the slowest portion of code will certainly speed your program up, but an entirely different approach to everything could, even un-optimized, possibly give even greater speed increases.

At the end of the day, having an understanding of the beast inside the box is the best optimization tool. Of course, remember the two principal rules of optimization:

  1. Don’t pre-preemptively optimize everything. Write clear, readable code and only when the end result doesn’t perform in a reasonable amount of time, go in and optimize. (Of course, when you understand the machine you’ll likely end up writing clear, readable code that naturally runs quite well.)
  2. 20% of the code will be 80% of what is being run. Optimizing anyplace else will have negligible results and simply eat your coding time.

The Chef, The Manager, and the Pantry

Deep within your computer, there is a single room,[sup]1[/sup] a kitchen. The kitchen has a workbench in the middle and a door on either side. The door in the front goes out to the restaurant (the rest of the computer) and the door in the back goes into the pantry (RAM).

There is a large timer in the kitchen that counts down from 10 microseconds, and when it reaches zero, the chef takes all of his things, goes into the pantry, and falls asleep. As soon as he closes the door though, it reopens to reveal an entirely different chef standing in an entirely different pantry. And this chef comes out, bringing his things with him, to work until the timer counts down to zero again.

To each of the chefs there appears to be only one pantry and it only contains their things. And none of them can go through the front door to the restaurant. Only the Manager has the key to the front door.

Eeach of the chefs has the same basic skills, and frankly this isn’t much. He can add, subtract, multiply, divide, shift bits, AND, OR, XOR, negate, compare two values, move to a different place in his list of instructions, save the result to the pantry, and grab more data from the pantry. Really there isn’t anything else that he can do, so don’t be fooled! And note that he can only work on a maximum of 32 (or 64) bits at a time.[sup]2[/sup] Again, don’t be fooled! A string is not an int regardless of what Python, PHP, or VBScript seems to represent it as to you.

Another thing to remember is that the chef is fat. His fingers are quite dexterous and nimble for most of his mathematical tasks, except for multiplication at which he is a tad slower, and at division for which he is significantly slower. That being said, he still quite fast with numbers. The problem is that since he is a bit overweight, any time he has to go to the pantry, it is not at a brisk run. More a waddle.

Intel is aware of the propensity for chefs to be overweight, so they have given him a shelf to put a good many of his recipe instructions on, and several more shelves to hold all the numbers he is currently working on, all nicely just over his workspace so that he does not have to go back to the pantry so often.

But of course, every time the timer counts down to zero, he has to take his personal stash back to the pantry and place them where they are meant to be, and then one-by-one take them all back out when has been awoken again.

The pantry, now, is a rather interesting place. Most specifically its layout.

Starting at the very bottom on the first shelf, there is the recipe. All of the steps that he needs to follow are nicely laid out for him. But the chef only takes a few hundred or so at a time, setting them up over his workspace, since it is rare that he will need to go that far in a recipe without having to skip to an entirely different section. But every single page of the recipe is locked into a glass case. He can read it just fine, but he cannot modify it.

Moving up the pantry, just past the recipe pages, are various bits and bytes and whatnot, also all locked up in glass cases. The chef can take these to look at, but he cannot modify them because of the glass casing. For instance, when he has an instruction like:

(EXAMPLE A)
String s = “Hello world!”;

The “Hello world!” string will be stored in one of these glass cases. So that you can modify it, the chef must copy the letters into somewhere else first. In the above command, he does just that.

Now, moving further up in the pantry, is a section for items which are not in glass boxes. These are items which are already known to exist before the recipe begins and that will exist until the recipe ends. For instance:


public void do_something() {
   static int i = 10;
   ...
}

Your variable “i”, being a static value, will exist for the duration of everything. So it’s not worthwhile to create a temporary i and copy 10 into it each time. Thus it will be set up in this area of the pantry. Global variables would be here as well.

Now the whooooole middle of the pantry is open space. We might put stuff in there later, but for the moment we’re going to shift our attention to the very end of the top shelf.

…But let’s take a slight detour before we get to that.

Now the sort of work the chef does generally boils down to taking a bunch of ingredients, working a bit of magic, and returning out a single, completed, dish. This dish might then be a component in an even bigger dish, all of which at some point ends up as the total full course meal for all the patrons, but the point is that in general he:

a) Works on small bits of the whole at a time and progressively combines those into the larger whole.
b) For any stage of work, we’re going to have a bunch of ingredients that get processed and merged down into a single item, making all the scraps and waste product immediately trashable.

So realising that this is a decent way to work on stuff, the chef keeps things arranged in a particular way starting from the very end of the top shelf, which we will call the Stack.

Say that I have this function:


int do_something() {
   int i = 10;
   int j = 42;

   return i * j;
}

Well. the chef is only going to need to keep i and j around for a little bit and then he can trash them. So what he does is:

  1. Puts a bookmark like thing at the top of the stack that will stick out noticeably.
  2. Creates i and j just after it.
  3. Determines the result.
  4. Puts the result in a bowl on his workbench, and then throws away everything on the stack after the last bookmark.

To show how this is handy, we’ll look at a version like this:

(EXAMPLE B)


void main() {
   int a;
   int b = 2;

   a = do_something()
   b += a;
}

int do_something() {
   int i = 10;
   int j = 42;

   return i * j;
}

To watch what the chef does:

  1. Places a bookmark.
  2. Creates 2 ints worth of room after the bookmark.
  3. Sets the value of the second-after-the-bookmark to 2.
  4. Places a bookmark.
  5. Creates 2 ints worth of room after the bookmark.
  6. Sets the value of the first-after-the-bookmark to 10.
  7. Sets the value of the second-after-the-bookmark to 42.
  8. Brings the first and second to his workbench.
  9. Multiplies them.
  10. Puts the result in the result bowl.
  11. Throws away everything after the last bookmark.
  12. Takes the contents of the result bowl and sets into into the first-after-the-bookmark slot.
  13. Takes the first and second items to his workbench.
  14. Adds them.
  15. Sets the second-item-after-the-bookmark to the result.
  16. Tosses everything after the last bookmark.

Now the important thing here is that his recipes can simply refer to local variables as per their distance from the bookmark, and that’s what the page on main() will do, and that’s what the page on do_something() will do.

But the Stack is, obviously, intended for things which have a short lifespan. And since the whole point of a recipe is to build large items via the processing and merging of many many little items, there’s a general correlation between size and lifespan. This is so true that in general compilers simply assume that anything larger than 32 (or 64) bits is likely to have a long lifespan, and so it will not put it on the stack.

And in fact, there is a maximum size that the stack can become, which assumes and necessitates that the above is so.

So if we go back and look at EXAMPLE A, our string is definitely longer than 32 bits. Point in fact, any string will be assumed to be longer and so will not be placed on the stack (by Java.) But of course we need to keep it in the pantry somewhere!

This is where that big empty section in the middle of the pantry comes in. This area is called the Heap.

The Heap does not have a clear method of creating and trashing data. With the stack you just add and remove from the end. But in the heap, something created in the first step of the whole meal might be the first thing trashed, and it might be the last. So the chef has a recipe book for managing the Heap. It is similar to the process of creating and deleting files from a hard drive. Managing it is, in essence, a program itself.

But now think back a little bit. The recipe was written before the chef began to work and the pages are held in glass cases. If page tells him that something is two off from the top stack bookmark, he knows where that is. And if tells him that an item is the 23rd in the read-only section of pre-initialised data, he knows where that is as well. But when the recipe was written, there was no way to know how large the pantry is, nor to know what program this chef happens to use to manage his heap, so there’s no way for the recipe to tell him where anything on the heap is or should go. And since the recipe pages are unchangeable, he can’t write it down there.

So instead what he does, is he has “pointers”. We can think of these as little tokens 32 (or 64) bits in size, with a long tether coming off them. Any time he creates something on the heap, he adds a token to either the stack, the static data area, or his results bowl and ties the other end of the tether to the thing in the heap. He can thus pass the token about without having to be moving large quantities of data all the time, and not overflow the stack size limit.

Right, so that’s the basic layout of the kitchen.

[sup]1[/sup] With multiple core processors, one can now view it as that there are multiple kitchens, though in general, unless a program is multi-threaded it will be fully run on a single core so far as I understand it. Different programs running at the same time will be run on separate cores though.

[sup]2[/sup] Ignoring the floating point or MMX processors or such, since this warning is mostly concerning operations on strings.


The Chef and Branches

As I said way back, one of the very few things the chef can do is jump to some other page or line in his recipe book. This is called “branching”, due to it most often occurring when there is a multiple choice involved.

As noted before, the Chef generally grabs a few hundred instructions from the pantry at a time. When he runs out, El Fatso waddles on back and grabs a hundred more.

But whenever he branches, being sort of stupid, he assumes that the place he is jumping to in the recipe will not be in his personal cache, he always goes back to grab more. Waddle waddle.

This is not awful but, when you really need to put the petal to the medal, doing some odd math rather than setting up a nice if-else -f-else chain might very well speed Tubby up.

Branches:
Trinary operator ? :
If-else if-else
Function calls
Loops


The Chef and Functions

As already mentioned, whenever a function is started, a bookmark is placed, some amount of space created at the end, and variables with values initialized. For each of these steps, the Chef waddles to the pantry, does it, comes back to his workbench, and then goes back all over again. He is really only any good at keeping one task in his head at a time.

Functions which have parameters also have those parameters pushed onto the stack before the function is called. In general, this is done individually. Which, most likely, means that you are going to see the chef waddling back and forth for each time.

To exhaustively go over the process of entering and exiting a function:

  1. (Bookmark) Place a pointer token to the old bookmark.
  2. (Bookmark) Place a pointer to the instruction following the function call in the old function.
  3. (Parameters) Individually place parameters to the new function on the stack. (If the function is declared in an object, there is a hidden parameter which is a pointer to the object’s data in the heap.)
  4. (Recipe Cache) Fetch the instructions for the function recipe
  5. (Local Variables) Create space for local variables on the stack
  6. (Local Variables) Individually initialise each variable
  7. Function contents →
  8. (Result) Optionally place result in the result bowl
  9. (Reset Bookmark) Reset to the old bookmark (current function’s data remains as it is, to be overwritten by the next function to use that space.)
  10. (Recipe Cache) Send the chef to grab the page for the old function starting just past where it called us.

Overall not a horrendously laborious process, by the chef’s standards, but still quite a rather involved process. Definitely worse than a simple branching.


The Chef, The Manager, and System Calls

If you recall back, the chef has a ten microsecond work window and then he has to trade with someone else’s chef. Now there’s not anything you can do about this in general. But there is a case where this all becomes relevant.

You see, of course, you want to use as much of your 10 microseconds as you can. If you give it up early, you’re already out thousands of instructions you could have done.

A System Call is what happens when the chef needs something from management. This means anything he does that involves anything beyond his own pantry (application space.) Keyboard, mouse, monitor, hard drive, printer, or even other chefs’ pantries! The chef is persona non grata in all of those areas, so far as Management is concerned.

When the chef wants to do something with any of these, he has to ask the Manager to do it for him. So what he does is:

  1. Allocates memory for the result of the operation on the heap.
  2. Picks up all of his things and moves them to the stack. (For instance, all of the fancy stuff he does with the stack might never actually reach the pantry since he can virtually do it on his personal shelves and just move stuff there in case the timer goes.)
  3. Writes a note saying what he wants, with a token pointing to the memory he left open in the heap.
  4. Turns on a klaxon alarm.
  5. Goes into the pantry, closes the door, and goes to sleep.
  6. The manager comes out of the pantry door (his pantry includes everyone elses), turns off the klaxon, and looks at the note.
  7. The manager goes in and grabs stuff from someone else’s pantry or goes out through the front door and accesses the printer or wherever.
  8. The manager follows back the heap token and writes the result.
  9. The manager goes back into his own pantry, closes the door, and goes to sleep.
  10. Some entirely different chef comes out and does 10 microseconds of work.
  11. Yet some entirely different chef comes out and works.
  12. etc.
  13. Our chef wakes up, opens his door, and starts returning his data and instructions to his work area, and goes back to work from right after where he left off.

Note that all of this also includes the basics of a normal function call as well. Plus, more importantly, is that if you think the Chef waddles…he doesn’t have anything on the hard drive or the printer, or pretty much any other operation except shared memory. These will all be sloooow. Sloooooooooooow.


Hidden Whoopsies

A thing to recall is my warning back at the beginning. The Chef only has a few limited abilities and anything else it may look like he is doing is most likely a function call under the hood.

If, in some language or another, you see code like this:


switch (s) {
case "Arugula":
   ...
break;
case "Wombat"
   ...
break;
}

Well, remember, the Chef can’t do string compares. He can only compare values up to 32 (or 64) bits and most likely is processing each byte of the strings individually. This means that you have a loop, which means an instruction cache refresh (waddle waddle), besides the loop itself. And since it’s unlikely that the compiler/interpreter would copy the body of a full string compare loop around multiple times, it’s almost definitely going to be inside a function behind the scenes. So now we have a loop, a buffer refresh, and a function call. Waddle waddle waddle waddle.

While as if you use integer constants, like so:


final static int ARUGULA = 0;
final static int WOMBAT = 1;

switch (i) {
case ARUGULA:
   ...
break;
case WOMBAT:
   ...
break;
}

The speed difference is going to be immense. (Plus a typo will turn into a compile time error rather than a runtime error.)

Another hidden whoopsie I recently saw was related:


print "#" * 42  -- repeats a character 42 times

Similar to the above, while it may look like this is a single line of code and so a single instruction for the Chef, internally it will be a function call, loop, and likely a heap allocation or 6.

Remember what the chef can and can’t do and how he would really have to be going about doing your one line of code!


Rankings of Badness

How bad (I think) the various things discussed are.

Don’t want in the deepest loop at all cost
#1 System calls - Slooooooooow!
#2 rand() - Wasn’t discussed, but many people are taken in and think that a pseudo-random number generator would be speedy and end up putting them in critical portions of code.[sup]1[/sup]

Try to minimize where possible
#3 Function calls
#4 Division
#5 Branches
#6 Multiplication

What you want
#7 Everything else

[sup]1[/sup] What I will often do is to cache the result of a random number and peel off as many bits as I need. Usually you only need a number between 0 and 99, for instance. That’s manageable in just seven bits. So if you divide your 32-bit result from rand() by 7, you can get 4 valid numbers from one call (just keep skipping bits left until the lower 7 are between 0 and 99, then skip seven and start again.)

After reading that last post from Sage Rat (which I mostly agree with), here’s some more advice:

When it comes to general advice about coding, the reasoning behind the advice is far more important than the advice itself. Some tricky programmer may have created something that invalidates advice in specific cases. See “Hidden Whoopsies” from the previous post. This example of string comparison is true for certain languages but not for others (think string internalization) and doesn’t address how you go from string s to int i to do the comparisons. Also these models of architecture are invalidated by pipelining and branch prediction. When the chef sees a decision-branch in the recipe he picks one path and starts it going if it turns out to be wrong he forgets what he was doing on that path and starts over going the other way (sort-of, its hard to imagine this chef pipelining anything).

From your previous post you mention “I tend to get scared that I’m doing something wrong if it’s O(n) or worse”.

  1. Remember that big-O notation is useful for selecting an algorithm to use when the worst case actually matters; it’s not really important when the worst case can only occur .000001% of the time.
    2.It’s based on number of specific operations and not some actual time measurement.
  2. 1,000,000n > n^2 when n < 1,000,000, although they would read as O(n) and O(n^2).