Ao contrário de ligadores sequenciais que processam arquivos e seções na ordem em que aparecem, o mold adianta informações críticas antes que elas sejam estritamente necessárias. Essa abordagem permite que a lógica de resolução de símbolos e de aplicação de realocações trabalhe sobre dados já presentes nas camadas superiores da hierarquia de memória, reduzindo stalls de cache e leituras aleatórias.
Princípios Fundamentais da Pré-busca
O desenho do mold gira em torno de duas premissas:
- Fixação antecipada do layout do arquivo de saída: assim que o tamanho e a posição de cada seção são conhecidos, a escrita pode começar sem que toda a resolução simbólica tenha sido finalizada.
- Sobreposição de computação e E/S: enquanto blocos de dados são copiados para o arquivo final, outras threads continuam resolvendo dependências e aplicando realocações.
Para que essa sobreposição funcione, o mold precisa que certos dados estejam disponíveis antes do momento convencional de uso. Essa disponibilidade antecipada é obtida por meio de pré-carregamento, estruturas compactas e acesso sequencial controlado.
Carregamento Antecipado de Objetos
Uma das primeiras etapas do mold é varrer os arquivos objeto em paraleto, extraindo metadados antes da fase principal de linkagem. A leitura precoce do cabeçalho ELF, tabelas de seções e tabelas de símbolos permite que o ligador decida sobre o layout final enquanto ainda carrega outras entradas.
struct LinkContext {
ConcurrentMap<std::string_view, Symbol> symtab;
std::vector<ObjectFile> objects;
};
void prefetch_inputs(LinkContext& ctx) {
tbb::parallel_for_each(ctx.objects, [](ObjectFile& obj) {
obj.map_into_memory();
obj.parse_headers();
obj.extract_sections();
for (const auto& sym : obj.visible_symbols()) {
ctx.symtab.emplace_or_update(sym.name, sym);
}
});
}
Nesse trecho, parallel_for_each dispara a leitura de múltiplos arquivos simultaneamente. Como o sistema operacional e o hardware de E/S podem atender requisições concorrentes, a latência de leitura é reduzida. Os símbolos extraídos são inseridos em uma tabela hash concurrente, permitindo que outras threads consultem o mapa antes mesmo que todos os arquivos tenham sido processados.
Internação de Strings e Resolução Rápida
Nomes de símbolos e strings de seções repetem-se com frequência em grandes projetos. Em vez de comparar sequências de caracteres caractere por caractere, o mold converte cada string única em um identificador canônico.
| Aspecto | Abordagem Tradicional | Abordagem do mold |
|---|---|---|
| Comparação | O(n) sobre os caracteres | O(1) por identificador |
| Armazenamento | Cópias duplicadas | Instância única compartilhada |
| Estrutura de busca | Hash encadeado | Hash aberto com endereçamento |
A internação não apenas acelera comparações, como também torna a estrutura de cache mais previsível. Ponteiros para entradas de string canônicas ocupam menos espaço que as próprias strings, diminuindo a pressão sobre a cache.
Seções Mergeáveis e Localidade Espacial
Seções que agrupam strings constantes, como .rodata e seções semelhantes, são tratadas de forma especial. O mold classifica as subseções por endereço e tamanho, favorecendo o acesso contíguo. Quando uma thread processa uma dessas seções, a próxima leitura já foi carregada em uma linha de cache próxima, reduzindo falhas de cache causadas por saltos entre regiões distantes da memória.
Arquitetura Paralela e Consciência de Cache
Paralelismo por Dados
O mold evita modelos baseados em tarefas com dependências complexas. Em vez disso, divide o conjunto de seções, símbolos ou realocações em blocos independentes que podem ser processados em paralelo.
void scan_relocations_for_got(LinkContext& ctx) {
auto& sections = ctx.input_sections;
tbb::parallel_for(tbb::blocked_range<size_t>(0, sections.size()),
[&](const tbb::blocked_range<size_t>& range) {
for (size_t i = range.begin(); i != range.end(); ++i) {
auto& sec = sections[i];
for (const auto& rel : sec.relocations()) {
Symbol& sym = ctx.resolve(rel.symbol_index);
if (requires_got_entry(rel, sym)) {
sym.flags.fetch_or(NEEDS_GOT, std::memory_order_relaxed);
}
}
}
});
}
Essa estrutura mantém cada thread trabalhando sobre um intervalo contíguo de seções. O padrão de acesso sequencial dentro de cada intervalo melhora a localidade espacial, enquanto a ausência de locks pesados permite escalabilidade em processadores com muitos núcleos.
Map-Reduce para Identificação de Builds
O cálculo de identificadores de build, como o hash do arquivo, é dividido em duas fases. Primeiro, cada thread computa o hash de fragmentos independentes do arquivo. Depois, um estágio de redução combina os valores parciais em um único resultado.
- Map: hash de blocos de 1 MB executado em paralelo.
- Reduce: concatenação ordenada dos hashes parciais para obter o identificador final.
Estruturas Compactas para Reduzir Pressão de Cache
| Técnica | Benefício | Implementação |
|---|---|---|
| Índices de 32 bits | Menor consumo de cache | Substituir ponteiros por índices densos |
| Agrupamento de símbolos relacionados | Maior taxa de acerto | Ordenar símbolos por seção de origem |
| Alinhamento de linha de cache | Evitar falso compartilhamento | Preenchimento entre campos concorrentes |
Por exemplo, a tabela de símbolos armazena referências como índices compactas em vez de ponteiros de máquina. Isso reduz pela metade ou mais o tamanho da estrutura em arquiteturas de 64 bits, permitindo que mais entradas cabam em cada linha de cache.
Processamento Sequencial de Seções
Após a fase de pré-busca, as seções de entrada são ordenadas por deslocamento lógico e processadas em sequência. O acesso linear permite que o hardware de prefetch da CPU antecipe as próximas linhas de memória, reduzindo a latência percebida.
void materialize_output(LinkContext& ctx) {
std::sort(ctx.input_sections.begin(), ctx.input_sections.end(),
[](const InputSection& a, const InputSection& b) {
return a.output_offset < b.output_offset;
});
for (auto& sec : ctx.input_sections) {
if (sec.requires_copy) {
sec.copy_bytes_to(ctx.output_buffer);
}
sec.apply_relocations(ctx.output_buffer);
}
}
Comparação de Desempenho
Medições em uma máquina com 16 núcleos e 32 threads mostram a vantagem do modelo paralelo do mold sobre ligadores mais antigos.
| Programa (tamanho de saída) | GNU ld | GNU gold | LLVM lld | mold |
|---|---|---|---|---|
| MySQL 8.3 (0,47 GiB) | 10,84 s | 7,47 s | 1,64 s | 0,46 s |
| Clang 19 (1,56 GiB) | 42,07 s | 33,13 s | 5,20 s | 1,35 s |
| Chromium 124 (1,35 GiB) | N/A | 27,40 s | 6,10 s | 1,52 s |
A aceleração em relação ao lld varia entre 3,6× e 4,0×. A diferença principal não está apenas na quantidade de threads utilizadas, mas na capacidade de manter as unidades de execução ocupadas com trabalho útil ao invés de esperar por dados da memória principal.
Métricas de Acesso à Memória
A melhoria nas métricas de memória reflete o efeito combinado de prefetch, localidade e estruturas compactas.
| Métrica | Ligadores Tradicionais | mold |
|---|---|---|
| Taxa de acerto de cache | 60%–70% | 85%–95% |
| Uso de banda de memória | 40%–50% | 70%–80% |
| Precisão de prefetch | Baixa | Alta |
Integração em Sistemas de Build
Projeto CMake
Para projetos que usam CMake, basta adicionar a flag do ligador no momento da configuração.
if(CMAKE_SYSTEM_NAME STREQUAL "Linux")
set(CMAKE_EXE_LINKER_FLAGS
"${CMAKE_EXE_LINKER_FLAGS} -fuse-ld=mold")
set(CMAKE_SHARED_LINKER_FLAGS
"${CMAKE_SHARED_LINKER_FLAGS} -fuse-ld=mold")
endif()
Projeto Rust
No Rust, o ligador pode ser configurado por alvo no arquivo de configuração do Cargo.
[target.x86_64-unknown-linux-gnu]
linker = "clang"
rustflags = ["-C", "link-arg=-fuse-ld=/usr/local/bin/mold"]
Recomendações de Ajuste
- Grau de concorrência: em máquinas com muitos núcleos, deixe o
moldusar o pool de threads padrão, mas restrinja se outros processos críticos competirem por CPU. - Alocador de memória: alocadores modernos como
mimallocoujemalloccostumam oferecer melhor desempenho em workloads de linkagem com muitas alocações pequenas. - Tamanho de buffers internos: projetos grandes podem se beneficiar de buffers de saída maiores, reduzindo a quantidade de escritas fragmentadas.
Diagnóstico com Estatísticas de Execução
O mold oferece opções para emitir estatísticas de desempenho. Esses dados ajudam a identificar gargalos em projetos específicos.
mold -perf -o binario_final arquivo1.o arquivo2.o
Entre os valores reportados estão tempo de CPU, tempo de parede, grau de paralelismo e consumo de memória.
Desafios Técnicos e Soluções
Dependências em Ambiente Paralelo
A resolução de símbolos pode introduzir dependências entre threads. O mold lida com isso através de:
- Divisão em fases: cada fase termina com uma barreira implícita antes que a próxima comece.
- Flags atômicas: sinalizações leves indicam quando um símbolo já foi resolvido, evitando locks globais.
- Afinidade de dados: símbolos e seções relacionados são atribuídos à mesma faixa de índices, mantendo o trabalho de cada thread sobre dados próximos.
Determinismo do Arquivo Gerado
Embora a execução seja paralela, o binário final precisa ser determinístico. Para garantir isso, o mold:
- Ordena resultados de fases paralelas antes de combiná-los.
- Usa sementes fixas para funções de hash.
- Controla o padrão de alocação de memória para evitar diferenças causadas por endereços aleatórios.
Tendências Futuras
Ligadores de alta performance podem incorporar ideias de compiladores just-in-time e aprendizado de máquina. A integração com JIT permitiria re-linkar trechos dinamicamente, enquanto modelos preditivos poderiam ajustar a quantidade de prefetch com base no histórico recente de acessos.
| Capacidade | Estado Atual | Perspectiva |
|---|---|---|
| Identificação de hot spots | Indisponível | Aálise em tempo de execução |
| Reotimização dinâmica | Indisponível | Re-linkagem sob demanda |
| Layout adaptativo | Estático | Ajuste em tempo de execução |
Outra frente promissora é o uso de modelos preditivos para selecionar automaticamente entre estratégias de prefetch agressivas e conservadoras, equilibrando uso de banda de memória e ocupação de cache.