[devel] вопрос по языку Си - realloc & bit hacks

[devel] вопрос по языку Си - realloc & bit hacks

[Alexey Tourbin]

[-- Attachment #1: Type: text/plain, Size: 3014 bytes --]

lib/depends.c:
   213  static /*@exposed@*/ struct availablePackage *
   214  alAddPackage(availableList al,
   215                  Header h, /*@null@*/ /*@dependent@*/ const void * key,
   216                  /*@null@*/ FD_t fd, /*@null@*/ rpmRelocation * relocs)
   217          /*@modifies al, h @*/
   218  {
   219      HGE_t hge = (HGE_t)headerGetEntryMinMemory;
   220      HFD_t hfd = headerFreeData;
   221      rpmTagType dnt, bnt;
   222      struct availablePackage * p;
   223      rpmRelocation * r;
   224      int i;
   225      int_32 * dirIndexes;
   226      const char ** dirNames;
   227      int numDirs, dirNum;
   228      int * dirMapping;
   229      struct dirInfo_s dirNeedle;
   230      dirInfo dirMatch;
   231      int first, last, fileNum;
   232      int origNumDirs;
   233      int pkgNum;
   234  
   235      if (al->size == al->alloced) {
   236          al->alloced += al->delta;
   237          al->list = xrealloc(al->list, sizeof(*al->list) * al->alloced);
   238      }

Здесь в последних строках проверяется, достаточно ли места в массиве
al->list (перед вставкой нового элемента).  Если место кончилось, то
делается realloc "с запасом" al->delta.

Первый вопрос -- есть ли смысл таким образом избегать вызовов realloc.
А именно, резервирует ли realloc дополнительное место на случай
последующих вызовов.  Если это так, то здесь просто дублируется логика
realloc.

Второй вопрос -- как избавиться от дополнительных полей al->alloced
и al->delta.  Ясно, что наличие места в массиве можно проверять по
одному только полю al->size.  Например, если поле size кратно какому-то
числу, то при достижении кратности можно всякий раз увеличивать размер
на это число.  Это лучше всего делать со степенями двойки, потому что
в этом случае modulo заменятся на более дешёвый bitwise and.

	const int step = 8;
	if ((al->size & (step - 1) == 0)
		al->list = xrealloc(al->list,
			sizeof(*al->list) * (al->size + step));

Это получается арифметическая прогрессия -- размер массива всё время
увеличивается на step.  Можно сделать геометрическую прогрессию --
чтобы размер массива удваивался.

	static inline
	bool power_of_2(int x)
	{
		return (x & (x - 1)) == 0;
	}
	if (power_of_2(al->size))
		al->list = xrealloc(al->list,
			sizeof(*al->list) * (al->size << 1));

Существуют ли более оптимальный план для выделения памяти "с запасом"?
Ясно, что на больших размерах массива арифметическая прогрессия будет
расти слишком медленно.  С другой стороны, "удвоение" растёт слишком
быстро.  Хотелось бы размер массива не удваивать, а "уполторять" --
чтобы было 8, 12, 16, 24, 32, 64 и т.д,
т.е. 2^n, 2^n + 2^{n-1}, 2^{n+1}, ...

То есть алгоритм будет примерно такой

	if (полуторный_размер)
		realloc(двойной размер);
	else if (двойной размер)
		realloc(полуторный размер);

Может кто-нибудь знает как это можно попроще изобразить.  Или может
быть кто-нибудь видел как в других местах с realloc'ом поступают.

[-- Attachment #2: Type: application/pgp-signature, Size: 198 bytes --]

Re: [devel] вопрос по языку Си - realloc & bit hacks

[Александр Мыльцев]

2009/10/1 Alexey Tourbin <at@altlinux.ru>:
> Первый вопрос -- есть ли смысл таким образом избегать вызовов realloc.

Первый принцип оптимизации гласит:

1. Don't optimize.

К сожалению, трудно будет объяснить это апстриму. Но надо попытаться.

-- 
AVM