Daniel Lemire

Daniel Lemire est professeur titulaire en informatique. Il s'intéresse particulièrement à la performance du logiciel et aux techniques d'indexation en science des données. Par exemple, il a travaillé sur les index bitmap et la compression des listes d'entiers. Il s'intéresse aussi au design des bases de données et aux algorithmes probabilistes (par ex. le hachage universel). Il aime poser un regard critique sur l'utilisation des technologies.

Ses travaux sur les index bitmap sont utilisés par des sociétés comme eBay, Facebook, LinkedIn et Netflix dans leurs entrepôts de données, au sein des  plate-formes de mégadonnées telles que Google Procella (base de données de YouTube), Apache Hive, Druid, Apache Spark, Netflix Atlas, LinkedIn Pinot  et Apache Kylin. Son code de compression de données est utilisé par Apache Arrow et Apache Impala. L'outil de contrôle de version Git utilise aussi ces mêmes techniques pour accélérer les requêtes. Ses techniques de compression d'index sont utilisées pour la recherche biomédicale. Certaines de ses techniques ont été adoptées par Apache Lucene, le moteur de recherche derrière des sites comme Wikipedia ou des plateformes comme Solr et Elastic. Un de ses techniques de hachage a été adoptée par Tensorflow de Google pour améliorer les performances. Son algorithme Slope One est une référence dans le domaine des systèmes de recommandation. En 2019, ses travaux de recherche ont fait l'objet d'un article dans le magazine Québec Science, L’intelligence artificielle pour rendre les logiciels plus rapides, ainsi que d'une entrevue à l'émission les Années Lumières de Radio-Canada, Des serveurs informatiques plus rapides et moins énergivores. Avec ses collaborateurs en 2019, il a écrit le parseur JSON le plus rapide au monde (simdjson): JSON est le format standard d'échange de données sur Internet. Le parseur simdjson a montré qu'il est possible de traiter des fichiers JSON à des gigaoctets par seconde sans rien sacrifier. Sa librairie simdjson est un des cents plus populaires projets en C++ de tous les temps sur GitHub. La librairie simdjson est utilisée par Facebook, par Shopify, par Intel, par Microsoft, par Apache Doris et par plusieurs autres systèmes importants tel que Node.js. 

Il est l’auteur de plus de 90 publications arbitrées, incluant plus de 50 articles parus dans des revues internationales. Ses travaux scientifiques furent cités près de 5,000 fois. Il détient des subventions de recherche depuis plus de 15 ans. Il sert régulièrement d'expert au sein des comités de programme de conférences prestigieuses (par ex., ACM CIKM, ACM WSDM, ACM SIGIR, ACM RecSys). 

Il s'investit beaucoup dans le développement de librairies logicielles open source. Il programme régulièrement en C, C++, Java, JavaScript, Python, Swift et Go. Il travaille principalement dans des environnements open source (par ex. Linux). En 2012, il fut récompensé par le Google Open Source Peer Bonus Program.  En février 2019, il était classé en deuxième position dans le monde parmi les développeurs les plus populaires sur GitHub et le plus populaire en C++ (devant Facebook, Google et Microsoft). En 2020, Daniel Lemire était l'un des 100 développeurs les plus suivis sur GitHub. Le site GitHub compte 28 millions de développeurs.

L'algorithme de génération de nombres aléatoires décrit dans son article Fast Random Integer Generation in an Interval a été adopté par le langage Swift, par le langage Go, par le langage Julia, par la librairie C++ (Linux) et par Numpy (Python). L'algorithme décrit dans son article Faster Base64 Encoding and Decoding using AVX2 Instructions est utilisé au sein du langage PHP. L'algorithme décrit dans son article Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries est utilisé au sein de la librairie standard du C# pour accélérer notamment la classe Dictionary.

Daniel Lemire est un des auteurs de la librairie Ada qui est peut-être le parseur d'URL le plus rapide au monde. Ada a amélioré la performance du populaire environnement JavaScript Node.js:

"Since Node.js 18, a new URL parser dependency was added to Node.js — Ada. This addition bumped the Node.js performance when parsing URLs to a new level. Some results could reach up to an improvement of 400%. As a regular user, you may not use it directly. But if you use an HTTP server then it’s very likely to be affected by this performance improvement." (State of Node.js Performance 2023)

Il est un avide utilisateur des médias sociaux : son blogue compte plusieurs dizaines de milliers de lecteurs. Il fut l'un des premiers utilisateurs de twitter où il est suivi par plus de 16 000 personnes : @lemire.

Pendant plusieurs années, il a organisé régulièrement des conférences ouvertes au public à Montréal: tribalab et technolab. Suite aux événements du printemps 2020, les conférences auront lieu principalement en ligne.

Conférences (YouTube)

NodeConf EU 2023

BID 2023

SPIRE 2021

Go Systems (San Francisco, 2020)

Performance Summmit III (Seattle, 2020)

QCon San Francisco 2019 (la conférence la plus appréciée par les participants)

Spark Summit East 2017

Laboratoire

Nous avons la chance d'avoir un laboratoire pleinement équipé avec un technicien dédié à nos travaux. Nous avons une ferme de serveurs utilisés partout dans le monde pour étudier la performance du lociel (par ex. par des chercheurs comme Agner Fog). Certaines de nos machines ont les spécifications suivantes:

• Microarchitecture Icelake : Intel(R) Xeon(R) Gold 6338 CPU @ 2.00GHz
• Microarchitecture Haswell : Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz
• Microarchitecture Knights Landing : Intel(R) Xeon Phi(TM) CPU 7210 @ 1.30GHz (64 coeurs)
• Microarchitecture Skylake : Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
• Microarchitecture Skylake-X : Intel(R) Xeon(R) W-2104 CPU @ 3.20GHz
• IBM POWER9 2.2 GHz, 4-core
• Microarchitecture Cannonlake: Intel Core i3-8121U CPU @2.20GHz
• Microarchitecture Skylark (ARMv8): Ampere eMAG CPU 32 coeurs @ 3.3 GHz

Le laboratoire comprend aussi plusieurs stations de travail. Il y a de l'espace dans notre laboratoire pour explorer la réalité virtuelle comme outil en science des données. 

Étudiants et stagiaires

Nous recrutons des étudiants et stagiaires post-doctoraux pour notre équipe. Si vous adorez concevoir du logiciel véloce, et que vous souhaitez venir à Montréal, écrivez-nous! Si vous disposez d'un profil GitHub impressionnant, ce sera un atout en votre faveur. Une connaissance du français est un atout si vous souhaitez suivre un programme universitaire. Certains de nos meilleurs étudiants sont des étudiantes. Nous offrons des bourses pour études supérieurs en performance du logiciel pour l’ingénierie des données.

Si vous êtes un canadien poursuivant des études de premier cycle avec au moins une moyenne de B, vous pourriez être intéressés à venir travailler avec Daniel Lemire dans le cadre d'une bourse de recherche de 1er cycle du CRSNG. Il s'agit d'un stage à temps plein dans nos laboratoires à Montréal. Les dates limites pour postuler sont :

• le premier mars pour un stage à l'été;
• le premier juillet pour l'automne;
• le premier novembre pour l'hiver.

Il s'agit d'un concours qui se poursuit continuellement : nous recevons des candidatures à toutes les sessions. Merci de prévoir au moins une semaine pour la préparation de votre candidature.

Si vous souhaitez poursuivre une maîtrise en technologie de l'information en technologie de l'information à temps plein sous la direction de Daniel Lemire à Montréal, nous recevons des candidatures pour les bourses d’études supérieures du CRSNG. Vous devez avoir un solide dossier universitaire pour postuler. Vous devez aussi être citoyen canadien ou résident permanent du Canada. La date limite pour postuler est le premier décembre de chaque année. Vous devez prévoir du temps pour préparer votre demande. Nous recevons des candidatures à tous les ans.

Si vous êtes intéressés par un doctorat en informatique cognitive à temps plein sous la direction de Daniel Lemire à Montréal, nous recevons des candidatures pour les bourses d’études supérieures du CRSNG. Vous devez avoir un solide dossier universitaire pour postuler. Vous devez aussi être citoyen canadien ou résident permanent du Canada. La date limite pour postuler est le premier novembre de chaque année. Vous devez prévoir du temps pour préparer votre demande. Nous recevons des candidatures à tous les ans.

Par ailleurs, tous les étudiants qui complètent une maîtrise en technologie de l'information avec mémoire ont droit à une bourse, automatiquement. Tous les étudiants qui progressent au sein du doctorat en informatique cognitive ont droit à des bourses automatiques. L'inscription au doctorat implique l'exonération des frais de scolarité pour étudiants étrangers.

Daniel Lemire supervise régulièrement des étudiants aux trois cycles universitaires. Il travaille principalement avec des étudiants qui adorent programmer et qui préfèrent les environnements open source (par ex., Linux). Plusieurs de ses étudiants aux cycles supérieurs contribuent à des projets open source sur des sites comme GitHub.

Il a récemment dirigé ou co-dirigé les thèses de doctorat des étudiants suivants :

• Pierre Marie Ntang, doctorat en informatique cognitive (diplômé en 2023);
• Gary Germeil, doctorat en informatique cognitive (diplômé en 2022);
• Tarek Khei, doctorat en informatique cognitive (diplômé en 2020);
• Xueping Dai, science de l'environnement (diplômé en 2019);
• Erick Aokou Koffi, doctorat en informatique cognitive (diplômé en 2018);
• Badis Merdaoui, doctorat en informatique cognitive (diplômé en 2017);
• Jing Li, doctorat en informatique (diplômée en 2016);
• Samy Chambi, doctorat en informatique (diplômé en 2016);
• Hazel Webb, doctorat en informatique  (diplômée en 2010).

Plusieurs de ses étudiants occupent des postes-clefs: par ex., Maxime Boisvert (M.Sc., 2017) est Production Engineering Manager chez Shopify, Shany Carle (M.Sc., 2017) est professeur d'informatique au cégep de Victoriaville, Shira Smith est ingénieure chez Discord en Californie.

Les projets de recherche majeurs que je propose en ce moment sont organisées en 4 axes: JSON, Unicode, URL et les index Roaring.

Traitement des documents JSON. Nous avons conçu la librairie de traitement des documents JSON la plus rapidement au monde : simdjson. Elle est utilisée par Facebook, Shopify, Microsoft, etc.

• Les programmeurs analysent souvent de grands flux de documents JSON. Bien que nous ayons une esquisse de la façon de faire un tel travail avec notre bibliothèque simdjson, la construction réelle et l'évaluation scientifique du problème ferait un bon mémoire de maîtrise.
• Notre bibliothèque simdjson rapide a des performances d'analyse de pointe, mais elle n'offre pas de moyen pratique pour sérialiser et désérialiser les structures de données (par exemple, une structure de données composée de trois chaînes de caractères et d'un tableau d'entiers). Nous avons esquissé la façon dont cela pourrait être fait à grande vitesse en C++, mais le construire réellement et évaluer le résultat serait un bonne mémoire de maîtrise.
• Pour interroger les documents JSON comme une base de données, JSON Path offre un ensemble de requêtes riche. En utilisant notre fondation simdjson, nous pensons que nous pouvons fournir un moteur de requête JSON-Path qui devrait être au moins 10 fois plus rapide que les logiciels existants prêts pour la production. Il s'agit d'un problème profond qui servira de sujet de doctorat ou de maîtrise.

Traitement des chaînes Unicode. Nous avons conçu la librairie de traitement des chaînes de caractères Unicode la plus rapidement au monde : simdutf. Elle est utilisée par Node.js, Bun, Microsoft Teams, Slack, etc.

• En C#, il est possible d'utiliser des instructions SIMD pour plus de vitesse. En utilisant un algorithme dédié, il devrait être possible d'accélérer la validation des chaînes de caractères Unicode (par ex., UTF-8) en C# avec les instructions SIMD (niveau bac. ou maîtrise).
• Au sein de la librarie simdutf, nos fonctions de transcodage ne prennent pas actuellement en charge le remplacement rapide lorsqu'un caractère incorrect est trouvé. Bien qu'il s'agisse d'un concept simple, la conception d'une telle fonctionnalité à des gigaoctets par seconde devrait s'avérer intéressante (niveau bac. ou maîtrise).
• En s'appuyant sur nos algorithmes accélérés Unicode de la bibliothèque simdutf, nous devrions chercher à construire une extension riche supportant le regroupement, la normalisation, la recherche, le tri et la collation des graphèmes Unicode qui battent tous les records (niveau maîtrise ou doctorat)

Traitement des URL. Nous avons conçu la librairie de traitement des URL respectant la norme WHATWG la plus rapide au monde : ada. Elle est utilisée par Node.js, Microsoft Teams, Slack, etc.

• Les développeurs Web s'appuient généralement sur les normes du WHATWG (URL, WebSockets, Fetch, Streams) telles qu'elles sont mises en œuvre dans des systèmes tels que Node.js. Nous construisons actuellement un analyseur d'URL qui bat tous les records. Cependant, il reste encore beaucoup à faire : par exemple, l'analyse vectorielle et l'encodage des données encodées en pourcentage, la normalisation et la validation Unicode vectorisées, l'analyse et la validation rapides des URL, etc. L'amélioration des performances d'analyse d'URL constituerait un bon projet de maîtrise.

Les index bitmap. Les index bitmap Roaring que nous avons développé sont utilisées par plusieurs systèmes majeurs tels que Apache Lucene et des systèmes dérivés comme Solr et Elasticsearch, Metamarkets' Druid, LinkedIn Pinot, Netflix Atlas, Apache Spark, OpenSearchServer, Cloud Torrent, Whoosh, InfluxDB, Pilosa, Bleve, Microsoft Visual Studio Team Services (VSTS), et Apache Kylin d'eBay. La bibliothèque CRoaring est utilisée dans plusieurs systèmes tels que Apache Doris, StarRocks. Le moteur SQL de YouTube, Google Procella, utilise les bitmaps de Roaring pour l'indexation.

• Intel et AMD fournissent de nouveaux jeux d'instructions rapides pour le traitement vectorisé (AVX-512). Nous disposons d'un support AVX-512 dans notre bibliothèque populaire Roaring Bitmap en C/C++. Un sujet idéal pour une thèse de maîtrise serait l'extension de ce support pour fournir des gains de performance importants dans le monde réel.

Si un de ces projets vous intéressent, veuillez me joindre.

Livres

• Java pas à pas

  

• Programmation avec Python: des jeux au Web

  

Formation

• Postdoctorat (Institut de génie biomédical)
• Doctorat en mathématiques de l’ingénieur (Université de Montréal et École Polytechnique)
• Maîtrise en mathématiques (University of Toronto)
• Baccalauréat en mathématique (University of Toronto), avec mention «High Distinction»

Champs d'expertise

• Science des données
• Ingénierie des données
• Indexation des données
• Performance du logiciel
• Vectorisation (SIMD)