buddy allocator workshop
1.0.0
Este repositório contém algumas pequenas implementações de exemplo de alocadores de amigos. Eles foram projetados para alocar a memória física, embora possam ser usados para outros tipos de alocação, como a pilha. Eventualmente, o melhor desempenho será fundido em flor.
Primeiro, clone o repo. Em seguida, cd nele e faça cargo +nightly run para executar todos os alocadores de demonstração. Por padrão, o tamanho do bloco é 4kib e a quantidade de blocos é de 100.000, portanto, isso pode demorar um pouco para o exemplo da lista vinculada. Não se preocupe, na verdade não alocará nada - apenas zombar de blocos de memória. Passe -h ou --help para obter ajuda e visualizar o uso. Você pode editar o código -fonte para alterar os tamanhos de blocos Min/Max, etc. Para executar os testes de unidade, executar cargo test . Infelizmente, ainda não há benchmarks de carga, mas eu a comparei de maneira não científica na minha máquina Windows.
Testei os algoritmos, cronometrando várias implementações usando os relatórios construídos, alocando um Gibibyte em blocos 4kib (com a impressão) na minha máquina Windows. Se você tiver outros benchmarks para adicionar, consulte Contribuindo.
(MSI CX61-2QF)
| Implementação | Tempo | Taxa de transferência |
|---|---|---|
| Listas - vetores | 2 min | ~ 8.33E-3 Gib/s |
| Listas - listas duplamente vinculadas | 25min | ~ 6.66e-4 gib/s |
| RB árvores - vetores | ~ 0,3s | ~ 3,33 Gib/s |
| RB árvores - listas ligadas individuais | ~ 0,5s | ~ 2 gib/s |
| Árvore de bitmap | ~ 0,07s | ~ 14.28 Gib/s |
Nota: A taxa de transferência é extrapolada a partir do momento em que levou para alocar 1 Gib em blocos 4kib. Para implementações que têm complexidade> O (log n) (como a implementação ingênua baseada na lista), isso não será preciso - a taxa de transferência desacelerará à medida que mais blocos são alocados. Isso deve ser preciso para aqueles que têm uma complexidade de O (log n) ou menos.
Esta implementação mantém uma lista por pedido de bloco. É genérico sobre as listas de tipo de uso usado. Decidi usar dois tipos de listas: vetores ( Vec da std ) e listas duplamente vinculadas ( LinkedList , também da std ). As listas vinculadas são frequentemente valorizadas por seu tempo de pressão previsível (nenhuma realocação necessária para empurrar), enquanto os vetores têm melhor localidade de cache, pois os elementos são alocados em um bloco de memória contíguo. Eu usei listas duplamente vinculadas porque elas são mais rápidas para indexação do que listas ligadas individualmente, pois elas podem iterar na parte traseira ou na frente, dependendo se o índice está mais próximo do início ou do final da lista. Decidi testar ambos para ver o que teria melhor desempenho geral.
A implementação é recursiva. Para alocar um bloco livre de ordem K , ele primeiro procura bloqueios livres na lista de blocos da ordem K. Não mantém uma lista gratuita. Se nenhum for encontrado, ele se destaca ao tentar alocar um bloco de ordem K + 1. Finalmente, se em nenhum momento houvesse bloqueios livres encontrados, ele desistiu e em pânico. Assim que um é dividido ao meio, removendo o bloco original da lista de pedidos e empurrando as metades para a lista de pedidos imediatamente mais baixa. Em seguida, ele retorna o pedido e o índice do primeiro bloco em sua lista de pedidos. Você pode encontrar esse algoritmo em find_or_split .
Uma referência rápida e não científica na minha máquina Windows diz que levou cerca de dois minutos para alocar um Gibibyte completo (1024^3 bytes). Eu notei que o Split Second pausas de vez em quando teve que realocar todo o vetor para empurrar um elemento.
stdUm benchmark semelhante diz que levou vinte e cinco minutos para alocar um Gibibyte completo. Isso é mais de doze vezes mais lento que a mesma implementação com os vetores. No entanto, essa implementação não foi otimizada para listas vinculadas, por isso é um pouco injusto. Ao contrário da implementação com vetores, não notei nenhuma pausa, mas a alocação gradualmente ficou mais lenta.
Podemos concluir que, embora as listas duplamente vinculadas em teoria sejam mais rápidas em empurrar do que os vetores, elas ainda eram 12 vezes mais lentas que os vetores. Isso pode ocorrer porque a implementação foi um pouco a favor dos vetores (muita indexação) ou porque os vetores tinham uma localidade de cache mais alta e, portanto, sofreram menos erros de cache, enquanto as listas vinculadas experimentam altas erros de cache, pois têm elementos alocados individualmente.
Essa implementação mantém uma árvore vermelha-preta (da intrusive_collections ) para todos os blocos e uma lista gratuita para cada pedido. As listas gratuitas foram implementadas para Vec da STD e SinglyLinkedList da intrusive_collections . Eu escolhi uma lista individual vinculada, pois não haveria benefício real em vincular dobrar - o único método que teria se beneficiado (de maneira insignificante) é FreeList::remove , mas isso é sempre chamado no máximo no segundo elemento nesta lista gratuita, portanto, não há nenhum ponto real em otimizar isso. A árvore vermelha-preta individualmente aloca cada nó, o que piora a eficiência do cache, mas, diferentemente do BTreeSet / BTreeMap da std , sua pesquisa é O(log n) , enquanto std usa uma pesquisa linear, que não é O(log n) (você pode ler sobre isso aqui). No entanto, as árvores de std não não alocam os nós individualmente, portanto a localidade do cache é melhor. Decidi que, embora isso fosse verdade, já que um amigo alocador deve lidar com um número incrivelmente grande de blocos, era mais importante ter um algoritmo de pesquisa mais eficiente.
A implementação é recursiva. Para alocar um bloco livre de ordem K , ele primeiro procura blocos livres na lista gratuita dos blocos da ordem K. Se nenhum for encontrado, ele se destaca ao tentar alocar um bloco de ordem K + 1. Finalmente, se em nenhum momento houvesse bloqueios livres encontrados, ele desistiu e em pânico. Assim que o é dividido ao meio, removendo o bloco original da árvore e inserindo as metades, empurrando seus endereços para a lista gratuita relevante. Em seguida, retorna um cursor apontando para o primeiro bloco. Você pode encontrar esse algoritmo em find_or_split . Na camada mais externa de recursão (a função que realmente chama a função Recursive find_or_split ), o bloco retornado é marcado como usado e removido da lista gratuita.
O uso de vetores como listas gratuitas levou ~ 0,3s para alocar um GIB completo. Isso é ~ 0,2s mais rápido que as listas vinculadas como versão de listas gratuitas. Provavelmente, isso se deve a vetores com melhor localidade de cache.
O uso de listas vinculadas como listas gratuitas levou ~ 0,5s para alocar um GIB completo. Veja os vetores como listas gratuitas seção acima.
Essa implementação foi 400x mais rápida que a implementação ingênua baseada na lista (na melhor das hipóteses, usando vetores como listas gratuitas). Provavelmente, isso se deve a árvores em preto vermelho tendo operações O(log n) em geral, mais rápido que as pesquisas, inserções e removes de vetores ou listas vinculadas.
Essa implementação não é estritamente um bitmap, por si só, mas é uma modificação de um sistema de bitmap. Essencialmente, cada bloco na árvore armazena a maior ordem (totalmente mesclada) em algum lugar embaixo dela. Por exemplo, uma árvore que é toda gratuita com 4 pedidos se parece com o seguinte:
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
Se alocarmos um bloco de ordem 0, parece que isso (T é Aken ):
2
1 2
0 1 1 1
T 0 0 0 0 0 0 0
É implementado como uma matriz achatada, onde para uma árvore
1
2 3
A representação é 1; 2; 3 . Isso tem a bela propriedade de que, se usarmos índices a partir de 1 (ou seja, índices e não compensações), o índice do filho esquerdo de qualquer índice é 2 * index e a criança certa é simplesmente 2 * index + 1 . O pai é floor(index / 2) . Como todas essas operações funcionam com o 2S, podemos usar o eficiente de bits para executá -las ( index << 1 , (index << 1) | 1 e index >> 1 ).
Podemos fazer uma pesquisa binária para encontrar o bloco A livre da ordem desejada. Primeiro, verificamos se existem blocos da ordem desejada gratuitamente, verificando o bloco raiz. Se houver, verificamos se o filho esquerdo tem o suficiente. Se isso acontecer, verificamos novamente que é filho, etc. Se o filho esquerdo de um bloco não tiver blocos suficientes, simplesmente usamos seu filho certo. Sabemos que a criança certa deve ter livre livremente, ou o bloco raiz é inválido.
Essa implementação foi muito rápida. No meu computador, levou apenas ~ 0,07s para alocar 1GIB. Eu já vi que o desempenho de até 0,04 no meu computador - o desempenho flutue um pouco. Presumo que isso tenha a ver com a carga da CPU.
Essa implementação não possui uma localidade de cache muito boa, pois os níveis são armazenados longe um do outro, para que um bloco pai possa estar muito longe de seu filho. No entanto, todo o resto ainda é muito rápido, por isso é compensado. É também O (log n), mas praticamente é tão rápido que isso realmente não importa. Para referência: a alocação do 8GIB levou 0,6s para mim, mas eu o vi ter um desempenho muito melhor a> 150ms no laptop do @Gegy1000.
Se você tiver alguma coisa a acrescentar (como uma edição ao ReadMe ou outra implementação ou referência), sinta -se à vontade para enviar uma solicitação de tração! Você também pode criar um problema. Se você quer apenas conversar, sinta -se à vontade para me expressar na Rust Discord (Restioson#8323).
