Arduino Bellek Kullanımını Azaltma

Bellek kullanımı azaltma işlemi, belkide sorunlu olduğunu düşündüğünüz ya da bozulduğuna bile karar verdiğiniz geliştirme kartınızı düzeltebilir! Daha fazla IO pinine ihtiyaç duyduğunuz için değil de, programınız için ekstra belleğe ihtiyacınız olduğunu için daha pahalı entegreler hatta daha pahalı bir Arduino geliştirme kartı kullanmak zorunda kalmış olabilirsiniz. Fakat bu yazıda anlatacağımız yöntemlerle projelerinizi oldukça küçük bir boyuta sığdırabilirsiniz.

Arduino Mega 2560 için hazırlanmış at turu kodu, burada gösterdiğimiz yöntemlerle Arduino Uno veya Arduino Pro Mini kartlarına uyumlu hale getireceğiz. Unutmadan hatırlatalım, Mega 2560, 256kB flash belleğe sahipken, ATmega328p mikrodenetleyicili Uno ve Pro Mini sadece 32kB flash belleğe sahiptir.

At Turu (Knight’s Tour) Nedir?

At turu, bir satranç tahtasındaki bir atı konu alan bir matematiksel problemdir. At, boş bir satranç tahtası üzerinde bir yerdedir ve satranç kurallarına uygun bir şekilde hareket ederek tahtadaki bütün karelere tam bir kez gitmesi gerekir. 

Mega 2560 için hazırlanmış at turu programını, uno ve pro mini’ye sığacak bir şekilde düzenleyeceğiz. Şimdi bellek kullanımını azaltacak yöntemlere geçelim:

Değişkenlerin Boyutu

Değişkenlerin yalnızca ihtiyaç duydukları minimum boyutu kullandığından emin olun.

MEGA versiyonunda, hareketleri(move) tutan dizi şu şekilde tanımlanır:

int sol[N + 1][N + 1]

C ve C++’da diziler sıfır tabanlıdır, yani dizideki ilk eleman 0’dır ve dizideki son eleman N-1 olmalıdır. 1 ila N aralığında düşünmek genellikle 0 ila N-1 aralığında düşünmek daha kolay olsa da, diziyi 0 ila N olarak tanımlamak, bu durumda eleman 0’ın asla kullanılmadığı anlamına gelir. Yani 8×8 dizisi artık 9×9’dur ve bu nedenle dizideki 17 eleman kullanılmamaktadır.

İkinci olarak, her dizi elemanı -1 ile 64 arasında bir sayı tutacaktır. int türü kullanılarak tanımlanan tamsayılar 16 bit veya 2 bayttır. Bu, -32768 ile 32767 arasında bir sayı tutacağı anlamına gelir. Ancak buna ihtiyacımız yok, diziyi int8_t kullanarak tanımlayarak, dizinin boyutunu yarıya indirecek ve -128 ile 127 arasındaki sayıları saklayabilecek ve gereksinimleri karşılayacaktır.

UNO versiyonunda dizi artık şu şekilde tanımlanabilir:

int8_t sol[N][N]

Kurtarılan bayt sayısı 98’dir (RAM’in yaklaşık %5’i)

Diğer değişkenlere baktığımızda aşağıdakileri 8 bitlik sayılara indirebiliriz:

int i, j, step_count, x_move[], y_move[], cnt, k

sadece dizilerin imzalanması gerekiyor, diğerlerine imzaya gerek yok.

uint8_t i, j, step_count, cnt, k
int8_t x_move[], y_move[]

Bu, yerel değişkenler oldukları için bu durumda RAM’i azaltmıyor gibi görünse de (derleyici yalnızca genel RAM kullanımını gösterir), Yığın(stack) adı verilen bir yapıda depolanırlar. Yığın, RAM’in bir parçasıdır ve belleğin sonundan belleğin başına kadar büyür. Geçici değişkenleri tutar, kayıtları ve işlevlerin dönüş adresini saklar. Yığın çok büyürse, global değişkenlerinizin üzerine yazmaya başlayacak ve programınız eninde sonunda çökecektir.

Değişkenleri Derleyici Sabiti ile Tanımlama

Genel olarak, tüm sabitler derleyici sabitleri olmalı ve değişken olarak tanımlanmamalıdır.

const float pi = 3.14

olarak 4 bayt kullanacaktır.

#define pi 3.14

sıfır bayt kullanır.

Derleme sırasında yapılan optimizasyonun bunu sizin için otomatik olarak yapacağını varsaymayın.

Güncelleme: Derleyici sabitleriyle ilgili sorun, bir veri türü belirtmemeleridir. Örneğin:

#define one 1

Burada “one” sabitinin veri türü yoktur. Bunun üstesinden gelmek için aşağıdaki gibi bir veri tipi ekleyebilirsiniz:

#define one (uint8_t)1

MEGA sürümünde, x_move[], y_move[] ve sol[] [] dizileri start_knight_tour işlevinde tanımlanır. x_move[] ve y_move[] dizileri asla değişmez. Dizileri yerel değişkenler olarak tanımlamanın sorunu, diziyi (bu durumda dizinin adresi) o diziye erişecek herhangi bir işleve parametre olarak iletmeniz gerektiğidir. Bu, yığına fazladan ek yük ekler. Yığın hala RAM’in bir parçası olduğu için, onu parametre olarak her ilettiğinizde aslında fazladan 2 bayt kullanırsınız. Bu durumda, bunları global değişkenler olarak tanımlayarak yığın alanından tasarruf edebilirsiniz.

const int8_t x_move[] = {2, 1, -1, -2, -2, -1, 1, 2};
const int8_t y_move[] = {1, 2, 2, 1, -1, -2, -2, -1};
int8_t sol[N][N];

Sabit Dizileri Flash Belleğe Koyun

Normalde tanımladığınız tüm veriler RAM’de saklanır. Sakladığınız veriler hiç değişmiyorsa, PROGMEM özniteliğini ekleyerek flash belleğe kaydedebilirsiniz,

const int8_t x_move[] = {2, 1, -1, -2, -2, -1, 1, 2};
next_i = i + x_move[k];

bu hale gelmelidir:

const int8_t x_move[] PROGMEM = {2, 1, -1, -2, -2, -1, 1, 2};
next_i = i + pgm_read_byte_near(x_move + k);

Bu daha yavaştır ancak diziler artık değerli RAM’den tasarruf sağlayan flash bellekte saklanmaktadır.

Not: Yukarıdaki kod satırını şu şekilde de yazabilirsiniz:

next_i = i + pgm_read_byte_near(&x_move[k]);

C’deki & karakteri “adresi” anlamına gelir. Bu durumda, x_move dizisinin başına k eklemekle aynı olan x_move[k] adresi olur.

Özyineleme(Recursion) ile Başa Çıkmak

Özyineleme, bir fonksiyonun kendini çağırma yeteneğidir. Standart yineleme yöntemleri yerine özyineleme kullanarak anlaşılması daha kolay olan bazı programlama çözümleri vardır. Klasik örnek, faktöriyel hesaplamak:

int faktoriyel(int x) {
if (x <= 1)
return 1
else
return x * faktoriyel(x - 1); }

Faktöriyel fonksiyon çağrıldığında, çağıran fonksiyon parametre değerlerini yığına koyacaktır (bu durumda x). Ardından dönüş adresini (işlev döndükten sonra yürütülecek sonraki ifadenin adresi) yığına koyar. Ardından fonksiyonun başlangıcına atlar. Fonksiyonun sonunda yığından dönüş adresi alınır, yığın işaretçisi artık gerekli olmadığı için parametreleri atlayacak şekilde ayarlanır ve program fonksiyondan sonraki ifadede devam eder.

Özyineleme ile, diyelim ki faktoriyel(10) diyoruz, yığına 10 sayısı yerleştirilir, yığına dönüş adresi yerleştirilir, fonksiyon yürütülür. faktoriyel(x – 1) olarak adlandırdığımız fonksiyonda şimdi 9 sayısı yığına yerleştirildi, dönüş adresi yığına yerleştirildi ve fonksiyon tekrar yürütüldü. Bu, x 1’e ulaşana kadar devam eder. Böylece yığına 10 sayı ve 10 dönüş adresi kaydedilir. Bu durumda 10!’u hesaplamak için 40 bayt gerekir. 20!’yi hesaplamak için 80 bayt gereklidir.

Genel olarak, RAM boyutu çok sınırlı olduğu için mikro denetleyicilerde özyineleme önerilmez. Verdiğimiz örnek çok basit. Pratikte, bir işlevi çağırmak için çok daha fazla ek yük kullanılır. Yığına yalnızca parametreler değil, aynı zamanda yerel değişkenler de yerleştirilir. Bir işlevin yüzlerce bayt yığın alanı kullanması alışılmadık bir durum değildir.

At turu örneğinde, tahtadaki her kareyi deneyecektir. Bu 64 seviye derinliğe ineceği anlamına geliyor. Şimdi knight_tour işlevinde ne kadar bellek gerektiğine bakalım:

MEGA sürümü (arama başına 20 bayt):

int knight_tour(int sol[N + 1][N + 1], int i, int j, int step_count, int x_move[], int y_move[])

Dönüş adresi için 2 bayt, sol[N+1][N+1] dizisinin adresi için 2 bayt, 2 bayt int i, 2 bayt int j, 2 bayt int step_count, x_move[] dizisinin adresi için 2 bayt, y_move[] dizisinin adresi için 2 bayt.

Yerel değişkenler int k, next_i, next_j 6 bayt alır.

Parametreler ve yerel değişkenler için gereken toplam yığın alanı 20 * 64 veya 1280 bayttır.

UNO sürümü (arama başına 4 bayt):

bool knight_tour(int8_t xy)

Dönüş adresi için 2 bayt, int8_t xy için 1 bayt

Yerel değişken int8_t k 1 bayt alır.

Parametreler ve yerel değişkenler için gereken toplam yığın alanı 4 * 64 veya 256 bayttır.

Derleyici Optimizasyonunu Anlama

Derleyici optimizasyonu, programınızı hızlandırmanıza yardımcı olur. Koda bakacak ve hafızadaki bir değişkeni kayıtlarından birine aktarmak yerine, onu saklamak için yedek bir kayıt kullanacağına karar verebilir. Bu, for döngüsünün dizini ile ortaktır. Ancak, daha hızlı olmasına rağmen daha fazla bellek kullanır. Değişken için yalnızca bellek ayrılmakla kalmaz, aynı zamanda çağrılan işlevin üzerine yazması durumunda kullandığı kaydın yığına kaydedilmesi gerekir. knight_tour işlevinde optimizasyonu kapatmak için özniteliğin eklenmesi, işlev her çağrıldığında 10 bayt yığını kurtarabilir (64 x 10 = 640 bayt kaydedildi)

__attribute__((optimize("O0")))
bool knight_tour(int8_t xy)

Koda Özel Optimizasyonlar

Hiçbir derleyici optimizasyon sistemi, kodun gerçekte nasıl çalıştığını anlayan programcı ile asla rekabet edemez. Örneğin bu kod parçacığını alın:

MEGA sürümü:

int knight_tour(..., int step_count, ...) {
:
if (knight_tour(..., step_count + 1, ...))
:
}

Burada step_count‘un knight_tour işlevi yinelemeli olarak her çağrıldığında bir arttığını görüyorsunuz. step_count değere göre iletildiğinden, fonksiyondan dönüşte değeri aynı olacaktır. Gerçekte, işlev her yinelemeli olarak çağrıldığında 2 bayt yığın alanı boşa harcanır.

UNO sürümü:

uint8_t step_count = 0;
:
bool knight_tour(int8_t xy) {
:
step_count++;
solved = knight_tour(next_xy);
step_count--;
:
}

Normal şartlar altında, yerel bir değişken yerine global bir değişken kullanmak genellikle hoş karşılanmaz. Ancak bu durumda 1 baytlık bir maliyetle 128 bayt yığından tasarruf sağlar.

Başka bir koda özel optimizasyon, x ve y değişkenlerini tek bir xy değişkeninde birleştirmekti. Hem x hem de y, 0 ile 7 arasında bir değere sahip olması gerektiğinden, aşağıdaki formülü kullanarak xy‘den x ve y değerini elde etmek kolaydır.

x = xy & 0x07;
y = xy >> 3;
xy = (y << 3) | x ;

Bunun daha yavaş olduğuna şüphe yok ama bu, özyinelemeli knight_tour işlevine yalnızca bir parametrenin geçirilmesi gerektiği anlamına gelir.

İşlev özyinelemeli olduğundan, daha az yerel değişken kullanmak çok önemlidir. MEGA versiyonunda üç yerel değişkeni vardır. UNO versiyonunda sadece bir tane gereklidir. Diğer ikisi, knight_tour işlevinden döndükten sonra yeniden hesaplanır.

Normal şartlar altında böyle bir kod yazmazsınız. Ancak bu durumda yığında depolanan veri miktarını azaltmak bir zorunluluktu.

Son Dokunuşlar

Derleyici tarafından oluşturulan derleme diline bakmadan, kodun knight_tour işlevinin her özyinelemeli çağrısında hala 24 bayt yığın kullanıyor. Bu, 24 * 64 = 1536 bayt yığın kullanımına eşittir. Bu, global değişkenler vb. için yalnızca 512 bayt bırakır.

At Turu Kodu(Arduino UNO)

//#define DEBUG
#include <LedControl.h>

#define CLOCK 11
#define CS 10
#define DIN 12
LedControl lc = LedControl(DIN, CLOCK, CS, 1);

#define N 8
#define N2 64

const int8_t x_move[] = {2, 1, -1, -2, -2, -1, 1, 2};
const int8_t y_move[] = {1, 2, 2, 1, -1, -2, -2, -1};
int8_t sol[N2];
int8_t m_level = 0;
bool solved = false;
bool thinking = false;
#ifdef DEBUG
uint8_t dot_count = 0;
#endif
unsigned long timeout;
int8_t step_count;
uint8_t next_xy;
uint8_t this_x;
uint8_t this_y;

void setup()
{
#ifdef DEBUG
  Serial.begin(115200);
#endif
  lc.shutdown(0, false);
  lc.setIntensity(0, 2);
  lc.clearDisplay(0);
  lc.setLed(0, 0, 0, true);

  unsigned long start_time = millis();
  timeout = start_time + 1000;
  solved = start_knight_tour();
#ifdef DEBUG
  Serial.println(((solved) ? "Found " : "Failed ") + String((millis() - start_time) / 1000) + "s");
#endif
}

bool start_knight_tour()
{
  for (int8_t xy = 0; xy < N2; xy++)
  {
    sol[xy] = -1;
  }

  sol[0] = 0;
  step_count = 1;
  return (knight_tour(0));
}


__attribute__((optimize("O0")))
bool knight_tour(int8_t xy)
{
  int8_t k;

  if (millis() > timeout)
  {
    lc.setLed(0, 0, 0, thinking);
    thinking = !thinking;
    timeout = millis() + 1000;

#ifdef DEBUG
    Serial.print(".");
    dot_count++;
    if (dot_count == 60)
    {
      dot_count = 0;
      Serial.println();
    }
  }
  if (step_count > m_level)
  {
    m_level = step_count;
    Serial.println("L:" + String(m_level) + ", S:" + String(SP));
#endif
  }

  if (step_count == N2)
    return true;

  for (k = 0; k < N; k++)
  {
    this_y = (xy >> 3) + y_move[k];
    if (this_y >= 0 && this_y < N)
    {
      this_x = (xy & 0x07) + x_move[k];
      if (this_x >= 0 && this_x < N)
      {
        next_xy = (this_y << 3) | this_x;
        if (sol[next_xy] == -1)
        {
          sol[next_xy] = step_count;
          step_count++;
          solved = knight_tour(next_xy);
          step_count--;
          if (solved)
            return true;
          this_x = (xy & 0x07) + x_move[k];
          this_y = (xy >> 3) + y_move[k];
          next_xy = (this_y << 3) | this_x;
          sol[next_xy] = -1;
        }
      }
    }
  }
  return false;
}

void loop()
{
  lc.clearDisplay(0);
  if (solved)
  {
    int8_t cnt = 0;
    while (cnt < N2)
    {
      for (int8_t xy = 0; xy < N2; xy++)
      {
        if (sol[xy] == cnt)
        {
          delay(1000);
          lc.setLed(0, xy & 0x07, xy >> 3, true);
          cnt = cnt + 1;
        }
      }
    }
  }
  delay(2000);
}

Devre Şeması