Showing posts with label string. Show all posts
Showing posts with label string. Show all posts

Saturday, 12 March 2022

Using Const Char* in Template

Compile Time Template Strings.... Yeah, these are a thing and I'm going to show you a live example of how to do them.  First lets take a moment to just understand what we want in some C++ pseudo code.

template<typename T>
T Square(const T value)
{
   return value * value;
}

const auto result = Square<int>(2);

const auto result = Square<double>(2.42);

In a template like this we can see this requires a number and more advanced writers might use SFINAE and type traits to ensure that the type is an arithmetic type, this would stop us doing something like...

const auto result = Square<"Hello">(2);

In this case we can not even compile, not because "Hello" is not operable with the multiplication, but that it's not that, the issue is that a const char* isn't allowed in the template itself.  You can't define a typename as const char*... Or can you?

Well, it seems you can in C++20.  The idea I had was to accept the template but treat it like a decaying length, copying the buffer in the template each step.  How could I do this?  Well, I need to compare the template somehow and determine the length of "Hello"... The buffer containing the data "Hello\0" itself is there in the code, what I needed was to think about how to treat that as type 6, the length...

The spaceship operator is what sprang to mind, but then I had the issue that the comparison result type wasn't known.... At least I don't know it, I don't know what string literal maybe being passed in, how to know it?  Well I didn't need to, I just return auto!

Here is the key code....  

  template<std::size_t Length>
  struct TemplateString
  {
    // Constructor is constexpr and simply copies the payload text
    // into the member data setup
    constexpr TemplateString(const char(&pPayloadText)[Length + 1])
    {
      std::copy_n(pPayloadText, Length+1, mText);
    }
    
    auto operator<=>(const TemplateString&) const = default;
    
    // Default is just an empty buffer of the Length+1
    char mText[Length+1] = {};
  };
  
  // Make decaying the template Length possible
  template<std::size_t Length>
  TemplateString(const char(&str)[Length])->TemplateString<Length-1>;


The template string is simply copying the buffer given locally, and the unwinding is stopped when the template length is met in the comparator.  I think this is a little strange, I may even be wrong (probably am) in explaining how this unrolling works.

However, what use do I have for this?

Well, my main use is in parameterising on the template the NAME of a thing... I have long seen code where the onus is on the engineer to put some static constant string into their derived class to allow some other feature to know what your class is called, or what it does.

Systems, Events, Services... These sort of things, general things that need a name for us mere humans all introduce this pattern of:

Base Class --> Derived Class :: sName

Where this sName is brittle, it can be forgotten, it can be mangled, it can be copy I paste... All sorts of issues with it.  I personally have my statemachine code up on github and I use an event within that, which could sorely use this very string trick... so I will be using it.

Lets take a look at the code in action on CompilerExplorer here.

And you can get hold of my personal example on github here.

As ever, if you liked this, subscribe on YouTube to let me know, comment below and if you use this trick feel free to buy me a coffee with the tip jar up top of this page.

Thursday, 30 November 2017

C++ : Trust the STL

One sore lesson to teach some developers is when to trust the compiler, once you've gotten that across you have to start teaching folks to stop re-inventing the wheel.

If someone has already implemented a file handler, or a serial port abstraction, or a wrapper for some obscure feature, you need to evaluate that offering...

To evaluate whether a library is worth using, firstly see if it works, then see how many folks actually use it, the more that use it then the more likely bugs will be flushed out and the whole thing has been tested.

Leveraging this kind of mature code within your projects assists in bootstrapping the startup phase of new projects.

Boost is a note worthy example of what I'm talking about here, many software shops (at least the ones I know) resist using open-source or third party libraries, they prefer to stick to in-house developed niche implementations until the very last moment, this of course slows development and completely symies innovation.

Boost however is one step further than the problem I'm going to tackle today... The Standard Template Library...

The STL is often commented upon negatively, this is despite it being a hugely available resource, vastly and deeply tested throughout and constantly incorporating new innovations.  Whole books have been written on the topic, and yet one can still find projects and individuals resisting using the STL.

STL nay-sayers will quote "no need for an STL requirement", "uses less memory than an STL implementation" or "faster than the STL"...

The problem with this attitude is, are such attitudes going to sufficiently tackle testing of their bespoke solution, is that bespoke solution going to be as robust or as easily maintained as something using the STL?

Probably not, and this is a hard one for die hard "purist" developers to swallow, we want to write all our own code, we want to be gods in our domain, the trouble is for the vast number of us, god has already been there and he wrote a decent enough library to do the task we need doing... So leverage this!

I came across one such niche item the other day, with an algorithm to see if a string starts with...

They hadn't used boost, or the STL, to do the searching, yet perversely had used an std::string... Their code, looked a little like this:

const bool StartsWith(
const std::string& p_Text,
const std::string& p_Pattern)
{
bool l_result(true);

if ( p_Text.length() >= p_Pattern.length() )
{
for (unsigned int i(0);
i < p_Pattern.length();
++i)
{
if ( p_Text[i] != p_Pattern[i] )
{
l_result = false;
break;
}
}
}
else
{
l_result = false;
}

return l_result;
}

It is fairly logical code, they're looking at the length of the presented parameters, to avoid looping when not required, then they only loop from the start and only return a fail when the character is a miss-match, looking at this with programming eyes from 1996, I'd say this is fine.

Looking with eyes well aware of the STL, I cringe a little, and replaced this whole function like this...

const bool StartsWith(
const std::string& p_Text,
const std::string& p_Pattern)
{
return (p_Text.find(p_Pattern) == 0);
}

One line, of very much more maintainable, vastly more readable and easy to comprehend code...

The developer of the original however was not happy... "you're wasting resources, this will find any instance and tell you the input".... he's right it will, but the STL will still be faster than his code.

I demonstrated this by plugging both into CompilerExplorer... He still refused to listen.

Therefore, I've written this little helper project, to run the two functions side by side, threaded three tests, looking for the match, a long match and a negative match at the start of the string (Code on Github).


The results of this are interesting, you see the project itself favours cases where it's highly likely the string being searched for is present and therefore we don't need to worry too much about the odd test not finding a match taking longer... This is exactly the behaviour seen in the STL based find example.


The Short search time, for the same data, on the same processor went from 28358 microseconds to just 5234... That's about 81% faster.  The longer search is more stark, falling from 185966 microseconds to just 6884, just over 96% faster!

The rub is the negative case took longer, rising from 19765 in the hand-crafted search to 25695, just over 30% slower.  Some of this increase can be explained perhaps by the hand-crafted version using the lengths to quickly skip too short an input, otherwise it is simply that the STL find has to iterate over the whole string when no match is found.  A hybrid to not perform the find at all, when there is insufficient data maybe in order; however this may add to our maintenance burden and lower code clarity, swings and roundabouts.

However, clearly in the case of this project, dismissing the STL resulted in slower code, we have a system propensity for matches, they're quite short, and all target platforms have the STL built in, use it.

Never be affraid to ask questions of what you're working with, ever.

Monday, 20 January 2014

C++ Integer to std::string conversion speed

There is often a lot of discussion about the most efficient way to convert things in C++, personally I like the boost::lexical_cast, I find it gives clear and readable code; very important in the systems I write, especially for maintenance and up keep.

However, many assume it to be slow, indeed most authors on the topic turn almost immediately to C for the fastest way to convert integers to strings, and unfortunately I find the same is true, even with std::string and std::ostringstream features the old sprintf tends to be faster.

But, crippling many users of std::string is their lack of understanding of that standard library staple class, so here is my little investigation into the speed of conversion, using a mix of C and standard C++, to give you a good idea of how fast things can be, and how to use your standard class and its memory to best effect.

The first trick you will see in this is the use of the std::string as a memory buffer, you can do this by declaring your standard string, then resizing it...

std::string MyName;
MyName.resize(12);

The memory location now at &MyName[0] points to 12 empty characters for you to use just as you would a char* or &char[], useful to stop using uncontrolled char* buffers left right and center, and perhaps the least used "tip" I can give when using std::string.

So, what conversions do we have?...

class Conversions
{
    public:

        static const std::string IntToString(const int& p_Input);

        static const std::string IntToString2(const int& p_Input);

        static const std::string IntToString3(const int& p_Input);

        static const char* IntToString4(const int& p_Input);

        static const void TestConversions (const int& p_Cycles);

};

The first three are going to be using whatever code to always give a pre-allocated std::string, the fourth conversion is going to return a raw char*, so the programmer has to delete the result etc, or rick a memory leak.

I still want that fourth result to be a std::string however, and I'm not going to worry about the leaking memory, so though the function performs a new[] I will not perform a delete[], but simply will assign the char* to a new std::string upon return.  Making the timings taken fairer.

So, lets look at the program code for each of the functions, and the timing in the test function.  I'm going to use boost::posix_time for the timings here:

const std::string Conversions::IntToString(const int& p_Input)
{
    std::string l_buffer;
    l_buffer.resize(33);
    sprintf(&l_buffer[0], "%d", p_Input);
    return l_buffer;
}

Above we can see the first function, using our string resizing tip, we resize the string as a buffer to take up to 33 characters (the maximum size for a 32bit integer is 33 characters) and then we use the old fashioned sprintf from the cstdlib header.  Many claim this to be the fastest, the defacto conversion, even more so than using itoa.

const std::string Conversions::IntToString2(const int& p_Input)
{
    std::ostringstream l_oss;
    l_oss << p_Input;
    return l_oss.str();
}

Next is the standard library way of working, we create a new ostringstream and stream the integer into it, then return the std::string from the stream.  I believe this to be pretty slow, my mind tells me that the creation of the stream and then the extraction of the result is going to be slow; but we shall see in a moment.

const std::string Conversions::IntToString3(const int& p_Input)
{
    char l_buffer[33];
    sprintf(l_buffer, "%d", p_Input);
    return std::string (l_buffer);
}

Next we have another use of sprintf, however, this time we're not resizing a string natively, we're creating a character string and then casting it back as a result.  I think this may be the fastest, but again we shall see.

const char* Conversions::IntToString4(const int& p_Input)
{
    char* l_buffer = new char[33];
    sprintf(l_buffer, "%d", p_Input);
    return l_buffer;
}

Finally, very similar to the third test, this conversion creates a new character array pointer as the buffer, and then uses sprintf.  This is going to leak memory if we don't delete[], but I'm ignoring that for now and just testing the speed.

Now onto the conversion test function, the basic layout is, take the start time before the conversion, call the conversion a lot of times assigning the result to a std::string locally, and then take the time after and output the difference in milliseconds...

Now, the speed of this code in C++ is going to be fast in all cases, so we need enough sample calls to get a reading... I'm settling on 30 million calls, 30000000.

const void Conversions::TestConversions (const int& p_Cycles)
{
    // Test 1
    std::cout << "Test 1...";
    boost::posix_time::ptime l_end;
    boost::posix_time::ptime l_start (boost::posix_time::second_clock::local_time());
    std::string l_result;
    for (int i = 0; i < p_Cycles; ++i)
    {
        l_result = IntToString(i);
    }
    l_end = boost::posix_time::second_clock::local_time();
    boost::posix_time::time_duration l_diff = l_end - l_start;
    std::cout << l_diff.total_milliseconds() << std::endl;

    // Test 2
    std::cout << "Test 2...";
    l_start = boost::posix_time::second_clock::local_time();
    for (int i = 0; i < p_Cycles; ++i)
    {
        l_result = IntToString2(i);
    }
    l_end = boost::posix_time::second_clock::local_time();
    l_diff = l_end - l_start;
    std::cout << l_diff.total_milliseconds() << std::endl;

    // Test 3
    std::cout << "Test 3...";
    l_start = boost::posix_time::second_clock::local_time();
    for (int i = 0; i < p_Cycles; ++i)
    {
        l_result = IntToString3(i);
    }
    l_end = boost::posix_time::second_clock::local_time();
    l_diff = l_end - l_start;
    std::cout << l_diff.total_milliseconds() << std::endl;

    // Test 4
    std::cout << "Test 4...";
    l_start = boost::posix_time::second_clock::local_time();
    for (int i = 0; i < p_Cycles; ++i)
    {
        l_result = IntToString4(i);
    }
    l_end = boost::posix_time::second_clock::local_time();
    l_diff = l_end - l_start;
    std::cout << l_diff.total_milliseconds() << std::endl;
}

Lets see what our output is:

Test1...6000
Test2...17000
Test3...5000
Test4...6000

Immediately we can see my hunch about using the string stream is correct, its very much slower, more than twice as slow.

Surprisingly, at least to most readers - one hopes - we can see that the string::resize and use of sprintf is very close to the other uses of sprintf.

Since sprintf should be taking a constant amount of time what we've timed in tests 1, 3 and 4 is the speed of our memory management, how quickly has the function made the result available.

Some readers maybe screaming at me to use itoa, and one could do that with a char buffer, or even a resized string, thus:

std::string buffer;
buffer.resize(33);
itoa (&buffer[0], p_Input, 10);

However, itoa is not a standard function and some compilers don't supply it, therefore you must generally always use the lowest common denominator and sprintf is just that.

There is also one last avenue, the lexical cast...

// Test 5
std::cout << "Test 5...";
l_start = boost::posix_time::second_clock::local_time();
for (int i = 0; i < p_Cycles; ++i)
{
    l_result = boost::lexical_cast<int>(i);
}
l_end = boost::posix_time::second_clock::local_time();
l_diff = l_end - l_start;
std::cout << l_diff.total_milliseconds() << std::endl;

Now, this approach should take into account the "bad_lexical_cast" exception, but exception handling is slow so we're ignoring that at this juncture.  And assuming we have a known data source (int i) which we have in a valid range.

Our test results how are similar for the original calls...

Test 1...6000
Test 2...17000
Test 3...5000
Test 4...5850

The new fifth test...

Test 5...1000

This is very much quicker than any of the other solutions proposed...

So, there you go...

#include <boost/lexical_cast.hpp>
#include <boost/date_time/local_time/local_time.hpp>
#include <string>
#include <iostream>

int main ()
{
// Test 5
std::cout << "Test 5...";
boost::posix_time::ptime l_start =
boost::posix_time::second_clock::local_time();
for (int i = 0; i < p_Cycles; ++i)
{
l_result = boost::lexical_cast<int>(i);
}
boost::posix_time::ptime l_end = 
boost::posix_time::second_clock::local_time();
boost::posix_time::time_duration l_diff = l_end - l_start;
std::cout << l_diff.total_milliseconds() << std::endl;

return 0;
}

Use lexical cast...

And about the exception handling, be smart the speed of this code is not affected by making the function throw the exception up, or by making the whole loop handle the exception once, be smart... and stop mucking about with conversions in C, you're only fooling yourself they're faster than other options.