binary search map

10 files changed, 122 insertions, 75 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 8ad23510..3ba21574 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -40,19 +40,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "ahash"
-version = "0.8.3"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "2c99f64d1e06488f620f932677e24bc6e2897582980441ae90a671415bd7ec2f"
-dependencies = [
- "cfg-if",
- "getrandom",
- "once_cell",
- "serde",
- "version_check",
-]
-
-[[package]]
 name = "aho-corasick"
 version = "0.7.20"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -349,7 +336,6 @@ dependencies = [
 name = "azalea-nbt"
 version = "0.6.0"
 dependencies = [
- "ahash 0.8.3",
  "azalea-buf",
  "byteorder",
  "compact_str",
@@ -656,7 +642,7 @@ version = "0.10.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "04d90ce493910ad9af3b4220ea6864c7d1472761086a98230ecac59c8d547e95"
 dependencies = [
- "ahash 0.7.6",
+ "ahash",
  "bevy_utils_proc_macros",
  "getrandom",
  "hashbrown",
@@ -1329,7 +1315,7 @@ version = "0.12.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "8a9ee70c43aaf417c914396645a0fa852624801b24ebb7ae78fe8272889ac888"
 dependencies = [
- "ahash 0.7.6",
+ "ahash",
  "serde",
 ]
 
diff --git a/azalea-nbt/Cargo.toml b/azalea-nbt/Cargo.toml
index e14c501f..76c57663 100644
--- a/azalea-nbt/Cargo.toml
+++ b/azalea-nbt/Cargo.toml
@@ -9,7 +9,6 @@ repository = "https://github.com/mat-1/azalea/tree/main/azalea-nbt"
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
 
 [dependencies]
-ahash = { version = "^0.8.3" }
 azalea-buf = { path = "../azalea-buf", version = "^0.6.0" }
 byteorder = "^1.4.3"
 compact_str = { version = "0.7.0", features = ["serde"] }
@@ -26,7 +25,7 @@ fastnbt = "2.4.3"
 
 [features]
 default = []
-serde = ["dep:serde", "ahash/serde"]
+serde = ["dep:serde"]
 
 [profile.release]
 lto = true
diff --git a/azalea-nbt/README.md b/azalea-nbt/README.md
index 63e0bfe7..5e20b008 100755
--- a/azalea-nbt/README.md
+++ b/azalea-nbt/README.md
@@ -7,17 +7,16 @@ Note: Running your code with `RUSTFLAGS="-C target-cpu=native"` will result in s
 # Examples
 
 ```
-use ahash::AHashMap;
-use azalea_nbt::Tag;
+use azalea_nbt::{Tag, NbtCompound};
 use std::io::Cursor;
 
 let buf = include_bytes!("../tests/hello_world.nbt");
 let tag = Tag::read(&mut Cursor::new(&buf[..])).unwrap();
 assert_eq!(
     tag,
-    Tag::Compound(AHashMap::from_iter(vec![(
+    Tag::Compound(NbtCompound::from_iter(vec![(
         "hello world".into(),
-        Tag::Compound(AHashMap::from_iter(vec![(
+        Tag::Compound(NbtCompound::from_iter(vec![(
             "name".into(),
             Tag::String("Bananrama".into()),
         )]))
diff --git a/azalea-nbt/benches/compare.rs b/azalea-nbt/benches/compare.rs
index 7aede267..bed77527 100755
--- a/azalea-nbt/benches/compare.rs
+++ b/azalea-nbt/benches/compare.rs
@@ -48,40 +48,40 @@ pub fn bench_read_file(filename: &str, c: &mut Criterion) {
 
     // // writing
 
-    // let nbt = azalea_nbt::Tag::read_from(&mut Cursor::new(input)).unwrap();
-    // group.bench_function("azalea_write", |b| {
-    //     b.iter(|| {
-    //         let nbt = black_box(&nbt);
-    //         let mut written = Vec::new();
-    //         nbt.write(&mut written).unwrap();
-    //         black_box(written);
-    //     })
-    // });
+    let nbt = azalea_nbt::Tag::read_from(&mut Cursor::new(input)).unwrap();
+    group.bench_function("azalea_write", |b| {
+        b.iter(|| {
+            let nbt = black_box(&nbt);
+            let mut written = Vec::new();
+            nbt.write(&mut written).unwrap();
+            black_box(written);
+        })
+    });
 
-    // let nbt = graphite_binary::nbt::decode::read(&mut &input[..]).unwrap();
-    // group.bench_function("graphite_write", |b| {
-    //     b.iter(|| {
-    //         let nbt = black_box(&nbt);
-    //         let written = graphite_binary::nbt::encode::write(nbt);
-    //         black_box(written);
-    //     })
-    // });
+    let nbt = graphite_binary::nbt::decode::read(&mut &input[..]).unwrap();
+    group.bench_function("graphite_write", |b| {
+        b.iter(|| {
+            let nbt = black_box(&nbt);
+            let written = graphite_binary::nbt::encode::write(nbt);
+            black_box(written);
+        })
+    });
 
-    // let nbt = valence_nbt::from_binary_slice(&mut &input[..]).unwrap();
-    // group.bench_function("valence_write", |b| {
-    //     b.iter(|| {
-    //         let nbt = black_box(&nbt);
-    //         let mut written = Vec::new();
-    //         valence_nbt::to_binary_writer(&mut written, &nbt.0,
-    // &nbt.1).unwrap();         black_box(written);
-    //     })
-    // });
+    let nbt = valence_nbt::from_binary_slice(&mut &input[..]).unwrap();
+    group.bench_function("valence_write", |b| {
+        b.iter(|| {
+            let nbt = black_box(&nbt);
+            let mut written = Vec::new();
+            valence_nbt::to_binary_writer(&mut written, &nbt.0, &nbt.1).unwrap();
+            black_box(written);
+        })
+    });
 }
 
 fn bench(c: &mut Criterion) {
     bench_read_file("tests/bigtest.nbt", c);
     // bench_read_file("tests/simple_player.dat", c);
-    // bench_read_file("tests/complex_player.dat", c);
+    bench_read_file("tests/complex_player.dat", c);
     // bench_read_file("tests/level.dat", c);
     // bench_read_file("tests/stringtest.nbt", c);
     // bench_read_file("tests/inttest.nbt", c);
diff --git a/azalea-nbt/benches/nbt.rs b/azalea-nbt/benches/nbt.rs
index 5eeb733f..3d56cad9 100755
--- a/azalea-nbt/benches/nbt.rs
+++ b/azalea-nbt/benches/nbt.rs
@@ -26,16 +26,16 @@ fn bench_file(filename: &str, c: &mut Criterion) {
 
     group.throughput(Throughput::Bytes(decoded_src.len() as u64));
 
-    // group.bench_function("Decode", |b| {
-    //     b.iter(|| {
-    //         black_box(Tag::read(&mut decoded_src_stream).unwrap());
-    //         decoded_src_stream.set_position(0);
-    //     })
-    // });
+    group.bench_function("Decode", |b| {
+        b.iter(|| {
+            black_box(Tag::read(&mut decoded_src_stream).unwrap());
+            decoded_src_stream.set_position(0);
+        })
+    });
 
     group.bench_function("Encode", |b| {
         b.iter(|| {
-            nbt.write(&mut io::sink()).unwrap();
+            nbt.write(&mut black_box(Vec::new())).unwrap();
         })
     });
     group.finish();
diff --git a/azalea-nbt/src/decode.rs b/azalea-nbt/src/decode.rs
index 635e2f6d..e2e9c7c9 100755
--- a/azalea-nbt/src/decode.rs
+++ b/azalea-nbt/src/decode.rs
@@ -1,6 +1,5 @@
 use crate::tag::*;
 use crate::Error;
-use ahash::AHashMap;
 use azalea_buf::{BufReadError, McBufReadable};
 use byteorder::{ReadBytesExt, BE};
 use flate2::read::{GzDecoder, ZlibDecoder};
@@ -265,7 +264,7 @@ impl Tag {
         }
         let name = read_string(stream)?;
         let tag = Tag::read_known(stream, tag_id)?;
-        let mut map = AHashMap::with_capacity(1);
+        let mut map = NbtCompound::with_capacity(1);
         map.insert(name, tag);
 
         Ok(Tag::Compound(map))
diff --git a/azalea-nbt/src/encode.rs b/azalea-nbt/src/encode.rs
index ba2b77a5..03715691 100755
--- a/azalea-nbt/src/encode.rs
+++ b/azalea-nbt/src/encode.rs
@@ -15,7 +15,7 @@ fn write_string(writer: &mut dyn Write, string: &str) -> Result<(), Error> {
 
 #[inline]
 fn write_compound(writer: &mut dyn Write, value: &NbtCompound, end_tag: bool) -> Result<(), Error> {
-    for (key, tag) in value {
+    for (key, tag) in value.inner() {
         match tag {
             Tag::End => {}
             Tag::Byte(value) => {
diff --git a/azalea-nbt/src/lib.rs b/azalea-nbt/src/lib.rs
index 048e466e..3c8aa2cd 100755
--- a/azalea-nbt/src/lib.rs
+++ b/azalea-nbt/src/lib.rs
@@ -6,23 +6,23 @@ mod error;
 mod tag;
 
 pub use error::Error;
-pub use tag::NbtList;
-pub use tag::Tag;
+pub use tag::{NbtCompound, NbtList, Tag};
 
 #[cfg(test)]
 mod tests {
     use std::io::Cursor;
 
+    use crate::tag::NbtCompound;
+
     use super::*;
-    use ahash::AHashMap;
     use azalea_buf::{McBufReadable, McBufWritable};
 
     #[test]
     fn mcbuf_nbt() {
         let mut buf = Vec::new();
-        let tag = Tag::Compound(AHashMap::from_iter(vec![(
+        let tag = Tag::Compound(NbtCompound::from_iter(vec![(
             "hello world".into(),
-            Tag::Compound(AHashMap::from_iter(vec![(
+            Tag::Compound(NbtCompound::from_iter(vec![(
                 "name".into(),
                 Tag::String("Bananrama".into()),
             )])),
@@ -34,9 +34,9 @@ mod tests {
         let result = Tag::read_from(&mut buf).unwrap();
         assert_eq!(
             result,
-            Tag::Compound(AHashMap::from_iter(vec![(
+            Tag::Compound(NbtCompound::from_iter(vec![(
                 "hello world".into(),
-                Tag::Compound(AHashMap::from_iter(vec![(
+                Tag::Compound(NbtCompound::from_iter(vec![(
                     "name".into(),
                     Tag::String("Bananrama".into()),
                 )])),
diff --git a/azalea-nbt/src/tag.rs b/azalea-nbt/src/tag.rs
index e1aecb91..e23db913 100755
--- a/azalea-nbt/src/tag.rs
+++ b/azalea-nbt/src/tag.rs
@@ -1,9 +1,7 @@
-use ahash::AHashMap;
-
 use compact_str::CompactString;
 use enum_as_inner::EnumAsInner;
 #[cfg(feature = "serde")]
-use serde::{Deserialize, Serialize};
+use serde::{ser::SerializeMap, Deserialize, Serialize};
 
 pub type NbtByte = i8;
 pub type NbtShort = i16;
@@ -13,7 +11,6 @@ pub type NbtFloat = f32;
 pub type NbtDouble = f64;
 pub type NbtByteArray = Vec<u8>;
 pub type NbtString = CompactString;
-pub type NbtCompound = AHashMap<CompactString, Tag>;
 pub type NbtIntArray = Vec<i32>;
 pub type NbtLongArray = Vec<i64>;
 
@@ -94,3 +91,71 @@ impl NbtList {
         unsafe { *<*const _>::from(self).cast::<u8>() }
     }
 }
+
+// thanks to Moulberry/Graphite for the idea to use a vec and binary search
+#[derive(Debug, Clone, PartialEq)]
+pub struct NbtCompound {
+    inner: Vec<(NbtString, Tag)>,
+}
+impl NbtCompound {
+    #[inline]
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self {
+            inner: Vec::with_capacity(capacity),
+        }
+    }
+
+    #[inline]
+    fn binary_search(&self, key: &NbtString) -> Result<usize, usize> {
+        self.inner.binary_search_by(|(k, _)| k.cmp(key))
+    }
+
+    #[inline]
+    pub fn get(&self, key: &NbtString) -> Option<&Tag> {
+        self.binary_search(key).ok().map(|i| &self.inner[i].1)
+    }
+
+    #[inline]
+    pub fn insert(&mut self, key: NbtString, value: Tag) -> Option<Tag> {
+        match self.binary_search(&key) {
+            Ok(i) => Some(std::mem::replace(&mut self.inner[i].1, value)),
+            Err(i) => {
+                self.inner.insert(i, (key, value));
+                None
+            }
+        }
+    }
+
+    #[inline]
+    pub fn inner(&self) -> &Vec<(NbtString, Tag)> {
+        &self.inner
+    }
+}
+#[cfg(feature = "serde")]
+impl Serialize for NbtCompound {
+    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
+        let mut map = serializer.serialize_map(Some(self.inner.len()))?;
+        for (key, value) in &self.inner {
+            map.serialize_entry(key, value)?;
+        }
+        map.end()
+    }
+}
+#[cfg(feature = "serde")]
+impl<'de> Deserialize<'de> for NbtCompound {
+    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
+        use std::collections::BTreeMap;
+        let map = <BTreeMap<NbtString, Tag> as Deserialize>::deserialize(deserializer)?;
+        Ok(Self {
+            inner: map.into_iter().collect(),
+        })
+    }
+}
+
+impl FromIterator<(NbtString, Tag)> for NbtCompound {
+    fn from_iter<T: IntoIterator<Item = (NbtString, Tag)>>(iter: T) -> Self {
+        let mut inner = iter.into_iter().collect::<Vec<_>>();
+        inner.sort_unstable_by_key(|(k, _)| k.clone());
+        Self { inner }
+    }
+}
diff --git a/azalea-nbt/tests/tests.rs b/azalea-nbt/tests/tests.rs
index 62852578..22fc1074 100755
--- a/azalea-nbt/tests/tests.rs
+++ b/azalea-nbt/tests/tests.rs
@@ -1,5 +1,4 @@
-use ahash::AHashMap;
-use azalea_nbt::{NbtList, Tag};
+use azalea_nbt::{NbtCompound, NbtList, Tag};
 use std::io::Cursor;
 
 #[test]
@@ -9,9 +8,9 @@ fn test_decode_hello_world() {
     let tag = Tag::read(&mut Cursor::new(&buf[..])).unwrap();
     assert_eq!(
         tag,
-        Tag::Compound(AHashMap::from_iter(vec![(
+        Tag::Compound(NbtCompound::from_iter(vec![(
             "hello world".into(),
-            Tag::Compound(AHashMap::from_iter(vec![(
+            Tag::Compound(NbtCompound::from_iter(vec![(
                 "name".into(),
                 Tag::String("Bananrama".into()),
             )]))
@@ -51,7 +50,7 @@ fn test_bigtest() {
 
 #[test]
 fn test_stringtest() {
-    let correct_tag = Tag::Compound(AHashMap::from_iter(vec![(
+    let correct_tag = Tag::Compound(NbtCompound::from_iter(vec![(
         "😃".into(),
         Tag::List(NbtList::String(vec![
             "asdfkghasfjgihsdfogjsndfg".into(),