7 ms·

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 a

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 https://ziglang.org/documentation/0.9.1/#Primitive-Types 1: https://ziglang.org/documentation/0.9.1/#packed-struct https://ziglang.org/documentation/0.9.1/#packed-struct

lhorie 4y ago
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?
- evil-olive 4y ago
  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 https://ziglang.org/documentation/0.9.1/#extern-struct
  - tomcam 4y ago
    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?
    - evil-olive 4y ago
      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.
      - lhorie 4y ago
        Yes, I meant in your sudoku solver, sorry, I should've been more clear.
wisnoskij 4y ago
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?
- skybrian 4y ago
  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.
  - anonymoushn 4y ago
    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.
- belmarca 4y ago
  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.
tialaramex 4y ago
> 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.
- alpaca128 4y ago
  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.
WalterBright 4y ago
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.
deck4rd 4y ago
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.
hansvm 4y ago
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).

lhorie 4y ago

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?

evil-olive 4y ago
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 https://ziglang.org/documentation/0.9.1/#extern-struct
- tomcam 4y ago
  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?
  - evil-olive 4y ago
    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.
    - lhorie 4y ago
      Yes, I meant in your sudoku solver, sorry, I should've been more clear.

wisnoskij 4y ago

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?

skybrian 4y ago
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.
- anonymoushn 4y ago
  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.
belmarca 4y ago
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.

tialaramex 4y ago

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

alpaca128 4y ago
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.

WalterBright 4y ago

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.

deck4rd 4y ago

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.

hansvm 4y ago

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