تراز ساختمان داده

تراز ساختمان داده یا هم‌تراز‌سازی داده ساختار (به انگلیسی: data structure alignment) روشی است که داده در حافظه رایانه، مرتب‌سازی و مورد دستیابی قرار می‌گیرد. این عمل دارای سه بخش کلی هم‌ترازسازی داده، داده‌ساختار لایه‌گذاری و دسته‌بندی می‌باشد.

تعاریف اولیه

1. هم‌ترازسازی داده: در این بخش هدف این است که برای راحتی کار پردازنده حافظه، هر داده در آدرسی قرار داده شود که مضربی از طول داده‌است. حال اگر فرض کنیم که همهٔ داده‌ها دارای طولی مضرب یک عدد مثلاً ۳۲ هستند، به این ترتیب کار پردازشگر برای دسترسی دوباره به حافظه خیلی راحت‌تر می‌شود و صرفاً نیاز است مضاربی از خانه‌های حافظه را بررسی کند و نه همه را.
2. لایه‌گذاری(padding): در قسمت قبل گفتیم که دوست داریم محل‌های حافظه مضارب طول داده باشند. حال برای اینکه این امر ممکن شود نیاز است که قبل و بعد از گذاشتن هر داده تعدادی خانهٔ خالی گذاشته شوند تا آدرس‌ها مضرب عددی خاص یا طول داده شوند. قرار دادن این فاصله‌ها و الگوریتم‌های رسیدگی به آن وظیفهٔ این بخش است.
3. بسته‌بندی(packing): نحوهٔ خوانش داده در کامپیوتر به این صورت است که چیزی با عنوان «واژه» در آن تعریف شده و داده‌هایی که می‌خواند دارای طولی با مضرب واژه هستند. حال اگر طول داده‌ای از این طول کمتر باشد چه؟ در این صورت اگر کامپیوتر پردازش‌گری داشته باشد که این چنین داده‌هایی را شناسایی کرده و آن‌ها را در محل ذخیره‌سازی یک واژه در حافظه قرار دهد، این امر موجب صرفه‌جویی زیادی در حافظه می‌شود. البته این کار، بار پردازشی را زیاد می‌کند که در برخی معماری‌ها ممکن است بهینه‌سازی حافظه‌ای که بعدتر انجام می‌شود نهایتاً آن را به صرفه کند.

هم‌ترازسازی داده

در زبان‌های برنامه‌نویسی، هر شی‌ای که به عنوان داده کاربرد دارد دارای دو ویژگی است: مقدار و مکان ذخیره‌سازی. منظور از هم‌ترازسازی داده این است که آدرس هر شی داده قابل تقسیم بر ۱، ۲، ۴ یا ۸ باشد. به‌طور مثال، اگر آدرس داده‌ای 12FEECh باشد که معادل ۱۲۴۴۹۰۸ در سیستم اعشاری است، آنگاه این داده در یک سیستم هم‌ترازسازی ۴ بایتی قرار دارد چرا که بزرگترین توانی از دو که آدرس داده بر آن بخش‌پذیر است، ۴ می‌باشد.

دسترسی واحد پردازش مرکزی چه برای نوشتن و چه برای خواندن از حافظه به صورت تک بایتی اتفاق نمی‌افتد. در عوض، دسترسی واحد پردازنده به حافظه در قالب بسته‌های ۲، ۴، ۸، ۱۶ یا ۳۲ بایتی است. علت چنین طراحی‌ای، بازدهی می‌باشد: دسترسی به خانه‌های حافظه با آدرس مضرب ۴ بایت یا ۸ بایت بسیار سریع‌تر از دسترسی به آدرس‌های ۱ بایتی است. اگر داده‌ها به طول مضرب ۴ یا ۸ نباشند، این مسئله بار پردازشی برای پردازنده دارد، چرا که باید برای دادهٔ مثلاً به طول ۶، دو بلوک به طول ۴ بایت را بیرون بکشد و با شیفت‌دادن دادهٔ اصلی را دریافت کند.

لایه‌گذاری و بسته‌بندی

مقایسه

این دو عمل به نوعی متضاد یکدیگر هستند. لایه‌گذاری پس از هر داده‌ای با با طولی غیرمضرب طول واژهٔ قراردادی، تعدادی بیت قرار می‌‎‌دهد تا همهٔ داده‌ها دارای آدرس مضرب عددی خاص مثلاً ۴ یا ۸ باشند. بسته‌بندی در مقابل، نقش بهینه‌سازی حجمی داده را بر عهده دارد. به‌طور مثال، یکی از کارهایی که در بسته‌بندی انجام می‌شود این است که بخش‌های تکرارشونده از داده را به صورت دنباله‌هایی که شامل آن بخش‌ها و تعداد تکرارشان است ذخیره می‌کند. این کار با وجود اینکه در حافظه صرفه‌جویی می‌کند، دو عیب را به همراه دارد:

1. در هر بار خواندن و نوشتن از حافظه یک بار پردازشی به پردازشگر اضافه می‌شود.
2. برنامه به صورت مستقیم به حافظه دسترسی نخواهد داشت، بلکه باید این کار را از طریق پیام‌های پی‌دی‌اف و سرویس‌های دسترسی کتابخانه‌ای بکند.

مثال

کد زیر از زبان C را در نظر بگیرید.

struct mystruct_A
{
   char a;
   int b;
   char c;
} x;

struct mystruct_B
{
   int b;
   char a;
} y;

اندازهٔ ساختارهای تعریف‌شده در بالا به ترتیب ۱۲ و ۸ می‌باشد. در زبان C پروسهٔ لایه‌گذاری به صورت خود به خود صورت می‌گیرد. به‌طور مثال در مورد ساختار اولی که در کد بالا آمده‌است، اتفاقی مشابه زیر می‌افتد:

struct mystruct_A {
    char a;
    char gap_0[3]; /* inserted by compiler: for alignment of b */
    int b;
    char c;
    char gap_1[3]; /* -"-: for alignment of the whole struct in an array */
} x;

در بالا می‌بینیم که طول داده‌ساختار کاراکتر به‌طور پیش‌فرض برابر ۱ بایت است، به همین علت خود کامپایلر ۳ بایت را به حافظه پس از جایی که این کاراکتر ذخیره شده‌است اضافه می‌کند تا شروع هر خانه حافظه‌ای که کد با آن سر و کار دارد دارای آدرسی مضرب ۴ باشد. همین اتفاق برای کاراکتر بعدی تعریف شده به عنوان c افتاده‌است. در مقابل پروسهٔ بسته‌بندی به صورت پیش‌فرض در کامپایلر C اتفاق نمی‌افتد و باید این تابع با عنوان $\_\_attribute\_\_((\_\_packed\_\_))$ به‌طور خاص صدا زده‌شود:

struct __attribute__((__packed__)) mystruct_A {
    char a;
    int b;
    char c;
};

به این ترتیب کد بالا از فرایند لایه‌گذاری که به صورت پیش‌فرض توسط کامپایلر صورت می‌گیرد جلوگیری می‌کند و ساختار یاد شده را در فضای ۶ بایت (هرکدام از ساختارهای کاراکتر ۱ بایت و ساختار عدد صحیح ۴ بایت) ذخیره می‌کند.