Modular•2mo ago

Is there any mutex available in the stdlibs?

Searched for mutex in the docs and it looks like it's not available yet. Is there a way I can atomically perform multiple ops or do the following with the atomic package? I want to perform an increment on an int, followed by a modulo which should round the number back to 0 after a certain limit and return the value.

43 Replies

Darkmatter•2mo ago

What is the limit?

sazidOP•2mo ago

user configurable but should be within 2^10

Darkmatter•2mo ago

What is this being used for?

sazidOP•2mo ago

struct IdGenerator:
    var current_sequence: Atomic[DType.int64]

    fn generate_next_sequence(inout self) -> Int64:
        # TODO: Need to handle max value for sequence.
        var result = self.current_sequence.fetch_add(1)
        return result

struct IdGenerator:
    var current_sequence: Atomic[DType.int64]

    fn generate_next_sequence(inout self) -> Int64:
        # TODO: Need to handle max value for sequence.
        var result = self.current_sequence.fetch_add(1)
        return result

I'm trying to write a small lib for 'id' generation which should be thread safe. In this case, the generate_next_sequence is where I would like to use the mutex or any other approach if possible.

Darkmatter•2mo ago

Why do you need the ID to roll over? Also, if you use inout won't be able to call this from multiple threads at once.

sazidOP•2mo ago

Snowflake ID - if you're familiar Basically a way to generate distributed unique ids. There are three parts to the ID which can be stored in a 64-bit integer. First 41 bits contain the timestamp and next 12 and 10 (both user configurable) holds a sequence. The last 10 bits will contain the generated sequence - which is the problem I'm trying to solve.

Snowflake ID

Snowflake IDs, or snowflakes, are a form of unique identifier used in distributed computing. The format was created by Twitter (now X) and is used for the IDs of tweets. It is popularly believed that every snowflake has a unique structure, so they took the name "snowflake ID". The format has been adopted by other companies, including Discord and...

ModularBot•2mo ago

Congrats @sazid, you just advanced to level 1!

sazidOP•2mo ago

It's usually safe to roll over the sequence part of the id to 0 once it reaches the max value because by then, a microsecond will have passed unless the id generation speed is too fast. oh okay, will it help if I share the full code - if you have time to take a quick glance? btw does this mean, in a multi-threaded environment, the lifetime checker will force me to have only exclusive access to this method?

Darkmatter•2mo ago

Can't you just use a mask?

struct IdGenerator[user_bits: UInt]
    var current_sequence: Atomic[DType.int64]

    fn generate_next_sequence(borrowed self) -> Int64:
        constrained[user_bits == 10 || user_bits == 12, "Invalid number of bits for sequence"]
        # TODO: Need to handle max value for sequence.
        var result = self.current_sequence.fetch_add(1)
        result = result & ((1 << Self.user_bits) - 1)
        return result

struct IdGenerator[user_bits: UInt]
    var current_sequence: Atomic[DType.int64]

    fn generate_next_sequence(borrowed self) -> Int64:
        constrained[user_bits == 10 || user_bits == 12, "Invalid number of bits for sequence"]
        # TODO: Need to handle max value for sequence.
        var result = self.current_sequence.fetch_add(1)
        result = result & ((1 << Self.user_bits) - 1)
        return result

If you use borrowed that goes away. I fixed it in my example

sazidOP•2mo ago

ooh, nice! thanks

sb•2mo ago

Do we need a mutex next?

sazidOP•2mo ago

isn't there still a little possibility that by the time the Atomic count is incremented and the result is calculated with the mask, the current_sequence may have changed?

Darkmatter•2mo ago

We have util.lock. Yes, but that doesn't matter, you already have your value. The next person who calls the function gets their value.

sazidOP•2mo ago

oh yes!

Darkmatter•2mo ago

That's how atomics work.

sazidOP•2mo ago

yes got it, thanks a ton!

Darkmatter•2mo ago

Please mark the question answered

sazidOP•2mo ago

didn't know about the constrained, that's neat... a small update: the fetch_add requires inout which is why the method itself needs to have inout.

ModularBot•2mo ago

Congrats @sazid, you just advanced to level 2!

sb•2mo ago

fetch_add shouldn't require inout?? What is the signature for atomic?

sazidOP•2mo ago

sazidOP•2mo ago

it's taking inout self https://docs.modular.com/mojo/stdlib/os/atomic/Atomic#fetch_add

sb•2mo ago

That seems....wrong?

sazidOP•2mo ago

in the docs, except for static max and static min, all the methods look like they're taking inout on self

sb•2mo ago

Interesting....I wonder if we got Arc wrong because of this @Owen Hilyard I'm on mobile rn, is that stuff taking inout sensical to you?

Darkmatter•2mo ago

No, it is not

sb•2mo ago

Awesome, I'm not (entirely) crazy then How does Arc even work here then... Arc might expose a rather uh...hm.... Good catch @sazid, I gotta dig into this

sazidOP•2mo ago

Nice, glad that I was able to help spot a bug. Just out of curiosity, are atomics not supposed to be inout because they will always be in a consistent state no matter the operations that are applied - read/write?

Darkmatter•2mo ago

Yes, atomics are supposed to have "interior mutability" meaning they can be safely mutated with an immutable reference.

sazidOP•2mo ago

i see, thanks for the clarification

sb•2mo ago

huh, I completely passed this by! Arc uses inout a bunch. Doesn't inout imply that it can't alias? I thought it implied "exclusive ownership passes in and back out again"

Darkmatter•2mo ago

Yes, inout = &mut

sb•2mo ago

🙃

sora•2mo ago

PR time

sb•2mo ago

this seems wrong to me, though some stdlib team peeps would probably know better than me

Darkmatter•2mo ago

I think that means something very wrong in std. Or the compiler is smart enough to recognize that it's all single threaded and not bother.

sb•2mo ago

it isn't single threaded this is in Arc

sb•2mo ago

those methods get called from potentially multiple threads

Darkmatter•2mo ago

Do we have a way to launch other threads? That is actually tested with Arc?

sb•2mo ago

not that I've seen so far, I think it's just in parallel or something? not at all Arc is tested only as an Rc currently though I designed my Weak thing to be sound in the face of multiple threads, except for the inout thing

sora•2mo ago

I think it's simply because there's no easy way to launch another thread to encounter this problem

sb•2mo ago

Does parallelize or whatever hit on this?

Gaming

Programming

Is there any mutex available in the stdlibs?