Quand je vois

    BigInt BigInt::operator-- (int i) {
        BigInt un(1, true, base);
        *this -= un;
        return *this;
    }

je me dis

• qu'on pourrait peut être définir une constante "un" plutôt que de la recréer à chaque fois (y en a d'autres un peu partout)
• que l'opération -=   fait un appel à - qui alloue  un nouveau nombre pour le résultat de la soustraction
• qui écrase ensuite *this  (ce qui entraîne une libération)

et qu'on pourrait peut être aller taper directement dans la représentation interne de Bigint pour retrancher 1 à *this, en court-circuitant ces abstractions fort  esthétiques, mais coûteuses.

-
Edité par michelbillaud 21 janvier 2025 à 21:21:08

Effectivement, les allocations/désallocations sont chronophages.

Pire elles ruinent le multithreading car une allocation, c'est un entonnoir : le système n'alloue que pour un à la fois.

Pour gagner ne vitesse, on pourrait envisager un cache (une mémoire déjà allouée de BigInt par exemple) qui ne seraient pas détruits et récréés mais simplement réutilisés

Alors BigInt n'est pas mon code (celui que j'ai profilé, qui est sur le lien GitHub).

@lmghs Je ne sais pas de quoi il retourne. Aurais-tu un exemple ?

Peut être aussi que des statistiques d'utilisation montreraient que la plupart des BigInt ne sont pas si grands que ça, et qu'on y gagnerait largement à utiliser une représentation hybride :

• un grand entier natif en dessous d'une certaine valeur absolue (sans allocation) 
• Un tableau dynamique pour les nombres qui rentrent pas

Ça va compliquer, c'est sur. No pain, no gain.

-
Edité par michelbillaud 22 janvier 2025 à 9:21:47

P'tit Ju a écrit:

Alors BigInt n'est pas mon code (celui que j'ai profilé, qui est sur le lien GitHub).

@lmghs Je ne sais pas de quoi il retourne. Aurais-tu un exemple ?

C'est ce qui est mis en place dans toutes les bibliothèques de calcul matriciel destinées exclusivement au C++ qui sont employées "professionnellement".

L'idée est que operator+(A, A) ne retourne pas un A, mais une expression conduisant au final à la définition d'un arbre à évaluer. Et c'est au moment de la construction ou de l'affectation <edit>d'un A à partir</edit> du dit arbre que l'évaluation est réalisée. On peut esquiver beaucoup d'allocations avec ça.

Ca veut dire qu'on retarderai le calcul que a+ b+c+d au dernier moment, et que la somme sur chacun des "chiffres" en base 2^64 ne se fait plus juste sur 2 opérandes mais sur n.

Après, je ne sais pas à quel point il serait simple de définir les multiplications avec ça. Il va falloir creuser. Et probablement s'inspirer de ce qui est fait dans eigen/blaze/armadillo/...

-
Edité par lmghs 22 janvier 2025 à 13:55:48

Ok, je vais essayer alors.

Voici ce que j'ai fait pour l'instant (idem pour la soustraction et autres opérateurs) :

template <typename E>
class IntegerExpression
{
    public:
        static constexpr bool is_leaf = false;

        CONSTEXPR bool isPositive() const
        {
            return static_cast<E const&>(*this).isPositive();
        }
    
        CONSTEXPR bool isNegative() const
        {
            return !isPositive();
        }
    
        CONSTEXPR std::vector<typename E::Type> const& bits() const
        {
            return static_cast<E const&>(*this).bits();
        }
        
        CONSTEXPR bool isNan() const
        {
            return static_cast<E const&>(*this).isNan();
        }
        
        CONSTEXPR bool isInfinity() const
        {
            return static_cast<E const&>(*this).isInfinity();
        }
};

template <typename E1, typename E2>
class IntegerAdd : public IntegerExpression<IntegerAdd<E1, E2> >
{
    typename std::conditional<E1::is_leaf, const E1&, const E1>::type u_;
    typename std::conditional<E2::is_leaf, const E2&, const E2>::type v_;

    public:
        static constexpr bool is_leaf = false;

        IntegerAdd(E1 const& u, E2 const& v) : u_(u), v_(v)
        {
        }
        
        CONSTEXPR bool isPositive() const
        {
            if (u_.isPositive() && v_.isPositive())
                return true;
            else if (!u_.isPositive() && !v_.isPositive())
                return false;
            else if (u_.isPositive() && !v_.isPositive())
                return (u_ > v_);
            else //if (!u_.isPositive() && v_.isPositive())
                return (u_ < v_);
        }
        
        CONSTEXPR std::vector<typename E1::Type> bits() const
        {
            auto const w(u_ + v_);
            
            return w.bits();
        }
            
        CONSTEXPR bool isNan() const
        {
            if (u_.isNan() || v_.isNan())
                return true;
            else if ((u_.isInfinite() && u_.isPositive() && v_.isInfinite() && v_.isNegative())
                     || (u_.isInfinite() && u_.isNegative() && v_.isInfinite() && v_.isPositive()))
                return true;
            else
                return false;
        }
            
        CONSTEXPR bool isInfinity() const
        {
            return (u_.isInfinity() || v_.isInfinity());
        }
};
  
template <typename E1, typename E2>
IntegerAdd<E1, E2> operator+(IntegerExpression<E1> const& u, IntegerExpression<E2> const& v)
{
   return IntegerAdd<E1, E2>(*static_cast<const E1*>(&u), *static_cast<const E2*>(&v));
}

Sauf que j'ai une erreur de compilation que je ne comprends pas :

In file included from ..\..\testinteger.cpp:32:
D:/tmp/MillsPrimes/Integer.h: In instantiation of 'class IntegerExpression<Integer<unsigned char> >':
D:/tmp/MillsPrimes/Integer.h:592:7:   required from 'class Integer<unsigned char>'
D:/tmp/MillsPrimes/Integer.h:2778:33:   required from here
D:/tmp/MillsPrimes/Integer.h:57:56: error: invalid use of incomplete type 'class Integer<unsigned char>'
   57 |         CONSTEXPR std::vector<typename E::Type> const& bits() const
      |                                                        ^~~~
D:/tmp/MillsPrimes/Integer.h:592:7: note: declaration of 'class Integer<unsigned char>'
  592 | class Integer<T, typename std::enable_if<std::is_unsigned<T>::value>::type> : public IntegerExpression<Integer<T> >
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Dans ma classe Integer, il y a plus loin (je ne sais pas si ça a un lien) :

template <typename T>
class Integer<T, typename std::enable_if<std::is_unsigned<T>::value>::type> : public IntegerExpression<Integer<T> >
{
    public:
        typedef T Type;

        static constexpr bool is_leaf = true;
    
        template <typename E>
        Integer(IntegerExpression<E> const& expr)
        {
            isPositive_ = expr.isPositive();
            bits_ = expr.bits();
            isNan_ = expr.isNan();
            isInfinity_ = expr.isInfinity();
        }
    
        CONSTEXPR auto const& bits() const noexcept
        {
            return bits_;
        }

        //...
};

EDIT : J'ai ouvert une nouvelle branche plus light (sans la tonne de nombres premiers donc) sur le GitHub dédiée à ce développement sur les expressions template : https://github.com/Julien-Livet/TestInteger/tree/expression-template.

EDIT2 : J'ai résolu le problème de définition incomplète avec ça.

        template<typename T>
        CONSTEXPR std::vector<T> const& bits() const
        {
            return static_cast<E const&>(*this).bits();
        }
            

J'ai supprimé les opérateurs directs d'addition et autres entre les classes Integer mais j'obtiens les erreurs suivantes (je ne vois pas ce qui manque pour que la surchage avec IntegerExpression soit bien prise en compte).

..\..\testinteger.cpp: In member function 'void TestInteger::testAddition()':
..\..\testinteger.cpp:51:26: error: ambiguous overload for 'operator+' (operand types are 'Integerll' {aka 'Integer<long long unsigned int>'} and 'Integerll' {aka 'Integer<long long unsigned int>'})
   51 |         auto const n3(n1 + n2);
      |                       ~~ ^ ~~
      |                       |    |
      |                       |    Integer<[...]>
      |                       Integer<[...]>
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long unsigned int, long long unsigned int)' (built-in)
   51 |         auto const n3(n1 + n2);
      |                       ~~~^~~~
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long unsigned int, long long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long unsigned int, long unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long unsigned int, long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long unsigned int, unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long unsigned int, int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long int, long long unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long int, long long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long int, long unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long int, long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long int, unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long long int, int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long unsigned int, long long unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long unsigned int, long long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long unsigned int, long unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long unsigned int, long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long unsigned int, unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long unsigned int, int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long int, long long unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long int, long long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long int, long unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long int, long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long int, unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(long int, int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(unsigned int, long long unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(unsigned int, long long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(unsigned int, long unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(unsigned int, long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(unsigned int, unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(unsigned int, int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(int, long long unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(int, long long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(int, long unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(int, long int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(int, unsigned int)' (built-in)
..\..\testinteger.cpp:51:26: note: candidate: 'operator+(int, int)' (built-in)
In file included from ..\..\testinteger.cpp:32:
D:/tmp/MillsPrimes/Integer.h:125:20: note: candidate: 'IntegerAdd<E1, E2> operator+(const IntegerExpression<E1>&, const IntegerExpression<E2>&) [with E1 = Integer<long long unsigned int>; E2 = Integer<long long unsigned int>]'
  125 | IntegerAdd<E1, E2> operator+(IntegerExpression<E1> const& u, IntegerExpression<E2> const& v)
      |                    ^~~~~~~~
In file included from ..\..\testinteger.cpp:32:
D:/tmp/MillsPrimes/Integer.h:2935:22: note: candidate: 'constexpr Integer<T> operator+(Integer<T>, const S&) [with T = long long unsigned int; S = Integer<long long unsigned int>]'
 2935 | CONSTEXPR Integer<T> operator+(Integer<T> lhs, S const& rhs)
      |                      ^~~~~~~~
D:/tmp/MillsPrimes/Integer.h:2941:22: note: candidate: 'constexpr Integer<T> operator+(const S&, Integer<T>) [with T = long long unsigned int; S = Integer<long long unsigned int>]'
 2941 | CONSTEXPR Integer<T> operator+(S const& lhs, Integer<T> rhs)
      |                      ^~~~~~~~

EDIT3 : Bon, j'ai réussi à avancer un peu mais je croule sous les erreurs, pas simple .

EDIT4 : Mine de rien, c'est assez velu à faire cette histoire . J'ai une erreur de compilation que j'ai du mal à lever sur la ligne suivante.

        auto const mid((L + R) >> 1);

L'erreur est :

In file included from ..\..\testinteger.cpp:32:
D:/tmp/MillsPrimes/Integer.h: In instantiation of 'constexpr decltype(auto) operator>>(const IntegerExpression<E1>&, const S&) [with T = IntegerAdd<Integer<long long unsigned int>, Integer<long long unsigned int> >; S = int; std::enable_if_t<(! is_base_of_v<S, T>)>* <anonymous> = 0]':
D:/tmp/MillsPrimes/Integer.h:4127:32:   required from 'constexpr std::pair<Integer<T>, Integer<T> > computeQrBurnikelZiegler(const Integer<T>&, const Integer<T>&) [with T = long long unsigned int]'
..\..\testinteger.cpp:160:53:   required from here
D:/tmp/MillsPrimes/Integer.h:3207:19: error: no matching function for call to 'IntegerAdd<Integer<long long unsigned int>, Integer<long long unsigned int> >::IntegerAdd(const int&)'
 3207 |     return lhs >> T(rhs);

Comment dois-je faire pour récupérer le bon type Integer<U> à la place de T quand j'ai une expression template (je ne sais pas si c'est très clair comme ça) ?
J'ai essayé de mettre dans IntegerExpression :

        typedef typename E::Type Type;

et dans Integer :

        typedef T Type;

pour faire ça :

return lhs >> Integer<typename IntegerExpression<T>::Type>(rhs);

mais je me heurte au fait que la classe Integer n'est pas encore complètement définie à ce moment... J'ai besoin d'une astuce.

EDIT5 : J'ai réussi à m'en sortir mais j'ai à nouveau une erreur de compilation qui est la suivante :

D:/tmp/MillsPrimes/Integer.h:245:26: error: use of 'constexpr decltype(auto) IntegerMul<E1, E2>::bits() const [with E1 = Integer<long long unsigned int>; E2 = Integer<long long unsigned int>]' before deduction of 'auto'
  245 |             return w.bits();
      |                    ~~~~~~^~

sur le code suivant :

        CONSTEXPR decltype(auto) bits() const
        {
            auto w(u_);
            w += v_;

            return w.bits();
        }

Une idée ?

EDIT6 : Ben y'a pas à dire, mais c'est chaud patate mine de rien cette affaire d'expression template... Il faut que je m'assure que tous les types Integer<> soient tous de même type pour faire les calculs sur les mêmes template ou bien convertir tout ça en char et faire les calculs dessus. Du coup, je vais peut-être abandonner l'idée que Integer soit une classe template.

-
Edité par P'tit Ju 25 janvier 2025 à 19:23:44

P'tit Ju a écrit:

Pour information, mon code pour tester qu'un nombre de 1024 bits est premier dure environ 5 secondes.

Ha oui mais le problème c'est quand il faut générer un nombre premier aléatoirement. Il y a pas mal de nombres à tester avant de tomber sur le bon et ça me prend trop de temps pour ça que j'utilise une lib qui le fait à ma place, j'avais essayé de le faire moi même pour le fun mais ce n'est pas aussi performant. 

Je reviens sur l'histoire d'utiliser des expressions template (le code sur la branche expression-template du GitHub est à jour) où je continue à galérer. J'ai l'erreur de compilation suivante et je ne comprends pas le problème. Pour information, j'ai limité la taille de profondeur des templates à 25 (-ftemplate-depth=25), j'ai le même problème avec 900 (valeur par défaut) mais ça met plus de temps et c'est encore moins compréhensible. Pourriez-vous m'aider s'il vous plaît ?

In file included from D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/bits/move.h:57,
                 from D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/bits/atomic_base.h:38,
                 from D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/atomic:41,
                 from ..\..\Integer.cpp:1:
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits: In instantiation of 'struct std::__and_<std::is_array<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >, std::__not_<std::extent<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, 0> > >':
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:798:12:   required from 'struct std::__is_array_unknown_bounds<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >'
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:115:12:   required from 'struct std::__or_<std::is_void<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >, std::__is_array_unknown_bounds<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> > >'
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:120:12:   required from 'struct std::__or_<std::is_reference<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >, std::is_function<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >, std::is_void<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >, std::__is_array_unknown_bounds<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> > >'
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:211:13:   required by substitution of 'template<class _TypeIdentity, class _NestedType> constexpr typename std::__or_<std::is_reference<_NestedType>, std::is_function<_NestedType>, std::is_void<_NestedType>, std::__is_array_unknown_bounds<_NestedType> >::type std::__is_complete_or_unbounded(_TypeIdentity) [with _TypeIdentity = std::__type_identity<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >; _NestedType = IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>]'
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:691:52:   [ skipping 9 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ]
..\..\Integer.h:734:81:   required from 'constexpr std::vector<long long unsigned int> IntegerAnd<E1, E2>::bits() const [with E1 = IntegerMul<IntegerMod<Integer, Integer>, Integer>; E2 = Integer]'
..\..\Integer.h:1608:45:   required from 'constexpr std::vector<long long unsigned int> IntegerMod<E1, E2>::bits() const [with E1 = IntegerMul<IntegerMod<Integer, Integer>, Integer>; E2 = Integer]'
..\..\Integer.h:54:53:   required from 'constexpr std::vector<long long unsigned int> IntegerExpression<E>::bits() const [with E = IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>]'
..\..\Integer.h:74:13:   required from 'constexpr bool IntegerExpression<E>::operator!() const [with E = IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>]'
..\..\Integer.h:69:21:   required from 'constexpr IntegerExpression<E>::operator bool() const [with E = IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>]'
..\..\Integer.h:1487:52:   required from 'constexpr bool IntegerMul<E1, E2>::isInfinity() const [with E1 = IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>; E2 = Integer]'
..\..\Integer.h:1065:74:   required from 'constexpr bool IntegerAdd<E1, E2>::isNan() const [with E1 = Integer; E2 = IntegerMul<IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>]'
..\..\Integer.h:1556:25:   required from 'constexpr bool IntegerDiv<E1, E2>::isNan() const [with E1 = IntegerAdd<Integer, IntegerMul<IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer> >; E2 = Integer]'
..\..\Integer.h:59:54:   required from 'constexpr bool IntegerExpression<E>::isNan() const [with E = IntegerDiv<IntegerAdd<Integer, IntegerMul<IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer> >, Integer>]'
..\..\Integer.h:161:27:   required from 'constexpr bool IntegerExpression<E>::operator<(const IntegerExpression<T>&) const [with T = Integer; E = IntegerDiv<IntegerAdd<Integer, IntegerMul<IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer> >, Integer>]'
..\..\Integer.cpp:736:19:   required from here
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:138:12: fatal error: template instantiation depth exceeds maximum of 25 (use '-ftemplate-depth=' to increase the maximum)
  138 |     struct __and_<_B1, _B2>
      |            ^~~~~~~~~~~~~~~~
compilation terminated.
mingw32-make[1]: *** [Makefile.Release:683: release/Integer.o] Error 1
mingw32-make[1]: *** Waiting for unfinished jobs....
In file included from D:/Programmes/Qt/6.7.0/mingw_64/include/QtCore/qglobal.h:13,
                 from D:/Programmes/Qt/6.7.0/mingw_64/include/QtTest/qttestglobal.h:7,
                 from D:/Programmes/Qt/6.7.0/mingw_64/include/QtTest/qtest.h:12,
                 from D:/Programmes/Qt/6.7.0/mingw_64/include/QtTest/QTest:1,
                 from ..\..\testinteger.cpp:1:
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits: In instantiation of 'struct std::__and_<std::is_array<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >, std::__not_<std::extent<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, 0> > >':
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:798:12:   required from 'struct std::__is_array_unknown_bounds<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >'
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:115:12:   required from 'struct std::__or_<std::is_void<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >, std::__is_array_unknown_bounds<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> > >'
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:120:12:   required from 'struct std::__or_<std::is_reference<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >, std::is_function<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >, std::is_void<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >, std::__is_array_unknown_bounds<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> > >'
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:211:13:   required by substitution of 'template<class _TypeIdentity, class _NestedType> constexpr typename std::__or_<std::is_reference<_NestedType>, std::is_function<_NestedType>, std::is_void<_NestedType>, std::__is_array_unknown_bounds<_NestedType> >::type std::__is_complete_or_unbounded(_TypeIdentity) [with _TypeIdentity = std::__type_identity<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer> >; _NestedType = IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerRShift<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>, Integer>]'
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:691:52:   [ skipping 9 instantiation contexts, use -ftemplate-backtrace-limit=0 to disable ]
..\..\Integer.h:734:81:   required from 'constexpr std::vector<long long unsigned int> IntegerAnd<E1, E2>::bits() const [with E1 = IntegerMul<IntegerMod<Integer, Integer>, Integer>; E2 = Integer]'
..\..\Integer.h:1608:45:   required from 'constexpr std::vector<long long unsigned int> IntegerMod<E1, E2>::bits() const [with E1 = IntegerMul<IntegerMod<Integer, Integer>, Integer>; E2 = Integer]'
..\..\Integer.h:54:53:   required from 'constexpr std::vector<long long unsigned int> IntegerExpression<E>::bits() const [with E = IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>]'
..\..\Integer.h:74:13:   required from 'constexpr bool IntegerExpression<E>::operator!() const [with E = IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>]'
..\..\Integer.h:69:21:   required from 'constexpr IntegerExpression<E>::operator bool() const [with E = IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>]'
..\..\Integer.h:1487:52:   required from 'constexpr bool IntegerMul<E1, E2>::isInfinity() const [with E1 = IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>; E2 = Integer]'
..\..\Integer.h:1065:74:   required from 'constexpr bool IntegerAdd<E1, E2>::isNan() const [with E1 = Integer; E2 = IntegerMul<IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer>]'
..\..\Integer.h:1556:25:   required from 'constexpr bool IntegerDiv<E1, E2>::isNan() const [with E1 = IntegerAdd<Integer, IntegerMul<IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer> >; E2 = Integer]'
..\..\Integer.h:59:54:   required from 'constexpr bool IntegerExpression<E>::isNan() const [with E = IntegerDiv<IntegerAdd<Integer, IntegerMul<IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer> >, Integer>]'
..\..\Integer.h:161:27:   required from 'constexpr bool IntegerExpression<E>::operator<(const IntegerExpression<T>&) const [with T = Integer; E = IntegerDiv<IntegerAdd<Integer, IntegerMul<IntegerMod<IntegerMul<IntegerMod<Integer, Integer>, Integer>, Integer>, Integer> >, Integer>]'
..\..\testinteger.cpp:276:19:   required from here
D:/Programmes/Qt/Tools/mingw1120_64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/type_traits:138:12: fatal error: template instantiation depth exceeds maximum of 25 (use '-ftemplate-depth=' to increase the maximum)
  138 |     struct __and_<_B1, _B2>
      |            ^~~~~~~~~~~~~~~~

Y aurait-il moyen de produire une version réduite - minimaliste - du code produisant ce type d'erreurs ?

Salut! Le message d'erreur n'est pas complet il te dit que l'erreur vient lors de l'instanciation d'un paramètre template dans std::__and_ et qu'il manque quelque chose qui est requis à la ligne 734 et la ligne 734 dans ton fichier c'est cette ligne-ci : (Pourtant je ne vois pas d'utilisation de template à cette ligne.)

threads.emplace_back(threadFunc, start, end);

Es tu sûr d'avoir bien spécifié les paramètres template qui doivent être spécifié explicitement comme ceci : (Je ne suis plus très sûr de la syntaxe mais normalement ça doit se faire comme ceci)

myfonction.template <Type1, type2, ...> (args ...);

Je me souviens avoir eu ce même genre d'erreurs en oubliant de faire cela.

Mais sans avoir plus d'informations sur le message d'erreur sur ce qui manque et ce qui est requis ça va être dur de débuguer.

-
Edité par OmbreNoire 27 janvier 2025 à 16:35:09

Remarque sur les opérateurs:

• a <= b <=> !(b < a)
• a >= b <=> !(a < b)

Pas besoin de faire < + ==. Aussi operator==(other) <=> *this == other

Sinon ton erreur vient d'appel récursif, par exemple IntegerMul qui fait ((u_ << shift) * r).bits(); et donc une nouvelle construction de IntegerMul de manière récursive. Ce n'est probablement pas le seul endroit.

Mais dans le cas général il y a une mauvaise compréhension des expressions templates. Le but est de réduire les constructions intermédiaires en réutilisant les buffers. Là, tout ce que tu fais est dévaluer plus tard l'expression et de les évaluer plusieurs fois ! Par exemple isPositive() qui peut faire appel à < qui utilise 6 fois la fonction bits() qui elle-même fait plein d'opération lourde.

Un exemple de réduction est le remplacement les constructions de la forme a + b + c + d qui vont faire 3 boucles et 2 buffers intermédiaires:

tmp1 = loop(a[i] + b[i]); // flemme d'écrire du vrai code
tmp2 = loop(tmp1[i] + c[i]);
result = loop(tmp2[i] + d[i]);

Par quelque chose qui fait une seule boucle et sans buffer intermédiaire.

result = loop(a[i] + b[i] + c[i] + d[i])

Et dans les cas complexe réutiliser le buffer intermédiaire pour réduire les allocations.

Au passage, le code est invalide, les itérateurs de début et fin ne sont pas le même vector et il y a plusieurs vector intermédiaires totalement inutiles:

foo(bits().begin(), bits().end()) -> 2 itérateurs qui n'ont rien à voir entre eux puisque pointant sur 2 std::vector différents.

-
Edité par jo_link_noir 27 janvier 2025 à 23:27:32

Merci pour ton retour @jo_link_noir.

Comme je n'ai pas d'utilisation de l'opérateur[] dans ma classe, je comprends que l'usage des expressions template n'est peut-être pas adapté. Dans le cas contraire, j'ai du mal à voir comment modifier mon code pour arriver au comportement voulu...

P'tit Ju a écrit:

@michelbillaud J'ai élagué au maximum le code pour obtenir la version minimaliste ici : https://github.com/Julien-Livet/TestInteger/tree/ligth-expression-template.

Heu non, avec un Integer.h de presque 2000 lignes, c'est pas minimaliste...  Faut lire tout ça pour comprendre ce qui est écrit, deviner quelle était l'intention, et trouver pourquoi elle n'est pas atteinte, du point de vue du compilateur.

Ceci dit, les messages d'erreurs provoqués par les templates de C++, honnêtement j'ai pas envie de m'y mettre et ça me fait fuir C++. La demande d'un cas d'erreur minimal, c'était pour simplifier la vie de ceux qui ont le courage de s'y coller.

-
Edité par michelbillaud 28 janvier 2025 à 11:11:22

@lmghs D'accord mais du coup je ne vois pas concrètement ce que je dois faire pour ma classe Integer (version template ou non), avec un exemple sur un opérateur par exemple (le plus simple pour la compréhension of course, peut-être &).

EDIT : Dans mes recherches, j'ai vu qu'il y avait boost::proto mais je ne sais pas si je peux en avoir usage dans mon cas et si oui, comment. J'ai essayé d'ajouter ça à la suite de ma classe Integer (depuis le code de la branche main) :

template<typename T>
struct is_terminal : boost::mpl::false_
{
};

template<>
struct is_terminal<Integerc> : boost::mpl::true_
{
};

template<>
struct is_terminal<Integers> : boost::mpl::true_
{
};

template<>
struct is_terminal<Integeri> : boost::mpl::true_
{
};

template<>
struct is_terminal<Integerl> : boost::mpl::true_
{
};

template<>
struct is_terminal<Integerll> : boost::mpl::true_
{
};

BOOST_PROTO_DEFINE_OPERATORS(is_terminal, boost::proto::default_domain)

Et les opérateurs semblent bien définis mais pas certains usages, comme par exemple pour l'opérateur ! à convertir en bool :

In file included from ..\..\..\expression-template2\testinteger.cpp:32:
..\..\..\expression-template2\Integer.h: In instantiation of 'constexpr std::string Integer<T, typename std::enable_if<std::is_unsigned<_Tp>::value>::type>::toString(size_t) const [with T = unsigned char; typename std::enable_if<std::is_unsigned<_Tp>::value>::type = void; std::string = std::__cxx11::basic_string<char>; size_t = long long unsigned int]':
..\..\..\expression-template2\Integer.h:2335:20:   required from here
..\..\..\expression-template2\Integer.h:1276:25: error: could not convert 'operator!<Integer<unsigned char>&>(number)' from 'const type' {aka 'const boost::proto::exprns_::expr<boost::proto::tagns_::tag::logical_not, boost::proto::argsns_::list1<boost::proto::exprns_::expr<boost::proto::tagns_::tag::terminal, boost::proto::argsns_::term<Integer<unsigned char>&>, 0> >, 1>'} to 'bool'
 1276 |                     if (!number)
      |                         ^~~~~~~
      |                         |
      |                         const type {aka const boost::proto::exprns_::expr<boost::proto::tagns_::tag::logical_not, boost::proto::argsns_::list1<boost::proto::exprns_::expr<boost::proto::tagns_::tag::terminal, boost::proto::argsns_::term<Integer<unsigned char>&>, 0> >, 1>}

Quelques tuyaux à me suggérer ?

EDIT2 : J'ai cherché à faire fonctionner ce bout de code mais sans succès...

#include <iostream>
#include <vector>

#include <boost/proto/proto.hpp>

template<typename T>
struct is_terminal : boost::mpl::false_
{
};

template<>
struct is_terminal<std::vector<int> > : boost::mpl::true_
{
};

BOOST_PROTO_DEFINE_OPERATORS(is_terminal, boost::proto::default_domain)

int main()
{
    std::vector<int> const a{0, 1, 2, 3};
    std::vector<int> const b{4, 5, 6, 7};
    std::vector<int> const c{0, 0, 0, 0};

    auto const exprAdd{a + b};
    std::vector<int> const d{exprAdd}; //je ne sais pas quoi ajouter pour que ça fonctionne

    return 0;
}

-
Edité par P'tit Ju 2 février 2025 à 11:53:06

P'tit Ju a écrit:

@lmghs D'accord mais du coup je ne vois pas concrètement ce que je dois faire pour ma classe Integer (version template ou non), avec un exemple sur un opérateur par exemple (le plus simple pour la compréhension of course, peut-être &).

Salut,
Après avoir un peu plus cherché, je ne pense pas que ce que je t'ai proposé puisse marcher. Quand les additions se font membre à membre, OK. Sauf que là, il y a des retenues à propager.

On en revient à des opérations optimisées dans l'idée de ce qui est fait par la lib de GNU. Addition, multiplication, multiplication + addition, etc. On peut même profiter des instrinics de gcc et clang pour additionner des unsigned long long et savoir s'il y a une retenue.

Maintenant, pour la place des ET dans tout ça... ben je dirai comme ce qui est fait avec boost.multiprecision (qui correspond à ce que tu cherches à faire): profiter des ET pour reconnaitre certaines opérations en éliminer un max de temporaires.

Ok, si j'ai bien compris, j'abandonne les expressions template.

Du coup, j'en reviens au profilage. L'implémentation de mon test de primalité est d'abord un test de division (algorithme d'Euclide), puis un test de Miller-Rabin. La fonction mpz_probab_prime_p de GMP a une étape en plus entre les deux qui est un test de Baillie-PSW. J'ai regardé le code C et c'est un peu touffu à comprendre.

#include <chrono>
#include <iostream>

#include "Integer.h"

int main()
{
    auto const n(56062005704198360319209_z);

    auto const mpz_n{n.cast<mpz_class>()};
    auto t{std::chrono::steady_clock::now()};
    std::cout << mpz_probab_prime_p(mpz_n.get_mpz_t(), 25) << std::endl;
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - t).count() << " ms" << std::endl;

    t = std::chrono::steady_clock::now();
    std::cout << n.isPrime() << std::endl;
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - t).count() << " ms" << std::endl;

    return 0;
}

J'ai la sortie suivante pour le code ci-dessus :

1
0 ms
1
432202 ms

Le code de GMP est bien plus rapide que le mien que voici :

        CONSTEXPR int isPrime(size_t reps = 25) const
        {
            assert(reps);
            
            if (*this < 2)
                return 0;
            else if (*this == 2)
                return 2;
            else if(!(*this & 1))
                return 0;
            else if (this->template fits<unsigned int>())
            {
                auto p{std::equal_range(primes.begin(), primes.end(), this->template cast<unsigned int>())};

                if (p.first != primes.end() && *p.first != this->template cast<unsigned int>())
                    --p.first;
                
                if (p.first != p.second && *p.first == this->template cast<unsigned int>())
                    return 2;
            }
            
            auto isPrimeDivisible
            {
                [](Integer const& n, unsigned int prime) -> bool
                {
                    return !(n % prime);
                }
            };

            //Trial divisions

            auto const sqrtLimit(sqrt(*this));
            
            if (sqrtLimit < primes.back())        
            {
                std::atomic<bool> divisible(false);
        
                auto threadFunc
                {
                    [this, &divisible, &sqrtLimit, &isPrimeDivisible] (size_t start, size_t end) -> void
                    {
                        for (size_t i{start}; i < end && !divisible.load(); ++i)
                        {
                            if (primes[i] > sqrtLimit)
                                break;
                            
                            if (isPrimeDivisible(*this, primes[i]))
                            {
                                divisible.store(true);
                                return;
                            }
                        }
                    }
                };

                size_t const numThreads{std::thread::hardware_concurrency()};
                size_t const chunkSize{primes.size() / numThreads};
                std::vector<std::thread> threads;

                for (size_t i{0}; i < numThreads; ++i)
                {
                    size_t const start{i * chunkSize};
                    size_t const end{(i == numThreads - 1) ? primes.size() : (i + 1) * chunkSize};
                    threads.emplace_back(threadFunc, start, end);
                }

                for (auto& t : threads)
                    t.join();

                if (divisible.load())
                    return 0;
                
                if (sqrtLimit < primes.back())
                    return 2;
            }

            //Miller-Rabin tests

            auto s(*this - 1);

            while (!(s & 1))
                s >>= 1;

            auto reduction
            {
                [] (Integer const& t, Integer const& R, Integer const& n, Integer const& n_) -> Integer
                {
                    auto const m(((t % R) * n_) % R);
                    auto const x((t + m * n) / R);

                    if (x < n)
                        return x;
                    else
                        return x - n;
                }
            };

            auto redmulmod
            {
                [&reduction] (Integer const& a, Integer b, Integer const& n,
                              Integer const& R, Integer const& n_, Integer const& R2modn) -> Integer
                {
                    auto const reda(reduction(a * R2modn, R, n, n_));
                    auto const redb(reduction(b * R2modn, R, n, n_));
                    auto const redc(reduction(reda * redb, R, n, n_));

                    return reduction(redc, R, n, n_);
                }
            };

            auto mulmod
            {
                [] (Integer const& a, Integer b, Integer const& m) -> bool
                {
                    Integer x(0);
                    auto y{a % m};

                    while (b > 0)
                    {
                        if (b & 1)
                            x = (x + y) % m;

                        y <<= 1;
                        y %= m;
                        b >>= 1;
                    }

                    return x % m;
                }
            };

            auto modulo
            {
                [&redmulmod] (Integer const& base, Integer e, Integer const& m,
                              Integer const& R, Integer const& m_, Integer const& R2modm) -> Integer
                {
                    Integer x(1);
                    auto y{base};

                    while (e > 0)
                    {
                        if (e & 1)
                        {
                            auto const x_(x);
                            x = redmulmod(x, y, m, R, m_, R2modm);
                            while (x < 0)
                                x += m;
                            assert(x == (x_ * y) % m);
                        }

                        auto const y_(y);
                        y = redmulmod(y, y, m, R, m_, R2modm);
                        while (y < 0)
                            y += m;
                        assert(y == (y_ * y_) % m);
                        e >>= 1;
                    }

                    return x % m;
                }
            };

            auto const number(*this - 1);
            auto const& m(*this);
            Integer R(Integer(1) << m.number());

            assert(R > m);

            if (!(m & 1))
                ++R;

            while (!m.isCoprime(R))
            {
                if (!(m & 1))
                    --R;

                R <<= 1;

                if (!(m & 1))
                    ++R;
            }

            auto const R2modm((R * R) % m);
            Integer R_, m_;
            auto const d(gcdExtended(R, -m, R_, m_));

            assert(d.abs() == 1);
            assert(R * R_ - m * m_ == d);

            if (d == -1)
            {
                R_ = -R_;
                m_ = -m_;
            }
            
            {
                std::atomic<bool> divisible(false);
            
                auto threadFunc
                {
                    [this, &divisible, &modulo, &mulmod,
                     &R, &m_, &R2modm, &number, &s]
                    (size_t start, size_t end) -> void
                    {
                        for (size_t i{start}; i < end && !divisible.load(); ++i)
                        {
                            auto a(*this);
                            a.template setRandom<std::random_device>();
                            a.setPositive();
                            a = a % number + 1;

                            auto temp{s};
                            auto mod{modulo(a, temp, *this, R, m_, R2modm)};

                            while (temp != number && !mod && mod != number)
                            {
                                mod = mulmod(mod, mod, *this);
                                temp <<= 1;
                            }

                            if (mod != number && !(temp & 1))
                            {
                                divisible.store(true);
                                return;
                            }
                        }
                    }
                };
                
                size_t const numThreads{std::thread::hardware_concurrency()};
                size_t const chunkSize{reps / numThreads};
                std::vector<std::thread> threads;

                for (size_t i{0}; i < numThreads; ++i)
                {
                    size_t const start{i * chunkSize};
                    size_t const end{(i == numThreads - 1) ? reps : (i + 1) * chunkSize};
                    threads.emplace_back(threadFunc, start, end);
                }

                for (auto& t : threads)
                    t.join();

                if (divisible.load())
                    return 0;
            }

            return 1;
        }

Le code du test de Miller-Rabin est adapté d'ici : https://www.tutorialspoint.com/cplusplus-program-to-implement-the-rabin-miller-primality-test-to-check-if-a-given-number-is-prime.

Voici aussi le résultat du profilage :

Est-ce que vous auriez des idées pour faire aussi bien que GMP (sans prétention :-P) ? Ou du moins des idées pour améliorer ce qui met le plus de temps ?

-
Edité par P'tit Ju 4 février 2025 à 13:05:07

-
Edité par P'tit Ju 4 février 2025 à 18:46:09

Il faut minimiser le nombre de Integer construit, car les vector interne finissent par coûter cher à construire/détruire et à copier lorsque les tailles changent.

Par exemple, dans reduction, le bloc:

if (x < n)
  return x;
else
  return x - n;

Peut être transformé en

if (n < x)
  x -= n;
return x;

Pour éviter la création d'un Integer résultant de x-n.

Idem pour x = (x + y) % m; qui devient x += y; x %= m. Etc.

En fait, c'est sur ce genre de chose que les expressions template sont pas mal puisqu'elles peuvent faire ces transformations automatiquement. Mais comme détecter la réutilisation d'un identifiant est délicat, je préfère une approche à base d'expression externe. Un truc genre auto expr = ("x"_c = ("x"_c + "y"_c) % "m"_c); expr.compute("x"_c = x, "y"_c = y, "m"_c = m). Mais c'est beaucoup de boulot pour quelque chose qui ici se fait assez facilement à la main.

Après, il y a la réutilisation pure et simple des temporaires. Si on regarde modulo, il y un Integer x(1); construit en début de fonction, peuplé via différente opération qui vont faire des allocations puis supprimé au prochain tour de boucle du parent. Les allocations faîtes dans x pourraient être évitées en réutilisant la variable pour que les prochains tours de boucle ne le fassent plus. Cela veut dire conserver la variable comme un "buffer" et la fonction pourrait faire un x = 1 plutôt qu'une reconstruction complète (en supposant un operator= qui prend un entier, car il peut y avoir une construction cachée si les constructeurs ne sont pas marqués explicit).

> abandon des expressions templates 

Par curiosité, c’était quoi la raison de les employer ici ?  Représenter les grands nombres par des vecteurs d'entiers, de type restant à déterminer ?

Ou que les templates c'est des sortes de macros, et que le compilateur peut mieux optimiser le code après expansion, que si c'était des fonctions ?  

(Ou alors c'est juste pour avoir des messages d'erreur gratinés à la compilation ?) 

-
Edité par michelbillaud 5 février 2025 à 11:26:33

C'était moi qui avait suggéré les ET.

Un framework qui définit des classes mathématiques autour de structures à taille dynamique... il est impossible d'avoir des bonnes perfs dès que l'on va enchainer les opérateurs car cela va déclencher des allocations et libérations de vecteurs à tour de bras.

Les ET permettent d'analyser les expressions et de réduire les besoins en allocs & cie, de façon automagique -- ce que fait boost.multiprecision (je l'ai découvert après). Là où avec GMP je soupçonne qu'on va le faire en réfléchissant, et donc limiter les dégâts. Mais je me trompe peut-être.

Je me suis fait un exemple jouet pour voir l'optimisation sur les templates.

L'exemple: une class Int qui contient un entier (c'est original), avec essentiellement deux opérations :

• plus qui retourne un autre Int, 
• et add qui modifie en ajoutant, en ayant (maladroitement) créé un autre Int, puis extrait sa valeur.

Cette classe Int est une instantiation de GenInt :  typedef GenInt<int> Int;

#include <iostream>
/* un entier dans une boite */

template<typename T>
class GenInt {
    T val;
    public: 
        GenInt(T v);
        T value() const;
        GenInt<T> plus(const GenInt<T> &b) const;
        void add(const GenInt &b);
};

template<typename T>
GenInt<T>::GenInt(T v)
    : val{v}
{}

template<typename T>
T GenInt<T>::value() const
{
    return val;
}

template<typename T>
GenInt<T> GenInt<T>::plus(const GenInt<T> &b) const
{
    return {val + b.val};
}

template<typename T>
void GenInt<T>::add(const GenInt &b)
{
    val = plus(b).value();
}

typedef GenInt<int> Int;

int main() {
    Int a{123}, b{543};
    std::cout << a.value() << " + " << b.value();
    a.add(b);
    std::cout << " = " << a.value() << std::endl;

}

Si on regarde le code généré (g++ -O3), on voit que les objets ne sont même pas créés - les fonctions encore moins appelées -, et que la valeur 666 est directement calculée par la compilation

	movl	$123, %esi          # -- 123 --------
	pushq	%rbx
	.cfi_def_cfa_offset 24
	.cfi_offset 3, -24
	movq	%rbp, %rdi
	subq	$8, %rsp
	.cfi_def_cfa_offset 32
	call	_ZNSolsEi@PLT       # -- écriture
	movl	$3, %edx
	leaq	.LC0(%rip), %rsi
	movq	%rax, %rbx
	movq	%rax, %rdi
	call	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l@PLT
	movq	%rbx, %rdi
	movl	$543, %esi          # -- 543
	call	_ZNSolsEi@PLT       # -- écriture
	movq	%rbp, %rdi
	movl	$3, %edx
	leaq	.LC1(%rip), %rsi
	call	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l@PLT
	movq	%rbp, %rdi          # -- 666
	movl	$666, %esi          
	call	_ZNSolsEi@PLT       # -- écriture

Encore un effort d'optimisation et il aurait directement produit la chaine "123 + 543 = 666"

-
Edité par michelbillaud 5 février 2025 à 12:21:56

Il y a aussi std::valarray qui peut faire ce genre d'optimisation (expression template, proxy ou rien du tout, la norme n'impose rien).