(I made rkyv) I took a look at lite3/tron because I was interested in seeing how it approached some of the issues I ran into with rkyv. I ended up with some additional information related to points 1 and 2 I figured I'd write down:
1) You're correct, rkyv uses a B-tree with a default branching factor of 6 [1]. I don't think I've ever implemented a binary tree in any version of rkyv - maybe one of the earliest versions used a sorted vec instead of a B-tree? I hate the B-tree map implementation because it is so complicated, even though it actually used to be even worse in 0.7 when it was implemented as a B+ tree. Sorry for making you read any of it!
2) Arbitrary mutations would definitely be an improvement on rkyv, and I was most interested to see what kind of approach lite3/tron took! Unfortunately growing the buffer is not supported [2] and freed memory isn't reclaimed [3]. These are the two actually difficult problems standing in the way of rkyv getting more comprehensive mutation support, so unfortunately I think there's nothing valuable to take away here.
The issue with growing the buffer is that you invalidate any pointers into the buffer and have to manually fix them up (e.g. by re-crawling the buffer). There's not a decent approach I'm aware of which manages these pointer fixups in a way that limits complexity and avoids really nasty API surfaces.
The issue with memory reclamation is that you effectively have to add an allocator to your buffer, and that allocator has to also be persistable. I actually got this part working in rel while that was still a project worth hacking on [4]. I just ran out of steam and willingness to play the type-tac-toe required to get a safe API out of it. The main problem I ran into there was related to value branding, since you shouldn't be allowed to make references to objects which cross between contiguous buffers.
This project is neat, but it does basically just look like an rkyv-converted `BTreeMap<String, JsonValue>`.
I disagree with this assertion. As you said, safety is an attribute of action. We have many of examples of artificial intelligence which can take action, usually because they are equipped with robotics or some other route to physical action.
I think whether providing information counts as "taking action" is a worthwhile philosophical question. But regardless of the answer, you can't ignore that LLMs provide information to _humans_ which are perfectly capable of taking action. In that way, 'AI safety' in the context of LLMs is a lot like knife safety. It's about being safe _with knives_. You don't give knives to kids because they are likely to mishandle them and hurt themselves or others.
With regards to censorship - a healthy society self-censors all the time. The debate worth having is _what_ is censored and _why_.
Mixing milliseconds down to picoseconds made the columns too wide. All of the benchmark data is also available as JSON in the benchmark_results directory if you wanted to drop it into sheets or some other analysis.
Author here, you’re correct. You can customize your validation context for your specific needs. For example, if you don’t have allocation available (i.e. `#![no_std]` without the alloc crate) then you’ll probably need to write your own mapping system to handle shared pointers. Or you can just not use them if that works better for you. That’s also a large part of why rkyv uses generics so heavily.
If your data is read-only then pointing to the same object from two locations is (usually) fine. But rkyv also supports in-place mutability, which requires validating that no two pointers will overlap each other. Otherwise you could have simultaneous mutable borrows to the same value which is UB.
> 6) Morality will degrade. Prostitution, drug use, nihilism, and degeneracy of every sort will explode.
> 7) America’s military will weaken dramatically as the quality of recruits plunges and we no longer have the money to properly maintain and supply our forces.
Tried and true right-wing media strategy: sucker people by talking about economic stress on the middle class (real issue), and gradually transition to moral hand-wringing and pumping the military-industrial complex (fake issues).
> 12) The government will institute a wealth tax. It will be sold as something to target the rich, but in practice, over time, they will be taking large amounts of money from people no one considers rich.
Interesting that they start by talking about how Campbell's soup is expensive and finish by talking about how the real threat is a wealth tax...
If you can't track provenance to un-restrict the pointers because it's infeasible, then you have to give up on at least one of the optimization passes. In this case, the optimizations used are very fundamental and giving up on any one of them unilaterally would be catastrophic for performance. The provenance models being suggested add more nuance to the model (pointer provenance) so that we can keep all of the optimization passes while preventing these cases from being optimized incorrectly. Weak provenance says we can't optimize away the pointer to integer cast, strict provenance says we must provide provenance for integer to pointer casts. Weak provenance is broadly compatible with existing code (compiler semantics change) whereas strict provenance is not (language semantics change). The tradeoff is that strict provenance leads to better optimization in general.
This analysis is correct but the solution is not feasible. Changing a modification through `x` to a modification through `y` does indeed violate the semantics of `restrict`. The problem is that in order to detect this situation, we'd have to track the provenance of integers. In this specific example, we'd have to know that replacing `xaddr` with `y2addr` affects `x` and `y`. There is general consensus that tracking provenance for integers causes many more problems than it solves, so although this would solve the problem it is not feasible. This is why weak and strict provenance are being pursued instead.
`restrict` pointers have nothing to do with the underlying "object" they point into (an array in this case). `restrict` lets the compiler assume that reads through a restricted pointer or any pointer expressions derived from it are only affected by writes through that pointer or expressions derived from it. There are only two writes in this example: `*x = 0`, which is trivially correct; and `*ptr = 1`, where `ptr` is derived from `x` (via `ptr = (int *)(uintptr_t)x`) so this is also correct. However, it's now easy to see that the optimization replacing `xaddr` with `y2addr` causes undefined behavior since it changes `ptr` to be derived from `y`. The post addresses this in "The blame game" and mentions that integers could carry provenance but that it's infeasible to actually do this.
The weak provenance solution is to ban optimizing the pointer to integer casts since they have a (conceptual) side-effect. The strict provenance proposal points out that the side effect is only observable if the integer is cast back to a pointer, so we can keep optimizing pointer to integer casts and instead ban integer to pointer casts. For example, an operation like `(int *)xaddr` is banned under strict provenance. Instead, we provide a casting operation that includes the pointer to assume the provenance of; something like `(int * with x)xaddr`. With this new provenance-preserving cast, we can see that the final optimization of replacing `*x` with its previously assigned value of `0` is no longer possible because the code in between involves `x`.
Really not sure why the state space would only grow as n^k / k!. As well as what n and k are in this case. Adding more tiles or more actors would both dramatically increase the size of the state space for that input.
I gave the thought some idle time, but it's been so long since I've constructed a proper hardness proof. If I do, I'll definitely make a post about it!
This is a great idea, and the low-level optimization tips are all excellent ones I have used in the past. I want to talk a little bit more about using bidirectional A* though, because I think it's very interesting. It's a great strategy in general, but this may be a case where it doesn't do as well.
Working backwards for this particular puzzle is very difficult because on each turn an actor may or may not move. This effectively increases the branching factor from 4 (one for each direction) to 4 * 2^n (for each of four directions, each actor may or may not have moved). In practice it would be lower than that upper bound, but it could still be significantly higher than the forward branching factor. A nice visualization for this to think of your start and end states as points in space, and your A* searches as cones emitting from one point and growing toward the other. The angle of the cone would be roughly approximate of your branching factor, and when your cones meet each other or a point the search is done. If your branching factor is the same forwards and backwards, you can travel through much less space by searching forwards and backwards simultaneously. However, if your backwards branching factor is higher then the cone from the end state will be much broader. This could travel through much more space than just doing a forward search.
This kind of behavior is very evocative one-way functions, and makes me think it might be related to NP-hardness in some way. I'm really not qualified to prove these kinds of statements though. Maybe someone else can offer a more rigorous mathematical perspective?
In my experience, the only way to make meaningful progress on performance from here on out is to:
- Squeeze out more entropy (for example, rotating states for symmetric boards)
- Make the heuristic function smarter (for example, by calculating the assignment bottleneck)
I wrote a Carcassonne solver once and found many little optimization opportunities by detecting fail states early for example. Avoiding dead ends saves a massive amount of time.
That would definitely work, and I’d be interested in the performance impact. This was written so that the state size would scale with the number of actors rather than the size of the grid. There is a degenerate case where a massive mostly empty grid becomes difficult not only to store in memory, but also to transition on move. The transition function would take time proportional to the size of the grid rather than the number of actors.
Bounding the maximum number of actors is just an optimization for the cases we want to solve. Of course if you wanted to really solve any case you would need infinite space, and that’s not achievable either. If you desired, you can also just omit that particular optimization. :) I think a better way to phrase it is that we are writing a solver for a reasonable subset of inputs to an NP-hard problem.
I think that's a really good point, and I definitely agree that rkyv, Cap'n Proto, and FlatBuffers all have different goals and design decisions. rkyv was primarily made with the intention of handling bulk structured data for game development; that's just because that's my background. Having schema evolution and validation wasn't important to me, but those are features that are important to a lot of other people. In the interest of getting more people interested in trying it out I've slowly added those features and I think that rkyv has been made better for it. It's the only of the three ZCD libraries that doesn't support schema evolution, and I think that's going to cause people to choose not to use it. So I'll probably figure out how to get schema evolution in there eventually.
As an aside, I updated the benchmarks yesterday and addressed some other responses that mentioned that the three libraries all have different behavior around validation. That's another place where the three libraries all differ in their approaches and it does materially affect the benchmarks. I found out that Cap'n Proto does validate-on-read, which is is a really cool idea that gives it a big edge while accessing complex structured data that rkyv takes a long time to validate. It's got me thinking about how to get the same kind of validation-on-demand functionality!
(Disclosure: I'm the author of rkyv - thanks for Cap'n Proto, it's been a big influence)
I actually agree with you; these are serialization issues that are very important to solve. I wrote a little about endianness and how it could be approached in the book FAQ [1]. rkyv's open type system enables a lot of really powerful extensions to the core library.
> The point of serialization is interop, not just rust-op. :)
I'm not personally interested in adding support for other languages, but I have been careful not to do anything that would make it especially difficult for someone else to do so. There's no reason why it being language-specific is so bad either, especially if it can take advantage of unique features to make it more expressive and performant.
1) You're correct, rkyv uses a B-tree with a default branching factor of 6 [1]. I don't think I've ever implemented a binary tree in any version of rkyv - maybe one of the earliest versions used a sorted vec instead of a B-tree? I hate the B-tree map implementation because it is so complicated, even though it actually used to be even worse in 0.7 when it was implemented as a B+ tree. Sorry for making you read any of it!
2) Arbitrary mutations would definitely be an improvement on rkyv, and I was most interested to see what kind of approach lite3/tron took! Unfortunately growing the buffer is not supported [2] and freed memory isn't reclaimed [3]. These are the two actually difficult problems standing in the way of rkyv getting more comprehensive mutation support, so unfortunately I think there's nothing valuable to take away here.
The issue with growing the buffer is that you invalidate any pointers into the buffer and have to manually fix them up (e.g. by re-crawling the buffer). There's not a decent approach I'm aware of which manages these pointer fixups in a way that limits complexity and avoids really nasty API surfaces.
The issue with memory reclamation is that you effectively have to add an allocator to your buffer, and that allocator has to also be persistable. I actually got this part working in rel while that was still a project worth hacking on [4]. I just ran out of steam and willingness to play the type-tac-toe required to get a safe API out of it. The main problem I ran into there was related to value branding, since you shouldn't be allowed to make references to objects which cross between contiguous buffers.
This project is neat, but it does basically just look like an rkyv-converted `BTreeMap<String, JsonValue>`.
[1]: https://github.com/rkyv/rkyv/blob/main/rkyv/src/collections/... [2]: https://github.com/fastserial/lite3/blob/main/src/lite3.c#L5... [3]: https://lite3.io/design_and_limitations.html#autotoc_md29 (see note at end of section) [4]: https://github.com/rkyv/rel/blob/main/rel_example/src/main.r...