Распределитель памяти

11

Вы разрабатываете новый эзотерический язык программирования, и одну из функций, которую вы решили добавить, это динамический распределитель памяти. Ваш язык определяет специальное выделенное виртуальное адресное пространство для программного пространства пользователя. Это отдельно от адресного пространства, используемого распределителем памяти для любого внутреннего состояния.

Чтобы снизить стоимость распространения вашей реализации, размер кода должен быть как можно меньше.

Интерфейс

Вы должны предоставить три функции: инициализация, распределение и освобождение.

инициализация

Эта функция принимает один положительный целочисленный параметр N. Это означает, что у программы пользователя есть Nбайты в его адресном пространстве, из которого есть N-1байты для выделения памяти. Адрес 0зарезервирован для «ноль».

Гарантируется, что эта функция будет вызываться ровно один раз перед любыми вызовами выделения / удаления.

Обратите внимание, что этой функции не нужно выделять физическую память для виртуального адресного пространства программы пользователя; вы в основном создаете «внешний вид» полого распределителя памяти.

ассигновать

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

Ваша функция должна возвратить целочисленный адрес в начало выделенного блока или 0указать, что нет доступного непрерывного блока запрошенного размера. Если непрерывный блок доступного размера доступен где-либо в адресном пространстве, вы должны выделить его!

Вы должны убедиться, что никакие два выделенных блока не перекрываются.

Освобождает

Функция освобождения должна принимать адрес начала выделенного блока и, необязательно, также может принимать размер данного блока.

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

Пример реализации Python

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

class myallocator:
    def __init__(self, N):
        # address 0 is special, it's always reserved for null
        # address N is technically outside the address space, so use that as a
        # marker
        self.addrs = [0, N]
        self.sizes = [1, 0]

    def allocate(self, size):
        for i,a1,s1,a2 in zip(range(len(self.addrs)),
                                 self.addrs[:-1], self.sizes[:-1],
                                 self.addrs[1:]):
            if(a2 - (a1+s1) >= size):
                # enough available space, take it
                self.addrs.insert(i+1, a1+s1)
                self.sizes.insert(i+1, size)
                return a1+s1
        # no contiguous spaces large enough to take our block
        return 0

    def deallocate(self, addr, size=0):
        # your implementation has the option of taking in a size parameter
        # in this implementation it's not used
        i = self.addrs.index(addr)
        del self.addrs[i]
        del self.sizes[i]

счет

Это код гольф; выигрывает самый короткий код в байтах. Вам не нужно беспокоиться об исчерпании памяти для любого внутреннего состояния, требуемого вашим распределителем.

Применяются стандартные петлевые отверстия.

Leaderboard

Показать фрагмент кода

code-golf helloworld922
источник
3
Я сомневаюсь, что списки Python занимают ровно один байт на элемент. Должна ли «выделенная память» быть в байтах, или это может быть просто «тип массива / списка вашего языка»?
Дверная ручка
4
Фактическое распределение не требуется (за исключением того, что вы хотите для внутреннего отслеживания состояния, которое находится в его собственном виртуальном адресном пространстве); вы возвращаете только целые числа в некоторое абстрактное конечное виртуальное адресное пространство.
helloworld922
To help reduce the cost of distributing your implementation the size of the code must be as small as possibleили это может быть эффективным (маленький и эффективный не то же самое), насколько это возможно? : D
Кодер
Да, язык-дизайн ?
Akangka
Несмотря на то, что этот вызов мотивирован фоном проектирования языка, проектирование языка на самом деле не является частью задачи (скорее, частью ее реализации), поэтому я удалил тег.
Мартин Эндер

Ответы:

4

Руби, 80

i,a,d=->n{$m=?o*n},->n{$m.sub!(/\B#{?o*n}/,?f*n);"#$`".size},->n,s{$m[n,s]=?o*s}

Как и в ответе MegaTom, но для хранения состояния используется строка вместо массива. Символ «o» обозначает открытую ячейку, а символ «f» обозначает заполненную. Это позволяет нам использовать относительно лаконичные функции Ruby для работы со строками:

?o*n инициализирует строку из n "o" s.

/\B#{?o*n}/является регулярным выражением, совпадающим с n последовательными символами «о», которые не включают первый символ. sub!заменяет первое совпадение на n "f" s.

"#$`" дает строку слева от совпадения или пустую строку, если совпадения не было, поэтому размер равен либо выделенному индексу, либо 0.

Deallocate просто устанавливает обозначенный раздел строки обратно в «o».

histocrat
источник
4

JavaScript (ES6), 88

Использование глобальной переменной _( очень разреженного массива) для отслеживания.

Теперь, как я мог это проверить?

I=n=>(_=[1],_[n]=0)
A=n=>_.some((x,i)=>i-p<n?(p=i+x,0):_[p]=n,p=1)?p:0
D=p=>delete _[p]
edc65
источник
3

Руби, 135

Имеет глобальный массив для отслеживания того, выделена ли каждая ячейка или нет.

i=->n{$a=[!0]*n;$a[0]=0}
a=->n{s=$a.each_cons(n).to_a.index{|a|a.none?};n.times{|i|$a[s+i]=0}if s;s||0}
d=->s,n{n.times{|i|$a[s+i]=!0}}
MegaTom
источник
1

Математика, 152

i=(n=#;l={{0,1},{#,#}};)&
a=If[#=={},0,l=l~Join~#;#[[1,1]]]&@Cases[l,{Except@n,e_}:>{e,e+#}/;Count[l,{a_,_}/;e<=a<e+#]<1,1,1]&
d=(l=l~DeleteCases~{#,_};)&

nхранить общий размер, lсохраняет внутреннее состояние. Распределитель будет пытаться выделить сразу за другим разделом выделенной памяти.

njpipeorgan
источник