modulovalue
Joined 7 years ago
Karma
159
Submissions
32
Member since
Sep 25
http://twitter.com/modulovalue
modulovalue.com
View on Hacker NewsRecent submissions
Comment · 2 days ago
> Maintaining the sizes of subtrees
Something that's not mentioned in that article is that you can maintain any monoid efficiently over balanced trees, not just the subtree size (aka you need an identity element and an associative operation). Most widely known monoids are boring, but there are more interesting monoids. Interval trees can be implemented as an augmentation using a monoid (this concept is more widely known as augmenting a tree). Range min max augmentations can be used to implement succinct trees (this comes from Sadakane's work on succinct trees, he didn't describe it as a monoid IIRC, but it turns out it is one).
By looking at it from a monoid angle, the specific balanced tree can be abstracted away. Treaps are VERY easy to implement, but the monoids apply to any n-ary balanced trees. There was an article a few days ago about very efficient B-Trees, but from what I've seen they did not support general purpose augmentations, probably because the implementation would have to be partially evaluated to be optimal while being general.
In any case, cool stuff and totally under-explored in my opinion. I hope LLMs will help us become optimal in this area one day and help us automatically select an optimal augmentation and balanced tree. There are so many problems that can be sped up by balanced trees and augmentations.
Comment · 1 month ago
> Pattern types could potentially maybe in the future allow for the compiler to know more details though.
Thanks, I’ll take a look!
Comment · 1 month ago
I’m not sure I agree on the impossible part, I feel like a sufficiently smart interprocedural analysis that also implements range analysis interprocedurally could prove a lot to where it becomes useful.
I guess what I would like to see is SIMD libraries being able to confidently say nobody needs to use intrinsics (or differentiate between relaxed/normal SIMD on the user API level) because the language + high level SIMD APIs are smart enough to choose the right implementation.
IIRC IEEE min/max with proper NaN handling needs 8 instructions on x86 vs 1 on arm64 I find it very sad that we apparently haven’t really solved that yet without forcing the user to use different APIs.
Comment · 1 month ago
I’m currently working on adding better SIMD support to Dart (https://github.com/dart-lang/sdk/issues/64170) and I have a question for the author or others here.
Does Rust or any other language support customizing the compiler so that interprocedural analyses can track custom subsets of, for example, doubles so that the compiler can choose the most efficient instruction sequence for example for min/max? If we know a double is never NaN then we can emit only one instruction on x86, but have to emit one more on arm64. If we know a double is never zero and never NaN, we can emit a single instruction on both.
This whole conversation between relaxed SIMD and deterministic SIMD seems to only exist because our compilers are not smart enough and/or their whole program analyses don’t support any plugin-like capabilities.
There are other examples where if we know a SIMD bitmask is canonical (all 1s per lane) then we can implement horizontal reductions more efficiently. This is very niche and I doubt that any language supports interprocedural analyses with such a rich domain, so it feels like a hole in the programming language space.
Comment · 3 months ago
I built something similar, but I managed to compile the Dart VM, its compiler and the static analyzer to wasm using emscripten:
- repo: https://github.com/modulovalue/dart-live
- demo: https://modulovalue.com/dart-live/
It's on my todo list to support compiling dart code through the wasm bundle to wasm directly. Right now it's running the dart arm simulator on the web because it supports hot reload.
I'm wondering if there are any cool use-cases that motivate having the compiler itself run in wasm. I did it mostly for fun and besides building tooling for compiler developers themselves or IDEs, I can't come up with much.
There was one guy that wanted a sandboxed environment for agents as he couldn't find anything else. A few other people used the dart live project to build playgrounds for their own packages.
Who's the target audience for minikotlin? I'm just curious.
In any case, cool project, thanks for sharing!
Comment · 3 months ago
I'm working on making SIMD better in Dart. Dart supports RISC-V as a target architecture for compilation, but I'm not really excited about figuring out how to map the wasm-SIMD-style primitives to RISC-V's RVV and so I don't really plan to look into it at all.
This is mostly because their approach to SIMD is so different, but also because I can't test it at all. Are there any RISC-V "machines"? that one can use to do something useful or fun with that someone here could recommend?
I guess it would be fun seeing all my SIMD-fiable use-cases become orders of magnitude faster on RISC-V, too, but I sadly never hear anything about machines that use RISC-V.
Comment · 4 months ago
It's already a breakthrough in my opinion.
Many things are possible that weren't possible before. For example, I was able to compile the Dart VM (the compiler + analyzer + VM) to wasm and run it on the web: https://github.com/modulovalue/dart-live it supports hot reload and many other cool features. It runs essentially everywhere and it's a very bare proof of concept for a fully integrated programming development system.
The problem is that things just take time if you have to coordinate across a bunch of languages and teams while trying to make everyone happy.
To give you a sense of what else is coming: the wasm ecosystem is moving towards supporting a component model. Eventually you'll be able to import any piece of code from any programming language that supports it. Wasm interface types will make that possible.
Comment · 7 months ago
There's an important issue with async iterables: what's the initial value of derived "signals"?
In the Dart/Flutter world, async iterables are known as streams. The biggest problem is that they are asynchronous so if you derive new streams from existing streams, you won't have a value immediately for those streams available, you'll have to wait a frame for values to propagate. That's not a problem if you're just processing data, but if you're using them in a UI framework and your UI framework is coupled to the event loop, then you have a problem.
This doesn't happen with the ReactiveX approach because things are evaluated immediately, one doesn't have to wait for the event loop to tick. (A fun historical artifact is that ReactiveX has not caught on in the Dart/Flutter community around 2019-ish because it was eventually migrated to use Streams and the initial-value-problem was a real problem that made the benefits of ReactiveX not carry its weight nobody noticed that but I was heavily involved and I am still using a custom framework derived from my observations back then).
If we zoom out a bit, the problem is actually that we are trying to define a computation graph and then need a strategy for evaluation it. I think Elm has actually made the biggest progress on that front (here's THE talk on that topic that shows how complicated working out all the kinks can be: https://www.youtube.com/watch?v=Agu6jipKfYw)
I still think that functional reactive programming solves most of the problems we have in UI-land, but the complexity that we have to deal with when we use traditional methods of state mutation, that complexity becomes enormous when trying to define a reactive programming framework, especially in languages that are not purely functional.
I think in 10 or 20 years there will be somebody that solves this problem, I don't see it happening anytime soon, sadly. It's just too complicated and we need programming languages that are built around those ideas for them to become comfortable enough to be usable in practice.
Comment · 8 months ago
Very interesting, I always believed we should have more declarative frameworks in other domains and not just UI. My experience shows me this gives LLMs a much smaller space to explore which leads to better results.