CPU increase with precomputed tables?

(edit: I'm done editing now, I promise. Maybe.)

The problem is that using precomputed tables results in higher CPU usage and that's confusing me. The routine which creates the table is in fact occurring outside of the applications render loop. It is NOT being recomputed every iteration.

So here are the details;

I've designed a class which executes some numerical algorithms and I've added some methods which allow user to specify the location to some precomputed tables to speed things up.

Code:

---

vector< vector< float > > *TCOS, *TSIN;
//...
void ALG::UseTrigTables(vector< vector< float > > *fsin, vector< vector< float > > *fcos)
{
        TCOS = fcos;
        TSIN = fsin;
}

---

After the object is created I will attach the tables like so;

Code:

---

vector< vector< float > >
 tcos(N, vector< float > (N)),
 tsin(N, vector< float > (N));

// [insert loop here to fill vector-vectors with data]... etc...

Blah.UseTrigTables(&fsin, &fcos)

---

Within the class the tables are used like so;

Code:

---

float f0;
for (int k = 0; k < N; ++k)
for (int j = 0; j < N; ++j)
{
        f0 = fA[k] * fB[j] * (*TSIN)[k][j];
        // ...
}

---

Why would that increase CPU usage?

With trig: ~8%
With tables: ~10%

Where N = 128 (size of tables/loop)

My first guess;

While I am passing a pointer, maybe I'm missing something critical and the tables are actually being copied to a new location in memory every time i call them??

If not, what exact tools do you recommend I use to profile this applications behavior?

Perhaps in your test program you only access the tables once, thus unnecessary computations are not eliminated since they never happen in the first place.

Accessing tables definitely occurs every iteration, I don't want to get specific because people get carried away on forums, but for arguments sake I'm talking about certain fourier transforms.

So the access must occur to get results for each frame that I am processing, another thing to note is that I've removed all math and get a very clear decrease in CPU usage. So I have a baseline that says clearly no math = less CPU intense, which is pretty obvious, but more importantly supports the notion that extra work is happening when both trig and the tables are in place.

Interestingly enough, the amount of 'more' work being done by the lookup-tables is higher than just using trig functions.

Any other ideas? This is going to drive me mad, Lol. I'll have to spend some time looking at what the good open source profiling tools there are, unless you have any recommendations?

... I have this feeling that passing vector pointers isn't doing what I'm expecting, I hope I'm wrong, trying to get 2d arrays to pass around without vectors has lead me to some painful attempts with little success. Maybe I'll try passing old school arrays wrapped in a class...

Quote:

---

Originally Posted by since

Accessing tables definitely occurs every iteration

---

What I mean is that the access of the entire table happens more than once. If the program accesses each element of the table exactly once, then it would not have done less work than computing each element of the table on the fly, assuming that the values are independent (otherwise you would presumably be using memoisation).

Ooooh. IIII seee. Sorry for misunderstanding. I was hoping that the impact of accessing that many array elements would be insignificant, because... no matter what I do I have to go through NxN operations, I thought it was that fact and not array access itself that was causing the performance impact. I'm actually surprised, if I'm using a pointer to look at a specific place in memory, why would that be less efficient than having to go through a series of operations to capture cos/sin values?

It's not like I'm traversing an array to find a value per operation, the array value I'm referencing is literally *defined for every value at NxN.

Is there something actually different about accessing a variable which is an array member versus variable which is not within the subset of an array (other then the fact that you have to use an index)?

Time to bust out the ASM and learn some more, because I would be extremely disappointed to discover that a CPU can't be told to look straight at any given array index and for some reason have that cost a crap ton of CPU cycles. How does a CPU look at any other type of variable data without killing the cpu, because I'm using a lot of other variables in the same operation. >:\

Quote:

---

Originally Posted by since

I'm actually surprised, if I'm using a pointer to look at a specific place in memory, why would that be less efficient than having to go through a series of operations to capture cos/sin values?

---

There is a slight cost in dereferencing the pointer, but perhaps the main cost is that of the array itself, e.g., having to load the array into cache if it is too large (though I am not sure what impact this has on CPU usage). Another cost would be the cost of traversing the array during pre-computation (e.g., incrementing array indices).

From what I can tell reading around I'm going to have to port this over to Visual C++ to have access to really good profiling and analysis. Looks like I'm stuck with that since it doesn't seem there's any easy tests to identify the exact reason for this behavior. Caching sounds like a good culprit.

Well, I guess I have two options, I can learn how to use profiling to troubleshoot this annoyance, and I could just move fft's on to the GPU instead of fighting the CPU for no better than 50% gain even if this did work like I imagined it might.

Bleh, I'll try to figure out why this is the way it is, and post back for who ever else that might ever run in to this and search the 'ol google, then just try this all out with shaders.

Where are the quantum computers at? I demand better. >:[

What compiler are you currently using? I believe that the profiling tools for Visual C++ are only available with the top end Team System (but if you have that, then great :) ).

I'm using GCC/G++ etc... the free stuff with Dev-C++.

I'd like to make it all work using just what I have available through opensource projects on principle for this.


(edit: I need to really think through my posts before I post, I go through like five edits within the first 10 seconds of all my posts. wow!)

if cache coherence is a problem, you could preload the cache.

also don't forget GPU readback doesn't come for free. though i hear that can be much improved with CUDA

Quote:

---

Originally Posted by since

I'm using GCC/G++ etc...

---

In that case you could use gprof for profiling.

If you're saying there's an array entry for each NxN operation, and N=128, then you're definitely killing L1 D-cache hit rates. That's 64K of data assuming only one value with no vector class overhead, and it looks like you've got two, plus other source and dest arrays which is way larger than the d-cache on modern processors.

So the biggest delay is likely the time it's taking to service an L1 miss (low tens of cycles?). There's also probably a bit of overhead in doing all of the pointer arithmetic, but that's probably able to be hidden fairly well by the compiler and is only a secondary concern.

Can you try cutting down the value of N and see if the calculation vs table performance difference changes? That would give you a hint that you're limited by cache size if the table lookups suddenly get better when N=16 or 32 - at that point they should fit in L1 if I'm doing the math correctly and your 10-20 cycle L2 access time drops to 3-4 cycles for an L1 hit.

KCfromNC,

You might have got it, I had to go all the way down to N=16 before the table lookups won out, that was doing just quick 15 second tests at N=64, 32, 16. At N=32 the CPU hit was about even between trig/tables. Well, that sucks.

This is just the base results that I have to work off of with a series of other stochastic processes, not going to work. Figures.

Alright, I might have to go an entirely different route, with hw accelleration. I need N=128 at least, I might be able to make this work with N=96 and just have it be a little 'sloppy', but with hw acceleration I might be able to get N=256 with relative ease, we'll see.

Thanks for your suggestions. I'm going to look at gprof anyway just so I can use it for other projects possibly.

Apart from any cache-related issues, the naive DFT is slower than the FFT by a factor of N / log N (i.e., it's HUGELY slower). Have you considered implementing FFT instead?

(I'm assuming you are implementing DFT based on the scant code you've posted so far, but I could be wrong)

Any chance you use the tables more than one in the loop? If you could rewrite it like this

Code:

---

float f0;
for (int k = 0; k < N/4; ++k)
for (int j = 0; j < N; ++j)
{
        f0 = fA[k] * fB[j] * (*TSIN)[k][j];
        // ...
}
for (int k = N/4; k < 2*N/4; ++k)
for (int j = 0; j < N; ++j)
{
        f0 = fA[k] * fB[j] * (*TSIN)[k][j];
        // ...
}
for (int k = 2*N/4; k < 3*N/4; ++k)
for (int j = 0; j < N; ++j)
{
        f0 = fA[k] * fB[j] * (*TSIN)[k][j];
        // ...
}
for (int k = 3*N/4; k < N; ++k)
for (int j = 0; j < N; ++j)
{
        f0 = fA[k] * fB[j] * (*TSIN)[k][j];
        // ...
}

---

And use TSIN[k][j] more than once per loop, you'd get some benefit. Of course you'd have to play with how much to divide the loop up, but hopefully you get the idea.

Also, here's a strange idea. Make the one or both of the vectors' dimensions sized at N+1. You won't use the extra entry, but it will move the data around a bit in the cache and maybe you'll have fewer conflicts. Still won't help as N gets larger, but in that case you're going to start missing in L2 as well and the penalty will get even larger.

I've implemented DCT Type-II and Type-I, as well as the DFT. What I like about the DFT is the quality of the results. I suppose the nature of the DCT and DST plays in to that, I don't understand in full yet the consequences of the Even|Real / Odd|Imaginary-ness of the DCT/DST, but I understand enough from exploring their results that it affects the how 'well' they define the spectrum components of a given audio sample. Well, I shouldn't actually say that, I'm gauging that from what I can see and the few statistics I'm performing based on the results.

One of the things that is most important in my application is resolution and not so much precision. I want to get as much information about the signal with taking a degree of hit on the precision of the results (if I have to lose something). Approaching this from a strategic perspective I'm falling towards hw accelerating the DFT, considering GPU's are a little sloppy on the quality of the floating point values in the general case, they are fast, and would perform the 'luxurious' DFT pretty damn quick regardless. If i used a 16x16 texture that's 256 samples, which is double the number of samples I was already satisfied with. Most mid-range GPU's these days have at least 8 stream proc's, the newest one's out there now are over 800 for about $200. (ATI HD5880). From general testing I can tell greater than 32bit floating point precision is not necessary, so that's another aspects in favor of GPU's, I could quadruple the amount of data I could process over four 32-bit color channels and actually pull off 1024 sample DFTs. (I'd store the results in an associated 16x16 'result' texture.) (But of course even GPU's have performance limitations and I'm doing a lot there too so... I'll have to find a balance.)

I think I'm OK with recommending like a cheap-o 9800pro $30 card and just call it a min spec and do this all with only GPU-CPU transfers as a the limit to the CPU load. Hell, maybe I can offset all of my statistics to the GPU. I think I've already convinced myself to just go a whole new route with all of this. (I have *a lot of other information to track for real-time visual models, so I need to be as strict as possible when managing what the CPU is doing.)

KCfromNC,
I have to say though there are some things I can't hw accelerate, like classes I keep trying to optimize which track and hold vertex locations (particle classes). I definitely never thought to consider the role of L1/L2 cache limits when dealing with large enough arrays/objects(?), I think I could still apply that in other areas where I'm still trying to reach for performance in having to track and manage 9k-13k+ vertices. I'm a little excited to think there's room to get a decent increase in the amount of vertices I can manage within 2-3% CPU use on a ~C2D 2.5ghz, if it turns out I am being a lot more sloppy than I realized.

Good stuff, I got more out of this thread then I thought I would, thinking this out sorta helped me rethink a few things that shoulda been more obvious to me earlier.

:]

Quote:

---

Originally Posted by since

I've implemented DCT Type-II and Type-I, as well as the DFT. What I like about the DFT is the quality of the results. I suppose the nature of the DCT and DST plays in to that, I don't understand in full yet the consequences of the Even|Real / Odd|Imaginary-ness of the DCT/DST, but I understand enough from exploring their results that it affects the how 'well' they define the spectrum components of a given audio sample. Well, I shouldn't actually say that, I'm gauging that from what I can see and the few statistics I'm performing based on the results.

---

I'm not sure if this is addressed to me, or whether you're trying to answer my question about implementing the FFT... But assuming it is, you are mistaken if you think the FFT is somehow less precise than the DFT. The FFT is what is used in ALL production signal processing applications, and I do mean all.

Speaking to why the Fourier transform involves complex numbers, while the cosine and sine transforms do not, this is because the Fourier transform determines not only the magnitude of a particular frequency but also its phase. A wave of arbitrary phase can be expressed as the sum of a cosine and a sine wave. The complex value of the Fourier transform is just a way of representing how much of the wave is cosine and how much of it is sine -- in other words, it describes the phase.

The DCT and DFT produce purely real output because they pay no attention to phase. This results in a loss (or more accurately, an obfuscation) of information, because frequencies in the input which are not phase matched to the basis functions will appear to have magnitudes that are less than the true magnitude. But for many application (JPEG, for instance) this is not so important, since the only requirement is that the original signal be somehow reconstructible from the transformed signal, and that is always possible. These sorts of transforms are just vector projections, and given a complete basis, are always reversible.

Brewbuck,

I do understand that the FFT is used in all production applications, though I can't say anything about their performance. I've looked over the list of FFT algorithms on WIKI and tried to find websites which explained them more in depth so I could implement them as an educational exercise, but that kind of material is sparse for most of the algorithms. (I found a few very good PDF's but, I'm putting them to the side for now.)

I'm not saying I won't use an FFT algorithm in the end, if I do still... I think I'll implement it on the GPU instead of the CPU.

I wasn't making any comments on the FFT's, if I were I would have specified that. I strictly have implemented and can only speak (limited) about DCT's and DFT's at the moment, so I wouldn't say anything about the FFT's with confidence until I explore them. (sigh, I still have a lot more to go through on the theory side actually, to have a more intuitive understanding.)

I also don't have the time to evaluate every form of FFT (I might look at FFTW) conveniently as far as I know right now. I still feel I could sooner benefit even more greatly from a parallel processing model over any CPU centric optimizations as far as the bottom line is concerned (I'm sure a few of the FFT's could be easily adapted to a parallel processing model, hopefully). So I'm still going to go for getting the traditional DFT in to shaders first and then work my way in to FFT's after that.

I'm open to any suggestions if you have experience implementing FFT's, any problems I'm about to run in to I'm sure you might have already dealt with. It seems like most people just go with existing libraries, which makes sense but since I'm working on shaders instead that changes things a bit.