Could you live with fixed size arrays only

If the trade off for a memory manager that works efficiently at high and low scale (think embedded) devices was that each array in your language must be of a size that is fixed at compile time, and cannot exceed some very strict maximum sizes, would that be a price worth paying.

If it was a fully functional language, there’s a good chance that all collection types are persistent, meaning that they are very unlikely to use large arrays ever anyway. But even persistent collections implemented in a language like Java use dynamic arrays, arrays that have a size chosen at runtime. Using a set of pre-defined fixed size arrays, say of size 4, 8, 12, 16, 24 etc up to 396 (yes an arbitrary figure, but it is meaningful) would be a workable and quite efficient alternative.

If you’re wondering what an array is, sorry, my posts are technical. If you’re wondering what a persistent collection is then your instinct might be misleading you into thinking that it has something to do with databases. Sorry, that is far from the truth. If you cannot mutate collections the methods for growing a collection are very different, as you can’t simple assign a new element at the end of an array. Instead functional languages (and non-functional sometimes, but that’s another tale) encode each modification as a tree of changes, and then each access enters that tree at a specific node to see what it looks like at that version. So, replace the word ‘persistent’ with ‘versioned’ and your instinct about ‘versioned collections’ should be better.

The key here is that persistent collections rarely if ever need to allocate a large array.

So what’s the problem, why do we want to impose such a strict limit on things. We could allow runtime sized arrays, and we could allow large arrays. If we allow large arrays, code that runs nicely on a system with lots of memory will struggle on a smaller system even if it could fit within available memory, mostly due to fragmentation. Working on smaller systems is a design goal of YAFL. Ok, so we limit maximum array size but allow them to be sized at runtime. Then we have a secondary problem of knowing when you will hit the limit. It’ll complicate code more than the effects of having fixed size arrays with nice compile time errors and likely introduce more errors.

YAFL is an experimental language, and it is a vanity project, so as always I will do as I please. I’m part way down the path if implementing array support, and will see what strings and collections look like when implemented on top of this. I’ll report back with my findings in a few weeks.

PS. It’s not just about array size. It’s about having a maximum size for any heap allocation, to reduce the possibility of fragmentation. On embedded systems this is a big risk without dipping into the murky world of compacting memory management, and that is definitely not simple.

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s