`sort_unstable` in native and wasm

help
1

I'm curious if I compile it to native and wasm. I'll get the same ouput?

I'm building a substrate chain. And today, I found one storage op is different.

The sorted value of native and wasm's are diffierent (All the elements are same but with diffierent order). Is that reasonable?

2

I think you shouldn't even assume that you'll get consistent results from the exact same compilation, running multiple times. For example, regardless of the current actual implementation, an unstable sort could use a random pivot point for partitioning.

2 Likes
3

But the wasm runtime code can always pass the checking then start syncing the blockchain.

So I think one input always get the only one output.

Codes here: https://github.com/paritytech/substrate/blob/master/frame/staking/src/lib.rs#L2892

4

I wouldn't count on it. Use the stable sort if you need consistency.

1 Like
5

For types that equal types are literally equal, like primitive integers, .sort() and .sort_unstable() would produces same sorted list - since every possible sorted list are literally equal. For more complex types where equal doesn't implies bitwise equality, you can't use .sort_unstable() if the actual order of equal types matter.

1 Like
6

Yes.

I'm sry, the link is use sort_unstable_by. The target is a struct list.

7

But the question is whether equality of these structs covers all of their members. The below struct, for example, can be used with sort_unstable, and you will get consistent results*.

#[derive(Eq, Ord, PartialEq, PartialOrd)]
struct Item {
    a: u32,
    b: u32,
}

What we're worried about is structs that don't actually define a total order. Something like this, for example,

struct Item {
    a: u32,
    b: u32,
}
impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        // notice that `self.b` is ignored
        PartialOrd::partial_cmp(&self.a, &other.a)
    }
}
impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        // notice that `self.b` is ignored
        Ord::cmp(&self.a, &other.a)
    }
}
impl PartialEq for Item {
    fn eq(&self, other: &Self) -> bool {
        self.a == other.a
    }
}
impl Eq for Item {}

* padding doesn't count; you're not supposed to read that anyway

1 Like
8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.