C++ compile time function execution

Question

I have string tags in my code that are converted to numbers and used to search values in a tag-value structure.

I have something like this:

void foo()
{
    type value = search("SomeTag");
}

Where search is defined like this:

type search(const char* tag)
{
    return internal_search(toNumber(tag));
}

Because all the time tag is constant at compile time I want to remove the call that converts the tag to a number from search function. I know it is possible to execute some simple functions at compile time using templates (http://en.wikipedia.org/wiki/Compile_time_function_execution), but I don't know exactly how to iterate through a null terminated string and keep intermediate values in the template. Can you give a simple sample that iterates a null terminated string and adds the chars in a public variable please?

As an alternative, maybe toNumber could keep a map of all the tags that it has seen, and their numerical value, so that you only have to pay the conversion cost once per tag? It's not as efficient as using the template language to do the evaluation at compile time, but I would bet that the code will be a lot more readable and maintainable that way. — aroth
– aroth, Commented May 3, 2011 at 12:33
@aroth I think the toNumber function is faster than the search, even if I would use a log2 search. — Mircea Ispas
– Mircea Ispas, Commented May 3, 2011 at 12:34
@sbi: You sort of can; take a look at boost::mpl::string. But you have to write 'all ','your',' str','ings' like this (taking advantage of the fact that a char can actually be 4 characters long). — Pedro d'Aquino
– Pedro d'Aquino, Commented May 3, 2011 at 12:45
I see, they aren't actually numeric strings. Why not use the preprocessor and a common header file? #define TAG_SPEED 12414121 You could generate this file directly from the DB. — edA-qa mort-ora-y
– edA-qa mort-ora-y, Commented May 3, 2011 at 13:47

ildjarn · Accepted Answer · 2016-03-18 05:08:25Z

It sounds like what you want is Boost.MPL's boost::mpl::string. It would be more-or-less trivial to write a metafunction to convert an mpl::string to an integral type at compile time using mpl::fold (or fail to compile if the string literal does not represent a valid integral value).

EDIT:

I'm not entirely sure what you're looking for, so here is effectively two different answers depending on interpretation:

IF what you're looking for is compile-time string-to-integral-value conversion (e.g. so "425897" could be recognized as the integral constant 425897 at compile time), then one can use Boost.MPL as I suggested:

#include <cstddef>
#include <boost/type_traits/is_integral.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/is_signed.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/char.hpp>
#include <boost/mpl/contains.hpp>
#include <boost/mpl/end.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/find_if.hpp>
#include <boost/mpl/fold.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/identity.hpp>
#include <boost/mpl/integral_c.hpp>
#include <boost/mpl/minus.hpp>
#include <boost/mpl/negate.hpp>
#include <boost/mpl/next.hpp>
#include <boost/mpl/not.hpp>
#include <boost/mpl/pair.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/pop_front.hpp>
#include <boost/mpl/push_back.hpp>
#include <boost/mpl/reverse_fold.hpp>
#include <boost/mpl/size_t.hpp>
#include <boost/mpl/string.hpp>
#include <boost/mpl/times.hpp>
#include <boost/mpl/vector.hpp>

namespace details
{
    namespace mpl = boost::mpl;

    typedef mpl::vector10<
        mpl::char_<'0'>, mpl::char_<'1'>, mpl::char_<'2'>, mpl::char_<'3'>,
        mpl::char_<'4'>, mpl::char_<'5'>, mpl::char_<'6'>, mpl::char_<'7'>,
        mpl::char_<'8'>, mpl::char_<'9'>
    > valid_chars_t;

    template<typename IntegralT, typename PowerT>
    struct power_of_10;

    template<typename IntegralT, std::size_t Power>
    struct power_of_10<IntegralT, mpl::size_t<Power> > : mpl::times<
        power_of_10<IntegralT, mpl::size_t<Power - 1u> >,
        mpl::integral_c<IntegralT, 10>
    > { };

    template<typename IntegralT>
    struct power_of_10<IntegralT, mpl::size_t<1u> >
        : mpl::integral_c<IntegralT, 10>
    { };

    template<typename IntegralT>
    struct power_of_10<IntegralT, mpl::size_t<0u> >
        : mpl::integral_c<IntegralT, 1>
    { };

    template<typename IntegralT, typename StringT>
    struct is_negative : mpl::and_<
        boost::is_signed<IntegralT>,
        boost::is_same<
            typename mpl::front<StringT>::type,
            mpl::char_<'-'>
        >
    > { };

    template<typename IntegralT, typename StringT>
    struct extract_actual_string : mpl::eval_if<
        is_negative<IntegralT, StringT>,
        mpl::pop_front<StringT>,
        mpl::identity<StringT>
    > { };

    template<typename ExtractedStringT>
    struct check_valid_characters : boost::is_same<
        typename mpl::find_if<
            ExtractedStringT,
            mpl::not_<mpl::contains<valid_chars_t, mpl::_> >
        >::type,
        typename mpl::end<ExtractedStringT>::type
    > { };

    template<typename ExtractedStringT>
    struct pair_digit_with_power : mpl::first<
        typename mpl::reverse_fold<
            ExtractedStringT,
            mpl::pair<mpl::vector0<>, mpl::size_t<0> >,
            mpl::pair<
                mpl::push_back<
                    mpl::first<mpl::_1>,
                    mpl::pair<mpl::_2, mpl::second<mpl::_1> >
                >,
                mpl::next<mpl::second<mpl::_1> >
            >
        >::type
    > { };

    template<typename IntegralT, typename ExtractedStringT>
    struct accumulate_digits : mpl::fold<
        typename pair_digit_with_power<ExtractedStringT>::type,
        mpl::integral_c<IntegralT, 0>,
        mpl::plus<
            mpl::_1,
            mpl::times<
                mpl::minus<mpl::first<mpl::_2>, mpl::char_<'0'> >,
                power_of_10<IntegralT, mpl::second<mpl::_2> >
            >
        >
    > { };

    template<typename IntegralT, typename StringT>
    class string_to_integral_impl
    {
        BOOST_MPL_ASSERT((boost::is_integral<IntegralT>));

        typedef typename extract_actual_string<
            IntegralT,
            StringT
        >::type ExtractedStringT;
        BOOST_MPL_ASSERT((check_valid_characters<ExtractedStringT>));

        typedef typename accumulate_digits<
            IntegralT,
            ExtractedStringT
        >::type ValueT;

    public:
        typedef typename mpl::eval_if<
            is_negative<IntegralT, StringT>,
            mpl::negate<ValueT>,
            mpl::identity<ValueT>
        >::type type;
    };
}

template<typename IntegralT, typename StringT>
struct string_to_integral2
    : details::string_to_integral_impl<IntegralT, StringT>::type
{ };

template<typename IntegralT, int C0, int C1 = 0, int C2 = 0,
    int C3 = 0, int C4 = 0, int C5 = 0, int C6 = 0, int C7 = 0>
struct string_to_integral : string_to_integral2<
    IntegralT,
    boost::mpl::string<C0, C1, C2, C3, C4, C5, C6, C7>
> { };

Usage would look like:

type search(int tag) { /*impl... */ }

void foo()
{
    type value = search(string_to_integral<int, '4258','97'>::value);
}

// OR, if you still want to maintain the separation
// between `search` and `internal_search`

type internal_search(int tag) { /*impl... */ }

template<typename TagStringT>
type search()
{
    return internal_search(string_to_integral2<int, TagStringT>::value);
}

void foo()
{
    typedef boost::mpl::string<'4258','97'> tag_t;
    type value = search<tag_t>();
}

Support for negative numbers is implemented, support for overflow detection is not (but your compiler will probably give a warning).

IF what you're looking for is compile-time string-to-integral-value mapping (e.g. so "SomeTag" could be recognized as the integral constant 425897 at compile time), then Boost.MPL still solves the problem, but all string-to-integral-value mappings must be known at compile time and registered centrally:

#include <boost/type_traits/is_same.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/integral_c.hpp>
#include <boost/mpl/map.hpp>
#include <boost/mpl/pair.hpp>
#include <boost/mpl/string.hpp>
#include <boost/mpl/void.hpp>

namespace details
{
    namespace mpl = boost::mpl;

    typedef mpl::map<
        mpl::pair<
            mpl::string<'Some','Tag'>,
            mpl::integral_c<int, 425897>
        >,
        mpl::pair<
            mpl::string<'Some','Othe','rTag'>,
            mpl::integral_c<int, -87>
        >,
        mpl::pair<
            mpl::string<'AnUn','sign','edTa','g'>,
            mpl::integral_c<unsigned, 7u>
        >
    > mappings_t;

    template<typename StringT>
    struct map_string_impl
    {
        typedef typename mpl::at<
            mappings_t,
            StringT
        >::type type;
        BOOST_MPL_ASSERT_NOT((boost::is_same<type, mpl::void_>));
    };
}

template<typename StringT>
struct map_string2 : details::map_string_impl<StringT>::type { };

template<int C0, int C1 = 0, int C2 = 0, int C3 = 0,
    int C4 = 0, int C5 = 0, int C6 = 0, int C7 = 0>
struct map_string : map_string2<
    boost::mpl::string<C0, C1, C2, C3, C4, C5, C6, C7>
> { };

Usage would look like:

type search(int tag) { /*impl... */ }

void foo()
{
    type value = search(map_string<'Some','Tag'>::value);
}

// OR, if you still want to maintain the separation
// between `search` and `internal_search`

type internal_search(int tag) { /*impl... */ }

template<typename TagStringT>
type search()
{
    return internal_search(map_string2<TagStringT>::value);
}

void foo()
{
    typedef boost::mpl::string<'Some','Tag'> tag_t;
    type value = search<tag_t>();
}

mappings_t is what needs to be edited to maintain your string-to-integral-value mappings, and, as demonstrated, the mapped integral values need not all be of the same underlying type.

In either case, because the mapping is done at compile time, search/internal_search (the one with the real implementation taking an int) could be made to take the integral value as a template parameter rather than as a function parameter if doing so makes sense for its implementation.

Hopefully this answers your questions.

I would not go as far as saying that it is trivial (at least not for me), but it can be done.
Please give me an implementation. This is the most voted answer, but I think it's not possible to do this, as others said. I'll up vote when I'll have a full answer.
@Felics : Edited with full implementations. I gave two approaches, since it's not clear to me what you're really looking for...
I need to map a string to an int something like "SomeTag" to 1234567 and you answer is wrong because you map int to int('abcd' is int, not string)
@Felics : The definition of a string is: a sequence of characters. While 'Some''s direct type may be int, semantically it is exposed via boost::mpl::string as a sequence of characters, so it is in fact a string. What you're really saying is that you don't like the syntax of 'Some','Tag' vs. "SomeTag", which is something you could have determined days before I typed out the code for you, and saved me the trouble; but they are, in fact, both strings. In the future, read the docs you're linked to before wasting someone else's time asking for code then trivially dismissing it.

sbi · Accepted Answer · 2011-05-03 14:09:19Z

You cannot operate on string literals at compile-time, so what you want isn't feasible in the way you suggested. However, if you're contemplating to process these strings at compile-time, then this means you know all strings at compile-time, and from that you might arrive at acceptable approximations to what you want.

The code you showed implies that the number generation (let's call it a hash) is invoked every time someone searches for a tag. Would reducing this to one invocation be acceptable? If so, you could define constants and use these instead of strings:

const int SomeTag       = toNumber("SomeTag"      ); 
const int SomeOtherTag  = toNumber("SomeOtherTag" ); 
const int YetAnotherTag = toNumber("YetAnotherTag"); 
// ...

Then, simply replace all occurances of search("SomeTag") by search(SomeTag).

If there's a great number of tags, typing the above could be very tedious, in which case a macro might help:

#define DEFINE_TAG(Tag_) const int Tag_ = toNumber(#Tag_); 

DEFINE_TAG(SomeTag); 
DEFINE_TAG(SomeOtherTag); 
DEFINE_TAG(YetAnotherTag); 
// ... 

#undef DEFINE_TAG

This can be a good idea because it solves the big problem from enum(I don't need to include the header in all project files and to recompile it every time I add a new tag) and from local defines(tag conflicts). The only problem here is the redefinition of same tag in different files and linker errors, but.. this can be solved with static const int instead of const int. Thanks!
So are you using strings because you don't want to the enum to be included everywhere? I suppose you are aware that you're actually trading compile-time performance for run-time safety there? Is this really worth it? What I have done in the past in such cases was to break down the value space (in your case: enum values) into independent chunks (you'd have to use const int instead) which are defined in different headers. Then you only include the one header you're interested in, and aren't affected by changes in other headers.

Juraj Blaho · Accepted Answer · 2011-05-03 12:44:30Z

2

If the string literal is known at compile time, then there is probably no reason to use it as a string literal. You may use enumeration or named integral constants.

If the string is passed to the search function by a variable and it is not known at compile time, then there is no way to do the toNumber() resulution at compile time. Then a good solution is to use some kind of a dictionary (e.g. std::map<std::string, int>)

answered May 3, 2011 at 12:44

Juraj Blaho

13.6k7 gold badges53 silver badges99 bronze badges

2 Comments

Mircea Ispas Over a year ago

As I said before, toNumber function is faster than the search.

sbi Over a year ago

I think the first paragraph here is the key. To do this at compile-time, you would need to know all possible strings at compile-time. And when you have those, there's no reason to not to use symbolic constants for them.

Viktor Sehr · Accepted Answer · 2011-05-03 12:36:04Z

0

Althrough not compile time, I think this is fast enough for you;

void foo()
{
    const static auto someTagN = toNumber("SomeTag");
    type value = internal_search(someTagN );
}

answered May 3, 2011 at 12:36

Viktor Sehr

13.2k6 gold badges64 silver badges98 bronze badges

4 Comments

Jan Hudec Over a year ago

That won't run at compile-time, but at global construction time instead, so it will prolong the program startup.

Mircea Ispas Over a year ago

This is what I want to avoid, string conversion at run time. I don't a few tags that are use many times, I have different tags that are used only once or few times.

Mircea Ispas Over a year ago

@Jan Hudec It will run when foo is called first time, but if foo will be called once this has no optimization effect because the tag will be converted once at run time like it was before and I will have global memory full with junk numbers that will not be used anymore.

sbi Over a year ago

@Jan: Actually, local static variables are initialized when program execution passes their initialization code for the first time. In plain English: someTagN is initialized when foo() is called for the first time.

sehe · Accepted Answer · 2011-05-03 12:38:57Z

0

I know it is probably not fashionable, but you can generate a hash-table ahead of time. I like to use gperf to generate the plumbing there.

I know know. You wanted something to make compilation last longer... Just saying :)

answered May 3, 2011 at 12:38

sehe

400k49 gold badges474 silver badges671 bronze badges

3 Comments

Mircea Ispas Over a year ago

That's not a problem, for debug it may be #define X(tag) toNumber(tag) and for release #define X(tag) someTemplate<tag>::number. This is for run time optimizations, and compile time is irrelevant.

sehe Over a year ago

I was half joking, I'm not worried about compile times :)

Mircea Ispas Over a year ago

Compile time is a big problem. In my current project a full rebuild can take several hours, and this is a very big problem:)

Lou Franco · Accepted Answer · 2011-05-03 12:39:15Z

0

Not sure that you can. Is the list of possible tags small? Even if not, is it small most of the time. If so, you can use template specialization on a subset of the tags

template<char *tag> 
int toNumber() {
    return toNumber(tag);
}

template<>
int toNumber<"0">() {
     return 0;
}

template<>
int toNumber<"1">() {
     return 1;
}

(caveats: my specialization syntax might be wrong, and I have no idea if this works for char*)

answered May 3, 2011 at 12:39

Lou Franco

89.3k14 gold badges137 silver badges199 bronze badges

2 Comments

Jan Hudec Over a year ago

Templates don't accept character literals, only addresses of constants. So you'd have to create const char * const variables for the strings and pass those constants to the templates.

ildjarn Over a year ago

String literals are lvalues and consequently cannot be compile-time constants. However, character literals can indeed be compile-time constants.

Collectives™ on Stack Overflow

C++ compile time function execution

6 Answers 6

5 Comments

2 Comments

2 Comments

4 Comments

3 Comments

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

5 Comments

2 Comments

2 Comments

4 Comments

3 Comments

2 Comments

Linked

Related