Template turing-completeness and code size optimization

Discussion in 'C++' started by a.tavs@hotmail.it, Jan 27, 2009.

  1. Guest

    Hello everyone,

    I'd like to bother you asking two questions:
    1) does the turing-completeness of c++ template metalanguage hinders
    templated code optimization? If so, how?
    2) is it possible to write a c++ compiler that removes ``duplicated
    instantiations'' i.e. template instantiations with different template
    parameters but identical low-level implementation such as,
    presumeably,
    Foo<int*> and Foo<void*>?

    TIA,

    Tavs
     
    , Jan 27, 2009
    #1
    1. Advertising

  2. Guest

    On Jan 27, 5:45 pm, wrote:
    > Hello everyone,
    >
    > I'd like to bother you asking two questions:
    > 1) does the turing-completeness of c++ template metalanguage hinders
    > templated code optimization? If so, how?


    That's an interesting question, albeit a bit confusing. One way to
    answer might be that if the template features in C++ had been defined
    more narrowly, such as to further restrict the possible set of
    problems that could be solved in it, then there would be potentially
    be better optimizations possible. Of course, this is assuming that
    such a definition would be simpler (it's hard to imagine otherwise).
    Nevertheless, you could have a non-turing complete language that was
    much more difficult to optimize.

    What you are asking might be equivalant to:

    Given a new programming language X, would this hinder or help
    optimizations vs. c++ ? But you don't mention what "X" might be.

    > 2) is it possible to write a c++ compiler that removes ``duplicated
    > instantiations'' i.e. template instantiations with different template
    > parameters but identical low-level implementation such as,
    > presumeably,
    > Foo<int*> and Foo<void*>?


    Sure! I don't see why not. In fact, in many cases, compilers remove
    the only instantiation of a template because it is optimized away.

    Joe C
     
    , Jan 28, 2009
    #2
    1. Advertising

  3. On Jan 27, 11:45 pm, wrote:
    > Hello everyone,
    >
    > I'd like to bother you asking two questions:
    > 1) does the turing-completeness of c++ template metalanguage hinders
    > templated code optimization? If so, how?
    > 2) is it possible to write a c++ compiler that removes ``duplicated
    > instantiations'' i.e. template instantiations with different template
    > parameters but identical low-level implementation such as,
    > presumeably,
    > Foo<int*> and Foo<void*>?


    Yes, it is possible to write such a compiler (or rather linker). In
    fact, it has already been done. The Microsoft linker supports such
    optimisations.
    Note that enabling these optimisations makes the implementation non-
    conforming w.r.t. the C++ standard, as different functions end up
    having the same address, which goes contrary to the rules in the C++
    standard.

    >
    > TIA,
    >
    > Tavs


    Bart v Ingen Schenau
     
    Bart van Ingen Schenau, Jan 28, 2009
    #3
  4. Bart van Ingen Schenau <> writes:

    > On Jan 27, 11:45 pm, wrote:
    >> Hello everyone,
    >>
    >> I'd like to bother you asking two questions:
    >> 1) does the turing-completeness of c++ template metalanguage hinders
    >> templated code optimization? If so, how?
    >> 2) is it possible to write a c++ compiler that removes ``duplicated
    >> instantiations'' i.e. template instantiations with different template
    >> parameters but identical low-level implementation such as,
    >> presumeably,
    >> Foo<int*> and Foo<void*>?

    >
    > Yes, it is possible to write such a compiler (or rather linker). In
    > fact, it has already been done. The Microsoft linker supports such
    > optimisations.
    > Note that enabling these optimisations makes the implementation non-
    > conforming w.r.t. the C++ standard, as different functions end up
    > having the same address, which goes contrary to the rules in the C++
    > standard.


    Well it's easy enough to allocate a 'JMP common' instruction for each
    function...

    --
    __Pascal Bourguignon__
     
    Pascal J. Bourguignon, Jan 28, 2009
    #4
  5. Guest

    ha scritto:

    > On Jan 27, 5:45 pm, wrote:
    > Given a new programming language X, would this hinder or help
    > optimizations vs. c++ ? But you don't mention what "X" might be.
    >

    Ada/Java generics?

    > Sure! I don't see why not. In fact, in many cases, compilers remove
    > the only instantiation of a template because it is optimized away.
    >

    Uh, I made a mistake with the 2nd the question, you know, it was late
    for me when I wrote the post...
    Obviously, if you have the same object code in more than one
    instanciation, you can trash all but one instantiation at link time.
    What I wanted to ask was: can the compiler optimize space consumption
    by guessing that two instantiations Foo<T1> and Foo<T2> /can/ be
    compiled into the same object code?

    For example the compiler could compile Foo<T1> and Foo<T2>
    differently, because of some optimization, writing two different
    object files. On the other hand, if I care about space consumption, I
    may want to have those instantiations compiled into the same object.


    Tavs
     
    , Jan 28, 2009
    #5
  6. James Kanze Guest

    On Jan 28, 10:42 am, (Pascal J. Bourguignon)
    wrote:
    > Bart van Ingen Schenau <> writes:
    > > On Jan 27, 11:45 pm, wrote:


    > >> I'd like to bother you asking two questions:
    > >> 1) does the turing-completeness of c++ template metalanguage hinders
    > >> templated code optimization? If so, how?
    > >> 2) is it possible to write a c++ compiler that removes ``duplicated
    > >> instantiations'' i.e. template instantiations with different template
    > >> parameters but identical low-level implementation such as,
    > >> presumeably,
    > >> Foo<int*> and Foo<void*>?


    > > Yes, it is possible to write such a compiler (or rather linker). In
    > > fact, it has already been done. The Microsoft linker supports such
    > > optimisations.
    > > Note that enabling these optimisations makes the implementation non-
    > > conforming w.r.t. the C++ standard, as different functions end up
    > > having the same address, which goes contrary to the rules in the C++
    > > standard.


    > Well it's easy enough to allocate a 'JMP common' instruction for each
    > function...


    Or just insert a no-op instruction in front of the code, and use
    its address for one of the functions. Only when taking the
    function's address, of course, and only do this when the code
    actually does compare the two addresses. Admittedly, this does
    require a bit of intelligence from the linker. But no more than
    a lot of other modern optimization techniques.

    In practice, I don't know if it is really worth the effort.
    Just do it the way Microsoft does, with a compiler switch to
    turn it off if you need strict compatibility. Probably 99% of
    all programs will never notice, and not need the switch.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Jan 28, 2009
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ravikiran

    Zero Optimization and Sign Optimization???

    Ravikiran, Nov 17, 2008, in forum: C Programming
    Replies:
    22
    Views:
    900
    Thad Smith
    Nov 24, 2008
  2. spinoza1111

    Turing, Navia and Schildt

    spinoza1111, Sep 11, 2009, in forum: C Programming
    Replies:
    28
    Views:
    895
    spinoza1111
    Oct 23, 2009
  3. Musical Notation

    Lambda function Turing completeness

    Musical Notation, Jul 31, 2013, in forum: Python
    Replies:
    4
    Views:
    106
    Piet van Oostrum
    Aug 25, 2013
  4. Schneider
    Replies:
    0
    Views:
    82
    Schneider
    Jul 31, 2013
  5. Ian Kelly
    Replies:
    0
    Views:
    87
    Ian Kelly
    Jul 31, 2013
Loading...

Share This Page