On optimizing scalar self-rebalancing trees - Rapports de recherche et Technique de l'Inria Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2020

On optimizing scalar self-rebalancing trees

Résumé

Balanced trees are pervasive and very often found in databases or other systems which are built around querying non-static data. In this paper, we show that trees implemented as a collection of pointers shows bad data locality, poor cache performance and suffer from a lack of parallelism opportunities. We propose an alternative implementation based on arrays. Both implementations appear to be equivalently efficient time-wise. This new layout exposes new parallelism opportunities which can be then exploited by an optimizing polyhedral compiler.
Fichier principal
Vignette du fichier
RR-9343.pdf (897.03 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02573052 , version 1 (14-05-2020)

Identifiants

  • HAL Id : hal-02573052 , version 1

Citer

Paul Iannetta, Laure Gonnord, Lionel Morel. On optimizing scalar self-rebalancing trees. [Research Report] RR-9343, ENS LYON; Inria - Research Centre Grenoble – Rhône-Alpes; Université de Lyon I Claude Bernard. 2020. ⟨hal-02573052⟩
295 Consultations
229 Téléchargements

Partager

Gmail Facebook X LinkedIn More