Comment by evil-olive | Hacker News Reader

Comment by evil-olive | Hacker News Reader

Parent Full thread

I wrote a Sudoku solver (my go-to "learn a new language" project) in Zig and the compile-time features were extremely useful.

entirely at compile-time, I was able to generate lookup tables for "given this cell index, give me the indexes of the cells in its row, column, and box". and I simply looped over that for each board size I wanted to support, from the standard 9x9 all the way up to 64x64.

another useful feature was support for arbitrary-sized ints [0] and packed structs [1]. for a 9x9 board, a cell can be represented with a 9-bit bitfield for possible values; a uint4 for the actual value; and a single bit indicating whether the value is known. Zig will happily pack that into a struct that occupies only 16 bits, and handle all the bit shifting & masking for you when you access the struct fields.

this meant I was able to represent the state of a 9x9 board in just 162 bytes - a flat array of those packed structs. and the exact same code could operate on the ~28kb of state needed for 64x64.

0: https://ziglang.org/documentation/0.9.1/#Primitive-Types

1: https://ziglang.org/documentation/0.9.1/#packed-struct

I am not good enough of a programmer to understand all the meta/compile time programming stuff.

So thank you for this actual concrete example of it being used. But why is that useful? Why regenerate a database every time you compile? Now that you have compiled the program once, can you not just delete that code and reduce your compile time to a fraction of what it was?

You rely on a compiler to produce an executable, right? Well there are many "phases" that the code goes through before becoming machine code. "Compile time metaprogramming" is having control over one of those phases available from the language itself. Exactly how it is implemented is, well, implementation and language specific. But the fact that you can do it is quite useful. You can not only write programs, you can also write programs that transform or generate programs. The full extent of what you're allowed to do is implementation-dependent.

In Lisps, for example, that phase is called the macro-expansion phase (of which there can be layers of) and generally acts as a source-to-source transformation from s-exp to s-exp (possibly with side-effects). Here's an example in a Gambit Scheme REPL:

    > when
    *** ERROR IN (stdin)@8.1 -- Macro name can't be used as a variable: when
    > (when #t #f)          
    #f
    > (pp (lambda () (when #t #f))) 
    (lambda () (if #t #f))

So you can see the 'when' macro expands to an 'if', and that has to happen _before_ evaluation. So the REPL is in fact a REEPL (Read Expand Eval Print Loop).

Very useful.

It's much more convenient than running an external tool to generate LUTs, which is how you'd do it in C(++). You shouldn't regenerate the database every time you compile, that's what incremental compilation is for. But it is very convenient to integrate code-generation into the build system. What happens when you find a bug in the code/LUTs and you've deleted what generated it?

It's useful due to convenient notation. Otherwise, you'd need to write a separate program that generates the code and call it using a separate Makefile target. (And in that case, you might check in the generated code; this is commonly done for Go packages, so that downstream dependencies don't need to run the code generator tools.)

Adding a compile-time parameter to a function is considerably more convenient than writing a code generator. Zig's compile-time performance might be a problem someday, but there is likely not enough Zig code yet for this to matter. Perhaps they'll add caching if it ever turns out to be an issue.

I think it's supposed to be cached in the same manner other things are cached, but the caching does not work great for us so far (and this may be because we are stuck on stage1 due to heavy use of async).

I have had comptime lookup table generation and similar stuff crash the compiler or take a long time to run. I fell back to external code generators in these cases.

think of loop unrolling, but able to be done by the developer instead of exclusively by the compiler.

A more natural form of duffs device. https://en.wikipedia.org/wiki/Duff%27s_device

That's what code generator are for.

The Go community has a rule of committing both the code generator (for later regeneration and maintenance) and the generated code (to avoid rebuilding it every time).

Hah, I had the same learner project for Zig. I chose a different board memory layout for some increased throughput on my hardware, but generating relevant lookup masks at comptime was super beneficial with that approach too.

On the topic of comptime lookup tables, transcendental discretizations are popular in graphics programming (rescale sin/cos to fit appropriately into some integer type, make an array of them to turn transcendental approximations into array lookups). Those are easy to make flawless and fast in Zig.

Another thing that enables without too much song and dance is compile-time duck typing. You can write a function that easily handles a call like randint([][4]@Vector(12, u8), .{Min(0), Max(13), my_allocator, Shape(.{12345})}) which would allocate that type with an appropriate size and fill it with random integers within the prescribed bounds. It's perhaps a bit more verbose than a truly dynamic language, but comptime type introspection enables that sort of powerful control flow without especially burdensome implementations or any runtime performance cost (ignoring cache effects and whatnot), and the whole thing is statically guaranteed to work (within the bounds of what Zig actually promises).

> the exact same code could operate on the ~28kb of state needed for 64x64.

64x64 seems to need 64 bits for values, ie 8 bytes before we consider the known case, but there are 4096 cells. So that's surely 32kB of state immediately ?

It seems to me that if we don't care to distinguish whether we "know" a value for which there is only one possibility, we can save encoding this, so the 9x9 board only needs 9 bits per cell, the 64x64 board only needs 64-bits.

In this case we can answer "known?" as is_power_of_two() and we can find the known value using e.g. trailing_zeros() which is cute.

I might be wrong but I think you do need to know which values were predetermined so the algorithm won't touch those cells while backtracking.

Just out of curiosity, in your opinion what's the benefit of using a packed struct and all the generated bit fiddling compared to just a regular struct? Just better memory consumption?

regular structs in Zig have an implementation-defined layout in memory - the compiler is allowed to re-order fields, add padding, etc.

if you want control over the memory layout you need either a packed struct or an extern struct [0].

0: https://ziglang.org/documentation/0.9.1/#extern-struct

With respect, I’m not sure that answered the question. Surely in a sudoku game the default layout of structs would be absolutely fine, no?

ahh, I might have misunderstood the question - I wasn't sure if they were asking about Zig in general or my solver in particular.

yes, normal structs would have worked fine - like I said, I was learning Zig in the process, so I was going out of my way to experiment with its unique features.

Yes, I meant in your sudoku solver, sorry, I should've been more clear.

That's pretty cool! What other learn-a-new-language projects do you (or others) have? I like to write a very basic HTTP 1.0 server when trying out a new language.

From reading the documentation, these seem to be analogous to C bit fields with a different syntax. D has bit fields, too, using the C syntax.

Reply on news.ycombinator.com