diff options
| -rw-r--r-- | Cargo.lock | 2 | ||||
| -rw-r--r-- | azalea-world/Cargo.toml | 2 | ||||
| -rw-r--r-- | azalea-world/benches/chunks.rs | 37 | ||||
| -rw-r--r-- | azalea-world/src/bit_storage.rs | 162 | ||||
| -rw-r--r-- | azalea-world/src/find_blocks.rs | 7 |
5 files changed, 117 insertions, 93 deletions
@@ -587,7 +587,6 @@ dependencies = [ name = "azalea-world" version = "0.15.0+mc1.21.11" dependencies = [ - "azalea", "azalea-block", "azalea-buf", "azalea-core", @@ -597,6 +596,7 @@ dependencies = [ "derive_more", "nohash-hasher", "parking_lot", + "rand 0.10.0-rc.7", "rustc-hash", "serde", "tracing", diff --git a/azalea-world/Cargo.toml b/azalea-world/Cargo.toml index 9e1a2729..73b2d3a8 100644 --- a/azalea-world/Cargo.toml +++ b/azalea-world/Cargo.toml @@ -7,8 +7,8 @@ license.workspace = true repository.workspace = true [dev-dependencies] -azalea.path = "../azalea" criterion.workspace = true +rand.workspace = true [dependencies] azalea-block.workspace = true diff --git a/azalea-world/benches/chunks.rs b/azalea-world/benches/chunks.rs index 64924fec..e1ca94a6 100644 --- a/azalea-world/benches/chunks.rs +++ b/azalea-world/benches/chunks.rs @@ -3,7 +3,7 @@ use std::hint::black_box; use azalea_core::position::ChunkBlockPos; use azalea_registry::builtin::BlockKind; use azalea_world::{BitStorage, Chunk}; -use criterion::{Criterion, criterion_group, criterion_main}; +use criterion::{BatchSize, Bencher, Criterion, criterion_group, criterion_main}; fn bench_chunks(c: &mut Criterion) { c.bench_function("Chunk::set", |b| { @@ -25,13 +25,36 @@ fn bench_chunks(c: &mut Criterion) { }); } +fn bench_bitstorage_with(b: &mut Bencher, bits: usize, size: usize) { + let mut storage = BitStorage::new(bits, size, None).unwrap(); + b.iter_batched( + || { + // let index = rand + let mut vec = Vec::with_capacity(size); + for _ in 0..size { + vec.push(rand::random_range(0..size)); + } + vec + }, + |indices| { + for index in indices { + storage.set(index, 1); + } + }, + BatchSize::SmallInput, + ); + black_box(storage); +} + fn bench_bitstorage(c: &mut Criterion) { - c.bench_function("BitStorage::set", |b| { - let mut storage = BitStorage::new(1, 4096, None).unwrap(); - b.iter(|| { - storage.set(136, 1); - }); - black_box(storage); + c.bench_function("BitStorage::set (1 bit per entry)", |b| { + bench_bitstorage_with(b, 1, 4096) + }); + c.bench_function("BitStorage::set (2 bits per entry)", |b| { + bench_bitstorage_with(b, 2, 4096) + }); + c.bench_function("BitStorage::set (3 bits per entry)", |b| { + bench_bitstorage_with(b, 3, 4096) }); } diff --git a/azalea-world/src/bit_storage.rs b/azalea-world/src/bit_storage.rs index daad9202..44705f88 100644 --- a/azalea-world/src/bit_storage.rs +++ b/azalea-world/src/bit_storage.rs @@ -1,72 +1,73 @@ use std::{error::Error, fmt}; +// fast constant division #[rustfmt::skip] -const MAGIC: [(i32, i32, i32); 64] = [ - // divide_mul, divide_add, divide_shift - (-1, -1, 0), - (-0b10000000000000000000000000000000, 0, 0), - (0b1010101010101010101010101010101, 0b1010101010101010101010101010101, 0), - (-0b10000000000000000000000000000000, 0, 1), - (0b110011001100110011001100110011, 0b110011001100110011001100110011, 0), - (0b101010101010101010101010101010, 0b101010101010101010101010101010, 0), - (0b100100100100100100100100100100, 0b100100100100100100100100100100, 0), - (-0b10000000000000000000000000000000, 0, 2), - (0b11100011100011100011100011100, 0b11100011100011100011100011100, 0), - (0b11001100110011001100110011001, 0b11001100110011001100110011001, 0), - (0b10111010001011101000101110100, 0b10111010001011101000101110100, 0), - (0b10101010101010101010101010101, 0b10101010101010101010101010101, 0), - (0b10011101100010011101100010011, 0b10011101100010011101100010011, 0), - (0b10010010010010010010010010010, 0b10010010010010010010010010010, 0), - (0b10001000100010001000100010001, 0b10001000100010001000100010001, 0), - (-0b10000000000000000000000000000000, 0, 3), - (0b1111000011110000111100001111, 0b1111000011110000111100001111, 0), - (0b1110001110001110001110001110, 0b1110001110001110001110001110, 0), - (0b1101011110010100001101011110, 0b1101011110010100001101011110, 0), - (0b1111111111111111111111111111000, 0b1111111111111111111111111111000, 0), - (0b1100001100001100001100001100, 0b1100001100001100001100001100, 0), - (0b1011101000101110100010111010, 0b1011101000101110100010111010, 0), - (0b1011001000010110010000101100, 0b1011001000010110010000101100, 0), - (0b1010101010101010101010101010, 0b1010101010101010101010101010, 0), - (0b1010001111010111000010100011, 0b1010001111010111000010100011, 0), - (0b1001110110001001110110001001, 0b1001110110001001110110001001, 0), - (0b1001011110110100001001011110, 0b1001011110110100001001011110, 0), - (0b1001001001001001001001001001, 0b1001001001001001001001001001, 0), - (0b1000110100111101110010110000, 0b1000110100111101110010110000, 0), - (0b1000100010001000100010001000, 0b1000100010001000100010001000, 0), - (0b1000010000100001000010000100, 0b1000010000100001000010000100, 0), - (-0b10000000000000000000000000000000, 0, 4), - (0b111110000011111000001111100, 0b111110000011111000001111100, 0), - (0b111100001111000011110000111, 0b111100001111000011110000111, 0), - (0b111010100000111010100000111, 0b111010100000111010100000111, 0), - (0b111000111000111000111000111, 0b111000111000111000111000111, 0), - (0b110111010110011111001000101, 0b110111010110011111001000101, 0), - (0b110101111001010000110101111, 0b110101111001010000110101111, 0), - (0b110100100000110100100000110, 0b110100100000110100100000110, 0), - (0b110011001100110011001100110, 0b110011001100110011001100110, 0), - (0b110001111100111000001100011, 0b110001111100111000001100011, 0), - (0b110000110000110000110000110, 0b110000110000110000110000110, 0), - (0b101111101000001011111010000, 0b101111101000001011111010000, 0), - (0b101110100010111010001011101, 0b101110100010111010001011101, 0), - (0b101101100000101101100000101, 0b101101100000101101100000101, 0), - (0b101100100001011001000010110, 0b101100100001011001000010110, 0), - (0b101011100100110001000001010, 0b101011100100110001000001010, 0), - (0b101010101010101010101010101, 0b101010101010101010101010101, 0), - (0b101001110010111100000101001, 0b101001110010111100000101001, 0), - (0b101000111101011100001010001, 0b101000111101011100001010001, 0), - (0b101000001010000010100000101, 0b101000001010000010100000101, 0), - (0b100111011000100111011000100, 0b100111011000100111011000100, 0), - (0b100110101001000011100111110, 0b100110101001000011100111110, 0), - (0b100101111011010000100101111, 0b100101111011010000100101111, 0), - (0b100101001111001000001001010, 0b100101001111001000001001010, 0), - (0b100100100100100100100100100, 0b100100100100100100100100100, 0), - (0b100011111011100000100011111, 0b100011111011100000100011111, 0), - (0b100011010011110111001011000, 0b100011010011110111001011000, 0), - (0b100010101101100011110010111, 0b100010101101100011110010111, 0), - (0b100010001000100010001000100, 0b100010001000100010001000100, 0), - (0b100001100100101110001010011, 0b100001100100101110001010011, 0), - (0b100001000010000100001000010, 0b100001000010000100001000010, 0), - (0b100000100000100000100000100, 0b100000100000100000100000100, 0), - (-0b10000000000000000000000000000000, 0, 5), +const MAGIC: [(i32, i32, u32); 64] = [ + // mul, add, shift + (1, 0, 0), // divide by 1 + (1, 0, 1), // divide by 2, etc + (0x55555555, 0x55555555, 32), + (1, 0, 2), + (0x33333333, 0x33333333, 32), + (0x2AAAAAAA, 0x2AAAAAAA, 32), + (0x24924924, 0x24924924, 32), + (1, 0, 3), + (0x1C71C71C, 0x1C71C71C, 32), + (0x19999999, 0x19999999, 32), + (0x1745D174, 0x1745D174, 32), + (0x15555555, 0x15555555, 32), + (0x13B13B13, 0x13B13B13, 32), + (0x12492492, 0x12492492, 32), + (0x11111111, 0x11111111, 32), + (1, 0, 4), + (0xF0F0F0F, 0xF0F0F0F, 32), + (0xE38E38E, 0xE38E38E, 32), + (0xD79435E, 0xD79435E, 32), + (0x7FFFFFF8, 0x7FFFFFF8, 32), + (0xC30C30C, 0xC30C30C, 32), + (0xBA2E8BA, 0xBA2E8BA, 32), + (0xB21642C, 0xB21642C, 32), + (0xAAAAAAA, 0xAAAAAAA, 32), + (0xA3D70A3, 0xA3D70A3, 32), + (0x9D89D89, 0x9D89D89, 32), + (0x97B425E, 0x97B425E, 32), + (0x9249249, 0x9249249, 32), + (0x8D3DCB0, 0x8D3DCB0, 32), + (0x8888888, 0x8888888, 32), + (0x8421084, 0x8421084, 32), + (1, 0, 5), + (0x7C1F07C, 0x7C1F07C, 32), + (0x7878787, 0x7878787, 32), + (0x7507507, 0x7507507, 32), + (0x71C71C7, 0x71C71C7, 32), + (0x6EB3E45, 0x6EB3E45, 32), + (0x6BCA1AF, 0x6BCA1AF, 32), + (0x6906906, 0x6906906, 32), + (0x6666666, 0x6666666, 32), + (0x63E7063, 0x63E7063, 32), + (0x6186186, 0x6186186, 32), + (0x5F417D0, 0x5F417D0, 32), + (0x5D1745D, 0x5D1745D, 32), + (0x5B05B05, 0x5B05B05, 32), + (0x590B216, 0x590B216, 32), + (0x572620A, 0x572620A, 32), + (0x5555555, 0x5555555, 32), + (0x5397829, 0x5397829, 32), + (0x51EB851, 0x51EB851, 32), + (0x5050505, 0x5050505, 32), + (0x4EC4EC4, 0x4EC4EC4, 32), + (0x4D4873E, 0x4D4873E, 32), + (0x4BDA12F, 0x4BDA12F, 32), + (0x4A7904A, 0x4A7904A, 32), + (0x4924924, 0x4924924, 32), + (0x47DC11F, 0x47DC11F, 32), + (0x469EE58, 0x469EE58, 32), + (0x456C797, 0x456C797, 32), + (0x4444444, 0x4444444, 32), + (0x4325C53, 0x4325C53, 32), + (0x4210842, 0x4210842, 32), + (0x4104104, 0x4104104, 32), + (1, 0, 6), ]; /// A compact list of integers with the given number of bits per entry. @@ -77,9 +78,9 @@ pub struct BitStorage { mask: u64, size: usize, values_per_long: usize, - divide_mul: u64, - divide_add: u64, - divide_shift: i32, + divide_mul: i32, + divide_add: i32, + divide_shift: u32, } #[derive(Debug)] @@ -99,8 +100,8 @@ impl fmt::Display for BitStorageError { impl Error for BitStorageError {} impl BitStorage { - /// Create a new BitStorage with the given number of bits per entry. - /// `size` is the number of entries in the BitStorage. + /// Create a new BitStorage with the given number of bits per entry. `size` + /// is the number of entries in the BitStorage. pub fn new( bits: usize, size: usize, @@ -145,18 +146,19 @@ impl BitStorage { mask, size, values_per_long, - divide_mul: divide_mul as u32 as u64, - divide_add: divide_add as u32 as u64, + divide_mul, + divide_add, divide_shift, }) } - pub fn cell_index(&self, index: u64) -> usize { - // as unsigned wrap - let first = self.divide_mul; - let second = self.divide_add; + #[inline] + fn cell_index(&self, index: u64) -> usize { + let mul = self.divide_mul as u32 as u64; + let add = self.divide_add as u32 as u64; + let shift = self.divide_shift; - (((index * first) + second) >> 32 >> self.divide_shift) as usize + (((index * mul) + add) >> shift) as usize } /// Get the data at the given index. @@ -254,7 +256,9 @@ mod tests { use super::*; #[test] - fn test_wikivg_example() { + fn test_protocol_wiki_example() { + // https://minecraft.wiki/w/Java_Edition_protocol/Chunk_format#Visual_example + let data = [ 1, 2, 2, 3, 4, 4, 5, 6, 6, 4, 8, 0, 7, 4, 3, 13, 15, 16, 9, 14, 10, 12, 0, 2, ]; diff --git a/azalea-world/src/find_blocks.rs b/azalea-world/src/find_blocks.rs index f8f1fd91..0980e825 100644 --- a/azalea-world/src/find_blocks.rs +++ b/azalea-world/src/find_blocks.rs @@ -11,11 +11,8 @@ impl World { /// /// ``` /// # use azalea_registry::builtin::BlockKind; - /// # fn example(client: &azalea::Client) { - /// client - /// .world() - /// .read() - /// .find_block(client.position(), &BlockKind::Chest.into()); + /// # fn example(world: &World) { + /// let pos = world.find_block(client.position(), &BlockKind::Chest.into()); /// # } /// ``` pub fn find_block( |