Rust memory optimization #

One of my goals this year is to learn new things that take more than a few weeks to learn. I've been learning Rust. One of the claims I saw is that Rust's borrow mechanics allow it to optimize better than C++ does. I wanted to see this in action so I ran some simple examples through godbolt. Here's some C++ code that reads from array A and writes to array B:

int test(const int* A, int* B, int i) {
    int x = A[i];
    B[i] = x+1;
    int y = A[i];
    return x+y;
}

This C++ code compiles to assembly, with -O2:

movsx   rdx, edx
lea     rcx, [rdi+rdx*4]
mov     eax, DWORD PTR [rcx]
lea     edi, [rax+1]
mov     DWORD PTR [rsi+rdx*4], edi
add     eax, DWORD PTR [rcx]
ret

Note that it is loading DWORD PTR [rcx] twice and loading DWORD PTR [rsi+…] once. That means it's accessing A[i]'s memory twice and B[i] once. It knows that A hasn't changed and it knows i hasn't changed but it doesn't know that A[i] hasn't changed. It's possible that A and B overlap. That means it has to load A[i] twice, even though it's marked const.

Here's the Rust version:

pub fn test(A: &[i32], B: &mut [i32], i: usize) -> i32 {
    let x = A[i];
    B[i] = x+1;
    let y = A[i];
    return x+y;
}

and the output (some parts omitted):

push    rax
mov     eax, DWORD PTR [rdi + 4*r8]lea     ecx, [rax + 1]
mov     DWORD PTR [rdx + 4*r8], ecx
add     eax, eax
pop     rcx
ret

This code has only two DWORD PTR accesses. It knows that A is a shared reference (so there are no other writers), and B is a mutable reference (so there are no other readers). That means it can conclude that A and B can't overlap. Once it's read A[i] from memory it doesn't have to read it again. Cool!

C (but not C++) has the restrict keyword for this. You can tell the C compiler "trust me, these don't overlap", but C doesn't check. Rust checks this at compile time.

So far I'm enjoying learning Rust. It has many of the things I wanted in a language since the mid-1990s. I don't know if I'll actually use it for a real project, but that's not my goal right now. My goal is to learn some new things that challenge my brain, and Rust is doing that for me.

Labels:

Cross-compiling Rust to Linux on Mac #

In my last blog post I said I wanted to spend some time learning new things. The first of those is Rust. I had previously tried learning it, but got distracted before I got very far.

Since one of the things I'd use Rust for is web pages, I decided to learn how to compile to WebAssembly, how to interface with Javascript, and how to use WebSockets. At home, I use a Mac to work on my web projects, so for Rust I am compiling a native server and a wasm client. But I also wanted to try running this on redblobgames.com, which is a Linux server. How should I compile to Linux? My first thought was to use my Linux machine at home. I can install the Rust compiler there and compile the server on that machine. Alternatively, I could use a virtual machine running Linux. Both of these options seemed slightly annoying.

Labels: ,

What I did in 2019 #

It's time for my annual self review. You can see previous ones from 2015, 2016, 2017, 2018. I didn't have a lot of goals for this year:

  1. Write to my blog instead of only to Twitter or other closed platforms.
  2. Improve my explanations and write new ones.

The first I can measure by looking at whether I blogged about my projects. I did: 24 blog posts this year. I'm pretty happy with that. The second is harder to evaluate, but I would say I didn't spend nearly as much time on explanations as I had hoped to. I wrote these new explanations, but they were small:

And I worked on these two, but didn't get them to a point I was happy with:

I spent some time improving existing explanations:

Instead of explanations, this year I was more inspired to work on art, learning, and other fun projects:

I also have 15 other projects that weren't for the general public (for clients, or responses to emails, etc.). I generated new logos for my social media presence using a new logo generator I wrote. And I updated my home page with links to lots of projects I hadn't previously linked. I track these projects on Trello.

What else? I'm hanging out on AIMA chat (students who want to contribute to the AIMA textbook open source project), Roguelike Discord, ProcJam Discord, a few Slacks, Twitter, and a few subreddits. I decided to go to non-GDC conferences this year, and went to BangBangCon, FDG, and Roguelike Celebration. I'm pretty happy with how all of this went this year.

For several years I've hoped that the coordinate systems page would become the next big successful project after the Hexagon page and the A* page. I've attempted to write it several times but just haven't been happy with it. I'm now starting to think that maybe it's not going to be the next big success for me. I've also been trying to come up with a good explanation of differential heuristics but can't seem to make much progress. Maybe I won't have any more big successes with tutorials, and should stop looking for that.

What are my goals for 2020? Unfortunately, I don't have any strong goals. After working on big projects in 2018, I ended up working on small projects in 2019. I would like to work on something bigger, but I think my focus will be on learning new things rather than explaining things I already know. I'd like to work on projects that last a month or two rather than a week or two, to really dig into them and learn a topic deeper than I can do in a week. Other than that, I feel kind of aimless right now. I'm ok with that. I'm in a wander-and-explore phase of my life.

Experimenting with outlines #

I posted recently about how I often do one-week projects to learn and experiment. I don't have a strict one-week time limit. Sometimes I'll extend a project or come back to it after I've learned something new.

Ten weeks ago I had a one-week project in which I wanted to draw outlines on an isometric view of a dungeon game. I didn't want to outline each block, which could be implemented easily by editing the sprites. Instead, I wanted to outline the larger units. Here's a comparison:

Outlines around every sprite vs around walls

Labels:

Fun art projects #

I've not been in the mood to write articles lately, so instead I've been working on some fun projects instead. Watabou posted about Dyson Hatching, which got me thinking it might be interesting to constrain the hatch lines to Voronoi cells. I implemented that and then got carried away with colors, line spacing, line width, and other fun things. The demo is here. You can drag an image onto the diagram to use the colors from your image.

Hatch lines applied to an image

Types of projects #

When I started writing articles on my site, sometimes I had great results, like writing the hexagonal grid guide in 6 weeks, and sometimes I had terrible results, like writing article about curved roads in 5 months. I eventually realized that the difference was that with hexagons, I understood the topic well, but with curved paths, I spent most of the time trying to understand the topic. To make matters worse, because I had a high standard for my articles, I spent too much time trying to polish the article about curved paths, even before I understood it well.

Back in 2013 I decided to create a separate directory /x/YYWW-name/ where I'd put the lower effort and experimental pages, numbered by year and week. For example, 1942-isometric means year 2019, week 42. Over the last few years I've realized I do two different types of projects:

Curved region rendering #

Around a month ago I had an idea in my head: a voronoi grid modified to have rounded cells that change in size. I made an attempt here for single cells changing size. The next step was to merge cells together, as I had done on this project. I decided that the way to demo this would be to simulate some kind of belief/cultural systems that spread over time across a map. I tried this here.

Screenshot of influence map experiment
Simulation

Labels:

Procedurally generated annotations #

Imagine exploring this dungeon:

Dungeon map
Procedurally generated dungeon map

Labels:

Chaikin Curves #

Sometimes I want to draw Voronoi or similar polygons in a rounded form:

Rounded polygons. Lots of them.

I use a process called Chaikin's Algorithm for this.

Labels:

Verb-noun vs noun-verb #

I went to the Roguelike Celebration over the weekend and enjoyed Thomas Biskup's talk about Ultimate ADOM. Among the many interface improvements they're making based on user testing is they're simplifying the controls from the traditional roguelike controls to W A S D + E F. I don't know how roguelike game players will respond to that but I'm a fan! This reminded me of two things from my past, so I thought I'd say a little about those.

Labels: