Sign in to follow this  

FAST string search in a small dataset , ideas?

This topic is 3668 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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..

Share this post


Link to post
Share on other sites

This topic is 3668 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this