Entry Pugh:1990:TRL from sigplan1990.bib

Last update: Thu Apr 12 03:37:15 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | 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{Pugh:1990:TRL,
  author =       "William Pugh and Grant Weddell",
  title =        "Two-directional record layout for multiple
                 inheritance",
  journal =      j-SIGPLAN,
  volume =       "25",
  number =       "6",
  pages =        "85--91",
  month =        jun,
  year =         "1990",
  CODEN =        "SINODQ",
  ISBN =         "0-89791-364-7",
  ISBN-13 =      "978-0-89791-364-5",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  bibdate =      "Thu May 13 12:37:27 MDT 1999",
  bibsource =    "Compendex database;
                 http://www.acm.org/pubs/contents/proceedings/pldi/93542/index.html",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/93542/p85-pugh/",
  abstract =     "Much recent work in polymorphic programming languages
                 allows subtyping and multiple inheritance for records.
                 In such systems, we would like to extract a field from
                 a record with the same efficiency as if we were not
                 making use of subtyping and multiple inheritance.
                 Methods currently used make field extraction 3-5 times
                 slower, which can produce a significant overall
                 performance slowdown. We describe a record layout
                 algorithm that allows us to assign a fixed offset to
                 each field name. This allows field extraction to done
                 just as quickly as in systems that do not provide
                 multiple inheritance. Assigning fixed offsets may
                 require us to leave gaps in some records (and waste
                 space). However, by placing fields at both positive and
                 negative offsets we can drastically reduce the amount
                 of wasted space. Finding an optimal layout is NP-hard,
                 so we propose and analyze heuristic algorithms for
                 producing good two-direction record layouts. In a trial
                 run, our algorithm produced a fixed layout for the
                 instance variables of the 563 flavors of a Lisp Flavors
                 system; this fixed layout only wastes 6\% of the total
                 space consumed by a collection of one instance of each
                 flavor.",
  acknowledgement = ack-nhfb,
  affiliation =  "Univ of Maryland",
  affiliationaddress = "College Park, MD, USA",
  annote =       "Published as part of the Proceedings of PLDI'90.",
  classification = "722; 723",
  conference =   "Proceedings of the ACM SIGPLAN '90 Conference on
                 Programming Language Design and Implementation",
  conferenceyear = "1990",
  journalabr =   "SIGPLAN Not",
  keywords =     "algorithms; Computer Operating Systems; Computer
                 Programming --- Object Oriented Programming; design;
                 languages; Multiple Inheritance; performance;
                 Polymorphic Programming Languages; Program Compilers",
  meetingaddress = "White Plains, NY, USA",
  meetingdate =  "Jun 20--22 1990",
  meetingdate2 = "06/20--22/90",
  sponsor =      "Assoc for Computing Machinery, Special Interest Group
                 on Programming Languages",
  subject =      "{\bf F.3.3} Theory of Computation, LOGICS AND MEANINGS
                 OF PROGRAMS, Studies of Program Constructs, Functional
                 constructs. {\bf D.3.3} Software, PROGRAMMING
                 LANGUAGES, Language Constructs and Features,
                 Procedures, functions, and subroutines. {\bf G.2.2}
                 Mathematics of Computing, DISCRETE MATHEMATICS, Graph
                 Theory, Graph algorithms.",
}

Related entries