Exploiting array manipulation habits to optimize garbage collection and type flow analysis

International audienceA widespread practice to implement a flexible array isto consider the storage area into two parts: the used area which is already available for read/write operations and, the supply area, which isused in case of enlargement of the array.The main purpose of the supply area is to avoid as much as possible the reallocationof the whole storage area in case of enlargement.As the supply area is not used by the application, the main idea of the paper is toconvey the information to the garbage collector, making it possible to avoidcompletely the marking of the supply area.We also present a simple method to analyze the types of objectswhich are stored in an array as well as the possible presence of null valueswithin the array.This allows us to better specialize the work of the garbage collector whenmarking the used area, and also, by transitivity, to improve overall resultsfor type analysis of all expressions of the source code.After introducing several abstract data types which represent the main arrays concernedby our technique (i.e. zero or variable indexing, circular arrays and hash maps), wemeasure its impact during the bootstrap of two compilers whose libraries are equippedwith these abstract data types.We then measure, on various software products we have not written, the frequency of certain habits of manipulation of arrays, to assess the validity ofour approach