C++ intérprete problema conceptual

Question

He creado un intérprete en C++ para un idioma creado por mí.

Un problema principal en el diseño fue que tenía dos tipos diferentes en el lenguaje: número y cadena. Así que tengo que pasar alrededor de una estructura como:

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

objetos de esta clase se pasan alrededor de un millón de veces por segundo durante ej .: un bucle de cuenta atrás en mi idioma.

Perfil señalado: el 85% del rendimiento lo consume la función de asignación de la plantilla de cadena.

Esto es bastante claro para mí: mi intérprete tiene un diseño incorrecto y no utiliza punteros suficientes. Sin embargo, no tengo una opción: no puedo usar punteros en la mayoría de los casos ya que solo tengo que hacer copias.

¿Cómo hacer algo para evitar esto? ¿Es una clase como esta una mejor idea?

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

Así que la clase sólo sabe de qué tipo representa y la posición en la tabla

Sin embargo, esto tiene más desventajas: tendría que agregar valores temporales a la tabla de cadenas int/vector y luego eliminarlos de nuevo, esto comería mucho rendimiento nuevamente.

• Ayuda, ¿cómo lo hacen los intérpretes de idiomas como Python o Ruby? De alguna manera necesitan una estructura que represente un valor en el lenguaje como algo que puede ser int o string.

Answer 1

Sospecho que muchos valores no son cadenas. Entonces, lo primero que puede hacer es deshacerse del objeto string si no lo necesita. Ponlo en una unión. Otra cosa es que probablemente muchas de sus cadenas sean pequeñas, por lo que puede deshacerse de la asignación de montón si guarda cadenas pequeñas en el objeto mismo. LLVM tiene la plantilla SmallString para eso. Y luego puedes usar el interinato de cuerdas, como también dice otra respuesta. LLVM tiene la clase StringPool para eso: llame al intern("foo") y obtenga un puntero inteligente que haga referencia a una cadena compartida potencialmente utilizada también por otros objetos myInterpreterValue.

La unión se puede escribir como esto

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

boost::variant hace el etiquetado tipo para usted. Puede implementarlo así, si no tiene impulso. La alineación no se puede obtener de forma portátil en C++ todavía, por lo que empujamos algunos tipos que posiblemente requieren una gran alineación en la unión de almacenamiento.

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(); } 
}; 

Ya sacó la idea.

Answer 2

Creo que algunos lenguajes dinámicos almacenan en caché todas las cadenas equivalentes en tiempo de ejecución con una búsqueda hash y solo almacenan punteros. En cada iteración del bucle donde la cadena se mantiene igual, por lo tanto, solo habría una asignación de puntero o como máximo una función de hashing de cadena. Sé que algunos idiomas (Smalltalk, ¿lo creo?) Hacen esto no solo con cadenas sino con números pequeños. Ver Flyweight Pattern.

IANAE en este caso. Si eso no ayuda, debe dar el código de bucle y explicarnos cómo se lo interpreta.

Answer 3

La forma más fácil de resolver eso sería convertirlo en un puntero a la cadena, y solo asignarlo cuando se crea el valor de la cadena. También puede usar la unión para guardar en la memoria.

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

Answer 4

Tanto en Python como en Ruby, los enteros son objetos. Entonces no se trata de que un "valor" sea un número entero o una cadena, puede ser cualquier cosa. Además, todo en ambos idiomas es basura. No es necesario copiar objetos, los punteros se pueden usar internamente siempre que estén almacenados de forma segura en algún lugar donde el recolector de basura los pueda ver.

lo tanto, una solución a su problema sería:

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; 
    } 
}; 

A continuación, utilice las llamadas virtuales y dynamic_cast para activar o comprobar los tipos, en lugar de comparar con los valores de myInterpreterType.

Lo habitual a hacer en este momento es la preocupación de que las llamadas a funciones virtuales y el lanzamiento dinámico sean lentas. Tanto Ruby como Python usan llamadas a funciones virtuales por todos lados. Aunque no llamadas virtuales en C++: para ambos lenguajes su implementación "estándar" está en C con mecanismos personalizados para el polimorfismo. Pero no hay ninguna razón en principio para suponer que "virtual" significa "rendimiento fuera de la ventana".

Dicho esto, espero que ambos tengan algunas optimizaciones inteligentes para ciertos usos de enteros, incluso como contadores de bucle. Pero si actualmente observa que la mayor parte de su tiempo lo dedica a copiar cadenas vacías, las llamadas a funciones virtuales, en comparación, son casi instantáneas.

La verdadera preocupación es cómo va a administrar los recursos: dependiendo de cuáles sean sus planes para su lenguaje interpretado, la recolección de basura puede ser más problemática de lo que usted desea.