Might just be independent discovery, but the main idea of this blog post is more or less the exact theory advanced in the recent book "The Dark Forest Theory of the Internet" by Bogna Konior (https://www.amazon.com/Dark-Forest-Theory-Internet-Redux/dp/...).
Like the author said this is completely unoptimized. The natural next step in optimization might be to profile and then SIMD optimize the slow bits in compression and decompression. This would likely produce a significant speedup and may even bridge the gap with lz4.
Agree with this and I think it's the crucial point. Where I've had the most success with UML-like tools and diagrams is early on in a project since its much faster to rip up and rebuild a few diagrams. The diagrams also help with getting consensus among stakeholders that this direction makes sense and doesn't have any glaring holes.
Later on you can drop the diagrams entirely and perhaps keep them as some onboarding documentation if they're still useful.
Type generic expressions [1] already exist in C11. You can do this without a special compiler front-end if you need it, you would just need to define each variant by hand. These are supported in GCC and Clang with the -std=c11 flag.
> This way you don't need to worry about keeping track of size and capacity either.
The only reason you don't have to worry about this is because std::vector handles it for you, at least in the code examples provided by the author. If you choose to go with a pure C implementation (which is what I'm trying out) then you will have to keep track of these.
> The reason I suggested -1 is because when we iterate through bd->items, we need a way to know if it's a valid value or just "holed".
Yep, I was able to get an example using -1 as a sentinel working and passing fuzz testing.
I think I've figured out roughly what the author intended, code below [0].
First, it looks like he's relying implicitly on data stored in std::vector. Namely vectors have both a capacity and a size. The capacity is total number of allocated elements. The size is the total number of elements stored actually stored.
Second, vector::resize won't reallocate until it runs out of capacity, but it will give you access to extra elements if you need them. So this is used to lazily re allocate while bumping up the size of the vector.
Both of these effectively make it "do the right thing" by leaning on the vector storing both size and capacity.
If you hand manage those values yourself you can get a pretty compact C implementation without a lot of code.
One last thing: Using a union here for the item_t is pretty much guaranteed to get you a segfault. The whole thing should really be a struct. This also allows for setting next to sentinel value if necessary.
I wanted to like this article because I'm been thinking about this a lot in the context of game development, noticed a few things. One thing I'll say from briefly playing with this - the code leaves lots out a looks ostensibly simpler than it really is. Would very much appreciate tips / pointers on this or a more fleshed out and working implementation of the code.
For the bulk data with holes code:
First, there's an initialization step that has to happen the first time you allocate your bulk_data_t. Namely, you need to iterate through every item in the list and set its next_free item to the item following it, looping the last item back around to zero. You also need to do this for all the items between the new size and old size every time you resize your item list.
Second, safe iteration over all of the bulk data doesn't seem possible without adding some sort of flag to indicate whether or not an item is free.
I think the strong counter-argument to this is in [1]. Quite simply we need to make sure we don't get fooled by randomness and see bias where there is none, thereby making good algorithms worse in an attempt to fix imaginary bias.
This reads largely like a recapitulation of Boehm's 2003 book "Balance Agility and Discipline" [1]. Have you read this and did this provide any inspiration for the article?