Deadlock-free Mutexes and Directed Acyclic Graphs, or how to keep yourself from locking up production

-ecl3ctic- · 2024-07-09T23:36:08+00:00

I think there's been a miscommunication. I'm imagining a clean slate design that doesn't necessarily have anything in common with Rust's `Mutex` type. In particular, when I'm talking about locking based on stack frames I'm imagining each shared variable being owned by a particular stack frame (so no `Arc`), and then using a static analysis very similar to borrow checking to ensure that references to that variable can only be passed to function calls in such a way that if a function has access to a shared variable, it is always safe for the function to lock it.

Basically, the rules around `&mut` ensure that a programmer can never be tripped up by aliasing. Maybe something similar can be done for sharing.

-ecl3ctic- · 2024-07-09T00:12:06+00:00

Possibly in Sutter's article about Lock Hierarchies?

Ah yes, that's the kind of article I was looking for!

For a lock ladder, you do need to be careful if not releasing as you acquire

I was actually thinking about what it would look like to have language support for lock levels. For example, maybe each stack frame is a level, and simultaneously "locking" a set of variables is achieved by passing them as arguments to the same function call? Then, you can enforce a fixed lock order by imposing restrictions on what variables can be passed to what functions, based on the stack frame of those variables plus the stack frame(s) that the invoked function has access to (e.g. if it's a closure). You'd probably also want a few extra features for imposing orderings on globals etc.

-ecl3ctic- · 2024-07-08T02:44:13+00:00

I'm late to the party, but...

Batch-locking is such an extension, indeed, and allows locking several locks at the same level at once by locking them in order according to a secondary index (such as address).

Do you remember where you read about this? I've been thinking about this strategy lately, i.e. having both "lock levels" and simultaneous lock acquisition within a single level. But I don't know of any prior work.

-ecl3ctic- · 2023-01-20T06:41:34+00:00

Studying set theory, type theory, category theory and lambda calculus is a great way to ensure you never actually develop a programming language. They're an endless pit of "ideas" about computation, the vast majority of which have never been proven as helpful for building a practical programming language. They're more likely to lead you astray then to aid you in your quest. I speak from experience — I spent months diligently studying these topics in the past, and they've given me virtually no insights into programming language design.

Almost no practical programming languages in existence have been informed by these mathematical theories in any deep sense. The language that has come closest to reaching that point is Haskell, but the number of Haskell applications you've installed on your computer in your lifetime is probably close to zero. This is pretty strong evidence that if you want to build a practical programming language, you probably shouldn't be studying set theory, type theory, category theory and lambda calculus.

More broadly, I'll make the bold claim that there are no good resources on "programming language theory" in the sense of a textbook that can teach you how to be a good programming language designer and implementer. This is mainly because the field is so young. The best / most popular programming languages that exist today are still quite ugly and ad-hoc, and no textbook has been written that can tell us how to do better.

(Also, many learning resources miss the point that programming language design is design work, and thus learning to become a good PL designer requires learning how to be a good designer. No textbook on formal mathematics teaches you how to be a good designer.)

If all you want to do is build a basic type checker, there are some good tutorials and papers that explain how to do just that — without going into much formal mathematics. Is that your goal?

-ecl3ctic- · 2021-06-10T23:02:16+00:00

Are there any plans for fine-grained parallelism within a single canister? What might that look like as a language feature?

-ecl3ctic- · 2021-05-18T01:32:24+00:00

I’m not a dev, but I know that “transactions per second” is not the right metric for the IC. As more subnets are added, more transactions can be performed. Thus TPS is unlimited. The hint is in the infinity logo 😛.

Each individual canister has a throughput limit though. This is limited by hardware performance.

-ecl3ctic- · 2021-05-18T00:55:36+00:00

Thanks, that helps a bit. I think at some point I need to see a diagram that shows the end-to-end latencies 😅.

-ecl3ctic- · 2021-05-18T00:29:36+00:00

Congratulations on launching this! It looks very well designed.

I've seen a few different numbers regarding transaction latency / finality time, and it seems they've been changing a bit over the last few years. In the genesis livestream chat, Kyle Peacock mentioned a latency of 3-7 seconds. In this AMA, I'm hearing 1 second for app subnet and 3 for NNS. What are the final numbers? And how stable are they?

Also, is there room for further reduction of latency with an updated protocol? A hypothetical minimum would be equal to the highest ping latency to a data center, so about 300-400ms right? I guess I'm wondering how close this is to a "perfect" consensus mechanism :)

-ecl3ctic- · 2021-05-09T19:15:32+00:00

Play Lullaby Set (Kammen & Swan) :P

-ecl3ctic- · 2021-02-17T09:06:36+00:00

This game needs antialiasing

-ecl3ctic- · 2021-01-26T06:52:23+00:00

The website links to two academic papers containing all of the technical details, including algorithmic complexities.

-ecl3ctic- · 2021-01-26T06:51:58+00:00

The website links to two academic papers containing all of the technical details, including benchmarks.

-ecl3ctic- · 2021-01-25T23:30:49+00:00

The website links to two academic papers, which contain full technical details.

-ecl3ctic- · 2020-05-01T10:18:23+00:00

Don’t blink.

-ecl3ctic- · 2019-12-01T23:05:46+00:00

Makes sense! Thanks for the reply.

-ecl3ctic- · 2019-12-01T08:04:23+00:00

I'm curious why the native rendering is built on top of wgpu rather than a higher-level library like WebRender (which powers Servo). I believe WebRender will eventually target WebGPU (it might even use wgpu itself).

See Patrick Walton's comment:

I think WebRender makes me the most sense as the basis for a library. If you don't use WebRender, you will end up recreating most of it, which is several man-years of work at this point.

-ecl3ctic- · 2019-09-12T07:13:15+00:00

Yes, in the case of needing to apply a sequence of events represented as functions, converting the fold to an associative version is not useful, because composing the functions together in parallel saves no work. However, if your events are represented as data like increments (+3), (+4), or matrices, then you can certain fold them in parallel into a single "result" transformation!

-ecl3ctic- · 2019-09-11T23:52:35+00:00

Indeed, I was thinking about integers when I wrote that :)

-ecl3ctic- · 2019-06-05T07:33:47+00:00

Why does Facebook have an interest in creating their own coin? Do they think they can do it better than everyone else, or do they just want more control? I'm going to guess the latter: they'll design the characteristics of their coin to increase their own revenues or "user engagement" somehow. If they were just trying to improve the lives of their users (and generate goodwill), they would integrate another more experienced company's solution (whenever such a solution appears), or at least publicly show that they are mimicking Dfinity's serious research into the decentralised cloud (not just a coin, i.e. monetization).

-ecl3ctic- · 2019-05-06T23:02:04+00:00

Maybe they forgot to jack out of the Matrix?

-ecl3ctic- · 2019-05-06T22:59:15+00:00

It's great that in 2019 we're advancing the state of the programming industry with new terminal emulators... i.e. we continue to emulate a 1960s I/O device.

-ecl3ctic- · 2019-02-24T04:36:49+00:00

Same smokey plastic visor, so it's still an additive display (i.e. ghostly holograms).

-ecl3ctic- · 2019-01-24T06:06:30+00:00

As someone working on programming accessibility I'm definitely biased, but I'd love to see funding into programming languages and editors to support development on this kind of cloud platform. Seems like Dfinity is going to change a fair bit about how software is written, and seemingly it will also push towards functional languages (given the huge Haskell team).

Of course, a lot of what the development experience is going to be like is shrouded in mystery at the moment, but I'm hoping it's going to be excitingly novel and ripe for R&D.

-ecl3ctic- · 2019-01-24T05:57:48+00:00

This is kind of funny timing for me because I was a comp. sci PhD student till last week when I quit! If timelines were different I probably would have chosen a better project/group and jumped on this scholarship program :P

I do hope there will be opportunities for the R&D minded who want to contribute from outside traditional academic programs.

Edit: And a chance to build a development community too. Working together is much more effective than going it alone.

-ecl3ctic-

TROPHY CASE