generics & efficiency

generics & efficiency

[David Erickson]

I recently gave an assignment in a data structures class that had
students trying lots of techniques to reduce the cpu-time consumed
by their programs (the project was to take a list of titles and
produce a key-word-in-context index).  One of the surprising results
was that the use of a generic package for the ADT's imposed a large
overhead.  One group of students compared the performance of linked
lists, binary-search-trees and AVL trees (height balanced binary
search trees).  They found a 60% speed up in the AVL tree case,
when they converted the ADT from a generic to a regular package.

The original (generic) version looked like this:

generic
type KEY is private;
type ITEM is private;
with function "<"(A,B:KEY) return BOOLEAN is <>;
with function KEY_VALUE(DATA: ITEM) return KEY;
with procedure VISIT(DATA: in ITEM);
package AVL is
type TREE_NODE;
type AVLT is access TREE_NODE;
type TREE_NODE is
  record
    INFO: ITEM;
    L, R: AVLT;
    HT: INTEGER;
  end record;
--functions and procedure declarations here
end AVL;

The non-generic version looked like:

package AVL2 is
  MAX_LENGTH: constant := 76;
  type ATOM is
    record
      S: STRING(1..(MAX_LENGTH + 3));
      L: NATURAL;
    end record;
  type TREE_NODE;
  type AVLT is access TREE_NODE;
  type TREE_NODE is
    record
      INFO: ITEM;
      L, R: AVLT;
      HT: INTEGER;
    end record;
--functions and procedure declarations here
end AVL2;

The procedures and functions in each package body were identical.

The compiler was Meridian/Sun 4.

Any guesses why the generic package imposed such an overhead?

I thought it would be of interest to reorder the fields in a TREE_NODE
and put the ITEM field last, but what with final exams, the students haven't
had a chance to try.

-Dave Erickson