logo le blog invivoo blanc

Réfléchir avant d’agir : à la recherche de la mémoire perdue (épisode 3)

10 avril 2020 | C++ | 0 comments

Contexte

Nous sommes dans le cadre d’un code legacy. Le but est de charger en mémoire une hyper-matrice creuse (une matrice à 3 dimensions) dont toutes les cases ne sont pas remplies. Chaque ligne de la matrice correspond à un scénario, les colonnes correspondent à un échéancier. Le groupe de valeurs (la 3ième dimension) est soit vide soit contient un vecteur de probabilités (5 valeurs flottantes allant de 0 à 1 avec une précision de 4 chiffres). Voici un exemple de ligne que l’on retrouverait dans le fichier :

Exemple de ligne
Exemple d’une ligne dans le fichier

On peut avoir des lignes totalement vides. Majoritairement, les colonnes contenant des quintuplés sont contigües mais exceptionnellement des valeurs vides peuvent s’intercaler entre des groupes de valeurs pleines…

Lors d’un calcul de risque, on est amené à charger jusqu’à une cinquantaine de fichiers de ce type en mémoire. Et dans le cas le plus défavorable on peut en charger une centaine.

Le code legacy

Voici le code tel que je l’ai trouvé :

#include <windows.h>
#include <psapi.h>
#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <time.h>

using namespace std;


SIZE_T getWorkingSize()
{
   HANDLE hProcess;
   PROCESS_MEMORY_COUNTERS_EX pmc;
   SIZE_T result = 0;
   hProcess = OpenProcess(PROCESS_QUERY_INFORMATION | PROCESS_VM_READ, FALSE, GetCurrentProcessId());
   if( NULL != hProcess )
   {
      if( GetProcessMemoryInfo(hProcess, (PROCESS_MEMORY_COUNTERS*)&pmc, sizeof(pmc)) )
      {
         result = pmc.WorkingSetSize;
      }
      CloseHandle(hProcess);
   }
   return result;
}


vector< vector< vector< double > > > tab;


size_t compute_size()
{
   size_t s =   sizeof( vector< vector< vector< double > > > )
              + tab.capacity() * sizeof( vector< vector< double > > );
   for( size_t i = 0; i < tab.size(); ++i )
   {
      s += sizeof( tab[ i ].capacity() * sizeof( vector< double > ) );
      for( size_t j = 0; j < tab[ i ].size(); ++j )
      {
         s += tab[ i ][ j ].capacity() * sizeof( double );
      }
   }
   return s;
}


const char *FILENAME = "C:\\personnel\\C++\\blog\\1-memory_management\\03\\data\\data.rec";


vector< string > split( const string &line )
{
   vector< string > vec;
   stringstream     s( line );
   string           col;

   while( getline( s, col, ';' ) )
   {
      vec.push_back( col );
   }
   return vec;
}


vector< double > split_vector( const string &line )
{
   vector< double > vec;
   stringstream     s( line );
   string           token;

   while( getline( s, token, ',' ) )
   {
      vec.push_back( std::atof( token.c_str() ) );
   }
   return vec;
}


vector< vector< double > > decompose( const string &line )
{
   vector< vector< double > > res;
   vector< string >           columns = split( line );

   for( auto it = columns.begin(); it != columns.end(); ++it )
   {
      if( it->empty() )
      {
         res.push_back( vector< double >() );
      }
      else
      {
         res.push_back( split_vector( *it ) );
      }
   }

   return res;
}


int main()
{
   ifstream f( FILENAME, ifstream::in );
   string   ligne; //Une variable pour stocker les lignes lues

   SIZE_T s1 = getWorkingSize();

   clock_t start = clock();
   while( getline( f, ligne ) )
   {
      vector< vector< double > > row = decompose( ligne );
      tab.push_back( row );
   }
   clock_t stop = clock();
   cout << ( double( stop - start ) / CLOCKS_PER_SEC ) << endl << endl << endl << flush;
   SIZE_T s2 = getWorkingSize();

   cout << "size/" << tab.capacity() << " / " << tab[0].capacity() << endl << endl;
   cout << "memory size = " << compute_size() << "    " << s2-s1 << endl << endl;

   system( "PAUSE" );
   return 0;
}

J’y ai rajouté les fonctions compute_size et getWorkingSize ainsi que les horloges pour mesurer le temps. L’exécution du code nous apprend les choses suivantes :

  • En release
    • Temps de la lecture : 0.1s
    • Taille supposée de la structure de données (vector<vector<vector<double>>>) : 634 072 octets
    • Mémoire allouée par le processus : 26 136 576 octets
  • En debug
    • Temps de la lecture : 0.439s
    • Taille supposée de la structure de données (vector<vector<vector<double>>>) : 634 072 octets
    • Mémoire allouée par le processus : 26 185 728 octets

Ce code legacy a le défaut d’allouer beaucoup de mémoire.

Réfléchir avant pour gagner en temps et en mémoire après

La première chose qui doit nous interpeller est le format de la donnée flottante utilisé dans le fichier : un nombre flottant allant de 0 à 1 avec 4 chiffres derrière la virgule… En d’autres termes on veut stocker un entier allant de 0 à 10 000 que l’on peut aisément stocker sur un ‘short’ (entier de 16 bits) : la donnée prendra 4 fois moins de place qu’avec un encodage en ‘double’. 

Le second point qui doit nous intéresser est le fait que pour chaque scénario (ligne de la matrice) il n’y a qu’un groupe quasi-contigu de colonnes non-vides. Il faut donc que nous réfléchissions à un moyen de stocker uniquement les informations utiles :

  • Le numéro de la première colonne non-vide
  • Le nombre de colonne non vide
  • Pour chaque colonne non-vide, le nombre de valeurs puis les valeurs

En jonglant avec des indirections dans des tableaux, on va pouvoir garantir un stockage optimal. Nous allons créer une classe Matrix qui servira d’utilitaire contenant la lecture ainsi que le stockage.

3.1 – L’interface de Matrix

#pragma once
#include <vector>


class Matrix
{
   public:
      /** @brief Constructor
       *
       */
      Matrix();



      /** @brief Destructor
       *
       */
      ~Matrix();



      /** @brief Real size
       *
       *  @return the real size
       */
      size_t real_size() const;



      /** @brief Compute size
       *
       *  @return the size
       */
      size_t compute_size() const;



      /** @brief Read file
       *
       *  @param filename  name of the file to read
       *
       *  @return true if successful, else false
       */
      bool read_file( const char *filename );



      /** @brief Get data
       *
       *  @param rowId     0-based row identifier
       *  @param columnId  0-based column identifier
       *  @param data      data
       *
       *  @return true if successful, else false
       */
      bool get_data( int                    rowId,
                     int                    columnId,
                     std::vector< double > &data ) const;



      /** @brief Dump
       *
       */
      void dump( const char *filename );



   private:
      struct Row
      {
         int   IndexFirstSize; //!< index inside  m_ColumnSize
         int   IndexFirstValue; //!< index inside m_Values
         short FirstNotNullColumnId;
         short NotNullColumnCount;

         Row();
      };



      /** @brief Decompose line
       *
       *  @param buffer  line to decompose
       */
      void decompose_line( char *buffer );



   private:
      std::vector< Row >   m_Rows;
      std::vector< char >  m_ColumnSize;
      std::vector< short > m_Values;
};

L’implémentation de Matrix

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include "matrix.hpp"


Matrix::Row::Row() :
   IndexFirstSize      ( -1 ),
   IndexFirstValue     ( -1 ),
   FirstNotNullColumnId(  0 ),
   NotNullColumnCount  (  0 )
{
}


Matrix::Matrix()
{
   m_Rows.reserve( 5000 );
   m_ColumnSize.reserve( 30000 );
   m_Values.reserve( 25000 );
}



Matrix::~Matrix()
{
}



size_t Matrix::real_size() const
{
   return   sizeof( std::vector< Row > ) + m_Rows.size() * sizeof( Row )
          + sizeof( std::vector< char > ) + m_ColumnSize.size() * sizeof( char )
          + sizeof( std::vector< short > ) + m_Values.size() * sizeof( short );
}



size_t Matrix::compute_size() const
{
   return   sizeof( std::vector< Row > ) + m_Rows.capacity() * sizeof( Row )
          + sizeof( std::vector< char > ) + m_ColumnSize.capacity() * sizeof( char )
          + sizeof( std::vector< short > ) + m_Values.capacity() * sizeof( short );
}



bool Matrix::get_data( int                    rowId,
                       int                    columnId,
                       std::vector< double > &data ) const
{
   // verify the rowId
   data.clear();
   if( ( rowId < 0 ) || ( int( m_Rows.size() ) <= rowId ) )
   {
      return false;
   }

   // case empty data
   const Row &row = m_Rows[ rowId ];
   if(    ( columnId < row.FirstNotNullColumnId )
       || ( columnId >= row.FirstNotNullColumnId + row.NotNullColumnCount ) )
   {
      return true;
   }

   //
   int index1 = row.IndexFirstSize + columnId - row.FirstNotNullColumnId;
   int index2 = row.IndexFirstValue;
   for( int i = 0; i < columnId - row.FirstNotNullColumnId; ++i )
   {
      index2 += m_ColumnSize[ i ];
   }
   for( int i = 0; i < m_ColumnSize[ index1 ]; ++i )
   {
      data.push_back( double( m_Values[ index2 + i ] ) * 0.0001 );
   }
   return true;
}



bool Matrix::read_file( const char *filename )
{
   // local variables
   FILE *pFile;
   char  buffer[ 32768 ];

   // open the file
   pFile = fopen( filename, "r" );
   if( nullptr == pFile )
   {
      return false;
   }

   // loop on file
   while( !feof( pFile ) )
   {
      // read row
      if( nullptr == fgets( buffer, sizeof( buffer ), pFile ) )
      {
         bool eof = feof( pFile );
         fclose( pFile );
         return eof;
      }

      // decompose line
      decompose_line( buffer );
   }

   // finalize
   fclose( pFile );
   return true;
}



void Matrix::decompose_line( char *buffer )
{
   // local variables
   char   *end;
   char   *ptr = buffer + strlen( buffer ) - 1;
   double  x;
   int     i;
   short   s;
   Row     row;

   // remove last '
   while(    ( buffer <= ptr )
          && (    ( ';'  == *ptr )
               || ( '\n' == *ptr )
               || ( '\r' == *ptr ) ) )
   {
      *ptr-- = 0;
   }
   if( 0 == *buffer )
   {
      row.FirstNotNullColumnId = -1;
      m_Rows.push_back( row );
      return;
   }


   // get first not null value
   ptr = buffer;
   while( ';' == *ptr ) ptr++;
   row.FirstNotNullColumnId = int( ptr - buffer );
   row.IndexFirstSize       = m_ColumnSize.size();
   row.IndexFirstValue      = m_Values.size();

   // get the values
   i = 0;
   while( 0 != *ptr )
   {
      switch( *ptr )
      {
         case ';':
         {
            m_ColumnSize.push_back( i );
            row.NotNullColumnCount += 1;
            i = 0;
            ++ptr;
            break;
         }

         case ',':
         {
            ++ptr;
            break;
         }

         default:
         {
            x = strtod( ptr, &end );
            s = short( 10000 * x + 0.5 );
            m_Values.push_back( s );
            ++i;
            ptr = end;
            break;
         }
      }
   }
   row.NotNullColumnCount += 1;
   m_ColumnSize.push_back( i );
   m_Rows.push_back( row );
}



void Matrix::dump( const char *filename )
{
   FILE *pFile = fopen( filename, "w" );

   for( auto it = m_Rows.begin(); it != m_Rows.end(); ++it )
   {
      if( it->FirstNotNullColumnId < 0 )
      {
         for( int i =0; i < 199; ++i )
         {
            fprintf( pFile, ";" );
         }
         fprintf( pFile, "\n" );
         continue;
      }

      for( int i =0; i < it->FirstNotNullColumnId; ++i )
      {
         fprintf( pFile, ";" );
      }

      int index = it->IndexFirstValue;
      for( int i = 0; i < it->NotNullColumnCount; ++i )
      {
         if( i != 0 )
         {
            fprintf( pFile, ";" );
         }
         int count = int( m_ColumnSize[ it->IndexFirstSize + i ] );
         for( int j = 0; j < count; ++j, ++index )
         {
            if( j != 0 )
            {
               fprintf( pFile, "," );
            }
            fprintf( pFile, "%.4lf", double( m_Values[ index ] ) * 0.0001 );
         }
      }

      for( int i = it->FirstNotNullColumnId+it->NotNullColumnCount; i < 200; ++i )
      {
         fprintf( pFile, ";" );
      }
      fprintf( pFile, "\n" );
   }

   fclose( pFile );
}

3.3 – Le résultat

L’exécution du code nous apprend les choses suivantes :

  • En release
    • Temps de la lecture : 0.015s
    • Taille supposée de la structure de données : 190 072 octets
    • Mémoire allouée par le processus : 253 952 octets
  • En debug
    • Temps de la lecture : 0.046s
    • Taille supposée de la structure de données : 190 072 octets
    • Mémoire allouée par le processus : 253 952 octets

Les temps de lecture sont de l’ordre de 10 fois plus rapide en debug et en release. Pour la mémoire le processus en alloue 100 fois moins environ. Cependant, l’accès aux données pour un rowId et un columnId donné est plus complexe que dans le cas du code legacy. On gagne d’un côté mais on perd de l’autre… Développer est un jeu d’équilibrisme

4 – Conclusion

En prenant le temps de réfléchir un peu au problème avant de coder on peut s’épargner de mauvaises contre-performances mémoire. Bien choisir ses structures de données est primordial tant pour les performances initiales que pour l’évolutivité du code.