Efficient Binary Transfer of Pointer Structures
Download full technical report (PDF, 730K)
I. Toyn and A. J. Dix (1994).
Efficient Binary Transfer of Pointer Structures.
Software Practice and Experience, 24(11): 1001-1023.
Keywords Pointer structure, Lazy transfer, Distributed system, Inter-process communication, Remote procedure call, Cadiz
This paper presents a pair of algorithms for output and input of pointer structures in binary
format. Both algorithms operate in linear space and time. They have been inspired by copying
garbage collection algorithms, and make similar assumptions about the representations of
In real programs, the transfer of entire pointer structures is often inappropriate. The algorithms
are extended to transfer partitions of a pointer structure lazily: the receiver requests partitions
when it needs them.
A remote procedure call mechanism is presented that uses the binary transfer algorithms for
communicating arguments and results. A use of this as an enabling mechanism in the implementation
of a software engineering environment is discussed.
- 1. R. R. Fenichel and J. C. Yochelson, 'A LISP garbage-collector for virtual-memory computer systems',
Communications of the ACM 12(11), 611–612 (1969).
- P. R. Wilson, 'Uniprocessor garbage collection techniques', in Y. Bekkers and J. Cohen (eds), International
Workshop on Memory Management, Springer Verlag Lecture Notes in Computer Science 637,
September 1992, pp. 1–42.
- C. J. Cheney, 'A nonrecursive list compacting algorithm', Communications of the ACM, 13(11), 677–
- D. A. Fisher, 'Copying cyclic list structures in linear time using bounded workspace', Communications
of the ACM, 18(5), 251–252 (1975).
- D. W. Clark, 'A fast algorithm for copying list structures', Communications of the ACM, 21(5), 351–
- A. S. Tanenbaum, R. van Renesse, H. van Staveren, G. J. Sharp, S. J. Mullender, J. Jansen and G.
van Rossum, 'Experiences with the AMOEBA distributed operating system', Communications of the
ACM, 33, 46–63 (1990).
- SUN Microsystems, Network Programming Guide, 1990.
- S. Wilbur and B. Bacarisse, 'Building distributed systems with remote procedure call', Software
Engineering Journal, 2(5), 148–159 (1987).
- Andrew S. Tanenbaum, Modern Operating Systems, Prentice-Hall Int., 1992.
- A. D. Birrell and B. J. Nelson, 'Implementing remote procedure calls', ACM Transactions on Computer
Systems, 2(1), 39–59 (1984).
- D. T. Jordan, J. A. McDermid and I. Toyn, 'CADiZ—computer aided design in Z', 5th Oxford Z User
Meeting, Springer-Verlag Workshops in Computing, December 1990.
- D. A. Lamb, 'Sharing intermediate representations: the interface description langauge', CMU-CS-83-
129, Department of Computer Science, Carnegie-Mellon University, May 1983.
- J. M. Newcomer, 'Efficient binary I/O of IDL objects', ACM SIGPLAN Notices, 22(11), 35–43 (1987).
- M. Herlihy and B. Liskov, 'A value transmission method for abstract data types', ACM Transactions
on Programming Languages and Systems, 4(4), 527–551 (1982).