OSDev.org

Brendan wrote:So in general, Rust's Options don't avoid branches in the caller but sometimes branches can be optimised out, while for my alternative exits the caller didn't have a branch to optimise out.

Brendan wrote:I'm not dismissing pointers - for that case the flexibility/power of pointers outweigh the "harder to learn" disadvantage; and I can't think of any alternative that isn't worse (for low level programming).

I am dismissing unions - for that case there are no advantages to outweigh the "harder to learn" disadvantage. It's just pure hassle for no sane reason (other than making a compiler's optimiser easier to write).

thepowersgang wrote:(this will possibly get me slightly flamed)

thepowersgang wrote:I prefer the idea of having tagged unions avaliable. Sure they're complex to learn, but the huge benefit is you can annotate that these two fields should NEVER be used at the same time, and the compiler will either compile-time check that each access is valid, or when it can't, emit an assertion to prevent undefined behavior (I guess it's kinda like C++ inheritance and dynamic casting, but with a simpler represenation)

With tagged unions, you communicate to the compiler your intention, and it makes sure that you don't accedentally go against that intention.

Rusky wrote:

Brendan wrote:So in general, Rust's Options don't avoid branches in the caller but sometimes branches can be optimised out, while for my alternative exits the caller didn't have a branch to optimise out.

So in general, your language doesn't catch errors when you do something that could be caught in the type system but sometimes unused structure members can be optimized out, while with tagged unions the language just does what you mean.

Rusky wrote:I'm claiming that unions are also more useful than they are hard. Tagged unions are not about optimization, they are about intent and correctness. Whether you acknowledge it or not, there are useful types that are represented correctly by unions (and polymorphism) and incorrectly by structs. Semantically speaking.

For example, a superset of everything you would represent with a C enum.

Brendan wrote:Note: I'm not necessarily saying that tagged unions aren't worthwhile in theory; only that they fail to detect unsafe usage at compile time. If I could find a way to ensure that unsafe usage is always detected at compile time (including cases involving "pointer to union member" and inline assembly) then I'd be interested in having tagged unions in addition to the structure member co-location optimisation.

enum tagTypes = {
    typeNone = 0
    typeFoo
    typeBar
}

structdef myTaggedUnion = {
    type as tagTypes
    foo as u32              ;Trivial structure member co-location!
    bar as bool             ;Trivial structure member co-location!
}

functiondef setFoo(union as @myTaggedUnion, value as u32) (void) {
    union->type = typeFoo
    union->foo = value
}

functiondef getFoo(union as @myTaggedUnion, badType as exit) (value as u32) {
    if(union->type != typeFoo) {
        exit badType
    }
    value = union->foo
}

functiondef setBar(union as @myTaggedUnion, value as bool) (void) {
    union->type = typeBar
    union->foo = value
}

functiondef getBar(union as @myTaggedUnion, badType as exit) (value as bool) {
    if(union->type != typeBar) {
        exit badType
    }
    value = union->foo
}

functiondef clear(union as @myTaggedUnion) (void) {
    union->type = typeNone
}

functiondef isClear(union as @myTaggedUnion) (result as bool) {
    result = (union->type == typeNone)
}

Brendan wrote:I'm arguing against untagged unions, and you're arguing against untagged unions.

Brendan wrote:Tagged unions are a separate issue. They simply don't work (they attempt to guarantee that unsafe usage will be detected, and then fail to detect unsafe usage).

enum TaggedUnion {
  None,
  Foo(u32),
  Bar(bool)
}

// these are rather redundant as using their contents directly is simpler/more flexible, doesn't require mutable variables, and doesn't use Option

fn setFoo(union : &mut TaggedUnion, value : u32) { *union = Foo(value); }
fn getFoo(union : &TaggedUnion) -> Option<u32> {
    match *union {
        Foo(value) => value,
        _ => None
    }
}

fn setBar(union : &mut TaggedUnion, value : bool) { *union = Bar(value); }
fn getBar(union : &TaggedUnion) -> Option<bool> {
    match *union {
        Bar(value) => value,
        _ => None
    }
}

fn clear(union : &mut TaggedUnion) { *union = None; }
fn isClear(union : &TaggedUnion) -> bool {
    match *union {
        None => true,
        _ => false
    }
}

// 'x is a lifetime; globals can only hold pointers with lifetime 'static, meaning the whole program's lifetime
static mut p : &'static u32;

fn do_something(x : &mut u32) {
    p = *x; // ERROR: x does not live long enough
    *x = 36; // this is fine
}

struct Struct {
    p : &u32
}

// specify that s and x both have the same lifetime, 'r, whatever that is when this gets called
fn do_something_else<'r>(s : &'r mut Struct, x : &'r u32) {
    s.p = x; // good: x will not go out of scope before s
}

fn main() {
    // with other enums in scope that use None, like Option, the type could not be inferred, so let mut t : TaggedUnion = None;
    let mut t = None;

    setFoo(t, 42); // or just t = Foo(42);
    println!("foo = {}", getFoo(f).unwrap()); // just fail!() on None; unwrap will be inlined and optimized out

    t.Bar = false; // ERROR: can't access enum members this way, must use match

    let p;
    let mut s1 : Struct; // type specified for clarity
    match t {
        Foo(ref foo) => {
            // ERROR: foo does not live long enough; reference must be valid for the body of main...
            // ...but borrowed value is only valid for the match
            p = &foo;

            // this is fine because the reference only lives for the body of do_something
            do_something(&foo);

            let mut s2 : Struct;
            do_something_else(&s1, &foo); // ERROR: foo does not live long enough
            do_something_else(&s2, &foo); // this is fine
        }
        _ => {}
    }

    let p2 = &t; // this is fine
}

Rusky wrote:

Brendan wrote:Tagged unions are a separate issue. They simply don't work (they attempt to guarantee that unsafe usage will be detected, and then fail to detect unsafe usage).

In Rust, they guarantee that tagged unions are used safely to the same degree that you can guarantee a ranged integer is used safely, using a combination of pointer lifetimes and scoping. Inline assembly is unsafe anyway, so if it uses a union incorrectly then you know exactly where the problem is. In other cases, it forces all enum member access through a match (basically a glorified switch on the tag):

Rusky wrote:As for "foo and bar", that doesn't seem to come up much in my experience, but Combuster did show some ways to deal with it using tagged unions.

enum tagTypes = {
    typeNone = 0
    typeFoo
    typeBar
}

structdef myTaggedUnion = {
    mutex lock
    type as tagTypes
    foo as u32              ;Trivial structure member co-location!
    bar as bool             ;Trivial structure member co-location!
    asmdata as u64          ;Only used by assembly
}

multitarget setFoo(union as @myTaggedUnion, value as u32) (void) {

    functiondef setFoo(union as @myTaggedUnion, value as u32) (void) {
        acquireMutex(@(union->lock))
        union->type = typeFoo
        union->foo = value
        releaseMutex(@(union->lock))
    }

    asmfunction x86_64 setFoo(union as @myTaggedUnion in rdi, value as u32 in rbx) (void) {
        mov rax,typeFoo << 32
        or rax,rbx
        mov [rdi+offset union.asmdata],rax
    }

    asmfunction x86_32 setFoo(union as @myTaggedUnion in edi, value as u32 in ebx) (void) {
        mov ecx,typeFoo
        mov eax,[edi+offset union.asmdata]
        mov edx,[edi+offset union.asmdata+4]
    retry:
        lock cmpxchg8b [edi+offset union.asmdata]     ;"cmpxchg8b" used as an atomic 64-bit write
        jne retry
    }

}


multitarget getFoo(union as @myTaggedUnion, badType as exit) (value as u32) {

    functiondef getFoo(union as @myTaggedUnion, badType as exit) (value as u32) {
        acquireMutex(@(union->lock))
        if(union->type != typeFoo) {
            releaseMutex(@(union->lock))
            exit badType
        }
        value = union->foo
        releaseMutex(@(union->lock))
    }

    asmfunction x86_64 getFoo(union as @myTaggedUnion in rsi, badType as exit in ebp) (value as u32 in rax) {
        mov rax,[rdi+offset union.asmdata]
        shld rbx,rax,32
        cmp ebx,typeFoo
        je OK
        exit ebp
    OK:
        movzx rax,eax
    }

    asmfunction x86_32 getFoo(union as @myTaggedUnion in esi, badType as exit in ebp) (value as u32 in eax) {
        clr eax
        clr edx
        clr ebx
        clr ecx
        lock cmpxchg8b [edi+offset union.asmdata]     ;"cmpxchg8b" used as an atomic 64-bit read
        cmp edx,typeFoo
        je OK
        exit ebp
    OK:
        movzx rax,eax
    }

}

Brendan wrote:

Code: Select all

mov eax,[edi+offset union.asmdata]

mov eax,[edi+union.asmdata]

Brendan wrote:I don't want to force all enum member accesses through a glorified switch. For example, imagine if you've got some TaggedUnion structures floating around your code (where a switch is needed), plus a linked list of TaggedUnion structures where you know "TaggedUnion.Foo" is used and don't need to check, plus a linked list of TaggedUnion structures where you know "TaggedUnion.Bar" is used and don't need to check.

Brendan wrote:

Rusky wrote:As for "foo and bar", that doesn't seem to come up much in my experience, but Combuster did show some ways to deal with it using tagged unions.

I've just been talking to the project manager. Apparently the QA team noticed some stability issues (on a 2-core test machine with 3 users) and traced it back to race conditions in "myTaggedUnion". The project manager was really worried because the production machine is expected to be a 32 core machine handling 500 or more users, and "myTaggedUnion" is going to get pounded from all directions. Basically; it has to be thread safe and it currently isn't. I also asked the project manager if "both foo and bar" will be needed or not, and they won't know until other parts of the project are done.

embryo wrote:

Brendan wrote:

Code: Select all

mov eax,[edi+offset union.asmdata]

Sorry, but to my opinion the indirect addressing in the code looks a bit unnatural. The offset variable is undefined and then I suppose it is a language keyword, but wouldn't it be more natural to write:

Code: Select all

mov eax,[edi+union.asmdata]

If we remove the extra keyword, then the result looks more like assembly and still is quite clear.

Rusky wrote:

Brendan wrote:I don't want to force all enum member accesses through a glorified switch. For example, imagine if you've got some TaggedUnion structures floating around your code (where a switch is needed), plus a linked list of TaggedUnion structures where you know "TaggedUnion.Foo" is used and don't need to check, plus a linked list of TaggedUnion structures where you know "TaggedUnion.Bar" is used and don't need to check.

Safety, or no glorified switch? Your choice (in fact in Rust it really is your choice- use unsafe). Your example is flawed here because you've incorrectly typed your linked list- if one list contains all Foo and one all Bar than saying they're lists of TaggedUnion is incorrect.

structdef myTaggedUnion = {
    next as @myTaggedUnion  ;Pointer to next structure on linked list
    type as tagTypes
    foo as u32              ;Trivial structure member co-location!
    bar as bool             ;Trivial structure member co-location!
}

Owen wrote:

Brendan wrote:

Rusky wrote:As for "foo and bar", that doesn't seem to come up much in my experience, but Combuster did show some ways to deal with it using tagged unions.

I've just been talking to the project manager. Apparently the QA team noticed some stability issues (on a 2-core test machine with 3 users) and traced it back to race conditions in "myTaggedUnion". The project manager was really worried because the production machine is expected to be a 32 core machine handling 500 or more users, and "myTaggedUnion" is going to get pounded from all directions. Basically; it has to be thread safe and it currently isn't. I also asked the project manager if "both foo and bar" will be needed or not, and they won't know until other parts of the project are done.

Why is there a race condition?

Owen wrote:Good languages don't let you write race conditions (Rust doesn't let you write race conditions)

Brendan wrote:If race conditions aren't possible; then lock-free and block-free algorithms aren't possible either. In that case it's not a good language, it's an unusable language.

Rusky wrote:

Brendan wrote:If race conditions aren't possible; then lock-free and block-free algorithms aren't possible either. In that case it's not a good language, it's an unusable language.

They're only impossible without unsafe blocks. The standard library currently has message passing, shared immutable refcounted data, and mutex-protected shared mutable data, based on unsafe blocks in functions that expose interfaces that, because of the type system, are impossible to create races with. Just wrap your lock-free implementation in unsafe blocks behind a similar interface.