Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Static Allocation with Zig

nickmonad.blog

Post reply on HN
Print view View original

61–70 of 112 posts

Re: Static Allocation with Zig

#61

Post by kibwen »

d3ckard wrote: post #45
kibwen wrote: post #31

Earlier quoted context omitted.

> It’s the only kind of program that can be actually reasoned about. Theoretically infinite memory isn't really the problem with reasoning about Turing-complete programs. In practice, the inability to guarantee that any program will halt still applies to any system with enough memory to do anything more than serve as an interesting toy. I mean, I think this should be self-evident: our computers already do have finite…

Yes, but allocations generate ever increasing combinatorial space of possible failure modes. Static allocation requires you to explicitly handle overflows, but also by centralizing them, you probably need not to have as many handlers. Technically, all of this can happen as well in language with allocations. It’s just that you can’t force the behavior.

Sure, but let's be clear: it's a tradeoff. If every program reserved as much memory at startup as needed to service 100% of its theoretically-anticipated usage, the amount of programs we could run in parallel would be drastically reduced. That is to say, static allocation makes OOM conditions dramatically more likely by their very nature, because programs are greedily sitting on unused memory that could be doled out to other processes.

Re: Static Allocation with Zig

#62

Post by kibwen »

matklad wrote: post #57
leumassuehtam wrote: post #2

> All memory must be statically allocated at startup. No memory may be dynamically allocated (or freed and reallocated) after initialization. This avoids unpredictable behavior that can significantly affect performance, and avoids use-after-free. As a second-order effect, it is our experience that this also makes for more efficient, simpler designs that are more performant and easier to maintain and reason about, com…

To add more context, TigerStyle is quite a bit more than just static allocation, and it indeed explicitly attributes earlier work: > NASA's Power of Ten — Rules for Developing Safety Critical Code will change the way you code forever. To expand: * https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI... * https://spinroot.com/gerard/pdf/P10.pdf

Those guidelines are quite clear that they're written specifically in the context of the C programming language, and may not make sense in other contexts:

"For fairly pragmatic reasons, then, our coding rules primarily target C and attempt to optimize our ability to more thoroughly check the reliability of critical applications written in C."

A version of this document targeting, say, Ada would look quite different.

Re: Static Allocation with Zig

#63

Post by dnautics »

chris- wrote: post #44
dnautics wrote: post #32

Earlier quoted context omitted.

out of curiosity, does that generally mean that (linux) OOM killer can't get you? IIRC the oom killer is only triggered on new page request, and only the requesting process is eligble for the murder?

No, it does not. The oom killer acts on (mostly) the oom score and no process is exepmt, regardless of whether or not it allocates new memory. It may help you write correct programs in certain situations though, eg. if your program was running in a defined context, eg. a cgroup, and you would not allocate beyond your cgroup limits, and the system was configured sanely, you can handle allocation problems easier.

aw damn. thanks for clarifying.

Re: Static Allocation with Zig

#64

Post by chris- »

brabel wrote: post #35
mitchellh wrote: post #17

Earlier quoted context omitted.

Snide and condescending (or at best: dismissive) comments like this help no one and can at the extremes stereotype an entire group in a bad light. I think the more constructive reality is discussing why techniques that are common in some industries such as gaming or embedded systems have had difficulty being adopted more broadly, and celebrating that this idea which is good in many contexts is now spreading more broa…

> had difficulty being adopted more broadly Most applications don’t need to bother the user with things like how much memory they think will be needed upfront. They just allocate how much and when necessary. Most applications today are probably servers that change all the time. You would not know upfront how much memory you’d need as that would keep changing on every release! Static allocation may work in a few domai…

That's just saying "we push our memory problems up the stack so our clients / users need to deal with that". The reason this works is because human users in particular have become accustomed to software being buggy and failing often.

Re: Static Allocation with Zig

#65

Post by pron »

matklad wrote: post #59
nromiun wrote: post #14

> All memory must be statically allocated at startup. But why? If you do that you are just taking memory away from other processes. Is there any significant speed improvement over just dynamic allocation?

See https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI... for motivation. - Operational predictability --- latencies stay put, the risk of threshing is reduced (_other_ applications on the box can still misbehave, but you are probably using a dedicated box for a key database) - Forcing function to avoid use-after-free. Zig doesn't have a borrow checker, so you need something else in its place. Static alloca…

> Forcing function to avoid use-after-free

Doesn't reusing memory effectively allow for use-after-free, only at the progam level (even with a borrow checker)?

Re: Static Allocation with Zig

#66

Post by mytailorisrich »

publicdebates wrote: post #37
leumassuehtam wrote: post #2

> All memory must be statically allocated at startup. No memory may be dynamically allocated (or freed and reallocated) after initialization. This avoids unpredictable behavior that can significantly affect performance, and avoids use-after-free. As a second-order effect, it is our experience that this also makes for more efficient, simpler designs that are more performant and easier to maintain and reason about, com…

> a technique known for 30+ years in the industry have been Knowledge sharing with next generations is one of those very tricky things. For one thing, how would I know where to find this? What book? What teacher? There are so many books, must I read all of them? What if my coworkers awaren't aware of it, how can they share it with me? Also, an old saying goes, if you're good at something, never do it for free. This i…

I'd say usually you learn those techniques when you join a company as a junior dev and come in contact with engineers with decades of experience and systems that have been in production for years, too.

I think it's when people consider that anything more than 5 years old is ancient and dismiss it that we lose established techniques and knowledge that we are then bound to rediscover again and again.

Re: Static Allocation with Zig

#67

Post by AlotOfReading »

kibwen wrote: post #62
matklad wrote: post #57

Earlier quoted context omitted.

To add more context, TigerStyle is quite a bit more than just static allocation, and it indeed explicitly attributes earlier work: > NASA's Power of Ten — Rules for Developing Safety Critical Code will change the way you code forever. To expand: * https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI... * https://spinroot.com/gerard/pdf/P10.pdf

Those guidelines are quite clear that they're written specifically in the context of the C programming language, and may not make sense in other contexts: "For fairly pragmatic reasons, then, our coding rules primarily target C and attempt to optimize our ability to more thoroughly check the reliability of critical applications written in C." A version of this document targeting, say, Ada would look quite different.

The JPL C rules are quite old, but avoiding dynamic allocation outside initialization is am considered best practice for spaceflight software regardless of language. Here's the recommendation from NASA's language-agnostic cFS:

    4.2.4 Consolidate Resource Allocations
    It is generally recommended to consolidate resource allocations to the application initialization function(s). Allocations and setup of resources such as memory pools and child tasks should happen once during initialization in order to provide more determinism during run time.
From: https://github.com/nasa/cFE/blob/main/docs/cFE%20Application...

The ESA Ada standard also recommends all allocation occur at initialization, and requires exceptions to be justified.

Re: Static Allocation with Zig

#68

Post by fsckboy »

matklad wrote: post #56
MatthiasPortzel wrote: post #38

One key thing to understand about TigerBeetle is that it's a file-system-backed database. Static allocation means they limit the number of resources in memory at once (number of connections, number of records that can be returned from a single query, etc). One of the points is that these things are limited in practice anyways (MySQL and Postgres have a simultaneous connection limit, applications should implement pagi…

Yes, very good point, thanks! As a tiny nit, TigerBeetle isn't _file system_ backed database, we intentionally limit ourselves to a single "file", and can work with a raw block device or partition, without file system involvement.

>we intentionally limit ourselves to a single "file", and can work with a raw block device or partition, without file system involvement

those features all go together as one thing. and it's the unix way of accessing block devices (and their interchangeability with streams from the client software perspective)

you're right, it's not the file system.

Re: Static Allocation with Zig

#69

Post by matklad »

pron wrote: post #65
matklad wrote: post #59

Earlier quoted context omitted.

See https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI... for motivation. - Operational predictability --- latencies stay put, the risk of threshing is reduced (_other_ applications on the box can still misbehave, but you are probably using a dedicated box for a key database) - Forcing function to avoid use-after-free. Zig doesn't have a borrow checker, so you need something else in its place. Static alloca…

> Forcing function to avoid use-after-free Doesn't reusing memory effectively allow for use-after-free, only at the progam level (even with a borrow checker)?

There's some reshuffling of bugs for sure, but, from my experience, there's also a very noticeable reduction! It seems there's no law of conservation of bugs.

I would say the main effect here is that global allocator often leads to ad-hoc, "shotgun" resource management all other the place, and that's hard to get right in a manually memory managed language. Most Zig code that deals with allocators has resource management bugs (including TigerBeetle's own code at times! Shoutout to https://github.com/radarroark/xit as the only code base I've seen so far where finding such bug wasn't trivial). E.g., in OP, memory is leaked on allocation failures.

But if you manage resources manually, you just can't do that, you are forced to centralize the codepaths that deal with resource acquisition and release, and that drastically reduces the amount of bug prone code. You _could_ apply the same philosophy to allocating code, but static allocation _forces_ you to do that.

The secondary effect is that you tend to just more explicitly think about resources, and more proactively assert application-level invariants. A good example here would be compaction code, which juggles a bunch of blocks, and each block's lifetime is tracked both externally:

* https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...

and internally:

* https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...

with a bunch of assertions all other the place to triple check that each block is accounted for and is where it is expected to be

https://github.com/tigerbeetle/tigerbeetle/blob/0baa07d3bee7...

I see a weak connection with proofs here. When you are coding with static resources, you generally have to make informal "proofs" that you actually have the resource you are planning to use, and these proofs are materialized as a web of interlocking asserts, and the web works only when it is correct in whole. With global allocation, you can always materialize fresh resources out of thin air, so nothing forces you to do such web-of-proofs.

To more explicitly set the context here: the fact that this works for TigerBeetle of course doesn't mean that this generalizes, _but_, given that we had a disproportionate amount of bugs in small amount of gpa-using code we have, makes me think that there's something more here than just TB's house style.

Re: Static Allocation with Zig

#70

Post by matklad »

kibwen wrote: post #62
matklad wrote: post #57

Earlier quoted context omitted.

To add more context, TigerStyle is quite a bit more than just static allocation, and it indeed explicitly attributes earlier work: > NASA's Power of Ten — Rules for Developing Safety Critical Code will change the way you code forever. To expand: * https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/TI... * https://spinroot.com/gerard/pdf/P10.pdf

Those guidelines are quite clear that they're written specifically in the context of the C programming language, and may not make sense in other contexts: "For fairly pragmatic reasons, then, our coding rules primarily target C and attempt to optimize our ability to more thoroughly check the reliability of critical applications written in C." A version of this document targeting, say, Ada would look quite different.

They do make a lot of sense in other contexts :-) From the actual rules, only #2 (minimize preprocessor) and #10 (compiler warnings) are C specific. Everything else is more-or-less universally applicable.
Post reply on HN