Для выполнения работы (goodput от good and throughput/output) на CPU программам необходим доступ к RAM. Скорость, с которой программы могут передавать данные в/из оперативной памяти, не растет так быстро, как производительность процессоров, получающие новые фичи на каждое ядро и большее количество ядер.
В 95-2000 все много рассказывали про Memory Wall, что мол, DRAM не будет расти так быстро. Это уже реальность, не растёт.
В целом доступ к RAM остался в около 100ns, даже если вы меняете один процессор на другой, вы получаете меньше преимуществ, если вы постоянно промахиваетесь по кешам. L1/L2/L3 растут, да, но и там есть предел, и вряд ли они будут больше сотни мегабайт. Поэтому когда вы оптимизируете программу, очень полезно посмотреть на так называемые LLC (Last Level Cache) Misses.
Советы тут какие-то дурацкие, мол
1. Никогда не используйте структуру linked list, это промах по памяти на каждую итерацию
2. Не используйте бакетные хеш таблицы, они очень плохи, так как промахиваются постоянно. Используйте хэш таблицы с открытой адресацией
3. Лишний раз не копируйте объекты и тут языки вроде C/C++/Rust выигрывают, потому что там явно указываешь, что копировать, а что нет
4. Делаете по возможности структуры более компактными
Если будете итерироваться и использовать id в векторе/слайсе чаще, процессор хуже будет класть данные в кеши, по возможности, когда это очень важно, делаете два отдельных вектора id и name.
5. Даже какие-то обычные операции в роде сложения матриц нельзя делать как вектор векторов/массив массивов, правильно хранить всё в одном куске памяти и логически разделять строки
6. Если объекты логически большие, структурные как json или protobuf, создавайте арены/memory pool, когда вы кладёте много объектов на один и тот же кусок памяти. Самый простой пример -- вектор строк, если строки разбросаны в памяти, то даже банальные операции типа сортировки будут в разы медленнее не потому, что строки надо больше сравнивать, а потому, что всегда есть плата пойти в память. Поэтому строки со Small String Optimization и пишут в библиотеках, плюс они выигрывают на скейле.
7. Если вы можете утилизировать память, делать более предсказуемой доступы, то вы будете выигрывать у других приложений. Пример -- ClickHouse хорошо понял историю поколоночного формата, потому что памяти так удобнее: утилизация всего сервера в итоге растёт. Библиотеки вроде ZSTD просто напичканы software prefetches, а процессоры Intel/AMD/ARM делают отдельные инструкции для копирования памяти произвольного размера.
8. Обрабатывайте меньше данных в памяти. Сжатие как минимум, как максимум -- слежка сколько вы тратите на пользователя/entity данных. Я находил на своём опыте какие-то огромные пробелы в том, зачем мы храним столько данных. Хоть и бизнесы скейлятся, как правило начинается бардак в схемах/логах. Детектить такие вещи тяжело. SQL со своими селективными предикатами здесь побеждает обычные языки программирования и MapReduce, в последнем надо писать код -- ставить трекеры на форматы в компилируемых языках тяжело.
Развитие SIMD, больше правильных структурированных форматов, подстройка парсеров под данные, самокорректирующиеся под data оптимизации вроде JIT будут доминировать в ближайшее время развитие data proc. Истории с прорывами происходят вроде SIMDJSON и тд, но никакого систематичного решения пока не видно, эта область имеет шансы сильно развиться или умереть, принимая, что это в какой-то степени предел и надо думать в других направлениях типа GPU/TPU/Quantum/FPGA/etc.
В Google мы репортим среднюю утилизацию сервера в 60% и проблемы с памятью одни из самых противных -- данных просто тьма, решения вроде использовать flat_hash_map, а не unordered_map помогают лишь держать это число на плаву. Тот, кто поймёт эту историю лучше всего, будет платить за датацентры меньше всего денег.
В эпоху рецессии кажется это может быть ещё более важно. Постараюсь сделать серию из постов про то, как увеличивать полезность при помощи уменьшения процессинга памяти. Тут много нетривиальных компромиссов.
В 95-2000 все много рассказывали про Memory Wall, что мол, DRAM не будет расти так быстро. Это уже реальность, не растёт.
В целом доступ к RAM остался в около 100ns, даже если вы меняете один процессор на другой, вы получаете меньше преимуществ, если вы постоянно промахиваетесь по кешам. L1/L2/L3 растут, да, но и там есть предел, и вряд ли они будут больше сотни мегабайт. Поэтому когда вы оптимизируете программу, очень полезно посмотреть на так называемые LLC (Last Level Cache) Misses.
Советы тут какие-то дурацкие, мол
1. Никогда не используйте структуру linked list, это промах по памяти на каждую итерацию
2. Не используйте бакетные хеш таблицы, они очень плохи, так как промахиваются постоянно. Используйте хэш таблицы с открытой адресацией
3. Лишний раз не копируйте объекты и тут языки вроде C/C++/Rust выигрывают, потому что там явно указываешь, что копировать, а что нет
4. Делаете по возможности структуры более компактными
struct Data {
int id;
std::string name;
};
Если будете итерироваться и использовать id в векторе/слайсе чаще, процессор хуже будет класть данные в кеши, по возможности, когда это очень важно, делаете два отдельных вектора id и name.
5. Даже какие-то обычные операции в роде сложения матриц нельзя делать как вектор векторов/массив массивов, правильно хранить всё в одном куске памяти и логически разделять строки
6. Если объекты логически большие, структурные как json или protobuf, создавайте арены/memory pool, когда вы кладёте много объектов на один и тот же кусок памяти. Самый простой пример -- вектор строк, если строки разбросаны в памяти, то даже банальные операции типа сортировки будут в разы медленнее не потому, что строки надо больше сравнивать, а потому, что всегда есть плата пойти в память. Поэтому строки со Small String Optimization и пишут в библиотеках, плюс они выигрывают на скейле.
7. Если вы можете утилизировать память, делать более предсказуемой доступы, то вы будете выигрывать у других приложений. Пример -- ClickHouse хорошо понял историю поколоночного формата, потому что памяти так удобнее: утилизация всего сервера в итоге растёт. Библиотеки вроде ZSTD просто напичканы software prefetches, а процессоры Intel/AMD/ARM делают отдельные инструкции для копирования памяти произвольного размера.
8. Обрабатывайте меньше данных в памяти. Сжатие как минимум, как максимум -- слежка сколько вы тратите на пользователя/entity данных. Я находил на своём опыте какие-то огромные пробелы в том, зачем мы храним столько данных. Хоть и бизнесы скейлятся, как правило начинается бардак в схемах/логах. Детектить такие вещи тяжело. SQL со своими селективными предикатами здесь побеждает обычные языки программирования и MapReduce, в последнем надо писать код -- ставить трекеры на форматы в компилируемых языках тяжело.
Развитие SIMD, больше правильных структурированных форматов, подстройка парсеров под данные, самокорректирующиеся под data оптимизации вроде JIT будут доминировать в ближайшее время развитие data proc. Истории с прорывами происходят вроде SIMDJSON и тд, но никакого систематичного решения пока не видно, эта область имеет шансы сильно развиться или умереть, принимая, что это в какой-то степени предел и надо думать в других направлениях типа GPU/TPU/Quantum/FPGA/etc.
В Google мы репортим среднюю утилизацию сервера в 60% и проблемы с памятью одни из самых противных -- данных просто тьма, решения вроде использовать flat_hash_map, а не unordered_map помогают лишь держать это число на плаву. Тот, кто поймёт эту историю лучше всего, будет платить за датацентры меньше всего денег.
В эпоху рецессии кажется это может быть ещё более важно. Постараюсь сделать серию из постов про то, как увеличивать полезность при помощи уменьшения процессинга памяти. Тут много нетривиальных компромиссов.