4

I have a string like the following:

{A}jahshs{b}jwuw{c}wuqjwhaha{d}{e}{f}jsj{g}

And I need to replace every {x} with a different string. The problem comes because this process will be repeated around 1000 times/second, so I need a optimized/fast way to do it.

Any idea? Boost replace? Boost format? Etc..

Improve this question
3
  • 1
    std::string::replace, measure, and demonstrate that it's not fast enough? Commented Mar 22, 2014 at 0:02
  • But I should call replace for every {x} in the string, around 10. So 10x1000 replaces per second. Commented Mar 22, 2014 at 0:07
  • Nothing will replace making tests and measurements on your end. There are so many variables. If you write up some code and it is still slower than you expect, we can at least look at your code and discuss. Commented Mar 22, 2014 at 0:13

1 Answer 1

Reset to default
0

  1. preallocate all buffers

    ....

  2. profit

Oh, and don't spam. Sample code in 5 10 minutes.

Okay here goes: also Live On Coliru

#include <string> #include <sstream> #include <boost/utility/string_ref.hpp> template <typename Range> int expand(Range const& /*key*/) { return rand()%42; // todo lookup value with key (be sure to stay lean here) } #include <iostream> int main() { static const std::string msg_template = "{A}jahshs{b}jwuw{c}wuqjwhaha{d}{e}{f}jsj{g}\n"; std::ostringstream builder; builder.str().reserve(1024); // reserve ample room, not crucial since we reuse it anyways for (size_t iterations = 1ul << 14; iterations; --iterations) { builder.str(""); std::ostreambuf_iterator<char> out(builder); for(auto f(msg_template.begin()), l(msg_template.end()); f != l;) { switch(*f) { case '{' : { auto s = ++f; size_t n = 0; while (f!=l && *f != '}') ++f, ++n; // key is [s,f] now builder << expand(boost::string_ref(&*s, n)); if (f!=l) ++f; // skip '}' } break; default: *out++ = *f++; } } // to make it slow, uncomment: // std::cout << builder.str(); } }

This runs in ~0.239s on my system. Thats about 68k expansions/second. Oops. In release build it does 4 million expansions/second. On Coliru it reaches almost 1 million expansions/second.

Room for improvement:

  • you can prevalidate the input
  • if you know the parameter keys are always 1 letter, then you can simply by replacing the string_ref with the char, and by not looping for the '}'.
  • you can precalculate the indicecs of arguments and jump ahead. The benefit here is not so certain (sequential memory access is very good on some processors and the naive approach may be faster)
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Each { x } is a macro name, and the content to be replaced could vary, besides the main string could vary too. So, is a kind of macro expander.
Yes? Did you run the code? Is there anything you can't figure out? Did you so the the expand function? As you'll note, it "is a kind of macro expander". I made doubly sure you can return any thing that is IO streamable. Maybe this 2-line edit will help?
This can be made more efficient easily by making insert_expanded take the builder stream. An example that mimicks mailmerge: coliru.stacked-crooked.com/a/cde6e91f3d898888
Oh, and with randomized templates ("besides the main string could vary too"). Last but not least: here is an old answer of mine implementing a yet-more-versatile macro expansion system with Boost Spirit (namely, nested macros, escaped macro characters, recursive evaluation). Cheers
Fixed the benchmark. Now doing 4 Mio/s expansions on my box, ~1Mio/s on Coliru
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.