Speeding up lookup table performance
-
Hey Guys, I have a project I'm using programmed in Visual C++ 6. It's a simulation package that needs to use double precision variables. Because it is a non linear simulation package I need to store a lot of data as Global variables. My question is how do I speed up access to these variables. Let me illustrate with an example. I came up with my own sqrt function. For my first cut for estimating the mantissa I used a polynomial curve fit and it blew the standard sqrt function away. Unfortunately the accuracy was awful. So I figured I would be clever and I would implement a global lookup table, with regular divisions. I looked at the code and I figured man this is going to be good. Well it was dog slow. So it dawned on me that using globals while good for code management is not good for speed. I'm just wandering does anyone have any suggestions. Thanks in advance. Danny
-
Hey Guys, I have a project I'm using programmed in Visual C++ 6. It's a simulation package that needs to use double precision variables. Because it is a non linear simulation package I need to store a lot of data as Global variables. My question is how do I speed up access to these variables. Let me illustrate with an example. I came up with my own sqrt function. For my first cut for estimating the mantissa I used a polynomial curve fit and it blew the standard sqrt function away. Unfortunately the accuracy was awful. So I figured I would be clever and I would implement a global lookup table, with regular divisions. I looked at the code and I figured man this is going to be good. Well it was dog slow. So it dawned on me that using globals while good for code management is not good for speed. I'm just wandering does anyone have any suggestions. Thanks in advance. Danny
Danny Nowlan wrote:
Because it is a non linear simulation package I need to store a lot of data as Global variables
I'm not sure that necessarily follows...but anyway.
Danny Nowlan wrote:
So I figured I would be clever and I would implement a global lookup table, with regular divisions
Why regular intervals? You want to vary the intervals with the rate of change of the curve, so you're getting a good approximation to the curve with a set of lines. I've written linear interpolating table lookups for embedded systems - we generally do a binary search over the independent variable to find the points that surround the input, then linearly interpolate between those two. One optimisation that often works is to remember the results of the last lookup (the indices of the two points surrounding the last input) - our systems vary slowly, so the current input often falls in the same range as the last input.
Danny Nowlan wrote:
So it dawned on me that using globals while good for code management is not good for speed
Wouldn't have thought the global-ness (or otherwise) of variables would impact the speed of using/writing them. I avoid global variables 'cause they make it too easy to design systems with high coupling between modules - that's bad.
-
Hey Guys, I have a project I'm using programmed in Visual C++ 6. It's a simulation package that needs to use double precision variables. Because it is a non linear simulation package I need to store a lot of data as Global variables. My question is how do I speed up access to these variables. Let me illustrate with an example. I came up with my own sqrt function. For my first cut for estimating the mantissa I used a polynomial curve fit and it blew the standard sqrt function away. Unfortunately the accuracy was awful. So I figured I would be clever and I would implement a global lookup table, with regular divisions. I looked at the code and I figured man this is going to be good. Well it was dog slow. So it dawned on me that using globals while good for code management is not good for speed. I'm just wandering does anyone have any suggestions. Thanks in advance. Danny
stdext::hash_map[^]can give you better performance than std::map. std::vector (sorted) also is an option. But map or hash_map will consume more memory than std::vector. If your table is not too big, it's better to implement using global arrays where you can access in constant time ( O(1) ). Just google, you can see lot of discussion around this topic.
-Sarath. "Great hopes make everything great possible" - Benjamin Franklin
My blog - Sharing My Thoughts
-
Hey Guys, I have a project I'm using programmed in Visual C++ 6. It's a simulation package that needs to use double precision variables. Because it is a non linear simulation package I need to store a lot of data as Global variables. My question is how do I speed up access to these variables. Let me illustrate with an example. I came up with my own sqrt function. For my first cut for estimating the mantissa I used a polynomial curve fit and it blew the standard sqrt function away. Unfortunately the accuracy was awful. So I figured I would be clever and I would implement a global lookup table, with regular divisions. I looked at the code and I figured man this is going to be good. Well it was dog slow. So it dawned on me that using globals while good for code management is not good for speed. I'm just wandering does anyone have any suggestions. Thanks in advance. Danny
Hi, the problem with global data is every one can access them, which also means the compiler has to allow for data changes all the time, so the data needs to be reloaded into registers/accumulators all the time. One way to improve this is to use local pointers to point into your global arrays. So for each global array you are interested in, create a local (and constant) pointer that points at it, then keep using the local pointers. I have been designing two floating-point packages in a previous life, and I did study quite a lot of existing ones. I was very much surprised by the amount of code and complexity they were willing to add in order to shave off a few percents of execution time. So I doubt very much you would come up with something revolutionary, I would rather not trust your initial measurements; blowing away the current implementation by something that has awful accuracy is no good: the standard library has to be accurate up to 1 or 2 of the lowest bits. Of course, if your applications don't need such accuracy, there are certainly faster algorithms to get that. But don't let me discourage you, when and if you really get good results, I hope we will all hear from you. :)
Luc Pattyn [Forum Guidelines] [My Articles]
I use ListBoxes for line-oriented text, and PictureBoxes for pictures, not drawings.