perf: use a heap queue for ordering names for processing

This shaves off about 2s of the 5s total run time for building my journal.

Sponsored-by: author

2 files changed, 17 insertions, 6 deletions

diff --git a/src/name.rs b/src/name.rs
index 9cfca6b..4cb5f16 100644
--- a/src/name.rs
+++ b/src/name.rs
@@ -1,4 +1,5 @@
 use crate::util::{join_subpath, make_path_absolute, make_path_relative_to};
+use std::cmp::Ordering;
 use std::fmt;
 use std::path::{Path, PathBuf};
 
@@ -48,6 +49,18 @@ impl Name {
     }
 }
 
+impl Ord for Name {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.src.cmp(&other.src).reverse()
+    }
+}
+
+impl PartialOrd for Name {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
 impl PartialEq<Name> for &Name {
     fn eq(&self, other: &Name) -> bool {
         self.src == other.src
diff --git a/src/site.rs b/src/site.rs
index 4c1d585..cf113d8 100644
--- a/src/site.rs
+++ b/src/site.rs
@@ -6,7 +6,7 @@ use crate::parser::WikitextParser;
 use crate::token::TokenPatterns;
 use crate::util::make_relative_link;
 use log::{debug, info, trace};
-use std::collections::HashMap;
+use std::collections::{BinaryHeap, HashMap};
 use std::path::{Path, PathBuf};
 use std::time::SystemTime;
 use walkdir::WalkDir;
@@ -18,7 +18,7 @@ pub struct Site {
     markdown_pages: Vec<MarkdownPage>,
     files: Names,
     patterns: TokenPatterns,
-    name_queue: Vec<Name>,
+    name_queue: BinaryHeap<Name>,
     page_queue: PageSet,
     whatchanged: HashMap<PathBuf, SystemTime>,
     shortcuts: HashMap<String, Shortcut>,
@@ -39,7 +39,7 @@ impl Site {
             markdown_pages: vec![],
             files: Names::default(),
             patterns: TokenPatterns::default(),
-            name_queue: vec![],
+            name_queue: BinaryHeap::new(),
             page_queue: PageSet::default(),
             whatchanged: HashMap::new(),
             shortcuts: HashMap::new(),
@@ -90,9 +90,7 @@ impl Site {
     }
 
     fn process_name(&mut self) -> Result<bool, SiteError> {
-        self.name_queue.sort_by_cached_key(|name| name.page_path().to_path_buf());
-        if !self.name_queue.is_empty() {
-            let name = self.name_queue.remove(0);
+        if let Some(name) = self.name_queue.pop() {
             debug!("loading wikitext page {}", name.source_path().display());
             let mut page = WikitextPage::read(&name)?;
             if let Some(mtime) = self.git_commit_timestamp(&name) {