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

41–50 of 112 posts

Re: Static Allocation with Zig

#41

Post by kevin_thibedeau »

mikepurvis wrote: post #22
d3ckard wrote: post #10

Personally I believe static allocation has pretty huge consequences for theoretical computer science. It’s the only kind of program that can be actually reasoned about. Also, not exactly Turing complete in classic sense. Makes my little finitist heart get warm and fuzzy.

I'm not an academic, but all those ByteArray linked lists have me feeling like this is less "static allocation" and more "I re-implemented a site-specific allocator and all that that implies". Also it's giving me flashbacks to LwIP, which was a nightmare to debug when it would exhaust its preallocated buffer structures.

This is still a more dependable approach with resource constraints. Fragmentation is eliminated and you can monitor pools for usage in a worst case scenario. The only other risk here versus true static allocation is a memory leak which can be guarded against with suitable modern language design.

LwIPs buffers get passed around across interrupt handler boundaries in and out of various queues. That's that makes it hard to reason about. The allocation strategy is still sound when you can't risk using a heap.

Re: Static Allocation with Zig

#42

Post by e12e »

chongli wrote: post #20
d3ckard wrote: post #19

Earlier quoted context omitted.

Nice correction :) It’s actually quite tricky though. The allocation still happens and it’s not limited to, so you could plausibly argue both ways.

I’m confused. How is a program that uses static allocation not Turing complete?

It's not, if it can do Io to network/disk..?

Re: Static Allocation with Zig

#43

Post by IshKebab »

d3ckard wrote: post #10

Personally I believe static allocation has pretty huge consequences for theoretical computer science. It’s the only kind of program that can be actually reasoned about. Also, not exactly Turing complete in classic sense. Makes my little finitist heart get warm and fuzzy.

> It’s the only kind of program that can be actually reasoned about.

What do you mean? There are loads of formal reasoning tools that use dynamic allocation, e.g. Lean.

Re: Static Allocation with Zig

#44

Post by chris- »

dnautics wrote: post #32
justincormack wrote: post #25

Earlier quoted context omitted.

You can work around overcommit by writing a byte to every allocated page at allocation time, so that it has to be actually allocated.

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.

Re: Static Allocation with Zig

#45

Post by d3ckard »

kibwen wrote: post #31
d3ckard wrote: post #10

Personally I believe static allocation has pretty huge consequences for theoretical computer science. It’s the only kind of program that can be actually reasoned about. Also, not exactly Turing complete in classic sense. Makes my little finitist heart get warm and fuzzy.

> 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.

Re: Static Allocation with Zig

#46

Post by AlotOfReading »

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…

It's best to think of it as an entire spectrum from "statically allocate everything with compile time parameters" to "directly call the system allocator for every new bit of memory". It's just a helpful way to separate the concerns of memory allocation from memory usage.

What this article is talking about isn't all the way at the other end (compile time allocation), but has the additional freedom that you can decide allocation size based on runtime parameters. That frees the rest of the application from needing to worry about managing memory allocations.

We can imagine taking another step and only allocating at the start of a connection/request, so the rest of the server code doesn't need to deal with managing memory everywhere. This is more popularly known as region allocation. If you've ever worked with Apache or Nginx, this is what they do ("pools").

So on and so forth down into the leaf functions of your application. Your allocator is already doing this internally to help you out, but it doesn't have any knowledge of what your code looks like to optimize its patterns. Your application's performance (and maintainability) will usually benefit from doing it yourself, as much as you reasonably can.

Re: Static Allocation with Zig

#47

Post by [deleted] »

chongli wrote: post #20
d3ckard wrote: post #19

Earlier quoted context omitted.

Nice correction :) It’s actually quite tricky though. The allocation still happens and it’s not limited to, so you could plausibly argue both ways.

I’m confused. How is a program that uses static allocation not Turing complete?

[deleted]

Re: Static Allocation with Zig

#48

Post by astrobe_ »

mitchellh wrote: post #17
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…

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…

Because garbage-collected languages are easier to teach and to use. So the low-level, low-resource or high-performance stuff is left to a handful of specialists - or "insects" according to Heinlein. Speaking of old things, this reminds me of one of Asimov's short stories, where someone who rediscovers mental calculus is believed to be a genius.

Re: Static Allocation with Zig

#49

Post by [deleted] »

testdelacc1 wrote: post #7
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…

It is known, but not widely used outside of embedded programming. The fact that they’re using it while writing a database when they didn’t need to makes people sit up and notice. So why did they make this conscious choice? It’s tempting to cut people down to size, but I don’t think it’s warranted here. I think TigerBeetle have created something remarkable and their approach to programming is how they’ve created it.

[deleted]

Re: Static Allocation with Zig

#50

Post by levkk »

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…

That makes sense. For example, your redis instance will have fixed RAM, so might as well pre-allocate it at boot and avoid fragmentation.

Memcached works similarly (slabs of fixed size), except they are not pre-allocated.

If you're sharing hardware with multiple services, e.g. web, database, cache, the kind of performance this is targeting isn't a priority.

Post reply on HN