Name
Abstract | ||
|---|---|---|
We introduce a new compacting garbage-collection algorithm with a very good averagecase performance. The algorithm combines the advantages of the two most frequently used algorithms for this purpose, mark-sweep and copying algorithms. The algorithm has an average time complexity that is only linear in the number of accessible edges, and it uses only a small amount of extra storage. As a subroutine, we use of a variant of the linear-probing sort algorithm that was presented and analysed by Gonnet and Munro. The distribution of the elements is better than uniform, thus we show a lower cost for sorting. We also give a new analysis of the cost of searching an element in the sorted table, since it is needed for the algorithm. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1007/BFb0020807 | STACS |
Keywords | Field | DocType |
good average-case performance,new compacting garbage-collection algorithm,time complexity,garbage collection,sorting algorithm | Subroutine,Computer science,Mark-compact algorithm,Parallel computing,Algorithm,Copying,Sorting,Garbage collection,Time complexity,Sorting algorithm | Conference |
Volume | ISBN | Citations |
480 | 0-387-53709-0 | 0 |
PageRank | References | Authors |
0.34 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Svante Carlsson | 1 | 764 | 90.17 |
| Christer Mattsson | 2 | 21 | 2.45 |
| Patricio V. Poblete | 3 | 232 | 50.10 |
| Mats Bengtsson | 4 | 1493 | 110.70 |