Malo Revel
email: malo.revel@irisa.fr

Aurélien Lamercerie
email: aurelien.lamercerie@tetras-libre.fr

Annie Foret
email: annie.foret@irisa.fr

Zoltan Miklos
email: zoltan.miklos@irisa.fr

Extracting ODRL Digital Right Representations from License Texts using AMR

Keywords: Content Extraction, Automated Semantic Analysis, Semantic Graph, AMR, License Rights, ODRL Overall objectives

Licenses of digital resources describe rights and duties for users. If the licenses are expressed in natural language, as it is frequently the case, it is hard to reason and verify the license compatibility to specific uses. We propose an automatic end-to-end workflow for extracting Open Digital Rights Language (ODRL) representations from textual license documents. This process uses AMR semantic representations as an intermediate; it adapts a tool that performs a semantic transduction analysis, using formal rules. This work focuses on deontic modalities expressing the permissions and obligations of the user. We provide a proof of concept and discuss experiments.

Introduction

One may wish to attach a license to a work (e.g. a program, a picture or a dataset) before publishing it on the Web. A license expresses in natural language (NL) the rights and duties that the users of the work must comply with. However, although some licenses such as the licenses provided by Creative Commons 1 are also available in a machine readable format, most licenses are only provided as human readable texts, which are written in NL. Machine readable licenses enable a much easier automatic extraction of the rights expressed by the licenses, which is useful for tasks such as license synthesis [START_REF] Havur | Automatic license compatibility checking[END_REF], or compatibility and compliance inference [START_REF] Moreau | Modelling the compatibility of licenses[END_REF], [START_REF] Havur | Automatic license compatibility checking[END_REF]. Performing such tasks using only NL license texts would be much more arduous and ambiguous. most are sentences that describe the permissions and obligations of the user. Such sentences typically contain a modal verb such as "may" or "must", and an action that is an object of this modal verb, such as "distribute" or "give credit". Additionally, the action of the sentence refers to a subject (e.g. the user) and a target (e.g. the work offered under the terms of the license). These parts of information all correspond to specific ODRL classes. For instance, in the sentence "You may reproduce the Work", the modal verb "may" expresses a permission, and controls the action "reproduce". The whole sentence means that the action of reproduction appears among the user's permissions.

Thus, our approach aims to extract ODRL representations for specific content, with a focus on deontic modalities expressing authorized actions and unauthorized ones. Minimizing errors in a fully automated workflow is also an important issue. Contribution. Our main contribution is the proposal of an automatic end-to-end workflow for extracting ODRL representations from textual license documents. This process integrates a pre-existing analysis tool [START_REF] Lamercerie | Construction d'ontologies à partir de textes : démonstration d'une approche basée sur l'analyse de graphes amr[END_REF], implementing the principles of semantic transduction analysis [START_REF] Lamercerie | Principe de transduction sémantique pour l'application de théories d'interfaces sur des documents de spécification[END_REF]. This tool automatically produces ontologies from semantic graphs, using formal rules. We adapted it by developing specific rules to deal with deontic modalities and to capture specific semantic content corresponding to the target representation. In addition, an ODRL graph generation step has been added to the workflow.

At this stage, we propose a proof of concept evaluated on a dataset composed of a hundred typical sentences with a moderate complexity. Our experimentation, which is intended to be preliminary, was notably oriented by following ODRL implementation best practices presented in the report [START_REF]ODRL Implementation Best Practices[END_REF].

Related works are explored in Section 2, while Section 3 introduces the notions and knowledge on which we rely in this paper. The workflow and the implemented methodology are detailed in Section 4. The experimentation carried out is finally presented in Section 5.

Related Works

Analyzing licenses written in NL to produce RDF graphs is quite a specific task that has not been extensively addressed yet. A state of the art for this task is provided by Cabrio et al. [START_REF] Cabrio | These are your rights -a natural language processing approach to automated rdf licenses generation[END_REF], whose goal is similar to ours, but whose method differs from ours.

In order to extract RDF specifications from NL texts, Cabrio et al. [START_REF] Cabrio | These are your rights -a natural language processing approach to automated rdf licenses generation[END_REF] first pre-process the input license by tokenizing, lemmatizing and processing the Parts of Speech of the text, then use classifiers based on Support Vector Machines (SVM) to generate a CC REL [START_REF]W3C Member Submission, ccREL: The Creative Commons Rights Expression Language[END_REF] or an ODRL [START_REF]W3C Recommendation[END_REF] graph. CC REL and ODRL are two Resource Description Framework (RDF) vocabularies dedicated to digital rights specification, and particularly license specification. Cabrio et al. [START_REF] Cabrio | These are your rights -a natural language processing approach to automated rdf licenses generation[END_REF] evaluated their system on a dataset of 37 licenses that they annotated in RDF. The classifiers achieved an overall precision of approximately 0.77 and a recall of 0.43, varying depending on the classified action.

These results are not totally satisfying and show that the framework of Cabrio et al. [START_REF] Cabrio | These are your rights -a natural language processing approach to automated rdf licenses generation[END_REF] must be considered as a first step towards automatic NL license analysis rather than a definitive solution. This article [START_REF] Cabrio | These are your rights -a natural language processing approach to automated rdf licenses generation[END_REF] shows that tackling this challenge with the use of SVM is not trivial, and we hope our approach will obtain better results.

Havur et al. [START_REF] Havur | Automatic license compatibility checking[END_REF] present DALICC, which is both a license library that indexes several license texts along with their ODRL representations, and a system to reason on these RDF graphs and for instance compose customized licenses. Moreau et al. [START_REF] Moreau | Modelling the compatibility of licenses[END_REF] propose CaLi, a model that compares and partially orders licenses based on compatibility and compliance relations between the licenses. To do so CaLi arranges formal representations of licenses based on ODRL in lattices over which CaLi reasons. Vu et al. [START_REF] Vu | Abstract meaning representation for legal documents: An empirical research on a human-annotated dataset[END_REF] introduce JCivilCode, an AMR dataset that is specific to legal texts, and they evaluate several AMR parsers with this dataset.

Background Knowledge

Semantic Representations, AMR

Semantic parsing is an active area of research, involving several annotation languages or formats to represent semantic information [START_REF] Abend | The state of the art in semantic representation[END_REF]. In this study we use Abstract Meaning Representation (AMR) introduced by [START_REF] Langkilde | Generation that exploits corpus-based statistical knowledge[END_REF], in the form proposed by [START_REF] Banarescu | Abstract Meaning Representation for sembanking[END_REF].

AMR is a readable expressive form of graph-based semantic representation at the sentence level, for which datasets and (semantic) parsing tools have been developped [START_REF] May | SemEval-2017 task 9: Abstract Meaning Representation parsing and generation[END_REF]. This scheme abstracts away from syntax, as a single AMR may correspond to several sentences (paraphrases). AMR relies heavily on the PropBank2 semantic roles inventory that is verb-oriented.

Basic AMR and example. We consider an AMR in figure 1 for sentence (1) "You may distribute the work". Every AMR has a unique root. It has variables (p, etc.), events and concepts (such as permit-01, determine-01) and roles (such as ARG0, ARG1) that label the edges. In a node, a slash indicates that the variable on the left denotes an instance of the concept on the right. The edge relations follow verb frame descriptions in PropBank, in the case of "determine-01" : ARG0 denotes "distributor", ARG1 denotes "thing distributed". AMR as an intermediate format. Our hypothesis here is that for texts in the domain of digital licenses, AMR forms are good intermediate representations, from which we can derive the deontic information to be expressed in languages such as ODRL (The Open Digital Rights Language). Obvioulsy at a practical level, a given AMR parser may output errors (a wrong AMR). But importantly, at the level of format and guidelines, the way AMR highlights verbs (with their arguments) and the way AMR expresses and attach modals and negation seems appropriate to extract ODRL-like information. While some general limitations have been noted: AMR does not explicitly deal with universal quantification, and has no tense (future, etc.), we think this should not create problems for the task and texts considered in this study.

Targeted ontology

ODRL The target representation of our analysis is the Open Digital Rights Language (ODRL). ODRL is an RDF vocabulary dedicated to the representation of statements describing rights and duties, and license texts are made of statements of this kind. An ODRL Policy is composed of one or many Rules, which are either a Permission (what one may do), a Duty (what one must do) or a Prohibition (what one is prohibited to do). These rules are linked to one or many Action which describe the terms of use of an Asset -e.g. software or pictures.

For instance, figure 2 shows an ODRL graph (serialized in Turtle syntax) that expresses the information contained in the sentence (1) "You may distribute the Work" (where "You" and "the Work" are terms that are defined within the license text) : ODRL actions come from the ODRL main namespace or from other ontologies such as The Creative Commons Rights Expression Language (CCREL), as in the previous example. CCREL is a RDF vocabulary created by Creative Commons and is meant to represent license text information. CCREL is more limited than ODRL.

Methodology

Our methodology defines a global processing workflow, starting from the NL license sentences to extract the necessary information for the construction of their ODRL representations. This workflow is composed of several steps (figure 3): (1) document splitting and selection of key sentences, (2) conversion of NL statements into semantic representations (AMR graph), (3) RDF serialization of the resulting representations, (4) transduction parsing to extract the semantic content, and (5) generation of the ODRL representations.

Text Data Preparation / Segment Selection

The first step of our workflow is the document preprocessing. It aims at highlighting different sets of sentences from the whole license document, and to select in particular the sentences that correspond to definitions of terminology or expressions of legal rules. Indeed the only sentences that we want to consider are the ones that describe rights and duties. The first approach would be to consider all the sentences and only keep at the end the ones that describe rights and duties, but this method may result in performance issues, since the semantic parsing takes quite a long time to process. Another approach would be to do a first preprocessing step before the semantic parsing, which filters out some "useless" sentences. This way less sentences are to be parsed, and the remaining "useless" sentences can be ignored in a later step of the analysis.

Moreover, most license texts contain a section (usually the first section of the document) that defines some terms used in the text. Here is an example of a definition of "You" (from [START_REF]Attribution-NonCommercial 4.0 International Public License[END_REF]) : "You means the individual or entity exercising the Licensed Rights under this Public License. Your has a corresponding meaning. ". Being able to automatically recognize this section and analyze its definitions would make the extraction of the deontic sentences easier and less ambiguous, because the deontic sentences make use of the defined words. This preprocessing step is currently purely hypothetic: so far the only computation done on a text before the semantic parsing step is the sentence splitting. As a consequence, in this article we only consider isolated sentences that express rights or duties.

Semantic Graph Construction

The second phase is the NL sentence parsing to construct the corresponding AMR graphs. This step is done by amrBatch 4 , which makes use of two modules:

• AMRLib5 is a module that among others parses NL sentences to create AMR graphs. This parser may rely on different pretrained models, and we chose the parse_xfm_bart_large model, which reached a SMATCH score of 83.7 in 2022. • AMR-LD6 is a utilitary module that is used by AMRBatch to convert AMR graphs from the PEN-MAN format provided by AMRLib into an AMR graph. This RDF version of the AMR is a direct translation, and is still far from the ODRL graph that we aim to reach.

Once the AMR graph is computed, the next step of our method is to extract its patterns that correspond to the ODRL features that we want to produce.

Strategies on Semantic Graph Patterns

Semantic Transduction Analysis aims at extracting the semantic content to generate the desired representations. This approach, similar to graph transformation techniques, was initiated in the thesis of A. Lamercerie [START_REF] Lamercerie | Principe de transduction sémantique pour l'application de théories d'interfaces sur des documents de spécification[END_REF]. We take up here the general idea, which we have adapted to an application on licenses in order to extract elements of digital rights. The notion of Semantic Net is introduced to support its implementation. A semantic net is an abstract object that covers graph nodes. It is a way to "capture" a meaning interpretation of nodes in relation. Each net can be typed and associated with different useful semantic data. For example figure 4 shows the nets A and B, which allow to capture respectively a modality and a property.

Transduction Mechanics defines the methodology used to direct the analysis. It aims to bring out semantic nets until one or more nets containing all the data needed to generate the expected ODRL statements are obtained. For its implementation, we define a set of net types, possibly structured as in figure 5. Using this typing, it becomes possible to check if a net has a given type with a simple formula as classNet(x). Similarly, two nets can be related, and we can check this using a formula as arg1(x, y). We can thus check if one or more nets By linking such a formula to a constructive method, a mechanism makes possible to generate new nets. These rules are called transduction rules, and can be structured using a schema, introducing recursion if necessary.

Figure 5: Semantic Net Typing

The Analysis Procedure is initialized by analyzing each node of a graph, and by associating an atomic net (a net that covers a single node) to it. The rest of the procedure consists in the analysis of the generated nets, and in the application of different rules permitting to build new nets by composition of different nets. The analysis of the nets A and B of the example of the previous figure (figure 4) reveals the existence of an action (corresponding to the property associated to B). A new net is created, E on the figure 6, covering the node associated with B, and extended by analyzing the relations starting from B (arg0 which points to C, and arg1 which points to D). Finally, A can be combined with this new net to produce another net, covering all the nodes and highlighting the existence of a digital rights rule.

The implementation uses composition rules as described in [START_REF] Lamercerie | Principe de transduction sémantique pour l'application de théories d'interfaces sur des documents de spécification[END_REF] or [START_REF] Lamercerie | Construction d'ontologies à partir de textes : démonstration d'une approche basée sur l'analyse de graphes amr[END_REF]. For this work on license rights, rules have been revised or specifically developed. These Finally, the last step exploits the result of the semantic transduction analysis to generate the expected ODRL representations.

Hypotheses on sentence structures

The sentences that we analyze are expected to follow a certain structure, which corresponds to the semantic graph patterns that are recognized by TENET 7 . This structure is also determined by the ODRL ontology classes and properties. Here are the features that we expect to encounter in sentences that express digital rights.

Modalities Three different deontic operators may appear: permission, obligation and prohibition. The simplest way to express these operators in NL is through the usage of "may" (which is usually translated to the AMR concept permit-01) and "must" (translated to obligation-01), although deontic modality can be expressed through much more complex structures in license texts (e.g. "the Licensor hereby grants You a worldwide, royalty-free, non-sublicensable, non-exclusive, irrevocable license to exercize the Licensed Rights in the Licensed Material to" 8 expresses a permission). In addition, negation can be applied to the operator, which changes its meaning. For instance "You are not prohibited to <ac-tion>" expresses a permission, while "You are prohibited not to <action>" expresses an obligation.

Entities Some entities can appear in the sentence, and can be actors (odrl:assignee) or targets (odrl:target) of the action. The main entities are often defined in the definitions section of the text, and they often start with a capital letter. 7 https://gitlab.tetras-libre.fr/tetras-mars/tenet 8 https://creativecommons.org/licenses/by-nc/4.0/legalcode Actions The actions are the most difficult features to recognize in a sentence, because there are a lot of different actions, and actions may be composed of a lot of AMR concept nodes that are not necessarily close together in the graph. Moreover, some actions have very similar meanings and are hard to differentiate in the AMR and even in the NL sentence. For instance [START_REF] Cabrio | These are your rights -a natural language processing approach to automated rdf licenses generation[END_REF], cc:shareAlike is textually described as "Redistributions must reproduce the above copyright notice" and Duty:attachPolicy as "Redistributions must retain the copyright notice".

Coordinating conjunctions Additionally, a single sentence can express a lot of information (for instance several actions) through coordinating conjunctions.

Aditionnal contraints Finally, elements of the sentence can be nuanced by additional constraints. For example, the assignee may be permitted to do an action only within a certain time interval or a certain country.

Example Here we study a simple sentence that follows the hypotheses above and we show its AMR and ODRL graph. The sentence (3) is the following: "You may not reproduce the Work". In this sentence, the modality is a prohibition, the assignee is "You", the target is "the Work" and the action is "reproduce".

Here is an AMR translation for this sentence (in PEN-MAN notation):

Sources of error

One important source of error for the whole system is the lack of precision of AMRLib parsing tool for some sentences that we consider. For instance, let us consider the previous sentence (3) again: "You may not reproduce the Work".

The AMR described above is manually annotated, and the AMR generated by AMRLib tool with this sentence as input is actually quite different: Appart from some concepts having changed, the real issue here is the fact that the negation is misplaced in the AMR. This AMR means "You are authorized not to reproduce the work": the negation is placed on the action, which changes the meaning of the modality.

This remark does not point to a weakness of the AMR format but a weakness of some current parsers, that we hope will improve in the future.

Preliminary Experiments

The goal of preliminary experiments is not yet to compete with state-of-the-art methods, but to obtain a proof of concept and to illustrate it. So it was chosen to work with fairly simple sentences at first.

Dataset

Our dataset is made of a hundred simple sentences expressing deontic policies, inspired by ODRL best practices examples [START_REF]ODRL Implementation Best Practices[END_REF]. About 20% of these sentences have been manually crafted in order to convey diverse and interesting linguistic phenomena. The other are automatically crafted using a simple grammar. These sentences must contain a modality (which may be negated), one or several actions that may be expressed in several ways. Actions can be simple or composite, and associated with one or two targets and an assignment. Moreover, 10 additional negative entries are added to the dataset. These 10 sentences are grammatically correct but do not express any deontic policy, and should not be recognized as deontic policies by our system. Indeed, many license text sentences are not relevant for the ODRL extraction and may be ignored during the analysis.

Evaluating experiments

The performance of our system was studied with the dataset described previously. The results are given by the figure 7. Precision (P) and recall (R) were evaluated for the modality and action extraction task. This dataset is used to show that our approach can work on simple cases. In this context, classification of modalities is decent but not excellent, partly since some negated modalities are incorrectly parsed by AMRLib. However, we have a very good precision and recall on the action classification. A classic F-score evaluation was chosen, because we were primarily interested in evaluating the system's ability to extract the expected semantic content. The results obtained confirm the direction followed. That said, our workflow also covers a formalization task, which it would be more relevant to evaluate with a semantic structure evaluation metric such as Smatch [START_REF] Cai | Smatch: an evaluation metric for semantic feature structures[END_REF]. This measure will be particularly interesting to refine our evaluations in future work. The goal remains the processing of real documents, with complex sentences. Additional experimentation is therefore targeted on broader data, such as the dataset of Cabrio et al [START_REF] Cabrio | These are your rights -a natural language processing approach to automated rdf licenses generation[END_REF].

Modalities

Conclusion

In this paper, we present a first step towards a workflow that automatically extracts ODRL representations from natural text licenses, with AMR as an intermediate representation. A formal representation of the rights could enable to automatically verify the licence compability in specific situations. Our first experiment provided a proof of concept, with sufficient results on a simple dataset. In particular, we obtained good performance figures for the extraction of modalities, which express permissions, requirements and prohibitions, and actions, which are what the user can, must or is forbidden to do. Some linguistic phenomena are taken into account, such as negations and coordinating conjunctions. Another outcome of the process is that it provides an indirect evaluation of AMR parsers.

Thus, although our full system is far from being complete, our method is achieving encouraging results so far and we plan to continue working on it. First, the effective implementation of a pre-processing phase (Figure 3) would improve runtime performance and help recognize entities and actions. Also, our rule system is still incomplete and more AMR patterns need to be covered. Some evolutions and alternatives can also be considered, such as the use of another pivot representation as an alternative of AMR or as a complementary information.

Figure 1 :

 1 Figure 1: AMR Graph of sentence (1) "You may distribute the work"

  @ p r e f i x c c : < h t t p : / / c r e a t i v e c o m m o n s . o r g / ns # > . @ p r e f i x o d r l : < h t t p : / / www. w3 . o r g / ns / o d r l / 2 / > . : l i c e n s e a o d r l : P o l i c y ; o d r l : p e r m i s s i o n [ a o d r l : P e r m i s s i o n ; o d r l : t a r g e t " Work " ; o d r l : a s s i g n e e " You " ; o d r l : a c t i o n c c : D i s t r i b u t e ] .

Figure 2 :

 2 Figure 2: ODRL representation of the sentence (1) "You may distribute the Work"

Figure 3 :

 3 Figure 3: Workflow of our method

Figure 4 :

 4 Figure 4: AMR Graph with semantic nets

Figure 6 :

 6 Figure 6: AMR Graph with new semantic nets

  # : : s n t You may n o t r e p r o d u c e t h e Work . ( p / p e r m i t -01 : p o l a r i t y -: ARG1 ( r / r e p r o d u c e -01 : ARG0 ( y / you ) : ARG1 (w / work -1 2 ) ) ) And here is an ODRL translation for this sentence (in TURTLE syntax): @ p r e f i x c c : < h t t p : / / c r e a t i v e c o m m o n s . o r g / ns # > . @ p r e f i x o d r l : < h t t p : / / www. w3 . o r g / ns / o d r l / 2 / > . " L i c e n s e " a o d r l : P o l i c y ; o d r l : p r o h i b i t i o n [ o d r l : t a r g e t " Work " ; o d r l : a s s i g n e e " You " ; o d r l : a c t i o n c c : R e p r o d u c t i o n ] .

  # : : s n t You may n o t r e p r o d u c e t h e Work . ( p / p o s s i b l e -01 : ARG1 ( r / r e p r o d u c e -01 : p o l a r i t y -: ARG0 ( y / you ) : ARG1 (w / work -0 1 ) ) )

Figure 7 :

 7 Figure 7: Precision (P), recall (R) and F-measure (F) of the output of our system on our dataset

see the PropBank sites: https://verbs.colorado.edu/~mpalmer/ projects/ace.html and https://propbank.github.io/

described for exemple here https://penman.readthedocs.io/en/ latest/notation.html

https://gitlab.tetras-libre.fr/tetras-mars/amrbatch

https://pypi.org/project/amrlib/

https://github.com/BMKEG/amr-ld

Acknowledgments

This work was proposed within the CLARA project (https: //project.inria.fr/clara/). We thank the CLARA members and our team colleagues for useful discussions.


Nahuel Palumbo
email: nahuel.palumbo@inria.fr

Sebastian Jordan Montaño
email: sebastian.jordan@inria.fr

Guillermo Polito
email: guillermo.polito@inria.fr

Pablo Tesone
email: pablo.tesone@inria.fr

Stéphane Ducasse
email: stephane.ducasse@inria.fr

Garbage Collector Tuning in Pathological Allocation Pattern Applications

Keywords: garbage collector, memory profiler, memory management, virtual machine, Pharo, Smalltalk

Automatic memory management is often supported by Garbage Collectors (GC). GC usually impacts running application performance. For tuning properly, they expose some parameters to support the adaptation of their algorithms to specific applications' scenarios. In some cases, the developers should modify the GC parameter values to achieve high performance.

However, many application developers cannot be expected to perform expert analysis to determine which parameter values are the best for their application. There are techniques to find "good enough" parameter values. But, even if the overhead was reduced, it is still unknown the cause of the problem and how the GC tuning managed it.

In this paper, we present a methodology to identify the causes of GC overhead in Pharo applications for tuning GC parameters. We describe the GC inside the PharoVM and its parameters, looking at how their variations change the allocation behaviour. We were able to analyse, identify and understand the GC performance issues present in one real application and suggest specific GC tuning actions. Using the suggested parameter values, we improved its performance by up to 12x and reduced GC overhead by up to 3.8x.

During the experiments, we also found: 1) a bug in the production PharoVM concerning the tenuring policy, 2) a misconception about one GC parameter even for the VM developers, and 3) some possible improvements for the current GC implementation.

Introduction

Automatic memory management is often supported by Garbage Collectors (GC) [START_REF] Deutsch | An efficient, incremental garbage collector[END_REF][START_REF] Jones | The garbage collection handbook: the art of automatic memory management[END_REF]. GC deals with different programs that manipulate different data. This data must be allocated in the memory (heap) and accessible when the application uses it. We refer to the allocation pattern as the ways that applications allocate and use their data.

There are different GC strategies to decide where to allocate, keep track and, eventually, free the application data [START_REF] Garner | The design and construction of high performance garbage collectors[END_REF][START_REF] Blackburn | Oil and water? high performance garbage collection in java with mmtk[END_REF][START_REF] Hertz | Quantifying the performance of garbage collection vs. explicit memory management[END_REF]. Garbage Collectors respond to the allocation pattern of running applications for better performance. So, they implement parametric algorithms to adapt their complex behaviour to each specific application [START_REF] Blackburn | Oil and water? high performance garbage collection in java with mmtk[END_REF][START_REF] Jayasena | Auto-tuning the java virtual machine[END_REF][START_REF] Neu | Automatic application performance improvements through VM parameter modification after runtime behavior analysis[END_REF].

There are reports about how garbage collection impacts application performance if not tuned properly [START_REF] Lengauer | The taming of the shrew: Increasing performance by automatic parameter tuning for java garbage collectors[END_REF][START_REF] Vijayakumar | Predicting jvm parameters for performance tuning using different regression algorithms[END_REF]. In the PharoVM [START_REF] Miranda | The cog smalltalk virtual machine[END_REF], GC parameters start with default values and application developers are able to override them from the image. If the GC parameter values respond to the application allocation pattern wrongly, the GC will increase overhead and the application performance will be degraded (see Section 2). In that case, we say that the application presents a pathological allocation pattern (see Section 6). Thus, applications exhibiting allocation patterns unexpected by the GC should modify these parameter values to optimise their performance.

Worst, most application developers do not know how the Pharo GC works or have misconceptions (see Section 4). Even for experts, it is hard to identify the issues between GC and the running application. There are techniques to achieve "good enough" performance based on trial and error of GC parameter values [START_REF] Lengauer | The taming of the shrew: Increasing performance by automatic parameter tuning for java garbage collectors[END_REF]. But, even though the overhead was reduced, the root cause of the issue and how the GC tuning solved it remains unknown in the end [START_REF] Singer | Garbage collection auto-tuning for java mapreduce on multi-cores[END_REF][START_REF] Jayasena | Auto-tuning the java virtual machine[END_REF].

To solve this problem, we propose a methodology to identify the causes of pathological allocation patterns in running applications. Using our modified version of the PharoVM, we log data about each GC execution into a file. By analysing the logs, we are able to understand the application's allocation issues and take better decisions about how to improve performance (see Section 3).

We reduced the time spent in GC by a factor of 3x for all benchmarks of the real application studied in this paper. Our results in Section 6.3 show performance improvements in total execution time up to 12.5x.

The main contributions of this work are:

• A methodology to identify application pathological allocation patterns and tune GC parameters for avoiding them. • A full description of the impact of Pharo GC parameters on the application allocation behaviour. • We also found a bug in the production PharoVM concerning the tenuring policy, which was fixed and integrated into the next version (see Section 5). We found a performance issue in the Data Frame1 open source project. A Data Frame is a data structure to manipulate and analyse large amounts of data. This project is used in real applications, for example in AI-related algorithms.

Motivation

We observed that the execution time grows exponentially related to the amount of data loaded into the Data Frame. We make some benchmarks just by loading data from a file into the DataFrame2 . Table 1 shows the relation between the total execution and GC running time on loading data files with different sizes into a Data Frame3 . For the case of a 3.1 GB data file, the application spends almost 90% of the execution time just garbage collecting. This is a sign of a pathological allocation pattern.

Knowing the GC overhead is useful to identify possible performance issues related to allocations. However, we need more information about how the Garbage Collector interacts with the application to understand the causes of those problems.

Solution

For garbage collecting, the VM analyses the data accessible from some roots and "discards" not accessible data. the GC performs two strategies to analyse if some data is accessible: a Scavenge using a Remembered Set as root, or a FullGC using global fixed roots in the VM. There is a detailed overview of the Pharo Garbage Collector in Section 4.

We modified the VM's code to collect information each time the Garbage Collection is triggered.

From Scavenges, we get:

• Amount of memory used to allocate objects in the Eden (before).

• Total survivor's memory size (before and after).

• Number of objects in the Remembered Set (before and after).

• Amount of tenured data (before and after).

• Tenured threshold (if objects were tenured in the pass).

• Executed time.

And from FullGC:

• Time spent marking.

• Time spent sweeping.

• Time spent compacting.

• Total executed time.

Using our version of the PharoVM, we log all listed data into a file. Then, analysing this file, we identify the causes of application pathological allocation patterns and adapt the set of GC parameters to achieve better performance. Our results show performance improvements in total execution time up to 12.5x for the Data Frame application presented in 2. We reduced the time spent in GC by a factor of 3x for all benchmarks (see Section 6).

In the next section, we introduce the Pharo Garbage Collector and its parameters. Profile data also help to understand how each parameter affects the application allocations.

Background: Pharo Garbage Collector

The PharoVM4 has automatic memory management based on a Generational Garbage Collector [START_REF] Ungar | Generation scavenging: A non-disruptive high performance storage reclamation algorithm[END_REF]. Memory heap is divided into two areas: New Space and Old Space. Each space has a different structure and strategies for allocation and garbage collection. A big picture of this organization is shown in Figure 1.

This design is based on the weak generational hypothesis: most of the objects die young [START_REF] Ungar | Generation scavenging: A non-disruptive high performance storage reclamation algorithm[END_REF][START_REF] Lieberman | A Real Time Garbage Collector Based on the Lifetimes of Objects[END_REF]. So, this kind of GC allocates newly instantiated objects and old ones in different spaces. The New Space will be garbage collected often by a Scavenger and the Old Space occasionally by a FullGC since it is bigger and more expensive to scan. The New Space is divided into 3 sections: the Eden and two semi-spaces. The amount of memory for each maintains always the same proportion of 5 7 for the Eden and 2 7 for the semispaces. The Eden is the place where new objects are allocated and the two semi-spaces keep the survivors. Big enough objects are created directly in the Old Space. This is referenced by 1 in Figure 1. When the amount of memory used in the Eden reaches a threshold, a Scavenge pass is automatically scheduled. The Scavenger performs a copy-collection, copying all survivors to one dedicated semi-space. It is referenced by 2 in Figure 1. All non-copied data will be overridden by new allocations. To know which objects survive, root references should be followed. The roots for the New Space are the references coming from objects in the Old Space. For avoiding to scan all objects in the Old Space looking for roots, there is a Remembered Set with the objects in the Old Space that have any reference to an object in the New Space [START_REF] Ungar | Generation scavenging: A non-disruptive high performance storage reclamation algorithm[END_REF]. This Remembered Set is updated at each store (write barrier), based on the object-allocated spaces.

Pharo Generational Collector Structure

After many passes, the amount of survivor objects could increase and not fit in the survivor's semi-space. Then, some objects are tenured to the Old Space, based on some policy [START_REF] Ungar | Tenuring policies for generation-based storage reclamation[END_REF]. This policy could be based on the object's age, memory location or a specific goal as reducing the number of objects in the Remembered Set. In the current implementation, the Scavenger triggers the tenuring objects when survivors in the semi-space fill the 90%, this value is hardcoded in the GC code. Tenured objects are referenced by 3 in Figure 1.

The Old Space is the memory region where most objects live, being at least 3 times bigger than the New Space. It is organised in segments and incorporates more segments dynamically to have enough free space for the demanded amount of the objects/memory by the application. On the contrary, if the system detects that much of managed memory is free and not being used, it returns the free segments to the OS. This process is referenced by 4 and 5 in Figure 1.

As the Old Space could be very big and expensive to traverse, this space is garbage collected occasionally. The garbage collection in this space is performed by a FullGC. On FullGC, objects in both, New and Old Spaces, are tracked and non-accessible memory is freed.

The system automatically decides when to run the Scavenge or FullGC passes. A Scavenge pass is triggered when the Eden is almost full, to free memory for new allocations. The reasons for triggering FullGC are mainly because the system does not have enough memory in the Old Space to allocate one object. In this case, GC tries to free the required amount of memory before requesting them to the Operating System. Applications can also execute a FullGC programmatically.

Analysis of GC Parameters

There are five parameters in the PharoVM to control the GC behaviour: Desired Eden size, Survivors to keep, Full GC ratio, Grow headroom and Shrink threshold. Next, we will explain each and see their impact on allocations.

Desired Eden size It is the desired memory size for the Eden. This parameter also controls the size of the entire New Space to maintain the proportion of each section. By default, the Eden size is 16MB. A bigger Eden implies that the GC will support more objects between passes. Thus, GC will perform fewer automatic garbage collections. Figure 2 shows the number of garbage collection passes based on Eden size for different applications. The total number of garbage collections (FullGCs and Scavenges) decreases asymptotically while the Eden size grows. The minimum value depends on how many allocations and FullGC are triggered by the application [START_REF] Hertz | Quantifying the performance of garbage collection vs. explicit memory management[END_REF].

Counterintuitively, Figure 2 also shows no clear correlation with the Scavenge time, it also depends on the number of survivors and objects in the Remembered Set (see Section 6.2).

Survivors to keep

This value is an integer with the desired number of survivor objects to keep in the New Space when the Scavenger decides to tenure objects.

The VM estimates the proportion of objects to keep in the semi-space based on an average object size of 64 bytes. Using the estimated memory size, the GC computes a tenuring threshold inside the survivor's semi-space to decide which objects will be tenured to the Old Space (i.e. the objects before the threshold). By default, only 10% of survivors in the semi-space will be tenured.

Figure 3 shows how the total amount of data tenured changes with different values of survivor objects to keep for different allocation patterns. The decision about which objects will be tenured has an impact on applications with different object lifetimes. For example, the application at the bottom of Figure 3 presents a critical value where long lifetime objects keep in the New Space and more data is tenured.

For applications that use enough amount of data for a long time, this threshold does not have a big impact. Most of the objects will be tenured anyway because of the application usage, independently of the tenuring policy. This is the case of the application on top of Figure 3.

As this parameter is a raw quantity, we need to consider the survivors' semi-space size. If the number of objects to keep is big enough to consider all survivors, then GC will not tenure objects from the survivors' semi-space. Instead, it will tenure all new incoming survivors from the Eden directly to the Old Space because there is no more space in the semi-space. The last point for each application in Figure 3 represents that scenario. FullGC ratio This ratio is a threshold for triggering a FullGC when the old space grows more than expected. By default, this value is set at 33%. Thus, when the old space grows 1/3 of its space (from the last FullGC) it will perform a FullGC. Increasing this value will reduce the number of FullGCs automatically performed by the VM. This parameter does not modify the behaviour of the Scavenger.

Figure 4 shows how the number of FullGC decreases by a bigger FullGC ratio value. This effect was only observable in applications with intensive use of memory, i.e. many allocated objects that finish in the old space.

Grow headroom

The grow headroom is the minimum amount of memory that the GC will order from the OS. It is used when the system detects that there is not sufficient space in the Old Space, so it will be expanded. The value is 16MB by default.

This parameter is important to avoid requesting many small chunks of memory from the OS. If the Old Space is filled and new small objects need to be allocated there, the space should grow with sufficient memory for many of them for better performance. Thus, the value for this parameter should be relative to the average size of the new allocations for avoiding unnecessaries FullGC. On the other hand, if the requested memory is much bigger than the total of newly allocated objects size, it wastes resources with unused memory.

To show this effect, we created an artificial tiny benchmark creating 100 objects of 24MB each. We run it with different headroom values, results are in Figure 5. The first configuration was executed with a headroom of 16MB, less than 24MB, so each object allocation triggered a FullGC. The number of FullGC decreases proportionally to the number of new objects that enter the headroom. In this extreme scenario, the last configuration was 5x faster than the first one. Shrink threshold This threshold determines the maximum amount of free memory (without objects) in the Old Space that the GC will manage before trying to get it back to the OS. In that case, it will return to the OS all chunks of free memory until the amount of free memory is close to the Grow headroom, introduced before. By default, the value of this parameter is 32MB.

In our experiments, we did not see any observable effect based on this parameter, maybe because we did not find the best application allocation pattern for it. We may need more integral profiling techniques for the analysis of this parameter.

Bug in the Scanvenge's tenuring policy

We observed a bug in the tenuring objects policy during the profiling sessions. The tenuring threshold value was computed outside the current survivors' semi-space for all cases where the GC should tenure objects from the New to the Old Space. It makes no sense since this threshold should divide the survivor objects that will and will not be tenured, so it will be at some part inside the current survivors' semi-space.

Checking the code, we found that the threshold was mistakenly computed in the wrong semi-space. So, any time that the scavenger wants to tenure objects, it was tenuring either none or all survivors, depending on the position of the semi-spaces in the memory.

We fixed it to compute the value in the correct semi-space. Figure 6 shows the amount of data that survives in the semi-space on each Scavenge before and after the fix respectively. Marked dots represent the value of the tenuring thresholds. The horizontal dotted line is the limit of the semi-space. Black lines are the survivor data amount in the semi-space, dots represent the tenuring threshold when the Scavenger decides to tenure (pointed by arrows and circles) and the red horizontal dotted line is the limit of the semi-space. At the left, the threshold is set outside the current semi-space, so all objects are tenured. At the right, the threshold is computing in the correct place, only 128KB of objects are tenured in each Scavenge.

Before the fix, the threshold is outside the semi-space and all survivors are tenured. After the fix, more scavenges perform tenuring but much less amount of data is tenured on each. Summarising them, the total amount of tenured data in this example decreases from 4 to 2.5 MB.

For the rest of the analysis in this paper, we will use the fixed version of the VM. This fix is already integrated into the PharoVM and will be present in the next release.

Case study: pathological allocation patterns

In this section, we will show the analysis of the pathological allocation patterns discovered for the Data Frame application presented in Section 2 based on the profile data collected by our instrumented GC. Our methodology is based on identifying what are the causes of performance issues and suggesting some changes in the GC parameters values for solving them. Then we rerun the benchmarks with the suggested changes to see if the observed problems were solved.

Reducing the number of FullGC passes

Looking at the profile data, the first thing that called our attention was the number of FullGC triggered together. Performing many FullGC together increases overhead because scanning all the Old Space is an expensive task. It is better to wait for some Scavenges before, so the application has more time to use the objects and then the GC has more chances to free their memory. Figure 7 shows the relation between Scavenges and FullGC. Analysing the first chart in Figure 7 we observed two patterns of FullGC: during data loading (before point P), FullGC are triggered periodically in time; and during Data Frame building (after point P), FullGC are triggered together.

The first group is due to the loaded data being tenured to the Old Space, growing it and triggering the FullGC ratio, as we introduced in Section 4.2. In this case, the application is loading a lot of non-temporary data, so the FullGC will not free memory. We should adapt the FullGC ratio relative to the amount of loaded data to avoid most of them.

The number of FullGC triggered together is due to the size of the Data Frame structures. They are big enough for being allocated directly in the Old Space. If the Old Space does not have enough free memory, FullGC is triggered as explained in Section 4.2. To avoid this anomaly, we need to set a Grow Headroom according to the expected Data Frame size.

So, we customised the FullGC ratio to a very big value, simulating an infinite ratio, and the Grow headroom to the same as the loaded file, depending on the benchmark. We ran the benchmarks again to compare performance and continue the analysis. These GC parameter values reduced the number of FullGC from 36 to only 1 time and increased the application performance between 1% and 5%.

Reducing Scavenge time

Analysing the newly profiled data, we saw a big increase in the time of Scavenges when the Data Frame is being built. Scavenges are 52x slower now! This increment in Scavenge time starts when the Data Frame is created and persists until the end of the benchmark, as we can observe in Figure 8, representing 25% of the running application time. This pathological scenario is due to a big object inside the Remembered Set, probably the Data Frame structure. To know which objects survive in each scavenge, all references from every object in the Remembered Set should be scanned. If an object with so many references arrives in the Remember Set, it could take a long time to scan it. Looking at the number of objects in the Remembered Set in each scavenge, we know that only one (or a very small group of objects) are the cause of this behaviour.

We should avoid spending so much time scanning objects on each Scavenge because it is very frequent. But, as there is no way to control the objects in the Remembered Set, it is not an easy task. We tried with different values for the tenuring threshold introduced in Section 4.2 to control which survivor objects in the New Space are tenured to the Old Space. None of the possible values could avoid this situation, since the pointed new objects are continually created and the big object always stays in the Remembered Set.

The solution that we found for this issue was to configure the tenuring threshold value to keep all survivors in the semi-space. Then, after the survivor's semi-space fills up, all new survivor objects will be automatically tenured from the Eden. Using this strategy, all survivor objects created at the end of the benchmark will live together in the Old Space. Thus, we avoid having big objects in the Remembered Set for almost all Scavenges.

Final configuration and Results

Given the previous observations, we tuned GC parameters to:

1) Have an infinite FullGC ratio

To reduce the number of FullGC when the Old Space grows.

2) Have a grow headroom equal to the loaded file To avoid many FullGC together.

3) Keep all survivors in the semi-space To tenure new objects to the Old Space quickly. We improved the time spent in GC for the Data Frame application benchmarks presented in Section 2 by a factor bigger than 3x, as we show in Table 2.

Take aways

Learnings about this experience are:

• It is possible to tune the GC parameters for a specific application based on the methodology presented in this paper. • Using profile techniques on running applications we were able to identify pathological allocation patterns. • We understood how variations in the GC parameters are related to the application pattern allocations. It is important to have a good overview of the GC algorithm to understand what the effect of changing each parameter is. • Mixing the items above, we have a set of tools to analyse the interactions between applications and VM garbage collection. We are able to make better decisions about tuning applications for performance improvements.

Related work

The work presented in this paper is a continuation of previous work [START_REF] Tesone | Profiling Code Cache Behaviour via Events[END_REF]. Even if we did not use Vicoca, the tool presented in that paper, we reuse part of the infrastructure developed on top of the Pharo VM. While previous work aims to identify Code Cache issues, in this work we use profiling via GC events to identify allocation issues. Both approaches are similar: profiling VM events to analyse specific applications' behaviour and, eventually, tune VM parameters to achieve better performance. Kaleba et al., [START_REF] Kaleba | A detailed vm profiler for the cog vm[END_REF] have extended an existing VMProfiler for the same VM as us. They were interested in profiling the generated machine code to improve the JIT compiler, different to our goal of GC tuning for applications.

There are many works exploring techniques to find an optimal set of GC parameter values for a specific application [START_REF] Lengauer | The taming of the shrew: Increasing performance by automatic parameter tuning for java garbage collectors[END_REF][START_REF] Vijayakumar | Predicting jvm parameters for performance tuning using different regression algorithms[END_REF][START_REF] Singer | Intelligent selection of application-specific garbage collectors[END_REF]. They present the problem of having too many parameters for tuning, so they use machine learning and hill-climber algorithms to find good values. Our approach is based on analysis and understanding the application allocation patterns for consciously tuning GC parameters. They also agree about the importance of tuning GC parameters to improve applications' performance.

The master thesis of Neu is the most similar to our work [START_REF] Neu | Automatic application performance improvements through VM parameter modification after runtime behavior analysis[END_REF]. He describes the parameters in the OpenJ9 Java VM showing the impact of each on applications performance, similar to us. His work also uses profile techniques to log VM information and a tool to analyse it later, such as ours. Both approaches intend to help users to get information about their running applications' behaviour and be able to manually tune GC parameters.

VM profiling techniques are commonly used in auto-tuning research [START_REF] Jayasena | Auto-tuning the java virtual machine[END_REF][START_REF] Singer | Garbage collection auto-tuning for java mapreduce on multi-cores[END_REF]. We agree about the difficulty of tuning GC parameters for user developers. To solve this problem, they propose a VM implementation which tunes itself online to improve the predictions about application behaviour. Instead, we prefer to build tools that users can use to learn about its applications and take the decision about the best way to improve its performance.

Finally, Ungar and Jackson already suggest a low effectiveness of a "simple two-generation scavenger" in programs that hang onto large amounts of temporary data for extended periods of time [? ]. This is exactly the main cause of our pathological case study. Next years after that, some researchers proposed solutions to this problem thru pretenuring [START_REF] Cheng | Generational stack collection and profile-driven pretenuring[END_REF][START_REF] Harris | Dynamic adaptive pre-tenuring[END_REF][START_REF] Jump | Dynamic object sampling for pretenuring[END_REF][START_REF] Buytaert | Garbage collection hints[END_REF]. They use profiling techniques and sampling to predict allocations of objects with long lifetimes.

Future work 8.1. Available for the community

Our next goal is that Pharo developers can profile the Garbage Collector on their applications and adapt its parameters if needed. For that, we need to integrate the work done in the PharoVM to be able to profile Garbage Collection passes and an API for users 5 . We also want to publish an application with tools for analysing and visualising the profiled data [START_REF] Araya | Agile visualization with Roassal[END_REF]. Using that tool and the methodology presented in this paper, developers will be able to adapt the Garbage Collector behaviour to their applications' specific allocation patterns.

Change GC parameters

We also have two suggestions to improve the API for the current GC parameters:

1. Change the Survivors to keep parameter for a Tenuring proportion. This parameter confuses even for VM developers, we saw erroneous comments in the GC code. The new suggested parameter will directly represent the percentage of survivor data to tenure when New Space is full.

2. Add a new parameter to manage the Tenuring criterion. Now the Scavenge have different criteria for tenuring objects. In this paper, we just presented the tenuring by age, because is the normal criterion. Using this parameter, we could set a criterion for reducing the Remembered Set, for example.

Improve GC in PharoVM

We are also excited to improve the Pharo Garbage Collector implementation to automatically avoid some of the pathological scenarios seen in Section 6.

First, we want to avoid big objects in the Remembered Set. Since the design of a Generation Garbage Collector is based on fast Scavenges, avoiding scanning big objects on each pass could improve its performance.

Another idea is to have a pretenuring strategy for long-life objects. We have an idea to identify these objects based on the allocation site (the method where the object is instantiated).

Continue profiling

Continuing this work, we want to increase the data collected by the profiling sessions to be able to make better analyses. During the experiments, some data about FullGC was missing for a better understanding of the passes. Cause of the pass, survived data size, free chucks, and segments information are some examples. With more information, we will be able to understand the application allocation patterns better and, for example, find better examples for each GC parameter change.

Conclusions

In this paper, we presented a methodology to identify the causes of performance issues with the Pharo Garbage Collector (GC) for running applications. It is based on profile data collected each time that the GC is executed. Using the profile data, we described the GC used by the PharoVM and its parameters. We showed how each parameter affects the underlined behaviour of the GC.

We introduced a real application scenario presenting performance issues with the GC. Then, we were able to identify the causes of these pathological allocation patterns. Using our methodology, we were able to tune the GC parameter values for the specific application allocation pattern. Our results showed performance improvements up to 12.5x in execution time and reduced the GC overhead by up to 3.8x, for the analysed benchmark.

This work highlights the importance of tuning GC parameters for specific application behaviour. Our descriptions of the GC and its parameters, the profiling tools and the presented methodology are useful to help developers with this task.

Figure 1 :

 1 Figure 1: Overview of the memory heap structure by the Generational Garbage Collector. There are two sections: New Space and Old Space. We zoomed the New Space to show inner divisions. Blue arrows show the data allocation flow. Red letters and arrows are for references in the paper.

Figure 2 :

 2 Figure 2: Garbage Collector behaviour based on Eden size for different applications. On the left, the number of garbage collection passes decreases asymptotically while the Eden size is bigger. On the right, the amount of time Scavenging is not fully dependent on the Eden size.

Figure 3 :

 3 Figure 3: Total amount of tenured data based on the number of survivor objects to keep in the New Space. Points at the end represent the case where all survivors in the semi-space are kept and only new survivors from the Eden are tenured.

Figure 4 :

 4 Figure 4: Number of FullGC based on Full GC ratio. Higher ratios imply fewer FullGCs automatically triggered.

Figure 5 :

 5 Figure 5: Number of Full GC for different Grow headroom values. The number of Full GC is proportional to the number of new objects that fit the headroom.

Figure 6 :

 6 Figure 6: Bug on computing the tenuring threshold in Scavenger.Black lines are the survivor data amount in the semi-space, dots represent the tenuring threshold when the Scavenger decides to tenure (pointed by arrows and circles) and the red horizontal dotted line is the limit of the semi-space. At the left, the threshold is set outside the current semi-space, so all objects are tenured. At the right, the threshold is computing in the correct place, only 128KB of objects are tenured in each Scavenge.

Figure 7 :

 7 Figure 7: Relation between Scavenges and FullGC in Data Frame benchmarks. In red, the number of FullGC triggered together. In blue, point P is used as a reference between the two different patterns. After the fix, only one FullGC is performed

Figure 8 :

 8 Figure 8: Time of each Scavenge in Data Frame benchmarks. After the red mark, all Scavenge passes at the end have increased their time by more than 52x. After the fix, only one Scavenge has this overhead.

Table 1

 1 Benchmarks for Data Frame application on load data files with different sizes. Garbage collection time increases exponentially related to the loaded data.

	Data size Total time (sec) GC time (sec) GC overhead
	529 MB	43	7	16%
	1.6 GB	150	38	25%
	3.1 GB	5599	5158	92%

Table 2

 2 Results of tuning GC parameters for Data Frame application benchmarks. We fixed the pathological allocation patterns to avoid GC overhead. Parenthesis values show performance improvement.

	Data size	Total secs GC overhead before before	Total secs GC overhead after after
	529 MB	43	16%	37 (1.1x)	5% (3.2x)
	1.6 GB	150	25%	122 (1.2x)	7% (3.6x)
	3.1 GB	5599	92%	440 (12.5x)	24% (3.8x)

https://github.com/PolyMathOrg/DataFrame

Evaluating: DataFrame readFromCsv: pathToFile asFileReference.

Data files used are:• https://www.kaggle.com/datasets/rahulbanerjee123/aws-product-length?resource=download (529 MB and 1.6 GB)• https://www.kaggle.com/datasets/antoninadolgorukova/proteinrna-vs-rna-spearman-correlation-data? select=Prot-RNA_corr_63gr.csv (3.1 GB)

https://github.com/pharo-project/pharo-vm

https://github.com/pharo-project/pharo-vm/pull/606