ANR PLASMA

Working groups in Caen - July 6-8 2026

This meeting brings together members of the ANR PLASMA project. Through small-group workshops, participants will explore topics such as how hash tables work in Python, modeling the Java garbage collector, and the delta algorithm in Mercurial.

The meeting takes place at the Salle du Belvédère, Bâtiment D, Campus 1, à Caen.

Schedule

See the lunch menus.

Confirmed participants

1. CHAU Minh (Marne)
2. CLÉMENT Julien (Caen)
3. COURTIEL Julien (Caen)
4. DAVID Julien (Caen)
5. DIEN Matthieu (Caen)
6. FANG Wenjie (Marne)
7. FORAX Rémi (Marne)
8. GARCIA Emmy (Caen)
9. KOECHLIN Florent (Villetaneuse, special guest!)
10. MARTINEZ Conrado (Barcelone)
11. NICAUD Cyril (Marne)
12. PÉPIN Martin (Caen)
13. PIVOTEAU Carine (Marne)
14. ROTONDO Pablo (Marne)
15. ROUSSEL Matthieu (Marne)
16. VALLÉE Brigitte (Caen)

Open questions

Question 1. Hashtables for data under Zipf law (Cyril)

The classical theoretical setting for analyzing the efficiency combines two levels of randomness:

• Internal: the hash function is modeled as mapping every key to a uniform random index in the table.
• External: when analyzing the cost of a successful search, the element queried is taken uniformly at random amongst all keys already in the table.

The first one is somehow unavoidable to make computations. However, the second one can be naturally questioned. Consider the problem of parsing a text in English and counting the number of occurrences of each word using a hashtable H. For each word in the text, one has to check whether it is already in the table, in which case 1 is added to the associated value H[x]; otherwise, we set H[x]=1. Obviously, words in a (large) English text have different frequencies, and the "uniform model" is not relevant in this case.

The idea here is to use Zipf-Mandelbrot laws for the data:

Problem: revisit classical theoretical results on hashtables, when data arrive according to a Zipf-Mandelbrot law.

Question 2. Pythonic probing (Conrado)

Analyze this variant of linear probing in which after B unsuccessful probes a second hash is used to jump to the next slot ("à la random probing"). Check the recent results of Alharbi, Banderier et al. (AofA 2026) on bounded linear probing. Merge with working group 2.1?

Question 3. Triggering criteria for Garbage Collectors (Julien Co.)

Real-world programs exhibit complex patterns of memory allocations and deallocations. To understand and analyze the behavior of garbage collectors (GCs), we need to model how memory is requested and freed. Execution traces collected from actual programs provide empirical data on these patterns. However, it seems that different programming languages employ different criteria to decide when to trigger garbage collection:

• Python uses a fixed counter-based rule: GC triggers when number of allocations - number of deallocations ≥ 720.
• Java employs some heuristics which Rémi vaguely told us about in the previous workshop.
• I have no idea what other languages use.

Central question: Are these different triggering criteria equivalent in their behavior? Can we find realistic allocation/deallocation patterns that expose weaknesses in specific criteria?

Problems:

1. Characterize the triggering policies in different GC implementations (Python, Java, and others). What exactly decides when collection occurs?
2. Develop probabilistic models of allocation/deallocation patterns, based on the execution traces from Julien Co. and Julien D.'s dumps.
3. Analyze the consistency of different triggering criteria under realistic allocation patterns: do they trigger at comparable frequency?
4. Search for pathological scenarios: can we construct allocation/deallocation sequences where one criterion performs significantly worse than another?
5. Propose alternatives for understanding robust triggering policies.

Question 4. Regression Search Problem in Version Control Systems

Version control systems like Git represent the history of a software project as a directed acyclic graph (DAG), where each node is a commit and edges represent parent-child relationships. A critical problem is the Regression Search Problem: given that a bug was introduced somewhere in the commit graph, how do we efficiently identify the commit responsible? The standard approach, implemented as git bisect algorithm, uses a binary search strategy. However, recent theoretical work by researchers at Caen has shown that bisect performs poorly in worst-case scenarios on certain graph structures.

If I'm not wrong, two undergraduate students should come: Emmy (Caen) and Matthieu (Marne). Emmy works on efficient exact algorithms for special graph families, such as feature graphs, where the structure is more constrained. Matthieu, if I'm correct, analyzes the Regression Search Problem under a probabilistic model, where the commit introducing the bug is assumed to be random.

I suggest that Emmy and Matthieu work together and talk about their respective problems. Ideally, they should talk about strategies that leverage structure (as in Emmy's feature graphs) and exploit probabilistic assumptions (as in Matthieu's average case) to achieve better practical performance.

Question 5. New algorithm in Java (from Rémi's email)

Potentially fun to look at, introduced in Java 25 (thus, very new).

https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/lang/ScopedValue.java

Featuring:

• a linked list of values per thread
• a global cache (with two parts)
• xor-shift used to hash the keys (with two step hashing)
• global cache invalidation (before and after)

Line 421

Line 444

No idea if this has already been done, but it looks very ad hoc, so probably not.

Kick-off Meeting (LIGM) - January 2026

Monday, January 26

• 2:00 PM - Habilitation de Recherche Defense of Carine Pivoteau

Tuesday, January 27

• 9:00 AM - Welcome at LIGM (4th floor of Copernic)
• 9:30 AM - Workshop on Version Control Systems (Room 2B113, 2nd floor)
• 11:00 AM - Workshop on Fundamental Structures (Room 2B113, 2nd floor)
• 12:30 PM - Buffet at LIGM
• 2:00 PM - Pablo Rotondo will present the seminar from Marne on hash tables with SIMD instructions
• 3:30 PM - Pierre-Yves David from Octobus will present various issues related to the development of a version control system: algorithms, programming, architecture, systems.

Wednesday, January 28

• 9:00 AM - Welcome at LIGM (4th floor of Copernic)
• 9:30 AM - Workshop on various project themes (Room 2B113, 2nd floor)
• 11:00 AM - Presentation on Garbage Collector mechanisms by Rémi Forax (Room 2B113, 2nd floor)
• 12:30 PM - Buffet at LIGM
• 1:30 PM - Project organization points
• 2:30 PM - Assignment of research tasks (for those who don't need to catch an early train)
• 4:00 PM - End