Я хочу сделать свой собственный Malloc

Ответ 1

Там довольно много хорошей литературы по реализации malloc и подобных вещей. но я замечаю, что вы включили С++ здесь - знаете ли вы, что вы можете написать собственную реализацию new и delete в С++? Это может быть полезно как способ сделать это легко.

В любом случае характеристики, которые вы хотите, будут в значительной степени зависеть от вашей рабочей нагрузки, то есть от характера использования с течением времени. Очевидно, что если у вас есть только mallocs и новые frees, это легко. Если у вас есть только mallocs одного или нескольких разных размеров блоков, это также просто.

В других языках вы получаете некоторый рычаг, имея возможность объединять память вместе, но C не настолько умный.

Основная реализация malloc просто выделяет заголовок, который содержит длину данных, "флаг использования" и многоязычную память. Затем Malloc создает новый заголовок в конце своего пространства, выделяет память и возвращает указатель. Когда вы освобождаете, он просто сбрасывает флаг использования.

Фокус в том, что, когда вы делаете много mallooc и бесплатно, вы можете быстро получить много небольших капель, которые не используются, но их сложно выделить. Таким образом, вам нужен какой-то bumpo gc для объединения блоков памяти.

Вы можете сделать более сложный gc, но помните, что это требует времени; вы не хотите свободно занимать много времени.

Там хорошая бумага в реализациях Solaris malloc, которые могут показаться вам интересными. Здесь еще один при создании альтернативного malloc, снова в Solaris, но основы те же. И вы должны прочитать статью Википедии о сборе мусора и следовать ей в некоторых более официальных документах.

Update

Вы знаете, вам действительно нужно взглянуть на коллекционеров мусора поколения. Основная идея заключается в том, что чем дольше что-то остается выделенным, тем более вероятно, что он останется выделенным. Это расширение упоминаемого вами "копирующего" GC. В принципе, вы выделяете новые вещи в одной части вашего пула памяти, назовите его g0. Когда вы достигнете отметки высокой воды, просмотрите выделенные блоки и скопируйте те, которые все еще используются в другой раздел памяти, назовите его g1. Затем вы можете просто очистить пространство g0 и начать выделение там. В конце концов g1 попадает на свой знак высокой воды, и вы исправляете это, очищая g0 и очищая g1, перемещая материал до g0, и когда вы закончите, вы переименуете старый g1 как g0 и наоборот и продолжаете.

Фокус в том, что в C особенно ручки, которые вы передаете в память malloc'ed, являются прямыми исходными указателями; вы не можете реально перемещать вещи без кучи большого лекарства.

Второе обновление

В комментариях @unknown спрашивает: "Не будет ли перемещение вокруг просто memcpy()". И действительно. но рассмотрите эту временную шкалу:

предупреждение: это не полная и непроверенная, просто для иллюстрации, только для развлечений, без явной или подразумеваемой гарантии

/* basic environment for illustration*/
void * myMemoryHdl ;
unsigned char lotsOfMemory[LOTS]; /* this will be your memory pool*/ 

Вы разделяете память

/* if we get past this, it succeded */
if((myMemoryHdl = newMalloc(SIZE)) == NULL)
    exit(-1);

В вашей реализации malloc вы создаете память и возвращаете указатель на буфер.

unsigned char * nextUnusued = &lotsOfMemory[0];
int partitionSize = (int)(LOTS/2);
int hwm = (int) (partition/2);
/* So g0 will be the bottom half and g1 the top half to start */
unsigned char * g0 = &lotsOfMemory[0];
unsigned char * g1 = &lotsOfMemory[partitionSize];


void * newMalloc(size_t size){
   void * rtn ;
   if( /* memory COMPLETELY exhausted */)
      return NULL;
   /* otherwise */
   /* add header at nextUnused */
   newHeader(nextUnused);     /* includes some pointers for chaining
                               * and a field with values USED or FREE, 
                               * set to USED */
   nextUnused += HEADERLEN ;  /* this could be niftier */
   rtn = nextUnused ;
   nextUnused += size ;
}

Некоторые вещи освобождены

  newFree(void * aHandle){
     *(aHandle-offset) = FREE ; /* set the flag in the header, 
                                 * using an offset. */
  }

Итак, теперь вы делаете все, и вы попадаете на свой знак высокой воды.

 for( /* each block in your memory pool */ )
    if( /* block header is still marked USED */ ) {
        memcpy(/* block into other partition */);
    }
 /* clear the partition */
 bzero(g0, partitionSize);

Теперь вернитесь к исходному дескрипту, сохраненному в myMemHdl. На что это указывает? (Ответ. Вы просто установили его в 0x00 с помощью bzero (3).)

То, где приходит волшебство. По крайней мере на C указатель, который вы вернули из вашего malloc, больше не находится под вашим контролем - вы не можете его перемещать после факта. В С++ с определенными пользователем типами указателей вы можете исправить это.

Ответ 2

Было бы полезно узнать немного больше о том, что вы пытаетесь сделать. Это для одного типа? Или набор относительно однородных типов?

• Пулы памяти - это проверенный метод, если вам нужно ускорить выделение для типа ввода (одним из возможных недостатков является то, что вы можете перепрыгивать всю память, влияя на производительность кэша).
• Методы распределения приложений обычно включают округление всех распределений до размеров ведра, зависящих от профиля, так что вы продолжаете фрагментацию.
• В многопоточных приложениях обычно есть пулы для потоков, которые могут быть выделены из-за отсутствия риска конкурировать с другими потоками.

Документ для tcmalloc довольно хорош в описании современного уровня техники для этих методов.

Здесь не слишком много сложного материала, но вы, вероятно, изобретаете колесо. Это несколько библиотек с открытым исходным кодом.

Ответ 3

Не используйте идею № 1, вы будете тратить много ресурсов, которые потенциально могут остаться неиспользованными для всего выполнения приложения, все время останавливая использование других процессов (в зависимости от того, сколько вы планируете брать).