Dominique Colnet   

LORIA
615 rue du Jardin Botanique
BP-101
54602 Villers-lès-Nancy
FRANCE
Professor, Université de Lorraine

IUT Nancy Charlemagne
Département Informatique
2 ter, Bd Charlemagne
54000 Nancy
FRANCE
Photograph of Dominique Colnet

Office: (33) 03 54 50 38 27 Cell: (33) 06 65 36 23 81 Email: Dominique.Colnet@loria.fr
Teaching materials.
[o] 2014, Software Practice and Experience, SP&E, DOI 10.1002/spe2300, 2014, 18 pages.
Exploiting array manipulation habits to optimize garbage collection and type flow analysis.
Dominique Colnet, Benoît Sonntag.
Abstract: A widespread practice to implement a flexible array is to consider the storage area into two parts: the used area which is already available for read/write operations and, the supply area, which is used in case of enlargement of the array. The main purpose of the supply area is to avoid as much as possible the reallocation of 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 to convey the information to the garbage collector, making it possible to avoid completely the marking of the supply area.
We also present a simple method to analyze the types of objects which are stored in an array as well as the possible presence of null values within the array. This allows us to better specialize the work of the garbage collector when marking the used area, and also, by transitivity, to improve overall results for type analysis of all expressions of the source code.
After introducing several abstract data types which represent the main arrays concerned by our technique (i.e. zero or variable indexing, circular arrays and hash maps), we measure its impact during the bootstrap of two compilers whose libraries are equipped with 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 of our approach.
[o] 2013, Software Practice and Experience, SP&E, John Wiley & Sons, Ltd, 2013, Volume 44, Issue 5, 565--593, DOI 10.1002/spe.2174, 28 pages.
Efficient compilation strategy for object-oriented languages under the closed-world assumption.
Benoît Sonntag, Dominique Colnet.
Abstract: Reaching the best level of runtime performance from a high-level, object-oriented language is often considered challenging if not unattainable. The closed world assumption involves considering all of the source code of an application together at compile-time. That assumption makes it possible to produce an efficient code. For instance, multiple inheritance can be implemented as efficiently as single inheritance.
Our compilation strategy is the result of a prolonged project, tying together several compilation techniques: call graph analysis, dead code elimination, type flow analysis, code customization, implementation of dynamic dispatch, inlining, pointer optimization, switch optimization, objects layout, etc. Merging all of these techniques into a global strategy appears to be quite problematic. Throughout the paper two real-world compilers are used as benchmarks to provide measurements for compiler-writers in order to evaluate the applicability of our approach.
Type flow analysis is a fundamental aspect of our strategy to resolve method calls. We have extended type flow analysis to deal with the content of arrays, enabling us to process additional expressions and thus making it possible to obtain a true global analysis. Typically more than 90% of method call sites are statically resolved. Our experience indicates that the closed world assumption is suitable for numerous applications. Surprisingly, even library-defined control statements from dynamic languages are perfectly processed with our strategy. The Smalltalk ifTrue:ifFalse:, whileTrue:, to:do:, etc. are, for the very first time, perfectly translated.
[o] 2012, Conference CIEL 2012, Rennes, 19 au 21 juin 2012.
Analyse simple de types dans les tableaux et optimisation du ramasse-miettes.
Dominique Colnet, Benoît Sonntag.
Résumé: Cet article commence en présentant une technique très simple, par analyse de flots de types et ordre de remplissage imposé, permettant de prédire le contenu des tableaux. D'abord présentée pour les tableaux primitifs indexés à partir de 0, notre technique est ensuite étendue pour prendre en compte les autres structures de données de plus haut niveau: tableaux à indexation variable, tableaux circulaires et tables de hachage.
Le résultat essentiel consiste à pouvoir faire suivre l'information de flots de types déjà collectée pour le reste du code source au travers des expressions qui manipulent des tableaux, permettant ainsi de procéder à une analyse de flots de types vraiment globale.
En plus de l'amélioration de la prédiction de types utile pour la liaison dynamique et la sécurité des langages à objets, notre technique permet d'optimiser la gestion mémoire. En effet, grâce à la technique de remplissage utilisée, le ramasse-miettes (GC) n'inspecte que les zones utiles des tableaux en évitant de collecter des objets inaccessibles, référencés par les zones de réserve. Ces zones de réserve n'ont par ailleurs nullement besoin d'être initialisées avant utilisation ni nettoyées aprés usage.
Les mesures présentées permettent de se rendre compte de l'impact de cette technique, aussi bien en terme de qualité de l'analyse de flots, qu'en terme de gain au niveau de la gestion mémoire durant le marquage et le balayage des tableaux.
[o] 2006, Proceedings of the 9th International Conference on Software Reuse, Turin, june 2006, Lecture Notes in Computer Sciences, Springer-Verlag, Volume 4039, pages 203-216, ISBN 3-540-34606-6.
Reconciling Subtyping and Code Reuse in Object-Oriented Languages: Using inherit and insert in SmartEiffel, The GNU Eiffel Compiler.
Dominique Colnet, Guillem Marpons, Frederic Merizen.
Abstract: SmartEiffel has been enjoying two different mechanisms to express subtyping and implementation inheritance for one year. After large scale practical tests and thanks to user feedback, this paper finalises the new typing policy of SmartEiffel, which combines two forms of multiple inheritance with genericity in one statically-checked, object-oriented language.
Having two forms of inheritance allows the designer to capture more design decisions in the source code. It is now straightforward to share reusable code between otherwise unrelated types. The new mechanism allows to reuse code from an existing class without polluting the reuser's interface. It also enables an elegant implementation of some design patterns.
Furthermore, this mechanism helps compilers to statically remove more dynamic dispatch code. It can also be used to add a no-penalty and no-risk multiple-inheritance-like construct to a single-inheritance language such as Java.
[o] 2006, Actes du Colloque Langages et Modèles à Objets, LMO'06, Nîmes, mars 2006, Édition HERMES, pages 87-100.
Héritage non conforme en Eiffel.
Frédéric Mérizen, Dominique Colnet, Philippe Ribet, Cyril Adrian.
[o] 2005, (1994--2005) Polycopié de cours et d'exercices, dernière version 177 pages.
Eiffel, SmallEiffel, conception, programmation, objets, contrats, et cetera.
Dominique Colnet
[o] 2002, Proceedings of the fortieth conference on Technology of Object-Oriented Languages and Systems (TOOLS Pacific'2002), Sydney, Australia, February 2002, Australian Computer Society, pages 45-52, James Noble and John Potterm, Eds.
Lisaac: the power of simplicity at work for operating system.
Benoît Sonntag, Dominique Colnet.
Abstract: The design as well as the implementation of the Isaac operating system (http://www.isaacOS.com) led us to set up a new programming language named Lisaac. Many features from the Lisaac language come from the Self programming language. Comparing to Self's skills, Lisaac integrates communications protection mechanisms as well as other tools related to operating systems' design. System interruptions support as well as drivers memory mapping have been considered in the design of Lisaac. The use of prototypes and especially dynamic inheritance, fits a flexible operating system in the making. First benchmarks of our compiled objects show that it is possible to obtain high-level prototype-based language's executables as fast as C programs are.
[o] 2001, Software Practice and Experience, 2001, Volume 31, No 6, pages 601-613.
Coping with aliasing in the GNU Eiffel Compiler implementation.
Olivier Zendra, Dominique Colnet.
Abstract: This paper report our experience about aliasing usage in the implementation of SmallEiffel, the GNU Eiffel Compiler. The SmallEiffel compiler source code makes intensive use of aliasing in order to achieve very good performance both in terms of memory and execution time. Thanks to the design by contract capabilities of the Eiffel language, aliasing can be handled very safely. The singleton pattern appears to be crucial in implementing alias provider objects. We propose an efficient implementation of this pattern made easy by some Eiffel idioms. This technique, which requires no language modification, is very appropriate for compilation, but can also be applied to a wide range of applications.
[o] 2000, Actes du Colloque Langages et Modèles à Objets, LMO'00, Mont Saint-Hilaire, Québec, janvier 2000, Édition HERMES, pages 183-194.
Vers un usage plus sûr de l'aliasing avec Eiffel.
Olivier Zendra, Dominique Colnet.
Résumé: Le code source du compilateur SmallEiffel fait un usage intensif de l'aliasing afin d'atteindre les meilleures performances, tant en termes de mémoire que de vitesse d'exécution. Cette technique semble très appropriée à la compilation mais peut aussi s'appliquer à une large gamme d'applications. Grâce aux capacités de programmation par contrat du langage Eiffel, l'aliasing peut être géré d'une façon assez sûre.Le modèle de conception singleton se révèle également crucial pour l'implantation d'objets fournisseurs d'alias. Nous présentons ici une implantation efficace de ce modèle rendue possible par certains idiomes d'Eiffel.
[o] 2000, Habilitation à Diriger des Recherches de l'Université Henri Poincaré -- Nancy I, Mémoire présenté et soutenu publiquement le 22 décembre 2000.
Compilation, langages à objets et programmation par contrats. Expérience acquise dans le cadre du projet ``SmallEiffel The GNU Eiffel Compiler.''
Dominique Colnet
[o] 2000, 35th conference on Technology of Object-Oriented Languages and Systems (TOOLS Pacific'2000), IEEE Computer Society, Sydney, Australia, November 2000, pages 190--201.
Match-O, a Dialect of Eiffel with Match-Types.
Dominique Colnet, Luigi Liquori.
Abstract: It is well known that the Eiffel language allows covariant redefinition. Regardless of system-level validity rules, Eiffel is not type safe. In this paper, we present a dialect of Eiffel called Match-O, which prohibits covariant redefinition. We introduce a new kind of types, the match-types, inspired by the papers of Kim Bruce. The scope of this project is many-fold: -- allowing binary methods; -- keeping sound ``mytype method specialization'', i.e. anchored type using Current; -- allowing subtyping in all other sound cases. We claim that match-types can be added in the Eiffel type system to eliminate type unsoundness without blocking many interesting Eiffel programs (e.g. the ones with ``binary methods''). We have implemented a compiler for Match-O and we have experimented our dialect on a large system using the original source code of SmallEiffel itself.
[o] 1999, 32nd conference on Technology of Object-Oriented Languages and Systems (TOOLS Pacific'99), IEEE Computer Society, Melbourne, Australia, 22-25 November 1999, pages 188--199.
Adding external iterators to an existing Eiffel class library.
Olivier Zendra, Dominique Colnet.
Abstract: This paper discusses common iteration schemes and highlights the interest of using explicit iterators. The advantages of external iterators are compared to those of internalized iterators. The integration of an iterator class hierarchy to an existing library without modifying the latter is detailed. This integration brings an extra level of abstraction to the library, which thus becomes more flexible, more adapted to certain design patterns and hence can be used in a higher-level way. Such an integration is not only possible, but can even be done in an optimized way, taking into account the specific structure of the collection traversed. A slight extension of existing class libraries can also be implemented that does not cause any compatibility problem and does not break existing code, but allows even further abstraction and makes it easier for the developer to use high-level, optimized, external iterators.
[o] 1999, 29th conference on Technology of Object-Oriented Languages and Systems (TOOLS Europe'99), IEEE Computer Society, Nancy, France, June 7-10, 1999, pages 341--350.
Optimizations of Eiffel programs: SmallEiffel, The GNU Eiffel Compiler.
Dominique Colnet, Olivier Zendra.
Abstract: The design of the Eiffel language makes it possible to perform global optimizations on Eiffel programs. In this paper, we describe some of the techniques we used in SmallEiffel, The GNU Eiffel Compiler, to generate highly efficient executables for Eiffel programs. Most of these techniques --- related to global analysis or not --- may also be applied to other object-oriented languages.
[o] 1998, ACM SIGPLAN International Symposium on Memory Management (ISMM'98), Vancouver, BC, Canada, October 17-19, 1998, pages 154-165.
Compiler Support to Customize the Mark and Sweep Algorithm.
Dominique Colnet, Philippe Coucaud, Olivier Zendra.
Abstract: Mark and sweep garbage collectors (GC) are classical but still very efficient automatic memory management systems. Although challenged by other kinds of systems, such as copying collectors, mark and sweep collectors remain among the best in terms of performance.
This paper describes our implementation of an efficient mark and sweep garbage collector tailored to each program. Compiler support provides the type information required to statically and automatically generate this customized garbage collector. The segregation of objects by type allows the production of a more efficient GC code. This technique, implemented in SmallEiffel, our compiler for the object-oriented language Eiffel, is applicable to other languages and other garbage collection algorithms, be they distributed or not.
We present the results obtained on programs featuring a variety of programming styles and compare our results to a well-know and high quality garbage collector.
[o] 1997, 12th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'97), Volume 32, Issue 10 - Atlanta, GA, USA, pages 125-141, October 1997.
Efficient Dynamic Dispatch without Virtual Function Tables. The SmallEiffel Compiler.
Olivier Zendra, Dominique Colnet, Suzanne Collin.
Abstract: SmallEiffel is an Eiffel compiler which uses a fast simple inference mechanism to remove most last binding calls, replacing them by static bindings. Starting from the system's entry point, it compiles only statically living code, which saves compiling and then removing dead code. As the whole system is analyzed at compile time, multiple inheritance and genericity do not cause any overhead.
SmallEiffel features a coding scheme which eliminates the need for virtual function tables. Dynamic dispatch is implemented without any array access but uses a simple static binary branch code. We show that this implementation makes it possible to use modern hardware very efficiently. It also allows to inline more calls even when dynamic dispatch is required. Some more dispatch sites are removed after the type inference algorithm has been performed, if the different branches of a dispatch site lead to the same code.
The advantage of this approach is that it greatly speeds up execution time and considerably decreases the amount of generated code.
[o] 1997, Joint Modular Languages Conference 1997 (JMLC'97), Volume 1204 of Lecture Notes in Computer Sciences, pages 67-81.
Type Inference for Late Binding. The SmallEiffel Compiler
Suzanne Collin, Dominique Colnet, Olivier Zendra.
Abstract: The SmallEiffel compiler uses a simple type inference mechanism to translate Eiffel source code to C code. The most important aspect in our technique is that many occurrences of late binding are replaced by static binding. Moreover, when dynamic dispatch cannot be removed, inlining is still possible. The advantage of this approach is that is speeds up execution time and decreases considerably the amount of generated code. SmallEiffel compiler source code itself is a large scale benchmark used to show the quality of our results. Obviously, this efficient technique can also be used for class-based languages without dynamic class creation: for example, it is possible for C++ or Java and not possible for Smalltalk.
[o] 1994, International Journal of Pattern Recognition and Artificial Intelligence (IJPRAI), October 1994, Volume 8 Number 5, pages 1131-1148.
Syntactic Analysis of Technical Drawing Dimensions
Suzanne Collin, Dominique Colnet.
Abstract: The transfer of technical drawings from paper to CAD software data-bases and the construction of a 3D model of an object from several 2D views drawn on a draft, are topical problems. There are several different types of data in an industrial drawing, such as graphics, nomenclature and dimensioning. Dimensioning gives the measurement of the parts with more precision than direct scale measurements on the drawing. This article deals with the problem of dimension extraction and interpretation.
We present a syntactic approach to technical drawing dimensions analysis. A specific grammar is used to describe dimensions of drawings. This grammar can be graphically designed by combining different graphic primitives. The algorithm used for analysis can start at different points of the grammar. The analysis proceeds bottom-up and top-down according to previously obtained results.