Muito bom os dois posts! Mas gostaria de corrigir um único ponto na resposta do maniero, onde ele fala sobre objetos não mudarem de tamanho na heap:

Para alocar no heap, que costuma na maioria das linguagens, mas não necessariamente precisa ser compartilhado pelas threads, os objetos precisam ter tamanho conhecido no momento da alocação e não podem variar (sendo pedante). Seria fisicamente muito complicado dar variabilidade no tamanho do objeto. Pense em um caminhão onde os pacotes dentro dele podem mudar de tamanho, para onde vão os pacotes que estão do lado dele? É uma questão bem concreta. Por isso não pode encher até a boca caminhão tanque. E assim os motoristas roubam(vam) combustível, tirando uma parte e deixando o caminhão no sol para dar o mesmo volume (por isso hoje se mede a temperatura quando vai descarregar). Objetos na memória não são líquidos.

Na realidade, em C, é possível alterar o tamanho de objetos alocados na heap em tempo de execução com o comando realloc().

void *realloc(void *ptr, size_t new_size);

O realloc recebe o endereço do objeto a ser redimensionado e o novo tamanho pra esse objeto. Caso consiga alterar o tamanho do objeto, ele retornará o mesmo endereço de memória, caso contrário, ele executará os passos a seguir:

1. Alocará um novo espaço de memória para o objeto;
2. Copiará o conteúdo atual do objeto para o novo espaço de memória;
3. Desalocará o espaço de memória anterior; e
4. Retornará o endereço do novo espaço de memória.

É bem mais fácil visualizar seu funcionamento com arrays, mas em C, essa operação pode ser feita com qualquer tipo de dados. Por exemplo, se alocarmos um array de int de 10 posições (40 bytes) e depois quisermos reduzir seu tamanho para 5 posições (20 bytes), é bem provável (uma "quase-certeza") que o endereço de memória retornado seja o mesmo, o array só ficou menor e deixou um espaço livre de 5 posições (20 bytes) ao seu lado.

Exemplo 1:

#include <stdio.h>
#include <stdlib.h>

int main() {
  int *array = malloc(10 * sizeof(int));
  printf("endereço anterior: %p\n", array);
  array = realloc(array, 5 * sizeof(int));
  printf("novo endereço:     %p\n", array);
  return 0;
}

Output do Exemplo 1:

endereço anterior: 0x1ccf2a0
novo endereço:     0x1ccf2a0

Obs: os endereços mudam em cada execução

Mas e se quisermos aumentar o tamanho do nosso array? Bom, às vezes ele vai alocar um novo espaço de memória, realizando toda a etapa de cópia do objeto pro novo espaço, como dito anteriormente, quando não houver espaço disponível ao seu redor. No exemplo a seguir, alocamos um array de 5 posições e depois tentamos redimensioná-lo para 10 posições, como "não existe" espaço livre ao seu redor, será retornado um novo endereço de memória.

Obs: usei "não existe" entre aspas porque existem detalhes sobre como o SO aloca esses espaços e como eles são expostos para o processo que não tenho conhecimento aprofundado pra explicar aqui

Exemplo 2:

#include <stdio.h>
#include <stdlib.h>

int main() {
  int *array = malloc(5 * sizeof(int));
  printf("endereço anterior: %p\n", array);
  array = realloc(array, 10 * sizeof(int));
  printf("novo endereço:     %p\n", array);
  return 0;
}

Output do Exemplo 2:

endereço anterior: 0x229c2a0
novo endereço:     0x229c6d0

Mas ele também pode reaproveitar espaços liberados por objetos que estavam na heap mas foram desalocados. Nesse caso, ele vai simplesmente alterar o tamanho do objeto e retornar o mesmo endereço. No próximo exemplo, são alocados dois arrays de 10 posições, depois o primeiro array é desalocado e, quando o segundo é redimensionado para 20 posições, o realloc() reaproveitará o espaço livre deixado pelo array desalocado.

Exemplo 3:

#include <stdio.h>
#include <stdlib.h>

int main() {
  puts("Alocação inicial");
  int *array1 = malloc(10 * sizeof(int));
  int *array2 = malloc(10 * sizeof(int));

  printf("array1: %p\n", array1);
  printf("array2: %p\n", array2);
  puts("");

  puts("Removendo array1 e realocando array2");

  free(array1);  // liberando o array1
  array1 = NULL; // atribuindo o ponteiro nulo pra ficar mais bonito no print :D
  array2 = realloc(array2, 20 * sizeof(int));

  printf("array1: %p\n", array1);
  printf("array2: %p\n", array2);

  return 0;
}

Output do Exemplo 3:

Alocação inicial
array1: 0x16836b0
array2: 0x16836e0

Removendo array1 e realocando array2
array1: (nil)
array2: 0x16836e0

Obs: se analisarem os endereços retornados, verão que eles não se crusam, mas novamente, isso é por conta de detalhes de como o SO expõe esses endereços da heap para o processo, que não tenho conhecimento suficiente pra explicar como funciona

Acredito que a maioria das linguagens não adota a estratégia do realloc por ser bem complicada de gerenciar. Acho que é como a herança múltipla em OOP, onde a maioria das linguagens prefere não permitir para mitigar possíveis problemas.

Espero que eu tenha contribuído pra discussão e que tenham gostado da explicação. Gostaria de saber onde estou errado também e, principalmente, sobre esses detalhes de como o SO expõe os endereços de memória pro processo.

Boa parte das linguagens não precisam ter conhecimento do tamanho do objeto para alocar na pilha. Java precisa, no momento, isso pode ser mudado. Se a intenção era falar especificamente de Java, está certo, mas não ficou claro. Todas as linguagens que alcançam um nível um pouco mais baixo, até mesmo C#, consegue alocar na stack sabendo o tamanho apenas no momento.

Boa, aqui estava querendo falar de "tempo de alocação", vou corrigir.

Há uma confusão sobre tipos por valor serem liberados quando saem de escopo. Existem tipos por valor que são liberados pelo GC, afinal se um objeto está no heap e ele contém objetos por valor dentro dele, é o GC que o libera, não é sobre o escopo

Boa, não tratei de casos em que os tipos de valor estão atrelados a um tipo de referência e tem um lifetime maior. Nesse caso realmente é o GC que trata de liberá-los.

No post tentei dissociar completamente os dois tipos de tipos, por brevidade.

Como adendo, a memória das strings fixas, como as usadas nos códigos exemplo, não ficam nem no heap, nem na stack, ficam em memória estática e duram por toda a aplicação, a alocação é feita já na carga do executável.

Boa, isso é algo que não tratei no artigo, infelizmente não dá pra entrar em todos os detalhes.

No C#, e outras linguagens, além da memória estática existe a string pool, que evita a alocação desnecessária de strings quando possível.

O tempo de vida do objeto no heap pode ser conhecido, o ideal até é que seja em tempo de compilação, e por sorte a maioria é

De fato, como exemplo tipos de referência que não tem a referência propagada e perdem escopo ao sair do local que o instanciou. Não queria dar a entender que objetos no heap nunca vão ter um lifetime definido.

Em geral os sistemas operacionais não impõem limite de tamanho para a stack de cada thread e todas podem ser configuradas durante a sua criação (a principal na carga). No Windows, até a última vez que eu vi, o padrão era 1MB, mas nada impede de criar com 4KB ou 4GB. É possível até ultrapassar esse limite.

Isso é outra coisa em que falhei em dizer que o limite padrão, mas como disse, pode ser configurado. Falhei também nos 2MB, para processos de 64bit está em 4MB.

Linguagens com GC são usadas em jogos de "tempo real", em locais de alta eficiência como o site Stack Overflow. Basta saber fazer.

Com certeza, o intuito aqui não é criticar o GC ou implementação específica de algum GC. Mas é evidente que, em busca de performance, é necessário facilitar seu trabalho

Usar algo que tem tamanho suficiente ajuda porque se precisar aumentar o tamanho do objeto, não pode, então a solução é criar um outro objeto maior em outro lugar e copiar os dados para esse novo lugar, e depois o GC terá que coletar o objeto velho. Isso pode gerar uma progressão geométrica e te destruir.

Assumo que isso ainda seja sobre o StringBuilder. É verdade, e o benefício dele começa a vir quando o custo de "gerar" a string final e seu processo é maior que o custo do SB em si.

Concordo que o post ficou muito específico para o C#, e não evidencio isso o suficiente, outra alteração que vou fazer.

Valeu por entrar mais em detalhes sobre as especificidades de stack e heap, e também sobre os tempos de execução e algoritmos do GC

Posso acrescentar um pouco mais à tua resposta! Mas minha contribuição vai ser exclusivamente acerca do C#.NET

Primeiro, nem toda classe que implementa a ICollection<T> utilizará um array. Mas o List<T>, que com certeza é a mais utilizada, usa um array em sua implementação.

Segundo, a eurística implementada em duas partes do código da List<T>. Os códigos que mostrarei aqui estão no repositório do .NET no GitHub, aqui o link pro arquivo de implementação da List<T> https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs.

A primeira parte está no método List<T>.Grow(), que é chamado sempre que a lista excede a capacidade anterior. É possível ver que a eurística é dobrar a capacidade até alcançar o patamar máximo que é Array.MaxLength.

/// <summary>
/// Increase the capacity of this list to at least the specified <paramref name="capacity"/>.
/// </summary>
/// <param name="capacity">The minimum capacity to ensure.</param>
internal void Grow(int capacity)
{
    Debug.Assert(_items.Length < capacity);

    int newCapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;

    // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
    // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
    if ((uint)newCapacity > Array.MaxLength) newCapacity = Array.MaxLength;

    // If the computed capacity is still less than specified, set to the original argument.
    // Capacities exceeding Array.MaxLength will be surfaced as OutOfMemoryException by Array.Resize.
    if (newCapacity < capacity) newCapacity = capacity;

    Capacity = newCapacity;
}

A segunda parte está implementada na propriedade List<T>.Capacity que é modificada no método List<T>.Grow(), onde é implementada toda a lógica de criação do novo array e cópia dos elementos do antigo pro novo. Não é feita a liberação do antigo array porque isso é feito pelo GC.

// Gets and sets the capacity of this list.  The capacity is the size of
// the internal array used to hold items.  When set, the internal
// array of the list is reallocated to the given capacity.
//
public int Capacity
{
    get => _items.Length;
    set
    {
        if (value < _size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
        }

        if (value != _items.Length)
        {
            if (value > 0)
            {
                T[] newItems = new T[value];
                if (_size > 0)
                {
                    Array.Copy(_items, newItems, _size);
                }
                _items = newItems;
            }
            else
            {
                _items = s_emptyArray;
            }
        }
    }
}