\Section{Способы собственной аллокации памяти}{21 сентября}{Никита Сазанович}
\Subsection{Бинарная куча кусков памяти}

\noindent
Задачи этого способа:
\begin{enumerate}  
	\item $new(x)$, возвращает указатель на кусок памяти размера $x$.
        \item $delete(a)$, удаляет кусок памяти $a$.
\end{enumerate}

\noindent
Сложности в этом способе начинают возникать, когда после удаления мы хотим выделить кусок. Ведь сумма размеров кусков возможно нам подходит, но нам нужен последовательный отрезок памяти размера  $x$.

\noindent
В современных операционных системах написаны хитрые аллокаторы, которые довольно оптимально выделяют память. Мы же обсудим упрощенную версию аллокатора основанного на бинарной кучке кусков. Кусок -- это пара $\q{\t{size, address}}$. Будем на вершине кучи хранить максимум из размеров. Тогда операции имеют следующий вид:

\begin{enumerate}  
        \item $new(x)$:
        
        Достаем максимальный элемент из кучи $\q{\t{maxsize, addr}}$. Если $maxsize<x$, то возвращаем кусок в кучу и говорим, что не смогли найти. Если же он нас устраивает $maxsize\ge x$, то скажем, что мы нашли такой адрес $= addr$ и, если $maxsize\ne x$, добавим в кучу $\q{\t{maxsize-x, addr+x}}$.
        
        Сложность операции: $\mathcal{O}($извлечение и добавление в кучу$)=\mathcal{O}(log_2{n})$, где $n$ - число кусков в куче.
        \item $delete(a)$:
        
        Чтобы корректно поддерживать куски в куче, нам нужно знать соседей текущего куска. Правый сосед, очевидно, начинается в $addr+size$. Для быстрого нахождения левого соседа заведем HashTable, которая для каждой правой границы куска будет хранить его начало. Тогда, в зависимости от состояния соседей куска мы удалим из кучи тех соседей, которые свободны, и добавим результирующий кусок. 
 
 
       \noindent 
        Сложность операции: $\mathcal{O}($извлечения и добавление в кучу$)+\mathcal{O}($запрос к HashTable$)=\mathcal{O}(log_2{n})+\mathcal{O}(1)=\mathcal{O}(log_2{n})$, где $n$ - число кусков в куче.
    \end{enumerate}
    
\Subsection{Стек}

\noindent
Нужно уметь делать:

\begin{enumerate}  
        \item $new(x)$ $\approx$ POP, возвращает указатель на кусок памяти размера $x$.
        \item $deletelast()$ $\approx$ PUSH, удаляет кусок памяти, выделенный последним.
    \end{enumerate}
    
   \noindent
   Преимуществом стека является то, что если его размер не превышает в любой момент $k$ байт памяти, то есть мы будем добавлять какую-то пачку кусков и потом ее освобождать, то они могут закэшироваться и наш стек будет работать быстрее.
  
  \noindent
  Практический пример использованию стека для собственного аллокатора с целью ускорения STL-стуктур (например set или map). Правда, мы не будем освобождать память из-за временных затрат, а воспользуемся только идеей $new(x)$ стека.
\lstset {language=C++}
\begin{lstlisting}
char mem[1 << 28];
int pos = 0;

void* operator new(size_t x) {
	void* res = mem + pos;
	pos += x;
	return res;
}

void operator delete(void* a) {
}
\end{lstlisting}
\noindent
Также в функциях, которые локально используют STL-структуры, можно хорошо ``очищать'' память, возвращая переменную $pos$ в ее состояние до вызова.
\lstset {language=C++}
\begin{lstlisting}
void f() {
	int old = pos;
	set<int> s;
	s.insert(5);
	s.insert(20);
	...
	pos = old;
}
\end{lstlisting}
\noindent
Но бывают сложные функции с несколькими точками выхода. Следовательно, нам придется везде возвращать значение переменной, а это легко забыть.
\lstset {language=C++}
\begin{lstlisting}
void f() {
	int old = pos;
	if () {
		pos = old;
		return;
	}
	if () {
		pos = old;
		return
	}
	...
	pos = old;
}
\end{lstlisting} 
\noindent
Решение состоит в создании собственной структуры с деструктором. Тогда  нужно всего лишь создать экземпляр этой структуры при входе в функцию.
\lstset {language=C++}
\begin{lstlisting}
struct T {
	int old;
	T() : old(pos) {}
	~T() {
		pos = old;
	}
};

void f() {
	T t {};
	if () {
		return;
	}
	if () {
		return
	}
	...
}
\end{lstlisting} 
\Subsection{Односвязный список}

\noindent
Функциональность:
\begin{enumerate}  
        \item $new()$, возвращает указатель на кусок памяти константного размера $C$.
        \item $delete(a)$, удаляет кусок памяти $a$.
    \end{enumerate}
    
\noindent
Будем использовать список свободных кусков. Для этого реализуем структуру Node и переменную указывающую на начало списка.
\lstset {language=C++}
\begin{lstlisting}
struct Node {
	void* data;
	Node* next;
};

Node* head;
\end{lstlisting} 
\noindent
Информация занимает $C$ байт, а указатель, например, $4$ байта. Тогда размер, на который нам нужно разбить всю память, это $C+4$ байта.

\noindent
Операции выглядят следующим образом:
        \lstset {language=C++}
\begin{lstlisting}
void* operator new() {
	void* res = head->data;
	head = head->next;
	return res;
}

void operator delete(void* a) {
	b = (Node*)a;
	b->next = head;
	head = b;
}
\end{lstlisting} 

 \noindent
 Нужно заметить, что здесь тоже уместно кэширование, т. к. после удаления куска памяти он становится первым в списке, и будет выдан быстрее, чем все следующие куски в списке.