[quote]HoHo, im intersetsed in your theory behind why 2 lines at a time would work quicker, care to elaborate[/quote]Basically it would be loop unrolling. Working with two different things gives CPU better opportunity to pipeline instructions. Of course I haven't made any tests with this particular problem so if those instructions do not pipeline well there might not be so big speedup.

[edit]

I just made a little test program to see if what I said holds true. It seems like not too well. Sure, unrolling helps a bit but not by as much as I hoped. I don't know why, perhaps there are too many bit logic instructions and P4 can't execute a lot of them in parallel. Another possibility is that it just ran out of registers and had to swap between L1 cache a lot.

One thing I found out was that the shortcut that Kitty Cat proposed wasn't the fastest I could come up by modifying the original program. Difference wasn't big but it definitely was there.

The biggest speedup came from reordering the loop to go from xy to yx. It gave ~3x speedup at smaller bitmaps and with bigger* 4x and more. That probably comes from the fact that CPU can prefetch the lines. Extracting the line pointer outside of the inner loop didn't give anything for some reason.
*) At 512x256 it was ~2.8x slower, 512x512 12x slower, 1024x512 ~25x slower.

The fastest was unrolling by two but difference with the reordered loop was only about 10%.

So here is the program. It requires gettimeofday function so it won't compile on Windows. I you replace the Timer class it should work.
[code]#include <allegro.h>
#include <iostream>
#include <sys/time.h>
using namespace std;
typedef void ( *testProc ) ( BITMAP* b );

class Timer {
timeval begin, end;
double time;
public:
virtual ~Timer() {}
void start() {
gettimeofday( &begin, NULL );
}
void stop() {
gettimeofday( &end, NULL );

time = end.tv_sec - begin.tv_sec + ( end.tv_usec - begin.tv_usec ) / 1.e6f;
}
double getTime() const {
return time;
}
double getTimePassed() const {
timeval tmp;
gettimeofday( &tmp, NULL );
return tmp.tv_sec - begin.tv_sec + ( tmp.tv_usec - begin.tv_usec ) / 1.e6f;
}
};

class AutoTimer : public Timer {
public:
AutoTimer() {
start();
}
~AutoTimer() {
stop();
cout << getTime() << endl;
}
};


void filterMakeMonochrom( BITMAP* bmp ) {
acquire_bitmap( bmp );
const int w = bmp->w, h = bmp->h;
for ( int x = 0; x < w; x++ ) {
for ( int y = 0; y < h; y++ ) {
int grey;
const int c = ( ( int * ) bmp->line[ y ] ) [ x ];
grey = ( c >> 16 ) & 0xFF;
grey += ( c >> 8 ) & 0xFF;
grey += c & 0xFF;
grey /= 3;
( ( int * ) bmp->line[ y ] ) [ x ] = grey * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
};
};
release_bitmap( bmp );
};

void filterMakeMonochromReordered( BITMAP* bmp ) {
acquire_bitmap( bmp );
const int w = bmp->w, h = bmp->h;
for ( int y = 0; y < h; y++ ) {
for ( int x = 0; x < w; x++ ) {
int grey;
const int c = ( ( int * ) bmp->line[ y ] ) [ x ];
grey = ( c >> 16 ) & 0xFF;
grey += ( c >> 8 ) & 0xFF;
grey += c & 0xFF;
grey /= 3;
( ( int * ) bmp->line[ y ] ) [ x ] = grey * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
};
};
release_bitmap( bmp );
};
void filterMakeMonochromReorderedExtractedPointer( BITMAP* bmp ) {
acquire_bitmap( bmp );
const int w = bmp->w, h = bmp->h;
for ( int y = 0; y < h; y++ ) {
int* line = ( int* ) bmp->line[ y ];
for ( int x = 0; x < w; x++ ) {
int grey;
const int c = line[ x ];
grey = ( c >> 16 ) & 0xFF;
grey += ( c >> 8 ) & 0xFF;
grey += c & 0xFF;
grey /= 3;
( ( int * ) bmp->line[ y ] ) [ x ] = grey * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
};
};
release_bitmap( bmp );
};
void filterMakeMonochromUnrolled2( BITMAP* bmp ) {
acquire_bitmap( bmp );
const int w = bmp->w, h = bmp->h;
for ( int y = 0; y < h; y += 2 ) {
int * line1 = ( int* ) bmp->line[ y ];
int* line2 = ( int* ) bmp->line[ y + 1 ];
for ( int x = 0; x < w; x++ ) {
int grey1, grey2;
const int c1 = line1[ x ];
const int c2 = line2[ x ];
grey1 = ( c1 >> 16 ) & 0xFF;
grey1 += ( c1 >> 8 ) & 0xFF;
grey1 += c1 & 0xFF;
grey1 /= 3;
grey2 = ( c2 >> 16 ) & 0xFF;
grey2 += ( c2 >> 8 ) & 0xFF;
grey2 += c2 & 0xFF;
grey2 /= 3;
line1[ x ] = grey1 * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
line2[ x ] = grey2 * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
};
};
release_bitmap( bmp );
};
void filterMakeMonochromUnrolled4( BITMAP* bmp ) {
acquire_bitmap( bmp );
int grey1, grey2, grey3, grey4;
const int w = bmp->w, h = bmp->h;
for ( int y = 0; y < h; y += 4 ) {
int * line1 = ( int* ) bmp->line[ y ];
int* line2 = ( int* ) bmp->line[ y + 1 ];
int* line3 = ( int* ) bmp->line[ y + 2 ];
int* line4 = ( int* ) bmp->line[ y + 3 ];
for ( int x = 0; x < w; x++ ) {
const int c1 = line1[ x ];
const int c2 = line2[ x ];
const int c3 = line3[ x ];
const int c4 = line4[ x ];
grey1 = ( c1 >> 16 ) & 0xFF;
grey1 += ( c1 >> 8 ) & 0xFF;
grey1 += c1 & 0xFF;
grey1 /= 3;
grey2 = ( c2 >> 16 ) & 0xFF;
grey2 += ( c2 >> 8 ) & 0xFF;
grey2 += c2 & 0xFF;
grey2 /= 3;
grey3 = ( c3 >> 16 ) & 0xFF;
grey3 += ( c3 >> 8 ) & 0xFF;
grey3 += c3 & 0xFF;
grey3 /= 3;
grey4 = ( c4 >> 16 ) & 0xFF;
grey4 += ( c4 >> 8 ) & 0xFF;
grey4 += c4 & 0xFF;
grey4 /= 3;
line1[ x ] = grey1 * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
line2[ x ] = grey2 * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
line3[ x ] = grey3 * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
line4[ x ] = grey4 * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
};
};
release_bitmap( bmp );
};

void filterMakeMonochromApprox( BITMAP* bmp ) {
acquire_bitmap( bmp );
const int w = bmp->w, h = bmp->h;
for ( int y = 0; y < h; y++ ) {
int* line = ( int* ) bmp->line[ y ];
for ( int x = 0; x < w; x++ ) {
const int color = line[ x ];
int grey =
( ( color & 0xFC0000 ) >> 18 ) +
( ( color & 0x00FE00 ) >> 9 ) +
( ( color & 0x00F800 ) >> 11 ) +
( ( color & 0x0000F8 ) >> 3 );

line[ x ] = grey * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
};
};
release_bitmap( bmp );

};

void filterMakeMonochromApprox2( BITMAP* bmp ) {
acquire_bitmap( bmp );
const int w = bmp->w, h = bmp->h;
for ( int y = 0; y < h; y++ ) {
int* line = ( int* ) bmp->line[ y ];
for ( int x = 0; x < w; x++ ) {
const int color = line[ x ];
int gray =
( ( color & 0xFC0000 ) >> 18 ) +
( ( color & 0x00FE00 ) >> 9 ) +
( ( color & 0x0000FC ) >> 2 );
gray |= ( gray << 8 ) | ( gray << 16 );

line[ x ] = gray * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
};
};
release_bitmap( bmp );

};

void filterMakeMonochromApproxUnrolled( BITMAP* bmp ) {
acquire_bitmap( bmp );
const int w = bmp->w, h = bmp->h;
for ( int y = 0; y < h; y += 2 ) {
int * line1 = ( int* ) bmp->line[ y ];
int* line2 = ( int* ) bmp->line[ y + 1 ];
for ( int x = 0; x < w; x++ ) {
const int color1 = line1[ x ];
int grey1 =
( ( color1 & 0xFC0000 ) >> 18 ) +
( ( color1 & 0x00FE00 ) >> 9 ) +
( ( color1 & 0x00F800 ) >> 11 ) +
( ( color1 & 0x0000F8 ) >> 3 );

line1[ x ] = grey1 * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
const int color2 = line2[ x ];
int grey2 =
( ( color2 & 0xFC0000 ) >> 18 ) +
( ( color2 & 0x00FE00 ) >> 9 ) +
( ( color2 & 0x00F800 ) >> 11 ) +
( ( color2 & 0x0000F8 ) >> 3 );

line2[ x ] = grey2 * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 );
};
};
release_bitmap( bmp );

};

void initWindow() {
if ( allegro_init() != 0 )
exit( 1 );
set_color_depth( 32 );
if ( set_gfx_mode( GFX_AUTODETECT_WINDOWED, 800, 600, 0, 0 ) != 0 ) {
if ( set_gfx_mode( GFX_SAFE, 320, 200, 0, 0 ) != 0 ) {
set_gfx_mode( GFX_TEXT, 0, 0, 0, 0 );
allegro_message( "Unable to set any graphic mode\n%s\n", allegro_error );
exit( 1 );
}
}
/* set the color palette */
set_palette( desktop_palette );
clear_to_color( screen, makecol( 255, 255, 255 ) );
}


void testLoop( string name, testProc proc, BITMAP* bmp ) {
//cout << name << endl;
AutoTimer at1;
for ( int i = 0;i < 5;i++ ) {
//AutoTimer at2;
for ( int j = 0;j < 1000;j++ ) {
proc( bmp );
}
}
cout << "Total ";
}
void test( int w, int h ) {
cout << "Testing at " << w << "x" << h << endl;
BITMAP* bmp = create_bitmap( w, h );
testLoop( "plain", filterMakeMonochrom, bmp );
testLoop( "reordered loop", filterMakeMonochromReordered, bmp );
testLoop( "reordered loop, extracted pointer", filterMakeMonochromReorderedExtractedPointer, bmp );
testLoop( "unrolled by two", filterMakeMonochromUnrolled2, bmp );
testLoop( "unrolled by four", filterMakeMonochromUnrolled4, bmp );
testLoop( "approx1", filterMakeMonochromApprox, bmp );
testLoop( "approx1 unrolled by 2", filterMakeMonochromApproxUnrolled, bmp );
testLoop( "approx2", filterMakeMonochromApprox2, bmp );
destroy_bitmap( bmp );
cout << endl;
}
int main() {
initWindow();
test( 128, 128 );
test( 256, 128 );
test( 256, 256 );
test( 512, 256 );
test( 512, 512 );
test( 1024, 512 );
test( 1024, 1024 );
}
END_OF_MAIN()


[/code]And here is the output from 32bit P4 @ 3.3GHz with 1M L2.

Order of the output is
Original code
reordered loop
reordered loop, extracted pointer
unrolled by two
unrolled by four
approx1
approx1 unrolled by 2
approx2

[code]hoho@WW004029 ~/katsepolygon/quicktests/grayscale $ g++ -O3 grayscale.cpp `allegro-config --libs`&& ./a.out
Allegro up, screen: 800x600 32
Testing at 128x128
Total 0.644086
Total 0.347362
Total 0.355598
Total 0.300813
Total 0.288017
Total 0.37723
Total 0.325882
Total 0.402296

Testing at 256x128
Total 1.24467
Total 0.698047
Total 0.698583
Total 0.591255
Total 0.571967
Total 0.749285
Total 0.619433
Total 0.80224

Testing at 256x256
Total 2.73151
Total 1.38458
Total 1.39629
Total 1.17581
Total 1.3294
Total 1.51228
Total 1.24345
Total 1.6106

Testing at 512x256
Total 8.02422
Total 2.80307
Total 3.01607
Total 2.74377
Total 2.58823
Total 3.21759
Total 2.68319
Total 3.36077

Testing at 512x512
Total 77.4398
Total 6.35915
Total 6.20438
Total 5.79059
Total 5.8432
Total 7.01474
Total 6.09081
Total 6.83415

Testing at 1024x512
Total 315.324
Total 12.642
Total 12.5239
Total 11.0038
Total 12.1963
Total 15.1906
Total 12.9711
Total 13.9239

Testing at 1024x1024
Total 600.725
Total 25.0655
Total 24.1274
Total 24.9667
Total 23.0532
Total 25.5888
Total 23.5083
Total 26.5958
[/code]

I'll run the same test tonight with my own P4. That one is running in 64bit. If indeed the problem is in too few registers it should show right away. Only problem is that it also has twice the L2 and that could alter the results.

Another interesting thing would be to use SIMD instructions. It should be relatively trivial to do and should give quite big speedup compared to what I got here. Currently the biggest bandwidth is around 870MiB/s with 1024x1024 in one direction. There is quite a bit more bandwidth available so it should be possible to get almost full speed out of SIMD stuff without hitting the bandwidth limits.