acquire_bitmap(frame);
        for(i=0;i<the_image[size]->w;i++)
          for(j=0;j<the_image[size]->h;j++)
            _putpixel32(frame,
tempex+cos(crix=(y+FLOW_CS_X/the_image[size]->w*i))*sin(criy=(y+FLOW_CS_Y/the_image[size]->h*j))*the_image[size]->w,
tempey+cos(criy)*sin(crix)*the_image[size]->h,_getpixel32(the_image[size],i,j));

release_bitmap(frame);

That's the code. It takes a picture & prints it to the screen, placing each pixel in such a way, that it looks like the picture is on a ball. But it is very slow, drawn every frame. Obviously, the bottleneck is the cosine & sine functions. Would you please help me out?

Thanks.

It's more likely to be the float to int conversion you do after the cosine & sine. Plus the fact that you're doing your work back to front. You should be looping through screen pixels and calculating backwards to source pixels rather than going through all source pixels and deciding where to put them on screen.

Uhm. First of all, I've no idea how to do that. Afterwards, The picture doesn't take all the screen & much smaller, and it can be anywheere generally. If your method is still OK, would somebody please expand it?

Thanks, still.

I have forgotten these functions a bit, but i don't think that sin(a)*cos(b), is the same as cos(a)*sin(b). (and I have that actually)

Thanks!

Oops. Both TeamTerradactyl and myself misread your code there. Still, all the ideas either of us mentioned still work. Corrected version of my code to fix the stuff we misread:

edit: fixed amount of memory allocated for tables.

You are wrong. The operations, are done with locked memory, inside the ram, and are simple data copying, with some addresing dificulties I guess. (second sentance is totally my opinion, is it correct?)

putpixel(just some int pluses)
 if(getpixel())
  putpixel()

40+ FPS

The code I gave, stable 9 FPS (same picture, color deapth, program)

If you do not believe me, I can post the program. But: I did think about it, and I'll later add an option, that would perform some operations in an 8bit mode & then blit to the screen.

I am sorry, I don't understand, would you please expand your idea? Thanks.

TeamTerradactyl & orz, thanks a lot!
Great idea. I think will help me a lot in future.. It looks like I'm going to have another question, I'll post there the program and will tell the FPS increasment.

Thank you.

Thank you, but: Would you please tell me where can I get some info about the cache & how does it work?

The cache is part of the physical computer hardware.

The very smallest are the registers found in the CPU chip itself. On most 32-bit machines, you have about 6-8 of these registers that you have available to use and fiddle with (the compiler does all this for you, as it is EXTREMELY hardware-dependant). It can usually handle up to about 2-3 billion operations a second on slower machines.

The next-smallest is the physical memory found directly next to the registers: the "L1 cache". This is typically kept small so as to speed up all the different math and memory calls necessary to do the calculations (typically, less than 8KB).

Above that is the L2 cache. This is what most CPU vendors will advertise about their chips: most have something like 2MB of L2-Cache (or on-board cache), but newer processors are coming with 4- and 8MB. The more you have, the slower the processor, but it depends on how the actual processor has been setup.

Then, after the L2 cache is the actual RAM you have in your computer. Most people have between 512MB and 4GB of RAM. This RAM is slower than the above-mentioned ones, simply because there is more of it and it is designed differently.

So when the others here have suggested that you do row-column order instead of column-row order, it means that the computer will grab a huge chunk of memory and stick it into the L2 cache. So a bitmap that you're _putpixel()-ing onto is going to be loaded into as much of the L2 cache as can fit. If you tell it to calculate the columns first, what essentially happens is:

1) The BITMAP is loaded into the L2 cache (as much as can fit)
2) You access a single pixel, doing the calculations you need
3) You then move "down" in the image (instead of "right", or into the rest of the contiguous memory which has already been loaded), which essentially repeats Step #1 again

This slows down the computations enormously, because you have to "reload" the memory a bunch of times. However, if you do it in row-column mode, this is what happens:

1) The BITMAP is loaded into the L2 cache (as much as can fit)
2) You access a single pixel, doing the calculations you need
3) You move "right" (into the next piece of the BITMAP which is still in memory)
4) You repeat Steps #2-3 until you run out of BITMAP. When this happens, Step #1 repeats with the next "segment" of BITMAP that needs to be loaded into memory

Because you don't need to load/unload the different sections of the BITMAP from memory, it's a LOT faster access-time.

Now, the above numbers (about the L1/L2 cache, etc.) aren't exactly accurate, but are guestimates (I forget the exact numbers from my CS class...) more for clarification than exact specs.

Oh, and if you have a 64-bit machine, the number of "registers" jumps from 6-8 to nearly 14-16, IIRC. So they're a LOT faster than 32-bit machines (if compiled for 64-bit processors, that is).

orz, TeamTerradactyl & HoHo, thank you very much. But of course, new questions appeared.

orz:

I don't really understand, what is nearly, how is the "near" defined? And,I understood out of here, that in lots of cases (my for example) most of the bus traffic is simply useless? And, is this the part where lower CL comes for help?

TeamTerradactyl:

(L2 cache)

I'm totally confused, and can't understand why. The only thing I can think of, is that it's being always used up completely, and transferring data inside takes more time. Is it right?

HoHo:

I don't understand how malloc can affect the performance, and what's the difference in 'malloc'ing space manually, and using standard routine.

Thank you all very much for the shared experience and knowledge. I'm serious

If you request something from memory, the computer will "grab" the whole chunk of memory physically around it. Meaning, that if I have some data like this:

..............XXX......................................

What happens is that the computer will grab ALL that data; the "..." before and after the actual "XXX" that I want. This has been done on purpose, because usually, if you want "XXX", then you may possibly want something found in memory immediately before or after it. An array is a good example. If you have a BITMAP, you first want "XXX" to draw onto screen, and then you want "YYY" which is found immediately following it, and then "ZZZ" after that.

So the computer will grab the entire chunk of memory "physically near" the part you want.

If you try to access a bitmap like this:

X..................
X..................
X..................
X..................
X..................
X..................
X..................
X..................

and you want to get all the X's, the memory for that BITMAP looks like one continuous block of memory like this:

X..................X..................X..................X..................X..................X..................X..................X..................

The problem with this, is that often, there's not physically enough memory to hold all of that at once. So the computer will grab the first few chunks of it at a time, like this:

X..................X..................X..................
X..................X..................X..................
X..................X..................

The problem with this, is that it will first take the first 'X', then grab the second 'X' and then the third. But when it needs the fourth 'X', it has to run out and grab the next "chunk" from memory. If, however, you wanted to access the BITMAP like this:

XXXXXXXX...........
...................
...................
...................
...................
...................
...................
...................

What the computer actually needs would look like this:

XXXXXXXX................................................................................................................................................

And since it doesn't all fit into memory at once, it would be like this:

XXXXXXXX.................................................
.........................................................
......................................

So it doesn't even need the extra two "chunks" of memory; it just grabs the first X, then the second, then third, then fourth... all contiguous.

That's what we meant by "near": it is located physically close-to the memory that you wanted to access. It will stay loaded into memory until the CPU decides that it wants a value from some other location in memory. This is a good thing because if you want to blit() a BITMAP to screen, it asks to grab the first "chunk", then when that chunk is done, it grabs the next, then the next...

This is correct. The way that it's being "used up completely" is what I just explained above: it grabs an entire chunk of memory and "fills up" the L2 cache with it. That way, if you need to access the memory immediately before or after the "piece" you requested, it is there already, ready to be used for the next CPU call.

The std::vector arrays have been implemented in a smart way: Each time you start adding stuff to the end of them, they double the size of memory they need. This is a speed advantage, because instead of jumping out to memory and requesting another single byte (or more) of memory for EACH object you want to tack on the back of the array (and sometimes, you may have a LOT that you want to push onto them, one-after-another, like a bunch of monsters that you have to allocate memory and BITMAPs for, before they're displayed on-screen), it simply tells the computer that you want "a lot of memory" all-at-once, and then uses that memory until it needs more.

It takes less time to simply add a value or two into an array than it does to actually request the RAM space somewhere, wait for a response (or Out-Of-Memory error response, etc.), then fill it with your new data. What malloc() does is that precisely: it requests space in memory somewhere. Those arrays/vectors do the same thing, but the std::vectors usually do it as optimized as possible so you don't have to do malloc()s nearly as often.

Sorry this was long-winded again. I hope it helped answer your questions, though!

When you read address X into memory, the lowest cached address is
(X & ~63), or equivalently (X - (X % 64)). The highest address cached is ((X & ~63) + 63), or equivalently (X - (X%64) + 63). That is, a 64 byte block starting the the lowest multiple of 64 such that the block will include the address you read. That's assuming you're using an Athlon/XP/64/X2 or Core/2 or P4. For some older processors (P3s, P2s, etc), replace all the 64s and 63s with 32s and 31s. This value is called the "cache line size", and on non-x86s is usually between 16 and 64 bytes.

If you do linear requests, recent CPUs will generally attempt to automatically prefetch the next data for you. There are prefetch hint opcodes too, with which you can explicitly tell the CPU to load some address into cache. I believe that some CPUs will prefetch if your doing linear accesses backwards (going down in memory), or if you're alternating between two different linear walks, or that kind of thing, but don't expect them to be smart. Prefetching was only introduced into mainstream CPUs in the last 4 years or so.

CPUs have special units that do that, no performance is lost while doing it.

And more expensive for us. Thanks.

What is the structure of a modern CPU?

Chip-Architect has a great article on the AMD Athlon64.
Happy reading!