modulovalue

> 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.

> Pattern types could potentially maybe in the future allow for the compiler to know more details though.

Thanks, I’ll take a look!

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.

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.

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!

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.

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.

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.

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.

NIT: That's not quite correct if your first statement is meant to imply an equality rather than a subset relation.

The idea of an index is more general, as an index can be built for many different domains. For example, B-trees can index monoidal data and inverted indexes are just an instance of such a monoid that a B-tree can efficiently index.

Furthermore, metric spaces (e.g., levenshtein distance) can also be efficiently indexed using other trees: metric trees. So calling inverted indexes just indexes would be really confusing since string data is not the only kind of data that a database might want to support having efficient indexes for.

The university I went to started its math education with groups, which is really unfortunate and they never even mentioned monoids.

Monoids are a key idea in computer science and I think that everyone should know what monoids are. Monoids are EVERYWHERE and once you recognize that you have a monoid you can immediately use known methods to compute over monoids in efficiently (e.g. https://static.googleusercontent.com/media/research.google.c...).

Once you have a certain lattice (I'm leaving out some details), you can solve problems efficiently by known methods (e.g. using dataflow solvers) and automatically have a proof that the solution always terminates.

I really wish that more people took their time to learn these fundamentals and I think this is a wonderful introductory site. I don't mean to offend anyone, but if you've never heard of most of that stuff, then I think that you don't deserve to call yourself a professional programmer. Why? You will reinvent solutions to problems that have been solved before much more efficiently then you will be able to i.e. you're an amateur.

That's a very good point. I wonder about the durability of a paper based solution, but 3d printed rolls might also be suboptimal in that regard. This needs some experimentation.

It's very easy. I'm using the cheapest weighted vest that I could find and it came with blue bags that I've just filled with coins. You don't really need straps to make the weights tight because the money just kind of spreads inside of the bag and doesn't move at all once it's there.

It's on my todo list to 3d print some containers to replace the bags with actual "money rolls" so that I can remove them more easily.

It's a vest that you can fill with stuff to increase the intensity of a workout.

There was a time in my life when my legs started hurting and shaking from muscle atrophy because I was programming too much and moving too little.

I was looking for a way to fix that issue and I didn't want to waste time going to a gym, so I started talking walks with a weighted vest. Walking is nice because you can think while walking and with a weighted vest you don't have to walk for hours for it to have a useful effect on your body.

I'm using euro cents as weights in my weighted vest.

When I started doing this I didn't want to afford dedicated weights as it seemed like a waste of money, but I had many cents saved up from my childhood, which I started to use instead.

I have roughly 15kg in euro cents in my vest and I'm regularly talking walks with it.

To get one kilo you need 435 cents and it turns out that in Germany you can also "buy" coins "for free" at the "Bundesbank", that is, you can exchange actual money for weights without any fees. You give 4 euros and 35 cents and you get a kilo. Once you need the money back, you can also sell those coins back to them for free.

> How do you gain associativity then? At a minimum, you can't throw information away.

That's an interesting perspective that I haven't considered before, thank you.

Now I'm wondering, could we throw away some information in just the right way and still maintain associativity? That is, it doesn't seem like throwing information away is fundamentally what's preventing us from having an associative operation, since we can throw information away and still maintain associativity by, for example, converting each summand to a 0 and adding them, and that operation would be associative. However, we would have thrown all information away, which is not useful, but we would have an associative operation.

I'm still wondering if there could exist an alternative world where efficient addition over decimal numbers that we developers use on a day to day basis is associative. Is that even possible or is there perhaps some fundamental limit that forces us to trade associativity for performance?

It seems to me that non associative floating point operations force us into a local maximum. The operation itself might be efficient on modern machines, but could it be preventing us from applying other important high level optimizations to our programs due to its lack of associativity? A richer algebraic structure should always be amenable to a richer set of potential optimizations.

---

I've asked a question that is very much related to that topic on the programming language subreddit:

"Could numerical operations be optimized by using algebraic properties that are not present in floating point operations but in numbers that have infinite precision?"

https://www.reddit.com/r/ProgrammingLanguages/comments/145kp...

The responses there might be interesting to some people here.

That's where Dart and Flutter shine. Sadly, people discussing Swift/SwiftUI, Kotlin/KMP, and Dart/Flutter often only have surface-level comments that do not address potential issues like these.

Dart's static type system has been designed to avoid such problems.

Not once have I had, or heard of, a performance issue related to the Dart type checker. That's also one of the reasons why hot reload always works as expected.

There's a similar project from Google: https://github.com/flutter/packages/tree/main/packages/rfw

rfw is used by Google's Gemini LLM to generate UI.

rfw runs on the web/android/ios/macos/linux/windows, anywhere where Flutter runs.

There's a similar project at Intel: https://github.com/intel/rohd

It uses Dart instead of Scala.

Are you saying this because r-trees expect a proper metric space, and people have the need to index datasets over non-metric spaces?