Привет, Хабр!

Сегодня мы публикуем перевод интересного исследования о работе с памятью и указателями в C++. Материал немного академический, но явно будет небезынтересен читателям книг Галовица и Уильямса.

Следите за рекламой!

В аспирантуре я занимаюсь построением распределенных структур данных. Поэтому абстракция, представляющая удаленный указатель, исключительно важна в моей работе для создания чистого и аккуратного кода. В этой статье я расскажу, почему необходимы умные указатели, расскажу, как написал на C++ объекты удаленных указателей для моей библиотеки, добился, чтобы они работали точно как обычные указатели С++; это делается при помощи объектов удаленных ссылок. Далее я поясню, в каких случаях эта абстракция отказывает по той простой причине, что мой собственный указатель (пока) не справляется с теми задачами, которые под силу обычным указателям. Надеюсь, что статья заинтересует читателей, занимающихся разработкой высокоуровневых абстракций.

Низкоуровневые API

Работая с распределенными компьютерами или с сетевым аппаратным обеспечением, вы часто располагаете доступом на чтение и запись к некоторому участку памяти, через API на C. Один из примеров такого рода — API MPI для односторонней коммуникации. В этом API используются функции, открывающие прямой доступ на чтение и запись из памяти других узлов, находящихся в распределенном кластере. Вот как это выглядит в слегка упрощенном виде.

void  remote_read(void* dst, int target_node, int offset, int size);
void remote_write(void* src, int target_node, int offset, int size);

При указанном смещении в сегмент разделяемой памяти целевого узла, remote_read считает из него некоторое количество байт, а remote_write запишет некоторое количество байт.

Эти API великолепны, так как открывают нам доступ к важным примитивам, которые пригодятся нам для реализации программ, выполняемых на кластере компьютеров. Еще они очень хороши потому, что работают действительно быстро и в точности отражают возможности, предлагаемые на аппаратном уровне: удаленный прямой доступ к памяти (RDMA). Современные суперкомпьютерные сети, такие как Cray Aries и Mellanox EDR, позволяют рассчитывать, что задержка при чтении/записи не превысит 1-2 ?s. Такого показателя удается добиться благодаря тому, что сетевая карта (NIC) может читать и записывать непосредственно в RAM, не дожидаясь, пока удаленный CPU проснется и отреагирует на ваш сетевой запрос.

Однако, такие API не столь хороши с точки зрения программирования приложений. Даже в случае с такими простыми API, как описанный выше, ничего не стоит нечаянно затереть данные, поскольку не предусмотрено отдельное имя для каждого конкретного объекта, хранимого в памяти, только один большой непрерывный буфер. Кроме того, интерфейс нетипизированный, то есть, вы лишены и еще одного ощутимого подспорья: когда компилятор ругается, если вы запишете в неподходящее место значение неподходящего типа. Ваш код просто получится неправильным, и ошибки будут иметь самый таинственный и катастрофический характер. Ситуация тем более осложняется потому, что в реальности эти API еще немного сложнее, и при работе с ними вполне можно по ошибке переставить местами два или более параметров.

Удаленные указатели

Указатели – это важный и необходимый уровень абстрагирования, нужный при создании высокоуровневых инструментов программирования. Использовать указатели напрямую порой бывает сложно, при этом можно наделать много багов, но указатели – это фундаментальные кирпичики кода. Структуры данных и даже ссылки C++ часто используют под капотом указатели.

Если предположить, что у нас будет API, подобный описанным выше, то уникальное местоположение в памяти будет указываться двумя «координатами»: (1) ранг или ID процесса и (2) смещение, сделанное в разделяемый участок удаленной памяти, занятый процессом с этим рангом. Можно на этом не останавливаться и сделать полноценную структуру.

 template <typename T>
    struct remote_ptr {
      size_t rank_;
      size_t offset_;
    };

На данном этапе уже можно спроектировать API для считывания и записи в удаленные указатели, и этот API будет более безопасным, чем тот, которым мы исходно пользовались.

 template <typename T>
    T rget(const remote_ptr<T> src) {
      T rv;
      remote_read(&rv, src.rank_, src.offset_, sizeof(T));
      return rv;
    }

    template <typename T>
    void rput(remote_ptr<T> dst, const T& src) {
      remote_write(&src, dst.rank_, dst.offset_, sizeof(T));
    }

Блоковые передачи выглядят очень похоже, и здесь я опускаю их для краткости. Теперь, для считывания и записи значения можно написать такой код:

 remote_ptr<int> ptr = ...;
   int rval = rget(ptr);
   rval++;
   rput(ptr, rval);

Он уже лучше исходного API, так как здесь мы работаем с типизированными объектами. Теперь не так просто записать или считать значение неподходящего типа или записать лишь часть объекта.

Арифметика указателей

Арифметика указателей – важнейшая методика, позволяющая программисту управлять коллекциями значений в памяти; если же мы пишем программу для распределенной работы в памяти, предположительно, мы собираемся оперировать большими коллекциями значений.
Что означает увеличение или уменьшение удаленного указателя на единицу? Простейший вариант – считать арифметику удаленных указателей аналогичной арифметике обычных указателей: p+1 просто укажет на следующий sizeof(T)-выровненный участок памяти после p в разделяемом сегменте исходного ранга.

Хотя, это и не единственное возможное определение арифметики удаленных указателей, именно оно в последнее время наиболее активно берется на вооружение, а используемые таким образом удаленные указатели содержатся в таких библиотеках как UPC++, DASH и BCL. Однако, язык Унифицированный параллельный C (UPC), оставивший богатое наследие в сообществе специалистов по высокопроизводительным вычислениям (HPC), содержит более тщательно проработанную дефиницию арифметики указателей [1].

Реализовать арифметику указателей таким образом просто, и она связана лишь с изменением смещения указателя.

 template <typename T>
   remote_ptr<T> remote_ptr<T>::operator+(std::ptrdiff_t diff)
   {
     size_t new_offset = offset_ + sizeof(T)*diff;
     return remote_ptr<T>{rank_, new_offset};
   }

В данном случае перед нами открывается возможность обращаться к массивам данных в распределенной памяти. Так, мы могли бы добиться, чтобы каждый процесс в программе SPMD производил бы операцию записи или считывания над своей переменной в массиве, на который направлен удаленный указатель [2].

void write_array(remote_ptr<int> ptr, size_t len) {
     if (my_rank() < len) {
       rput(ptr + my_rank(), my_rank());
     }
   }

Также несложно реализовать и другие операторы, обеспечив поддержку полного набора арифметических операций, выполняемых в обычной арифметике указателей.

Выбираем значение nullptr

У обычных указателей значение nullptr равно NULL, что обычно означает сведение #define к 0x0, поскольку этот участок в памяти вряд ли будет использоваться. В нашей схеме с удаленными указателями мы можем либо выбрать конкретное значение указателя в качестве nullptr, сделав таким образом данное местоположение в памяти неиспользуемым, либо включить специальный булев член, который будет свидетельствовать, является ли указатель нулевым. Притом, что делать некое местоположение в памяти неиспользуемым – не лучший выход, также учтем, что при добавлении всего одного булева значения размер удаленного указателя с точки зрения большинства компиляторов удвоится и вырастет со 128 до 256 бит, чтобы соблюсти выравнивание. Это особенно нежелательно. В моей библиотеке я выбрал {0, 0}, то есть, смещение 0 с рангом 0, в качестве значения nullptr.

Возможно, удастся подобрать и другие варианты nullptr, которые будут работать не хуже. Кроме того, в некоторых окружениях для программирования, например, в UPC, реализованы узкие указатели, умещающиеся в 64 бит каждый. Таким образом, они могут использоваться при атомарных операциях сравнения с обменом. При работе с узким указателем приходится идти на компромисс: или идентификатор смещения, или идентификатор ранга должен умещаться в 32 бит или менее, а это ограничивает масштабируемость.

Удаленные ссылки

В таких языках как Python, bracket-оператор служит в качестве синтаксического сахара для вызова методов __setitem__ и __getitem__, в зависимости от того, считываете ли вы объект или записываете в него. В C++, operator[] не различает, к какой из категорий значений принадлежит объект, и будет ли возвращенное значение сразу же подпадать под считывание или под запись. Для решения этой проблемы структуры данных C++ возвращают ссылки, указывающие на содержащуюся в контейнере память, которая поддается записи или считыванию. Реализация operator[] для std::vector может выглядеть примерно так.

 T& operator[](size_t idx) {
     return data_[idx];
   }

Здесь наиболее существенен факт, что мы возвращаем сущность типа T&, представляющую собой сырую ссылку C++, по которой можно записывать, а не сущность типа T, которая всего лишь представляет значение исходных данных.

В нашем случае мы не можем возвращать сырую ссылку C++, так как ссылаемся на память, расположенную на другом узле и не представленную в нашем виртуальном адресном пространстве. Правда, мы можем создавать наши собственные кастомные ссылочные объекты.
Ссылка представляет собой объект, служащий оберткой вокруг указателя, и она выполняет две важнейшие функции: ее можно преобразовать в значение типа T, а также можно присвоить значению типа T. Так, в случае удаленной ссылки нам всего лишь потребуется реализовать оператор неявного преобразования, считывающий значение, а также сделать оператор присваивания, записывающий в значение.

template <typename T>
  struct remote_ref {
    remote_ptr<T> ptr_;

    operator T() const {
      return rget(ptr_);
    }

    remote_ref& operator=(const T& value) {
      rput(ptr_, value);
      return *this;
    }
  };

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

template <typename T>
  remote_ref<T> remote_ptr<T>::operator*() {
    return remote_ref<T>{*this};
  }

  template <typename T>
  remote_ref<T> remote_ptr<T>::operator[](ptrdiff_t idx) {
    return remote_ref<T>{*this + idx};
  }

Итак, теперь мы восстановили всю картину, показывающую, каким образом можно использовать удаленные указатели как обычные. Можем переписать простую программу, приведенную выше.

void write_array(remote_ptr<int> ptr, size_t len) {
     if (my_rank() < len) {
       ptr[my_rank()] = my_rank();
     }
   }

Разумеется, наш новый API указателей позволяет написать и более сложные программы, например, функцию для выполнения параллельной редукции на основе дерева [3]. Реализации, использующие наш класс удаленного указателя, безопаснее и чище тех, что обычно получаются при использовании C API, описанного выше.

Издержки, возникающие во время выполнения (или их отсутствие!)

Однако, чего нам будет стоить использование такой высокоуровневой абстракции? При каждом обращении к памяти мы вызываем метод разыменования, возвращаем промежуточный объект, обертывающий указатель, затем вызываем оператор преобразования или оператор присваивания, воздействующий на промежуточный объект. Во что это нам обойдется во время выполнения?

Оказывается, что, если аккуратно спроектировать классы указателя и ссылок, то никаких издержек за эту абстракцию во время выполнения не будет – современные компиляторы C++ справляются с этими промежуточными объектами и вызовами методов путем агрессивного встраивания. Чтобы оценить, чего нам будет стоить такая абстракция, можно скомпилировать простую программу-пример и проверить, как пойдет сборка, чтобы посмотреть, какие объекты и методы будут существовать во время выполнения. В описанном здесь примере с редукцией на основе дерева, скомпилированном с классами удаленных указателей и ссылок, современные компиляторы сводят редукцию на основе дерева к нескольким вызовам remote_read и remote_write [4]. Никакие методы классов не вызываются, никаких ссылочных объектов во время выполнения не существует.

Взаимодействие с библиотеками структур данных

Опытные программисты, работающие с C++, помнят, что в стандартной библиотеке шаблонов C++ указано: STL-контейнеры должны поддерживать кастомные аллокаторы C++. Аллокаторы позволяют выделять память, а затем на эту память можно ссылаться с использованием типов указателей, сделанных нами. Означает ли это, что можно просто создать «удаленный аллокатор» и подключить его для хранения данных в удаленной памяти с использованием STL-контейнеров?

К сожалению, нет. Предположительно, из соображений производительности стандарт C++ больше не требует поддержки кастомных ссылочных типов, и в большинстве реализаций стандартной библиотеки C++ они действительно не поддерживаются. Так, например, если вы используете libstdc++ из GCC, то можете прибегать к кастомным указателям, но при этом вам доступны лишь обычные ссылки C++, что не позволяет вам использовать STL-контейнеры в удаленной памяти. Некоторые высокоуровневые библиотеки шаблонов C++, например, Agency, использующие кастомные типы указателей и ссылочные типы, содержат собственные реализации некоторых структур данных из STL, которые действительно позволяют работать с удаленными ссылочными типами. В данном случае программист получает большую свободу в креативном подходе к созданию типов аллокаторов, указателей и ссылок, а, кроме того, получает коллекцию структур данных, которые автоматически можно использовать с ними.

Широкий контекст

В этой статье мы затронули ряд более широких и пока не решенных проблем.

• Выделение памяти. Теперь, имея возможность ссылаться на объекты в удаленной памяти, как же нам зарезервировать или выделить такую удаленную память?
• Поддержка объектов. Как быть с хранением в удаленной памяти таких объектов, которые относятся к типам посложнее int? Возможна ли аккуратная поддержка сложных типов? Можно ли в то же время поддерживать простые типы, не затрачивая ресурсов на сериализацию?
• Проектирование распределенных структур данных. Теперь, имея эти абстракции, какие структуры данных и приложения можно построить с их помощью? Какие абстракции следует использовать для распределения данных?

Примечания

[1] В UPC у указателей есть фаза, определяющая, на какой ранг будет направлен указатель после увеличения на единицу. Благодаря фазам, в указателях можно инкапсулировать распределенные массивы, причем, паттерны распределения в них могут быть самыми разными. Эти возможности очень мощные, но пользователю-новичку могут показаться магическими. Хотя, некоторые асы UPC действительно предпочитают такой подход, более разумный объектно-ориентированный подход заключается в том, чтобы сначала написать простой класс удаленного указателя, а затем обеспечивать распределение данных, полагаясь на специально предназначенные для этого структуры данных.

[2] Большинство приложений в HPC пишутся в стиле SPMD, это название означает «одна программа, разные данные». В API SPMD предлагается функция или переменная my_rank(), сообщающая процессу, выполняющему программу, уникальный ранг или ID, на основании которых затем можно выполнить ветвление от основной программы.

[3] Вот простейшая редукция дерева, написанная в стиле SPMD с использованием класса удаленных указателей. Код адаптирован на основе программы, исходно написанной моим коллегой Эндрю Белтом.

 template <typename T>
   T parallel_sum(remote_ptr<T> a, size_t len) {
     size_t k = len;

     do {
       k = (k + 1) / 2;

       if (my_rank() < k && my_rank() + k < len) {
         a[my_rank()] += a[my_rank() + k];
       }

       len = k;
       barrier();
    } while (k > 1);

    return a[0];
  }

[4] Скомпилированный результат вышеприведенного кода можно посмотреть здесь.