Use of "as" idiomatic?

community
1

I'm playing around with trying to create both maximally efficient and maximally idiomatic Rust implementations for the book, "Intro to Algorithms, Thomas H. Cormen et al" as a way to learn Rust for myself as well as a way to provide some learning resources for others. In implementing something simple like "Insertion Sort" I found myself needing to use "as" to cast between usize and isize in order to follow the example algorithm as closely as possible with that given in the book. My question is, is this sufficiently idiomatic?

I came up with a solution that uses "slice.swap" instead that seems more idiomatic, but, is less efficient. What's the opinion of the experts? Is there a more idiomatic, yet, also more efficient way to do this?

Here is the way using "as casts":

pub fn sort_slice_mut<T: Ord + Copy>(slice: &mut [T]) {
	for j in 1..slice.len() {
		let key = slice[j];
		let mut i = (j - 1) as isize;
		while i >= 0 && slice[i as usize] > key {
			slice[(i + 1) as usize] = slice[i as usize];
			i -= 1;
		}
		slice[(i + 1) as usize] = key;
	}
}

Here is what I think is more idiomatic, but, slightly less efficient:

pub fn sort_slice_mut_2<T: Ord + Copy>(slice: &mut [T]) {
	for j in 1..slice.len() {
		for i in (0..j).rev() {
			if slice[i] > slice[i + 1] {
				slice.swap(i, i + 1);
			}
		}
	}
}

Is there anything else I should be considering to make either of the above example even more idiomatic (without taking away the opportunity to actually implement the algorithm)?

2

(disclaimer: not an expert)

I'd try to make i a usize and avoid the casting, and work the logic to handle the zero case. Here's a (verbose) version of the same logic (playground):

pub fn sort_slice_mut<T: Ord + Copy>(slice: &mut [T]) {
    for j in 1..slice.len() {
        let key = slice[j];
        let mut i = j - 1;
        loop {
            if slice[i] > key {
                slice[i + 1] = slice[i];
            } else {
                slice[i + 1] = key;
                break;
            }

            if i > 0 {
                i -= 1;
            } else {
                slice[0] = key;
                break;
            }
        }
    }
}

Once the logic works with the type, would try to figure out how to refactor it to be more idiomatic.

3

I tried an implementation like that and couldn't seem to eliminate in an idiomatic way the extra branch/if which seems like it would be less efficient. I thought because the cast between usize and isize are no-ops that there is no efficiency loss, just a slight idiomatic loss. The first example replicates the book's algorithm exactly as near as I can tell and the only reason that the casts are needed is because slices/array indexes must be usize. I strongly feel the 2nd example is more idiomatic, but, which should be given as the "Best" example of this for Rust? I could include the 3rd option (like you've proposed above) as well, but, I think the 3rd option suffers from both being not that idiomatic as the 2nd and not as efficient as the 1st.

Am I considering the right things? Agree/Disagree?

4

You've given me a lot to think about :upside_down_face:. Definitely agree on those points (which is more idiomatic vs accuracy to the book).

Perhaps to be sure/complete, we could check if compiler optimizations are clever enough to allow us the same efficiency if we use the idiomatic version, and demonstrate by looking at the assembly / with a benchmark, but that's where my experience is quite shallow.

5

You can use checked_sub to capture the semantics of an underflow and write your ocde around it:

pub fn sort_slice_mut<T : Ord + Copy> (slice: &'_ mut [T])
{
	for j in 1 .. slice.len() {
		let key = slice[j];
		let mut i = j.checked_sub(1);
		loop {
			i = match i {
				| Some(i) if slice[i] > key => {
					slice[i + 1] = slice[i];
					i.checked_sub(1)
				},

				| _ => break,
			};
		}
		slice[i.map(|x| x + 1).unwrap_or(0))] = key;
	}
}

In a world with no a prioris I think this version describes slightly better the "semantics" of the program, but:

  • such world does not exist, and since we are all used to transmuting between signed and unsigned integers your code is, in practice, more readable;

  • my code uses Ă’ption<usize> which does not benefit from enum layour optimization and should thus be less efficient than yours;

  • but it does manage to avoid using as :sweat_smile:

1 Like
6

Something using swap (or some other built-in) is definitely more idiomatic, since it allows you to remove the Copy bound.

But really, I'd say the trick is to notice that the inner loop of insertion sort is actually a rotate, and maybe do something like this:

pub fn insertion_sort<T: Ord>(x: &mut [T]) {
    for i in 1..x.len() {
        match x[..i].binary_search(&x[i]) {
            Ok(j) | Err(j) => {
                x[j..=i].rotate_right(1);
            }
        }
    }
}

(That rotate is optimized using unsafe code so it can read out the one item, memmove the rest over, and write the item into its new location.)

8 Likes
7

OK, I've tried the following variations:

pub fn sort_slice_mut<T: Ord + Copy>(slice: &mut [T]) {
	for j in 1..slice.len() {
		let key = slice[j];
		let mut i = (j - 1) as isize;
		while i >= 0 && slice[i as usize] > key {
			slice[(i + 1) as usize] = slice[i as usize];
			i -= 1;
		}
		slice[(i + 1) as usize] = key;
	}
}

pub fn sort_slice_mut_2<T: Ord>(slice: &mut [T]) {
	for j in 1..slice.len() {
		for i in (0..j).rev() {
			let k = i + 1;
			if slice[i] > slice[k] {
				slice.swap(i, k);
			} else {
				break;
			}
		}
	}
}

pub fn sort_slice_mut_3<T: Ord + Copy>(slice: &mut [T]) {
	for j in 1..slice.len() {
		let mut i = j;
		let key = slice[i];
		let mut k = 0;
		while i > 0 && { k = i - 1; slice[k] > key } {
			slice[i] = slice[k];
			i -= 1;
		}
		slice[i] = key;
	}
}

pub fn sort_slice_mut_4<T: Ord>(slice: &mut [T]) {
	for j in 1..slice.len() {
		match slice[..j].binary_search( &slice[j] ) {
			Ok(i) | Err(i) => slice[i..=j].rotate_right(1)
		}
	}
}

And here are the benchmark results:

running 4 tests
test bench_sort_slice_mut ... bench: 132,522 ns/iter (+/- 18,350)
test bench_sort_slice_mut_2 ... bench: 465,862 ns/iter (+/- 94,437)
test bench_sort_slice_mut_3 ... bench: 182,958 ns/iter (+/- 18,680)
test bench_sort_slice_mut_4 ... bench: 67,323 ns/iter (+/- 12,581)

test result: ok. 0 passed; 0 failed; 0 ignored; 4 measured; 0 filtered out

In my opinion, variation 4 benefits greatly from the use of the binary search and is not really expressing the algorithm as given closely enough to qualify as an idiomatic version of the algorithm.

The first variation is nearly exactly the algorithm as given in the book, but, the use of "as" casting makes it so it can only handle slices 1/2 the size of the address space and will not work correctly if the array slice is greater than that. The 3rd variation avoids that problem, but, due to having to perform the extra addition on every iteration of the loop regardless of whether it is the match entry makes it perform about 30% worse. The 2nd variation is fairly idiomatic without relying on another optimization algorithm like the 4th, but, performs extremely poorly in comparison to the others.

Would it be best to show all these variations and analyze the differences for someone trying to learn Rust, or, are some of the variations too advanced for the first Chapter of this book? I'm on the fence about it. Thoughts?

1 Like
8

If you're concerned about the binary search, rewrite it using rposition.

Slices are only allowed to be that long because of how GEP works in LLVM. See from_raw_parts in std::slice - Rust

1 Like
9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.