Understanding comptime

[dan3]

I don’t have a specific problem to solve or issue other than trying to understand how comptime works.

In StaticStringMapWithEql.initComptime() function, my understanding is that the sorting and bucketing for the map is done at compile time. The bits that make up the StringMap object are, for lack of a better term, copied into the runtime.

When I look at the implementation of initComptime(), the comptime block was storing stack allocated array pointers in the returned object. Here is a snippet:

    var len_indexes: [self.max_len + 1]u32 = undefined;
    self.initLenIndexes(&len_indexes);
    const final_len_indexes = len_indexes;
    self.len_indexes = &final_len_indexes;
    self.len_indexes_len = @intCast(len_indexes.len);
    return self;

In non-comptime code, final_len_indexes would be stack allocated and putting that pointer in the returned self object would be bad. Yet, the StaticStringMaps initialized with initComptime seem to work fine in my code (in comptime blocks and non-comptime blocks).

Does a comptime block have its own concept of a stack? What is “&final_len_indexes” pointing to? When the self object is returned, it contains a pointer to “final_len_indexes” via “self.len_indexes”. I don’t understand how self.len_indexes ultimately contains a valid pointer.

[uben]

In my understanding, comptime is very different from runtime, and every value is reference counted and dynamically typed, it is almost like Python.

[n0s4]

@dan3

Does a comptime block have its own concept of a stack?

As far as I understand, in comptime, all values are allocated in an arena (on a per-block/per-decl basis) and not on a stack so there’s no issues around dangling pointers.

I think I got this from @mlugg, who I believe would be the ideal person to answer this

@dan3

What is “&final_len_indexes” pointing to?

The comptime generated array, which is stored in your programs static data segment. self.len_indexes is a runtime value of type [*]const u32, so it stores a pointer to the static memory but cannot write to it.

[n0s4]

@uben

every value is reference counted and dynamically typed

I believe it’s arena allocation, not reference counting, and I’m not sure where you’re getting the dynamic typing idea from, I’m pretty sure all normal static type rules apply.

I do find it useful to think of comptime like a ‘zig interpreter’ though.

[uben]

I don’t have information about how it is implemented. It is rather a deduction. Because what is possible in comptime, to be statically typed, would need a dependent type theory implementation (Dependent type - Wikipedia), and I know for sure Zig doesn’t have it. Now knowing that some values have to by dynamically typed, there are no reason to think some are and other don’t. Sure, type indication will force type, but its different from static typing.

Also, for reference counting, it is also an intuition, as from my experience, any value can escape its defining scope, there won’t be an undefined behavior. I just don’t see any other mechanism than reference counting that can do so (and garbage collection). Even an arena allocator has a scope.

Am I wrong? This got my curiosity.

[n0s4]

Ah, I see what you mean. Yeah, I imagine the compiler needs some sort of dynamic value type, but as far as the user is concerned there’s no difference.

[n0s4]

@uben

Also, for reference counting, it is also an intuition, as from my experience, any value can escape its defining scope, there won’t be an undefined behavior. I just don’t see any other mechanism than reference counting that can do so (and garbage collection). Even an arena allocator has a scope.

I found the post I read that from, the whole thing is worth reading: Comptime Garbage Collection - #3 by mlugg.

Particularly

@mlugg

Sema is no exception – each instance of Sema stores an arena: std.mem.Allocator field. This arena is used for any temporary data needed during semantic analysis – such allocations are thrown into the arena, which is then chucked out when this individual semantic analysis completes. A single analysis is either analyzing the value of a declaration (a global const or var), or is analyzing a runtime function body (type checking it and generating code). Any such analysis may call arbitrary comptime code: for instance, in your snippet, analysis of the runtime body of main evaluates getEvens(16) at comptime.

Ah, but of course I misread it. This is talking about temporary state the compiler has when processing these comptime values. The values themselves are stored in an InternPool, which in theory would be garbage collected:

@mlugg

Regarding interned values (those stored in the InternPool), the idea is that the pool can undergo periodic garbage collection using a simple conventional mark+sweep approach. However, this is currently vaporware, since the InternPool is a fairly new creation (more on this later). Thus, interned values are currently never cleaned up.

[dan3]

It makes sense that the data would be in the ro section at runtime. I suppose it can’t really live anywhere else.

I am still a little unsure how final_len_indexes gets into the ro section. Is it because it is declared const or the & operator is used in the assignment?

I found this post, which was sorta the same question as mine, Comptime Garbage Collection - #3 by mlugg which helped understand this stuff better.

I also found an article for using comptime for string interning: Cool Zig Patterns - Comptime String Interning - Zig NEWS (apparently, there is some memoization stuff that happens too!)

But, I am still not confident that I know enough about comptime to do some of the more advanced things.

[vulpesx]

@dan3

I am still a little unsure how final_len_indexes gets into the ro section. Is it because it is declared const or the & operator is used in the assignment?

It’s because it’s a comptime value that’s being used by runtime code, it has to exist in the final file in some form.