From: taurus!grus!erickson@lll-winken.llnl.gov (David Erickson)
Subject: generics & efficiency
Date: 18 Sep 92 22:50:37 GMT [thread overview]
Message-ID: <6342@grus.cs.nps.navy.mil> (raw)
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
reply other threads:[~1992-09-18 22:50 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox