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 :
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]
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 >
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 ]
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.
