Недавно мне поставили задачу улучшить некоторый встроенный код, в котором непропорционально много времени было потрачено на malloc.
Клиент хочет простого исправления, которое может быть выполнено с помощью некоторых очень простых команд поиска и замены (то есть без значительных и сложных изменений исходного кода), обеспечивая при этом существенную выгоду.
При анализе кажется, что подавляющее большинство (~ 80%) выделений было для 128 байтов или меньше.
С этой целью я собрал некоторое доказательство концептуального кода с использованием быстрого пула, идея в том, что одно выделение из malloc выполняется при запуске (достаточно для хранения, например, 1024 блоков по 128 байт каждый) и ассигнования, которые могли бы быть удовлетворены из этого быстрого пула. Я надеялся, что удаление более сложных вычислений в malloc (более сложных, поскольку оно должно обрабатывать блоки различного размера) приведет к увеличению скорости.
Затем весь исходный код изменяется на использование быстрого пула вместо обычного malloc. Если бы быстрый пул был исчерпан или для выделения потребовалось больше, чем размер блока, запрос был бы передан на malloc.
Результаты были неплохими, что дало мне (примерно) 50% сокращение времени, но мне интересно, смогу ли я сделать лучше.
Функции быстрого подключения показаны ниже. Сначала заголовочный файл:
#ifndef QUICKPOOL_H_INCLUDED
#define QUICKPOOL_H_INCLUDED
#include <stdlib.h>
typedef struct qp_pool_s qp_pool;
qp_pool *qp_create (size_t, size_t);
qp_pool *qp_destroy (qp_pool *);
void *qp_malloc (qp_pool *, size_t);
void *qp_free (qp_pool *, void *);
#endif
Функции create и destroy позволяют создавать различные пулы с разными размерами блоков и количеством блоков:
#include <string.h>
#include "quickpool.h"
// Various global values.
#define DEFLT_BLKS 1024
#define DEFLT_SZ 128
struct qp_pool_s {
char *data; // Actual blocks.
char *enddata; // First byte beyond data.
char *isused; // Used map for blocks.
size_t total_blks; // Number of blocks in pool.
size_t free_blks; // Free blocks in pool.
size_t blk_sz; // Size of each block.
size_t low_free; // Lowest free block.
};
qp_pool *qp_create (size_t quant, size_t sz) {
// Zero means a default size.
if (quant == 0) quant = DEFLT_BLKS;
if (sz == 0) sz = DEFLT_SZ;
// Allocate memory blocks for pool.
qp_pool *pool = malloc (sizeof (*pool));
if (pool == NULL) return NULL;
if ((pool->data = malloc (quant * sz)) == NULL) {
free (pool);
return NULL;
}
if ((pool->isused = malloc (quant)) == NULL) {
free (pool->data);
free (pool);
return NULL;
}
// Set information on pool and return it.
pool->enddata = &(pool->data[quant * sz]);
memset (pool->isused, 0, quant);
pool->total_blks = quant;
pool->free_blks = quant;
pool->blk_sz = sz;
pool->low_free = 0;
return pool;
}
qp_pool *qp_destroy (qp_pool *pool) {
// Just free all the memory for pool.
if (pool != NULL) {
free (pool->data);
free (pool->isused);
free (pool);
}
return NULL;
}
А затем есть аналоги malloc и free:
void *qp_malloc (qp_pool *pool, size_t sz) {
int index;
// If no pool, need more than BUFSZ bytes or pool empty, use default.
if (pool == NULL) return malloc (sz);
if ((sz > pool->blk_sz) || (pool->free_blks == 0))
return malloc (sz);
// Otherwise, get from quickpool. First we find a free block.
for (index = pool->low_free; pool->isused[index]; index++)
;
// Then we mark it used.
pool->isused[index] = 1;
pool->free_blks--;
// Set lowest possible free block for speeding up next search.
pool->low_free = index + 1;
return &(pool->data[index * pool->blk_sz]);
}
void *qp_free (qp_pool *pool, void *ptr) {
int index;
// No pool created, use default.
if (pool == NULL) {
free (ptr);
return NULL;
}
// Not in quick pool, use default.
if (((char*)ptr < pool->data) || ((char*)ptr >= pool->enddata)) {
free (ptr);
return NULL;
}
// This is a quickpool address, free it.
index = ((char*)ptr - pool->data) / pool->blk_sz;
pool->isused[index] = 0;
pool->free_blks++;
// Optimise next search.
if (index < pool->low_free)
pool->low_free = index;
return NULL;
}
Для полноты основная программа тестирования приведена ниже:
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "quickpool.h"
#define FREE 0
#define ALLOC 1
#define NUMPTRS 512
static void *pointer[NUMPTRS];
static size_t numPointers = 0;
int main (int argCount, char *argVal[]) {
int count, val, index, memsz, stMode, seed;
qp_pool *quickPool;
seed = atoi (argVal[1]);
stMode = (strcmp (argVal[2], "standard") == 0);
srand (seed);
int baseline = clock();
quickPool = qp_create (0, 0);
for (count = 0; count < 1000000; count++) {
if (numPointers == 0)
val = ALLOC;
else if (numPointers == NUMPTRS)
val = FREE;
else if (numPointers > NUMPTRS/2)
val = ((rand() % 100) < 50) ? FREE : ALLOC;
else
val = ((rand() % 100) < 33) ? FREE : ALLOC;
if (val == FREE) {
index = rand() % numPointers;
if (stMode)
free (pointer[index]);
else
qp_free (quickPool, pointer[index]);
pointer[index] = pointer[--numPointers];
} else {
memsz = rand() % 160;
if (stMode)
pointer[numPointers++] = malloc (memsz);
else
pointer[numPointers++] = qp_malloc (quickPool, memsz);
}
}
quickPool = qp_destroy (quickPool);
baseline = clock() - baseline;
printf ("%d\n", baseline * 1000 / CLOCKS_PER_SEC);
return 0;
}
вместе со сценарием оболочки для анализа:
#!/usr/bin/bash
normal=0
quick=0
printf " %10s %10s\n" Normal Quick
printf " ========== ==========\n"
for iter1 in 0 1 ; do
for iter2 in 0 1 2 3 4 5 6 7 8 9 ; do
seed=$RANDOM
val=$(./qptest.exe $seed standard)
printf "${iter1}${iter2} %10d " $val
((normal = normal + val))
val=$(./qptest.exe $seed quickpool)
printf "%10d\n" $val
((quick = quick + val))
done
done
printf " ========== ==========\n"
((pct = quick * 100 / normal))
printf "sum %10d %10d (%d%%)\n" $normal $quick $pct
который выводит:
Normal Quick
========== ==========
00 469 219
01 453 219
02 453 235
03 453 219
04 453 235
05 453 219
06 469 219
07 453 234
08 453 219
09 453 219
10 453 219
11 453 235
12 453 235
13 453 219
14 453 219
15 453 235
16 453 235
17 453 235
18 469 219
19 469 234
========== ==========
sum 9124 4522 (49%)
Теперь мой вопрос заключается в следующем: есть ли другие возможности для оптимизации кода быстрого пула, который не зависит от обхода требований:
- простое в интеграции исправление, требующее только простого глобального поиска и замены в исходном коде.
- возможность иметь пулы разного размера (количество блоков) с блоками разного размера.
- сбрасывается до
malloc, если быстрый пул не может удовлетворить запрос.