Found a cheaty way to get sub 1s:

    fn defrag2(p0: &mut [i64]) {
        let mut i = *p0.last().unwrap();
        while i > 3000 {  // Stop defragging here, probably cant find free spots after this point
            let (old_pos, size) = find_file(p0, i);
            if let Some(new_pos) = find_slot(p0, size, old_pos) {
                move_file(p0, i, size, old_pos, new_pos);
            }
            i -= 1;
        }
    }

Might be possible to correctly do this in the find_slot code, so that if it fails to find a slot, it never searches for that size again.

edit:

fn defrag2(p0: &mut [i64]) {
        let mut i = *p0.last().unwrap();
        let mut max_size = 10;
        while i > 0 {
            let (old_pos, size) = find_file(p0, i);
            if size <= max_size {
                if let Some(new_pos) = find_slot(p0, size, old_pos) {
                    move_file(p0, i, size, old_pos, new_pos);
                } else {
                    max_size = size - 1;
                }
            }
            if max_size == 0 {
                return;
            }
            i -= 1;
        }
    }

500ms, I can go to sleep now.