WordNet-blast. Con boost::add_edge hemos topado.

Posted on Thu 20 August 2015 in C++

WordNet-blast es una biblioteca de C++ creada por Ugo Jardonnet para construir en memoria el gráfico de WordNet y permitir un acceso rápido a los synsets y sus relaciones.

Encontré esta librería buscando recursos lingüísticos para mi tesis de fin de máster, en ella necesitaba cálcular la distancia semántica entre conceptos y para ello utilizaba el grafo de WordNet, así que esta librería, que utiliza la Boost Graph Library (BGL), resultaba perfecta para lo que quería hacer.

NOTA.- En todo lo que se sigue hay que tener en cuenta que las pruebas se han realizado con Microsoft Visual Studio Premium 2013. Version 12.0.40418.00 Update 5 RC.

Sin embargo, había un problema: el tiempo empleado en la construcción del grafo en memoria era excesivo cuando se ejecutaba en debug (hablo de minutos) lo que complicaba las tareas de depuración. Así que aprovechando unos días de relax me he dedicado a darle un lavado de cara a la librería y a tratar de acelerar la construcción del grafo en mi repositorio.

Sin embargo, no he sido capaz (aún). Me he encontrado con un caballo de batalla contra el que no quiero pelear: la función _Orphan_me, que, tal y como se ve en la imagen siguiente, supone más del 90% del tiempo de ejecución de la aplicación:

Profiling WordNet-blast

Esta función es llamada desde boost::add_edge cuando se crea un nuevo arco en el grafo. es decir, cada vez que añadimos una nueva relación al grafo de WordNet que estamos construyendo en memoria:

boost::add_edge

Si buscamos el código de la función podemos ver que sólo se ejecuta en caso de que la macro de preprocesador _ITERATOR_DEBUG_LEVEL valga 2. Es decir, que sólo tenemos que preocuparnos si estamos compilando con Microsoft y en debug (salvo que establezcamos este valor nosotros mismos) (NOTA Esta macro se añade en Microsoft Visual Studio 2010).

    void _Orphan_me()
        {   // cut ties with parent
 #if _ITERATOR_DEBUG_LEVEL == 2
        if (_Myproxy != 0)
            {   // adopted, remove self from list
            _Iterator_base12 **_Pnext = &_Myproxy->_Myfirstiter;
            while (*_Pnext != 0 && *_Pnext != this)
                _Pnext = &(*_Pnext)->_Mynextiter;

            if (*_Pnext == 0)
                _DEBUG_ERROR("ITERATOR LIST CORRUPTED!");
            *_Pnext = _Mynextiter;
            _Myproxy = 0;
            }
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
        }

Para más información sobre _ITERATOR_DEBUG_LEVEL puedes consultar esta documentación de Microsoft, o este vídeo de Stephan T. Lavavej:

Workaround

Entonces, ¿qué podemos hacer? Básicamente eliminar todas las comprobaciones que se realizan por defecto en debug (_ITERATOR_DEBUG_LEVEL == 2) y cambiar el valor de esta macro. Debemos tener en cuenta que al eliminar todas estas comprobaciones, en caso de error en el código, tendremos un comportamiento indeterminado en vez de la amigable alerta Debug Assertion que nos indica que algo ha ido mal y nos permite ir al punto del código donde ha sucedido.

Como siempre, hay solución/workaround, pero hay que tener muy presente cuáles son las consecuencias (side effects).

Seguimos trabajando en ello.