Alokator pamięci

11

Projektujesz nowy ezoteryczny język programowania, a jedną z funkcji, którą postanowiłeś dodać, jest dynamiczny alokator pamięci. Twój język określa specjalną dedykowaną wirtualną przestrzeń adresową dla przestrzeni programowej użytkownika. Jest to oddzielne od przestrzeni adresowej używanej przez alokator pamięci dla dowolnego stanu wewnętrznego.

Aby zmniejszyć koszt dystrybucji implementacji, rozmiar kodu musi być jak najmniejszy.

Berło

Musisz zapewnić trzy funkcje: inicjowanie, przydzielanie i cofanie przydziału.

Inicjalizacja

Ta funkcja przyjmuje pojedynczy dodatni parametr liczby całkowitej N. Oznacza to, że program użytkownika ma Nw swojej przestrzeni adresowej bajty, z których są N-1bajty do przydzielenia pamięci. Adres 0jest zarezerwowany dla „null”.

Zagwarantowane jest, że funkcja ta zostanie wywołana dokładnie raz przed każdym połączeniem alokacji / cofnięcia przydziału.

Należy pamiętać, że ta funkcja nie musi przydzielać pamięci fizycznej dla wirtualnej przestrzeni adresowej programu użytkownika; zasadniczo tworzysz „wygląd i styl” pustego alokatora pamięci.

Przeznaczyć

Funkcja przydzielania musi przyjąć żądanie liczby bajtów pamięci do przydzielenia. Dane wejściowe są gwarantowane jako pozytywne.

Twoja funkcja musi zwrócić adres liczby całkowitej na początek przydzielonego bloku lub 0wskazać, że nie ma dostępnego ciągłego bloku o żądanym rozmiarze. Jeśli ciągły blok o dostępnym rozmiarze jest dostępny w dowolnym miejscu w przestrzeni adresowej, musisz go przydzielić!

Musisz upewnić się, że żadne dwa przydzielone bloki się nie pokrywają.

Cofnij przydział

Funkcja dezalokacji musi przyjmować adres początku przydzielonego bloku i opcjonalnie może również przyjmować rozmiar danego bloku.

Pamięć, która została zwolniona, jest ponownie dostępna do alokacji. Zakłada się, że adres wejściowy jest prawidłowy.

Przykładowa implementacja języka Python

Pamiętaj, że możesz wybrać dowolną metodę śledzenia stanu wewnętrznego; w tym przykładzie instancja klasy śledzi to.

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]

Punktacja

To jest kod golfowy; najkrótszy kod w bajtach wygrywa. Nie musisz się martwić, że zabraknie pamięci dla dowolnego stanu wewnętrznego wymaganego przez twój program przydzielający.

Obowiązują standardowe otwory na pętle.

Tabela liderów

Pokaż fragment kodu

code-golf helloworld922
źródło
3
Wątpię, czy listy Python zajmują dokładnie jeden bajt na element. Czy „przydzielona pamięć” musi być w bajtach, czy może to być po prostu „typowa tablica / typ listy w Twoim języku”?
Klamka
4
Nie jest wymagany faktyczny przydział (z wyjątkiem czegokolwiek, co chcesz do wewnętrznego śledzenia stanu, które znajduje się na własnej wirtualnej przestrzeni adresowej); zwracasz tylko liczby całkowite do jakiejś abstrakcyjnej skończonej wirtualnej przestrzeni adresowej.
helloworld922
To help reduce the cost of distributing your implementation the size of the code must be as small as possibleczy może być wydajny (mały i wydajny to nie to samo), jak to możliwe? : D
The Coder
Co, projektowanie języka ?
Akangka
Podczas gdy wyzwanie jest motywowane doświadczeniem w projektowaniu języka, projektowanie języka nie jest tak naprawdę częścią zadania (raczej implementacja części jednego), więc usunąłem tag.
Martin Ender

Odpowiedzi:

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}

Podobnie jak odpowiedź MegaTom, ale do przechowywania stanu używa ciągu zamiast tablicy. Znak „o” oznacza otwartą komórkę, a „f” oznacza wypełnioną. To pozwala nam używać względnie zwięzłych funkcji manipulacji ciągiem Ruby:

?o*n inicjuje ciąg n "o".

/\B#{?o*n}/jest wyrażeniem regularnym pasującym n kolejnych „o”, które nie zawierają pierwszego znaku. sub!zastępuje pierwsze dopasowanie n „f” s.

"#$`" podaje ciąg po lewej stronie dopasowania lub pusty ciąg, jeśli nie było dopasowania, więc rozmiar jest albo przydzielonym indeksem, albo 0.

Deallocate po prostu ustawia wyznaczoną sekcję ciągu z powrotem na „o”.

histocrat
źródło
4

JavaScript (ES6), 88

Używanie zmiennej globalnej _( bardzo rzadkiej tablicy) do śledzenia.

Jak mogę to przetestować?

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
źródło
3

Ruby, 135

Ma globalną tablicę śledzącą, czy każda komórka jest przydzielona czy nie.

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
źródło
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~{#,_};)&

nzapisz całkowity rozmiar, lprzechowuje stan wewnętrzny. Alokator spróbuje przydzielić bezpośrednio za inną sekcją przydzielonej pamięci.

njpipeorgan
źródło