exDM69

If I understood the algorithm correctly, it is using the standard WFC algorithm to generate blocks that match a constraint.

Then it creates a tiling of those blocks, and substitutes parts of the tiling with new blocks generated using WFC.

So it's a higher level algorithm, using WFC as its building block.

Here's another interesting O(1) memory allocator but with arbitrary sized allocations and low fragmentation. Negative side is relatively high memory overhead (a few dozen bytes per allocation).

This kind of allocator is often used to suballocate GPU memory in game and graphics applications.

I'm using a variant of this algorithm with added support for shrinkable and aligned allocations and flexible bin sizing.

You can also extend this idea to two dimensions to create texture atlases, which is possible in O(1) for power of two sized allocations.

Original: https://github.com/sebbbi/OffsetAllocator Rust port: https://crates.io/crates/offset-allocator

Very delightful article. Based on my experience in "hobby" OS programming, I would add setting up GDB debugging as early as possible. It was a great help in my projects and an improvement over debugging with the QEMU monitor only.

QEMU contains a built-in GDB server, you'll need a GDB client built for the target architecture (riscv in this case) and connecting to the QEMU GDB server over the network.

https://qemu-project.gitlab.io/qemu/system/gdb.html

> Rust game development seems more about releasing half baked crates than actual games

It's because these are mostly passion projects by hobbyists. A lot of the stuff is written by undergrad students with a lot of time on their hands, and once they graduate and move into professional life they no longer have the time and the projects get abandoned.

Creating high quality, reusable components (like game engines) takes a lot of effort. It's unlikely to happen without funding.

And that's only half of the story, to make an actual game (or other product) you'll still need the art content which is expensive.

I'm about 3 years worth of Saturdays and 20kLOC into my current project in this field and I haven't even released anything because I don't need anyone to tell me it's "half baked". While I have some stuff that's starting to be in a shape where it could be usable to others, it would still need a lot of effort to make it friendly for others (e.g. api docs, examples and stuff) to jump in. That again takes effort (there are only so many Saturdays in a year) and it's much less interesting work than doing the research-ey bits and experimental work.

Unfortunately I think this is a chicken and egg problem. No-one with the funds and the staffing to build a game or an engine isn't going to jump in to unproven technology. Not using Unreal or Unity is a huge gamble to take with your business venture.

The distance from Helsinki to Tallinn is just above 80 km and there is only a narrow sliver of international waters in between the territorial waters. It is quite well monitored by surface and underwater surveillance.

In this particular case there is no need for a choke point, it already is one.

The ship suspected for this sabotage was promptly escorted to Finnish territorial waters and is guarded by coast guard vessels and helicopters.

This time the ship in question is under Cook Island / New Zealand flag, and they are more likely to cooperate than the previous instances where vessels under Hong Kong and Chinese flags. Apprehending a vessel on international waters requires the nation whose flag it's under to approve.

In Vim, the "stupid" auto complete will get 80% of the way there and works without setting up a language server and it works for any language.

By default it will give all the identifiers in all open files. Having a few of the relevant files open in the editor will get you pretty far.

I do use LSP in other environments where it is available but I still do a lot of my work with just plain vim because I jump between code bases a lot and setting up LSP for C/C++ needs some extra steps to work.

> (it'd need to also save memory map

Typically the memory map is only required when capturing the backtrace and when outputting the stack frames' addresses relative the the binary file sections are given/stored/printed (with the load time address subtracted). E.g. SysRq+l on Linux. This occurs at runtime so saving the memory map is not necessary in addition to the relative addresses.

Not sure if this is viable on all the platforms that Rust supports.

> but for some reason Rust's standard library wants to resolve human-readable paths at runtime.

Ah, I see that Rust's `std::backtrace::Backtrace` is missing any API to extract address information and it does not print the address infos either. Even with the `backtrace_frames` feature you only get a list of frames but no useful info can be extracted.

Hopefully this gets improved soon.

> External debug info is also more fragile.

I use external debug info all the time because uploading binaries with debug symbols to the (embedded) devices I run the code on is prohibitively expensive. It needs some extra steps in debugging but in general it seems to work reliably at least on the platforms I work with. The debugger client runs on my local computer with the debug symbols on disk and the code runs under a remote debugger on the device.

I'm sure there are flaky platforms that are not as reliable.

> Your binary usually won't get loaded at the same address in memory.

The addresses you typically see in a backtrace error message (with debug syms disabled) are relative to the sections in the binary file, the runtime address it was loaded at has already been taken into account and subtracted. At least that's how you typically see a backtrace address in a typical native app on Linux.

> The bigger problem is how you unwind the stack.

Rust can unwind the stack on panic when built without debug symbols.

Why does adding `backtrace` to thiserror/anyhow require adding debug symbols?

You'll certainly need it if you want to have human readable source code locations, but doesn't it work with addresses only? Can't you split off the debug symbols and then use `addr2line` to resolve source code locations when you get error messages from end users running release builds?

On an embedded system out in the field? Depends on the use.

On your prototype devkit? Absolutely.

I will respectfully disagree with your statement, with the caveat that I mostly dabble in arithmetic with 128b/256b float and int vectors.

Using C or C++ with vector extensions (Gcc/Clang) or Rust (nightly) std::simd is very easy and you get code that is portable to different CPUs and ISAs.

But most importantly they have a zero cost fallback option to CPU-specific intrinsics when you need them. An f32x8 can be passed at zero cost as __mm256 to any core::arch::x86_64::__mm_intrinsic (or xmmintrin.h in C++ land).

You gain portable arithmetic and swizzles and SIMD vector types, but lose nothing. Not having to write everything for x86_64 and aarch64 is a huge win even if doesn't quite cover everything.

Additionally you can use wider vectors than your hardware supports, the compiler is able to split your f64x64 to 128, 256 or 512 bit registers as needed depending on the compile target.

> package management belongs to the os

Os package managers do a fundamentally different task than dependency management tools used in development.

They ship a bunch of applications and the libraries you need to run the applications.

If you need different version of libfoo than e.g. Firefox does, you're out of luck.

Need to support a customer with an older release which needs a different version of libfoo? Not gonna happen.

Unless you're talking about Nix or Guix, your OS package manager is not a substitute for a dependency management tools.

I haven't measured because I broke my pH testing kit.

Thanks for the pointers, I will read further.

I need to monitor my compost to keep it from freezing in the winter. Probably not what OP's system is for, given that they are from Australia.

The biological processes produce enough heat to keep the thermally insulated compost bin from freezing easily down to -15C (~5 F). But this requires that there isn't too much finished compost in the bin that won't produce heat any more, so any turn downwards on the thermometer means I'm probably late in emptying the bin. Which happens every year when it gets cold (below -20C/-5F), but can be remedied by a 40W light bulb for 48 hours to heat up and restart the composting.

Another thing that needs to be monitored is humidity, because too humid and the compost goes anaerobic and starts rotting instead of composting. This I "monitor" by smell but this project has some kind of gas composition sensor which could be useful. I don't have issues with this any more as I have practically unlimited supply of wood chips to keep it dry.

But the wood chips bring another problem which is pH levels that may go too low. Here's where I'd really like to have a monitor so I could estimate if I need to do something to adjust the pH.

I have a similar technique before, embedding the entire font data in the fragment shader source code. Then you can use `snprintf` to directly print into a GPU buffer mapped to the CPU (this is a footgun, I know). Instead of drawing individual characters with a vertex shader, I've just drawn one full screen triangle and use `gl_FragCoord` instead of UV coordinates. Not the most efficient way of doing things but it's a debug feature and it's fast enough to be practical.

Despite what the filename says, this is using the font from the IBM PC ROM, not the NES. You can find the "NES font" and other 8x8 pixel fonts around the web.

https://github.com/rikusalminen/triangles/blob/nesfont/shade...

> Ray tracing is just math, is that math applicable for any non graphics use?

It's not "just math", it's data structures and algorithms for tree traversal, with a focus on memory cache hardware friendliness.

The math part is trivial. It's the memory part that's hard.

Ray tracing hardware and acceleration structures are highly specific to ray tracing and not really usable for other kinds of spatial queries. That said, ray tracing has applications outside of computer graphics. Medical imaging for example.

This statement isn't true at all. There are tons of fixed function hardware units for graphics in GPUs in addition to compute cores: triangle rasterizers, texture units, raytracing units, blitters, copy engines, video codecs, etc. They interact with the shader/compute cores and it's getting more common that the shader core is driving the rasterizer etc than vice versa (mesh shaders and ray tracing for example).

Calling it "all emulated" is very very far from the truth.

You can independently verify this by digging into open source graphics drivers.

> Can this be adapted to work with classic line segments made from quads or is it just for drawing grids in screen space?

It can be applied like a texture in the fragment shader using UV coordinates and their partial derivatives.

You can't really use this technique with line segments because the grid density up close to the camera is higher than far away. You'd need to do a lot of math to figure out where to draw your line segments. If you calculate all the line segment geometry, a fancy shader isn't required any more.

I have an even better darn grid shader that I use in my graphics projects.

The shader in this article wants to emulate the look of a sampled texture so that it blurs to medium gray at distance while avoiding moire patterns. And it does indeed look quite good at what it's aiming for.

I on the other hand wanted an "infinitely zoomable grid paper" look with constant-ish pixel width lines, such that the density of the grid changes. If applied to a "ground" plane, the grid gets sparser near the horizon. When you zoom in, the grid gets denser with a new "decade" of grid fading in with the old grid fading out.

I generally apply this to a "full screen triangle", and do a raycast against the ground plane (e.g. the y = 0 plane) and extract the "uv" coordinates from the raycast result (that would be the x,z coordinate of the ray hit). I've also applied this technique to a skybox, where I take the view ray direction unit vector and convert it to spherical coordinates (latitude, longitude) for the UV.

This shader gives a very clean looking grid at almost any viewing angle and distance. If your world space units are meters, this can be zoomed in from nanometers to gigameters while looking crisp and clean. Unfortunately, floating point issues take over after that point and there are some pixel artifacts when the camera is very close to the ground plane and the viewing angle is extreme. This could be fixed by adding some clamping to the the `log_width` variable, but I haven't bothered with that as I don't work in nanometers in computer graphics projects. There's also some flickering at the horizon line, which I've solved with a trivial fade out factor (not visible in the source code below).

As it is shown below, it'll show a grid with a subdivision factor of 10, like millimeter paper with the primary grid in centimeters and secondary grid in millimeters. The subdivision can be changed by adjusting the `base` and `N` variables. See the comments for explanation.

Here's the thing in all its glory. Apologies that I don't have a screenshot hosted where I could share. Please let me know if you're trying this out in your projects.

    float grid(vec2 uv, float linewidth) {
        vec2 width = linewidth * fwidth(uv);
        vec2 grid = abs(fract(uv - 0.5) - 0.5) / width;
        float line = min(1.0, min(grid.x, grid.y));
        return 1.0 - line;
    }

    float decade_grid(vec2 uv) {
        // grid subdivision factor (logarithm base)
        float base = 10.0;
        // grid density, primary grid is approximately base^N pixels wide
        // with N = 3, primary grid is 100 pixels, secondary grid 10 px
        float N = 3.0; // 3.0 is the densest grid that does not have moire patterns

        // approximate grid cell size using screen space uv partial derivatives
        vec2 width = fwidth(uv);
        //vec2 width = vec2(length(dFdx(uv)), length(dFdy(uv)));
        float w = max(width.x, width.y);
        //float w = length(width.xy);

        // take logarithm of grid cell size to find zoom factor
        float log_width = log2(w) / log2(base); // logarithm change of base

        // round down to find grid zoom factor (power of ten)
        float exponent = -floor(log_width) - N;
        float blend = 1.0 - fract(log_width); // blend between powers of ten

        // primary grid with wider lines
        float grid1 = grid(uv * pow(base, exponent), 1.0 + blend);
        // secondary grid with narrow lines
        float grid2 = grid(uv * pow(base, exponent + 1.0), 1.0);

        // mix primary and secondary grid with linear interpolation
        return mix(grid1, grid2, blend);
    }

Absolutely, look into your standard library, CPU built-ins and intrinsics first.

However, these tricks are not useless even on modern CPUs. There are scalar instructions for a lot of this stuff, but if you are working with SIMD, several of them are not available.

Recently I wrote bit interleaving stuff with Morton codes. Maybe the scalar instruction would be faster in isolation but I already have my data in SSE registers for other arithmetic so in total it was probably faster. I used the code in this article as a basis.

> At least the electrical ones I’ve seen wouldn’t work on a 12” log.

I have cut 12" logs on a small electric chain saw with batteries and it works pretty damn well. Much better than a small gas powered chain saw of similar size because of the ample amounts of torque available.

But of course the small saws have a limited capacity and for hard forestry work you should opt for a tool suitable for the job.

As pointed out by another commenter, there is no ban on large gas powered chain saws (contrary to what TFA suggests), only the small ones which are in the same category with the electric ones.

I have to agree with the author that battery powered chain saws are not for heavy forestry work.

But for a homeowner's odd chain saw jobs they beat gas powered chain saws hands down. Particularly if the use is infrequent, it starts when you press the button and no two stroke maintenance tools, space and knowledge required.

My small saw has scary amounts of torque, to the point where I am terrified of it. I don't think normal chain saw protectors will stop it in case of accident.

Chain saw protector clothing is filled with pockets of fibrous padding and when a chain breaks it, the fibers are supposed to clog the sprocket and stall the engine. Works with two strokes that have little torque at low rpm but electric motors have much more available.

I've cut much larger trunks of hardwood with the tiny saw than you would think possible.

> GPUs are Turing complete computers. > what's missing from existing GPU languages that prevents this kind of flexibility?

GPUs contain many Turing complete computers that are orchestrated by a non-Turing complete fixed function logic block which interprets your command buffers (as opposed to shader code). That component is different in every architecture.

The work graphs are about creating a scheduling system for the fixed function component.

You can't effectively do this in shaders only.

Unreal Engine's "Nanite" system uses something like a work graph in a shader. It is full of pitfalls and gotchas to make it work but you can read about it in the white paper.

The core issue here is that without workgraphs, each compute shader needs to write out its results to DRAM and finish all work it is doing. Then another compute shader is dispatched and it reads back all the results from DRAM.

With work graphs you can make a producer/consumer type of setup where a compute shader's outputs are fed as input to another compute shader without going through DRAM. It also removes the need to know how much output the producer produces ahead of time, no need to preallocate a buffer for the intermediate results.

DRAM bandwidth is typically the bottleneck in modern graphics so this makes sense.

Yes, radix sort can sort integers in linear O(N) time.

Problem with radix sorting strings is that it is O(k*N) where k is length of key, in this case it's the second longest string's length. Additional problems arise if you are dealing with null terminated strings and do not have the length stored.

Radix sort is awesome if k is small, N is huge and/or you are using a GPU. On a CPU, comparison based sorting is faster in most cases.

Guitar Pro tabs have time durations on every note (as described in the article), and can also be displayed in standard musical notation. It also has a whole host of articulation symbols, including the standard musical articulations (mezzoforte etc) as well as a bunch of guitar specific special articulations (e.g. artificial harmonics).

Printed guitar tab books also have durations and articulation symbols.

I agree that old fashioned ASCII art guitar tabs without durations aren't great.

They are very similar, but wgsl is its own language. Vulkan can run SPIR-V shaders written in glsl, hlsl or slang. Other experimental languages exist (like rust-gpu).

Wgpu is a bit behind on GPU features, for example they've added support for shader subgroups (aka warps or waves) in 2024, where as this feature was available in Vulkan 1.1 released in 2018 or Direct3d 12 shader model 6.0 (same timeframe). Wgpu still does not support buffer device address ("GPU pointers") which I consider quite a game changer.

Many popular tools, e.g. RenderDoc, don't have wgpu support.

If you are not targeting the web platform, wgpu isn't really bringing anything to the table.

I've done some compute shaders with Vulkan (and a lot of graphics shaders). It's quite nice and simple, after you have gone through the initial hurdle of setting it up (or used a helper library to do it for you). For compute shaders in particular you should enable buffer device addresses, shader subgroups and timeline semaphores (need to be explicitly enabled at init).

The downside of compute shaders, regardless of graphics API (gl, dx, vk), is that they have an unspecified time limit after which the OS will kill your process. There are ways to disable this in your OS/GPU configuration but there isn't a portable way of doing this programmatically from your code.

Another issue is that if you use the same GPU for compute (or heavy graphics tasks) as your display output, your desktop responsiveness may go down. I had some issue where my desktop got really sluggish when I was drawing some graphics that took 350ms per frame (laptop integrated graphics).

Yes, but audio glitches are much worse for the experience.

Games do a very impressive amount of work for graphics but there's a huge difference: a dropped/late graphics frame every now and then is not a big deal.

An audio glitch is very annoying by comparison, especially if the application is a live musical instrument or something like that. Even the choppy rocket motor sounds of Kerbal Space Program (caused by garbage collector pauses) are infuriating.

It's kind of the difference between soft and hard real time systems. Although most audio applications don't strictly qualify as hard real time (missing a deadline is as bad as a total failure) but failing a deadline is much worse than in graphics.