NDLI: Incremental algorithms for dispatching in dynamically typed languages

Please wait, while we are loading the content...

The essence of XML

Selective memoization

Environment classifiers

Bigraphs and transitions

The m-calculus: a higher-order distributed process calculus

A generic approach to the static analysis of concurrent programs with procedures

Discovering affine equalities using random interpretation

Bitwidth aware global register allocation

From symptom to cause: localizing errors in counterexample traces

Folklore confirmed: reducible flow graphs are exponentially larger

New results on the computability and complexity of points--to analysis

Incremental algorithms for dispatching in dynamically typed languages

From control effects to typed continuation passing

Coercive subtyping for the calculus of constructions

Efficient algorithms for isomorphisms of simple types

A type theory for memory allocation and data layout

Static prediction of heap space usage for first-order functional programs

Toward a foundational typed assembly language

Ownership types for object encapsulation

Guarded recursive datatype constructors

A type system for higher-order modules

Pure patterns type systems

Destructors, finalizers, and synchronization

Interprocedural compatibility analysis for static object preallocation

A real-time garbage collector with low overhead and consistent utilization

Incremental algorithms for dispatching in dynamically typed languages

Content Provider	ACM Digital Library
Author	Gil, Joseph Yossi Zibin, Yoav
Abstract	A fundamental problem in the implementation of object-oriented languages is that of a frugal dispatching data structure, i.e., support for quick response to dispatching queries combined with compact representation of the type hierarchy and the method families. Previous theoretical algorithms tend to be impractical due to their complexity and large hidden constant. In contrast, successful practical heuristics, including Vitek and Horspool's compact dispatch tables (CT) [16] designed for dynamically typed languages, lack theoretical support. In subjecting CT to theoretical analysis, we are not only able to improve and generalize it, but also provide the first non-trivial bounds on the performance of such a heuristic.Let n,ml denote the total number of types, messages, and different method implementations, respectively. Then, the dispatching matrix, whose size isnm, can be compressed by a factor of at most ι ≡ (nm)/l. Our main variant to CT achieves a compression factor of ½ √ι. More generally, we describe a sequence of algorithms CT1, CT2, CT3,., where CTd achieves compression by a factor of (at least) $^{1}overdι^{1—1/d},$ while using d memory dereferencing operations during dispatch. This tradeoff represents the first bounds on the compression ratio of constant-time dispatching algorithms.A generalization of these algorithms to a multiple-inheritance setting, increases the space by a factor of $κ^{1-1/d},$ where κ is a metric of the complexity of the topology of the inheritance hierarchy, which (as indicated by our measurements) is typically small. The most important generalization is an incremental variant of the CTd scheme for a single-inheritance setting. This variant uses at most twice the space of CTd, and its time of inserting a new type into the hierarchy is optimal. We therefore obtain algorithms for efficient management of dispatching in dynamic-typing, dynamic-loading languages, such as Smalltalk and even the Java invokeinterface instruction.
Starting Page	126
Ending Page	138
Page Count	13
File Format	PDF
ISBN	1581136285
DOI	10.1145/604131.604143
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-01-15
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Ct Hierarchy Incremental Dynamic-typing Message Dispatch
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in