Alocador de memória

11

Você está projetando uma nova linguagem de programação esotérica e um recurso que decidiu adicionar é um alocador de memória dinâmico. Seu idioma especifica um espaço de endereço virtual dedicado especial para o espaço do programa do usuário. Isso é separado do espaço de endereço usado pelo alocador de memória para qualquer estado interno.

Para ajudar a reduzir o custo de distribuição de sua implementação, o tamanho do código deve ser o menor possível.

Interface

Você deve fornecer três funções: inicialização, alocação e desalocação.

Inicialização

Esta função aceita um único parâmetro inteiro positivo N. Isso significa que o programa de um usuário possui Nbytes no espaço de endereço dos quais existem N-1bytes para alocar memória. O endereço 0está reservado para "nulo".

É garantido que esta função será chamada exatamente uma vez antes de qualquer chamada de alocação / desalocação.

Observe que essa função não precisa alocar memória física para o espaço de endereço virtual do programa do usuário; você está basicamente criando a "aparência e aparência" de um alocador de memória vazio.

distribuir

A função de alocação deve receber uma solicitação do número de bytes de memória a ser alocada. A entrada é garantida para ser positiva.

Sua função deve retornar um endereço inteiro para o início do bloco alocado ou 0para indicar que não há nenhum bloco contíguo do tamanho solicitado disponível. Se um bloco contíguo do tamanho disponível estiver disponível em qualquer lugar do espaço de endereço, você deverá alocar!

Você deve garantir que nenhum dos dois blocos alocados se sobreponha.

Desalocar

A função de desalocação deve assumir um endereço do início de um bloco alocado e, opcionalmente, também pode assumir o tamanho do bloco especificado.

A memória desalocada está disponível novamente para alocação. Supõe-se que o endereço de entrada seja um endereço válido.

Exemplo de implementação em Python

Observe que você pode escolher qualquer método para acompanhar o estado interno; neste exemplo, a instância da classe controla isso.

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]

Pontuação

Isso é código de golfe; o menor código em bytes vence. Você não precisa se preocupar com a falta de memória para qualquer estado interno exigido pelo seu alocador.

Aplicam-se orifícios de loop padrão.

Entre os melhores

Mostrar snippet de código

code-golf helloworld922
fonte
3
Duvido que as listas Python ocupem exatamente um byte por elemento. A "memória alocada" precisa ser em bytes ou pode ser apenas "o tipo genérico de matriz / lista do seu idioma"?
Maçaneta
4
Nenhuma alocação real é necessária (exceto o que você deseja para rastreamento interno do estado, que está em seu próprio espaço de endereço virtual); você só está retornando números inteiros para algum espaço de endereço virtual finito abstrato.
precisa
To help reduce the cost of distributing your implementation the size of the code must be as small as possibleou poderia ser eficiente (pequeno e eficiente não são os mesmos) possível? : D
The Coder
Huh, design de linguagem ?
Akangka
Embora esse desafio seja motivado com um background de design de linguagem, o design de uma linguagem não faz parte da tarefa (em vez de implementar partes de uma), por isso removi a tag.
Martin Ender

Respostas:

4

Ruby, 80

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

Como a resposta do MegaTom, mas usa uma string em vez de uma matriz para armazenar o estado. O caractere "o" indica uma célula aberta, enquanto um "f" indica uma célula preenchida. Isso nos permite usar as funções de manipulação de string relativamente concisas do Ruby:

?o*n inicializa uma sequência de n "o" s.

/\B#{?o*n}/é uma expressão regular que corresponde a n "o" s consecutivos que não incluem o primeiro caractere. sub!substitui a primeira correspondência por n "f" s.

"#$`" fornece a sequência à esquerda da correspondência ou uma sequência vazia, se não houver correspondência; portanto, o tamanho é o índice alocado ou 0.

A desalocação apenas define a seção designada da string de volta para "o" s.

histocrata
fonte
4

JavaScript (ES6), 88

Usando uma variável global _(uma matriz muito esparsa) para acompanhar.

Agora, como eu poderia testá-lo?

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
fonte
3

Ruby, 135

Possui uma matriz global para acompanhar se cada célula está alocada ou não.

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
fonte
1

Mathematica, 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~{#,_};)&

narmazenar o tamanho total, larmazena o estado interno. O alocador tentará alocar logo atrás de outra seção da memória alocada.

njpipeorgan
fonte