Vc mencionou alocação em blocos e até mesmo a implementação de alocadores personalizados. Isso é possível de se fazer para tornar esse código mais rápido?
Uma abordagem muito simples e ingênua seria, em vez de alocar cada entrada individualmente, alocar, digamos, 1000 de uma vez. Ou simplesmente alocar, digamos, 1 KB de memória, seria mais inteligente e alinhar o número de elementos para caber nesse tamanho de bloco predefinido. E se você estiver realmente preocupado com desempenho, poderia ajustar esse tamanho para preencher a cache L1 do seu processador.
Se você quiser ficar mais sofisticado, consulte a documentação do cppreference para o alocador polimórfico e etc. Ou se você quiser ir ainda mais fundo, estude a documentação do Linux para brk e implemente seu próprio malloc com ele. Ou não.
Se vc quiser baixar o nível para "controlar melhor a performance" então vc deve ser um DEUS e nesse caso melhor partir direto para o assembly.
Novamente, entender quais chamadas do sistema acontecem e quando é a primeira coisa a começar a entender e pensar sobre desempenho. Não, não precisa ser um deus. Mas tem que saber de sistemas operacionais e organização de computadores, no mínimo.
Programar em assembly, é uma grande perda de tempo. Compiladores modernos são altamente otimizados e geralmente superam em muito capacidade de micro-otimização humana.
No entanto, quando desempenho é crítico, uma prática essencial é examinar o código assembly gerado pelo compilador para identificar possíveis gargalos e oportunidades de otimização. Algumas vezes, o compilador pode falhar em gerar o código mais eficiente. Em muitos casos, alterar a construção da linguagem de alto nível é suficiente.
Além disso, temos as instruções mágicas (como as vetorias) de processadores atuais. Compiladores são bastante inteligentes e frequentemente otimizam o código para usar essas instruções sem intervenção explícita do programador, mas, em muitos casos, é necessário utilizá-las diretamente em código C/C++ de forma inline.
Um abraço e bons estudos!