From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.5-pre1 (2020-06-20) on
	ip-172-31-74-118.ec2.internal
X-Spam-Level: *
X-Spam-Status: No, score=1.0 required=3.0 tests=BAYES_20,MSGID_SHORT,
	TO_NO_BRKTS_PCNT autolearn=no autolearn_force=no version=3.4.5-pre1
Date: 18 Sep 92 22:50:37 GMT
From: taurus!grus!erickson@lll-winken.llnl.gov  (David Erickson)
Subject: generics & efficiency
Message-ID: <6342@grus.cs.nps.navy.mil>
List-Id: <comp.lang.ada>

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