Entry Ducournau:2008:PHA from toplas.bib

Last update: Tue May 1 02:05:46 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Ducournau:2008:PHA,
  author =       "Roland Ducournau",
  title =        "Perfect hashing as an almost perfect subtype test",
  journal =      j-TOPLAS,
  volume =       "30",
  number =       "6",
  pages =        "33:1--33:56",
  month =        oct,
  year =         "2008",
  CODEN =        "ATPSDT",
  DOI =          "http://doi.acm.org/10.1145/1391956.1391960",
  ISSN =         "0164-0925 (print), 1558-4593 (electronic)",
  ISSN-L =       "0164-0925",
  bibdate =      "Sat Nov 1 20:05:05 MDT 2008",
  bibsource =    "http://www.acm.org/pubs/contents/journals/toplas/;
                 http://www.math.utah.edu/pub/tex/bib/toplas.bib",
  abstract =     "Subtype tests are an important issue in the
                 implementation of object-oriented programming
                 languages. Many techniques have been proposed, but none
                 of them perfectly fulfills the five requirements that
                 we have identified: constant-time, linear-space,
                 multiple inheritance, dynamic loading and inlining. In
                 this article, we propose a subtyping test
                 implementation that involves a combination of usual
                 hashtables and Cohen's display, which is a well-known
                 technique for single inheritance hierarchies. This
                 novel approach is based on {\em perfect hashing}, that
                 is, an optimized and truly constant-time variant of
                 hashing that applies to {\em immutable\/} hashtables.
                 We show that the resulting technique closely meets all
                 five requirements. Furthermore, in the framework of
                 Java-like languages --- characterized by single
                 inheritance of classes and multiple subtyping of
                 interfaces --- perfect hashing also applies to method
                 invocation when the receiver is typed by an interface.
                 The proposed technique is compared to some
                 alternatives, including the proposal by Palacz and
                 Vitek [2003]. Time-efficiency is assessed at the cycle
                 level in the framework of Driesen's pseudo-code and the
                 linear-space criterion is validated by statistical
                 simulation on benchmarks consisting of large-scale
                 class hierarchies.",
  acknowledgement = ack-nhfb,
  articleno =    "33",
  fjournal =     "ACM Transactions on Programming Languages and
                 Systems",
  keywords =     "Casting; coloring; downcast; dynamic loading;
                 interfaces; method tables; multiple inheritance;
                 multiple subtyping; perfect hashing; single
                 inheritance; subtype test; virtual function tables",
}

Related entries