18 ms·

Memory-efficient enum arrays in Zig

• __s 3y 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
• wyldfire 3y 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?
  • anonymoushn 3y 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 3y 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.
  • cryptonector 3y 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 3y ago
      Maybe I'm just dumb but isn't the endgame of vec of enums going to be an ECS?
      • setr 3y ago
        And the end game of ecs is a columnar rdbms
  • deleted 3y ago
    [deleted]
  • dan-robertson 3y 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).
  • AndyKelley 3y 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
    • wyldfire 3y 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)?
• sdfghswe 3y 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...?
  • Sharlin 3y 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 3y 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
      • Semaphor 3y 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 I think "cult following" is used here like you would for movies, it’s not actually cult-like, it’s more that it’s a rather small, close-knit community.
    • pron 3y 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.
• BaculumMeumEst 3y 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 3y 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.
  • insanitybit 3y 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.
  • sdfghswe 3y 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.
• ForkMeOnTinder 3y 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.
  • dist1ll 3y 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 3y ago
      I'd love for someone to benchmark these variants to tease out their actual characteristics (particularly for x86).
    • dan-robertson 3y 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.
• Joker_vD 3y 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 3y ago
    Don't you mean something like [A+B+C] ≃ [A]×[B]×[C]
  • pornel 3y 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 3y 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.
    • 3y ago
• pornel 3y 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.
  • avgcorrection 3y 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.)
    • insanitybit 3y ago
      I don't think anyone has ever been surprised to find that a type system (with inference) is turing complete.
  • Ar-Curunir 3y 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 3y 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 https://aphyr.com/posts/342-typing-the-technical-interview
  • dist1ll 3y 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.
• fweimer 3y 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 3y 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.)
  • catgary 3y ago
    Yeah I imagine an array write that changes the type of an index would be insanely expensive…
    • Aransentin 3y 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.
      • MobiusHorizons 3y ago
• bfrog 3y 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 3y ago
    > I still have yet to understand if Zig actually provides memory safety in the same manner Rust does or not It doesn't.
    • bfrog 3y 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.
      • cmrdporcupine 3y ago
        It's more than that in that it has a sane syntax and module and build system. I'm a Rust person by both day job and hobby, but I can see the niche Zig is in as being quite useful in particular for embedded work. One thing it definitely has over Rust is way better support for explicit per-structure allocator/allocation management. The allocator_api stuff in Rust has just been sitting unstable for years at this point, while Zig shipped with support for this immediately. Which is key for work in all sorts of systems level contexts. Probably the language I want is somewhere between the two.
        • deleted 3y ago
          [deleted]
        • bfrog 3y ago
          I mean I really have a hard time going backwards on the whole idea of lifetimes and send/sync type traits which force escape hatches if you want to do something idiotic. The key piece here is, any project of significant size and usage, someone will try to do something stupid. Rust makes the stupid so obvious with unsafe blocks and annotations, that reviewing code from some random person on the internet is made easier. The tooling made the task of reviewing code mostly limited to the code being changed rather than the whole project. In C/C++ land you need to consider not only the code being changed but also the entire code base and how that code is used. It's not enough to look at the diff. You need to understand the context. Not to say that isn't also true with Rust to some degree, but the degree is usually in terms of logic and less "is some pointer/reference going to cause a race/segfault/buffer xflow?" The langauge itself doesn't define allocation, Box is in the stdlib and this allows for nostd libraries to deal with things as I guess most of us might expect I'd think. It would be cool to allow for a global allocator though to enable std on more platforms with better semantics, no disagreement there.
• deleted 3y ago
  [deleted]
• zoogeny 3y 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.
  • dist1ll 3y ago
    Thanks! It's inspired by this https://edwardtufte.github.io/tufte-css/ https://edwardtufte.github.io/tufte-css/
    • ghosty141 3y ago
      Thanks for sharing this! Looks fantastic, I'll definitely incorporate this into my own blog once it's finished.
      • chrismorgan 3y ago
        If you’re interested in the general concept of sidenotes and labelling figures in the margin, here’s my take on it for further inspiration: https://chrismorgan.info/blog/2019-website/ https://chrismorgan.info/blog/2019-website/, with https://chrismorgan.info/blog/rust-fizzbuzz/ https://chrismorgan.info/blog/rust-fizzbuzz/ exhibiting figures. Do search around for other sidenote implementations, too. I like the markup and presentation I end up with, but you’ll also find other approaches to mobile support in particular, involving things like checkbox hacks to toggle visibility, or just flat-out requiring JavaScript.
    • ammar2 3y ago
      Another quick question for you, what are you using to make those hand-drawn looking diagrams? They look amazing.
      • dist1ll 3y ago
        I'm using Excalidraw :) [0] https://excalidraw.com/ https://excalidraw.com/ [1] https://github.com/excalidraw/excalidraw https://github.com/excalidraw/excalidraw
  • 3y ago
• kazinator 3y 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 }; }
  • cryptonector 3y ago
    But it's C. The idea here is to have higher-level, type-safe languages do this transformation automatically.
  • deleted 3y ago
    [deleted]
    • deleted 3y ago
      [deleted]
  • masfuerte 3y ago
    But this still takes 9 bytes (at least) to store a tagged uint8_t.
    • kazinator 3y 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.
      • masfuerte 3y ago
        The final approach in the article is an array for each unique object size plus tagged indices/pointers. This would take one byte per uint8_t and doesn't suffer from the problems you mention, though it does have others. If memory pressure is your main problem it's a big win.
• Andrew018 3y ago
  [dead]
• npigrounet 3y ago
  [dead]
• airstrike 3y 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 3y 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.)
    • airstrike 3y ago
      Thanks, great point indeed. I am looking into this https://github.com/rust-lang/hashbrown 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 3y 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)
• cmrdporcupine 3y 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.
  • aw1621107 3y 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 https://en.wikipedia.org/wiki/Structural_type_system
    • cmrdporcupine 3y 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.
• eximius 3y 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 3y 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_ 3y 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 https://en.wikipedia.org/wiki/Packing_problems
• gilcot 3y ago
  What about https://doc.rust-lang.org/reference/type-layout.html#the-alignment-modifiers https://doc.rust-lang.org/reference/type-layout.html#the-ali...