Simple and Efficient Subclass Tests Paper / Talk

[Jonathan Bachrach <address@hidden>]

As promised, my ECOOP-02 paper submission on Simple and Efficient
Subclass Tests is now available at:

  www.ai.mit.edu/~jrb/pve/pve.pdf

i will also be presenting this material at our dynamic languages
seminar this friday.  for those that want to get these sort of
announcements, please sign up on our emailing list by sending a
request to gregs@ai.mit.edu .

Jonathan Bachrach

            Dynamic Languages Seminar
    http://www.ai.mit.edu/projects/dynlangs/ 

Who:   Jonathan Bachrach, MIT AI Lab
When:  Friday, Nov. 30, 2-3pm.  Refreshments from 1:45pm to 2.
What:  Simple and Efficient Subclass Tests
Abstract:
  Fast subclass tests are crucial for the performance of
  object-oriented languages, especially those with dynamic
  typing. Unfortunately, fast constant time subclass encodings to date
  present a difficult tradeoff: either choose a simple encoding with
  O(n^2) space requirements (where n is the number of classes) or a
  more complicated and slower to construct encoding with better space
  properties. In this paper, we present a new subclass test encoding,
  called the Packed Vector Encoding (PVE), that is fast, simple and
  requires average case O(n log n) space.

Where: 8th floor play room of MIT building NE43, aka 545
       Technology Square, aka 200 Technology Square.

Upcoming Events: 

  * Fri. 12/14/01, Brian Lewis, "BRL: Code simply, that others might
    simply code"

  * Fri. 12/21/01, Ali Rahimi, "Lazy Containers: an Efficient
    Compile-time Abstraction for Manipulating Collections of Objects
    Using Expression Templates"

Directions: http://www.ai.mit.edu/visiting/directions.shtml