Research more efficient World storage

[jonas-schievink]

Chunks in the World are currently stored in a HashMap. Rust uses a collision-resistant cryptographic hash by default (SipHash), which can be quite slow for small keys (and AxialPoint is very small).

A few different approaches should be implemented and compared:

• Use a different hashing algorithm, but keep the HashMap
  • FNV-Hash - crate
  • Should be the easiest to implement
• Use the BTreeMap
  • This requires the key to be Ord, which AxialPoint isn't. To keep AxialPoint clean, a private newtype wrapper can be implemented which implements PartialOrd and Ord (we can also just #[derive] it on AxialPoint for simplicity - but < and > on points doesn't really make sense).
• Use a sparse vector holding a fixed NxN grid of chunks
  • This should be very fast, but you'll have to actually think a bit about what you're doing since the player can move around in the world (might need deeper integration than just world.rs)
• ... any other ideas?

If the chunk storage efficiency doesn't cause any practical problems, this isn't very important. But if anyone wants to fix this anyways, feel free to.

[jonas-schievink]

perf output:

   8,67%  plantex  plantex                     [.] glium::program::uniforms_storage::UniformsStorage::set_uniform_value::ha5e5f596cb2f2efe
   7,27%  plantex  plantex                     [.] client::render::Renderer::render::hcc24235783bb4164
   6,72%  plantex  plantex                     [.] _$LT$hash..sip..SipHasher$u20$as$u20$hash..Hasher$GT$::write::he3cca41a9c199b36
   6,54%  plantex  plantex                     [.] _$LT$hash..sip..SipHasher$u20$as$u20$hash..Hasher$GT$::finish::hcaaa5006afab4023
   4,08%  plantex  plantex                     [.] _$LT$hash..sip..SipHasher$u20$as$u20$hash..Hasher$GT$::write::he3cca41a9c199b36
   4,01%  plantex  plantex                     [.] _$LT$program..program..Program$u20$as$u20$ProgramExt$GT$::get_uniform::h98f3787d3c45f7b5
   3,50%  plantex  plantex                     [.] _$LT$hash..sip..SipHasher$u20$as$u20$hash..Hasher$GT$::finish::hcaaa5006afab4023
   3,45%  plantex  plantex                     [.] glium::draw_parameters::sync::he374d9e2f3825e96
   2,95%  plantex  plantex                     [.] glium::vertex_array_object::Binder::bind::hc8a902c9ed8a805f

Do we use a HashMap anywhere else?

EDIT: This seems to be #61 and not this - We don't seem to access the HashMap in the render loop

[Cranc]

i remembered sometime ago reading about "voxel engines" one part of it was read times of different types of different data structures.
if i remember correctly it turned out that "Interval tree + hashing" is by far one of the best ways if you do not have random reads, which isn't really the case here.

ps: found the repository again git repo