12-дюймовая пицца — это не в полтора раза больше пиццы, чем 8-дюймовая. Это в 2,25 раза больше. Это происходит потому, что площадь пиццы подчиняется квадрату её радиуса. У людей обычно плохая интуиция в отношении площадей или чего-либо, что растёт быстрее, чем его линейные границы. Именно поэтому пиццерии устанавливают цены по диаметру, а клиенты стабильно покупают пиццы, которые не могут доесть. Та же ошибка интуиции сидела в пайплайне сопоставления 3D-сканов одного клиента почти год. Она стоила им вдвое больше памяти на каждом воркере в парке. Где-то в коде скоринга была таблица с одной строкой и одним столбцом на каждый элемент. Все, кто читал этот код, видели список, хотя должны были видеть квадрат. Пайплайн выравнивает два скана поверхности, вычитает один из другого и проверяет, что осталось. Если два скана принадлежат одному объекту, то остаток — это ничего. Один класс сканеров имеет известный режим сбоя: там, где у объекта есть плоская грань, сканер иногда записывает вместо неё мелкую пирамиду. Оставленные в данных, эти пирамиды выглядят как реальные геометрические различия и приводят к отклонению истинного совпадения. Поэтому перед тем, как отметить два элемента как совпадающие, мы проверяем, имеет ли остаточная оболочка форму пирамиды. Если да, то части пирамиды удаляются из объектов, а не рассматриваются как доказательство совпадения. Обнаружение пирамиды означает нахождение её плоского основания, и скорер находит основание, глядя на ориентацию поверхности. Каждый треугольник в сетке имеет нормаль (единицу направления, перпендикулярную плоскости треугольника), и треугольники плоского основания все направлены примерно в одну сторону. Скорер группирует нормали в кластеры. Затем он измеряет, насколько разбросан каждый кластер. Самый плотный кластер — кандидат в основание, и если его разброс ниже порога, основание принимается. Разброс — это то, где жил квадрат. Он был определён как дисперсия косинусов между каждой парой нормалей в кластере. Это совершенно разумная мера разброса, и косинусы регулярно используются для сравнения векторов, так как они быстрые, легко вычисляются и инвариантны к масштабу. Однако для каждого кластера вызов строил таблицу косинусов N * N. Если кластеры большие, например на плоских перекрывающихся поверхностях, это приводит к плотной таблице, которая потенциально сравнивает каждую соответствующую нормаль. В худшем случае таблица становится квадратной матрицей. Это проблема, потому что она требует много памяти, и в худшем случае требуемая память в N^2 раз больше памяти, требуемой для одного сравнения косинусов. Что это значило В большинстве сравнений N было маленьким, и никто не замечал. Остаточная оболочка между двумя сканами одного объекта тонкая. Она распадается на множество мелких частей, и каждая часть имеет несколько сотен нормалей. Несколько сотен в квадрате — это ничто. Исключением был случай, который пайплайн больше всего хотел обработать правильно: два скана одного объекта, сделанные разными сканерами. Вычитание оставляет одну непрерывную тонкую оболочку, а не много. Что усугубляло ситуацию, поверхности оболочки были почти параллельны. Это привело к одному кластеру и плотной таблице разброса с высоким сходством. При восьми байтах на запись таблица для кластера в высоких десятках тысяч сама по себе составляет несколько гигабайт. Две из них, плюс рабочие копии, которые библиотека делает по ходу дела, достигли примерно пятнадцати гигабайт в худшем сравнении, которое мы профилировали. Это одно сравнение установило минимальный порог памяти для каждого воркера в парке. Каждая задача выравнивания была подготовлена с слотом, достаточно большим, чтобы пережить его, примерно вдвое больше того, что нужно типичной задаче.