Access refactoring RFC about bitvec HOT 4 CLOSED

Okay, atomics are still required for this, to write data back once it's done with changing dangling bits, and the actual split should return two different AfterSplits: (One, Other), so their accesses won't overlap, and each part should know, where it should write its dangling bits. Yet, this would strip atomics from all other parts of library. And no possible atomic bottleneck, because just like BitMut those AfterSplits would write it's shared bits only on drop.
While "atomic" feature is off, all split_mut functions could return (&mut self, &mut BitSlice), since BitSlice is not Send-Sync without it, and one-threaded access should be okay.

from bitvec.

Okay so I've been thinking about this all day and you're right in spirit, though as your follow-up comments mention, less so in implementation. This is my fifth draft at a reply, so I'll try to be concise:

• atomic writes are never faster than non-atomic; they are at best as fast as and at worst slower. therefore, on unaliased memory, they should be removed.
• I do not want to diverge from [T] except where absolutely necessary. &mut bool requires a proxy type. slices do not. Changing the split_at_mut API is not something I will do without very strong evidence that atomics are intolerable and there is no better option
• but I have one. The domain module fractures a slice into its aliased edges and unaliased center.

We can encode that a particular slice has an unaliased view to memory in its T: BitStore parameter by creating a wrapper type over the store integers that unconditionally uses Cell for memory access. We can add a method to BitSlice to produce such deätomized slices using domain, and change the methods that affect aliasing (ctors are mostly unaliased; splitters are always aliased) to add or remove that wrapper.

I've been working on doing exactly this. It's a lot of boilerplate, mostly in trait forwarding, but I think once done it should be able to make this work without severe external effects.

Thank you for bringing this to my attention; indexed access is important to keep performant and this is a strong opportunity to do so.

from bitvec.

Wow it's only been a month? For some reason I thought this was filed earlier in January.

Okay. So. This has been a nightmare of a feature to actually implement.

Summary:

This program

extern crate bitvec;

use bitvec::prelude::*;

fn main() {
  let mut raw = [0u8; 3];
  let bits = raw.bits_mut::<Local>();
  let (left, _right) = bits.split_at_mut(12);
  match left.bit_domain_mut() {
    BitDomainMut::Region { body, tail, .. } => {
      body.set(4, true);
      tail.set(2, true);
    },
    _ => unsafe{std::hint::unreachable_unchecked()},
  }
}

produces this output

bitvec::main:
    push   rax
    mov    word, ptr, [rsp, +, 6], 0
    mov    byte, ptr, [rsp, +, 5], 16
    lock   or, byte, ptr, [rsp, +, 6], 4
    pop    rax
    ret

You can observe that this writes a zero into [6] (initializing the middle byte), then a sixteen into [5] (body.set(4, true)), then a lock or of [6] with 4 (tail.set(2, true)).

The default behavior has been moved back from atomic to ordinary accesses. The methods that cause aliasing of memory elements contaminate their entire slices with an aliasing marker, which causes all accesses through tainted slices to use atomic access, even when unneeded. This is because switching instructions once is faster than performing an alias detection check on every write.

To untaint a slice, use the .bit_domain_mut() method to get access to three slices: two aliased, and restricted to only the aliased element, and one unaliased, covering all the unaliased elements.

You now have full control over whether an access may be unaliased, or must be aliased.

This feature is currently only available on branch feature/47-noalias. When I am satisfied with the code quality and also implementation correctness in Miri, I will merge it into master, close this issue, and cut the 0.18 release.

I have added an example file, examples/aliasing.rs. Please let me know if the example of how to operate the new behavior is sufficient, and if the type system rules on display there are acceptable or painful to use. In generic contexts, the alias markers are deeply unpleasant, but in instantiated contexts, they are easy to drag back to the specific integer or atom required.

Thank you again for this issue. I am happy to have a community of users pushing bitvec to continually be better.

I am probably going to stop working on it for a month or so once 0.18 is published.

from bitvec.

This behavior is now present in trunk. I will issue an 0.18 that includes it by this Saturday at the latest.

from bitvec.