search

orlp / slotmap

Slotmap data structure for Rust
zlib License
1.08k stars 70 forks source link

Add `values_as_slice()` to DenseSlotMap #81

Open Jasper-Bekkers opened 2 years ago

Jasper-Bekkers commented 2 years ago

I'm opening this PR not because it's the final proposal, but I wanted to start a discussion at least.

I have some performance sensitive code that currently takes a slice of data to ensure that the iteration it's doing is linear in memory. I don't want that code to accidentally receive an iterator that's not linear in memory, so taking an argument along the lines of impl Iterator<Item = X> is a bit of a no-go.

On top of that, the performance sensitive code is behind a dyn trait, so even if I wanted to, I think it'd be impossible to enforce linearity through a trait there. What do the project maintainers think of exposing the values list of a DenseSlotMap as a slice directly? Obviously this should come with the caveat that one can't depend on the order of items in that slice, and that one shouldn't store indices into the slice anywhere (I'd be OK for example with marking this as unsafe).

Additionally, I found some odd code where the Values iterator also seems to require a) the Key type and b) not forward directly into std::slice::Iter but through the other iterator and map'ing out the key values, seems like we're leaving some performance on the table there potentially though I didn't do those measurements yet. If desirable I can move those changes into a different PR.

Jasper-Bekkers commented 2 years ago

After some thought, another option would be to publicly expose the std::slice::Iter for values directly, it would signal the same thing except that one wouldn't be as easily inclined to index into it (though still possible through nth).

orlp commented 2 years ago

Sorry for the late reply, this kind of slipped. I took a look at your pull request, which contains two separate things (which really should be separate):

  1. Making Values iterator for DenseSlotMap not depend on the key type.
  2. Adding a slice method for values on DenseSlotMap.

I don't think I want to do (1) because it can't be done for SlotMap. Making this change reduces interchangeability between SlotMap and DenseSlotMap. It would also be a backwards-incompatible change so would have to wait until slotmap 2.0.

I'm a bit hesitant to add (2) because it might lead to bad assumptions, but I do recognize the usefulness. If I were to add it, I think I would add two methods, as_slices(&self) -> (&[K], &[V]) and as_mut_slices(&mut self) -> (&[K], &mut [V]) to DenseSlotMap.