Концептуальная проблема интерпретатора C ++

Question

Я создал интерпретатор в C ++ для созданного мной языка.

Одной из основных проблем в дизайне было то, что у меня было два разных типа в языке: число и строка. Поэтому я должен обойти структуру вроде:

class myInterpreterValue
{
 myInterpreterType type;
 int intValue;
 string strValue;
}

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

Профилирование указано: 85% производительности съедается функцией выделения шаблона строки.

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

Как что-то сделать против этого? Является ли такой класс лучшей идеей?

vector<string> strTable;
vector<int> intTable;
class myInterpreterValue
{
 myInterpreterType type;
 int locationInTable;
}

Таким образом, класс знает только, какой тип он представляет, и позицию в таблице

Это, однако, опять же имеет недостатки: Мне бы пришлось добавить временные значения в таблицу векторов string / int, а затем удалить их снова, это опять бы снизило производительность.

• Помогите, как это делают интерпретаторы таких языков, как Python или Ruby? Им как-то нужна структура, которая представляет значение в языке, например, что-то типа int или string.

Answer 1

Я подозреваю, что многие значения не являются строками. Поэтому первое, что вы можете сделать, это избавиться от объекта string, если он вам не нужен. Поместите это в союз. Другое дело, что, вероятно, многие из ваших строк очень малы, поэтому вы можете избавиться от выделения кучи, если сохраните небольшие строки в самом объекте. Для этого у LLVM есть шаблон SmallString. И тогда вы можете использовать интернирование строк, как говорит другой ответ. Для этого LLVM имеет класс StringPool: вызовите intern("foo") и получите умный указатель, ссылающийся на общую строку, потенциально используемую другими объектами myInterpreterValue

Союз можно записать так

class myInterpreterValue {
 boost::variant<int, string> value;
};

boost::variant делает маркировку типов за вас. Вы можете реализовать это так, если у вас нет поддержки. Выравнивание не может быть получено переносимым в C ++, поэтому мы добавляем некоторые типы, которые, возможно, требуют большого выравнивания в объединение хранилища.

class myInterpreterValue {
 union Storage {
   // for getting alignment
   long double ld_;
   long long ll_;

   // for getting size
   int i1;
   char s1[sizeof(string)];

   // for access
   char c;
 };
 enum type { IntValue, StringValue } m_type;

 Storage m_store;
 int *getIntP() { return reinterpret_cast<int*>(&m_store.c); }
 string *getStringP() { return reinterpret_cast<string*>(&m_store.c); }


public:
  myInterpreterValue(string const& str) {
    m_type = StringValue;
    new (static_cast<void*>(&m_store.c)) string(str);
  }

  myInterpreterValue(int i) {
    m_type = IntValue;
    new (static_cast<void*>(&m_store.c)) int(i);
  }
  ~myInterpreterValue() {
    if(m_type == StringValue) {
      getStringP()->~string(); // call destructor
    }
  }
  string &asString() { return *getStringP(); }
  int &asInt() { return *getIntP(); }
};

Вы поняли идею.

Answer 2

И в Python, и в Ruby целые числа являются объектами. Так что вопрос не в том, что «значение» является целым числом или строкой, это может быть что угодно. Кроме того, все на обоих этих языках является сборщиком мусора. Нет необходимости в копировании объектов, указатели могут использоваться внутри, если они безопасно хранятся где-то, где сборщик мусора их увидит.

Итак, одним из решений вашей проблемы будет:

class myInterpreterValue {
    virtual ~myInterpreterValue() {}
    // example of a possible member function
    virtual string toString() const = 0;
};

class myInterpreterStringValue : public myInterpreterValue {
    string value;
    virtual string toString() const { return value; }
};

class myInterpreterIntValue : public myInterpreterValue {
    int value;
    virtual string toString() const {
        char buf[12]; // yeah, int might be more than 32 bits. Whatever.
        sprintf(buf, "%d", value);
        return buf;
    }
};

Затем используйте виртуальные вызовы и dynamic_cast для включения или проверки типов вместо сравнения со значениями myInterpreterType.

Обычно в этот момент нужно беспокоиться о том, что вызовы виртуальных функций и динамическое приведение могут быть медленными. Как в Ruby, так и в Python повсеместно используются вызовы виртуальных функций. Хотя это и не виртуальные вызовы C ++: для обоих языков их «стандартная» реализация на C с пользовательскими механизмами полиморфизма. Но в принципе нет оснований предполагать, что «виртуальный» означает «производительность из окна».

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

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

Answer 3

Я думаю, что некоторые динамические языки кэшируют все эквивалентные строки во время выполнения с поиском хеша и хранят только указатели. Следовательно, в каждой итерации цикла, где строка остается неизменной, будет только указатель или самое большее функция хеширования строки. Я знаю, что некоторые языки (Smalltalk, я думаю?) Делают это не только со строками, но и с небольшими числами. См. Шаблон для навеса .

IANAE на этом. Если это не поможет, вы должны дать код цикла и рассказать нам, как он интерпретируется.

Answer 4

Самый простой способ решить эту проблему - создать указатель на строку и выделить его только при создании строкового значения. Вы также можете использовать объединение для экономии памяти.

class myInterpreterValue
{
 myInterpreterType type;
 union {
  int asInt;
  string* asString;
 } value;
}