[HN Gopher] Flattening ASTs and other compiler data structures
___________________________________________________________________
Flattening ASTs and other compiler data structures
Author : fagnerbrack
Score : 252 points
Date : 2023-07-02 08:03 UTC (14 hours ago)
(HTM) web link (www.cs.cornell.edu)
(TXT) w3m dump (www.cs.cornell.edu)
| kazinator wrote:
| > _Instead of allocating Expr objects willy-nilly on the heap,
| we'll pack them into a single, contiguous array. Instead of
| referring to children via pointers, Exprs will refer to their
| children using their indices in that array._
|
| This isn't flattening; it's just an alternative heap
| representation. The shape of the AST hasn't changed. It's been
| done in many languages before; such as Lisps (packing cons cells
| and other objects into arrays, using bump allocation, and indices
| for pointers and such).
|
| Objects being in an array makes them convenient for GC to
| traverse them in a sweep pass after the marking is done. Marking
| walks the graph to find the reachable objects; sweep goes trough
| the flat arrays to clear the GC bits, and indicate unreachable
| objects for recycling.
|
| I don't think you will easily find a semi-serious Lisp
| implementation that just mallocs every cons cell individually.
| You'd have to put them into a global linked list to be able to do
| the sweep part of GC. Or a global array that just contains
| pointers. I've seen at least two toy Lisp project someone banged
| up in one weekend in which cons cells were malloced and leaked;
| GC was left as a giant TODO.
|
| Global arrays can end up happening anyway, even if cells come
| from a packed array heap. E.g. if you implement generational GC
| in a non-copying allocator, one way to round up the baby objects
| so you can sweep them in a fast GC cycle is to add them into an
| auxiliary array; that then represents the nursery.
| t43562 wrote:
| Flattened memory seems rather like normal memory. ie. it's linear
| and addressed by an offset. So you could "just" use a custom
| memory allocator that didn't bother with all the design
| considerations that are needed to be able to free memory and
| prevent fragmentation.
|
| It wouldn't get you the benefit of using 16-bit indices or
| whatever but it should still be helpful and might let you write
| your program very "normally".
| triska wrote:
| This is also how Prolog terms are represented on the heap in the
| Warren Abstract Machine (WAM). For instance, taking the example
| of the article, if we have an expression such as the Prolog term
| +(*(a,b), c), written using operator notation as:
| expr(E) :- E = a*b + c.
|
| Then we get a _flattened_ representation on the global stack of
| the virtual machine. In Scryer Prolog, we can inspect the WAM
| instructions with: ?- wam_instructions(expr/1,
| Is), maplist(portray_clause, Is).
|
| yielding: put_structure(*,2,x(3)).
| set_constant(a). set_constant(b).
| put_structure(+,2,x(2)). set_value(x(3)).
| set_constant(c). execute(=,2).
|
| Note how both compound terms are _linearized_ , and appear on the
| heap as: functor, followed by arguments, each occupying exactly
| one memory cell of the WAM. The arguments can point to other
| memory cells. The heap is an array of such cells, all of the same
| concrete (as opposed to abstract, i.e., WAM-level) type. For
| example, Scryer Prolog uses 8 bytes for each cell, making cell
| access and modification very efficient on 64-bit architectures.
| revskill wrote:
| I did something similarly for my Yaml to Sql compiler at
| https://yaml2sql.netlify.app.
|
| The process of flattening is kinda weird, but fun, worth the
| effort afterall.
|
| For example, the Boolean expression flatten is good exercise for
| who wants to try out:
| https://github.com/revskill10/yaml2sql/blob/main/app/query.r...
| tayistay wrote:
| I'm using this technique in a compiler [1]. One thing I really
| like about it is that, unlike pointers, I can reuse the integer
| indices (`ExprRef` in the article) between arrays. So, for
| example, I have separate arrays for the AST and computed types,
| which allows the AST to be immutable. (perhaps the article
| already mentions this advantage, but I didn't see it in the list
| of advantages)
|
| [1] https://github.com/audulus/lyte
| FullyFunctional wrote:
| I was surprised to see nodes still have two pointers
| ("references") given that you now know that that the first
| pointer will always point exactly to the next node. I've see
| https://github.com/rswier/c4 use that. Granted it doesn't make
| for the most readable code, but it's even smaller and faster.
| francasso wrote:
| This reminds me of a GDC talk where rust was praised because it
| forces you to either go mad because of the borrow checker or
| structure code using an entity component system. I find it funny
| that the value of the borrow checker in all these real world
| scenarios with complicated lifetimes is to find a way to avoid it
| entirely by putting stuff in arrays and reference them by their
| index.
| chubot wrote:
| Yes totally, I keep seeing people mention these arena /
| flattened tree and graph structures, without mentioning memory
| safety.
|
| And also weird claims that arenas solve memory safety problems
| in C, when it's equally likely (depending on the program) that
| they CAUSE dangling pointers, use-after-free, etc.
|
| The same issue comes up in slightly different ways in both
| C/C++ and Rust
|
| ---
|
| My comment on this post from 2 months ago:
|
| https://old.reddit.com/r/ProgrammingLanguages/comments/1350d...
|
| Summary: the upsides are very real, but we should mention the
| downsides too:
|
| - Arenas punt on memory safety; Ownership can be nontrivial (a
| bunch of examples)
|
| - Mutation, and appending to list/vectors are complications
|
| - Pointer representations are more friendly to debuggers
|
| My wiki page is linked at the bottom of this article (which I
| appreciate because it actually has code and measurements!)
|
| https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
| kazinator wrote:
| > _when it 's equally likely (depending on the program) that
| they CAUSE dangling pointers_
|
| Packing your objects into their own tight heap not only
| doesn't solve memory allocation issues, but makes them harder
| to debug. The tools for fighting these problems in C don't
| work as well.
|
| In TXR Lisp, I have to have a number of strategies in place
| for debugging GC issues.
|
| One is Valgrind integration. If you want to use Valgrind, but
| have implemented your own bump allocation within packed
| heaps, Valgrind won't be as helpful.
|
| For example, what is a semantic use-after-free in your world
| (something accessing an object that has been garbage
| collected) looks fine to the C library; you're just
| dereferencing a pointer into a large object that you
| allocated just fine.
|
| With Valgrind integration, you can use the API mark free
| objects inaccessible. But: that only means Valgrind will
| detect the wrong use of a reclaimed object (quite swiftly,
| thank you very much). It will not tell you who allocated that
| object. The diagnostic will be something like "invalid read,
| 15300 bytes into a 262164 object, allocated at <call stack>".
| That is not very useful! It gives you the call stack when
| that entire heap was allocated, not when that misused object
| within that heap was allocated.
|
| I have some debug support which takes advantage of
| reproducible repro test cases where we can count on addresses
| of bad objects being the same. Once I know the address of the
| offending object, I can put it into a debug variable called
| _break_obj_. When the object is allocated or reclaimed, there
| is a VALGRIND_PRINTF which will dump a trace. I can also get
| a breakpoint in gdb (that 's why it's the _break_obj_ ).
|
| There is also an option to run the GC in a kind of torture
| mode where garbage collection is invoked on every allocation.
| Newly allocated objects that are not properly retained by the
| caller (made visible to gc) will be scavenged immediately,
| revealing those kinds of bugs by bringing the allocation and
| misuse contexts close together. A substantial portion of the
| test suite runs in this GC torture mode. Not everything,
| because it's quite slow.
| dist1ll wrote:
| Correct. Rust lifetimes become less powerful in certain niches
| of high-performance programming where you're avoiding the heap
| or don't have one in the first place. Games, databases,
| embedded, HPC-style batch workloads, and even compilers.
|
| Of course you still have restrictions on aliasing, so you're
| not going to get data races. But you'll still get bugs that are
| essentially equivalent to ones you'd get with raw pointers.
| pornel wrote:
| Note that you still have implicit/elided lifetimes for
| basically every function argument and every local variable.
| They're everywhere, even if you're not typing 'a.
| PartiallyTyped wrote:
| You could say that it forces you to define long living entities
| that _own_ memory and _lend_ it to short-lived objects.
|
| In the process you avoid use-after-free, double-free, and
| accessing unallocated memory because the borrowers always live
| shorter lives than the owners, and can only access borrowed and
| thus allocated memory that is deallocated once the owner dies,
| and there is nobody else who can use it or free it once more.
| verdagon wrote:
| Ironically, we could say that we're _losing_ the true
| ownership relationships between the objects, and we 're
| making medium-term memory leaks more likely; drop() can free
| a Box pointing to a child, but can't free an index. In other
| words, we lose the guarantee that an element is released for
| reuse.
|
| AFAICT, a language would need something like higher RAII [0]
| or linear types [1] for that. I'd love to see Rust adopt
| these features too one day, though it may be difficult to do
| backwards compatibly.
|
| [0] https://verdagon.dev/blog/higher-raii-7drl
|
| [1] https://austral-lang.org/linear-types
| PartiallyTyped wrote:
| Re linear types, Rust actually has an affine typesystem,
| and the compiler complains when you move a variable and try
| to access it, so instead you need to provide a reference if
| you intend to do that multiple times.
|
| A reference is a new object that references an existing
| memory value. You can not store a reference unless the
| borrow-checker can prove that the object that stores it has
| a shorter lifetime than the referenced object.
|
| That is also why you can't just pass that reference around
| willy-nilly, because the reference is consumed due to
| affine types.
|
| I may be misunderstanding something though so feel free to
| correct me.
| eyelidlessness wrote:
| It's almost as if immutability writ large is vindicated, but
| with a whole lot of complicated rules to let mutation infect
| everything everywhere even if you'll never use it. At least
| that was my takeaway trying to learn Rust.
| Flow wrote:
| Do you think a purely functional language without GC would
| be much simpler than Rust and Rust's borrow checker? I
| don't think the mutation part of Rust is what makes it
| complicated.
| c_crank wrote:
| Ada has better tools for the task if mutability is allowed.
| jlokier wrote:
| _> In the process you avoid use-after-free, double-free, and
| accessing unallocated memory_
|
| You don't really avoid those things, though. In the process
| you end up with index-use-after-index-free, double-index-
| free, and accessing index-unallocated array entries.
|
| These are the exact same bugs the borrow checker prevents in
| main memory, just hidden from the borrow checker by adding a
| layer of abstraction.
|
| These are memory-unsafety bugs. You still get the same wrong
| answers caused by coding errors. Random junk values and
| behaviours, when dereferencing use-after-free invalid
| pointers that point to memory reused for a new object. It's
| just that pointers are now called indexes, and the borrow
| checker doesn't check these pointers.
|
| It's like turning the borrow checker off for this set of
| objects. Those long-lived entities you mentioned act as a
| mechanism to enable that. That's useful to do, but nobody
| should be under the impression use-after-free, pointers to
| the wrong objects and other memory-unsafety bugs don't happen
| in the array index model.
| PartiallyTyped wrote:
| That's the specific case of (mis)using an arena, no? Could
| this be extended to the general model of ownership?
| skybrian wrote:
| Yes, this is true, but sometimes it's because pointer
| ownership is a poor fit for the problem. Sometimes dangling
| references are logically possible and what you want. (There
| should be a runtime check, though. Generation numbers can
| help.)
|
| A compiler can only prevent bad things from happening
| within a system, typically just one process. The world
| around it doesn't work that way. A system is often a cache,
| not an owner, and caches go out of date because the world
| changed without notice. You want to update on what notices
| you get that the world changed. You can't prevent
| inconsistency, only detect it and react by updating or
| removing outdated information.
|
| This probably isn't relevant within a batch compiler, but
| it would be for a language service in an IDE.
|
| Games often simulate worlds where references shouldn't own
| things. It would be a weird form of power to remotely
| prevent something from getting destroyed because you
| remember it. Even though both objects are within the same
| process, they're modeled as independent systems where
| pointer ownership doesn't happen.
| avgcorrection wrote:
| > These are memory-unsafety bugs.
|
| It seems that these are memory-unsafety bugs with the
| caveat that they have nothing to do with the memory
| allocator. Maybe a sort of _sandboxed_ memory unsafety? I
| don't know.
| kmstout wrote:
| > nothing to do with the memory allocator
|
| It's an application-specific memory allocator.
| avgcorrection wrote:
| That's in effect what I'm saying. You've implemented a
| memory allocator using the "system" one.
| noelwelsh wrote:
| Using an entity component system felt like writing very fancy
| spaghetti code in my limited experience with the Bevy game
| engine in Rust. No longer having direct references between
| objects means the type system isn't nearly as useful and I
| found it very hard to reason about the code. I can believe it
| becomes useful in very large systems but it was just a
| hinderance in the small program I was writing.
| logicchains wrote:
| You can use phantom-typed index types (a wrapper type per
| container) to recover type safety. Or at least you can when
| using an ECS in C++; I'm not sure how easy it is to write the
| wrapper types generically in Rust.
| pornel wrote:
| You can have typed indices (https://lib.rs/crates/typed-
| index-collections), but unless you force the collection to
| be a singleton, there's no way to prevent mixing of indices
| between different instances (clones) of the same collection
| type.
| syntheweave wrote:
| A lot of the mangling produced by ECS is an outcome of
| representing dynamic behaviors through static optimizations.
|
| If you have a dynamic type that you can attach arbitrary new
| fields to, then, capability-wise, you have exactly what's
| needed to make game entities: to do a lookup by entity type,
| just traverse the list of all entities looking for a magic
| pattern in the data. To look up a specific one, assign each
| one a unique ID and search by ID.
|
| The problem is that game developers get anxious about this
| kind of lackadaisical structure(for good reason, if there's
| any aim at serious performance) and want to put more things
| in their own index, and allocate things with a more compact
| representation and less fragmentation.
|
| And the alternatives are...god object with every possible
| behavior crammed into an oversized record type, and ECS
| bookkeeping, in its various flavors, some more compilation-
| heavy and others more reflective with more runtime editing
| functionality.
|
| But regardless of what approach you take, every time you
| introduce dynamism into your entities and enable more
| flexibility in asset assignment, you convert more of your
| bugs into data bugs. There are a huge number of bugs in games
| that are configuration problems with the entity and not a
| flow control or algorithms issue.
| bregma wrote:
| Pointers are just indexes into memory space. Seems to me that
| if Rust is trying to solve a general programming problem the
| borrow checker needs to handle all indexes, not just those
| specialized for memory space.
| dist1ll wrote:
| I feel that for this to be really viable, Rust would have to
| allow references that consume less memory (like 8-bit or
| 16-bit pointers).
| jmmv wrote:
| Interesting. When I read the title, I thought "flattening ASTs"
| would refer to eliminating control structures (ifs and loops) and
| converting those to a flat list of instructions with jumps
| (gotos) between them.
|
| And the reason I thought that is because I used this term,
| "flattening ASTs", when implementing "bytecode compilation" for
| EndBASIC (see https://jmmv.dev/2022/11/endbasic-bytecode.html).
| This kind of flattening had the nice side-effect of unlocking the
| ability to implement GOTO as well as the ability to more-
| accurately capture and handle "interrupts" in the language
| executor.
|
| Anyhow, I'll have to keep this article in mind when I end up
| implementing flattening for expression evaluation as well, which
| I haven't gotten around to yet :P
| Joker_vD wrote:
| AFAIK, many BASIC implementations worked in-place: each input
| line was replaced by its tokenization, then by the bytecode,
| then the labels would be resolved. Consequently, printing the
| program listing was not a matter of simple "print all earlier
| input lines" (those are gone), it involved actual pretty-
| printing.
|
| In fact, replacing the program text with its tokenization as
| the first compilation step was a very popular strategy back in
| the day, due to memory constraints. IIRC the early IBM FORTRAN
| compilers, being quite large (they performed quite a lot of
| optimizations), would not even fit into the core memory
| together with the source code of any reasonably useful program.
| So they were instead written as a series of passes (about fifty
| or so, I believe) each of which took the output of the previous
| pass and transformed it into the input for the next one; the
| tokenizer was quite tiny but it freed lot of space (text is
| _quite_ redundant) so the next passes had room for the
| auxiliary structures and could themselves be larger, too.
| jmmv wrote:
| Right, thanks. That's more than I knew about how the old
| interpreters worked, although I suspected something along
| these lines.
|
| This explains why I have had so much trouble representing the
| language as an AST, and I tried to cover this in this other
| post: https://jmmv.dev/2023/01/endbasic-parsing-
| difficulties.html
| raphlinus wrote:
| I love flattened ASTs. One of my favorite uses of them is for
| inline markup in pulldown-cmark (see [1] for a brief
| description).
|
| Here's a sketch of the problem being solved. The raw input is
| broken into a sequence of nodes, and something like * is turned
| into a "MaybeEmphasis" node, as it has the potential to turn into
| emphasis, or remain text if no match for it is found.
|
| Another pass goes through those nodes in sequence, using a stack
| to find potential matches (the rules for whether a pair of such
| nodes actually match are quite fiddly and complicated). When a
| match is found, the MaybeEmphasis node is turned into the
| appropriate emphasis node, and the entire sequence of nodes
| between open and close is snipped out and made into a subtree of
| the new node. This is a somewhat unusual tree transformation, and
| a straightforward implementation could easily be O(n). But with
| the flattened AST representation, it can all be done O(1), no
| matter the number of nodes or stack depth.
|
| For those interested in details, the tree representation is in
| [2] - there's basically a "child" and "next" index along with the
| node body - and the tree surgery on emphasis match is in [3].
|
| The performance is excellent. I think pulldown-cmark may not be
| _the_ single fastest CommonMark parser out there, but it 's
| certainly competitive, and a lot faster than approaches that do,
| for example, an allocation per node.
|
| [1]: https://fullyfaithful.eu/pulldown-cmark/
|
| [2]: https://github.com/raphlinus/pulldown-
| cmark/blob/b7e709c0bd6...
|
| [3]: https://github.com/raphlinus/pulldown-
| cmark/blob/b7e709c0bd6...
| [deleted]
| ithkuil wrote:
| I used such a succinct AST structure to implement a JavaScript
| parser and interpreter for a severely memory constrained
| environment (embedded): V7 (https://github.com/cesanta/v7)
|
| We later switched to a ast->bytecode compilation step but for a
| while the implicit AST was directly traversed during
| interpretation.
| hgs3 wrote:
| Good article, but I'll mention two gotchas:
|
| 1. Storing nodes in a resizable array means as the input program
| grows the compiler will need a larger and larger block of
| contiguous memory (which may or may not be available). You could
| work around this by allocating page-sized blocks to pool from.
|
| 2. Care needs to be taken with how AST nodes are represented in
| code. For example, using a union type to store nodes is self-
| defeating as a union type is as large as its largest member and
| since not all AST nodes are equal size, this means small AST
| nodes will be pointlessly padded to account for the size of the
| largest AST node.
| comonoid wrote:
| Can be mitigated by a rope(?) structure (i.e. the vector is
| split into chunks of fixed size, no re-allocation required)
| with real pointers. It will be unsafe inside, but safe (read-
| only) interface seems to be possible.
|
| Deallocation will be O(n), but still much faster than a tree.
| dist1ll wrote:
| > small AST nodes will be pointlessly padded to account for the
| size of the largest AST node.
|
| This is a great point, and something I mentioned in my blog
| post on custom-bitwidth integer types:
| https://alic.dev/blog/custom-bitwidth
|
| Discriminated unions can work, but you have to be clever with
| your memory footprint.
| Joker_vD wrote:
| Sometimes I wish we didn't end up with flat address spaces. The
| "virtual memory" technique allows us to stitch fragmented
| regions of physical memory into a contiguous region of virtual
| memory and if virtual address space was segmented, it simply
| would not ever become fragmented; any memory region could
| always be grown in-place, without intersecting with any other
| region, so realloc() implementations could just drop their
| memcopy() paths... oh well.
| tempodox wrote:
| I haven't seen RPN inside a compiler yet, but that's actually not
| a bad idea. Interesting article.
| vanderZwan wrote:
| Aren't stack machines the bread and butter of many intermediate
| representations? Or is that more of an interpreter thing than a
| compiler thing?
| pjmlp wrote:
| They are for executable formats.
|
| On compiler IR, the modern way is to use SSA rather.
| HarHarVeryFunny wrote:
| When I think of "arena" related to memory management, it's not
| about "flattening", but just an arena allocator ... When you're
| allocating a bunch of items with the same lifetime, you can more
| efficiently allocate them from one or more large chunks of
| memory, and then at the end of their collective lifetime you free
| the large chunk(s) rather than freeing the items individually.
| The allocation can also be more efficient since you can just
| incrementally use the space in the parent chunk - no need for
| free-lists like a general purpose heap allocator.
|
| In this context, the "flattening" aspect of this - using indices
| rather than pointers - could be viewed just as using pointers
| (offsets) that are relative to the parent chunk.
| jnordwick wrote:
| [flagged]
| planetis wrote:
| Same ideas are used in Nim's incremental compilation (wip)
| https://github.com/nim-lang/Nim/tree/devel/compiler/ic Also there
| are two JSON implementations with a flat architecture
| https://github.com/Araq/packedjson and
| https://github.com/planetis-m/packedjson2 (this one I wrote) But
| I agree it's a pain to write it like that.
| ergeysay wrote:
| One more JSON implementation using this approach is
| https://github.com/zserge/jsmn.
| TazeTSchnitzel wrote:
| Blender (the 3D modelling software) is a fascinating case of
| this. To make loading and saving files fast and lossless, it uses
| identical on-disk and in-memory representations. In other words,
| everything is in an arena, and saving and loading is just a
| memcpy of the entire arena. Considering the massive potential
| complexity of a Blender project and the myriad issues you could
| have with serialisation and deserialisation, this seems like a
| great design to me.
|
| The trade-off of course is that your data structure design is
| kinda sticky, insofar as you need to be able to open files for
| older versions.
| 3cats-in-a-coat wrote:
| You can have the benefits of fast save and load without having
| the same representation. Stream changes to disk.
| seventhson wrote:
| I once worked on a very large commercial application that was
| based on a home-grown I/O framework which operated on similar
| principles.
|
| It was a complete pain in the ass. You were constantly future-
| proofing your data structures because you knew you were going
| to be stuck with them for all eternity because the I/O
| framework was going to serialize them verbatim whether you
| liked it or not. Those were dark days...
| Solvency wrote:
| I don't get it. Surely if you ever needed to, you could write
| an interpreter for loading tbe older files if you decided to
| abandon this 1:1 representation?
| dragontamer wrote:
| You ever hear of .doc files?
|
| https://learn.microsoft.com/en-
| us/openspecs/office_file_form...
|
| Yeah. There is a reason XML was seen as the future back in
| the 90s.
|
| Custom databases often get extended into custom
| filesystems. And these systems on top of systems get
| obscure features (like embedding excel sheets inside of
| Word) and... Thing get hairy.
| amomchilov wrote:
| I think the effort involved disincentivizes against it, and
| nudges people towards defensively adding spare fields or
| whatever.
|
| The other comment pointed out that you can make a fall back
| migration code path that migrates over older file versions.
| That's the escape hatch if you have no other options
| giovannibonetti wrote:
| > The trade-off of course is that your data structure design is
| kinda sticky, insofar as you need to be able to open files for
| older versions.
|
| The missing piece is a way to evolve those data structures over
| time, in a similar way to database migrations. Only when
| loading data from an older version of the app those operations
| would need to be issued, and then the app could save the
| updated version in disk immediately to avoid incurring that
| cost again.
|
| An example implementation of this concept is this project [1]
| that was created in the context or CRDTs. If it is not directly
| applicable, at least it should be a good inspiration.
|
| [1] https://www.inkandswitch.com/cambria/
| pavlov wrote:
| I believe Microsoft Word originally did this, and it was a
| major pain as the file format evolved.
| jeffreygoesto wrote:
| Wasn't that also the way Word used to dump structs onto disc in
| the "doc" days? I think I read that way also a major problem in
| writing converters, you baobab needed to decode Word's internal
| data structures which were of course undocumented.
| orthoxerox wrote:
| I remember Spolsky saying Excel .xls worked like this, but I
| guess this should apply to .doc files as well.
|
| This is usually orders of magnitude faster than serializing
| to/deserializing from a different storage format.
| bestouff wrote:
| I don't think so. Serializing is IO-bound, if your format
| is "simple" (e.g. CBOR) you can't measure the difference.
|
| All this look like BS to justify laziness to me, and makes
| loading/saving operations fragile and setting in-memory
| structures in stone.
| Joker_vD wrote:
| > Serializing is IO-bound
|
| Once upon a time, DMA did not meaningfully exist in the
| x86 world, so an IO-bound task was _also_ CPU-bound.
| bestouff wrote:
| Yes of course, but the original example was Blender,
| running on today's hardware. IMO this is just sloppy
| engineering in this case.
| orthoxerox wrote:
| Don't forget that Excel file format is literally 30 years
| old. When you have 4MB of RAM in total for your OS, Excel
| and whatever part of the file you can fit into the rest
| and your CPU is an i486 if you're lucky, minimizing
| parsing starts to make lots of sense.
| masklinn wrote:
| It's very common in old software and video games. Pre-97
| office did that though with more formalisation than most (the
| binary format is now called Binary Interchange File Format,
| or BIFF, and is relatively generic, at the time MS almost
| certainly had utility libraries for working with BIFF).
|
| This was a common source of portability issues for game saves
| (as well as blowing your saves on updates), as they'd
| commonly just blit internal data structure, with no
| formalised interface.
| agumonkey wrote:
| And potentially photoshop.
| glandium wrote:
| It also means you can't share files between little endians and
| big endians.
| rollcat wrote:
| There's almost certainly byte order+version markers in the
| header, a "happy path" that just memcpy's the structs, and a
| "safe path" that does byte order swapping, migrates the old
| structs to the current format, etc.
|
| You can version the structs/loaders by keeping the relevant
| header files in their own version subfolders, and copious
| usage of sed. I've done this in a Django project to maintain
| support for ancient untouchable clients using an old version
| of the API, it's pretty manageable.
| tjalfi wrote:
| I checked the repo. Blender detects files with a different
| endian and byte swaps if necessary.
| WJW wrote:
| Is this a real problem though? It seems to me that any system
| you would realistically want to run Blender on will be
| little-endian.
| tjalfi wrote:
| It isn't a real problem. Blender supports only little-
| endian targets and the code byte swaps data files as
| needed. I guess someone could port it to AIX, z/OS, or
| Linux/zSeries, but that's unlikely at best.
| [deleted]
| grogenaut wrote:
| This is exactly how a PlayStation game I worked on worked and
| because everything was signed they were in no way worried about
| attackers. If you were able to alter the files on disk you had
| already owned your device. It meant loading was absurdly fast
| we pulled everything in the memory and then just patched
| pointer locations to where they actually got loaded
| bjourne wrote:
| That is of course not Kosher at all. Compilers are generally
| free to layout and pad structs in whichever way they prefer,
| meaning that two compilers for the same platform might very
| well use incompatible layouts. It can lead to major problems if
| structs saved by say a 64-bit version of the program is to be
| loaded by the 32-bit version.
| azornathogron wrote:
| Compilers (for C and C++) typically provide mechanisms to
| control padding and other layout requirements as necessary to
| make this work.
|
| It's not that unusual in C and C++ code to define a struct
| that has a specific and well-defined memory layout. It's
| kosher, as long as you accept that you're working with a
| specific set of real compilers and use the appropriate
| #pragmas or other controls as needed to avoid undefined
| behaviour.
| [deleted]
___________________________________________________________________
(page generated 2023-07-02 23:01 UTC)