hi,
basically this is my filter:

it is very slow... when I try it with lower resolutions, it is much smoother (1024*768 compared to 640*480 ). So the part in the loop is not so well done by me... There must be a critical mistake, otherwise such a simple filter wouldn't lag so bad...

If I don't call acquire_bitmap() the performance doesn't get worse... shouldn't that lower fps to almost zero?

thx, ~~Backe

Don't use generic getpixel, putpixel, makecol and getX functions! Use the colour depth specific ones instead. Actually you should access bitmap memory directly. That'll make your code several times faster.

EDIT: But at 1024x768 that will still be slow. You can probaly use OpenLayer to get the same effect. I've no idea how though...

What type of bitmap is being passed? A memory bitmap? Video? If you know the depth, you can use the functions directly:

_getpixel32 // note the underscore!
_putpixel32 // note the underscore!
getr32
getg32
getb32
makecol32

Replace 32 with the depth you're using.

EDIT:
You can also use

bmp_select(bmp);
addr = bmp_read_line(bmp, y);
for(x)
   buf[x] = bmp_read32(addr+(x*4));

do_stuff_to_line(buf);

addr = bmp_write_line(bmp, y);
for(x)
   bmp_write32(addr+(x*4), buf[x]);

Check the exflame example for methods of writing directly to bitmaps.

For some info on how to access BITMAP data directly check out: http://www.allegro.cc/manual/api/direct-access-to-video-memory/

In addition to what was said above, swapping the order of your loops may also help due to the way the bitmaps are layed out in memory.
If you can use an 8 bit image for this, you can get the effect very quickly by using a grey-scale palette.

It should also be noted that the code you provided may not produce the result you want. In that case, you'll have to weight your color components: luminance

the colour depth specific getpixel and putpixel functions and the ((long *)bmp->line[y])[x] crash my program in my IDE the program quits, and keeps the resolution, though. If I run the exe manually, the window just becomes black.
The bitmap passed is a memory bitmap. Nothing special, just a simple doublebuffer.
color depth is 32. The getX functions work better when color depth specific.

If it crashes then you are trying to read from a point outside the bitmap.

I also find that, instead of using nested for loops, using a single for loop can benefit speed more than you would think. That is, instead of:

// maxa represents the max "width"
// maxb represents the max "height"
for(int b = 0; b < maxb; b++)
  for(int a = 0; a < maxa; a++)
    do_something();

use:

// maxa represents the max "width"
// maxb represents the max "height"
for(int i = 0; i < (maxb * maxa); i++)
{
  int b = i / maxa; // b represents vertical movement
  int a = i % maxa; // a represents horizontal movement
  
  do_something();
}

Of course, this doesn't always work(mostly due to optimizations where possible), and you probably knew this anyways.

I was thinking that, maybe, you could somehow use draw_lit_sprite to fake the whole grayscaling processes. I haven't used this function before, and don't know it's limitations.

Yes, your right.
Ok, this already does a pretty good job:

It still lags, but it's better.
How could one single loop improve performance? I tried it, it is not noticeable without counting the frames (I don't count the frames in my program)

Store bmp->w*bmp->h, and copy bmp->w and bmp->h to local variables (right now, you're doing a pointer dereference in your inner loop, which is slower than accessing a local variable).

The single loop might buy you some time because it safes one jump instruction at the end of the loop (the nested loops have two jumps, one for each loop), on the other hand, division and modulus are slow operations (but they can probably be pipelined and executed together, someone else will know).

Try this:

It can be optimised further, but I wanted you to see what was happening first.

.3 * R + .59 * G + .11 * B

Isn't that much slower in a computer that can do 5 trillion calculations a second.

True, but unless it needs to be accurate, the quick divide by 3 will look fine and be a little bit faster.

Yep, that's the optimised version. Although you could put the grey bit in the pixel write and get rid of the grey variable altogether.

A faster way would be to make a whole new set of bitmaps, which are greyscale. They could be automaticly generated on load and stored "together" (in the same class/struct) with their "parent" bitmap. Then you'd have some function which switch their pointers when you want to draw in greyscale.

.25*R + .625*G + .125*B shouldn't be too much off.

gray =
    ((color&0xFC0000)>>18) +
    ((color&0x00FE00)>> 9) +
    ((color&0x00F800)>>11) +
    ((color&0x0000F8)>> 3);

gray|=(gray<<8)|(gray<<16);

And if .25*R + .5*G + .25*B is fine for you:

gray =
    ((color&0xFC0000)>>18) +
    ((color&0x00FE00)>> 9) +
    ((color&0x0000FC)>> 2);

gray|=(gray<<8)|(gray<<16);

What's with the seemingly random decimal points? I could understand multiplying them all by 0.3, or even using a slightly different number for green, but where do .59, .11, .625, and .125 come from?

They come from empirical testing. r * 0.299f + g * 0.587f + b * 0.114f is what Photoshop uses, from what I've read.

That's the standard set by some standard setting organization whose name is a French acronym I can't remember right now. .625, .5, .25, .125, etc. come from the fact that multiplying a number with them can be done with bitshifts.

For optimizing the loops a bit more, a good thing would be to do the operations on several bitmap lines in one cycle, probably 2 or 4 should be good options. That way compiler will probably mix those functions and CPU can execute several of those in parallel.
If done correctly I wouldn't be surprised if you would get two or more times faster execution with relatively modern CPU with good OoO execution

For a lot of colour effects I find converting to HSL much easier. One thing I've used in a game is convert to grey-scale but keep the orangey/red colours.

I would just save the double loop / modu operator speed headaches all together and just do one loop.

for(int y = 0; y < bmp->h; y++)
 for(int x = 0; x < bmp->w; x++)
  c = ((long *)bmp->line[y])[x];

becomes

for(int i = bmp->w * bmp->h - 1; i >=0; i--)
 c = ((long *)bmp->line[0])<i>;

Can someone confirm or deny this?

dustin, your algo is wrong, and potentially dangerous.
you should not use the line[] beyond a single line.
not to mention that you also start out-of-bounds

HoHo, im intersetsed in your theory behind why 2 lines at a time would work quicker, care to elaborate

Why not?

Because there is no guarantee that memory of line 2 will follow the memory of line 1.

It's very likely to happen, but not guaranteed.

For memory bitmaps, the lines will be continuguous (go across line 1, you'll eventually reach line 2). However, the end of the right side is not necessarilly the beginning of the left. There may be extra padding, and the bitmap struct doesn't have a public pitch member, so you need to get it yourself.

int w = (bmp->line[1]-bmp->line[0]) / ((get_bitmap_color_depth(bmp)+7)/8);
for(i = w*bmp->h - 1;i >= 0;--i)
...

and doing your memory accesses backwards will be slower than forwards.. memory controllers and prediciton in CPU's prefer/presume forwards access.

Forgot to mention, if you do the two loops, copy the bmp->line[y] to a local pointer and dereference that in your inner loop.

Here are 2 more options:
1. Use 8bpp mode. Create a greyscale palette and set it. Create an RGB table and select it. Load all sprites with COLORCONV_TOTAL | COLORCONV_TRANS. There you go.
2. Use >8bpp mode. Create a greyscale palette and select it. Create RGB table. Load all sprites normally, set_color_conversion(COLORCONV_TOTAL | COLORCONV_TRANS), then blit each sprite to an 8bpp sprite of same size and use that instead.

Both ways make use of the built-in palette conversions allegro offers.

and using a long* will be wrong on 64bit systems

all that bit shifting and masking, why not simply use a uint8_t* and avoid all that.

A what?

unsignedinteger8bit_type

Ok.

How will that stop the need for bitshifting and masking when using Bitmap data?

Hehe, good point. That's what happens when you just take someones code and don't really think what is going on.

Instead of calculating RGB from the 32bit integer you simply get the RGB values directly.

I'll make some tests after I have finished configuring my system. That shouldn't take more than couple of hours.

Well, in that case I imagine the compiled code still has to do masking and bitshifting? Otherwise it would be reading one byte at a time instead of at least 4.

why does the compiled code still need to do bit shifting and masking ?

I imagine the compiler wants to read in 4 bytes into a 32 bit register (for most PC's). It then can process 4 bytes worth of information.

The alternative is to use a register for 1 byte, process it, and then read new data into the register.

you like to 'imagine' dont you?

why would you want to read in 4 bytes, when all you wanted was one ?

how much asm programming have you done ?

'the' alternative, there is only 1 alternative ?

what about the 64bit registers, and the 128 bit registers ?

First of all: Get rid of the negative attacking attitude. ok?

Secondly: I have done limited 8-bit cpu programming in the past. And in this case it's better to read in 2 or more bytes than 1.

Perhaps because it's inefficient? It was pretty well known in the past to read in more than one byte if you could.

is there any value in discussing technical stuff when you pre-empt it with 'imagine' ? and 'perhaps'

you made a bunch of assumptions, and all i asked was how you got to that conclusion ?

you also claim there is only one alternative, how did you come to that conclusion ?

so you dont have much experince with modern CPUs, or asm programming, yet you make statements that dont make a whole lot of sense.

I used those words because while I have experience of 8 and 16 bit processors I have no more recent experiences.

My 'assumptions' were based on my experience. Nothing you've said indicates that you have experience of cpu's either.

Why don't you back up your assumptions and criticisms first eh?

Old CPU's have quite little in common with modern ones when you are comparing different optimization techniques

That may be the case, which is why I used the cautious language I wrote, rather than a 'this is the best way' type of statement.

I'd still like to see AJ show some knowledge of this himself instead of just negative comments.

ive made no negative comments, ive simply asked how you got to your conclusions ?

which statements of mine require proof of validity ?

'cautious' a statement pre-empted with 'imagine' or 'perhaps' is hardly cautiuos...

perhaps you have sex with fluffy animals, is a little cautios, but
i imagine you have sex with fluffy animals, isn't particauly cautious.

some might even say "i imagine" is the same as "i believe"

you've almost admitted you know very little on this subject, yet persist..
or maybe (you do love those fence-sitting qualifiers) you want to keep going, your ego seems to be up for it.

you can throw as much mud as you like, when the results arrive (Thanks HoHo) that will be all the knowledge you will require.

Really?

You must be blind!

I'm explained quite a few times now how I've come to my conclusions. You have failed to do that each time I've asked.

So I conclude you know nothing about this.

Having followed some discussions in AD and some topics here in a.cc I conclude that AJ knows about optimizations way more than average programmer

I haven't yet got to the testing but I'm almost there. I just have to move some files around to make room for installing some necessary programs. It shouldn't take more than two hours for first results.

You guys are funny hehehe...

The fastest way... it will use more memory too.

Hmm... I don't know nothing about hsl, but converting rgb -> hsl to do the effect and then hsl -> rgb to blit in screen doesn't seen very good if you want real time.

For the others solutions, Kitty Cat and Krzysztof Kluczek can be mixed to get the job... and avoid *, / and % if you can...

In the test Hoho did before:

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

should be

gray |= ( gray << 8 ) | ( gray << 16 );
line[ x ] = gray;

right?

FBlend uses this optimization too no?

ps: sorry for the English... I'm Brazilian :p

Natually. Just about twice as much (assuming the majority of your memory usage is from bitmaps)
I still say it's better than the alternative... With this method you could have 133 500 by 500 bitmaps (24bpp) for 200 megs of ram. That is quite a lot of bitmap-space, and not very much in regards to the average RAM of a modern computer...
and at NO performance penalty (afaik).

For better memory usage, you can use 8 bpp bitmaps too, with a grayscale palette, so you can simple use set_palette() and then blit()... it will add 25% memory usage for each bitmap in 32bpp. You then will use the method that Tobias Dammers pointed above

Wow, I want one of those modern computers hehehe... I only have 256 MB

Finally after some trouble with moving entire /usr directory to other partition I got time to do some more benching

First I ran the exact same program I posted before on my home PC, a P4 @3.6GHz running 64bit Gentoo.
Main differences with the previous one are 64 bittiness, ~10% faster CPU clock, 1M vs 2M L2 cache and DDR1@220 vs DDR2@320 theoretically giving ~45% more memory throughput.

Results are here, order is as before:

More registers certainly seem to help because now unrolling by four is clear winner on average being about 20-30% faster than unrolling by two and ~50-70% faster than no unrolling. Extra memory bandwidth also seems to help, especially with the original code.

L2 cache doesn't seem to help a whole lot. With each pixel doubling the time doubles. 1024x512@32 bitmap is a bit bigger than 2M and twice as big and small bitmap processing scales almost linearly in 2x increments. If there would have been a big jump in time that would have indicated that L2 cache was actually useful.

Before I started to do some more benches I decided to literally take a look how those grayscale images look like and saved them to disk. To my suprise almost all of them were blue instead of grayscale, even the original one. Only the approx2 gave grayscale image. It might be because I assume RGB order, also perhaps 64bittiness has something to do with it. I'll take a closer look at it and try to fix the functions.

I can't promise when will I get some more results. I did try converting byte-at-a-time and it seemed to give almost 2-3x speedup compared to the 4x unrolled one but the output is not correct so the real speedup might change. It's 1:30 a.m here so I'm afraid I can't get anything up before tomorrow night. By then I try to make a bit more sophisticated test program.

Perhaps if I get time and I find my PAPI wrapper I can get some more interesting results, like L1/2 cache misses/hits, retired instruction count, cycles stalled waiting for recourses etc

[edit]

whoops, I think I found the mistake.
It seems the modifications dudaskank proposed are to blame. I made them shortly after getting the results and before saving out bitmaps. It seems like when I put back line[ x ] = gray * ( ( 1 << 16 ) | ( 1 << 8 ) | 1 ); it works again.

I think I would be much more productive if it wouldn't be so late

Richard, just facts, you used 'imagine' twice, and most (majority) of your statements in those 3 posts contained maybe,imagine,perhaps etc..

Either you say something because its a fact or you strongly believe it to be a fact, or you dont say it.
If you dont know something, or are uncertain, you ask directly, not this "Perhaps <statement> ?" nonsense.

Btw, im not 'attacking' RichardPhipps.intellect or RichardPhipps.logic or RichardPhipps.emotion, im attacking RichardPhipps.ego which seems to be unwilling to accept what RichardPhipps.intellect is telling it, i strongly apologize if the former 3 elements are offended, if being asked a few direct questions is too much for your ego to handle, i think its time it got put in its place.

War are a waste of time. ( and are off-topic ;-p )

Rubbish. There's no reason not to say something you're not sure about if you specify that (which one does by adding `I expect...' or `perhaps...').

Wasn't that `I imagine that to do X, Y does Z' in the meaning `I don't know for sure, but if I try to think how to do X, Y does Z'?
Which is a fairly normal way of using the phrase `I imagine...', as far as I know.

I have done some test, (smaller value is faster, best to worst)

3830 2x unrolling, array method, better ordering
3964 2x unrolling, array method, bad ordering
4014 1x array method
4340 2x unrolling, ptr method
4840 1x ptr method

So it looks like unrolling a little helps, so does using array notation.

The unrolling amount will be CPU specific, but 2x is a fairly safe on most systems.
Array notation helps the optimz compiler avoid aliasing issues.
And a little re-ordering helps too.

AJ: Regardless of what I have said (which Evert understood why I said it) you have not explained why what I said about registers is wrong. I explained my knowledge was limited, but you have not shown me any knowledge of cpu registers despite my repeated requests that you do so. Until you do that why should I believe your views over mine?

Because RAM-to-cache is the major bottleneck in modern systems. Reading from cache is cheap, and whether you read one byte at a time or in groups of 4 doesn't make much of a difference. Multiple sequential cache reads are cheaper than reading 32 bits and then manually slicing them into bytes.

At last some information! Thanks Tobias.

So, is not the compiled code slicing the cached bytes from 32/64 bit values into 8 bit values itself as each one is read?

Depends on cpu architecture I guess. It will hardly be slower though.

All I said was that if the cpu uses registers that are 32 bits or more than I would imagine it's reading in more than one pixel and then splitting it to be more efficient.

Yeah. It just so happened that you imagined wrong
Copying data into registers isn't so much of a bottleneck anymore due to cache.

You want to explain asm programming to you ?
It would take about 20 pages..

A register is where work is done, not where data is stored.
You dont read in any more than you can actually work on.
If you read into a register 4 bytes, but want to process a byte, you then need to read into another register more data to operate on it, until you are left with 1 byte. This is 'Asm programming 101: Know your hardware'

Your confusing registers with memory, registers with cache, cache with main memory, just about all of them with each other. There are some fairly fundamental points you've missed that make me wonder just how much if any ams programming you have done.

We are talking about real things, they all have names, there is no need to use any abstraction, so you can refrain from using 'its' which just leaves room for confusion.

Ok. Obviously CPU's have moved on since my 8 bit and 16 bit days. Thank you AJ for explaining why after about 5 requests to do so. Next time, it would be much easier if you did it straight away.. ok?

...and in order to work on data, you need to store it somewhere. In other words, data is stored in registers and cache and main memory, all of which are different sorts of memory. Though registers don't necessarily contain what is typically referred to as "data" (when used to distinguish "code" from "data"), technically there isn't too much of a difference - pointers, numbers, cpu instructions - all of these are ultimately represented as bits & bytes.
You load data from main memory into registers to manipulate it, you write data back to main memory when you're done. Only that several levels of cache sit between registers and main memory, and data transfer through the cache is one of the crucial factors to consider when optimizing for a modern cpu.

no.

Tobias: Ah I see. I never dealt with cache's on the 8-bit and 16-bit machines.
AJ: Kiss my Ass then.

No what?

Can't see anything wrong with this.

Maybe you don't agree, but if they aren't memory, what are they? They all fit the criteria: you can write a certain number of bits to them, and you can read them back. What's special about registers is that the cpu can perform a lot of operations directly on them.

That is the basic (simplified) procedure. I left out the cache part, the fact that at times the values in registers are generated rather than read from somewhere else, and I didn't go into i/o.

I didn't say the crucial factor, but one of the. Stuff like thread switching, instruction pairing, branch optimization etc. are equally important. Also, to clarify, by "data transfer through the cache" I am referring to the fact that avoiding cache misses is usually an easy and effective optimization technique.

Anyway, I just tried to explain the general concepts from the C++ point of view; you're the ASM god, so if you care to explain properly, please do so. No sarcasm or offense intended.

unless your memory access is very random, like in original code

With this particular case caches are not much of use when images are bigger than what fits into cache because by the time that image has gone through processing once the first lines of it have already been flushed back to ram and are needed to fetch into caches again.

When CPU reads some data from ram it automagically copies a chunk into cache. The size of that chunk is the length of a cache line. Usually it is either 32, 64 or 128 bytes. IIRC my P4 should have 64byte cache lines, Opterons and probably regular AMD64's should have 128 byte lines. PM and some older CPU's should have 32byte cache lines.

Now if you access memory the same way as in original code, it gets fun. Every time you need four bytes but CPU prefetches 64, 16x more than needed. So, when you thought for 1024x1024x32bit bitmap you would need 4MiB bandwidth you really use around 64MiB.

My work PC could do ~8 1024x1024x32bit grayscale images per second* or ~400 cycles per pixel. That is about 32MiB in total. Not at all too much. Because of what I said earlier that translates to 0.5GiB/s. Still not too much because theoretical bandwidth should be about 10x as big. So what is the problem with the code?

*) With just reordering the loop it could do 200 images per second or ~25x increase in speed. That is about 16 cycles per pixel.

My guess is that cache misses are to blame*. Cycle count for single pixels seem to confirm that. Reading from L1 takes just a few cycles, usually 2-4. If data is not in L1 it takes about 15-25 cycles to read it from L2. If it is not there too it takes about 200-400 cycles to get it from memory. Comparing that 200 cycles to the time it takes to grayscale a single pixel (~16 cycles) it should be obvious that for the most of the time CPU just sits idle while waiting for new data to arrive.

*) I haven't yet found my code for counting cache misses but when I do I'll test it. I give no promises but I'll try to do it as soon as I can so I can learn something from it and share it with others

Hopefully some of you now understand why data structures and memory access patterns are important. They can make your code about an order of magnitude faster if done correctly

All of that gets even more interesting once you start dealing with SIMD instructions and memory aligning, software prefetch, read/write around cache, streaming from several sources come into play.

Guys, quit it. You're not being helpful or even moderately funny.

HoHo, have you ever had software prefetch make much of a difference ?
most of my tests haven't shown much improvement, althou i've only done linear forwards access which seems to get prefetched already.

I personally have never used it in my code. Most what I have said here is just theory and educated guesses. I try to test and prove the points I make gradually and that is also the reason why I want to perform some thorough test with the code.

Someone programmed a realtime ray tracer and used prefetching when traversing KD-tree*. Usually there is little linear access but it is really simple to prefetch a few steps ahead. IIRC he got ~15-30% speedup.

That ray tracer was once IOTD at flipcode. Basically it was supposed to be the next article in Jacco Bikker's ray tracing article series. Unfortunately it was never published. I have the code for that tracer stored on disk somewhere. If you want to I can send it to you once I find it.

Fortunately he and some other guys have created a new forum for discussing RT and he has a newer version of the tracer somewhere there.
http://ompf.org/forum

So, to wrap it up, 4 options:
a) Use palettes in some way, so you can (ab)use allegro's built-in (and optimized) color conversion routines to achieve grey-scaling.
b) Use one of the functions discussed by HoHo e.a.; whichever works best. Whatever you do, always use y for the outer loop and x for the inner one.
c) Use a different library that supports hardware-accelerated color effects. OpenLayer might actually get you quite far.
d) Pre-calculate everything.

Wouldn't a hardware-accelerated grayscale filter require programmable pixel shader?

Marcello

No. Texture combiners with dot product support would be enough.

i know not what a KD-Tree is, but i presume it uses ptrs to store data, so data will not be linear in memory, therefore prefetch would make sense, and achieve some speed up.

dont bother with that article, i'll do some more research...
i've heard all the theory of prefetch, but have yet to see it work (for me) in practice.

You persume wrong. The KDTree is static and calculated in preprocesing step and gets stored in single array. That makes things a bit better than linked list. The data structure is laid out so that close nodes should be quite close in memory too so when one node is prefetched some of it's neibourghs get prefetched too. Each node is 8 bytes so usually quite a lot of them get fetched.

Hoho, that piece of code was on the filterMakeMonochromApprox2() on your post... so when you said it didn't work, I've made some test...

the code:

well it's Java but you get the idea, hehehe... the output in my machine is:

gray: 80
gray rgb1: 808080
gray rgb2: 808080
a simple benchmark...
rgb1 method 100000000 times: 971 ms
rgb2 method 100000000 times: 951 ms

so you can see the method #2 works too... but don't have that super speed improvement that I think, hehehe

that just makes the colour grey{Solid} we (as the topic heading indicates) are trying to do grey{scale}

Also there is no memory access.

For a bit better performance numbers you should put that whole function content to a new function an call it around five to ten times in a row. I wouldn't be suprised if speed increases several times.