Listas vinculadas aumentadas: um guia essencial

Como funciona uma lista vinculada?

Uma lista vinculada é uma estrutura de dados onde os campos de cada dado são conectados por ponteiros em vez de deslocamentos. Consiste em um elemento principal que armazena o primeiro e o último elemento, os chamados elementos do nó, contendo todos os campos necessários do usuário (como telefone, proprietário, empresa, etc.) e um ponteiro para o próximo nó. O último elemento está vinculado ao campo NULL que indica o final da lista.

Quando um novo elemento é adicionado à lista vinculada, o nó principal deve atualizar o ponteiro “cauda” para o novo nó final, e o ponteiro NULL anterior deve ser atualizado para a nova cauda.

Esta estrutura de dados permite um registro eficiente de novos dados sem redimensionar todo o array. É um método eficaz para armazenar dados somente gravação e não requer conhecimento prévio da quantidade de elementos. É uma estrutura de dados simples e, na memória, fica assim:

Lista vinculada para chaves de despejo

Em um artigo anterior, discutimos a necessidade de um buffer para varrer a árvore sem sair dela após cada exclusão de item. Em linguagens com GC, isso não é um problema. Porém, quando o código da aplicação gerencia memória, um buffer baseado em uma lista vinculada contendo elementos desatualizados pode ser uma solução.

Uma lista vinculada permite a adição rápida de elementos. No entanto, encontrar qualquer coisa na lista vinculada requer verificação sequencial, tornando-a inadequada para recuperação rápida de chaves. Portanto, é uma solução eficiente para registrar dados, criar buffers temporários e organizar dados para fazer leituras sequenciais de nós principais.

Encontrar elementos para antecipar é um exemplo de tal tarefa. A preempção é frequentemente usada nas diferentes implementações de cache. O cache contém dados que podem ser restaurados de outras fontes de memória com maior latência. O cache geralmente é armazenado na memória principal. A memória principal é limitada e, para uso eficaz, apenas um pequeno instantâneo de dados pode ser armazenado na memória principal.

Isso exige que usemos a memória de maneira mais inteligente, evitando o uso de memória para dados raramente solicitados e removendo esses dados se eles forem solicitados com pouca frequência.

Um método eficaz para remover campos do cache é o método menos usado recentemente (LRU). Aqui está a representação LRU abaixo:

Neste caso, a aplicação inclui pelo menos uma lista vinculada para armazenar objetos usados recentemente e possui outras estruturas de dados (como uma tabela hash) para uma pesquisa rápida. Os nós estão interligados.

Quando um usuário recupera dados da tabela hash, a lista vinculada atualiza esses dados movendo-os para o final. Como resultado, após várias operações, a cauda contém dados usados recentemente, enquanto a cabeça contém dados raramente solicitados.

Em casos de estouro de memória, o aplicativo pode verificar os primeiros N elementos para liberar memória suficiente. Esta é uma operação simples, pois a lista vinculada se adapta a varreduras sequenciais. Memória com dados raramente usados será liberada e novos nós mais frequentes poderão ser armazenados em cache.

 #include <stdlib.h> #include <stdio.h> typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr; } lnode_t; typedef struct list_t { lnode_t *head; lnode_t *tail; } list_t; lnode_t* lru_insert(list_t *list, char *ptr) { if (!list->head) { list->head = list->tail = calloc(1, sizeof(lnode_t)); list->head->ptr = ptr; return list->head; } lnode_t *saved_tail = list->tail; lnode_t *new = calloc(1, sizeof(sizeof(lnode_t))); new->ptr = ptr; saved_tail->next = new; new->prev = saved_tail; list->tail = new; return new; } void lru_update(list_t *list, lnode_t *lnode) { if (list->tail == lnode) { return; } lnode_t *saved_tail = list->tail; saved_tail->next = lnode; if (!lnode->prev) list->head = lnode->next; lnode->next = NULL; lnode->prev = saved_tail; list->tail = lnode; } void lru_evict(list_t *list, int items, void (*func)(void* arg, void *ptr), void* arg) { lnode_t *lnode = list->head; while(items-- && lnode) { func(arg, lnode->ptr); lnode_t *prev = lnode->prev; lnode_t *next = lnode->next; if (prev) prev->next = next; if (next) next->prev = prev; free(lnode); lnode = next; } if (!lnode) list->head = list->tail = NULL; } void print_deleted_obj(void *arg, void *ptr) { printf("evicted: %p\n", ptr); deleteThisInTheOtherStructure(arg, ptr); } int main() { list_t *list = calloc(1, sizeof(list_t)); lnode_t *test = lru_insert(list, "some data"); lru_insert(list, "another data"); lru_update(list, test); lru_evict(list, 1, print_deleted_obj, otherStructure); }

Uma observação: quando o número de elementos de uso difere significativamente em frequência (por exemplo, 95% das solicitações distribuídas nas 100 principais chaves de 1 milhão), a Splay Tree pode ser mais adequada para armazenar cache. Esta árvore é balanceada com base na frequência de uso de cada nó.

A ideia principal do Splay Tree é o oposto do LRU - os elementos mais utilizados estão localizados próximos à raiz, tornando esta estrutura de dados ideal como estrutura primária para o cache.

O despejo pode ser resolvido de duas maneiras: usando uma lista vinculada interconectada com a estrutura principal ou modificando uma Splay Tree para Threaded Binary Tree. Os nós da Splay Tree já estão ordenados por frequência de uso. Embora o encadeamento adicional de folhas de árvores possa exigir mais tempo de CPU, ele pode economizar memória.

Para compreender melhor a aceleração de dados usados recentemente na memória, você pode explorar um exemplo de migração de VM ao vivo neste link .

Melhore a velocidade de verificação da lista vinculada

Como foi mencionado anteriormente, as listas vinculadas oferecem a solução mais rápida para escrever dados. A velocidade de varredura é boa, mas é mais lenta que a velocidade de varredura do array.

Descrevi esse problema como localidade de dados no artigo anterior. Porém, por serem semelhantes às árvores binárias, as listas vinculadas têm potencial para melhorias. O desenrolamento de listas vinculadas permite armazenar mais dados em cada nó da lista. Assim, ele economiza memória no próximo nó ponteiro e, às vezes, melhora o desempenho, desde que o tamanho do elemento corresponda à linha de cache da CPU:

A ideia principal permanece inalterada, mas a representação da lista na memória será alterada.

Isso mudará de muitas maneiras. Existem 2 opções abaixo:

Essas melhorias aumentam o desempenho das listas vinculadas, mas acrescentam alguma complexidade ao código. Para operações de disco com uma lista vinculada, um nó desenrolado pode ter mais elementos. Uma maneira fácil de entender como isso funciona é imaginar uma lista vinculada de arrays.

No código, precisamos modificar a descrição da struct e, a partir de agora, ler ou escrever cada elemento do array da estrutura:

 typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr[3]; } lnode_t;

Ignorar lista

A lista de pulos é um método para melhorar as características de velocidade dos elementos de pesquisa em uma lista vinculada. Este tipo de lista vinculada armazena uma chave para ordenar a lista vinculada e inclui ponteiros extras para localizar nós de forma mais eficiente do que uma simples operação de varredura.

Nós extras aumentam a velocidade de travessia entre nós em uma lista de pulos. Funciona como uma pesquisa binária. Pelo contrário, leva mais tempo para adicionar novos elementos. Portanto, as listas de pulos devem ter uma chave. Os aplicativos podem fazer qualquer número de níveis para melhorar as características de velocidade. Na maioria dos casos, a melhor escolha é ter um pouco menos ou aproximadamente os mesmos níveis de altura da árvore. (Assista a foto acima)

Durante a pesquisa, um aplicativo inicia no nível mais alto, que é o caminho mais rápido. Ao detectar a chave próxima, ele desce para um nível inferior até que o nó desejado seja encontrado.

Este processo resulta em uma complexidade de tempo de O(log(n)). Por exemplo, usar 4 níveis para uma lista de pulos com 16 nós, 20 níveis para 1 milhão de nós e 32 níveis para 4 bilhões de nós fornece complexidade de tempo semelhante à árvore RB.

A lista de pulos é melhor pelos seguintes motivos:

• Simplicidade de implementação. Apesar das características semelhantes à árvore RB, é muito mais fácil de implementar e manter.

• Alta eficiência na adição de novos nós ao final da lista de pulos.

• Criar uma implementação thread-safe da lista de pulos é mais fácil do que a árvore.

Vamos explorar a implementação deste conceito!

Nós de estrutura:

 typedef struct skip_node { uint64_t key; uint64_t value; struct skip_node **forward; } skip_node; typedef struct skip_t { uint64_t level; uint8_t max_level; skip_node *header; } skip_t;

Função para criar nós:

 skip_node* create_skip_node(uint64_t key, int value, int level) { skip_node *newskip_node = (skip_node*)malloc(sizeof(skip_node)); newskip_node->key = key; newskip_node->value = value; newskip_node->forward = malloc(sizeof(skip_node)*level); for (uint64_t i = 0; i < level; i++) { newskip_node->forward[i] = NULL; } return newskip_node; } skip_t* skip_new(uint8_t max_level) { skip_t *list = (skip_t*)malloc(sizeof(skip_t)); list->level = 0; list->max_level = max_level; skip_node *header = create_skip_node(0, 0, max_level); list->header = header; for (uint64_t i = 0; i < max_level; i++) { header->forward[i] = NULL; } return list; }

Durante a inserção, a tarefa inclui a detecção do local correto para armazenar o nó e a determinação do número de níveis para conectar a este nó. O uso de uma função aleatória para determinar os níveis ajuda a simplificar o processo para cada novo nó. Em média, esta função aloca o segundo nível em 50% dos casos, o terceiro nível em 25% dos casos e assim por diante. Este método minimiza o tempo de acesso à memória para reequilibrar os elementos.

 uint64_t random_level(uint8_t max_level) { uint64_t level = 1; while (rand() < RAND_MAX / 2 && level < max_level) { level++; } return level; } void skip_insert(skip_t *list, uint64_t key, int value) { skip_node *update[list->max_level]; skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; if (current == NULL || current->key != key) { uint64_t newLevel = random_level(list->max_level); if (newLevel > list->level) { for (uint64_t i = list->level; i < newLevel; i++) { update[i] = list->header; } list->level = newLevel; } skip_node *newskip_node = create_skip_node(key, value, newLevel); for (uint64_t i = 0; i < newLevel; i++) { newskip_node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newskip_node; } } }

Função para pesquisar nós:

 skip_node* skip_search(skip_t *list, uint64_t key) { skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } } current = current->forward[0]; ++nodes_scan; if (current != NULL && current->key == key) return current; else return NULL; }

Uma função de benchmark para testar o desempenho de uma lista vinculada, lista de pulos e árvore RB. Os valores, usados como chaves, são definidos como potências de dois. O valor para fins de teste não importa.

 skip_t *skipList = skip_new(atoi(argv[1])); list_t *llist = list_new(); tree_t *tree = calloc(1, sizeof(*tree)); size_t to_index = 50000000; struct timespec s_icalc; struct timespec e_icalc; struct timespec s_scalc; struct timespec e_scalc; clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) tree_insert(tree, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; nodes_scan = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { node_t *node = tree_get(tree, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) skip_insert(skipList, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { skip_node* ret = skip_search(skipList, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) list_add(llist, NULL, NULL); clock_gettime(CLOCK_REALTIME, &e_icalc);

Resultados do teste dessas estruturas de dados nas chaves de crescimento sequencial:

Este é o melhor momento para inserir (se você não levar em conta uma simples lista vinculada) e um método bastante rápido para pesquisar elementos.

Resultados do teste dessas estruturas de dados nas chaves decrescentes sequencialmente:

Isso é fácil de entender: esta implementação de uma lista de pulos possui apenas um ponteiro principal para o primeiro elemento. Adicionar nós ao final é mais complexo. Para mudar essa abordagem, podemos adicionar um segundo ponteiro (para a cauda) ou uma lista de pulos reversa (a cabeça apontará para os valores grandes). Isso significa que uma lista de pulos é uma estrutura de dados eficaz para dados de log, como fluxos Kafka. Nesse caso, pode ser pelo menos duas vezes mais rápido que a árvore RB e mais fácil de implementar.

Skip List reduz a velocidade de inserção da Linked list, porém, para dados sequenciais, ela permanece mais rápida que outras estruturas de dados com tempo logarítmico de acesso aos elementos, principalmente enquanto as chaves crescem sequencialmente. Porém, qualquer crescimento sequencial das chaves complica as inserções na árvore, pois provoca muitas rotações para manter o equilíbrio da árvore.

Funciona efetivamente apenas quando o valor aumenta (ou diminui) ao longo da sequência. Por exemplo, se randomizarmos as chaves, os resultados serão diferentes:

Como pode ser visto, a distribuição entre os valores não afeta significativamente a característica de velocidade da árvore RB, mas afeta notavelmente o desempenho da lista de pulos.

Conclusões

Hoje, nossos aplicativos podem organizar os dados na memória ou no disco de diferentes maneiras. Mapas e listas desempenham um papel significativo na organização de dados em diferentes ordens para diversos fins. Essas estruturas garantem desempenho, eficiência de recursos e capacidade suficientes.

Ocasionalmente, não é suficiente para as nossas necessidades e a aplicação deve ser alterada nas partes críticas para ser mais otimizada. Alguns casos podem se beneficiar do uso de estruturas de dados mais adequadas, como árvores para correspondência inexata ou economia de memória. Outros - desde melhorias no algoritmo, como o uso de métodos assíncronos para melhorar o desempenho de threads individuais.

Quando todas as outras opções estiverem esgotadas, a abordagem restante é adaptar a estrutura de dados e ajustar a metodologia de uso. Existem exemplos de algumas mudanças na estrutura de dados para torná-los mais adequados para uma tarefa praticamente específica.

Embora uma lista vinculada seja principalmente uma estrutura de dados somente gravação e varredura de sequência, ela pode ser mais otimizada do que a árvore RB e permanecer eficiente em um caso somente gravação. No entanto, um aumento de características específicas pode impactar outras. Portanto, a melhor forma é priorizar o que é importante e descartar o que não é.