Andrew Que Sites list Photos
Projects Contact
Main
   The drive back to Cedar Rapids with LJ.  LJ is coming to scope out the area and see about finding some work.  Rock County has a high unemployment rate due to the closing of GM.  So, he is going to try his hand in my new stomping ground.  It'll be nice to not be completely alone here :)

August 15, 2009

Happy Birthday Xiphos

The Culvert Spelunkers

The Culvert Spelunkers

   Xiphos (or in modern day, Xix), celebrated his birthday today.  A group of us met up at Palmer Park for a cook out.  Pluvius, Steve, Xiphos and I decided, for old times sake, to seek out a culvert we use to explore that was right next to the park.  We use to be somewhat of culvert spelunkers back in the day.  So a group of us decided to have a look again, and here we (well, most of us) are.

1 comment has been made.

From Steve

JanesHell, WI

August 21, 2009 at 4:29 PM

Ahh, yes. Our spelunking trip definately brought back memories of olden times. I still remember the first time we set foot in that culvert. It was fun rampaging through there again, even though slogging through there further illustrated just how out of shape I am. Hell, even Tyson and Drew were roughing it too. LOL!

August 13, 2009

Search engine

My power pig

My power pig

   I noticed some traffic to my site from a search engine called Cuil.  In their blurb about themselves, they boast how Google and Microsoft haven't kept up with the times and how they search "more pages on the Web than anyone else."  In addition, they have this blurb:
   "Rather than rely on superficial popularity metrics, Cuil searches for and ranks pages based on their content and relevance. When we find a page with your keywords, we stay on that page and analyze the rest of its content, its concepts, their inter-relationships and the page’s coherency."
   Cool... let's see how well it works.  Search "Andrew Que".  First hit, my fractal website (called "Andrew Que's Fractals") which hasn't been updated since 2002.  Second hit, something in Spanish with Andrew and "que" existing but not together.  Hit 3, a post I made on the Cygwin forms in 2004.  Hit 5, a hit on imdb for some Spanish movie.  Hit 6, Cygwin forms again.  Hit 7, 8 and 9, facebook hits in Spanish for someone with the first name Andrew.  And last, something about canoe races in Canada in 2002.
   Well, they sure don't rely on "superficial popularity metrics."  They also don't list DrQue.net in the first 10 pages (after which time, I gave up looking).  Both Yahoo and Google list DrQue.net first.  This seems natural to me since those search engines aren't completely oblivious.  Even Bing (microsoft) puts DrQue.net on the first page.  Ask.com has DrQue.net as the first finding--and their search engine hasn't not sucked since it was Ask Jeeves back in early 2000.
   Strange, because the search engine Cuil is suppose to be made up of mostly ex-Google people.  Well, maybe now we know why they don't work for Google anymore.

1 comment has been made.

From Simeon Becker (thingywummit.blogspot.com)

IL

August 23, 2009 at 12:04 AM

I checked out Cuil after reading what you wrote here; it\'s pretty much as stupid as you described. What baffles me is how someone who worked for Google for YEARS would suddenly decide that their essential rip-off of Google\'s interface with pissy-ass workability would \"search more pages on the Web than anyone else.\" Anyone else being people who don\'t own computers or have been in a coma for the past fucking century. Assholes. Why do we need more search engines? They all suck besides Google anyway. Can that fruity dicklick Jeeves butler me up an email address? No? He\'s fired. Tell him I\'m not paying for him to dry-clean that penguin suit again this week.

This happened to me yesterday at work, and the reasons had me a bit stumped. The project I'm working on had a bug and the comments said it was (temporally) solved when they removed the optimization flag. We use the GNU C compiler, and optimization level 2 (-O2). This level of optimization is suppose to be fairly safe. So I was curious why this had any effect. After some research, I came across the following scenario.

#define VALUE_A   ( 50 )
#define VALUE_B   ( VALUE_A / 100 )
#define VALUE_C   ( 150 )
#define VALUE_D   ( 133 )

void Delay( int Value );

void FunctionA( int Value )
{
   int Remainder;

   Value *= VALUE_B * VALUE_C;

   Remainder = Value % VALUE_D;

   Value /= VALUE_D;

   /* Round result. */
   if ( Remainder >= ( VALUE_D / 2 ) )
     Value += 1;

   if ( Value > 0 )
     Delay( Value );
}

First of all, this isn't the most efficient way to do rounding, but the problem isn't with the rounding. If you're clever, you've already seen that VALUE_B is a non-integer number below 1. However, VALUE_B is being multiplied up by 150 (VALUE_C), so it will end up greater then zero.

This function happened to be part of a high-resolution delay function, which is why it was so tricky to catch—tricky because it had worked until optimization. To figure out what happened, we have to go to the assembly level.

First, the assembly output if no optimization is used.

_FunctionA:
pushl %ebp
movl %esp, %ebp
subl $8%esp
movl $08(%ebp)
movl 8(%ebp)%ecx
movl $-161464935%eax
imull %ecx
leal (%ecx,%edx)%eax
movl %eax, %edx
sarl $7%edx
movl %ecx, %eax
sarl $31%eax
subl %eax, %edx
movl %edx, %eax
sall $5%eax
addl %edx, %eax
sall $2%eax
addl %edx, %eax
subl %eax, %ecx
movl %ecx, %eax
movl %eax, -4(%ebp)
movl 8(%ebp)%ecx
movl $-161464935%eax
imull %ecx
leal (%edx,%ecx)%eax
movl %eax, %edx
sarl $7%edx
movl %ecx, %eax
sarl $31%eax
subl %eax, %edx
movl %edx, %eax
movl %eax, 8(%ebp)
cmpl $65-4(%ebp)
jle L2
incl 8(%ebp)
L2:
cmpl $08(%ebp)
jle L1
movl 8(%ebp)%eax
movl %eax, (%esp)
call _Delay
L1:
leave
ret

Our project doesn't use an x86 CPU, but nonetheless, I read Intel assembly just fine, and I can tell you this looks to be what I expect from this function. There is some math in the first 2/3rds, two jumps for the "if" statements and a call to "Delay". The problem is here, and quite early on, but it doesn't stand out. And it didn't stand out in the other assembly language output as well.

Now, the same function compiled with optimization set to level 2.

_FunctionA:
pushl %ebp
movl %esp, %ebp
popl %ebp
ret

You don't need to know assembly to know something is wrong here. In fact, all that happens is the stack is setup, then cleaned up, and we return. This is a completely empty function. On our platform, the assembly was even shorter—just a return statement.

A clever reader would know the problem early on—it's the non-integer number. But what happened? How did optimization "break" this code? The answer is that the code is broken in both assembly versions. In the non-optimized version, "Delay" is never called. It's never called because "ticks" will always be zero, and it will be zero because of the first math operation. VALUE_B is zero, because it is a number below 1. All non-integer numbers resulting from a divide are truncated, or rounded down. Doesn't matter that it was then multiplied by VALUE_C, which would have brought the value above zero—the arithmetic was done using integers. A more careful read of the non-optimized assembly reveals the problem early on.

movl $08(%ebp)
movl 8(%ebp)%ecx
movl $-161464935%eax
imull %ecx

Register "ecx" is being set to zero (first two instructions). "eax" (the accumulator register) is being set to some seemingly strange number. Then the two are multiplied together. The result: 0 of course!

Since the result is 0 and always zero, the rest of the logic always happens the same way, no matter what input is given to the function. The compiler knows this, and when optimization is turned on, it gets rid of all that dead code and leaves one with an empty function.

Here's where things get tricky and rather project specific. This function was part of a high-speed timer, and had to calculate the number of wait cycles before calling an assembly delay function. The amount of delay time we were requesting was in the hundreds of nanoseconds on a system where instructions execute in a few nanoseconds. It doesn't take many instructions to achieve the desired delay. The non-optimized function is just as broken as the optimized function. In both cases, "Delay" is never called. However, there happened to be enough instructions in the non-optimized function to achieve the desired delay time. No one had ever noticed that requesting different amounts of time from this function always resulted in the same amount of time delayed—there are not a lot of places one needs a delay like this. Thus it was thought that optimization broke the function.

I didn't question the function too much at first. It had worked. I was looking for why it stopped working, not for what was wrong with the implementation. Right away, I saw the math that was sure to end up having a non-integer value. However, I assumed the last multiple must have pushed the value up, and thus why it could have worked. Before getting out the o-scope, I did do some calculations to see if the problem was a rounding error (the numbers in our implementation were obviously different), but didn't find anything significant enough to cause our problem. I went ahead and fixed the math so the rounding error wouldn't happen, went home, and forgot I had done made the change. The next day I went to produce the error and watch it on the scope, and didn't see a problem. I was running my corrected version, which did multiplication before division—thus no decimal numbers and (the reason I corrected it) no rounding errors due to truncation. After figuring out I had changed the function and restoring the original, I quickly found the empty function in the assembly output. But it wasn't until today I put it all together as to why. Once I considered that the function had always been broken, it just took a simple "printf" statement to prove it.

#define VALUE_A   ( 50 )
#define VALUE_B   ( VALUE_A / 100 )
#define VALUE_C   ( 150 )
#define VALUE_D   ( 133 )

void Delay( int Value );

void FunctionA( int Value )
{
   int Remainder;

   Value *= VALUE_B * VALUE_C;

   Remainder = Value % VALUE_D;

   Value /= VALUE_D;

   /* Round result. */
   if ( Remainder >= ( VALUE_D / 2 ) )
     Value += 1;

   printf( "Value: %i\n", Value );

   if ( Value > 0 )
     Delay( Value );
}
The result, optimized or not, always: "Value: 0".

The lesson here: Always remember to think in integer math unless you specifically tell the compiler otherwise. There are a few things that could have made this function work.

#define VALUE_B   ( (float)VALUE_A / 100 )

#define VALUE_B   ( VALUE_A / 100.0 )

Both of these cause the value to be evaluated as a floating-point type. However, unless you cast "VALUE_B * VALUE_C" as an integer, you will end up with floating-point math in the assembly, optimization or not.

The method I think is most correct is to arrange the math so multiplications happen first.

#define VALUE_A   ( 50 )
#define VALUE_B   ( 100 )
#define VALUE_C   ( 150 )
#define VALUE_D   ( 133 )

void Delay( int Value );

void FunctionA( int Value )
{
   int Remainder;

   Value *= ( VALUE_A * VALUE_C ) / VALUE_B;

   Remainder = Value % VALUE_D;

   Value /= VALUE_D;

   /* Round result. */
   if ( Remainder >= ( VALUE_D / 2 ) )
     Value += 1;

   if ( Value > 0 )
     Delay( Value );
}

And while I'm at it, let's clean up that rounding code.

#define VALUE_A   ( 50 )
#define VALUE_B   ( 100 )
#define VALUE_C   ( 150 )
#define VALUE_D   ( 133 )
#define VALUE_CD  ( VALUE_C * VALUE_D )

void Delay( int Value );

void FunctionA( int Value )
{
   Value *= ( VALUE_A * VALUE_C );
   Value += VALUE_CD / 2;
   Value /= VALUE_CD;

   if ( Value > 0 )
     Delay( Value );
}

Although I spent the last two days working this problem out, most of my time was spent coding a better total alternative—not searching specifically for this problem. But this is a good example of what we embedded programmers do for a living!

On a positive note, I got to spend some time using my favorite oscilloscope. There is just something that feels good when you're sitting in front of a $20,000+ oscilloscope grab'n at numbers in the nanoseconds range. It's gota be a geek thing!

   The Blue Dragon, my primary computer for the past year, despite being designed to consume less power then the Red Dragon, is nevertheless a power pig.  To sit here and listen to music pulls 480 watts.  With the twin monitors off , the system sits at 315 watts.  And in "sleep," the beast still draws 200 watts.  Heck, with the power off, the setup still draws 20 watts--as much as my web server peaking out! 
   Pictured is me, my hair looking ridiculous and me loving it.

2 comments have been made.

From Steve

Janes-Hell, WI

August 12, 2009 at 11:50 PM

I kind of figured that despite your best efforts, the Blue Dragon was still gonna suck up quite a bit of juice. After all you\'ve got the thing crammed with tons of hardware (for example, your many hard drives for your RAID array). Hell, your Logitech speaker system alone draws almost enough power by itself to power a couple of computers, and it\'s not even powered by your system. I almost wonder what kind of energy usage my next system will go through. Probably a great deal, as I want it set up as a gaming system. On the other hand, my current system, despite my having it geared for gaming did fairly well with only a stock Dell 250-watt PSU. Guess I\'ll find out whenever I get my new system built and up and running. :)

From Steve

Janes-Hell, WI

August 12, 2009 at 11:52 PM

Oh, and BTW, for some reason whenever I post comments, backslashes appear in the text right next to wherever I use apostrophes.