Memory-efficient enum arrays in Zig

by dist1ll • 3 years ago

322 239 3 years ago

wyldfire2• 3 years ago

In it he describes how a parsed clang AST regularly consumes 50x more memory than the original source code!

I guess that seems like a lot but the context I'm missing is - how good could it get? I mean, if you want to preserve source locations of each token and you need to encode enough information in the AST to properly recover, what's the ideal growth factor over the original? 1.5x? 15x?

anonymoushn2• 3 years ago

As a point of comparison, I think simdjson tape is only ~3x larger than the original document. Much of this could be saved if one did things like stuffing numbers into only one tape slot or not copying strings that have no escape sequences in them (instead referencing their location in the original document).

The largest overhead you could achieve is apparently 8x for a document that is mostly the characters "[]" or also 8x for a document that is mostly the characters "0,"

halayli• 3 years ago

There's a ton more context that needs to be held in a clang AST node compared to a JSON doc. Just to mention a few: file source, token range, expr/stmt/decl statements and their relation, macro expansion related info, and tons of diag to be able to walk back to the original source token, and padding added by the compiler in those data structures.

cryptonector2• 3 years ago

If you can achieve a memory savings of 30%, say, that would be pretty big news. If you can only achieve a 30% memory savings by doing things to the compiler that make it harder to work on the compiler in the future, then it's probably not worthwhile. But if you can achieve an 80% memory savings by doing violence to the compiler, that might be worth the trouble.

As for what's an ideal source->AST expansion factor for a language that has a user-friendly compiler that's also compiler dev-friendly, that's hard to say. Clearly 50x is workable.

In TFA the 50x expansion factor is used as a motivator for automating a particular type of optimization. It'd be very interesting to see a Rust vec-of-enums that automatically deconstructs enum values into tags and opaque values that it could store in a struct-of-arrays like TFA does in Zig. The places to bury unsafe use into for this would not be many.

fnord123• 3 years ago

Maybe I'm just dumb but isn't the endgame of vec of enums going to be an ECS?

dan-robertson7• 3 years ago

I think you should just watch the linked talk. It’s excellent. Though they don’t put exact numbers on it iirc (perhaps too early to be confident – they might be small due to missing data they don’t yet realise they’ll need).

AndyKelley2• 3 years ago

Source code is surprisingly compact.

As for one data point on how much better it can be, here is Zig's own parser, parsing Zig's own parser:

    # Source bytes:       139 KiB
    # Tokens:             24646 (120 KiB)
    # AST Nodes:          10998 (140 KiB)

Each token is 5 bytes which is pretty minimal (1 byte tag + 4 byte file offset). AST Nodes are also encoded compactly and non-uniformly, in this case coming out to roughly 13 bytes each. Despite these minimal encodings, the parse tree comes out to almost 2x the size of the source file in this case. 2x is a lot better than 50x though.

Source: zig ast-check -t lib/std/zig/Parse.zig | head -n7

wyldfire2• 3 years ago

2x is a lot better than 50x though.

the 50x metric was using something like this AST analysis mechanism (and not a system metric like resident set size)?

sdfghswe3• 3 years ago

More or less OT.

I keep hearing about both Zig and D as interesting C-like low level languages with better satefies/ergonomics. I wonder if someone who's familiar with both would like to discuss the main differences...?

Sharlin3• 3 years ago

Zig is C-like. D is C++-like. Zig has first-class compile-time metaprogramming. D is a kitchen sink language; it has many more features than even C++ does. Zig is minimalistic and strictly imperative rather than multi-paradigm. D has a cult following but hasn't really taken off. Zig is a relative newcomer trying to prove itself.

systems• 3 years ago

i think the term "D has a cult following" is a bit harsh D's community is small, that is it, nothing cult like, they dont over defend D most of the community seem to be happy using other languages etc ..

but i agree with D being a kitchen sink language, trying to be many things, but never being the absolute best at anything, which i think is why it never really took off

i am really hopeful for Zig, trying to be a more pragmatic C replacement

pron3• 3 years ago

Zig is C-like

Only in the sense that the language is simple and small, but C pays for that by being inexpressive (you can find families of C++ programs for which an equivalent C program would require exponentially more code). Zig, on the other hand, is small and simple while being just as expressive as C++. It achieves that through a remarkable observation: many primitive features can be avoided with a powerful enough compile-time computation mechanism with introspection.

Zig is so revolutionary in its design that it's hard to compare it to anything else. Or, put another way, any comparison is sure to miss out on some very foundational piece. So yes, in some sense Zig is like C (simple, low-level), but it's as expressive as C++. In another sense, Zig is like Scheme (minimalistic elegance), and yet it feels familiar and it does not rely on macros for its core power. In other ways it's like Go (easy to learn, easy cross-compilation), but it gives full control and is more flexible.

At this point, Zig is sui generis.

1980phipsi3• 3 years ago

I agree with most of this, but I would say that D was probably designed to be an alternative to C++ or Java. Zig shares many of C's design philosophies, though I think D's syntax is a little closer to C's than Zig's is to C's.

D also has a betterC mode that removes some of those "kitchen sink" features, but I couldn't say how popular it's use is. Many people who use D like some of those features. Zig's more minimalistic approach to language features is closer to C's approach.

Zig likely has been influenced by D (among other languages), but I wouldn't be surprised if D's new importC functionality has been influenced by Zig.

I don't use D (or C or C++) at work, but learning D and using it at home has made me a much better programmer in the languages I use for work. Maybe I would have learned those lessons with C or C++, but I guess I took more easily to D than them.

esjeon2• 3 years ago

D is a GC-based C++/Java-like OOP language. People used to call it "a C++ done right", but it was never simple and didn't have any clear edges against its competitors. TBH, one simply should not build on top of C++ - it's a beast that no one can comprehend, and it only keeps growing.

In case of Zig, I think it's a very good modern C alternative. Zig can do what C can do, can interoperate w/ C (e.g. importing C headers), and offers new features that are useful (comptime, slices, error type). It's like Go, but without GC and a large runtime.

sdfghswe3• 3 years ago

Oh many I was loving your description of Zig up until when you said "it's like Go"...

optymizer• 3 years ago

Having written a few toy compilers for C, to me D is the most elegant of the C families of languages.

For example, consider the versatility of the '.' operator. It does pointer dereference, static field access and class/namespace member/method access. In all those cases I want to access "a thing from this other thing". Having 3 operators in a language (., ->, ::) is easier for a compiler writer but it puts more cognitive load on the developer.

Now consider type extensions. As a language designer you could think: "if a developer wishes to add methods to a type Vector that exists in a third party library, then in their project, the developer would use some special syntax" like maybe:

    class Vector { void json() { ... } }

and maybe the developer also needs to have it even repeated across a header file and an implementation, but... why? It's an idea, but it's not a law of the Universe. There is a better way.

Instead, the compiler can help you out. Just declare a regular function anywhere like so:

    void json(Vector v) { ... }

which is not special in anyway, and then be free to invoke it as:

    json(v);

    v.json();

Why if it isn't our familiar dot operator! It also does type extensions via some syntax sugar? What an elegant solution.

This is just one feature of D, and it's filled with features. Though I don't really use D in my day to day work, it's wonderful to see how the authors thought about hard problems in language design and implemented elegant solutions. I think D deserves more recognition for the things it absolutely hit out of the park as a general purpose programming language.

ksec2• 3 years ago

Well WalterBright could have answered that. But since HN has started taking a piss out of WalterBright replying in every single Zig ( or Rust ) threads he stopped commenting on most if not all Programming languages topics. Sigh.

saagarjha7• 3 years ago

There are productive ways to comment on threads without being a shill for your own thing.

BaculumMeumEst4• 3 years ago

I was checking out gameboy emulators recently written in C++, Rust, and Zig that have seen recent development.

I couldn't get the Zig projects to build, which is understandable since the language seems to have had a lot of breaking changes in its build system and the language in general (which is why it comes with a caveat not to use it in production yet).

But given the sheer number of comments I've read over the years recommending Rust as a replacement for C++, I was more surprised to see that I couldn't really find a single Rust project that had correct timings (the frame rates were incorrect and audio distorted) and worked with most ROMs I tried.

Meanwhile, the C++ projects I found built without issue or hassle, had correct timings, ran all the games I've tried, had lots of features, etc.

What gives? Is emulation just not a good use case for Rust?

xmodem• 3 years ago

I think its a perfectly fine use case but we're not yet at the point where that community has reached a high enough level of rust adoption that there are a significant number of mature projects, even for something as relatively simple to emulate as a gameboy.

insanitybit5• 3 years ago

Emulation seems fine for Rust. I don't think there's a good answer to this anecdote. One option is that when I learned C++ I built an emulator to learn how to write an emulator, whereas people writing emulators in Rust are perhaps often trying to learn Rust. Maybe that leads to a difference.

It's basically impossible to say though, we'd need to do a full survey of the C++ and Rust emulator ecosystem and look at which bugs are most prevalent, control for authors experience and skill, etc...

edit: I'll also note that when I built an emulator there were guides for it in C++. I don't know what materials exist in Rust but building an emulator is actually a project that I would consider C++ for (if for learning purposes) just because it's so well documented how to build one using the language.

sdfghswe3• 3 years ago

What gives?

My guess based on no evidence whatsoever: The Rust community seems to have lots of low effort enthusiasts - people whose primary motivation is "use Rust" rather than "solve a problem". People whose motivation is to solve a problem (in this case build an emulator so they can play a game or whatever) tend to be a lot more oriented towards the end-result, rather than what tool they're using. I'm pretty confident this isn't an issue with the language.

mkl• 3 years ago

I think it's more "learn rust" than "use rust", and nowadays a lot of partly written learning projects are published on GitHub. A lot of the similar "learn C++" projects happened earlier and either stayed private or are quite good by now.

jandrewrogers2• 3 years ago

Most of the developers I know that are learning Rust do not come from a systems language background. They have to learn the domain as well as the language, which is a high bar. Learning to write systems-like code well takes a lot of time and experience.

mathstuf• 3 years ago

Timings and audio handling sound like logic things and not something Rust's advantages over C++ would inherently support better.

If I had to hazard a guess, it's that the C++ projects are just more mature and have seen more "in-the-wild combat" to get to the state they're in now. Other factors that may contribute (in no particular order):

  - existing emulators are Good Enough and polishing a new one is less "urgent" than other problems in the current zeitgeist;
  - hobby project vs. no-longer-a-hobby project status; and
  - emulator projects in C++ are of similar quality are just as prevalent, but are significantly older and instead of being discoverable on GitHub are abandoned on Sourceforge or personal websites.

TonyTrapp• 3 years ago

That would be my guess as well. Emulation, interpretation of decades-old binary formats, and similar problems are hard to get right on the first try, they often need years of testing and breaking until they are right. A project that has been around for 20 years will always have an advantage in this space over a newcomer project.

loup-vaillant• 3 years ago

Funny how being on GitHub makes you discoverable, while maintaining your own domain name does not…

Actually no, that’s not funny at all.

InfamousRece• 3 years ago

I don’t think Rust is inherently bad to write emulators. For example one of the best cycle-accurate IBM XT emulators is written in Rust: https://github.com/dbalsom/martypc

olafura• 3 years ago

So the question is why a project created in a language that has been around since before the devices being emulated are more mature than ones in a language that is 8 years old?

Sorry to be so snarky. It probably depends on people's time working on it and their familiarity with async processes. This is an inherent problem with any media like that. With sound, it's primarily that it can't come before the image but can lag behind the image. Stuff like this.

I don't think any programming language is going help with that because it's how we perceive things, not just how correct your code is.

0xDEF• 3 years ago

Building large-scale C++ projects has become less of an issue because of CMake slowly becoming the default build tool.

anymouse1234562• 3 years ago

An alternative opinion (that I happen to hold) is that the unbelievable pain and frustration of dealing with CMake has been at least one of the forces that have led to the Cambrian explosion of new programming languages and build systems in recent-ish years.

raincole• 3 years ago

What gives?

There are still more good C++ programmers than good Rust programmers.

tmccrary55• 3 years ago

This.

Many people are still learning Rust and an emulator is probably a good way to get your hands dirty.

I'm doing something similar with a compiler project and my code is gradually getting better and more idiomatic.

But I'm still doing a lot of stupid things and getting the hang of it.

jackmott42• 3 years ago

C++ has an ages old tried and tested ecosystem for game stuff which probably makes a lot of rendering and audio tasks easier. It could take Rust years to catch up even supposing the language is inherently better.

wiz21c2• 3 years ago

I'm currently writing an emulator in Rust (for Apple 2). For some aspects I'm better than my C++ counterparts.... BUT those counterparts have years and years of little refinements that make a huge difference on the fact that some games run or don't. There's no question about that.

Besides Rust is just fine. I use a bit of threads, a bit of OpenGl and none of these is a problem. I'd venture to say that the rust compiler is real good and that allows me to code things without worrying about optimisation. Older emulator have started years ago and they often had to optimize by hand which leads to not so readable code; just your usual code legacy story.

Finally, the cargo tool is a modern way to build the code and I've been able to port my code to Linux, windows, MacOs and raspberry pi without a single code modification (besides expected stuff like audio frequency, file system, etc being different).

The Rust crowds are just too new to have produced good emulators. Give us time :-)

raphlinus3• 3 years ago

I'm also noodling on an emulator, shooting for cycle accuracy (to the point where you'd be able to run vapor lock demos). Mine passes the 6502 functional tests but not yet the Tom Harte suite. To add to the difficulty, I want to run it on an RP2040 and bit-bang the video. Is yours up in an open source repo? Mine isn't (yet) but I'm open to joining forces.

I started mine about 6 years ago, put it on the shelf, and am getting back to it. Overall I think Rust is working well for it (and for pico DVI out), but I can also see the advantages of Zig for something this low-level and specialized.

panick21_• 3 years ago

Are you serious, a single specific software you like doesnt exist in a specific language and you blame the language for that? You see how that makes no sense right?

itishappy3• 3 years ago

That's not the situation. The software does exist and doesn't work. "Is this a because of the language?" seems a reasonable question.

simias• 3 years ago

Most people developing GameBoy emulators these days do it as a toy project, not a serious effort to create an ultra-accurate general purpose emulator. It's like writing a raytracer or a Pong clone.

The best GameBoy emulators like Gambatte predate Rust by almost a decade and are often written in C++. Since GameBoy emulation is pretty much a solved problem there's no strong motivation to innovate in the scene.

I've written several emulators in Rust, I'd argue that it's very well suited to this exercise, but it's also not an area where Rust shines particularly. There's no complex memory management in emulators usually since most memory buffers are just statically allocated constant-size arrays that mimic the physical RAM on the console.

hu32• 3 years ago

Related: for all the flak GC gets, C# was used to produce two amazing emulators:

1) https://github.com/Ryujinx/Ryujinx

2) https://github.com/TASEmulators/BizHawk

agentultra• 3 years ago

GC often gets more flak than is deserved.

Often such flak ignores the differences between throughput and latency.

For long, lived processes you’ll end up writing some kind of garbage collection system.

ghosty1413• 3 years ago

Personally I think C# is a great language to get stuff done. The big problem it has is the portability (especially when it comes to using it with a GUI).

guipsp• 3 years ago

Fwiw, ryujinx uses a jit on the hot path, and most (but not all!) bizhawk cores are not actually c#.

WhereIsTheTruth2• 3 years ago

ryujinx doesn't use the GC for their sub-systems, they use a mix of manual memory allocations throught their allocators or RC

For such project to succeed, you have to be able to optimize your memory allocation strategy

If you just rely on the GC, you'll have bad surprises (why does my game stutter during gameplay?!), they already have multiple due to their double dip on the JIT, nothing prevents the JIT compiler to compile during your gameplay, causing massive stutters, just like how shaders compilation is an issue at runtime

ilyt• 3 years ago

...probably the fact most of the C/C++ project you'd find in emulation exist longer than Rust itself ?

I'd imagine most of them in Rust were written for fun rather than trying to best the established ones.

kristoff_it• 3 years ago

wrt Zig, according to some it's a great fit for emulators, so maybe that's why there are a few :^)

https://www.youtube.com/watch?v=jkkUS0nmdsg

caskstrength• 3 years ago

What gives? Is emulation just not a good use case for Rust?

You fell for Rust PR (which is understandable, considering that both this site and Reddit are full of loud Rust fans/influencers). The language provides memory safety and some fancy ML-like syntax and that is it. It won't implement good emulator for you or make you a better SW developer.

coldtea• 3 years ago

Meanwhile, the C++ projects I found built without issue or hassle, had correct timings, ran all the games I've tried, had lots of features, etc. What gives?

Aside the fact of the C++ projects being from seasoned C++ developers (which exist 3 decades now in huge quantities), not people starting with Rust as their first "native" language and using an emulators as a toy project? C++ exists for 3 decades more on top of Rust's entire life of 8 years since v1.0. And given the over time adoption distribution, most Rust devs are like 1-4 years old Rust users max.

Or the fact that those C++ are probably much more mature, and with more manyears in them compared to the Rust ones, some even being major community projects?

dogben• 3 years ago

The most accurate IBM PC emulator is in rust. https://github.com/dbalsom/martypc

rahkiin• 3 years ago

I recently found https://github.com/Rodrigodd/gameroy to be a very complete implementation

BaculumMeumEst4• 3 years ago

I did see that one, but it doesn't seem to build on Mac.

alex_lav• 3 years ago

But given the sheer number of comments I've read over the years recommending Rust as a replacement for C++,
What gives?

This is The Hype Wave, where something is new and exciting so it's recommended over the things of the past without regard to whether it's as stable/full featured/correct. People are excited about Rust so Rust has been jammed into just about everywhere to varying degrees of success/correctness. This is the same as Javascript/Node and Go over the last decade-ish. Zig and Mojo are probably next.

elcritch• 3 years ago

You should add Nim to the list! There's a few implementations, though I'm not sure how complete they are. As others point out they're often used as ways to learn a language.

Fun writeup: https://itwasscience.com/blog/gameboy Improving RosettaBoy performance: https://forum.nim-lang.org/t/9859

Shish2k• 3 years ago

As somebody who has written the same gameboy emulator in C++, Rust, and Zig (as well as C, Go, Nim, PHP, and Python) - I have yet to find a place where language affected emulation correctness.

Gameboy audio is kind of a pain in the ass (at least compared to CPU, which is fairly easy, and GPU, which is easy to get "good enough” if you don’t care about things like palette colours being swapped mid-scanline) - and some languages take more or less code to do the same thing (eg languages which allow one block of memory to be interpreted in several different ways concurrently will make the “interpret audio RAM as a bunch of registers” code much shorter with less copying) - but in my case at least, each one of my implementations actually has the same audio distortions, presumably because I’m misreading some part of the hardware spec :P

https://github.com/shish/rosettaboy/

(Also yes, the zig version is currently failing because every time I look at it the build system has had breaking changes...)

BaculumMeumEst4• 3 years ago

Oh that's so cool! Thanks for sharing. I skimmed a few of these and I'll definitely take a closer look later. I enjoyed your observations on each language as well.

From a reader standpoint, I enjoy reading emulators written in C the most. It sucks when C is missing features for complex tasks, but emulation seems to fit nicely into what it can do without black magic fuckery. Of course as someone not super experienced with C, writing it feels like an endless sea of "oh god why is this segfaulting".

Rust OTOH bothers me to look at because there are so many sigils and language doodads for functionality that seems like it should be really straightforward but whatever, I'm sure that's just because I've barely used it and can't understand it. I've been learning C++ recently because learning materials are usually tailored to it for stuff I'm interested in (vulkan currently), while ignoring a constant nagging feeling that I should stpo being curmudgeon and take a closer look at Rust.

I've tried Zig but am not looking too hard atm for many of the reasons you mentioned in your repository, I'm hoping the language will stabilize at some point and that LLMs will help with some of the repetition/verbosity.

bowsamic• 3 years ago

Which Rust emulators? Which C++ emulators?

Perhaps the C++ emulators were serious, long-standing projects, and the Rust emulators were just hobby projects.

Most hobbyists only care about getting a game on the screen.

ForkMeOnTinder• 3 years ago

There's another strategy that has good storage efficiency and keeps the ability to iterate over elements. vec #1 is a list of tags, vec #2 keeps the byte offset of each element, and vec #3 (not really a vec) is the packed variant data pointed to by vec #2. This:

- is half the number of vecs of the author's final solution (6 vs 3)

- wastes no bytes for padding (unless needed for alignment)

- lets you iterate in a cache-friendly way since the data is laid out in order in memory regardless of type

- even lets you access items by index in O(1)

Generally it has the same performance characteristics as a Vec<T>, but for heterogeneous data.

dist1ll5• 3 years ago

Storing byte offset inline, great idea. Thanks for mentioning that.

Just note one disadvantage: if the byte offset is stored in memory, you have a data dependence on the traversal. So even though it's cache-friendly, it may cause serious memory stalls in the processor's pipeline.

jadbox• 3 years ago

I'd love for someone to benchmark these variants to tease out their actual characteristics (particularly for x86).

dan-robertson7• 3 years ago

One trick for this is to leverage the branch predictor to guess where the next item will be (I first saw this trick for linked list traversal as in practice linked lists are often laid out linearly). Something like

  // or guess based on the size of the current item
  let guessed_next_offset = current_offset + (current_offset - previous_offset);
  let actual_next_offset = byte_offsets[++i];
  previous_offset = current_offset;
  current_offset = guessed_next_offset;
  if(current_offset != actual_next_offset)
    // need to make sure the compiler doesn’t ‘optimise out’ this if and always run the below line
    current_offset = actual_next_offset;
  // ...

In the ordinary case, where the guessed offset is correct, the cpu predicts the branch is not taken, and no data dependency of ... on actual_next_offset is introduced. If the branch is mispredicted then that speculatively executed work with the wrong current_offset is dropped. This is a bit slow but in the case where this happens all the time, the branch predictor just gives you the slightly bad perf of the traversal with the data dependency (computing the guess will be negligible) except you pay if the guess was actually right.

loeg2• 3 years ago

Offsets can add a significant amount of space relative to small T, if their size is not optimized (e.g., 64-bit size_t and uint8_t T). So as long as we are careful about offset size this seems like a reasonable approach.

dan-robertson7• 3 years ago

Indeed part of this is pointed out in the video about Carbon linked in the OP: juxtaposition gives you a ‘free’ pointer going from each node of your data structure and for some tasks you don’t really need more than that.

pornel3• 3 years ago

But if you need to mutate such collection, you’ll end up writing a memory allocator (to handle removals, changes to larger variant, and to deal with fragmentation).

Joker_vD3• 3 years ago

Wait, the thing the article calls "array of variant arrays (or AoVA)" is not the canonical way to decompose tagged unions? Seriously? [A×B×C] ≃ [A]×[B]×[C], that's the most obvious thing, isn't it?

Edit: Actually, never mind, as the comment points out, the correct equation should be [A+B+C] ≃ [A]×[B]×[C] and it's not obvious at all whether it's actually correct.

ratmice• 3 years ago

Don't you mean something like [A+B+C] ≃ [A]×[B]×[C]

pornel3• 3 years ago

Things like that can be done by specific collections (e.g. most ECS implementations store components per "archetype").

But from language perspective the limiting factor is that you're always allowed to take a reference to any instance of an enum. This means the tag must be stored in every instance. If you allow mutable references to enums, you must have enough space for writing any variant there through the reference.

kccqzy• 3 years ago

Of course not: you are mistaking sum types and product types.

Even if we assume they are product types, [A×B×C] ≃ [A]×[B]×[C] is still not correct. The former doesn't allow the number of As and Bs and Cs to differ: the latter does. So the latter strictly speaking admits more values than the former.

Since both of them allow infinite number of values, to make a size comparison we will use generating functions. A list of A (or [A] in your notation) allows an empty list (one possible value), a one-element list (as many values as A itself), a two-element list… which becomes 1+A+A^2+…=1/(1-A). The beautiful thing about calling them sum types or products types is that you can manipulate it just by summing or multiplying respectively.

So the number of values for [AxBxC] is identified by 1/(1-ABC). For [A]*[B]*[C] it's 1/(1-A)/(1-B)/(1-B) which simplifies to 1/(1-A-B-C+AB+AC+BC-ABC). Now it becomes obvious† this form admits more values and you can in a sense quantify how many more!

†: Okay perhaps it's only obvious if I also include a Venn diagram but diagramming is beyond what I can do on HN.

Joker_vD3• 3 years ago

Yeah, and if you carefully expand 1+(A+B+C)+(A+B+C)^2+(A+B+C)^3+..., there'll be strictly more summands than in (1+A+A^2+A^3+...)×(1+B+B^2+B^3+...)×(1+C+C^2+C^3+...) due to more flexible ordering of elements, so they're not isomorphic.

I still think it's the most obvious thing that [A+B+C] at least maps surjectively onto [A]×[B]×[C] :)

catgary2• 3 years ago

It’s a section/retract, definitely not an isomorphism. You’ll need to carry around the index data, and any sort of array update will incur a crazy upfront cost.

Joker_vD3• 3 years ago

Eh, I imagine it should be possible to maintain an out-of-line skip-list or an array of tombstones or something to deal with deletion/tag mutation (although in my experience with ASTs that's not that common of a requirement); and allocation can be done quite effectively with the help of the good old .bss section: just grab couple of millions of every type of node at the program's startup, virtual memory is almost free.

pornel3• 3 years ago

Rust’s type system ended up being Turing-complete anyway. It seems like it fell into the same trap as C++ templates: it’s an accidental programming language in a programming language, but with way worse syntax.

The lesson for language designers may be that every useful type system is doomed be Turing complete, so you may embrace it from the start, instead of trying to make it declarative.

avgcorrection2• 3 years ago

Surely they knew that it would become a programming language in its own right. That's the fate of all such statically typed languages which give you type-level power but that aren't dependently typed. (Of course dependently typed languages might end up with other languages like its own tactics language.)

insanitybit5• 3 years ago

I don't think anyone has ever been surprised to find that a type system (with inference) is turing complete.

Ar-Curunir• 3 years ago

That something can be Turing-complete in the worst case doesn’t mean that you hit those worst-cases on a frequent, or even occasional basis.

hnfong• 3 years ago

Rust’s type system ended up being Turing-complete anyway. It seems like it fell into the same trap as C++ templates

I hear it is a common trap.

https://aphyr.com/posts/342-typing-the-technical-interview

dist1ll5• 3 years ago

author here. That's a really good observation kornel. Rust's philosophy of avoiding post-monomorphization errors at all costs is usually sung in high praises (followed by a ridicule of C++ template errors) - but it comes at a cost. And when you stray away from the declarative way and start plastering const generic bounds everywhere you really feel the pain.

Anyways, I think engaging in this topic as a community is super important. Cause that's the only way to push PLs forward and explore this massive space.

bhouston5• 3 years ago

Rust’s type system ended up being Turing-complete anyway. It seems like it fell into the same trap as C++ templates: it’s an accidental programming language in a programming language, but with way worse syntax.

Most anything in software can easily end up Turing-complete though. It isn't that high of a bar unfortunately. I think most mature type and template systems end up as Turing-complete. To single out Rust for this is to ignore that this is just standard fare for mature typing systems.

TypeScript's types are Turing complete: https://github.com/microsoft/TypeScript/issues/14833

Python's type hints are Turing complete: https://arxiv.org/abs/2208.14755

Java generics are Turing complete: https://arxiv.org/abs/1605.05274

dgb235• 3 years ago

The point is that Zig basically circumvents issues surrounding that, by introducing "comptime", where you can just write regular Zig to achieve the same things.

The article showcases a nice example of having this very direct power.

But it really comes up more often than you think as soon as you actually have it.

It's easy in Zig to allocate precisely based on computed values and then have the sizes as part of your types etc. It all falls out of some simple ideas and it's all just regular Zig code.

"Types in Zig are values of the type type" from: https://ziglearn.org/chapter-1/

So instead of making it hard to write incorrect programs, Zig makes it easy to write correct programs.

383• 3 years ago

Most anything in software can easily end up Turing-complete though.

not really, if you actually pay attention when youre designing the type system:

https://arxiv.org/pdf/2005.11710.pdf

egl2021• 3 years ago

"It isn't that high of a bar unfortunately." --> "It isn't that high of a bar."

baq2• 3 years ago

it's easier to make something Turing-complete than not... most interesting example is probably rule 110.

wredue3• 3 years ago

The point is that it’ll end up that way, so just embrace it from the start.

marcosdumay• 3 years ago

instead of trying to make it declarative

Wait, no. A language being Turing complete and declarative are completely independent things.

dgb235• 3 years ago

That's the point!

packetlost• 3 years ago

This is sort of the approach that I've considered. Type systems are just predefined code/behavior baked into a language, but there's technically nothing stopping you from arbitrarily extending the compiler like Lisps do with macros to support a type system that's written in the language itself.

naasking• 3 years ago

Type Systems as Macros:

https://www.khoury.northeastern.edu/home/stchang/pubs/ckg-po...

throwaway894345• 3 years ago

I think there's still value in pushing people towards something declarative. For example, a static type system might have an `any` type for things that aren't expressible statically but that doesn't mean type system designers should embrace dynamic typing from the start instead of trying to make it static. Similarly, it makes sense to have panics/exceptions in a language as an escape hatch for errors where the application can't reasonably do anything gracefully, but it's (arguably) a bad experience to take that to the extreme and panic for all errors.

I think there's value in accounting for the possibility that there will be edge cases that preclude hard-and-fast rules like "purely static" or "purely declarative", but I dislike the philosophy of projecting the 1% use case (e.g., "dynamic" or "turing complete") onto the 99% use case (where e.g., static and declarative would be ideal). I like when languages design for the 99% case and allow for escape hatches for the remaining 1% with the understanding that these escape hatches are intended to be used judiciously.

To put it differently, embrace that there may be escape hatches in the initial design, but prefer to think of them as "escape hatches" with the entailed understanding that they should be rarely used.

mlochbaum• 3 years ago

I did this! Singeli is an Elixir-like compile-time language where types and variables are first-class values, on top of C-ish semantics that are meant to be more like "portable assembly". It's designed for high-performance code where you have to be able to control the specific instructions, but the overall strategy could be useful in other domains too.

https://github.com/mlochbaum/Singeli

And a podcast on it came out Friday:

https://www.arraycast.com/episodes/episode62-what-is-singeli

mk12• 3 years ago

I listened to that, it was good! I was surprised there is an entire podcast about array programming. Looking forward to future episodes, and also to trying AoC with BQN again in a few months.

lenkite• 3 years ago

Basically design in dependent types into the language right from the beginning (like Iris) - such that types are first class and can be computed and manipulated like any other language construct.

itishappy3• 3 years ago

Fascinating! Now I'm curious, what causes this? Where does Turing completeness come from?

Polymorphism? Inference? Higher-kinded types? (Probably not that last one, I don't think Rust has them.)

Put another way, what would it take a for a type system to NOT become Turing complete?

ynik• 3 years ago

Turing completeness doesn't have to come from a single feature, it often comes from a combination of features.

e.g. the interaction between subtyping (e.g. inheritance) and generics (with variance) is tricky: https://www.cis.upenn.edu/~bcpierce/papers/variance.pdf

It can be highly nontrivial to tell if a language actually has a Turing complete type system: the 2007 Kennedy&Pierce paper made it likely that java was turing complete; but it took until 2016 until it was finally proven that to be turing complete (https://arxiv.org/abs/1605.05274).

What would it take a for a type system to NOT become Turing complete?

An analysis of all possible interactions between all features in the type system, building a formal proof that the type system is not turing complete. This is not really realistic for the style of complex generic type systems that programmers are now used to, it would need to be a vastly simpler language.

AprilArcus• 3 years ago

All you need is a way to branch and a way to loop, so anything with conditional types and recursive types will be Turing Complete

justinpombrio3• 3 years ago

Agreed. The strong agree is that Rust's type system---and many other languages' type systems---is a parallel language to its runtime language. Parameterized types are like functions; instantiating a type parameter is like a function call; `impl ... where` does pattern matching. You get a pure functional language based on pattern matching and implemented with memoization. These type systems are often Turing complete on purpose, but yet it's surprisingly hard to get an infinite loop. Like, both Rust's and Java's type systems are Turing complete, yet I've never hit an infinite compilation loop in either by accident.

For more on type systems as programming languages: https://ductile.systems/oxidizing-the-technical-interview/ plus its links at the top.

What I would like to see is a programming language where the runtime language and the comptime language are the same, or nearly the same, and where the comptime language is type safe. Zig isn't this: its `comptime` language is essentially dynamically typed. In Zig, if a function `f` takes a `comptime` argument `t: Type`, it can call `.print()` on it, and the compiler will just assume that that's fine. If you call `f`, you had better read the docs because the type system won't tell you that `t` needs to have an `print()` method. If you're calling `f` directly, that's pretty straightforward, but the trouble comes when you actually call `h`, and `h` looks at the value of some string and based on that decides to call `g`, and `g` calls `f`, and the docs for `h` weren't entirely clear, so now you're seeing an error in `h`, which you didn't even call. Instead, if `f` is going to call `.print()` on a `t`, then its argument `t` can't just be a `Type`, the compiler should check that it's a `Type with method .print()->String`. This requirement would then flow to `g` and `h`, so the type signature for `h` is guaranteed to tell you that `t` is required to have an `print()` method.

For more on merging runtime and comptime languages in a type safe way, see 1ML: https://people.mpi-sws.org/~rossberg/1ml/

EDIT: Deleting my criticism of C++ templates lest it distract from the more substantial things I had to say above.

gpderetta3• 3 years ago

What I would like to see is a programming language where the runtime language and the comptime language are the same, or nearly the same, and where the comptime language is type safe

I have aproximately 0 knowledge of it, but I think TemplateHaskell should do that.

avgcorrection2• 3 years ago

What I would like to see is a programming language where the runtime language and the comptime language are the same, or nearly the same, and where the comptime language is type safe.

MetaOCaml might the closest one.

zozbot234• 3 years ago

and where the comptime language is type safe

You need dependent types in order to do this, which means doing away with Turing-completeness. (Moreover, the principle 'Type is of type Type' as found in Zig comptime leads to type-unsafety. So you need to replace that with some notion of universes.)

haberman• 3 years ago

100 times this. C++ is progressively making more and more of the language and stdlib available at compile time (constexpr, consteval, constinit). Once this is accomplished, there will be two very complicated Turing-complete programming languages available at compile time, one that is convenient to program (C++) and one that is not (C++ templates).

Zig jumps straight to the finish line by making the main language available at compile time out of the gate, and by using it as the "generics language", Zig's generics are both simpler and more powerful.

Aardwolf2• 3 years ago

Genuine question:

How do type system that are so abstract and complex to become turing complete help?

I definitely find it extremely helpful to be able to write containers of any type (like std::vector<T>), that saves a ton of code duplication, but beyond that what more is needed and why? What we're competing with here is: just write a function that operates on the data types you want and gets the job done.

You're writing code for the CPU that has to actually do something, on actual known types.

What programming task is simplified by having an "any" type or a type system that allows you to write pong-played-turn-by-turn-using-compiler-error-messages? It's cool that you can have an "any" type just like universal sets in set theory, but what real-life programming scenario does this simplify (you can already write containers that can contain anything you want without using such as thing as an "any" type)?

At least not the kind of programming tasks I do, but admittely I think fairly low level and prefer my types to have exact known amounts of bits, known signed integer convention and endianness so I can efficiently use shifts and get the bits I need, preferably with as little undefined behavior as possible.

Asked differently: If one were to design a programming language that only has basic types (primitives, structs/classes, ...) and templates to allow functions/classes to operate on any type (but not more than that; substitute template type with the actual type, compile this, nothing more), what feature will users of the language be missing and complain about?

gpderetta3• 3 years ago

You're writing code for the CPU that has to actually do something, on actual known types.

(Partial) specialization, which is a feature used to get templates to do actual something on actual types is what principally allows templates to be turing complete.

widdershins• 3 years ago

It's about when you want to enable optimisations or conveniences depending on the parameterized type.

For example, in the std::vector<T> type, if T supports being moved, you want to use that when growing your vector for performance. If T doesn't support being moved, you will have to copy it instead.

Boom: you've ended up with template metaprogramming.

munificent2• 3 years ago

Asked differently: If one were to design a programming language that only has basic types (primitives, structs/classes, ...) and templates to allow functions/classes to operate on any type (but not more than that; substitute template type with the actual type, compile this, nothing more), what feature will users of the language be missing and complain about?

This is a really good question. There are some languages that work as you describe: SML and some others in that family. There are generic functions and types, but the type parameters are basically just placeholders. You can't do anything with a value whose type is a type parameter, except store it and pass it to things that also take type parameters.

That gives you enough to write a nice reusable vector type. But it doesn't let you easily write a nice reusable hash table. You can, but users have to pass in an explicit hash function that accepts the key type every time they create a hash table.

It might be nice if a type itself could indicate whether it's hashable and, if so, what it's hash function is. Then, if you create a hash table with that key type, it automatically uses the hash function defined by that type.

Now you need some sort of constraints or type bounds in your generics. That's what traits in Rust and bounds in Java and C# give you. (The literature calls it "bounded quantification".) It's a big jump in complexity. But it does mean that now you can call functions/methods on arguments/receivers whose type is a type parameter, and those calls can be type checked.

Bounds are themselves types, so what kinds of types can you use in bounds? Can they be generic? If so, what kinds of type arguments are allowed? Can you use type parameters from the surrounding type?

For example, which of these are OK and which aren't (using Java-ish syntax):

    class A<T extends Foo> {}       // 1.
    class A<T extends Bar<Foo>> {}  // 2.
    class B<T extends B<Foo>> {}    // 3.
    class B<T extends Bar<T>> {}    // 4.
    class B<T extends B<T>> {}      // 5.

Any kind of bounded quantification will give you 1-3. What about 4 and 5? This is called "F-bounded quantification". Why would you want such a thing?

Collections with fast look-up are important, which is why we extended our generics to enable us to write nice reusable hash tables. But some data types aren't easily hashed but can be easily ordered. A sorted collection is faster than an unsorted one.

How would we write a generic sorted collection? We could require you to always explicitly pass in an ordering function for any given element type, but it would be nice if the element type itself could supply is order function.

You could define a "Comparable" interface that a type can implement to support comparing an instance against another object of some type, like:

    interface Comparable<T> {
      int compareTo(T other);
    }

And then implement it on your type, like:

    class Color implements Comparable<Color> {
      int r, g, b;

      int compareTo(Color other) => ...
    }

In our sorted collection, elements all have the same type, so the bound that we need looks like:

    class SortedCollection<T extends Comparable<T>> { ... }

Notice that we have "T" inside the bound. That's F-bounded quantification.

Using type parameters inside a bound isn't the only place recursive types like this show up. Let's say you wanted to make a generic type comparable. You'd do something like:

    class Pair<T> implements Comparable<Pair<T>> {
      T a, b;

      int compareTo(Pair<T> other) => ...
    }

Now here, the implements clause is using not just the type parameter of the enclosing type, but the entire type.

We had a couple of fairly modest goals:

* Be able to create reusable hash tables where the hash function is inferred from the key type.

* Be able to create reusable sorted collections where the comparison function is inferred from the element type.

And in order to get there, we needed generics, bounds, and even F-bounded quantification.

Adding even a little more usefulness to our collection types will quickly have us reaching for variance annotations, associated types, and even more exotic stuff.

jjtheblunt• 3 years ago

Can you show how you'd implement a Turing machine in Rust types?

I am not seeing it, so am likely overlooking that.

fweimer• 3 years ago

How does this AoVA data structure work in practice? Don't you lose index-based access, in the sense that arithmetic on indices is potentially no longer meaningful in the array sense? Iteration will not preserve insertion order.

I think TLV (tag-length-value; length can be implied by the tag) is more commonly used in this context due to its better caching properties, and it least it provides meaningful forward iteration. See getdents/inotify/Netlink messaging.

LegionMammal978• 3 years ago

How does this AoVA data structure work in practice? Don't you lose index-based access, in the sense that arithmetic on indices is potentially no longer meaningful in the array sense? Iteration will not preserve insertion order.

The caption to figure 4 suggests that the AoVA pattern is not a good fit if you need to retain the full order of inserted elements:

Compared to the SoA layout from before, we have a partial order instead of a total order. So upon insertion, we get back a tagged index that holds both the enum tag and the index in the particular variant array.

So by my reading, ordered access is considered out of scope here. (I suppose you could recover ordered iteration by storing a global index in each element, but that still wouldn't help with ordered random access, and it would likely lead to some really branchy code.)

catgary2• 3 years ago

Yeah I imagine an array write that changes the type of an index would be insanely expensive…

Aransentin• 3 years ago

In practice, changing tag type is rarely done.

In any case it wouldn't be particularly expensive; you'd have to make a new member of the destination type which is as expensive as an append. The "hole" that remains in the original vector can be filled in constant time by taking the last member of it and moving it there, then shrinking its size by 1.

skybrian• 3 years ago

upon insertion, we get back a tagged index that holds both the enum tag and the index in the particular variant array.

These are essentially pointers. If you want to iterate, you store the pointers in an array in the order you want to use. It’s the same thing a program would do if it allocated memory from a heap.

Storing things based on their size is also done by garbage collectors and general-purpose allocators. They might get some efficiency from knowing all possible object sizes, though. Also, like an arena, they could gain some efficiency from having a simpler way of deallocating.

dylukes• 3 years ago

AoVA lacking its own total ordering on indices might be a problem for some use cases, but not for the one that is suggested here: AST nodes.

In these cases, the arrays can be just one component (could think of it as an arena) of a heap-ish structure. [1]

The cost is that your indices now need to be two dimensional (tag_idx, va_for_tag_idx). But the number of tags is known at compile time and you can optimize storage by packing so that tag_idx is the upper 4-5 bits and va_for_tag_idx uses the rest.

See: [1] https://www.cs.cornell.edu/~asampson/blog/flattening.html

bfrog5• 3 years ago

I still have yet to understand if Zig actually provides memory safety in the same manner Rust does or not, it seems like its another C like language without memory safety? Or did I happen to miss that bit?

xigoi• 3 years ago

I still have yet to understand if Zig actually provides memory safety in the same manner Rust does or not

It doesn't.

bfrog5• 3 years ago

So its C with nicer macros and maybe some more sensible ways of dealing with arrays and such?

For me that's not enough to move the needle.

emmanueloga_3• 3 years ago

It doesn't, but it puts a RED BANNER in every place where memory is allocated, and you need to explicitly pass an allocator of your choosing whenever memory is allocated. It also contains no hidden allocations or function calls. So it forces you to think about your memory allocation patterns, and also includes some tools to catch memory leaks [1].

1: https://ziglang.org/learn/samples/#memory-leak-detection

maxmcd• 3 years ago

I found this article to be clarifying: https://www.scattered-thoughts.net/writing/how-safe-is-zig/

bfrog5• 3 years ago

In effect this answers my question pretty well, the answer seems to be a resounding "No there's no memory safety" at least in the practical or realistic sense that results in few to no memory lifetime errors.

dgb235• 3 years ago

Zig provides tools to avoid memory related bugs, but it doesn't enforce it via compile time checked RAII/burrow checking etc.

Nullability (and error handling) is compile time checked though.

bfrog5• 3 years ago

To me the biggest win in Rust is just that, the memory related bugs are nearly non-existent. Throw in a group of people working on something and this makes the project move just so much faster in both review time and time hunting bugs.

throwawaymaths4• 3 years ago

Zig gives buffer overflow safety and null pointer safety but not use after free, double free, or stack pointer escape safety.

Zig also gives you memory exhaustion safety which rust does not.

oconnor663• 3 years ago

Is there a memory exhaustion scenario where Rust does something other than panic?

gpanders• 3 years ago

Zig gives buffer overflow safety and null pointer safety but not use after free, double free

It can provide the latter two through the use of the `GeneralPurposeAllocator`, which tracks UAF and double free.

Stack pointer escape safety is being actively researched (there are a few tracking issues, see [1]). I'm personally interested in this, I've written a decent-ish amount of Zig for toy/personal projects, and anecdotally stack pointer escape is the only type of memory error that has bitten me more than once (though to be fair, one of these cases was calling into a C API, so even Rust wouldn't have helped).

More broadly, the ability to catch all forms of UB in Debug/safety builds is an accepted proposal [2], though whether or not it will be possible in practice is a different (and interesting!) question.

[1] https://github.com/ziglang/zig/issues/2646

[2] https://github.com/ziglang/zig/issues/2301

pitaj2• 3 years ago

What do you mean by memory exhaustion safety?

zoogeny• 3 years ago

As an aside and unrelated to the content of the article ... but the form of the article, with footnotes in the margin, is really useful.

dist1ll5• 3 years ago

Thanks! It's inspired by this https://edwardtufte.github.io/tufte-css/

ghosty1413• 3 years ago

Thanks for sharing this! Looks fantastic, I'll definitely incorporate this into my own blog once it's finished.

ammar2• 3 years ago

Another quick question for you, what are you using to make those hand-drawn looking diagrams? They look amazing.

chrismorgan4• 3 years ago

Generally speaking: sidenotes are excellent, footnotes are fine, endnotes are terrible. On the web, as a typically-not-paged medium, “footnotes” practically always actually means endnotes.

kazinator2• 3 years ago

You can solve this problem if a few clear lines of GNU C. We declare two sister types, one of which is packed:

  typedef struct taggedunion {
    unsigned char tag;
    union tu {
      uint64_t   u64;
      uint32_t   u32;
      uint8_t    u8;
    } u;
  } taggedunion_t;

  typedef struct __attribute__((packed)) packed_taggedunion {
    unsigned char tag;
    union tu u;
  } packed_taggedunion_t;

Then accesses to our dynamic array will convert between the packed stored representation and the unpacked one in a straightforward way:

  taggedunion_t array_get(packed_taggedunion_t *a, size_t i)
  {
    return (taggedunion_t){ a[i].tag, a[i].u };
  }

cryptonector2• 3 years ago

But it's C. The idea here is to have higher-level, type-safe languages do this transformation automatically.

masfuerte2• 3 years ago

But this still takes 9 bytes (at least) to store a tagged uint8_t.

kazinator2• 3 years ago

The article's approach requires 8 bytes, plus a separate array of 1 byte tags.

The article reduces it to 4 bytes, plus an array of 1 byte tags, by dropping the requirement for a 64 bit member.

If we have to grow the array, we have to do two reallocations.

Caching is worsened: the tag and content are going to be in separate cache lines.

WhereIsTheTruth2• 3 years ago

For any language to be labeled as a "better c" language, it must solve this problem, having better enums is a requirement

It's actually one of the reason I initially gave Zig a try, not Comptime, it was Tagged Union

loeg2• 3 years ago

Your packed union eliminates pure padding, yes, but it still costs 9 bytes to store a u8 value and misaligns accesses for wider elements. These are both significant misses on "solving the problem." You also need to copy each element on access, which could be expensive for larger plain-old-data types, or especially for non-POD types.

airstrike6• 3 years ago

I only partially understand this article but this seems incredibly relevant to me since I'm planning on writing a spreadsheet engine in rust. Cell values require me to have something like (this very poorly written POC code, sorry):

    pub enum Expr {
        Number(i32),
        String(String),
        Reference(Position),
        Binary(Box<Expr>, char, Box<Expr>),
        Function(String, Vec<Expr>), 
    }

I'll keep reading and studying! If anyone has more resources to throw at me, I'm all ears

hathawsh• 3 years ago

Sounds like a fun project. If it's intended for ordinary users, one thing you should expect them to do is add content to the 4 extreme corners of a sheet and see if the spreadsheet engine falls over as a result. If you allow 1 million by 1 million cells, and you store a "null" for every cell not filled in, then the engine will run out of memory. That means you might consider storing the cell content in a sparse manner. One way to do that is with a hash map implementation such as "hashbrown". Just a thought.

(To clarify why I'm bringing this up, the points in this article are low level details that you probably don't need to think about if you start with a hash map and thereby avoid running into memory constraints initially.)

airstrike6• 3 years ago

Thanks, great point indeed. I am looking into this https://github.com/rust-lang/hashbrown

The way I think about it -- rather naively, I suppose -- is that I care more about the references cells make to each other than the actual grid of cells displayed on a table. The latter feels more like a "view" of the data than an actual data structure?

This also seems to align with the relative priority of (sorted from highest to lowest): figuring out the order of evaluation, calculating those evaluations, and finally displaying the results of the evaluation

vlovich123• 3 years ago

The problem being highlighted is that if you have widely disparate sizes of the variants and/or a lot of these in an array, your hurting performance because there’s a lot of space being wasted on padding.

A common technique that came from gaming is that if you have an array of structs (AoS) (eg array<struct { health: int, ammo: Ammo, … }> to break it up into a struct of arrays (SoA): struct Humans { healths: Vec<int>, ammo: Vec<ammo>, … }. Then the ith index into those vecs is the ith Human in the AoS layout (parallel vecs here are for example, but it’s not optimally efficient because the bookkeeping of length and capacity on a per field basis is wasteful as that info is duplicate).

This is basically a similar idea except for enums and doing it automatically in a way that Rust can’t. It’s possible the problem is a bit overrated in terms of how big of a problem this is. Also, in Rust you may be able to wrap the third party type in your own and then the derive macro approach probably can work.

Re your spreadsheet, just keep in mind of this as a possible optimization and you have to first figure out if you’re building for speed (ie you’ve done this a few times and you know this is probably a bottleneck) or experience (ie build for simplicity and understanding)

rudedogg• 3 years ago

On the subject of AoS, Zig has a cool data structure for that: https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-i...

airstrike6• 3 years ago

Thank you -- definitely building it for speed which is why this felt topical. I really appreciate your explanation, it's super clear.

nhatcher2• 3 years ago

Hey, I've actually build a spreadsheet engine in Rust. Not open sourced, but could give you some pointers. You are going to hit lots of performance issues before you can have some gains using the methods of the article. The single most difficult problem is the evaluation strategy.

airstrike6• 3 years ago

Hey, thanks for the offer. I have been thinking about evaluation and the extent of my strategy so far has been to consider it as a dependency graph, which led me to this interesting article: https://hyperformula.handsontable.com/guide/dependency-graph...

Also it sounds like the right next step for me is to read more on incremental computation. Someone on reddit just pointed me to adapton: https://docs.rs/adapton/latest/adapton/

Actually implementing anything with Rust is on my TODO list (I'm spending some time on the UI prototype right now)

I will give a couple things a try and then, if you don't mind, I can ping you via email. I was checking out your website and loved the read on the parser -- not to mention A MAZE (played all the way to level 4!)

cmrdporcupine6• 3 years ago

In general I'm maybe somewhat disappointed that pattern matching in Rust can't be expressed more as a type system trait-type thing (hand waving here) that any struct could conform to, rather than an explicit first class hardcoded object type with its own storage structuring, etc?

I may not be expressing this cogently, but. I've implemented both an AST (as in this article) and an opcode/bytecode interpreter recently, and I feel that in large part Rust's enums are not ideal for either:

I never had the memory usage concerns about the AST that this author did, but I wanted to do things like: add a line number / column attribute to every statement node. I had a `Stmt` enum, and I had a choice: put line # and column on every enum possibility (boilerplate and ugly), or put the enum in a new Stmt struct that contains both the original enum and the line/col attributes -- which involved a bunch of refactoring and also didn't feel elegant. I feel there must be a more elegant type system way that my "Stmt" struct could have been reworked, that Rust isn't offering me.

And re: the opcode stuff,I am fairly sure that a pattern-matched Rust enum is not an ideal encoding for a VM opcode interpreter performance wise. But the language really does want to point you in this direction, and the facilities for de-structuring patterns are very seductive. I haven't gotten to yak shaving this yet, but again I feel like there's likely some potential for improvements in the type system that could open things up so one could get pattern matching facilities while using one's own preferred lower level impl.

I dunno. Thoughts.

aw16211072• 3 years ago

pattern matching in Rust can't be expressed more as a type system trait-type thing (hand waving here) that any struct could conform to, rather than an explicit first class hardcoded object type with its own storage structuring, etc?

Do you think you can provide a more concrete example? First thing that comes to mind for me is some kind of structural typing [0], but I'm not confident I'm interpreting your comment correctly.

[0] https://en.wikipedia.org/wiki/Structural_type_system

cmrdporcupine6• 3 years ago

Other people who are better with these things could probably conceptualize it better than me.

What I'd like to be able to do is declare a trait that says "this thing can yield the following patterns, can destructure in this pattern, and these are the functions you'd call to extract references to those values"

And then be able to use match on it as usual.

Putting it another way, I wish an algebraic data type "enum" was something any struct could "be", with the type system providing the means to express that that's the case, and the programmer being able to provide the "how" and with existing Rust enums merely being the default way of doing this.

patrec2• 3 years ago

Several languages have what I think you are asking for. Have a look at Scala's extractors or F#'s active views.

foderking• 3 years ago

you mean f# active patterns?

cmrdporcupine6• 3 years ago

Ah yes, many moons ago (like... almost 15 years) I worked in Scala and I recall extractors, or at least the discussion of them.

dan-robertson7• 3 years ago

An old trick for bytecode interpreters is to use indirect jumps for going to the next opcode’s implementation (gcc had a ‘computed goto’ extension that was used for this. For Rust I guess you would want function pointers plus something to force TCE?) and putting those indirect jumps at the prelude of every opcode implementation. This meant that the indirect-jump-predictor (which cpus have because of oop) would have separate models for the ends of different opcodes and so would be more likely to predict correctly (maybe you have a hard time predicting a the next instruction but it is much more likely that a test is followed by a branch).

I think other tricks (e.g. storing top of stack in registers for a stack machine) matter more though, and I don’t know if the trick described above is still relevant.

AndyKelley2• 3 years ago

For Zig this is planned via labeled continue syntax inside switch expressions: https://github.com/ziglang/zig/issues/8220

As mentioned in the proposal, this would even allow implementation of Duff's Device in Zig :-o

cmrdporcupine6• 3 years ago

Yeah I've spent time on this topic before when working in C++, but haven't invested much energy in thinking about how one would do it efficiently in Rust yet. Luckily performance is not my #1 concern, at least not yet. And maybe if I got down that road more I'd just invest in going JIT with cranelift or similar.

dist1ll5• 3 years ago

Just to add some jargon for folks who want to do more research into this:

The technique of having the interpreter dispatch duplicated in the postlude of each handler function is called "threading". If your dispatch uses an indirect jump, it's called "indirect threading". The indirect-jump-predictor is known as branch target predictor (BTB).

eximius• 3 years ago

I do with proc macros could evolve to be able to query the compiler for information (which would necessitate careful thought to adding stages to compiling). I've wanted to know "does this struct impl this trait" or "give me a list of all concretely implemented traits" or various things like this that would be very, very useful in a proc macro.

Arnavion• 3 years ago

IIRC the compiler runs plugins in two stages. The first stage gets the AST before any typechecking and it can make modifications to the AST; macros and some clippy lints run in this stage. The second stage runs after typechecking so it gets type information, but it cannot make any modifications; other clippy lints run in this stage.

emmanueloga_3• 3 years ago

This problem space feels like some variation of a packing problem [1]...

It would be nice to start with the end result (the human friendly structure) and generate data structure recommendations to reduce memory waste, respect alignment rules, and improve spatial locality of reference.

1: https://en.wikipedia.org/wiki/Packing_problems

__s• 3 years ago

I think the example code is bugged

field_map[idx] = svec.len - 1;

Would be wrong when svec contains size already at not the last svec entry

gilcot• 3 years ago

What about https://doc.rust-lang.org/reference/type-layout.html#the-ali...

Memory-efficient enum arrays in Zig

Related Stories