Uma pizza de 12 polegadas não é uma vez e meia mais pizza do que uma de 8 polegadas. É 2,25 vezes mais. Isso ocorre porque a área da pizza segue o quadrado do seu raio. As pessoas geralmente têm uma intuição ruim para áreas, ou qualquer coisa que cresça mais rápido do que seus limites lineares. É por isso que as pizzarias precificam por diâmetro e os clientes compram de forma confiável pizzas que não conseguem terminar.

A mesma falha de intuição estava dentro do pipeline de correspondência de scans 3D de um cliente pela maior parte de um ano. Custou-lhes o dobro de memória em cada worker da frota. Em algum lugar do código de pontuação havia uma tabela com uma linha e uma coluna por elemento.

Todos que leram aquele código viram uma lista quando deveriam ter visto um quadrado. O pipeline alinha dois scans de superfície, subtrai um do outro e inspeciona o que sobra. Se os dois scans forem do mesmo objeto, então o que sobra é nada.

Uma classe de scanner tem um modo de falha conhecido: onde o objeto tem uma face plana, o scanner às vezes registra uma pirâmide rasa em vez disso. Deixadas nos dados, essas pirâmides parecem diferenças geométricas reais e fazem com que uma correspondência verdadeira seja rejeitada. Então, antes de marcarmos dois itens como correspondentes, verificamos se a casca restante tem forma de pirâmide.

Se tiver, as peças da pirâmide são removidas dos objetos, em vez de serem consideradas como evidência de uma correspondência. Detectar uma pirâmide significa encontrar sua base plana, e o avaliador encontra a base olhando para a orientação da superfície. Cada triângulo na malha tem uma normal (uma unidade de direção perpendicular ao plano do triângulo) e os triângulos de uma base plana todos apontam aproximadamente para a mesma direção.

O avaliador agrupa normais em clusters. Em seguida, mede quão espalhado cada cluster está. O cluster mais compacto é o candidato a base, e se sua dispersão estiver abaixo de um limite, a base é aceita.

A dispersão era onde o quadrado vivia. Foi definida como a variância dos cossenos entre cada par de normais no cluster. Esta é uma medida perfeitamente razoável de dispersão, e cossenos são regularmente usados para comparar vetores, pois são rápidos, fáceis de calcular e invariantes em escala.

Para cada cluster, no entanto, a chamada construiu uma tabela de cossenos N * N. Se os clusters forem grandes, como em superfícies planas sobrepostas, isso resulta em uma tabela densa que potencialmente compara cada normal correspondente. No pior caso, a tabela se torna uma matriz quadrada.

Isso é um problema porque requer muita memória, e no pior caso a memória necessária é N^2 vezes a memória necessária para uma única comparação de cosseno. O que isso significou Na maioria das comparações N era pequeno e ninguém notou. A casca restante entre dois scans do mesmo objeto é fina.

Ela se fragmenta em muitos pedaços pequenos, e cada pedaço tem algumas centenas de normais. Algumas centenas ao quadrado não é nada. A exceção foi o caso que o pipeline mais queria acertar: dois scans do mesmo objeto feitos por scanners diferentes.

A subtração deixa uma casca fina contínua em vez de muitas. Para piorar as coisas, as superfícies da casca eram quase paralelas. Isso resultou em um cluster e uma tabela de dispersão densa de alta similaridade.

A oito bytes por entrada, uma tabela sobre um cluster na casa das dezenas de milhares é vários gigabytes por si só. Duas delas, mais as cópias de trabalho que a biblioteca faz ao longo do caminho, chegaram a aproximadamente quinze gigabytes na pior comparação que analisamos. Aquela única comparação definiu o piso de memória para cada worker da frota.

Cada trabalho de alinhamento foi provisionado com um slot grande o suficiente para sobreviver a ela, aproximadamente o dobro do que o trabalho típico precisava.