FAST string search in a small dataset , ideas?
Author
Hello,
I've been making an app whose current bottleneck is string search in a dataset, (called about several thousand times per frame), and I can't decide how to make it faster.
The dataset that needs to be searched is very small, about 3-7 elements, but still the time that is consumed in iterating over the (std::)vector & comparing is very much (~5-7ms in debug mode each frame, ~50 fps).
The datatype cannot be changed (I want the changes to be transparent in the app), so I'm confined to std::string / const char *
Most algorithms that I've read about are for large datasets so they probably won't help. I can preprocess the dataset, since it's not changed in the main loop, but I still can't think of an extremely fast search method (time is also pressuring me much). Any ideas anyone??
Thanks in advance.
Why do people test performance in debug mode?
Make a release build, then see if it's a problem. Stuff in debug mode runs 2-200 times slower than in release - the ratio isn't linear.
Make a release build, then see if it's a problem. Stuff in debug mode runs 2-200 times slower than in release - the ratio isn't linear.
Author
It is still a problem (w/ release) but a more minor one (1ms in 14ms of each frame time). I (and I guess many) just test in debug because the app takes too long to build/link in release, especially if I change inline code.
Author
for uniform name passing in shaders, it sounds lame but it's very convenient.. :-)
The shader manager gets the string & the data, checks the active shader's stored uniforms to find the appropriate (hence the string comparison), calls the uniform's appropriate virtual (yes I know, another hit) function, glUniform1iv,glUniform2iv or whatever.. thanks both of you for the quick replies!
The shader manager gets the string & the data, checks the active shader's stored uniforms to find the appropriate (hence the string comparison), calls the uniform's appropriate virtual (yes I know, another hit) function, glUniform1iv,glUniform2iv or whatever.. thanks both of you for the quick replies!
This is going to sound very ambiguous and maybe not helpful at all, but jpetrie said something in these forums once that really stuck with me: "If you really want to be efficient, try to figure out ways you can do less rather than do more faster." Loosely translated: optimize your methods before looking at your code If you're doing that many string lookups each frame and it's your bottleneck, I'd say you need to be doing fewer string lookups.
Or none at all. Is there a particular reason you can't use pointers instead of names? They don't even have to be real pointers, but rather index values that point to an element in an array. This is what I do with resource managers: names (typically file names) are passed to the manager, which loads the resources, ups the reference count, and passes out a pointer (array index). When the resource is accessed, the recipient passes the index back to the resource manager, which then hands out the actual object data.
It's not the most efficient means, but it's very fast, and I can do it with any type of resource. If you want to be faster, you can pass pointers to actual data, rather than using the index as a middleman.
Or none at all. Is there a particular reason you can't use pointers instead of names? They don't even have to be real pointers, but rather index values that point to an element in an array. This is what I do with resource managers: names (typically file names) are passed to the manager, which loads the resources, ups the reference count, and passes out a pointer (array index). When the resource is accessed, the recipient passes the index back to the resource manager, which then hands out the actual object data.
It's not the most efficient means, but it's very fast, and I can do it with any type of resource. If you want to be faster, you can pass pointers to actual data, rather than using the index as a middleman.
What he said. Nobody in their right mind would use an implementation that relies on thousands of string lookups per frame. Your optimization needs to happen at a higher level than what you're looking for. Do them once, store a handle to whatever you looked up or something.
Quote:Original post by DrEvil
Do them once, store a handle to whatever you looked up or something.
QFE.
Author
I guess you are right, I checked more carefully the release build stats, & it showed a whopping 20% percent of the frame time searching & setting the uniforms. So I guess I'll eliminate the search completely..
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
