В первом случае ты подсчитываешь все a, которые с любым x дают false.
Во втором случае, ты подсчитываешь все пары a, x, которые удовлетворяют условию.

Управление памятью в .NET для профессионалов

Как работает сборка мусора.
В .NET используется 2 фазная сборка мусора: Mark & Sweep (Пометить и Убрать).

Mark

На этом этапе обходится весь граф объектов. И выявляются все недостижимые.

Каким образом достижимость объектов определяется?

Достижимые это:
- Аллоцированные на стеке
- В статических полях
- Достижимые из достижимых (см. выше)

Все объекты, которые не удалось достичь (в граф не попали) - являются недостижимыми.

Но на стеке лежат числа. могут быть как числами, так и адресами, как и числами?

JIT копилятор достаточно умный, чтобы сгенерить код, который будет знать, что за объект/ссылка лежит на стеке. Так и получаются знания об объектах.

Sweep

Тогда итог, что языки с сборщиком мусора, под в 2 раза медленнее должны быть.(помимо сборки)

Вот тут интереснее. Есть несколько хаков как достигается большая производительность.
1. Линеризованное пространство памяти.
Адреса 0, 1 и 2 поколения расположены не абы где, а последовательно, друг за другом. Т.е. если нужно сократить пространство 0 поколения, то это означает простое передвигание указателя влево.

2. Переход в след. поколение происходит не всегда
Из 0 в 1 - переход быстрый, но из 1 в 2 - не всегда.
На этом этапе тоже может не затрачиваться много времени.

3. Ссылки из недостижимых объектов не обновляются - эти объекты и так нигде не участвуют
Обновление ссылок, к сожалению, - это ручное изменение и копирование. Ничего не поделаешь.

Теперь где-то, сборщик мусора, начинает переносить arr в другое место.

Ты слишком большой массив выделил, он аллоцируется в LOH. Оттуда не вытащишь.

Я много о чем не упомянул. Например, очередь финализации, таблица дескрипторов (Handle), сегментирование памяти и т.д. но ответы на основные вопросы дал

Используй HashSet. Если при Add вернет true - значит есть дубликат

Используй пул соединений. В asyncpg он поддерживается.

В доке есть