Stream: beginners

Topic: ✔ Preallocate a generic List

Mo (Dec 16 2024 at 02:40):

Say I want to preallocate a generic List a with a function like this:

prealloc : U64 -> List a
prealloc = \n -> List.repeat * n

What is the correct syntax to refer to the type variable a within the function, in place of the *? And to zero-initialise the type?

I guess an alternative would be to supply a function, like this:

prealloc2 : U64, ({} -> a) -> List a
prealloc2 = \n, f -> List.repeat (f {}) n

From a performance perspective, would this compile to the same code as (effectively) List.repeat 0 n for a simple type? What if a is a tagged union type?

(Separate question, is there a good way to see Roc compiled code a la Godbolt?)

Mo (Dec 16 2024 at 02:42):

I mean, I suppose a better signature would be:

prealloc3 : U64, a -> List a
prealloc3 = \n, x -> List.repeat x n

Mo (Dec 16 2024 at 02:43):

But I'm curious if there's zero-initialisation available somehow

Luke Boswell (Dec 16 2024 at 02:49):

is there a good way to see Roc compiled code a la Godbolt?

I'm not sure... but I often generate the LLVM IR using

$ roc build --no-link --emit-llvm-ir app.roc

Brendan Hansknecht (Dec 16 2024 at 03:04):

What is the goal? Do yu need to initialize the value at all?

Brendan Hansknecht (Dec 16 2024 at 03:06):

Anyway, you can either...

use an item passed in:

prealloc : U64, a -> List a
prealloc = \n, x -> List.repeat x n

not preallocate with an item and just reserve the memory

prealloc : U64 -> List a
prealloc = \n -> List.withCapacity n

Use an ability (only works for opaque types that are created with the ability and probably not what you want).

Mo (Dec 16 2024 at 03:07):

No, uninitialised is fine. My goal is to preallocate a buffer like a monotonic arena to avoid repeated allocations of lists of objects of the same type, a tagged union.

Mo (Dec 16 2024 at 03:08):

The thing about withCapacity is I want to use List.set in my algorithm, rather than append. Keeping track of the valid indices myself, etc. So I ended up with List.repeat

Brendan Hansknecht (Dec 16 2024 at 03:08):

Yeah, that is the only way here

Mo (Dec 16 2024 at 03:11):

All good. I was confused a bit about type variables, thinking I needed some way to instantiate (zero-initialise) a value given a type. This would avoid needing to pass in a value at each call site. But it's been a while since I've done functional programming, so I'm refreshing my brain cells a bit.

Brendan Hansknecht (Dec 16 2024 at 03:32):

One update, making this generic is actually easier than I initially thought. You could use the decode ability and make a custom zero value decoder. Not saying it is a good idea, but it would automatically work with all structural types.

Mo (Dec 16 2024 at 03:33):

That's interesting - something too look at a bit further down the road

Richard Feldman (Dec 16 2024 at 03:52):

yeah we could consider someday having platforms implement something like Rust's alloc_zeroed and then expose some way to do that for things like lists of numbers, or optimize to it when we detect List.repeat 0 on an empty list, but there aren't any plans to do anything like that at the moment :big_smile:

Mo (Dec 16 2024 at 06:54):

Interesting that List.reserve can never fail. That's my go-to if I need to allocate and absolutely positively must not fail. :smiley:

Brendan Hansknecht (Dec 16 2024 at 07:23):

If it fails, it does so in the catastrophic entire application out of memory sort of way.

Brendan Hansknecht (Dec 16 2024 at 07:23):

But most people don't need to worry about that much

Notification Bot (Dec 19 2024 at 02:16):

Mo has marked this topic as resolved.

Last updated: Jul 06 2025 at 12:14 UTC