More powerful SortableBy trait?

[dbregman]

This is the current trait:

pub trait SortableBy<O: ?Sized + TotalOrder> {
    fn sort_key(&self) -> &O::OrderedType;
}

If instead it was:

pub trait SortableBy<O: ?Sized + TotalOrder> {
    fn sort_key(&self, &O) -> &O::OrderedType;
}

Then sort_key() could lookup the key based on anything accessible through O. This would allow the actual keys to not be owned by the collection, for example they could be dynamically loaded thru a cache or a memory mapped file. The "key" type stored in the collection can just be some kind of indexing data which may be very small compared to the real keys.

This is actually what I was hoping this crate did when I searched for it. Anyone know if something similar exists? Otherwise, perhaps the idea could be useful here. I have not spent any time looking at how feasible this is, but I thought it could be worth mentioning.

[eggyal]

Rather than changing the signature of sort_key, which would make the trait that bit more difficult/confusing for most users (albeit not by much!), we could just add a new SortableByWithOrder trait or similar, blanket-implemented for all types that implement the existing SortableBy trait.

Then users can choose which of the two traits they wish to implement; copse would always call the new "with order" trait (whereupon the blanket impl will delegate to the existing trait if that is the one that has been user implemented).

In any event, I've done that in 18e5122, which you can use right away with the following added to your Cargo.toml:

[patch.crates-io]
copse = { git = "https://github.com/eggyal/copse" }

It really just needs some tests and documentation (PRs welcome!) and then it can be released, I think just a patch (because we're pre-1.0).

[dbregman]

In any event, I've done that in 18e5122, which you can use right away with the following added to your Cargo.toml:

That's awesome you found an easy way to implement it and I appreciate that you got it added so quick. I'll check this out as soon as I get a chance. Thanks!

[dbregman]

I just got around to writing a test for the new code. I ran into a lifetime issue with the signature of sort_key_with_order. The lifetime doesn't allow borrowing from O which is what I'm trying to do. I used an unsafe hack to bypass for testing and it seems to work otherwise.

here's my code [Click to expand]

fn copse_test() {
	use common::rand;
	use copse::{SortableByWithOrder, TotalOrder};
	use std::cmp::Ordering;
	use std::sync::atomic::{AtomicUsize, Ordering as MemOrdering};
	use std::sync::Arc;

	static COMPARISON_COUNT: AtomicUsize = AtomicUsize::new(0);

	// define a total order
	struct OrderByIndexedKeys {
		key_size: usize,
		keys: Arc<Vec<u8>>,
	}

	fn extend_lifetime_hack<'b>(slice: &'b [u8]) -> &'static [u8] {
		unsafe { std::mem::transmute::<&'b [u8], &'static [u8]>(slice) }
	}

	fn extract_key(bytes: &[u8], key_size: usize, idx: usize) -> &[u8] {
		&bytes[idx * key_size..(idx + 1) * key_size]
	}

	impl OrderByIndexedKeys {
		fn get_key(&self, idx: usize) -> &'static [u8] {
			extend_lifetime_hack(extract_key(&self.keys.as_slice(), self.key_size, idx))
		}
	}

	impl TotalOrder for OrderByIndexedKeys {
		type OrderedType = [u8];
		fn cmp(&self, left: &Self::OrderedType, right: &Self::OrderedType) -> Ordering {
			COMPARISON_COUNT.fetch_add(1, MemOrdering::SeqCst);
			left.cmp(right)
		}
	}

	// define lookup key types for collections sorted by our total order
	impl SortableByWithOrder<OrderByIndexedKeys> for usize {
		fn sort_key_with_order(&self, order: &OrderByIndexedKeys) -> &[u8] {
			order.get_key(*self)
		}
	}
	impl SortableByWithOrder<OrderByIndexedKeys> for [u8] {
		fn sort_key_with_order(&self, _order: &OrderByIndexedKeys) -> &[u8] {
			self
		}
	}
	impl SortableByWithOrder<OrderByIndexedKeys> for str {
		fn sort_key_with_order(&self, _order: &OrderByIndexedKeys) -> &[u8] {
			self.as_bytes()
		}
	}
	impl SortableByWithOrder<OrderByIndexedKeys> for String {
		fn sort_key_with_order(&self, _order: &OrderByIndexedKeys) -> &[u8] {
			self.as_bytes()
		}
	}

	use rand::RngCore;
	let mut rng = rand::thread_rng();

	let mut v = Vec::new();
	let key_count = 40;
	let key_size = 128;
	v.resize(key_count * key_size, 0);
	for x in v.iter_mut() {
		*x = (rng.next_u32() % 26) as u8 + b'A';
	}

	let v = Arc::new(v);
	let order = OrderByIndexedKeys { key_size, keys: v.clone() };
	let mut set = copse::btree_set::BTreeSet::new(order);

	let key_count = v.len() / key_size;
	for i in 0..key_count {
		if rng.next_u32() & 1 == 1 {
			set.insert(i);
		}
	}

	let n = set.len();
	let cmp_count = COMPARISON_COUNT.load(MemOrdering::SeqCst);

	for i in 0..key_count {
		assert_eq!(set.contains(&i), set.contains(extract_key(v.as_slice(), key_size, i)));
	}

	for &i in set.iter() {
		let key = std::str::from_utf8(extract_key(v.as_slice(), key_size, i)).unwrap();
		println!("{}->{}", i, key);
	}

	println!(
		"sorted {} items with {} comparisons ({:.2}x of n*log(n))",
		n,
		cmp_count,
		(cmp_count as f32) / ((n as f32) * (n as f32).log2()),
	);
}

(EDIT: made long code collapsible)

[eggyal]

Oops. I've fixed that in 17f6dc2.

By the way, in your example you can actually impl SortableBy<OrderByIndexedKeys> for the types that don't require order ([u8], str and String), saving you from including the (unused) _order arguments.

[dbregman]

Thank you I confirm the lifetime issue is fixed, and good to know regarding the types that don't require order.

[dbregman]

Trying to use it in practice now and I'm running into the issue that I would like to update the order after creation.
Adding accessors like get_order and get_order_mut could be a good solution, I think.

The only other solution I can think of would be that the data used for sorting is not owned exclusively by the order, meaning Rc<RefCell<>> or Mutex etc.
Or passing the order to every operation, but I don't think you would like to change the API like that.

[dbregman]

Sorry, I should have been more specific: I need to update the order to add new items, not to change comparisons for existing items.

[eggyal]

Ah, got you.

I don't have any issue at all with copse's collections providing a get_order accessor through which one can obtain a shared reference to the ordering. But if you're okay with interior mutability, then you could pass an Rc of your ordering into copse's collections so that you can retain other handles onto it outside of the collection (negating any need for the accessor method, at the negligible cost of a heap allocation and refcount updates).

Returning an exclusive/mutable reference is much more dangerous, for the reasons given above. If copse is to provide a get_order_mut accessor, I'm more inclined for it instead to return a guard type that mutably derefs to the order; on drop, that guard can then update the collection so that it is sorted by the modified order. But that could be pretty costly, especially for larger collections.

I think only with that in place would I feel comfortable offering a get_order_mut_unchecked or similar that returns an &mut directly, as the different API will clearly emphasise the caller's responsibility to uphold the ordering's invariants.

[dbregman]

I attempted to use the Rc<RefCell<>> pattern and I could not even get it to work. When writing the body of sort_key_with_order, I cannot return something borrowed from a RefCell because it doesn't have the correct lifetime (it's borrowed from the RefCell Ref<> guard which doesn't live past the end of the function).

Is there a way to do it that I missed?

The workaround I came up with is to use a raw pointer and unsafe dereference:

code [Click to expand]

fn copse_test() {
	use common::rand;
	use copse::{SortableBy, SortableByWithOrder, TotalOrder};
	use std::cmp::Ordering;
	use std::sync::atomic::{AtomicUsize, Ordering as MemOrdering};

	static COMPARISON_COUNT: AtomicUsize = AtomicUsize::new(0);

	// define a total order
	struct MyOrder {
		key_size: usize,
		keys: Vec<u8>,
	}
	struct MyOrderPtr {
		inner: *const MyOrder,
	}
	impl MyOrder {
		fn get_key(&self, idx: usize) -> &[u8] {
			&self.keys.as_slice()[idx * self.key_size..(idx + 1) * self.key_size]
		}
	}
	impl TotalOrder for MyOrderPtr {
		type OrderedType = [u8];
		fn cmp(&self, left: &Self::OrderedType, right: &Self::OrderedType) -> Ordering {
			COMPARISON_COUNT.fetch_add(1, MemOrdering::SeqCst);
			left.cmp(right)
		}
	}

	// define lookup key types for collections sorted by our total order
	impl SortableByWithOrder<MyOrderPtr> for usize {
		fn sort_key_with_order<'a>(&'a self, order: &'a MyOrderPtr) -> &[u8] {
			unsafe { (*order.inner).get_key(*self) }
		}
	}
	impl SortableBy<MyOrderPtr> for [u8] {
		fn sort_key(&self) -> &[u8] {
			self
		}
	}
	impl SortableBy<MyOrderPtr> for str {
		fn sort_key(&self) -> &[u8] {
			self.as_bytes()
		}
	}
	impl SortableBy<MyOrderPtr> for String {
		fn sort_key(&self) -> &[u8] {
			self.as_bytes()
		}
	}

	struct Index {
		order: Box<MyOrder>,
		set: copse::btree_set::BTreeSet<usize, MyOrderPtr>,
	}

	impl Index {
		fn new(key_size: usize) -> Index {
			let order = Box::new(MyOrder { key_size, keys: Vec::new() });
			let order_ptr = MyOrderPtr { inner: order.as_ref() };
			Index { order, set: copse::btree_set::BTreeSet::new(order_ptr) }
		}
		fn insert(&mut self, key: &[u8]) -> bool {
			assert!(key.len() == self.order.key_size);
			self.order.keys.extend(key);
			self.set.insert(self.set.len())
		}
	}

	use rand::RngCore;
	let mut rng = rand::thread_rng();

	let key_size = 128;
	let key_count = 40;
	let mut index = Index::new(key_size);

	let mut key = vec![0; key_size];
	for _i in 0..key_count {
		for b in key.iter_mut() {
			*b = (rng.next_u32() % 26) as u8 + b'A';
		}
		index.insert(key.as_slice());
	}

	let n = index.set.len();
	let cmp_count = COMPARISON_COUNT.load(MemOrdering::SeqCst);

	for &i in index.set.iter() {
		let key = std::str::from_utf8(index.order.get_key(i)).unwrap();
		println!("{}->{}", i, key);
	}

	println!(
		"sorted {} items with {} comparisons ({:.2}x of n*log(n))",
		n,
		cmp_count,
		(cmp_count as f32) / ((n as f32) * (n as f32).log2()),
	);
}

I think if there was a get_order_mut_unchecked then I could write this code without any unsafe blocks.

[eggyal]

Added in 8b451a4.

[dbregman]

Great! It works and I don't need unsafe anymore.