[UACA]
[<==] [\/] [/\] [==>]


Reutilización de Contenedores Parametrizables con Lenguajes de Semántica Limitada


Capítulo 8: Análisis de resultados

       La Reutilización en computación es un concepto que ha cambiado conforme pasa el tiempo. Al principio consistió simplemente en la facilidad sintáctica que le pemitiera al programador usar subrutinas. Hoy en día reconocemos que una pieza de programación es reutilizable si puede ser usada en la construcción de un nuevo programa o programa producto. Ya no se habla entonces de rutinas y programas reutilizables, sino más bien de reutilizar Artefactos de programación ("software artifacts" en inglés). Recientemente este significado se ha afinado mucho más, pues ahora ya sabemos cuáles son las cualidades que debe tener una buena técnica de reutilización de artefactos de programación [Kru-92]:
  1. Para que una técnica de reutilización sea efectiva debe reducir la distancia cognoscitiva entre el concepto inicial de un sistema y su implementación ejecutable final.
  2. Para que una técnica de reutilización sea efectiva debe ser más fácil reutilizar los artefactos que desarrollarlos de nuevo desde el principio.
  3. Para seleccionar un artefacto a ser reutilizado, es necesario saber qué es lo que hace.
  4. Para reutilizar un artefacto de programación efectivamente es necesario encontrarlo más rápidamente de lo que se tardaría reconstruyéndolo.

      Es obvio que el grado de reutilización que se logra al usar la técnica expuesta en este trabajo, es de un nivel relativamente bajo, pues sólo sirve para reutilizar estructuras de datos. Esto no es un pecado, como se explica en [US-94] (pg 1), en donde se define el lugar que ocupan en la taxonomía de reutilización de Biggerstaff [Big-84] las bibliotecas de tipos abstractos de datos.

      A la luz de estas definiciones se vislumbran dos maneras interesantes de evaluar las ideas sobre parametrización ya expuestas. La primera es mostrar cuán incómoda resulta la programación al parametrizar usando las técnicas expuestas en este trabajo, y la segunda es analizar la pérdida en eficiencia que comporta usar Binder.pas para implementar contenedores parametrizables. Después de analizar los resultados obtenidos bajo esta óptica, al final del capítulo se dan algunas opiniones moldeadas por los argumentos expuestos.

      Como la cantidad de recurso humano que se necesita es el costo de más alto en que se incurre al crear un sistema, definitivamente es más importante la facilidad de uso de una técnica de reutilización que su eficiente implementación; por eso se hace un análisis de rendimiento después de discutir el costo cognoscitivo de uso de Binder.pas. Prueba de esto es la existencia de lenguajes de programación que usan recolectores de basura, en los que muchas veces no es posible determinar apriori el rendimiento real de un algoritmo (de hecho, Lisp es el lenguaje más viejo que todavía está en uso, y su gran popularidad en parte se debe a que utiliza un recolector de basura que ayuda a que el programador no tenga que invertir esfuerzos en manejar la memoria dinámica [PZ-98]).

      En toda investigación es su autor quien está más calificado para criticar los resultados obtenidos, pues conoce a fondo el trabajo desarrollado. En este capítulo se mencionan primero todos los defectos y limitaciones de Binder.pas, y luego sus virtudes y ventajas. Las críticas que se exponen a continuación son duras y profundas, quizá un poco más de lo necesario, pero buscan identificar todas las limitaciones de la tecnología expuesta, para eliminarlas lo más pronto posible. No es rehuyendo la crítica como se llega a la excelencia.

8.1 Comparación de estilos de codificación [<>] [\/] [/\] [<>]

      Conviene mucho, y así lo exige la costumbre de los investigadores, conocer el trabajo realizado en el pasado para usarlo al desarrollar una investigación. Hay bastantes bibliotecas de contenedores parametrizables, pero las más importantes son las siguientes:

      Los autores de estas bibliotecas han hecho una labor encomiable, pues en muchos casos han invertido cientos y miles de horas en su desarrollo. Han condimentado su diseño con el sabor del lenguaje que en algún momento fue de su preferencia: por ejemplo, Keith Gorlen usó como modelo la biblioteca de Smalltalk para implementar Libg++. Lo mismo hizo Alexander Stepanov, arquitecto de STL, quien antes trabajó mucho en su biblioteca parametrizable para Ada [MS-96]. De hecho, Stepanov logró convencer a Bjarne Stroustrup (creador del lenguaje C++ [Str-86a]) de que modificara el lenguaje para adaptarlo mejor a las necesidades de su biblioteca [Ste-95]. 

TYPE
  TLint = TList < INTEGER >;

VAR
  L : TLint; { TList < INTEGER > }

  { ... }
  L.Append(1);    L.Append(3);
  L.Append(2);    L.Append(4);
Figura 8.1: Estilo usual de uso de la parametrización

      Todas estas bibliotecas son similares en su forma de uso. Para declarar un contenedor, el programador debe instanciar en una variable el tipo del contenedor. Por ejemplo, en la Figura 8.1 aparece la manera de usar una lista de enteros (se ha usado una sintaxis "pascalizada" en el ejemplo). En este caso se ha declarado un nuevo tipo llamado TLint (T+List+integer) mediante el artilugio de definir un nuevo tipo: lista de enteros (este estilo de programación es frecuente en programas C++). El compilador en este caso debe generar el código para la lista, especializando los algoritmos al caso del tipo INTEGER. Este estilo de programación fue introducido en la famosa biblioteca de componentes Booch [Boo-87]. Es un estilo directo y muy intuitivo, pues cuando un programador implementa un contenedor como TLint, lo usual es que le incluya operaciones como Append() e Insert(), en lugar de usar los que se recomiendan en este trabajo: TList.LinkAfter() (ver Figura 7.17). En la Figura 7.3 se muestra el modelo que corresponde a esta manera de implementar contenedores y se contrasta con el de la técnica expuesta en este trabajo, que se muestra en la Figura 7.4.

      Cabe aquí la pregunta: ¿Por qué hay que mantener el estilo de codificación de la Figura 8.1, si se puede lograr que un contenedor sea parametrizable con sólo implementarlo manipulando únicamente campos de enlace, como se muestra en la Figura 7.4? La respuesta a esta interrogante es muy simple: ya existe una costumbre muy arraigada sobre la forma de hacer las cosas, y es muy difícil cambiarla (es más fácil dejar de fumar, o perder peso, que abandonar la sintaxis usada en la Figura 8.1). Por eso todas las bibliotecas de contenedores que se han diseñado tienen en común esta manera de usarlas; es más, difícilmente se les ha ocurrido a esos autores siquiera imaginar usar una sintaxis diferente. Fue necesario implementar el instanciador de plantillas CTPinst porque es muy posible que, si no existiera, muchas personas ni siquiera considerarían usar Binder.pas. 







VAR
  L : TList <INTEGER>; 


  { ... }
  L.Append(1);
  L.Append(2);

TYPE
  Tint = RECORD
    i    : INTEGER;
    link : TLlink;
  END;

VAR
  L   : TList;
  n,m : Tint;

  { ... }
  n.i := 1; L.Append(n.link);
  m.i := 2; L.Append(m.link);
Figura 8.2: Confrontación de estilos de parametrización

      En la Figura 8.2 se confrontan los estilos de parametrización de otras bibliotecas con el de contenedores parametrizados con Binder.pas. Salta a la vista que quienes usan Binder.pas tienen que escribir más código. Como en una lista de tipo TList puede enlazarse cualquier cosa que contenga un campo de tipo TLlink, además de escribir mucho pierden la ventaja de la verificación fuerte de tipos que ofrece el compilador (ver Figura 7.30). 

UNIT Utypes;

TYPE
  Tint = RECORD
    i    : INTEGER;
    link : TLlink;
  END;


USES
  Envelope, Utypes;

VAR
  L   : Envelope.TList_Tint_link;
  n,m : Tint;

  { ... }
  n.i := 1; L.Append(n);
  m.i := 2; L.Append(m);
Figura 8.3: Parametrización con CTPinst

      Si se usa una plantilla de las que CTPinst puede instanciar, el estilo de programación que se puede usar es el que se muestra en la Figura 8.3. La situación ahora no es tan preocupante como antes, pues mediante el tipo TList_Tint_link, definido en la unidad Envelope.pas, que genera CTPinst, ya el programador cuenta con verificación fuerte de tipos. Pero ahora surge otro dilema: además de definir el tipo Tint que sólo contiene un número entero, hay que crear otro módulo aparte, llamado Utypes.pas en este ejemplo, que contiene la definición del tipo Tint. Además, el uso de tipos de interfaz como TList_Tint_link implica que la invocación a cada operación del contenedor es indirecta, lo que disminuye la eficiencia.

      Aparentemente no vale la pena del todo usar Binder.pas: la única ventaja es que todas las instancias de la lista usan el mismo código. Surge entonces la siguiente duda: ¿No sería mejor modificar CTPinst para que en lugar de instanciar contenedores más bien instanciara plantillas como lo hace un compilador de Ada o C++? ¿O tal vez es mejor invertir esfuerzos para implementar un preprocesador para incluirle a Pascal la construcción TYPECAST de la Figura 7.45?

      Estas preguntas no tienen una fácil respuesta, pues parece que todo el esfuerzo invertido en producir Binder.pas se pierde cuando el lenguaje incorpora plantillas en su sintaxis. Pero todavía hay más. 

UNIT List;

TYPE
  Tnode = OBJECT
    link : ^Tnode;
  END;

  TList = OBJECT
    _last : ^Tnode;

   PROCEDURE Append(VAR n: TNode);
  END; { TList }


USES
  List;
TYPE
  Tint = OBJECT(List.Tnode)
    i : INTEGER;
  END;

VAR
  L   : TList;
  n,m : Tint;

  { ... }
  n.i := 1; L.Append(n);
  m.i := 2; L.Append(m);
Figura 8.4: Parametrización por Herencia

      En la Figura 8.4 se muestra cómo es posible simular en parte lo que se hace con Binder.pas. La idea es que los elementos que están almacenados en una lista sean extensiones del nodo de la lista, por lo que contienen el campo de enlace de la lista. Como ocurre con el ejemplo de la Figura 8.2, en este caso se pierde la verificación fuerte de tipos del compilador y, además, un mismo elemento no puede estar enlazado en más de un contenedor (si el lenguaje soporta la herencia múltiple entonces el mismo elemento no puede estar enlazado en dos instancias del mismo tipo del contenedor, aunque sí puede estar en dos o más contenedores de diferente tipo).

      La parametrización por herencia fue propuesta hace bastante tiempo por los pioneros de la programación por objetos, en el lenguaje SIMULA [DMN-70]. Luego esta técnica de parametrización ha sido usada por Bertrand Meyer [Mey-86], padre del lenguaje Eiffel, [Mey-88], y por los adeptos al lenguaje Oberon-2 [Mös-94], para implementar bibliotecas de contenedores parametrizables como se muestra en la Figura 8.4. Incluir de forma explícita en un registro el campo de enlace es precisamente la técnica para parametrizar de Binder.pas, aunque también se puede lograr ese efecto usando herencia. Sin embargo, la parametrización de contenedores por herencia usada en Oberon-2 tiene las siguientes limitaciones:

      No hay más incomodidades producidas por el uso de Binder.pas, aunque en realidad la mayor parte de los inconvenientes mencionados son producto de la formación común a todos los científicos de la computación, que aprenden que la forma correcta de percibir una estructura de datos es aquella en la que no están separados los campos de enlace del contenedor del elemento contenido. Si esta barrera mental se elimina, entonces el estilo de codificación que requieren los contenedores parametrizados con Binder.pas no es muy distinto al tradicional.

      Sólo es el programador del contenedor quien debe seguir cierto protocolo relativamente estricto para implementar su ADT, pues el programador cliente del contenedor no necesita conocer esos detalles: le basta incluir en los objetos que desea almacenar en el contenedor el campo de ligamen, y de ahí en adelante el código es similar al que el programador escribiría si no usa el contenedor parametrizable. La barrera mental en contra de Binder.pas se parece mucho a la que al principio existió contra la programación por objetos. De hecho, una tabla de métodos virtuales no es más que un vector de punteros a funciones.

      Desde el principio Ada contó con paquetes genéricos, y a partir del año 1990 lo mismo ocurrió con C++, por lo que la comunidad académica quedó satisfecha con las implementaciones de contenedores parametrizables que recurren a la especialización de plantillas, y dejó de estudiar los ADT's para dedicarse a solucionar otros problemas. El problema que representa no compartir el código de los contenedores, que agranda los programas, simplemente dejó de existir, pues las máquinas progresivamente han aumentado exponencialmente su capacidad de proceso y de memoria. La computadoras personales de los noventas son mucho más potentes que las computadores que ayudaron a posar al primer hombre en la Luna a fines de los sesentas. Por eso, aunque ya todos los ingredientes para hacer la "salsa Binder.pas" existían hace mucho tiempo, nadie se había molestado en hacer la receta.

      A la luz de los argumentos esgrimidos en estos últimos párrafos, examine el lector de nuevo el ejemplo de la Figura 8.2, y el de Figura 8.3: no hay gran diferencia en los estilos de codificación, pero los contenedores que han sido parametrizados con Binder.pas no tienen el problema de las otras bibliotecas, en donde cada instanciación genera una versión diferente del módulo parametrizado, y en las que no es posible usar una sola versión del código objeto, que pueda ser distribuida sin entregar los fuentes de los programas. La especialización de las plantillas contribuye a que el tamaño de los programas crezca y crezca.

      ¿Es necesario reducir el tamaño de los programas? Las empresas productoras de programas han respondido negativamente a esta pregunta, pues, conforme pasa el tiempo, producen programas cada vez más grandes. Por ejemplo, la primera versión del procesador de palabras Word de MicroSoft era muy pequeña, hasta el punto de que se distribuía en un disquete de 800 kilobytes. Las versiones más modernas de este mismo programa ocupan cientos de megabytes, aunque la funcionalidad agregada no es cien veces mayor. Aunque los computadores tenga 32, 64, 128 o un millón de megabytes de memoria, ciertamente llegará el momento en que sea necesario reducir de nuevo el tamaño de los programas. Cuando llegue ese momento, tecnologías similares a Binder.pas serán parte de la respuesta.

      En el Capítulo 7 de [LG-86] se describe extensamente otro método para implementar ADT's en Pascal que requiere, al igual que los tipos opacos de Modula-2, definir un puntero para cada instancia del ADT. Lo malo de esa propuesta es que está orientada a que todos los objetos manipulados por un programa sean accesados por medio de punteros, o sea, que usa semántica de referencia. Este excesivo uso de punteros resulta en programas innecesariamente ineficientes, que deben pagar un sobretrabajo significativo para cada instancia de un objeto, pues se necesita un puntero que lo referencie; esta técnica tampoco protege la parte interna del ADT. Pero el uso de punteros tiene una ventaja: no es necesario distribuir código fuente que implementa el ADT para que el programador cliente use el contenedor polimórfico, aunque sí se pierde la verificación fuerte de tipos del compilador.

      Los módulos parametrizados con Binder.pas tienden a ser estructuras de datos de bajo nivel. En la biblioteca STL de C++ es posible componer unos módulos con otros. Por ejemplo, los adaptadores para contenedores existen gracias a la armónica y astuta conjunción de las plantillas y la sobrecarga de identificadores. La declaración:
      stack< vector< char *> > S;
declara una variable "S" que es una pila (stack) cuya implementación usa un vector. Con gran facilidad el programador cliente de la biblioteca STL puede cambiar su contenedor:
      stack< list< char *> > S;
Ahora "S" es de nuevo una pila, pero la implementación usa una lista en lugar de un vector. Este tipo de maleabilidad se puede lograr con Binder.pas, pero no cambiando sólo una línea de código.

      Por eso se ha afirmado que STL es el paradigma actual de parametrización. Examinemos el siguiente ejemplo, tomado de [MS-94] (pg 641): 

template <class BinaryFun, class T>
class IndirectBinaryFun {
    BinaryFun b;
public:
    IndirectBinaryFun() {}
    operator()(T* x, T* y) { return b(*x, *y); }
};
Figura 8.5: Maleabilidad de los algoritmos de STL

      Con código como el de la Figura 8.5 es posible transformar un algoritmo genérico para que trabaje con un vector de punteros en lugar de manipular directamente los valores. Esto sirve, en particular, para instanciar algoritmos de ordenamiento como el qsort() para que, al ordenar, intercambie punteros en lugar de mover por todo lado los valores. Este tipo de expresividad sólo se logra con la conjunción de muchas cualidades del lenguaje, ¡y con mucha perspicacia!

8.2 Requerimientos [<>] [\/] [/\] [<>]

      Todo programador espera que, si necesita un nuevo contenedor, lo pueda obtener combinando los anteriores. La esperanza es que muy pronto (en un plazo no mayor de cinco años), la humanidad como un todo cuente con todos los contenedores que se necesitan, a un costo bajo y sin sacrificar eficiencia. En ese momento los contenedores parametrizables dejarán de ser un problema, y se convertirán simplemente en uno de los activos que la humanidad tiene, de la misma forma que hoy en día disfrutamos a un costo mínimo de la aspirina, la rueda o la navegación.

      En última instancia es necesario producir una biblioteca de componentes de programación que sean independientes de la plataforma donde se utilicen. Para mejorar su eficiencia, incluirá herramientas automáticas para lograr la portabilidad de algunas de sus partes, sin desaprovechar las ventajas propias de cada plataforma. Los requerimientos originales de trabajo que se han seguido al producir las primeras implementaciones parametrizables en Pascal de los tres contenedores más importantes, son éstos:

  1. Espacio: La cantidad adicional de espacio que se necesita si se usa un contenedor parametrizable debe ser nula o mínima, y en todo caso O(1) o, cuando más, O(n).

  2. Tiempo: La eficiencia en tiempo de ejecución no debe sacrificarse en el sentido de que el costo de usar un contenedor parametrizable en lugar de uno programado específicamente para la tarea debe ser mínimo y, en todo caso, nunca mayor a O(1).

  3. Compartir código: Es fundamental que todas las instancias de cada contenedor puedan compartir código, independientemente del tipo de datos que contengan, pues los programas son cada vez más complejos y requieren de estructuras de datos cada vez más sofisticadas. De esta manera se aumenta la eficiencia de los programas, y disminuye al mismo tiempo su tamaño.

  4. Soporte a varias plataformas computacionales: Ya no es posible suponer que se usará un solo lenguaje para implementar una aplicación computacional. Por eso es importante que la reutilización no esté circunscrita a un solo lenguaje, o a una única plataforma de cómputo.

  5. Protección del código fuente: Al aumentar el control que tiene el programador sobre los módulos que vende, puede reducir su precio, para que los pueda utilizar un auditorio mucho más amplio. Si el programador puede distribuir artefactos de programación funcionalmente completos sin su código fuente, entonces casi de manera natural se evita duplicar código cuando se instancia un contenedor.

      La puerta que abre la posibilidad de distribuir el código de un contenedor parametrizable también permite luego lograr que la misma implementación pueda utilizarse desde varios lenguajes, pues las interfaces entre lenguajes ya están muy bien definidas. De esta forma un programador podría implementar una biblioteca de contenedores en su lenguaje preferido, Pascal por ejemplo, la que luego podría ser utilizada por los programadores C++ y Ada. Eventualmente sería posible incluir dentro del sistema operativo, como un servicio adicional, una biblioteca de contenedores que pueda ser compartida por todos los programas, lo que ayudará a mejorar la eficiencia de los sistemas de cómputo. Una forma sencilla de lograr este mismo objetivo es distribuir la biblioteca binaria de contenedores como una Bibliotecas de Enlace Dinámico (DLL: Dynamic Link Library), pues todos los sistemas operativos actuales tienen un buen soporte específico para manejar este tipo de bibliotecas de código objeto. Otra alternativa es usar tecnologías como CORBA [Bet-95].

      Si es posible que desde varios lenguajes se pueda accesar la misma implementación de una biblioteca, también es posible que la misma biblioteca se pueda trasladar con relativa facilidad a otras plataformas, simplemente recompilando el código fuente. Por eso es natural incluir soporte para múltiples plataformas en la lista de requerimientos.

      Una biblioteca que cumpla con dichos requerimientos aumentará su capacidad de reutilización. Al permitir ocultar el código fuente de una implementación se logra proteger la inversión intelectual del programador especializado, lo que aumentará la rentabilidad económica de construir componentes de programación. La especialización es muy importante pues es el motor que impulsa tanto al progreso como a la productividad económica; este es el incentivo económico que se necesita para producir bibliotecas de componentes de altísima calidad.

      Las bibliotecas que están disponibles actualmente no cumplen con todos estos requisitos. Por ejemplo, como las bibliotecas STL [STL-95] y Libg++ [Libg++95] están implementadas usando casi únicamente archivos de encabezado o macros del preprocesador de C, no es posible distribuir la biblioteca sin que el cliente final también obtenga el código fuente de todos los algoritmos que se usan en la implementación. Lo mismo ocurre con las bibliotecas para Ada, pues para usar paquetes genéricos también hay que entregar los fuentes de los programas. Como el uso de plantillas y paquetes genéricos requiere que el compilador recompile una gran parte de la biblioteca cada vez que se instancia un contenedor, la velocidad de compilación disminuye, lo que incrementa el costo de producción de una aplicación (por suerte las máquinas actuales son tan potentes que este problema se ha minimizado). Otro problema del uso de plantillas es que para los depuradores simbólicos a veces es difícil seguir el código fuente cuando se ejecuta el programa.

  Espacio Tiempo Compartir Plataforma Fuentes
Booch SI SI NO Ada NO
BIDS SI SI SI C++ NO
Eiffel NO NO SI Eiffel SI
Libg++ SI SI NO C++ NO
LEDA SI SI NO C++ NO
STL SI SI NO C++ NO
Binder SI SI - SI - Todos SI
Figura 8.6: Comparación de Binder.pas con otras bibliotecas

      La Figura 8.6 es una tabla comparativa en que se muestran las principales implementaciones que existen para varios lenguajes y plataformas junto al grado en que cumplen con estos requerimientos. Por ejemplo, la biblioteca de componentes reutilizables de Eiffel es una implementación nueva de la biblioteca Booch, lo que muestra que no es reutilizable, pues un cambio de lenguaje implica el escribir de nuevo todos los algoritmos. Además, como en la implementación se usa semántica de referencia, tampoco es de gran eficiencia. En esta implementación el código fuente sí está protegido, pues para usar la biblioteca de componentes de Eiffel no es necesario tener acceso a los fuentes. La biblioteca PAL para Ada cumple con casi todos los requerimientos, aunque no protege los fuentes.

      En la Figura 8.6 está la comparación de Binder.pas con las demás bibliotecas, en relación con los cinco criterios de diseño expuestos anteriormente. En la tabla se nota que sólo los contenedores parametrizados con Binder.pas cumplen con todos los requerimientos. Binder.pas es especial porque es la única biblioteca en la que siempre se comparte la implementación de los algoritmos, pero sin usar semántica de referencia para lograrlo. Se nota también que, si se logra compartir código, se paga en eficiencia, como es el caso de la biblioteca de Eiffel, pues como todos sus contenedores lo que almacenan son punteros a las instancias, incurren en un costo extra que no hay que pagar si se parametriza con Binder.pas: en este caso, un contenedor de "n" elementos agrega una cantidad O(n) de espacio para el contenedor. Todas las demás, y en particular STL, son muy eficientes, pero no permiten compartir código ni tampoco proteger los fuentes de los programas. A diferencia de los demás, Binder.pas es un enfoque que se puede implementar en varios lenguajes, no en uno solo.

8.3 Limitaciones [<>] [\/] [/\] [<>]

      Una vez definidos estos requerimientos, cabe discutir los problemas que comporta el uso de la tecnología que Binder.pas representa; en los párrafos que siguen se detalla la lista de objeciones.

8.4 Análisis de rendimiento [<>] [\/] [/\] [<>]

      Hubo una época en el desarrollo de la computación en la que el costo más alto de cualquier aplicación era la inversión en equipo. Sin embargo, ahora lo más caro es el personal humano, que cada vez es más especializado. En este contexto cabe preguntarse si la eficiencia de un algoritmo es todavía importante. La respuesta, por supuesto, es obvia: la eficiencia de los algoritmos nunca dejará de ser importante.

      Para lograr que este trabajo esté completo, también se ha examinado el costo de parametrizar contenedores por medio de Binder.pas. Las primeras pruebas se corrieron en un computador con las siguientes características:

      Esas pruebas se corrieron bajo el sistema operativo DOS v6.20 porque es un sistema operativo monousuario, que nunca le quita control al programa que se está ejecutando. Para evitar que pequeñas variaciones de ambiente influyeran en los resultados, cada prueba se corrió miles de veces y, en todos los casos, el computador estuvo dedicado exclusivamente a correr las pruebas, sin interferencia de otros programas. A fin de cuentas se obtuvo un tiempo total de corrida, con base en el cual se han sacado las conclusiones que más adelante se discuten sobre el rendimiento de los algoritmos.

      Al revisar los resultados obtenidos en las primeras pruebas fue obvio que algunas mediciones estaban mal hechas, y que el contexto en que se ejecutaban los programas debía ser muy simple, para evitar cambios en los tiempos de ejecución. Fue necesario diseñar una metodología que permite repetir el experimento. El programa usado para medir los tiempos de ejecución es bndrbnch.pas, que se recompila en cada ocasión invocando el archivo de comandos BENCH.bat. Se continuó usando el sistema operativo DOS, pero se le eliminaron de los archivos CONFIG.sys y AUTOEXEC.bat todos los programas residentes que pudieran interferir con el desempeño de la máquina. En particular, se eliminaron los programas SmartDrive (que acelera el acceso a los discos) y DosKey (que permite editar en la línea de comandos), pues ambos roban ciclos de procesador asincrónicamente. El computador utilizado en esta nueva ronda de pruebas fue el siguiente:

      Al correr estas pruebas surgió otro problema. Como el procesador Pentium es muy rápido, para listas pequeñas el tiempo total de ejecución era cero, pese a que las pruebas se repitieron 2,000 veces para cada lista. Fue necesario repetir de nuevo todo el experimento, pero aumentando a 50,000 veces las repeticiones para listas cortas, de hasta 450 elementos, y hasta 10,000 iteraciones para listas de hasta 900 elementos. Para las listas más grandes, cada ciclo de pruebas se ejecutó, de nuevo, 2,000 veces.

      Es difícil determinar si una forma de programación es mejor que otra porque no se puede predecir en cuál contexto será usada una u otra. Ante esta dificultad, para cuantificar el costo de usar Binder.pas se ha seguido la ruta más simple, usando el contenedor más famoso: la lista. Por eso, lo que se ha cuantificado es el tiempo que se tarda procesando una lista implementada usando el estilo de programación de Binder.pas, para compararlo con lo que se tarda si se usa una lista común, no parametrizable. Para evitar sesgar los resultados, se ha usado un generador de números aleatorios cuya semilla inicial es igual en todos los casos.

      El procesador Pentium tiene acceso de 32 bits a su memoria, pero como el compilador usado fue Turbo Pascal versión 7.0, todos los programas objetos accesan la memoria utilizando instrucciones de 16 bits. Esto presenta un problema, pues el criterio para alinear datos en palabras de 16 bits, que es el que se obtiene con la directiva de compilación {A+} usada en todas las pruebas, no alinea en frontera de palabra de 32 bits, que es lo óptimo para el procesador Pentium, lo que también afecta los tiempos de ejecución. Por eso es posible que al repetir las pruebas en otros ambientes, las estadísticas varíen respecto de las recolectadas en esta plataforma, aunque la relación de eficiencia en cada prueba debe mantenerse constante. Por ejemplo, puede ocurrir que los tiempos de ejecución de la lista de enteros varíen respecto de los de la lista de hileras, pero la razón entre los tiempos de ejecución de un mismo tipo de lista, enteros vs. enteros, no debe variar significativamente.

Figura 8.7: Localización de TElem.link

      En las primeras pruebas de rendimiento, el campo de enlace del contenedor era el primer campo del objeto, como se muestra en la parte izquierda de la Figura 8.7, pero luego fue trasladado después del valor del elemento. Esto se hizo para que al transformar un puntero al campo de enlace, de tipo ^TLlink, en un puntero al elemento, de tipo ^TElem, haya que ajustar el valor del puntero para que apunte al principio del elemento (quitándole la distancia a que se encuentra el campo de enlace del principio del elemento), de manera que esa operación quedara reflejada en los tiempos de ejecución de los programas. En caso contrario, para transformar un puntero al campo de enlace en el puntero al elemento basta usar una transferencia de tipos (typecast), que siempre tiene costo nulo en tiempo de ejecución.

      Se forzó, en algunos casos, que el campo de enlace "link" de la lista quedara desalineado de frontera de palabra. Por eso se corrieron pruebas con dos tipos de listas de hileras, unas que ocupan una cantidad de bytes divisible por cuatro, y otras que siempre dejan desalineado el campo de enlace de la lista. Cuando el valor del nodo de la lista es CHAR, que siempre ocupa un byte de memoria, aun si se usa la directiva de compilación {$A+}, el campo de enlace quedará desalineado, pues queda almacenado un byte después del valor. 

PROCEDURE Copy_LstB(
  {?} VAR L     : TListB;
  {?} VAR Lcp   : TListB;
  {+}     cycles: WORD;      { cuántas veces }
  {+}     seed  : LONGINT;   { # aleatorio }
  {-} VAR lap   : LONGINT    { duración total }
);
{ RESULTADO
  Copia "cycles" veces a lista "L" sobre "Lcp", 
  y calcula el tiempo "lap" que ha transcurrido. }
Figura 8.8: Prueba de la lista TListB

      En la Figura 8.8 está el encabezado del procedimiento Copy_LstB() que se encarga de ejercitar las operaciones de la lista. Las operaciones que se han cuantificado sobre la lista son simples: copiar la lista y eliminarle elementos en orden aleatorio. El tiempo total registrado es el requerido para realizar estas operaciones varias veces, de acuerdo con el valor de la variable "cycles". Los valores de la lista "L", que es copiada sobre "Lcp", son generados usando un generador de números aleatorios, cuya semilla es "seed".

      Hay varias razones por las que conviene usar un procedimiento de copia de listas como Copy_LstB() para medir el rendimiento de los contenedores implementados con el apoyo de Binder.pas:

  1. Las operaciones básicas de la lista son familiares para los estudiosos de la computación, y la complejidad de cada operación es por todos conocida. Con base en ese conocimiento se puede generalizar los resultados que he obtenido para la lista y sacar conclusiones para otros contenedores.
  2. Es fácil reproducir los resultados, pues las operaciones del contenedor lista son simples.
  3. Los programas de prueba son relativamente pequeños.
  4. Se pueden generar corridas de prueba usando un generador de números aleatorios bastante simple. En este caso, se usó el generador Brand.pas basado en el que Borland International incluye con su compilador de C++ v3.1. 

    /* rand.c  Copyright (c) 1987, 1991 by Borland Int. */

#define MULTIPLIER      0x015a4e35L   /* 22,695,477 */
#define INCREMENT       1
static  long     Seed = 1;

void srand(unsigned seed) {
    Seed = seed;
}

int rand(void) {
    Seed = MULTIPLIER * Seed + INCREMENT;
    return((int)(Seed >> 16) & 0x7fff);
}
/* rand.c   End of file */
    Figura 8.9: rand() de Borland C++ v3.1

          El generador de números aleatorios de 16 bits de la Figura 8.9 es simple, y ha sido usado por muchos programadores, pese a que no es lo mejor que existe. Lo que importa es que produce listas cuyos valores no son todos consecutivos. 

VAR
  px: PLlink;
  i,count: WORD;

  rand  : TBRand ;
  chrono: TTimer;
BEGIN { Copy_LstB }
  rand.Init;  rand.Seed(seed);
  chrono.Init;
  FOR i := 1 TO cycles DO BEGIN
    Lcp.Copy(L);
    IF NOT Lcp.Equal(L) THEN BEGIN
      WriteLn('ERROR: Copy_LstB(Lcp <> L)');
    END;

    count := L.Count;
    px := Lcp.LPos(rand.Rand MOD count);
    WHILE NOT Lcp.Empty DO BEGIN
      px := Lcp.LPos(rand.Rand MOD count);
      Lcp.DeleteAfter(px);
      DEC(count);
    END;
    Lcp.Delete_All;
  END;

  lap := chrono.Lap;
  rand.Done; chrono.Done;
END;  { Copy_LstB }
Figura 8.10: Implementación de Copy_LstB()

      La Figura 8.10 es la implementación del procedimiento Copy_LstB(), especificado en la Figura 8.8. Este código es el adecuado para una lista que incluye un puntero al contenedor, de tipo TListB (con B).

      El proceso que se aplica a cada lista es el siguiente: Primero la lista original entra en el argumento "L", y de ahí es copiado a "Lcp". El generador de números aleatorios es la variable "rand", de tipo TBRand, definido en la unidad BRand.pas. Luego se genera un nuevo número aleatorio invocando a rand.Rand() y luego se elimina el elemento de la lista que está en esa posición. Se continúa hasta que ya no queden elementos en la lista. La variable "chrono" sirve para calcular la cantidad de tiempo que ha transcurrido; es de tipo TTimer, definido en la unidad SFCtimer.pas. La cantidad de tiempo transcurrido se mide en las unidades de reloj que el procedimiento Pascal DOS.GetTime() retorna; este es el valor que queda guardado en la variable "lap". 

PROCEDURE Copy_LstK(
  {?} VAR L      : TList;
  {?} VAR Lcp    : TList;
  {+}     cycles : WORD;     { cuántas veces }
  {+}     seed   : LONGINT;  { # aleatorio }
  {-} VAR lap    : LONGINT;  { duración total }
  {+} VAR Element: TBinder   { ligador }
);
VAR
  px   : PLlink;
  i,count: WORD;

  rand  : TBRand ;
  chrono: TTimer;
BEGIN { Copy_LstK }
  rand.Init;  rand.Seed(seed);
  chrono.Init;
  FOR i := 1 TO cycles DO BEGIN
    Lcp.Copy(L, Element);
    IF NOT Lcp.Equal(L, Element) THEN BEGIN
      WriteLn('ERROR: Copy_LstK(Lcp <> L)');
    END;

    count := L.Count;
    px := Lcp.LPos(rand.Rand MOD count);
    WHILE NOT Lcp.Empty DO BEGIN
      px := Lcp.LPos(rand.Rand MOD count);
      Lcp.UnlinkAfter(px, px);
      Element.Discard(px);
      DEC(count);
    END;
    Lcp.Delete_All(Element);
  END;

  lap := chrono.Lap;
  rand.Done; chrono.Done;
END;  { Copy_LstK }
Figura 8.11: Copy_LstK()

      Para el procedimiento Copy_LstB(), en la Figura 8.10, se invoca la operación TListB.DeleteAfter(px) porque, como la lista Lcp es de tipo TListB (con B), tiene un ligador asociado, Lcp.Bound^, por medio del cual se invoca la operación TBinder.Discard() para eliminar el elemento recién desligado de la lista. Si se usa una lista que no tenga asociado un ligador, de tipo TList (sin la B), hay que desligar el elemento invocando TList.UnlinkAfter(), para luego destruirlo usando TBinder.Discard():
      Lcp.UnlinkAfter(px, px);
      Element.Discard(px);
Esto se muestra en la Figura 8.11 en donde está el procedimiento Copy_LstK() completo. El encabezado de este procedimiento tiene un argumento más que el de Copy_LstB(): el ligador de tipo TBinder, llamado en este caso "Element". Por eso, para destruir el elemento recién desligado de la lista con Lcp.UnlinkAfter(px, px), se invoca Element.Discard(px) pasando como argumento la posición "px", de tipo ^TLlink, que es un puntero al campo de enlace de la lista.

      El tiempo total de corrida de las pruebas asciende a varios meses, pues algunas pruebas tomaron mucho tiempo. Por ejemplo, insertar y borrar en una lista de dos elementos de tipo CHAR, toma un par de segundos, pero se necesitan horas si la lista tiene 5,000 elementos, y cada uno de ellos es una hilera de 255 caracteres. Cuando se corrieron las pruebas, el computador tardó noches enteras corriendo las distintas versiones del mismo algoritmo: unas usaban el contenedor lista implementado directamente, y otras usaban la lista genérica parametrizada a través de Binder.pas. 

UNIT Etst;
{$IFDEF  Etst_INTEGER}
  TYPE
    Etst_TYPE = INTEGER;

  CONST
    SizeOf_TEtst =  SizeOf(Etst_TYPE);
    TEtstName    = 'INTEGER';
    {$DEFINE Use_INTEGER}
{$ENDIF}

TYPE
  TEtst = OBJECT (Binder.TObj)
    _val : Etst_TYPE;

    PROCEDURE Init;
    PROCEDURE Done;
  END;
Figura 8.12: Definición del tipo de _val en Etst.pas

      Para determinar si el tipo de datos contenido en la lista afecta los resultados, se usaron varios tipos de datos en las pruebas. Para eso fue necesario crear un mecanismo que permitiera crear listas que en un caso contendrían elementos de tipo entero, en otro, elementos reales o hileras. Para evitar usar varios programas diferentes para cada tipo de datos se usó la unidad Etst.pas en donde se define el tipo TEtst, que es el tipo de dato almacenado en la lista. De esta forma, para que la lista ejercitada por el programa bndrbnch.pas fuera una lista de números enteros, se definió el campo "_val" de TEtst como un campo de tipo entero, pero para hacer las pruebas con listas de números reales se definió "_val" como un campo real. Por eso la unidad Etst.pas contiene varias directivas de compilación condicional que sirven para recompilar el programa bndrbnch.pas. En la Figura 8.12 se muestra el segmento de código en que se define el tipo del campo "_val" como un campo entero, siempre y cuando la variable de compilación condicional "Etst_INTEGER" esté definida. 

{ S6-1000.bch }
  CONST Bench_File  = 'S6-1000';
  CONST List_Length =     1000;
  CONST Random_Seed =    11111;
  CONST STRING_size =       64; { = 2^6  }
  {$DEFINE Etst_STRING}
Figura 8.13: Archivo S6-1000.bch

      En el archivo de comandos BENCH.bat se invoca el compilador de Turbo Pascal para recompilar bndrbnch.pas, pero usando un archivo "*.bch" diferente. Cada archivo "*.bch" representa una lista diferente, tanto por la cantidad de elementos que tiene, como por el tipo de datos de cada elemento. Por ejemplo, el archivo LL-2000.bch representa una lista de dos mil enteros largos; la letra "L" en el nombre del archivo indica cuál tipo de datos contiene la lista (L=LONGINT). El archivo S6-1000.bch que se muestra en la Figura 8.13 define una corrida de bndrbnch.pas, en donde se usa una lista de hileras de 1,000 elementos, que es el número que aparece en el nombre del archivo. La letra "S" al principio del nombre del archivo indica que, en la corrida, los elementos de la lista serán hileras, de tipo STRING; el tamaño de cada hilera es de 64 bytes, pues 64 = 2^6, lo que efectivamente implica que la hilera tiene capacidad para 63 = 64-1 caracteres. El valor "6" es el dígito que está en el nombre del archivo: S6. 

{ Z6-1000.bch }
  CONST Bench_File  = 'Z6-1000';
  CONST List_Length =     1000;
  CONST Random_Seed =    11111;
  CONST STRING_size =     64-1; { = 2^6  }
  {$DEFINE Etst_STRING}
Figura 8.14: Archivo Z6-1000.bch

      Si se hubiera compilado bndrbnch.pas usando el archivo z6-1000.bch (con una "Z" en lugar de una "S", como se muestra en la Figura 8.14), se obtendría una lista que tiene un byte menos de tamaño en el campo del elemento, para forzar a que el campo de enlace de la lista no quede alineado en frontera de palabra.

      Cada archivo "*.bch" representa una combinación tipo-longitud diferente, y en cada archivo "*.bch" está el código Pascal necesario para que, al compilar el programa bndrbnch.pas, el tipo del campo "_val" de TEtst, definido en la unidad Etst.pas, sea el que corresponde al nombre del archivo "*.bch". Los archivos "*.bch" deben ser generados con anterioridad a la corrida de BENCH.bat, y son archivos diseñados para ser incluidos con la directiva del compilador Pascal {$I Bench.inc}, para que completen la implementación de la unidad Etst.pas. Todos los archivos "*.bch" son parecidos, y contienen código Pascal similar al del archivo S6-1000.bch de la Figura 8.13. 

{$IFDEF Run_Batch}
  {$I Bench.inc}
{$ELSE}
  CONST  Bench_File   = 'Warp';
  CONST  STRING_size  = 255 DIV 127;
  CONST  List_Length  =   500;
  CONST  Random_Seed  = 11111;

  {$DEFINE Etst_EXTENDED}
{$ENDIF}
Figura 8.15: Uso de Bench.inc en Etst.pas

      En cada corrida de BENCH.bat se usa la opción -DRun_Batch para que al recompilar el programa bndrbnch.pas se use un archivo "*.bch" diferente. Para lograr esto, en BENCH.bat se usa el siguiente llamado recursivo:
      for %%d in (*.bch) do call BENCH.bat +++ %%d
El primer argumento contiene +++ para distinguir la invocación inicial a BENCH.bat de los llamados recursivos. Si el siguiente archivo "*.bch" que se va a procesar en el ciclo for es el archivo llamado "S6-1000.bch", en BENCH.bat copiará este archivo sobre Bench.inc, que es el archivo que se incluye, usando {$I Bench.inc}, en la unidad Etst.pas, como se muestra en la Figura 8.15. Por eso en BENCH.bat aparece el siguiente comando:
      copy %2 BENCH.inc
En cada invocación recursiva de BENCH.bat, el segundo argumento %2 se reemplaza por alguno de los archivos "*.bch". Por eso, eventualmente ese argumento tendrá el valor "S6-1000.bch", por lo que el comando ejecutado en BENCH.bat será:
      copy S6-1000.bch Bench.inc

      El último renglón de cada archivo "*.bch" es muy importante, como puede verse en el caso de S6-1000.bch en la Figura 8.13, pues es el que define la variable de compilación Etst_STRING. De esta forma, al compilar la unidad Etst.pas, el tipo del campo "_val" del tipo TEtst es STRING[64-1]: en esa corrida de bndrbnch.pas, el tipo Etst.Etst_TYPE queda definido como STRING[63] gracias a la compilación condicional. 

TYPE
  PEtstL = ^TEtstL;
  TEtstL =  OBJECT (TEtst)
    link : List.TLlink;

    PROCEDURE Init;
    PROCEDURE Done;
  END;
Figura 8.16: Definición de TEtstL

      El tipo TEtst de la Figura 8.12 solamente contiene un campo, llamado "_val". Para almacenar elementos de tipo TEtst en las listas parametrizadas con Binder.pas, es necesario agregarle un campo de enlace de tipo List.TLlink. Esto se logra al definir un nuevo tipo derivado de TEtst, llamado TEtstL (con la "L" de Lista), como se muestra en la Figura 8.16. Al definir el tipo TEtstL también conviene definir PEtstL, que es un puntero al elemento de la lista. Estos punteros no apuntan al campo de enlace (link), pues no son de tipo List.PLlink.

      Todas las ideas descritas anteriormente sirven para lograr usar el mismo programa, bndrbnch.pas, para correr el mismo algoritmo en diferentes implementaciones del ADT lista. El uso de una lista parametrizable en Pascal no es tan complicado, pero el que sea posible implementar un programa como bndrbnch.pas es muestra de que efectivamente es posible parametrizar contenedores en Pascal, compartiendo la implementación de los algoritmos. Para terminar la descripción de cómo fueron obtenidas las mediciones de tiempo de ejecución, falta describir los diferentes tipos de lista que fueron usados. En total se usaron cuatro tipos de lista diferentes, y a cada uno de ellos corresponde un procedimiento de copiar la lista; en la Figura 8.8 está el que corresponde a TListB, y en la Figura 8.11 el de TList. Esta es la descripción detallada de los diferentes tipos de listas usados para comparar los tiempos de ejecución:

TLstC
Esta es una lista circular no polimórfica, basada en la implementación descrita en [DiM-94f]. Es la que usualmente un programador produciría cuando no puede reutilizar contenedores. Su implementación está en la unidad LstC.pas, y requiere que el programador cliente escriba una unidad Elem.pas que implemente cada una de las operaciones elementales que se usan en la implementación de LstC.pas. Para usar dos de estas listas, el programador cliente debe copiar manualmente la implementación completa de la unidad LstC.pas, efectivamente instanciando a mano sus listas.
TList
Esta es una lista parametrizable pura, obtenida al usar el módulo compilado List.pas, por lo que para accesar el elemento de la lista hay que contar, de antemano, con el ligador que lo describe. Esta lista es la que corresponde al procedimiento Copy_LstK() de la Figura 8.11, en donde se usa el ligador "Element" para manipular los valores almacenados en la lista, que el procedimiento recibe como un argumento extra.
TeList_TEtstL_link
Para obtener este tipo se aplicó el programa CTPinst al elemento TEtstL definido en la unidad Etst.pas, para generar una interfaz para la lista con base en la plantilla que está en el archivo List.ctp, interfaz que CTPinst dejó en la unidad Envelope.pas. Todas las operaciones de esta lista siempre reciben punteros a los elementos como argumentos (de tipo PEtstL), por lo que para el programador cliente estas listas se usan de forma similar a una lista de tipo TLstC. En otras palabras, en esta lista una "posición" en la lista es simplemente un puntero al elemento que está almacenado en la lista. La única diferencia entre esta lista y una definida con el módulo LstC.pas es que el programador cliente tiene la responsabilidad de incluir un campo de enlace en su elemento (si no lo hiciera, el código generado en la unidad Envelope.pas por CTPinst no compilaría con el resto del programa). En otras palabras, el programador cliente debe usar elementos de tipo TEtstL (con L), en lugar del tipo TEtst que se usa en una lista TLstC.
      Como las operaciones de una lista TeList_TEtstL_link tienen que invocar las operaciones del elemento a través de un ligador definido como variable global en la unidad Envelope.pas, es natural esperar que estas listas sean un poco menos eficientes en tiempo de ejecución que las listas de tipo TLstC, que accesan directamente las operaciones del ADT elemental almacenado. Por ejemplo, para comparar dos listas se usa esta invocación:
      TeList_TEtstL_link.Equal(o);
la que resulta en una invocación a:
      TList.Equal(o, Binder_TList_TEtstL_link);
en donde Binder_TList_TEtstL_link es el ligador definido en Envelope.pas como variable global para que sea compartido por todas las listas. Más aún, las operaciones de estas listas necesitan ajustar los punteros usando el ligador antes de invocar las operaciones de TList, que es donde se hace efectivamente todo el trabajo algorítmico de la lista. Por ejemplo, como se muestra en la Figura 7.32, la invocación a:
      TeList_TEtstL_link.LinkAfter(p, x); { con "e" }
resulta en una invocación a:
      TList.LinkAfter(@ (p^.link), x.link);
      Pese a que para el programador cliente estas listas se sienten como las listas que se pueden obtener instanciando manualmente la unidad LstC.pas, tienen la gran ventaja de que todas comparten la misma implementación de la lista, lo que disminuye el tamaño de los programas si se usan varias listas diferentes.
TListB
Esta es una lista que ha sido implementada usando directamente Binder.pas, pero sin usar el programa CTPinst para lograr verificación fuerte de tipos. El camino seguido incluye usar la unidad Bound.pas en la implementación de la unidad ListB.pas. Estas listas incluyen un puntero al ligador que describe el elemento que contienen, el que se puede obtener invocando cualquiera de las operaciones TListB.Element() o TListB.Bound() (ver Figura 7.39). Para estas listas no hay que instanciar plantilla alguna con CTPinst, pero a cambio hay que usar un poco más de espacio en cada lista (para almacenar el puntero al ligador). Para esta lista el compilador no verifica que los tipos de los elementos sean los correctos, pues se usa directamente el método TList.UnLinkAfter(x.link) para enlazar el campo de enlace ".link" a la lista.

      {$IFDEF INSTANTIATE}  {$IFNDEF INSTANTIATE}
TYPE
  List{.ctp} = TEMPLATE (TList)
    INSTANTIATE <TElem> TO TEtstL;
    INSTANTIATE <PElem> TO PEtstL;
    INSTANTIATE <link>  TO link;

    USES Init;    TO Less USES IsLess;
    USES Done;            USES Equal;

  END; { List }               {$ENDIF} {$ENDIF}
Figura 8.17: Uso de la plantilla List.ctp para definir Etst.TEtstL

      En la Figura 8.17 se muestran las declaraciones que están en la unidad Etst.pas y que son usadas por el programa CTPinst para instanciar las listas de acuerdo con el archivo de plantillas List.ctp (todo el código Pascal generado por CTPinst queda en la unidad Envelope.pas). Como en la plantilla List.ctp el nombre de una lista se obtiene concatenándole al identificador "TList" el nombre del elemento, que en estos casos es "TEtstL", y también agregando el nombre del campo de enlace de elemento, que para el tipo TEtstL es "link", el resultado es que el nombre del tipo de la lista es bastante largo:
      TList_TEtstL_link  = TList + TEtstL + link
      TeList_TEtstL_link = T+e+List + TEtstL + link

      La diferencia entre TList_TEtstL_link y TeList_TEtstL_link (con "e") es difícil de apreciar a primera vista, pues ambos tipos comparten una cualidad: en ninguna instancia de esos tipos de lista se incluye un campo de tipo ^TBinder, para asociar la lista con su ligador, sino que se usa un solo ligador para todas las listas: Binder_TList_TEtstL_link. Una de las ventajas de usar la plantilla List.ctp es que varias instancias de contenedores del mismo tipo compartan el mismo ligador. La diferencia está en el segundo tipo, cuyo nombre incluye la letra "e" de "elemento", pues en este caso las posiciones dentro de la lista son punteros a elementos (^TEtstL), mientras que en el otro son punteros a los campos de enlace (^TLlink).

      En el programa bndrbnch.pas no se ejercitan listas de tipo TList_TEtstL_link (sin la "e"), pues el rendimiento en tiempo de esas listas es mejor que el de las listas TeList_TEtstL_link, porque no hace falta ajustar el puntero al elemento para que apunte al campo de enlace, con la consiguiente pérdida de eficiencia en tiempo de ejecución, como se discute en los párrafos que siguen a la Figura 7.32: lo que se busca determinar con las corridas de bndrbnch.pas es cuán ineficiente es una lista parametrizada a través de Binder.pas respecto de una implementada tradicionalmente, como la lista de la unidad LstC.pas. 

UNIT Etst;

{$I Bench.inc}

{$IFDEF  Etst_INTEGER}
  TYPE
    Etst_TYPE = INTEGER;
    {$DEFINE Use_INTEGER}
{$ENDIF}

TYPE
  TEtst = OBJECT (Binder.TObj)
    _val : Etst_TYPE;

    PROCEDURE Init;
    PROCEDURE Done;
  END;

TYPE
  PEtstL = ^TEtstL;
  TEtstL =  OBJECT (TEtst) { con L }
    link : List.TLlink;

    PROCEDURE Init;
    PROCEDURE Done;
  END;

{$IFDEF INSTANTIATE} {$IFNDEF INSTANTIATE}
TYPE
  List{.ctp} = TEMPLATE (TList)
    INSTANTIATE <TElem> TO TEtstL;
    INSTANTIATE <PElem> TO PEtstL;
    INSTANTIATE <link>  TO link;

    USES Init;    TO Less USES IsLess;
    USES Done;            USES Equal;

  END; { List }          {$ENDIF} {$ENDIF}
Figura 8.18: El tipo TEtstL definido en la unidad Etst.pas

      La Figura 8.18 es la combinación de las definiciones que se usan en la unidad Etst.pas para definir el tipo TEtstL, usado por el programa bndrbnch.pas. Las pruebas que se han hecho buscan comparar la velocidad con que se puede manipular una lista tra