Compile-time static `std::integral_counter`

[Vittorio Romeo]

Introduction

There have been many occasions in my games/libraries where I need to assign a `0..n` compile-time integer to a series of types. Here are two examples:

• In one of my component-based entity management systems, I assign an `std::bitset` to every entity, where every bit corresponds to a specific component type.
• One of my polymorphic memory management/recycling classes stores several "chunks" of allocated memory for specific types that are part of the same hierarchy.
  To quickly retrieve the chunks, they're stored in a contiguous array. Every index of the array corresponds to a chunk of a specific type.

The problem here is assigning an unique integer, starting from zero, to a specific type, and maintaining it throughout the whole program. This requires keeping track of the last used integer.

Current solution/workaround

Sacrificing performance, it is currently possible to achieve what I described above. Not at compile-time, but at run-time instead.

// Statically store the last used global unique id.
inline int getLastId() noexcept
{
   static int lastId{0};
   return lastId++;
}

// Statically store an unique id for a specific type `T`.
template<typename T> int getIdForType() noexcept
{
    static int id{getLastId()};
    return id;
}

struct TypeA { };
struct TypeB { };
struct TypeC { };

int main()
{
    // Whenever `getIdForType<T>()` gets instantiated,
    // an unique id is "bound" to `T` for the rest of the program.

    std::cout << getIdForType<TypeA>() << std::endl; // Prints '0'
    std::cout << getIdForType<TypeB>() << std::endl; // Prints '1'
    std::cout << getIdForType<TypeC>() << std::endl; // Prints '2'

    return 0;
}

The workaround allows me to implement the aforementioned examples. However, it requires `static` storage for something that could be determined at compile-time. 

It also requires overhead to access this storage every time we need to get a type's unique id.

Possible proposal

Implement a stateful compile-time `std::integral_counter` class that somehow (compiler magic?) remembers its value.

// We need to "store" a counter during compile-time.
// A new keyword/contextual keyword combination is probably required for this.

// We basically "allocate" memory for this counter during compilation and
// use the counter during compilation. The counter should not exist anymore
// at run-time (or be accessible at run-time).

static template std::integral_counter<int, 0> lastIdCounter;
// ____________ _____________________ ___  _  _____________
// |            |                     |    |  L name
// L contextual keyword combination   |    |
//              |                     |    L counter starting value
//              L type                L counter value type

// Everything is done at compile-time. Constexpr should work, but also using
// `std::integral_constant` with a template struct.
template<typename T> constexpr int getIdForType() noexcept
{
    constexpr int id{lastIdCounter::value}; // Get the compile-time counter's current value
    lastIdCounter::increment(); // Increment the compile-time counter - it will remember its last value
    return id;
}

int main()
{
    // Whenever `getIdForType<T>()` gets called with a certain `T`, a value from
    // the compile-time counter is "bound" to that `T` for the rest of the program.
    // Since it is `constexpr` and evaluated at compile-time, there's no need to store
    // the id anywhere in memory - calling the `getIdForType<T>()` function can
    // basically be thought of as replacing `getIdForType<T>()` with a constant
    // at compile time.

    std::cout << getIdForType<TypeA>() << std::endl; // Prints '0'
    std::cout << getIdForType<TypeB>() << std::endl; // Prints '1'
    std::cout << getIdForType<TypeC>() << std::endl; // Prints '2'

    return 0;
}

Thoughts? 

What motivated me to write this post is the fact that we have all necessary information at compile-time to assign an unique constant id to a specific type - but there (apparently) is no way of doing so. 

[TONGARI J]

Q: What happens if used in different TUs?

    // in file a.cpp

    std::cout << getIdForType<TypeA>() << std::endl; // Prints '0'

    std::cout << getIdForType<TypeB>() << std::endl; // Prints '1'

    std::cout << getIdForType<TypeC>() << std::endl; // Prints '2'

    

    // in file b.cpp

    std::cout << getIdForType<TypeC>() << std::endl; // Prints '0'

    std::cout << getIdForType<TypeB>() << std::endl; // Prints '1'

    std::cout << getIdForType<TypeA>() << std::endl; // Prints '2'

Is that the expected result?

[Matheus Izvekov]

What about using typeid / std::typeinfo hash_code?

[Vittorio Romeo]

On Friday, 19 September 2014 16:07:25 UTC+2, TONGARI J wrote:

Q: What happens if used in different TUs?

    // in file a.cpp

    std::cout << getIdForType<TypeA>() << std::endl; // Prints '0'

    std::cout << getIdForType<TypeB>() << std::endl; // Prints '1'

    std::cout << getIdForType<TypeC>() << std::endl; // Prints '2'

    

    // in file b.cpp

    std::cout << getIdForType<TypeC>() << std::endl; // Prints '0'

    std::cout << getIdForType<TypeB>() << std::endl; // Prints '1'

    std::cout << getIdForType<TypeA>() << std::endl; // Prints '2'

Is that the expected result?

No - the expected result is 0, 1, 2, 3, 4, 5.
An unique id has to be "bound" to a type for the rest of the program, regardless of the TU.

-----

On Friday, 19 September 2014 16:12:39 UTC+2, Matheus Izvekov wrote:

What about using typeid / std::typeinfo hash_code?

`hash_code` does not return an unique number in a specific range (cannot be used for array indices, for example).

`hash_code` does not guarantee unique hashes - two types can have the same hash.

`hash_code` is not constexpr or compile-time.

[Tony V E]

On Fri, Sep 19, 2014 at 10:24 AM, Vittorio Romeo <vittorio....@gmail.com> wrote:

On Friday, 19 September 2014 16:07:25 UTC+2, TONGARI J wrote:

Q: What happens if used in different TUs?

    // in file a.cpp

    std::cout << getIdForType<TypeA>() << std::endl; // Prints '0'

    std::cout << getIdForType<TypeB>() << std::endl; // Prints '1'

    std::cout << getIdForType<TypeC>() << std::endl; // Prints '2'

    

    // in file b.cpp

    std::cout << getIdForType<TypeC>() << std::endl; // Prints '0'

    std::cout << getIdForType<TypeB>() << std::endl; // Prints '1'

    std::cout << getIdForType<TypeA>() << std::endl; // Prints '2'

Is that the expected result?

No - the expected result is 0, 1, 2, 3, 4, 5.

ODR says that the function getIdForType<TypeC>() only exists once, so it will always return the same value.

I expect

0
1
2
2
1
0

(regardless of which cpp is called first (but assuming they are not called concurrently (the counters would need to be atomic in a threading case))).

Tony

[Vittorio Romeo]

`getIdForType<T>` should be marked as `inline` then. I forgot about it - I actually do it in my code (using the `static` storage method for counting ids).

---

Date: Fri, 19 Sep 2014 10:45:03 -0400
Subject: Re: [std-proposals] Re: Compile-time static `std::integral_counter`
From: tvan...@gmail.com
To: std-pr...@isocpp.org

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[Thiago Macieira]

On Friday 19 September 2014 10:45:03 Tony V E wrote:
> ODR says that the function getIdForType<TypeC>() only exists once, so it
> will always return the same value.
>
> I expect
>
> 0
> 1
> 2
> 2
> 1
> 0

ODR is not enough. This could print:

0
1
0
0
1
0

if somehow the build selected getIdForType from different TUs for different
types.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358

[Vittorio Romeo]

True. Inlining both functions should prevent that from happening (it already does work as intended in my implementation that unfortunately uses run-time static storage).

[Thiago Macieira]

No, it doesn't, since inline non-static means they are merged at link- or run-
time so that ODR is followed. Which one is selected is entirely up to the
linkers, which rightly assumes that any copy is fine.

Usually, they select all from the same TU, but they don't have to. Just try
with three TUs now, with the third one using only getIdForType<TypeC>().

[inkwizyt...@gmail.com]

Why don't move this types to one typedef?

typedef any_variadic_template<A, B, C, D> typeColection;
template<typename T>
constexpr int f() { return type_pos_in_param<T, typeColection>::value; }

You can query this type anywhere you want.

[David Krauss]

On 2014–09–19, at 9:42 PM, Vittorio Romeo <vittorio....@gmail.com> wrote:

Introduction

There have been many occasions in my games/libraries where I need to assign a `0..n` compile-time integer to a series of types. Here are two examples:

Please see my StackOverflow Q&A, "Does C++ support compile-time counters?” (Scroll to the C++11 section.)

I see some discussion of the ODR in this thread. Any counter usage with linkage does need to be placed in the header file and repeated exactly the same in each TU. Avoid sharing a counter between headers unless those headers are all-or-nothing.

[Vittorio Romeo]

On Friday, 19 September 2014 19:13:48 UTC+2, inkwizyt...@gmail.com wrote:

Why don't move this types to one typedef?

typedef any_variadic_template<A, B, C, D> typeColection;


template<typename T>
constexpr int f() { return type_pos_in_param<T, typeColection>::value; }


You can query this type anywhere you want.

This requires creating and maintaining a list of types... which it's (should be) unnecessary and it's very cumbersome for the user of my libraries.

---

On Friday, 19 September 2014 19:23:22 UTC+2, David Krauss wrote:

I see some discussion of the ODR in this thread. Any counter usage with linkage does need to be placed in the header file and repeated exactly the same in each TU. Avoid sharing a counter between headers unless those headers are all-or-nothing.

Can you elaborate more on this? What I am currently doing is putting the workaround code in an header file (header-only library) and using inline in every function. Is that not guaranteed to return expected values in different TUs? (values that never repeat, I mean)

[Sean Middleditch]

On Friday, September 19, 2014 7:12:39 AM UTC-7, Matheus Izvekov wrote:

What about using typeid / std::typeinfo hash_code?

Embedded and games very frequently turn off RTTI. It might be more palatable if the user had direct control over which types had RTTI and which don't (we don't need every polymorphic type to have the info).

One of the main uses for the feature that Vittorio is presenting here is in developing custom RTTI-like data structures that (a) provide explicit control and (b) have useful information that RTTI lacks (which may be high-level application semantic information that C++ itself won't and can't even know about).

This seemed to be something that a lot of people got surprised by at CppCon so perhaps it bears repeating: a very significant set of C++-using industries usually will not (often /cannot/) use exceptions or RTTI or virtual inheritance or a few certain other C++ language features. RTTI is not a solution, especially in Vittorio's stated domain (games).

That said... I don't think Vittorio's feature request is possible. There's no way to give stable compile-time IDs across translation units in the usage pattern he wants them in, even with a new magic language construct.

[David Krauss]

On 2014–09–20, at 1:40 AM, Vittorio Romeo <vittorio....@gmail.com> wrote:

On Friday, 19 September 2014 19:23:22 UTC+2, David Krauss wrote:

I see some discussion of the ODR in this thread. Any counter usage with linkage does need to be placed in the header file and repeated exactly the same in each TU. Avoid sharing a counter between headers unless those headers are all-or-nothing.

Can you elaborate more on this? What I am currently doing is putting the workaround code in an header file (header-only library) and using inline in every function. Is that not guaranteed to return expected values in different TUs? (values that never repeat, I mean)

It’s in reference to the StackOverflow answer.

If the counter values are assigned at runtime, it’s sufficient to have external linkage (inline or not) on some object or function which does the counting. This should also be mutex-locked, because each TU is allowed to be initialized in a different thread.

If the counter values are assigned at compile time, you need to compute each value immediately as the counter updates are declared within the TU. Other TUs are invisible until linking. In order to have consistent counter values, the counting and assignment of the counter to whatever variables need to be the same across all TUs that observe the counter or those variables.

There is no way to “peek” at things in another TU, because that information doesn’t exist. Maybe the next TU hasn’t even be written yet by a programmer. inline certainly won’t help.

[Matheus Izvekov]

On Friday, September 19, 2014 3:49:07 PM UTC-3, Sean Middleditch wrote:

That said... I don't think Vittorio's feature request is possible. There's no way to give stable compile-time IDs across translation units in the usage pattern he wants them in, even with a new magic language construct.

Yeah I see, it would require something like -flto to be mandated.

[Thiago Macieira]

On Friday 19 September 2014 23:18:59 Matheus Izvekov wrote:
> Yeah I see, it would require something like -flto to be mandated.

With static linking. LTO is not enough if the same symbol were used in
different shared libraries. And even then, I'm depending on how each compiler
does link-time code generation, it may not work at all.

No, the standard requires that the functions be the same, with the same body,
or the program is ill-formed.

But you know what you could use for an identifier that is unique? The address
of the function itself.

[Thiago Macieira]

On Saturday 20 September 2014 07:32:29 David Krauss wrote:
> If the counter values are assigned at runtime, it's sufficient to have
> external linkage (inline or not) on some object or function which does the
> counting. This should also be mutex-locked, because each TU is allowed to
> be initialized in a different thread.

std::atomic<int> can do it without the need for locking a mutex.

[Matheus Izvekov]

On Saturday, September 20, 2014 3:58:44 PM UTC-3, Thiago Macieira wrote:

But you know what you could use for an identifier that is unique? The address
of the function itself.

That has a small caveat though: the compiler is allowed to merge different functions
and use the same address for them in case their generated code is identical.
I have been bitten by this before :)

[Sean Middleditch]

On Sat, Sep 20, 2014 at 2:55 PM, Matheus Izvekov <mizv...@gmail.com> wrote:
> On Saturday, September 20, 2014 3:58:44 PM UTC-3, Thiago Macieira wrote:
>>
>> But you know what you could use for an identifier that is unique? The
>> address
>> of the function itself.
>>
>
> That has a small caveat though: the compiler is allowed to merge different
> functions

I don't think so. I believe that the linker is not supposed to do that
for any distinct definition, be it a function or global or static;
addresses must be unique for each definition. At least one popular
implementation does do it by default but I'm fairly sure that's not
conforming behavior (and it can be turned off). Other implementations
allow the user to pass a flag that enables the behavior. Some even
allow a different flag that only merges identical functions when it
can be proved that their addresses are not taken.
--
Sean Middleditch
http://seanmiddleditch.com

[Matheus Izvekov]

On Sunday, September 21, 2014 4:51:52 PM UTC-3, Sean Middleditch wrote:

I don't think so. I believe that the linker is not supposed to do that
for any distinct definition, be it a function or global or static;
addresses must be unique for each definition. At least one popular
implementation does do it by default but I'm fairly sure that's not
conforming behavior (and it can be turned off).

That might be the case, yeah, I am fairly certain visual studio 2013 does this, and there is
nothing in the option that turns this on/off indicating this is not standard conforming.

[Sean Middleditch]

It's called Identical COMDAT Folding in their implementation. See
http://msdn.microsoft.com/en-us/library/bxwfs976.aspx for information
on controlling this behavior.

[Matheus Izvekov]

On Sunday, September 21, 2014 5:13:01 PM UTC-3, Sean Middleditch wrote:

It's called Identical COMDAT Folding in their implementation. See
http://msdn.microsoft.com/en-us/library/bxwfs976.aspx for information
on controlling this behavior.

Yeah exactly, and notice how it seems there is no mention of this optimization being non-conforming even in that documentation you linked.

[Thiago Macieira]

On Sunday 21 September 2014 13:17:39 Matheus Izvekov wrote:
> > http://msdn.microsoft.com/en-us/library/bxwfs976.aspx for information
> > on controlling this behavior.
>
> Yeah exactly, and notice how it seems there is no mention of this
> optimization being non-conforming even in that documentation you linked.

MSVC and DLLs have plenty of non-conforming behaviours, including violation of
ODR rules and over-instantiation of templates.

[David Krauss]

On 2014–09–22, at 4:12 AM, Sean Middleditch <se...@middleditch.us> wrote:

> It's called Identical COMDAT Folding in their implementation. See
> http://msdn.microsoft.com/en-us/library/bxwfs976.aspx for information
> on controlling this behavior.

Yuck. I’d heard of MSVC doing that, but I assumed they also generated trampoline instructions (jumps or prologue nops) to generate unique addresses when observation happens.

To be sure, this optimization doesn’t need to be nonconforming. There should be no difficulty to proving that an address is never taken, just generate a linker symbol for each trampoline and let it get stripped by the normal process.

[Sean Middleditch]

On Sun, Sep 21, 2014 at 8:19 PM, David Krauss <pot...@gmail.com> wrote:
> To be sure, this optimization doesn't need to be nonconforming. There should be no difficulty to proving that an address is never taken, just generate a linker symbol for each trampoline and let it get stripped by the normal process.

See --icf=safe in Gold for an implementation of ICF that is conforming.

[Matthew Fioravante]

I had another use case for a compile time counter.

I created a instruction set (think assembly) to model a certain system. I had a raw instruction class which was essentially just an integer ordinal and an untyped buffer fixed size to store the operands. I had a different type for each different kind of instruction and set the ordinal of that instruction to a compile time integer value. I could convert the specific instruction types to and from the raw instruction type, allowing an efficient type erasure scheme. The idea behind the API was to allow callers to push any sequence of instructions into a buffer and then send them off to be executed by the system.

In my case I just assigned the integer values to each class manually using templates and inheritance, taking care not to have them collide. It would have been nice if there was compiler magic to do this for me.

As others have mentioned, such a feature may not be possible. There is a chicken and egg problem here. For a particular TU, the compiler needs to know the actual value of the counter in order to compile the TU and this value cannot be known until link time. Throw shared libraries into the mix and you've got even more complications.