float cast underflow slow

Today I noticed that some of code that just blended some images was being really slow dependent on some of the coefficients used in the blending. After checking the coefficients for strange values (nans/infs), for which there were none, it was still slow. The problem was only appearing in one function used for blending (some integer code that used floating coefficients that were casted from doubles). The problem didn't appear when strictly using floating point arithmetic. Turns out it is due to slow casting from double to float when there is underflow.

Some timing results for casting from double to double (d), double to float (f), double to integer (i), for test program, included below:

Without optimization
time for d (init=1e-30) 0.013476
time for f (init=1e-30) 0.012164
time for i (init=1e-30) 0.016217
time for d (init=1e-50) 0.019088
time for f (init=1e-50) 0.229608
time for i (init=1e-50) 0.019010

Without optimization (-O3)
time for d (init=1e-30) 0.005358
time for f (init=1e-30) 0.004038
time for i (init=1e-30) 0.003713
time for d (init=1e-50) 0.004566
time for f (init=1e-50) 0.135538
time for i (init=1e-50) 0.003527

You can see the floating point cast is something like 30x slower for the value of 1e-50 (where there is underflow) as opposed to the case of 1e-30 where there is no underflow.

Try the code for yourself.

#!/bin/sh

cat <<EOF > _f_.cc
#include 
#include 
#include 
#include 
#include 

template 
void test(int m, double init){
  double * v = new double[m];
  T * f = new T[m];
  struct timeval tv;
  gettimeofday(&tv, 0);

  for(int its=0; its< 20; its++){
    v[0] = init;
    double * vptr = v;
    for(int i=0; i< m; i++){
      *(vptr++) = v[0];
      f[i] = ((T)v[i]);
    }
  }
  struct timeval tva, el;
  gettimeofday(&tva, 0);
  timersub(&tva, &tv, &el);
  printf("time for %s (init=%g) %lf\n", typeid(T).name(), init, double(el.tv_sec) + double(el.tv_usec)/1e6);
  delete [] f;
  delete [] v;
}

int main(int ac, char * av[]){
  int m = 100000;

  test(m, 1e-30);
  test(m, 1e-30);
  test(m, 1e-30);
  
  test(m, 1e-50);
  test(m, 1e-50);
  test(m, 1e-50);
  return 0;
}
EOF

echo "Without optimization"
g++ _f_.cc -lm -o _f_
./_f_

echo "Without optimization (-O)"
g++ _f_.cc -lm -o _f_ -O
./_f_

echo "Without optimization (-O3)"
g++ _f_.cc -lm -o _f_ -O3
./_f_

echo "Without optimization (-O3)"
g++ _f_.cc -lm -o _f_ -O3 -mmmx -msse
./_f_

rm _f_.cc _f_

backtrace and friends

Just some notes on instrumenting code using gcc.

Add hooks before and after function calls with "-finstrument-functions" (__cyg_profile_func_exit, ...).

Several ways to look up symbols:

backtrace, backtrace_symbols

libbfd (library used by nm)

create your own symbol table (have macro to map function pointer to name).


On mac, atos is useful.

More to come.

WTF apple!

Just spent a long time (as in several hours) stumbling on things that shouldn't have even been problems.

1) Multi-touch on the iPhone. The freaking canvas has to have a property set to enable multi-touch. You still get multi-touch if you don't enable it, but the data is random--which makes you think that the scale and translation you are applying to your canvas is wrong. I see no good reason for having the option of turning off multi-touch events, so whoever decided that I want my wasted hour back.

2) OpenGL errors on the iPhone. Put in some glGetErrors to trace down the few errors I was having. Oddly enough they seemed to be right around the calls that used GL_CLIP_PLANE1 (not GL_CLIP_PLANE0, just clip plane 1). Sure, that didn't seem to be a problem before, but what'evs--I can deal with it. Still some other textures that looked wrong. Turns out I inadvertently created some non-power-of-two textures (which work fine in new versions of OpenGL now-a-days). As soon as I realized this I decided to double check the clip plane problem. Sure enough, no longer a problem. Why in the hell was an error being reported on the CLIP_PLANE1 and not somewhere closer to the texture. Damn, damn, double damn.

And again

I found live ammunition on a bridge late last night. Made my day.

Still not much more luck with the lines. This rasterizes the current line, computes the signed distance from the line, extracts the level set at a specific distance, and then tries to connect the resulting polygons to the existing line. That's why the line appears to follow itself.

Slow. Downsampled they almost look like the embedded code images.

Line update

Some more lines. I have tried several different methods, and still nothing is giving me what I expect.

The code (which is a mess) because I wrote it at 3 in the morning is also embedded in the other not-so nice image (as usual).

Static is good, and static is great, but static initialization order sucks. I have had problems that could be attributed to static initialization in c++ before, but I wasn't entirely certain at the time that this was the problem. Just like an ugly memory bug, the static initialization order rears its head with meaningless memory access violations--which in my case seem to always end up deep in the stl. While porting something from linux to Mac, a simple re-ordering of the object files on the make line was enough to solve the problem. Wrapping the static variables in static functions to ensure an initialization order is clearly a better solution.

Obviously these things should become a problem and cause problems before main is even entered. I was also building the application for the iPhone and was experiencing problems with it as well. The problem was a segfault of sorts, and the stack was getting f'ed, and GDB was being almost hopeless. Of course, as I just had problems with static initialization I attributed these problems to be that beast. After several failed attempts at re-organizing the static initialization, digging through the semi-automatic resource handling code--I eventually followed the trail down the wormhole with the debugger to a buffer underflow error. Damn it! The only part of code that was different between the Linux/Mac version and the iPhone version was the loading of resources--which first have to dereferencee file names from the main application bundle. This code was different, and in the iPhone port I was using CFString and its reverse search to find the last occurrence of the '.' for file extensions. Obviously I wasn't checking to see if the return value was within bounds before computing a substring--which suprisingly wasn't being checked in the CFString substring functions. I'm certain I spent an hour looking for that. So obvious, but I was led astray by the static initialization. Cut again by Occam's---again and again and again.

Arduino

Got an arduino for x-mas and just got around to playing with it the last couple nights. Pretty damn fun. Learnt a little (pull-down and pull-up circuits).

Also started working on generating an image from a continuous line. Preliminary results and some embedded source code are linked in this page. The version is based on subdivision and post-processing.