Archivo

Entradas Etiquetadas ‘memoria’

Destructores virtuales en C++

Lunes, 5 de Diciembre de 2011 Gaspar Fernández Sin comentarios

papel destruido

Muchas veces, cuando leemos código de otras personas, hemos visto destructores declarados como virtual en algunas clases. Es una de esas cosas que si hacemos siempre no pasa nada, pero si no hacemos nunca, en ocasiones nos llevamos sorpresas; pero muchos desarrolladores optan por poner sólo en los casos justos.

¿ Para qué valían los métodos virtual ?

Eso está en un post anterior, pero básicamente valen para que las subclases tengan un método propio que se llame de la misma forma que el método declarado como virtual. Aunque cuando se trata de los destructores… en cada clase tendremos un destructor que se llama como mi clase, por lo que parece que esto no tiene demasiado sentido. Aunque está relacionado.

¡Demostración de la destrucción!

Aunque esto difiera de cómo construiríamos esta estructura en realidad, vamos a imaginarnos que nuestras clases formarán un edificio. Tendremos la clase Edificio, la clase Planta, y la clase Habitación, donde Planta será subclase de Edificio y Habitación subclase de Planta.

Para construir la habitación, todo va bien, primero creamos el Edificio, luego la Planta y finalmente la Habitación; pero para destruirlo todo, depende del tipo de objeto que creemos y, en ocasiones, como con las Mascotas, nos interesará declarar los objetos con la clase padre (o superclase) y a la hora de construirlo hacerlo con la clase hija (o subclase) correspondiente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>

using namespace std;

class Edificio
{
public:
  Edificio()
  {
    cout << "Se construye el edificio" << endl;
  }

  virtual ~Edificio()
  {
    cout << "Sacamos las bombillas del ascensor" << endl;
    cout << "Se destruye el edificio" << endl;
  }

private:
};

class Planta : public Edificio
{
public:
  Planta()
  {
    cout << "Se construye la planta" << endl;
  }

  ~Planta()
  {
    cout << "Sacamos los muebles de los pasillos" << endl;
    cout << "Se destruye la planta" << endl;
  }

private:
};

class Habitacion : public Planta
{
public:
  Habitacion()
  {
    cout << "Se construye la habitación" << endl;
  }

  ~Habitacion()
  {
    cout << "Saco las cosas de la habitación "<<endl;
    cout << "Se destruye la habitación" << endl;
  }

private:
};


int main()
{

  Edificio *h = new Habitacion();

  delete h;
  return 0;
}

La respuesta esperada es la siguiente:

Se construye el edificio
Se construye la planta
Se construye la habitación
Saco las cosas de la habitación
Se destruye la habitación
Sacamos los muebles de los pasillos
Se destruye la planta
Sacamos las bombillas del ascensor
Se destruye el edificio

Pero si quitamos el virtual, la respuesta será la siguiente:

Se construye el edificio
Se construye la planta
Se construye la habitación
Sacamos las bombillas del ascensor
Se destruye el edificio

Muchas veces, los destructores no tendrán nada, cuando no hay nada que hacer, pero imaginad que el Edificio reserva memoria para almacenar ciertos datos, la Planta, reserva también memoria para algo, y la Habitación por su parte también, en ese caso sería necesario pasar por todos los destructores para que cada uno libere su región de información. Así evitamos memory leaks.

En el caso de poner virtual en todos los destructores, no pasa nada.

Más ejemplos

Otro ejemplo puede ser cuando queremos crear un árbol, y los nodos pueden ser de dos tipos (nodo con ramificaciones, o sin ellas):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Nodo
{
public:
  Nodo(string n)
  {
    nombre=n;
    cout << "Construyo el nodo "<<nombre<<endl;
  }

  virtual ~Nodo()
  {
    cout<< "Destruyo el nodo "<<nombre<<endl;
  }
 
  virtual void print(int espacios)
  {
    cout << "Nodo: "<<nombre<<endl;
  }

public:
  string nombre;
};

class Rama: public Nodo
{
public:
  Rama(string n):Nodo(n)
  {  
    cout << "Construyo la rama "<<n<<endl;
  }

  ~Rama()
  {
    while (!nodos.empty())
      {
    delete nodos.back();
    nodos.pop_back();
      }
    cout <<"Destruyo la rama " << nombre << endl;
  }

  void addNodo(Nodo *n)
  {
    nodos.push_back(n);
  }

  void print()
  {
    cout << "Rama: "<<nombre<<endl;
    for (vector<Nodo*>::iterator it=nodos.begin(); it!=nodos.end(); ++it)
      {
    (*it)->print();
      }
  }

public:
  vector<Nodo*> nodos;
};

int main()
{
  Nodo *arbol= new Rama("main");

  Nodo *nodo= new Nodo("Abuelo sin nietos");
  static_cast<Rama*>(arbol)->addNodo(nodo);
  nodo= new Rama("Abuelo 2");
  static_cast<Rama*>(arbol)->addNodo(nodo);
  Nodo *nodo2= new Nodo("Hijo 1");
  static_cast<Rama*>(nodo)->addNodo(nodo2);
  nodo2= new Rama("Padre 1");
  static_cast<Rama*>(nodo)->addNodo(nodo2);
  Nodo *nodo3= new Nodo("Hijo 3");
  static_cast<Rama*>(nodo2)->addNodo(nodo3);
  nodo3= new Nodo("Hijo 4");
  static_cast<Rama*>(nodo2)->addNodo(nodo3);
  nodo3= new Nodo("Hijo 5");
  static_cast<Rama*>(nodo2)->addNodo(nodo3);
  nodo3= new Nodo("Hijo 6");
  static_cast<Rama*>(nodo2)->addNodo(nodo3);
  nodo2= new Nodo("Hijo 2");
  static_cast<Rama*>(nodo)->addNodo(nodo2);

  nodo= new Rama("Abuelo 3");
  static_cast<Rama*>(arbol)->addNodo(nodo);
  nodo2= new Nodo("Hijo 7");
  static_cast<Rama*>(nodo)->addNodo(nodo2);
  nodo2= new Rama("Padre 2");
  static_cast<Rama*>(nodo)->addNodo(nodo2);
  nodo3= new Nodo("Hijo 8");
  static_cast<Rama*>(nodo2)->addNodo(nodo3);

  cout << endl;
  arbol->print();
  cout << endl << endl;

  delete arbol;
}

En este caso, si quitamos el virtual al destructor, podemos ver que sólo se destruye el nodo main, quedándose todo lo demás en memoria.

Otros ejemplos de este uso pueden ser:

  • Sistemas que mantentan archivos, sockets, pipes abiertos desde la superclase (todo tiene que ser cerrado)
  • Instancias cuyas superclases tengan cadenas char* , tenemos que liberar todas las cadenas
  • Estoy abierto a sugerencias en los comentarios

Foto:  <a href=”http://www.flickr.com/photos/randomurl/445352972/”>WagsomeDog</a> (Flickr) Compartido con CC-by a 28/Nov/2011

Categories: C/C++, Clases particulares Tags: , , , , , , , ,

[Arduino] Utilizando la memoria Flash en lugar de la SRAM para constantes

Viernes, 2 de Diciembre de 2011 Gaspar Fernández Sin comentarios

temp_ardublogOtra cosa no, pero los Arduino no son conocidos por su gran memoria RAM, y es que, por ejemplo en la serie Diecimila, con el Atmega168 tenemos 1Kb de RAM, con el Atmega328, hay 2Kb de RAM, aunque puede que para algunos de nuestros programas nos quedemos un poco cortos.

Una gran ayuda para esto puede ser utilizar las constantes que cree nuestro programa, en forma numérica de tabla de valores constante, o de cadena de caracteres, por ejemplo, para enviar mensajes predeterminados por el Serial, decir el nombre de la aplicación, la versión, etc.

PROGMEM

Será una macro creada para almacenar datos en espacio de programa. El programa no ocupará más, y tendremos más memoria libre para utilizar y reservar a nuestro antojo.

Antes de utilizar PROGMEM, debemos hacer

1
#include <avr/pgmspace.h>

y así poder tener acceso a todas las funciones adicionales que nos proporciona esta biblioteca.

Viendo la memoria libre

Hay una función que encontré aquí, un poco chapucera, pero eficiente (en la web hay mejores funciones, pero esta es la primera que encontramos), y que calcula el espacio que queda en la memoria (en bytes):

1
2
3
4
5
6
7
8
9
10
11
12
13
// this function will return the number of bytes currently free in RAM
// written by David A. Mellis
// based on code by Rob Faludi http://www.faludi.com
int availableMemory() {
  int size = 1024; // Use 2048 with ATmega328
  byte *buf;

  while ((buf = (byte *) malloc(--size)) == NULL);

  free(buf);

  return size;
}

Con esta función podemos ver la memoria que nos queda:

PROGMEM CON NÚMEROS (int, float, char, byte, unsingeds…)

Para probarlo, lo mejor es ver una demostración (no he incluido la función availableMemory(), copiad y pegad de arriba):

1
2
3
4
5
6
7
8
9
10
11
12
void setup()
{
  Serial.begin(9600);
}

PROGMEM int numero=25;
void loop()
{
  Serial.println(numero, DEC);
  Serial.println(availableMemory(), DEC);
  delay(1000);
}

Podemos ver cómo numero está declarado como PROGMEM int, bien, eliminemos el PROGMEM y vemos qué hace, ¡tenemos 2 bytes menos libres! Aquí demostramos que de verdad no estamos utilizando la RAM.

Arrays de números

Ahora viene lo bueno, no hacemos nada si sólo almacenamos en Flash valores, por separado, lo interesante es poder almacenar arrays con lo que tendremos muchas más posibilidades.
Por ejemplo, podemos hacer:

1
2
3
4
5
6
7
8
9
10
11
12
PROGMEM int numeros[]={10, 29, 38, 47, 56, 64, 73, 82, 91, 0};

void loop()
{
  static int pos=0;
  Serial.println(pgm_read_word(&numeros[pos++]));
  Serial.println(availableMemory(), DEC);
  if (pos==10)
    pos=0;

  delay(1000);
}

Cada segundo mostrará por pantalla un número del array de enteros, y todos estarán en Flash, el coste de eso será de unos 100bytes más en el binario que, por tanto también irá a Flash, además de algunos ciclos de procesador; aunque en este caso, importa más la memoria.

He utilizado pgm_read_word() porque el array es de enteros (2 bytes = 1 word), si nuestra variable fuera de 1 byte (char, byte) se podrá utilizar pgm_read_byte() y si la variable es de 4 bytes (long) podremos utilizar pgm_read_dword(), para variables tipo float tenemos de igual manera pgm_read_float().

Cadenas de caracteres sin buffer

Para escribir cadenas de caracteres, lo mejor es utilizar un buffer (pero ya estamos gastando memoria), por tanto vamos a hacer un ejemplo para imprimir por el Serial sin necesidad de utilizar buffer:

1
2
3
4
5
6
7
8
9
10
11
12
13
char mens[] PROGMEM = "Hola mundo cruel y despiadado";

void loop()
{
  char *mem=mens;

  while (pgm_read_byte(mem) != 0x00) /* Comparamos con \0, un terminador */
    Serial.print(pgm_read_byte(mem++));
  Serial.println();

  Serial.println(availableMemory());
  delay(1000);
}

Podemos hacer el mensaje más largo, que seguimos consumiendo la misma cantidad de memorial. Para imprimir por el Serial con esta técnica podemos crear una función (printpgm()):

1
2
3
4
5
6
7
8
void printpgm(char *texto)
{
  char *mem=texto;

  while (pgm_read_byte(mem) != 0x00) /* Comparamos con \0, un terminador */
    Serial.print(pgm_read_byte(mem++));
  Serial.println();
}

o como comentan aquí, modificar la clase HardwareSerial para incluir un método que imprima cadenas de caracteres procedentes de la memoria de programa.
Y creando estas funciones nos llevamos alguna que otra sorpresa en memoria libre (aunque pequeña).

Categories: Arduino, C/C++ Tags: , , , , , , , , , , , ,

Listas enlazadas en Arduino (primera versión)

Miércoles, 30 de Noviembre de 2011 Gaspar Fernández Sin comentarios

Es parte de un proyecto personal que quiero compartir. Se trata de una clase para utilizar listas enlazadas desde Arduino, aunque la memoria RAM de estos bichillos no sea gran cosa (1K para la versión Diecimila), puede dar para mucho, y es que hay ocasiones en las que podemos necesitar esta flexibilidad a la hora de almacenar y acceder a la información (aunque no pueda ser mucha).

La clase ha sido desarrollada utilizando templates, por lo que podréis particularizar esta clase para cualquier tipo de dato que estéis manejando. Declarando la lista de la siguiente forma:

1
LList <tipo> lista;

Antes de dar el código, hagamos algunas operaciones, vamos a ver lo que podemos hacer con 1K (vale con 600 bytes libres):

  • Con un tipo int, cada nodo ocupará 4 bytes: 600 / 4 = 150 nodos (alguno menos en realidad). Pero estos nodos pueden indicar posiciones en un mapa, un pequeño informe de lo que ha transcurrido, lecturas, estado de periféricos, etc
  • Con un tipo:
    1
    2
    3
    4
    5
    struct Map
    {
      int key;
      int value;
    }

    : podemos almacenar 600/6 = 100 elementos con clave y valor, por ejemplo, una matriz o vector disperso que nos pueden ayudar para un cálculo matemático

  • Lo malo son las cadenas, no podemos escribir un libro, pero si hacemos un tipo que almacene unas 28 letras, cuyo nodo ocupará 30 bytes, podremos almacenar 600/30=20 mensajes distintos, aunque recomiendo que esos mensajes sean generados por el programa, ya que si los mensajes son predefinidos, podemos almacenarlos en la memoria flash, que tendremos más sitio.

Ahí va el código para los copy-paste aunque el archivo lo podéis bajar de aquí (9.5Kb). Por cierto, al final del archivo hay un código de ejemplo para probar que todo funcione bien.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
/**
*************************************************************
* @file ArduinoList.pde
* Another implementation of linked lists to use in Arduino.
*    Copyright (C) 2011 Gaspar Fernández
*
*    This program is free software: you can redistribute it and/or modify
*    it under the terms of the GNU General Public License as published by
*    the Free Software Foundation, either version 3 of the License, or
*    (at your option) any later version.
*
*    This program is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*    GNU General Public License for more details.
*
*    You should have received a copy of the GNU General Public License
*    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*
* @brief Linked list implementation for Arduino
*
* Features:
*   - Can access to head and tail directly
*   - Can pop back and front from this class
*   - Can access any item from the item number
*   - Can set a callback function when an error occurs
*
* @author Gaspar Fernández <blakeyed@totaki.com>
* @web http://totaki.com/poesiabinaria
* @version 0.1
* @date 27 nov 2011
* Change history
*
* To-do:
*   - Better control over non-critical errors, maybe another callback
*   - Pre-defined error methods: by serial, by output leds...
*************************************************************/

#define LLIST_ERROR_NOMEMORY     1 // Not enough memory to insert element
#define LLIST_ERROR_NOTAIL       2 // Can't get last items
#define LLIST_ERROR_NOFRONT      3 // Can't get head items
#define LLIST_ERROR_NOITEMS      4 // List empty, can't read items
#define LLIST_ERROR_NEITEMS      5 // Not enough items (pos>=sz)

template <typename Type>
class LList
{
public:
  typedef void (*ErrorCallback)(int);

  // We can add more error types
  enum ListErrorType
    {
      NO_ERROR_REPORTING,   // No error reporting
      CALLBACK          // Errors will trigger a callback
    };

  // Destruction. Clear data
  ~LList();

  // Initialization
  LList();

  // Inserts new item in the last position
  void push_back(const Type item);
  // Is the list empty?
  inline bool isEmpty() const;
  // Returns the size of the list
  inline int size();
  // Returns the last item
  inline Type back();
  // Returns the first item
  inline Type front();
  // Return the last item and delete it
  Type pop_back();
  // Return the first item and delete it
  Type pop_front();

  // Get the item at position pos
  Type getElement(unsigned pos);
  // Insert a new item at position pos
  void insert(int pos, Type item);
  // set error callback function
  void setErrorCallback(ErrorCallback cback);
  // no error reporting
  void setNoErrorReporting();
  // clears the list
  void clear();
private:
  // Reports an error
  void report_error(int err);
 
  // Deletes a list when there is only one element
  void delete_list();

  typedef struct node
  {
    Type item;
    node *next;
  } node;

  node *head;           // Pointer to the head
  node *tail;           // Pointer to the tail
  int sz;           // List size
  ListErrorType errorType; 
  ErrorCallback ecback;     // Callback when reporting an error
};

template <typename Type>
LList<Type>::LList()
{
  head=NULL;
  tail=NULL;
  sz=0;
  errorType=NO_ERROR_REPORTING;
}

template <typename Type>
LList<Type>::~LList()
{
  clear();          // Clears the list before destroying
}

template <typename Type>
void LList<Type>::push_back(const Type item)
{
  node *aux=tail;
 
  // Reserve memory for a new node
  tail=(node*)malloc(sizeof(node));
  if (tail==NULL)
    {
      report_error(LLIST_ERROR_NOMEMORY);
      return;
    }

  // Stores the item information
  tail->item=item;
  tail->next=NULL;

  // Link to the list
  if (isEmpty())
    head=tail;
  else
    aux->next=tail;

  sz++;

}

template <typename Type>
bool LList<Type>::isEmpty() const
{
  return (sz==0);       // (sz==0) = EMPTY
}

template <typename Type>
int LList<Type>::size()
{
  return sz;
}

template <typename Type>
inline Type LList<Type>::back()
{
  if (isEmpty())        // List empty = No last item
    {
      Type t;
      report_error(LLIST_ERROR_NOTAIL);
      return t;
    }

  return tail->item;
}

template <typename Type>
inline Type LList<Type>::front()
{
  if (isEmpty())        // List empty = No first item
    {
      Type t;
      report_error(LLIST_ERROR_NOFRONT);
      return t;
    }

  return head->item;
}

template <typename Type>
Type LList<Type>::pop_back()
{
  node *aux=head;
  Type t;

  if (isEmpty())        // List empty = No last item
    {
      report_error(LLIST_ERROR_NOTAIL);
      return t;
    }
 
  if (head==tail)       // If there is only 1 item
    {
      t=head->item;
      delete_list();
      return t;
    }
  else
    {               // More than one item
      while (aux->next!=tail)   // Searches for the item previous to the last
    aux=aux->next;
     
      t=tail->item;     // I will return the tail item
      free(tail);      
      tail=aux;         // Define the new tail
      tail->next=NULL;
      sz--;         // 1 item less

      return t;
    }
}

template <typename Type>
Type LList<Type>::pop_front()
{
  Type t;
  node *aux=head;
 
  if (isEmpty())        // List empty = No head
    {
      report_error(LLIST_ERROR_NOFRONT);
      return t;
    }

  t=aux->item;          // I will return the head
  head=head->next;      // The new head is the item after the head
  free(aux);
  if (head==NULL)       // If I had deleted the last item, replace the tail
    tail=NULL;          // too.
  sz--;

  return t;
}

template <typename Type>
void LList<Type>::delete_list()
{
  free(head);           // I will call this method when deleting
  head=NULL;            // a list with only one element, so all
  tail=NULL;            // the variables are set.
  sz=0;
}

template <typename Type>
void LList<Type>::insert(int pos, Type item)
{
  node *newitem;
  node *aux=head;
  int i;

  // Allocate memory for the new item
  newitem=(node*)malloc(sizeof(node));
  if (newitem==NULL)
    {
      report_error(LLIST_ERROR_NOMEMORY);
      return;
    }
  // Stores the item information
  newitem->item=item;
  newitem->next=NULL;

  // Link the item to the list
  if (isEmpty())
    {               // If the list is empty there will be only
      head=newitem;     // one item, so it will be the head and the
      tail=newitem;     // tail.
    }
  else if (pos==0)      // If the item is going to be inserted at the beginning
    {
      newitem->next=head;   // we will move the head
      head=newitem;
    }
  else if (pos>=sz)     // If the position is greater than the last item's position
    {               // it will be inserted after this item, at the tail.
      tail->next=newitem;      
      tail=newitem;
    }
  else
    {               // If not, we will have to find the position of the
      i=0;          // previous item to link its next pointer to the new
      while (i<pos-1)       // element.
    {
      aux=aux->next;
      ++i;
    }
      newitem->next=aux->next;  // And then link the next pointer of our new element
      aux->next=newitem;    // to where the next pointer of the previour element
    }               // was pointing.
  sz++;
}

template <typename Type>
Type LList<Type>::getElement(unsigned pos)
{
  int i=0;
  Type t;
  node *aux=head;

  if (isEmpty())        // If the list is empty = No data
    {
      report_error(LLIST_ERROR_NOITEMS);
      return t;
    }

  if (pos>=sz)          // If the item asked for is greater than the
    {               // last item's position. There is no valid element
      report_error(LLIST_ERROR_NEITEMS);
      return t;
    }
 
  if (pos==sz-1)        // If the item we asked for is the last, we can
    return tail->item;      // return it inmediately


  while (i<pos)         // If not, we must look for it
    {
      aux=aux->next;
      i++;
    }
  return aux->item;
}

template <typename Type>
void LList<Type>::setErrorCallback(ErrorCallback cback)
{
  ecback=cback;         // This method sets the error callback to invoke
  errorType=CALLBACK;       // when an error occurs.
}

template <typename Type>
void LList<Type>::report_error(int err)
{
  if (errorType==CALLBACK)  // If the error reporting is through a callback,
    {               // call it.
      ecback(err);
    }
}

template <typename Type>
void LList<Type>::clear()
{
  node *aux;

  while (head!=NULL)        // Delete all elements
    {
      aux=head;
      head=head->next;
      free(aux);
    }
 
  tail=NULL;            // Restore variable stats
  sz=0;
}  

template <typename Type>
void LList<Type>::setNoErrorReporting()
{
  errorType=NO_ERROR_REPORTING;
}

// Test program
// LList<int> l;

// void blink(int err)
// {
//   while (1)
//     {
//       digitalWrite(11,HIGH);
//       delay(1000);
//       digitalWrite(11, LOW);
//       delay(1000);  
//     }
// }

// void setup()
// {
//   pinMode(11, OUTPUT);
//   Serial.begin(9600);
//   l.setErrorCallback(blink);
//   l.push_back(45);
//   l.push_back(42);
//   l.push_back(47);
//   l.push_back(89);
//   l.insert(0, 33);
//   l.insert(1, 53);
//   l.insert(9, 73);
//   // 33
//   // 53
//   // 45
//   // 42
//   // 47
//   // 89
//   // 73
// }

// void loop()
// {
//   char r;
//   if (Serial.available()>0)
//     {
//       while (Serial.available()>0)
//  {
//    r=Serial.read();
//    delayMicroseconds(10000);
//  }

//       for (unsigned i=0; i<l.size(); i++)
//  {
//    Serial.println(l.getElement(i), DEC);
//  }
//       Serial.print("Elements: ");
//       Serial.println(l.size(), DEC);
//       Serial.print("Last: ");
//       Serial.println(l.pop_front(), DEC);
//     }
// }
Categories: Arduino, C/C++, Descarga disponible Tags: , , , , , , , , , , , , ,

Iniciación a los memory leaks [ejemplos en C++]

Lunes, 28 de Noviembre de 2011 Gaspar Fernández Sin comentarios

leak

Hablemos de un fenómeno que nos afecta, sobre todo en desarrollos que están en ejecución durante mucho tiempo, pero , y es que, debido a la mala gestión de la memoria podemos llegar a consumir más de lo necesario y podemos volver loco al sistema operativo utilizando la memoria virtual para darnos el espacio que necesitamos.

Los memory leaks son fugas de memoria debidas a que hemos pedido un cierto espacio de memoria durante la ejecución de nuestro programa, la hemos usado y cuando hemos dejado de usarla, no la hemos liberado, por tanto estamos ocupando más de lo que necesitamos y acaparando recursos; un ejemplo de esto son esos procesos o programas que tenemos arrancados durante varios días, y cuanto más tiempo llevan arrancados más memoria ocupan (a veces es necesario, pero otras veces, la mayoría, no).

Antes de iniciarnos en la creación de un programa acerca de lo que no debemos hacer, vamos a hacerlo bien, y echaremos un vistazo a un artículo sobre el Out Of Memory Killer (desconozco si Windows tiene algo parecido, tal vez instalando alguna aplicación), que será una utilidad de nuestro kernel que matará el proceso cuando esté consumiendo mucha memoria, o nos permitirá matarlo fácilmente con las teclas (Alt+SysRq o imprimir pantalla+F). Con unas líneas antes de nuestro programa, nos podemos evitar un disgusto, como puede ser un reinicio de sistema mientras hacemos pruebas, y puede que estemos ejecutando algo útil.

¡Precaución!

Si vemos que nuestro proceso hace que el sistema vaya muy lento, será porque en lugar de utilizar nuestra RAM, estará usando la memoria virtual de forma intensa, esta memoria es mucho más lenta que nuestra RAM, si hemos entendido lo que quiero demostrar, podemos parar el proceso gracias al OOM Killer de antes con Alt+SysRq+F, pero sólo pulsa una vez las teclas, aunque veamos que no nos hace mucho caso, el sistema tarda un tiempo en volver a recolocar toda la información y limpiar la memoria del proceso. Si pulsamos más veces, lo mismo terminamos matando el servidor gráfico o algún proceso importante, y no queremos eso.

Ajustando OOM Killer

Para todo eso, debemos incluir el siguiente código (al final pondré todo el programa, pero primero lo analizamos por separado), el objetivo es escribir el valor 15 sobre el fichero /proc/PID/oom_adj:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void error(const char *mens)
{
  cerr << "ERROR: ("<<mens<<") errno: "<<errno<<": "<<strerror(errno)<<endl;
  exit (1);
}

void ajusta_oom()
{
  ofstream fi;
  char nom[30];

  // Obtenemos el nombre del fichero, aunque estemos haciéndolo
  // a lo C++, uso sprintf() aquí porque es más rápido.
  sprintf(nom, "/proc/%d/oom_adj", getpid());

  // Abrimos el fichero
  fi.open(nom);
  if (fi.fail())
    error("No puedo abrir oom_adj");

  // Escribimos 15 en el fichero, para dar más "apeletas de muerte"
  // a este proceso. Ver:
  // http://totaki.com/poesiabinaria/2010/04/cuando-un-proceso-se-come-la-memoria-de-nuestro-sistema/
  fi<<"15";
  if (fi.fail())
    error("No puedo escribir oom_adj");

  fi.close();
}

Gastando memoria

Para esta parte hay que tener cuidado, ya que depende de la RAM que tengamos cada uno, yo he hecho esto en un equipo con 2GB de RAM, hasta que se ha vuelto extremadamente lento. Aunque el objetivo es que veamos la memoria que está actualmente en consumo. Podemos utilizar el comando free() en paralelo con el programa para ver que cada vez tenemos más memoria consumida, cuando no deberíamos, porque la intuición nos diría que cuando salimos de la función todo lo reservado se libera, pero no es así.
En los sistemas operativos actuales no podremos ponernos a reservar memoria sin control, ya que el SO casi siempre nos la dará (aunque no disponga de ella, dejando el marrón al gestor de memoria del futuro), si de verdad queremos reservar memoria, gastarla y darnos cuenta, debemos utilizar la memoria que reservamos; por ello he optado por rellenar un vector de números. Cuidado con subir mucho más MAX_NEW_ELEMENTS, es más, si tienes poca memoria, te recomiendo bajarla un poco, a la mitad, por ejemplo, en un primer cálculo, sólo contando los elementos del vector (8.000.000 x 8 (long int) = 64Mb), por lo que depende de lo que haya en ejecución, con cuatro llamadas a la función gasta_memoria() habremos gastado 256Mb de memoria.
Para ver lo que vamos gastando, debemos ejecutar en un terminal el programa que voy a mostrar, y en otro terminal ejecutamos free. El programa hará varias paradas pidiendo que pulsemos intro a cada llamada de gasta_memoria() para que podamos ver lo que se ha gastado, después del código veremos la ejecución.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <vector>
#include <cstdio>
#include <unistd.h>
#include <cstdlib>
#include <cerrno>
#include <cstring>
#include <fstream>

#define MAX_NEW_ELEMENTS 8000000

using namespace std;

// Sale del programa devolviendo un error
void error(const char *mens);
// Ajunta oom_adjust para matar este proceso si se nos cuelga el sistema
// Así nos quitamos un disgusto
void ajusta_oom();
// Gasta memoria (casi) sin control
void gasta_memoria();
// Espera una tecla
void intro();

void gasta_memoria2()
{

  vector <long int> *v;


  v=new vector<long int>;

  for (unsigned long i=0; i<MAX_NEW_ELEMENTS; i++)
    v->push_back(i);

  intro();
  // delete v;
}


int main()
{
  ajusta_oom();
  cout << "OOM ajustado" << endl;
  intro();
  gasta_memoria();
  gasta_memoria2();
  gasta_memoria();
  gasta_memoria2();
}

void intro()
{
  char key;
  cout << "Pulse Intro"<<endl;
  cin.get(key);
}

void gasta_memoria()
{
  vector <long int> *v;

  v=new vector<long int>;

  for (unsigned long i=0; i<MAX_NEW_ELEMENTS; i++)
    v->push_back(i);

  intro();
  // delete v;
}

void error(const char *mens)
{
  cerr << "ERROR: ("<<mens<<") errno: "<<errno<<": "<<strerror(errno)<<endl;
  exit (1);
}

void ajusta_oom()
{
  ofstream fi;
  char nom[30];

  // Obtenemos el nombre del fichero, aunque estemos haciéndolo
  // a lo C++, uso sprintf() aquí porque es más rápido.
  sprintf(nom, "/proc/%d/oom_adj", getpid());

  // Abrimos el fichero
  fi.open(nom);
  if (fi.fail())
    error("No puedo abrir oom_adj");

  // Escribimos 15 en el fichero, para dar más "apeletas de muerte"
  // a este proceso. Ver:
  // http://totaki.com/poesiabinaria/2010/04/cuando-un-proceso-se-come-la-memoria-de-nuestro-sistema/
  fi<<"15";
  if (fi.fail())
    error("No puedo escribir oom_adj");

  fi.close();
}

La ejecución será escalonada, es decir, ejecutamos, y antes de pulsar intro ejecutamos free(), así vemos cómo se va gastando la memoria tal y como indica la imagen.
testi
Lo que quiero demostrar es que el puntero al vector v, cada vez que ejecutamos new vector sobre ella, restablece su valor, y por tanto, aunque la memoria asociada a ese vector sigue reservada (y encima tiene 8000000 de elementos), ya no tenemos forma de acceder a ella, ya no sabemos la dirección de memoria con la que accedemos; vamos que el hecho de que no sea accesible no significa que no esté reservada, en uso y molestando, porque el sistema no podrá utilizar esos datos para otras cosas.
En este caso, la solución a este problema habría sido escribir:

1
delete v;

al final de la función gasta_memoria(). Aunque en ocasiones esto no es tan fácil de ver.

Cuando el programa se cierra…

Generalmente el sistema operativo, que sí que sabe lo que el proceso ha reservado y consumido, libera la memoria, y a veces puede invertir un rato, aunque a veces no aparezca toda la memoria como libre directamente, al cabo de unos minutos (como mucho) ya estará listo.

Si el sistema no reacciona…

Recuerdo, que si hemos reservado mucha, mucha memoria, el sistema dejará de responder, para ello podemos pulsar Alt+SysRq+F, y el programa morirá rápidamente (pero, pulsad estas teclas, sólo una vez, y esperar).

Foto: tao_zhyn (Flickr) Compartido con CC-by a 26/11/2011

Categories: C/C++, General, Linux Tags: , , , , , , , , , , , , , , ,

Dialogando con HardwareSerial y SoftwareSerial más fácil

Lunes, 29 de Agosto de 2011 Gaspar Fernández Sin comentarios

A la hora de dialogar con los Serials en Arduino, durante estos días he desarrollado funciones para leer cadenas completas de texto desde el Serial y para escribir con la sintaxis de printf(), ya que esto es mucho más fácil cuando se trata de formatear texto.

Bien, ahora se trata de unirlo todo y de dar soporte a cualquier Serial, ya sea HardwareSerial o SoftwareSerial sin complicarnos mucho la vida, con la posibilidad de cambiar esta entrada/salida en cualquier momento y así hacer nuestro programa más flexible.

Para ello he creado la biblioteca SerialExt:
SerialExt.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#ifndef SERIALEXT_H
#define SERIALEXT_H

/* Quitar comentario si no vamos a usar SoftwareSerial, así
 reducimos un poco el tamaño del ejecutable. */
/* #define SEXT_NOSOFTWARESERIAL */

#include <WProgram.h>
#include <stdio.h>
#include <stdarg.h>

/* Si no vamos a usar el Software Serial, no creamos soporte para el */
#ifndef SEXT_NOSOFTWARESERIAL
#include <dynmem.h>
#include <SoftwareSerial.h>
#endif

class SerialExt
{
public:
  ~SerialExt();
  SerialExt(const HardwareSerial &serial, long bps=19200);
  #ifndef SEXT_NOSOFTWARESERIAL
  SerialExt(uint8_t rxp=2, uint8_t txp=3, long bps=19200);
  #endif
  int readString (char *str, unsigned size, const char *stop="\0");
  void printf(const char *fmt,...);
  // A veces, podemos necesitar esto desde fuera
  void serialPrint(const char *txt);
private:
  bool serialAvailable();
  int serialRead();
  HardwareSerial *hs;
  #ifndef SEXT_NOSOFTWARESERIAL
  SoftwareSerial *ss;
  #endif
  int timeout;
};

#endif

SerialExt.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include "SerialExt.h"

void SerialExt::serialPrint(const char *txt)
{
  if (hs)
    hs->print(txt);
  #ifndef SEXT_NOSOFTWARESERIAL
  else
    ss->print(txt);
  #endif
}

void SerialExt::printf(const char *fmt,...)
{
  char tmp[128]; // resulting string limited to 128 chars
  va_list args;
  va_start (args, fmt );
  vsnprintf(tmp, 128, fmt, args);
  va_end (args);
  serialPrint(tmp);
}

SerialExt::SerialExt(const HardwareSerial &serial, long bps)
{
  hs=(HardwareSerial*)&serial;

  #ifndef SEXT_NOSOFTWARESERIAL
  ss=NULL;
  #endif
  timeout=3000000/(bps/8);  // ( 1000/(bps/8) ) * 1000 * 3.0 (milisegundos por signo por 1.5)
  // Initialize serial
  hs->begin(bps);
}

#ifndef SEXT_NOSOFTWARESERIAL
SerialExt::SerialExt(uint8_t rxp, uint8_t txp, long bps)
{
  ss=new SoftwareSerial(rxp, txp);
  hs=NULL;
  // Initialize serial
  ss->begin(bps);
}
#endif

SerialExt::~SerialExt()
{
  #ifndef SEXT_NOSOFTWARESERIAL
  if (ss)
    delete ss;
  #endif
}

// Sólo aplicable con HardwareSerial
bool SerialExt::serialAvailable()
{
  if (hs)
    return hs->available();
  else
    return true;
}

int SerialExt::serialRead()
{
  if (hs)
    hs->read();
  #ifndef SEXT_NOSOFTWARESERIAL
  else
    ss->read();
  #endif
}

int SerialExt::readString(char *str, unsigned size, const char *stop)
{
  unsigned i=0;
  char sIn;
  unsigned long m;
  // Queremos que la cadena se rellene hasta size-2 para que en el carácter
  // size-1 (el último) podamos meter el terminador \0
  --size;      
  while (serialAvailable() && i<size)
    {
      sIn=serialRead();
      if (strchr(stop, sIn))
    break;
      str[i++]=sIn;
      m=micros();
      while (!serialAvailable() && micros()<m+timeout);
    }
  str[i++]='\0';
  return i;
}

Esta biblioteca, hace uso de dynmem, para poder utilizar new y delete y crear el objeto SoftwareSerial. Aunque si no vamos a utilizar el Serial por Software, hay una directiva de pre-procesador (#define SEXT_NOSOFTWARESERIAL) que si quitamos el comentario no compilará nada del soporte, con lo que ahorraremos unos 600 bytes en el binario (que a veces, pueden salvarnos la vida).

Para probar la biblioteca, cargamos el siguiente programa de ejemplo:
serial1.h

1
2
3
4
5
6
7
/* En este archivo veremos la configuración de nuestro proyecto */

#define SERIAL_SPEED 19200
/* Led que queremos que parpadee mientras se ejecuta el programa */
#define STATUS_LED   11
/* Led que indica transferencia de datos */
#define BLINK_DELAY  500

serial1.pde:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// serial1
// Hace un eco con el puerto serie del Arduino
// Dialogamos con el Serial a través de la clase SerialExt. Desde aquí podremos dialogar
// con cualquier HardwareSerial o SoftwareSerial

#include "serial1.h"
#include <dynmem.h>
#include <SerialExt.h>
#include <SoftwareSerial.h>

#define MAX_BUFFER 100

// Almacenamos el estado como variable global
int estado=LOW;
// Almacenamos también el número de milisegundos anterior
unsigned long momento_anterior=0;
unsigned long bytes_recibidos=0;
// SerialExt SExt(Serial);

SerialExt *SExt;

void setup()
{
  // Queremos que un led parpadee mientras trabajamos
  pinMode(STATUS_LED, OUTPUT);
  digitalWrite(STATUS_LED, HIGH);
  delay(1000);
  digitalWrite(STATUS_LED, LOW);
  delay(1000);
  SExt = new SerialExt(Serial);
  digitalWrite(STATUS_LED, HIGH);
}

void loop ()
{  
  int recibe;
  unsigned long momento_actual=millis();
  char buf[MAX_BUFFER];
// No bloqueante, si hay algo para leer entramos, si no, no.
  if(Serial.available())
    {
      SExt->readString(buf, MAX_BUFFER);
      // Escribimos el buffer completo
      SExt->printf("Texto recibido: %s\n", buf);
    }
  // No usamos delay para el parpadeo porque nos entorpece la comunicación con el serial
  if (momento_actual-momento_anterior>=BLINK_DELAY)
    {
      // Cambiamos el estado siguiente. Si era HIGH (1) ahora será
      // LOW (0). He leído en algún lado que el valor de HIGH no
      // siempre es 1; pero en este caso sí es así.
      estado=!estado;
      // Escribimos el estado actual del led
      digitalWrite(STATUS_LED, estado);
      // Establecemos el momento anterior como actual.
      momento_anterior=momento_actual;
    }
}

Como vemos, SerialExt se encarga de hacer Serial.begin() y todo (tampoco es que sea gran cosa, pero nos ahorra una línea); en este ejemplo podemos ver cómo podemos intercambiar líneas completas de texto con Arduino a través del puerto serie.

Categories: Arduino, C/C++ Tags: , , , , , , , , , , , ,

Memoria dinámica con Arduino en C++

Lunes, 15 de Agosto de 2011 Gaspar Fernández Sin comentarios

Uno de los problemas al programar en C++ con Arduino es la utilización de memoria dinámica. Podemos comprobar que el uso de malloc / realloc / free está soportado, pero no new y delete.

La ventaja, en Arduino, para utilizar new y delete es que éstos llaman al constructor y al destructor respectivamente, lo cual nos permite poder crear objetos de forma dinámica.

Para crear los operadores new y delete, he utilizado malloc() y free(), lo malo es que no hacemos comprobación de errores, por lo que, cuando falle algo, los resultados serán inesperados, aunque podremos crear alguna función que detenga la ejecución del programa cuando ocurra algún error.

Dejo tres ficheros, dos pertenecen a la biblioteca dynmem, y otro será el programa de ejemplo (dynres.pde):

dynmem.h:

1
2
3
4
5
6
7
8
9
10
11
/* Con estos operadores podremos hacer reserva dinámica de variables,
 objetos y arrays al estilo C++ */
#ifndef DYNMEN_H
#define DYNMEN_H

void * operator new(size_t size);
void * operator new[](size_t size);
void operator delete(void * ptr);
void operator delete[](void * ptr);

#endif

dynmem.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdlib.h>     // Para malloc() y free()
#include "dynmem.h"

// No tenemos excepciones, no hacemos comprobación de errores, aunque podemos
// hacer una función de error que bloquee el Arduino cuando ocurra algo y llamarla
// desde aquí si ocurre algo...
// La ventaja de usar un operador new frente a malloc() es que el operador
// llamará al constructor del objeto que vamos a crear...
void * operator new(size_t size)
{
  void *p;
  p=(void*)malloc(size);

  // if (!p)
  //   error();

  return p;
}
// lo mismo ocurre con delete, con este, llamamos al destructor del objeto.
void operator delete(void * ptr)
{
  if (ptr)
    free(ptr);
}

void * operator new[](size_t size)
{
  void *p;
  p=(void*)malloc(size);

  // if (!p)
  //   error();

  return p;
}

void operator delete[](void * ptr)
{
  if (ptr)
    free(ptr);
}

dynresv.pde:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <dynmem.h>

class MiClase
{
public:
  ~MiClase();
  MiClase();
};

MiClase::~MiClase()
{
  Serial.println("Objeto destruido");
}

MiClase::MiClase()
{
  Serial.println("Objeto construido");
}

MiClase *objet;

void setup()
{
  Serial.begin(9600);
  objet=new MiClase[10];
  Serial.println(sizeof(*objet));
  delete [] objet;
}

void loop()
{

}
Categories: Arduino, C/C++ Tags: , , , , , ,

Tamaños de variables en Arduino

Martes, 9 de Agosto de 2011 Gaspar Fernández Sin comentarios

Si estamos acostumbrados a programar para procesadores de 32 ó 64bits, tal vez creamos que en un Arduino podemos almacenar números extremadamente grandes. ¡ pues no ! Estamos ante procesadores sencillos, de 8bit, puede que sean demasiado… de los 80 (más grandes en los 80), pero dado lo pequeño que puede llegar a ser, puede valernos para fabricar cualquier gadget/utensilio/aparato… e incluso para aprender… que para eso estamos aquí.

Para ver los tamaños de las variables aquí presentes podemos hacer el siguiente programa:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Presentar en el serial el tamaño de una variable o un tipo
// de variable. Como macro es más rápido de implementar
#define VarSize(var) {              \
    Serial.print("Tam. "#var": ");      \
    Serial.println(sizeof(var));        \
  }
void setup()
{
  Serial.begin(9600);
}

// Llamamos a VarSize con todos los tipos de variable básicos que podemos usar, para ver su tamaño.
void loop()
{
  VarSize(bool);
  VarSize(char);
  VarSize(byte);
  VarSize(long byte);
  VarSize(word);
  VarSize(long word);
  VarSize(int);
  VarSize(long);
  VarSize(long long);
  VarSize(float);
  VarSize(double);
  VarSize(long double);

  delay(100000);
}

Lo que en Arduino Diecimila, y otros modelos basados en Atmega168 devolverá:

Tam. bool: 1
Tam. char: 1
Tam. byte: 1
Tam. long byte: 4
Tam. word: 2
Tam. long word: 4
Tam. int: 2
Tam. long: 4
Tam. long long: 8
Tam. float: 4
Tam. double: 4
Tam. long double: 4

Aquí vemos que el tipo más grande son ¡ 8×8=64bit ! que no está nada mal, aunque dado el hecho de la limitada memoria de la que disponemos, es mejor no hacer reservas de memoria demasiado a la ligera.

Categories: Arduino, C/C++ Tags: , , , , , ,

¡ Siempre olvido la alineación de las variables ! GRR

Jueves, 7 de Abril de 2011 Gaspar Fernández 2 comentarios

1GB DDR3 Memory Module

Algo que pocas veces tenemos en cuenta es la alineación de las variables en la memoria RAM. Muchas veces, ni nos va, ni nos viene, aunque en ciertas ocasiones suele causar calentamientos de cabeza.

Tiene que ver con la forma que tiene la CPU para dialogar con la RAM y la arquitectura de éstas. Partimos del hecho de que pedir un dato a la memoria es algo lento, sí se hace muchos millones de veces por segundo, pero mientras viene o no viene el dato, la CPU simplemente espera.  Ahora, tenemos que tener en cuenta:

  • El diálogo CPU<–>Memoria es a través de palabras y la palabra, en un sistema de 32bit es de 32bit (4bytes), en uno de 64bit serán 8bytes, no en todos los procesadores es así, pero casi.
  • Cada byte en memoria tiene una dirección, para que la CPU y la memoria puedan ubicar el dato.
  • Por otra parte,  las palabras en memoria tienen una posición que coincide con que su dirección sea divisible por la longitud de la palabra.
  • Sólo podemos acceder a una palabra en un mismo instante.

Por tanto, en mi PC de 32bit, cuando quiero un int de 32bit, normalmente me lo traigo de direcciones que sean divisibles por 4, por lo tanto, sólo hago una lectura a la memoria; por ejemplo, mi dato ocupa desde la dirección 0×0030 a la 0×0033 (4bytes), me lo traigo de una sola tirada. De otro modo, si mi dato ocupara desde la direccion 0×0032 a la 0×0035 (4bytes también), tendría que hacer dos peticiones, la palabra 0×0030–0×0033 y la palabra 0×0034-0×0036, y luego coger los dos últimos bytes de una y los dos últimos bytes de la otra; cosa que por experimentar está bien, pero no es óptimo, perdemos mucho tiempo, tardamos el doble. Si nos queremos traer una variable de 8bytes, tendremos que hacerlo de dos tandas, y por diseño, es más fácil traérsela de una dirección de memoria divisible por 8

También tenemos que tener en cuenta que perdemos memoria, es decir, tendremos bytes en memoria que no usaremos para nada (y a veces no nos sobra precisamente), pero sólo podemos aguantarnos… u optimizar más nuestros programas (siempre que compense). Por ejemplo cuando declaramos dos variables, un short (2bytes) y un int(4 bytes), la primera de ellas (el short) se situará en memoria en la dirección 0×0030 y la segunda (el int) en la 0×0034, dejando 2 bytes dentro de la memoria inutilizados. Aunque los compiladores modernos, a la hora de declarar variables intentan hacerlo de la forma más inteligente posible, para aprovechar los huecos al máximo, aunque no declaremos las variables por orden, a la hora de situarlas en memoria, se suelen colocar bien:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>

int main()
{
  char c,c2,c3,c4,c5,c6;
  int i;
  short k;
  long long i2;
  long long ai2;
  short k2;


  printf("%lX [c]\t\t(%lu bytes)\n",    (long unsigned)&c,   sizeof(c));
  printf("%lX [c2]\t\t(%lu bytes)\n",   (long unsigned)&c2,  sizeof(c2));
  printf("%lX [c3]\t\t(%lu bytes)\n",   (long unsigned)&c3,  sizeof(c3));
  printf("%lX [c4]\t\t(%lu bytes)\n",   (long unsigned)&c4,  sizeof(c4));
  printf("%lX [c5]\t\t(%lu bytes)\n",   (long unsigned)&c5,  sizeof(c5));
  printf("%lX [c6]\t\t(%lu bytes)\n",   (long unsigned)&c6,  sizeof(c6));
  printf("%lX [i]\t\t(%lu bytes)\n",    (long unsigned)&i,   sizeof(i));
  printf("%lX [i2]\t\t(%lu bytes)\n",   (long unsigned)&i2,  sizeof(i2));
  printf("%lX [k]\t\t(%lu bytes)\n",    (long unsigned)&k,   sizeof(k));
  printf("%lX [ai2]\t\t(%lu bytes)\n",  (long unsigned)&ai2, sizeof(ai2));
  printf("%lX [k2]\t\t(%lu bytes)\n",   (long unsigned)&k2,  sizeof(k2));

  return 0;
}

Nota: represento variables de tipo long unsigned para representar bien los valores en sistemas de 64bit.
El resultado es algo así:

BFAF2BCF [c]            (1 bytes)
BFAF2BCE [c2]           (1 bytes)
BFAF2BCD [c3]           (1 bytes)
BFAF2BCC [c4]           (1 bytes)
BFAF2BCB [c5]           (1 bytes)
BFAF2BCA [c6]           (1 bytes)
BFAF2BC4 [i]            (4 bytes)
BFAF2BB8 [i2]           (8 bytes)
BFAF2BC2 [k]            (2 bytes)
BFAF2BB0 [ai2]          (8 bytes)
BFAF2BAE [k2]           (2 bytes)

Esto resultará lo siguiente:

BFAF2BA8 BFAF2BAB BFAF2BAC k2 k2 BFAF2BAF
BFAF2BB0 ai2 ai2 ai2 ai2 BFAF2BB3 BFAF2BB4 ai2 ai2 ai2 ai2 BFAF2BB7
BFAF2BB8 i2 i2 i2 i2 BFAF2BB7 BFAF2BBC i2 i2 i2 i2 BFAF2BBF
BFAF2BC0 k k BFAF2BC3 BFAF2BC4 i i i i BFAF2BC7
BFAF2BC8 c6 c5 BFAF2BC7 BFAF2BCC c4 c3 c2 c1 BFAF2BCF

El caso es que las variables siempre encajan.

Pero el tema es que cuando creamos un struct en C, lógicamente las variables también tienen que encajar, y además tienen que estar en el mismo orden en que las ponemos, el compilador, esta vez no tiene la libertad de antes de reubicar información.
Vemos el siguiente ejemplo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>

typedef struct
{
  short s1;         /* 2 */
  int   i1;         /* 4 */
  long long l1;         /* 8 */
  int   i2;         /* 4 */
  long long l2;         /* 8 */
  short s2;         /* 2 */
  char  c1;         /* 1 */
  short s3;         /* 2 */
} mi_struct;

int main()
{
  mi_struct e1;
  printf("%lX [e1]\t\t(%lu bytes)\n",       (long unsigned)&e1,      sizeof(e1));
  printf("%lX [e1.s1]\t\t(%lu bytes)\n",    (long unsigned)&e1.s1,   sizeof(e1.s1));
  printf("%lX [e1.i1]\t\t(%lu bytes)\n",    (long unsigned)&e1.i1,   sizeof(e1.i1));
  printf("%lX [e1.l1]\t\t(%lu bytes)\n",    (long unsigned)&e1.l1,   sizeof(e1.l1));
  printf("%lX [e1.i2]\t\t(%lu bytes)\n",    (long unsigned)&e1.i2,   sizeof(e1.i2));
  printf("%lX [e1.l2]\t\t(%lu bytes)\n",    (long unsigned)&e1.l2,   sizeof(e1.l2));
  printf("%lX [e1.s2]\t\t(%lu bytes)\n",    (long unsigned)&e1.s2,   sizeof(e1.s2));
  printf("%lX [e1.c1]\t\t(%lu bytes)\n",    (long unsigned)&e1.c1,   sizeof(e1.c1));
  printf("%lX [e1.s3]\t\t(%lu bytes)\n",    (long unsigned)&e1.s3,   sizeof(e1.s3));
 
  return 0;
}

Y en este ejemplo sí que podemos ver gran diferencia entre 32bit y 64bit.

32bit
BFC5E510 [e1]           (36 bytes)
BFC5E510 [e1.s1]                (2 bytes)
BFC5E514 [e1.i1]                (4 bytes)
BFC5E518 [e1.l1]                (8 bytes)
BFC5E520 [e1.i2]                (4 bytes)
BFC5E524 [e1.l2]                (8 bytes)
BFC5E52C [e1.s2]                (2 bytes)
BFC5E52E [e1.c1]                (1 bytes)
BFC5E530 [e1.s3]                (2 bytes)
BFC5E510 e1.s1 e1.s1 ? ? BFC5E513 BFC5E514 e1.i1 e1.i1 e1.i1 e1.i1 BFC5E517
BFC5E518 e1.l1 e1.l1 e1.l1 e1.l1 BFC5E51B BFC5E51C e1.l1 e1.l1 e1.l1 e1.l1 BFC5E51F
BFC5E520 e1.i2 e1.i2 e1.i2 e1.i2 BFC5E523 BFC5E524 e1.l2 e1.l2 e1.l2 e1.l2 BFC5E527
BFC5E528 e1.l2 e1.l2 e1.l2 e1.l2 BFC5E52B BFC5E52C e1.s2 e1.s2 e1.c1 ? BFC5E52F
BFC5E530 e1.s3 e1.s3 ? ? BFC5E533

Ya de primeras vemos que la estructura ocupa 36bytes y la suma de sus partes (2 + 4 + 8 + 4 + 8 + 2 + 1 + 2 = 31 bytes), por lo que vemos que la estructura ocupa más.
Si vemos el mapa de memoria (la tabla de arriba), vemos cinco interrogaciones, es decir, 5 huecos donde no trabajamos, y sólo servirán para poder alinear los demás datos.
Vemos que las primeras interrogaciones están en BFC5E512 y es que lo próximo que tenemos que colocar es un entero, por ello nos desplazamos hasta BFC5E514. El siguiente byte problemático es justo después de un char, y lo siguiente será al final, porque se nos quedan algunos bytes “colgados” y no vamos a poder aprovechar.

64bit
7FFFB3652EF0 [e1]               (40 bytes)
7FFFB3652EF0 [e1.s1]            (2 bytes)
7FFFB3652EF4 [e1.i1]            (4 bytes)
7FFFB3652EF8 [e1.l1]            (8 bytes)
7FFFB3652F00 [e1.i2]            (4 bytes)
7FFFB3652F08 [e1.l2]            (8 bytes)
7FFFB3652F10 [e1.s2]            (2 bytes)
7FFFB3652F12 [e1.c1]            (1 bytes)
7FFFB3652F14 [e1.s3]            (2 bytes)

En la tabla acortaré las direcciones de memoria:

B3652EF0 e1.s1 e1.s1 ? ? e1.i1 e1.i1 e1.i1 e1.i1 B3652EF7
B3652EF8 e1.l1 e1.l1 e1.l1 e1.l1 e1.l1 e1.l1 e1.l1 e1.l1 B3652EFF
B3652F00 e1.i2 e1.i2 e1.i1 e1.i2 ? ? ? ? B3652F07
B3652F08 e1.l2 e1.l2 e1.l2 e1.l2 e1.l2 e1.l2 e1.l2 e1.l2 B3652F0F
B3652F10 e1.s2 e1.s2 e1.c1 ? e1.s3 e1.s3 ? ? B3652F17

De primeras vemos que en 64bit la estructura ocupa 40bytes en lugar de 31bytes… pero esta vez, vemos cómo a la hora de colocar un long int (8bytes) en B3652F04, se lo lleva a B3652F08, así será capaz de leerlo en una lectura a memoria (de la palabra entera de 8bytes) en lugar de 2 lecturas (de 4bytes cada una en dos palabras diferentes).

¿Cuándo debemos tener esto en cuenta?

Esto tampoco tiene mucha importancia si sólo vamos a almacenar una pequeña información en un registro, pero, si vamos a almacenar un array de muchos elementos de un registro, o una lista enlazada, podremos observar que si en el registro tenemos 9bytes que sólo sirven para hacer bulto, es decir, para conseguir alinear la información, en un millón de elementos, estaremos perdiendo cerca de 9Mb, nos puede ayudar a optimizar un poco la información que almacenamos.

Por otra parte, si lo que estamos haciendo es implementar una lectura/escritura de información en un formato determinado y, por ejemplo, tenemos:

  • 3 bytes de identificación
  • 4 bytes de control
  • 4 bytes tamaño
  • resto de archivo de información

No podremos crear un registro del tipo:

1
2
3
4
5
6
struct
{
  char identif[3];
  int  control;
  int  size;
} TFormato;

Ya que desde el último carácter hasta el entero de control habrá 1byte de diferencia y el formato no se respetará correctamente, por lo que seguramente haya algún fallo.

Esto tampoco quiere decir que no se pueda leer una variable que no esté alineada, siempre podemos hacerlo jugando con los bytes y trabajando un poco con el código, aunque las arquitecturas modernas lo permiten directamente con instrucciones especiales, eso sí, no se recomienda mucho su uso, ya que es más lento hacer dos peticiones a memoria, y luego trabajar con el resultado de las dos para unirlo; por otra parte, si trabajamos con un procesador que no disponga de estas instrucciones, tendremos que programar cómo hacemos las peticiones y la fusión de la información, aunque de eso se encargue el compilador, debemos tenerlo en cuenta si queremos que nuestro programa sea rápido.

Un pequeño ejemplo de un acceso no alineado

Si queremos provocar un acceso no alineado en C, podemos hacer lo siguiente: crear un array de char más o menos grande, y un puntero a un entero que apunte a una dirección dentro del array de char (con que apunte a la dirección base+1 vale para que no esté alineado.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>

int main()
{
  unsigned char datos[6];
  int *punt;
  printf("%lX (%lu)\n", (unsigned long)&datos, sizeof(datos));
  punt=(int*)&datos[1];
  printf("%lX (%lu)\n", (unsigned long)punt, sizeof(*punt));
  *punt=123456789;
  printf("%d %d %d %d => %d %X <= %X %X %X %X\n", datos[1], datos[2], datos[3], datos[4], *punt, *punt, datos[4], datos[3], datos[2], datos[1]);
 
}

La salida es algo así (en 64bits, aunque sólo se nota en el tamaño de las direcciones de memoria):

7FFFC98BE8B0 (6)
7FFFC98BE8B1 (4)
21 205 91 7 => 123456789 75BCD15 <= 7 5B CD 15

Primero mostramos la dirección de memoria base del array y el tamaño del mismo, luego la dirección de memoria base de la variable entera con la que trabajaremos y su tamaño (muy importante el sizeof(*punt), sin el * nos daría el tamaño del puntero, y estamos en 64bit, es decir, sería de 8bytes.
Y tras ello, asignaremos al entero el valor 123456789, podremos ver el valor en decimal de cada uno de los bytes que componen el entero, el valor del entero, y luego el valor del mismo en hexadecimal acompañado de los valores en hexadecimal de cada uno de los bytes de antes.

Esto está diseñado para verse en un sistema little endian, en un sistema big endian, la última línea de salida sería:

7 91 205 21 => 123456789 75BCD15 <= 15 CD 5B 7

Foto: wwarby (Flickr)

Categories: C/C++, Cosas que damos por hechas, General Tags: , , , , , , ,

Compilando y linkando a mano con GCC

Sábado, 11 de Septiembre de 2010 Gaspar Fernández Sin comentarios

GCC compila y linka automáticamente, nos devuelve un ejecutable directamente:

$ gcc -o ejecutable fuente.c

pero en realidad, aparte de pre-procesar y compilar, enlaza algunas bibliotecas del sistema para que nuestro ejecutable funcione bien. Sólo por jugar un poco, veamos, más o menos (depende del sistema) cómo obtener el ejecutable a mano, es decir, compilamos por un lado, y linkamos por otro.

Primero, creamos un programa sencillo, un hello.c que contenga lo siguiente:

1
2
3
4
5
6
7
8
#include <stdio.h>

int main(int argc, char *argv[])
{
   printf("Hola mundo!!\n");

   return 0;
}

Ahora obtenemos el fichero objeto, nuestro código compilado de la siguiente manera:

$ gcc -c hello.c

Veremos que se ha generado el fichero hello.o ; éste fichero aún no lo podremos ejecutar, ya que no tenemos las librerías del sistema necesarias para ello.

Ahora obtendremos el fichero ejecutable con el linkador:

ld -o hello -m elf_i386 -dynamic-linker /lib/ld-linux.so.2 /usr/lib/crt1.o /usr/lib/crti.o /usr/lib/gcc/i686-pc-linux-gnu/4.2.3/crtbegin.o -L/usr/lib/gcc/i686-pc-linux-gnu/4.2.3 hello.o /usr/lib/gcc/i686-pc-linux-gnu/4.2.3/crtend.o /usr/lib/crtn.o -lc

Debemos cambiar /usr/lib/gcc/i686-pc-linux-gnu/4.2.3 por la ruta correspondiente en nuestro equipo; los archivos necesarios se encontrarán en en el directorio de GCC, tras seleccionar la arquitectura y SO correspondiente (en mi caso i686-pc-linux-gnu), y dentro de ese directorio encontraremos otro correspondiente a la versión de GCC (en mi caso la 4.2.3).

Más o menos lo que vemos en el proceso de linkado es lo siguiente:

  • -o hello : es el nombre del ejecutable
  • -m elf_i386 : es el tipo de ejecutable y la arquitectura. También puede ser elf_x86_64 si tenemos las bibliotecas necesarias.
  • -dynamic-linker /lib/ld-linux.so.2: es el cargador dinámico
  • /usr/lib/crt1.o /usr/lib/crti.o: son dos objetos encargados de la inicialización de memoria del programa
  • /usr/lib/gcc/i686-pc-linux-gnu/4.2.3/crtbegin.o : indica cómo tiene que empezar el programa.
  • /usr/lib/gcc/i686-pc-linux-gnu/4.2.3/crtend.o : indica cómo tiene que terminar el programa
  • hello.o : es el objeto de nuestro programa.
  • -L/usr/lib/gcc/i686-pc-linux-gnu/4.2.3 : hacemos que el linkador busque bibliotecas en el directorio indicado.
  • /usr/lib/crtn.o : realiza tareas de limpieza de memoria.
  • -lc: incluye la librería de C estándar.

Los archivos que empiezan por crt* normalmente se encargan de poner los datos que nos entran en su sitio; parece que el hecho de coger los parámetros que nos pasan por la línea de comandos y colocarlos en memoria para que nuestro programa los lea es tarea fácil, y que luego nuestro programa devuelva una respuesta; y además, los programas no se ejecutan siempre en la misma posición de memoria, depende de la memoria que haya libre, eso lo suele controlar el S.O. pero nuestros ejecutables tienen que estar preparados… en definitiva, hay muchos agentes involucrados.

Una vez hecho esto, tenemos nuestro hola mundo preparado para ser ejecutado.

Debo agradecer a Carlos, que me dio la idea de escribir este artículo.

Categories: C/C++, Cosas que damos por hechas Tags: , , , , , , , , , , , , , ,

GPGPU: Exprimiendo el potencial de tu GPU para propósito general (I)

Domingo, 25 de Julio de 2010 Gaspar Fernández Sin comentarios

Hace unas semanas estuve en el Curso Avanzado de GPU impartido por el Dr. Manuel Ujaldón en la Universidad de Málaga; y me parece interesante compartir algunas conclusiones y un poco de investigación sobre el tema con todos ustedes.

Una arquitectura diferente

Disponemos de un chip con gran capacidad de procesamiento, pero a su estilo. Aunque originalmente está diseñado para su uso en juegos, recientemente (no tan recientemente porque el primer uso de GPU (Graphics Processing Unit, o Unidad de Procesamiento Gráfico) para propósito general fue en el 1997, lo que sí es más reciente es la implicación de empresas en este tipo de sistemas) muchas personas están concienciadas en aprovechar sus capacidades, y es muy interesante ya que con poco dinero podemos compararnos en capacidad de procesamiento a algunos superordenadores, y es que en ciertas tareas de cálculo muy pesado que en procesadores CPU actuales tardan varios días, con procesamiento GPU y con un coste mucho menor podemos completarlas en pocos minutos.

Ya podríamos pensar que es el momento de prescindir de la CPU, pero ese momento aún no ha llegado, ya que la GPU puede ser muy buena en ciertas tareas relacionadas con el paralelismo, pero la CPU es buena con las sentencias de control y los saltos en el código.

Paralelismo en GPU

Las GPU actuales pueden tener 128, 256 ó 512 núcleos (frente a los 4 ó 6 núcleos de los actuales procesadores más avanzados). Es decir, podemos tener 512 hilos corriendo concurrentemente en GPU. Si estamos acostumbrados a utilizar pthreads, vemos cómo tenemos que programar el hilo y crearlos, y si tenemos 512 núcleos deberíamos crear los 512 hilos; el problema y la solución vienen, en la programación GPU, en que todos los núcleos ejecutarán el mismo código, y cada hilo tendrá una serie de identificadores que nos indicarán qué procesador está funcionando. Por tanto podemos lanzar 512 tareas simultáneas y cada una será lanzada por un núcleo diferente. Si, por ejemplo queremos sumar un vector de 512 elementos con otro, en CPU, realizamos una operación cada vez (hasta 512 operaciones), en GPU lanzaremos las 512 a la vez, y terminarán en el tiempo de una operación (más o menos y a grosso modo)

Velocidad de acceso

Las tarjetas gráficas, por lo general, tienen una memorial RAM, unas cuántas generaciones por delante (mientras en CPU vamos por DDR3, las gráficas ya usan DDR5). La principal razón es que esta memoria está soldada en la plata y precisamente, muy cerca de la GPU, y además, el controlador de memoria está integrado en GPU, lo que facilita las transacciones. Por esto y mucho más, una lectura o escritura en la memoria de la tarjeta gráfica consumirá pocos ciclos en GPU, mientras que los accesos a memoria en CPU consumen muchos ciclos de reloj.
Con esto, tenemos una lectura/escritura en memoria mucho más rápida, y además, tenemos una memoria compartida, mucho más pequeña (de varios Kilobytes) que es mucho más rápida, y que nos permitirá una interacción más rápida. Es algo así como la caché de la CPU, pero en este caso es una memoria que sí podemos controlar (leer y escribir en esa memoria lo que queremos y cuando queremos, mientras que la caché de la CPU es automática).

Metodología de programación

El código que podemos utilizar se ejecuta en CPU, por tanto tenemos que programar la tarea que queremos que realice la GPU aparte (en una función, por ejemplo), ese será nuestro kernel. Justo antes de ejecutar nuestro kernel en GPU, debemos copiar los datos necesarios desde la RAM de nuestro sistema (host) a la memoria de nuestro sistema gráfico (device), tras ello ejecutar el kernel, y luego volver a copiar los datos obtenidos desde el device al host.
Sólo podemos ejecutar un kernel a la vez; éste se ejecutará en todos los núcleos a la vez, y es nuestro trabajo hacer que merezca la pena, si dejaos núcleos sin usar, es potencia que no estamos aprovechando.
Por otra parte, tenemos que conseguir que la realización de las tareas en GPU merezca la pena, ya que:

T_copia_H2D + Procesamiento GPU + T_copia_D2H < Procesamiento CPU

Es decir, el tiempo que tardamos en copiar los datos, primero desde el host al device y luego desde el device al host, más el tiempo que tarde el procesamiento en GPU tiene que ser menor que el tiempo que tarde el procesamiento en CPU, si no, todo esto no merecería la pena.

Dada la naturaleza de los kernels, y que todos los procesadores tienen que ir sincronizados, ejecutando la tarea encomendada, lo óptimo es que estos sean lo más pequeños posible y que tengan el menor número de decisiones posible (un if … else, implica que si la condición se cumple en un conjunto de núcleos, al ir todos los procesadores a la par, mientras unos núcleos procesan, otros pierden tiempo).

¿Cómo empezamos?

Aunque tenemos varias posibilidades, siempre podemos programar en ensamblador, específico a cada modelo de Chip, pero tal y como ocurre en CPU, van surgiendo lenguajes y sistemas que nos permiten generalizar nuestro código y poder ejecutarlo en una amplia gama de Chips (sí, se pierde un poco de rendimiento, pero perderíamos mucho tiempo haciéndolo así, por tanto es un coste que podemos permitirnos). Actualmente hay dos sistemas que podemos utilizar: CUDA (sólo para tarjetas nVidia, a partir de la serie 8) y OpenCL desarrollado por Apple y propuesto al grupo Khronos para ser un estándar de programación GPU libre del control de una empresa y compatible con una amplia gama de chips gráficos y que tanto nVidia, como ATI, y otros muchos fabricantes de chips gráficos.

Lectura recomendada

Giz Explains: GPGPU Computing
Wikipedia: Unidad de Procesamiento Gráfico

Categories: General Tags: , , , , , , , , , , , , ,

Visita otras webs de la red