mikejsavage.co.uk / blog

20 Aug 2017 / Ruoka Helsingissä

(heh that needed <meta charset="utf-8"> to render properly locally)

Some quick restaurant reviews for Helsinki, in no particular order:

16 Aug 2017 / SIGGRAPH 2017

I don't understand how anyone can say the food is so much better in America. I've been to NY and SF which are both supposed to be amazing for food, and just got back from LA.

Their reasoning is usually along the lines of "oh, if we Uber/subway for half an hour we can find a single restaurant that serves great food". Ok, but then if you try to pick somewhere at random it's very close to 100% chance that it's just awful. If you try to be smart, and only pick from places that have four or more stars online it's still very close to 100% chance that it's just awful.

It's fine if I'm planning a meal out somewhere and we can ask people what is actually good, but if I'm out and hungry and want to find somewhere quickly it's very annoying.

Driving vehicles with unmuffled exhausts should be punishable with huge fines. Let's look at an extreme case: driving an unmuffled car through the middle of LA at night. Everyone within a block or two's radius will get woken up, and if you drive a few miles that's easily several thousand people. Now let's say that costs them $5 in lost productivity the next day. That's easily five digits of damage just because they wanted to be a shithead and do something which doesn't actually bring them any benefit.

The same logic goes for police sirens. If the guy you're chasing did less than $10k of damage, write the victim a cheque and be done with it, it's a net positive.

Don't share hotel rooms at conferences. I had plans to go see friends in SF after Siggraph, so I was very deliberately avoiding meeting people and shaking hands and going to bed on time so I could be healthy and fresh for fun times with my best friends. It very nearly backfired on me because one of the guys in my room got sick on the first day. I was lucky enough to stay good until I was waiting in SFO to go home. (but then the vacation days I booked to recover got wasted because I was sick and wouldn't have gone to work anyway)

America is big enough that NY -> LA takes almost as long as Helsinki -> NY. Fuck that! Helsinki -> SF is direct and I should hang out there both sides next time.

BTW the advances talks about cloud rendering in HZD and ocean rendering were awesome, as was the open problems one about using deep learning to learn TAA. The latter sounds like "oh god please no god", but the presenter was really very good at explaining everything and his videos were cool. Unfortunately I can't find any videos of the talks and only having slides is not so great.

Addendum: The ocean rendering talk finally made clipmaps click for me. You upload a constant mesh with more triangles in the middle at init, then when rendering you snap it to integer coordinates and sample your heightmap texture in the vertex shader. Very simple! For performance I assume you can sample high mip levels at high lod levels to preserve locality when sampling. And if that's true you probably want to page out lower mip levels when you aren't using them to save memory.

14 Aug 2017 / Rust performance: finishing the job

Today I saw a story about profiling and optimising some Rust code. It's a nice little into to perf, but the author stops early and leaves quite a lot on the table. The code he ends up with is:

pub fn get(&self, bwt: &BWTSlice, r: usize, a: u8) -> usize {
        let i = r / self.k;

        let mut count = 0;

        // count all the matching bytes b/t the closest checkpoint and our desired lookup
        for idx in (i * self.k) + 1 .. r + 1 {
                if bwt[idx] == a {
                        count += 1;
                }
        }

        // return the sampled checkpoint for this character + the manual count we just did
        self.occ[i][a as usize] + count
}

Let's factor out the hot loop to make it dead clear what's going on:

// BWTSlice is just [u8]
pub fn count(bwt: &[u8], a: u8) -> usize {
        let mut c = 0;
        for x in bwt {
                if x == a {
                        c += 1;
                }
        }
        c
}

pub fn get(&self, bwt: &BWTSlice, r: usize, a: u8) -> usize {
        let i = r / self.k;
        self.occ[i][a as usize] + count(bwt[(i * self.k) + 1 .. r + 1])
}

It's just counting the number of times a occurs in the array bwt. This code is totally reasonable and if it didn't show up in the profiler you could just leave it at that, but as we'll see it's not optimal.

BTW I want to be clear that I have no idea what context this code is used in or whether there are higher level code changes that would make a bigger difference, I just want to focus on optimising the snippet from the original post.

SIMD

x86 has had instructions to perform the same basic operation on more than one piece of data for quite a while now. For example there are instructions that operate on four floats at a time, instructions that operator on a pair of doubles, instructions that operate on 16 8bit ints, etc. Generally, these are called Single Instruction Multiple Data instructions, and on x86 they fall under the MMX/SSE/AVX instruction sets. Since the loop we want to optimise is doing the same operation to every element in the array independently of one another, it seems like a good candidate for vectorisation. (which is what we call rewriting normal code to use SIMD instructions)

Rewrite It In C++

I would have liked to have optimised the Rust code, and it is totally possible, but the benchmarking code for rust-bio does not compile with stable Rust, nor does the Rust SIMD library. There's not much I'd rather do less than spend ages dicking about downloading and installing other people's software to try and fix something that should really not be broken to begin with, so let's begin by rewriting the loop in C++. This is unfortunate because my timings aren't comparable to the numbers in the original blog post, and I'm not able to get numbers for the version Rust.

size_t count_slow( u8 * haystack, size_t n, u8 needle ) {
        size_t c = 0;
        for( size_t i = 0; i < n; i++ ) {
                if( haystack[ i ] == needle ) {
                        c++;
                }
        }
        return c;
}

As a fairly contrived benchmark, let's use this count how many times the letter 'o' appears in a string containing 10000 Lorem Ipsums. To actually perform the tests I disabled CPU frequency scaling (this saves about 1.5ms!), wrapped the code in some timing boilerplate, ran the code some times (by hand, so not that many), and recorded the fastest result. See the end of the post for the full code listing if you want to try it yourself.

If we build with gcc -O2 -march=native (we really only need -mpopcnt. FWIW -march=native helps the scalar code more than it helps mine) the benchmark completes in 21.3ms. If we build with -O3 the autovectoriser kicks in and the benchmark completes in 7.09ms. Just to reiterate, it makes no sense to compare these with the numbers in the original article, but I expect if I was able to compile the Rust version it would be about the same as -O2.

Vectorising by hand

The algorithm we are going to use is as follows:

  1. The instructions we want to use only work on data that's aligned to a 16 byte boundary, so we need to run the slow loop a few times if haystack is not aligned (this is called "loop peeling")
  2. For each block of 16 bytes, we can compare all of them with needle at once to get a mask with the PCMPEQB instruction. Note that matches are set to 0xff (eight ones), rather than just a single one like C comparisons.
  3. We can count the number of ones in the mask, and divide it by eight to get the number of needles in that 16 byte block. x86 has POPCNT to count the number of ones in a 64 bit number, so we need to call that twice per 16 byte block.
  4. When we're down to less than 16 bytes remaining, fall back to the slow loop again.

Unsurprisingly the implementation is quite a bit trickier:

size_t count_fast( const u8 * haystack, size_t n, u8 needle ) {
        const u8 * one_past_end = haystack + n;
        size_t c = 0;

        // peel
        while( uintptr_t( haystack ) % 16 != 0 && haystack < one_past_end ) {
                if( *haystack == needle ) {
                        c++;
                }
                haystack++;
        }

        // haystack is now aligned to 16 bytes
        // loop as long as we have 16 bytes left in haystack
        __m128i needles = _mm_set1_epi8( needle );
        while( haystack < one_past_end - 16 ) {
                __m128i chunk = _mm_load_si128( ( const __m128i * ) haystack );
                __m128i cmp = _mm_cmpeq_epi8( needles, chunk );
                u64 pophi = popcnt64( _mm_cvtsi128_si64( _mm_unpackhi_epi64( cmp, cmp ) ) );
                u64 poplo = popcnt64( _mm_cvtsi128_si64( cmp ) );
                c += ( pophi + poplo ) / 8;
                haystack += 16;
        }

        // remainder
        while( haystack < one_past_end ) {
                if( *haystack == needle ) {
                        c++;
                }
                haystack++;
        }

        return c;
}

But it's totally worth it, because the new code runs in 2.74ms, which is 13% the time of -O2, and 39% the time of -O3!

Unrolling

Since the loop body is so short, evaluating the loop condition ends up consuming a non-negligible amount of time per iteration. The simplest fix for this is to check whether there are 32 bytes remaining instead, and run the loop body twice per iteration:

while( haystack < one_past_end - 32 ) {
        {
                __m128i chunk = _mm_load_si128( ( const __m128i * ) haystack );
                haystack += 16; // note I also moved this up. seems to save some microseconds
                __m128i cmp = _mm_cmpeq_epi8( needles, chunk );
                u64 pophi = popcnt64( _mm_cvtsi128_si64( _mm_unpackhi_epi64( cmp, cmp ) ) );
                u64 poplo = popcnt64( _mm_cvtsi128_si64( cmp ) );
                c += ( pophi + poplo ) / 8;
        }
        {
                __m128i chunk = _mm_load_si128( ( const __m128i * ) haystack );
                haystack += 16;
                __m128i cmp = _mm_cmpeq_epi8( needles, chunk );
                u64 pophi = popcnt64( _mm_cvtsi128_si64( _mm_unpackhi_epi64( cmp, cmp ) ) );
                u64 poplo = popcnt64( _mm_cvtsi128_si64( cmp ) );
                c += ( pophi + poplo ) / 8;
        }
}

It's just a little bit faster, completing the benchmark in 2.45ms, which is 89% of the vectorised loop, 12% of -O2, and 35% of -O3.

Conclusion

For reference, here's a little table of results:

VersionTime% of -O2% of -O3
Scalar -O221.3ms100%-
Scalar -O37.09ms33%100%
Vectorised2.74ms13%39%
Unrolled2.45ms12%35%

Hopefully this post has served as a decent introduction to vectorisation, and has shown you that not only can you beat the compiler, but you can really do a lot better than the compiler without too much difficulty.

I am no expert on this so it's very possible that there's an even better approach. I should really try writing the loop in assembly by hand just to check the compiler hasn't done anything derpy.

Full code

For reference if you want to try it yourself. It should compile and run anywhere x86, let me know if you have problems.

14 Jul 2017 / Fixing the Visual Studio forms designer

More to file under "things that are excruciatingly stupid so nobody smart writes about them".

One thing that causes the designer to shit the bed is if your form isn't at the top of the non-designer file. So a specific example:

namespace Things {
        class FuckingEverythingUp { }
        class MyForm : Form {
                // ...
        }
}

will not work (and will give you a useless error message about dragging and dropping from the components window). You need to move MyForm above FuckingEverythingUp. Btw Microsoft made $85 billion revenue last year and has over 100k employees.

The other thing that's not so obvious to work around (but still pretty obvious) is custom form components. In our case we have a few hacked components to enable text anti-aliasing (lol), but the designer can't handle them. I got sick of going into the designer file and replacing them all with normal labels whenever I wanted to change the UI, so I added methods like ConvertLabelToHackLabel and call them in the form constructor. All they do is make a new thing and copy all the properties over.

The only things that are non-trivial are copying events, which is copied and pasted from StackOverflow thusly:

using System.Reflection;

// ...

var eventsField = typeof(Component).GetField("events", BindingFlags.NonPublic | BindingFlags.Instance);
var eventHandlerList = eventsField.GetValue(originalButton);
eventsField.SetValue(hackedButton, eventHandlerList);

and making sure you update the form's AcceptButton to point at the hacked button as needed.

Booooooooring!

04 Jul 2017 / Vim

Pressing o in visual mode moves the cursor to the other end of the selection. So if you're selecting downwards it moves the cursor to the top and lets you select upwards.

30 Jun 2017 / Wat

Found this in the arch repos:

core/mkinitcpio-nfs-utils 0.3-5
    ipconfig and nfsmount tools for NFS root support in mkinitcpio

Seems awesome!

"My internet is flaking and now I can't turn my PC on"

"My internet is flaking and now I can't run any programs"

"My internet is slow so running cowsay took half an hour"

30 Jun 2017 / C++ tricks: least effort conditional breakpoints

Let's say you want to place a breakpoint deep in some leaf code, but only when the user presses a key.

For a more concrete example, my recent refactoring broke collision detection on some parts of the map. I want to be able to point the camera at a broken spot, press a key, and step through the collision routines to see what went wrong. My terrain collision routines use quadtrees and hence are recursive, and I'd like to be able to break fairly close to the leaf nodes to minimise the amount of stepping, but still before the leaf nodes in case anything interesting happens.

Debuggers have conditional breakpoints but I doubt they can express something so complex, and I don't want to learn another shitty meta language on top of the real programming language I already use which is inevitably different for each debugger I use.

Obviously a simple hack is to add a global variable, but this happens so often it would be nice to leave them in the entire time. In my case I added extern bool break1; extern bool break2; etc to one of my common headers, put bool break1 = false; bool break2 = false; etc in breakbools.cc, and added that to my list of common objects.

Then adding the breakpoint I want is very simple. High up in my frame loop I add break1 = input->keys[ KEY_T ], and in my collision routine I add something like if( break1 && node bounding box is sufficiently small ) asm( "int $3" ), and it does exactly what I want. (for MSVC you need __debugbreak(); instead of int 3)

29 Jun 2017 / Writing installers for Windows

Writing a software installer for Windows is apparently a slog of people with weird configs and requests asking for things that are impossible to implement nicely.

Everyone has to do this and it's conceptually so trivial (extract an archive) so it's baffling how this is so difficult to get right, and it's crazy to think about how much time is wasted on this shit. I'm not a fuckup, and in total I've probably wasted several days on this.

The biggest roadblock is that Google is just completely worthless. You try to search for something and the results are saturated with absolute shit that's totally unrelated because for whatever reason Google puts huge weight on popular/recent articles that are only very loosely related to what you want. "Oh he has Windows and uninstall in the query, let's return millions of forum posts asking how to uninstall software!" etc. Of course that means this blog post is excruciatingly dull to write with no benefit because nobody can find it.

The hardest part is getting a nice system-wide or single-user installation without running into UAC sadness.

I know this is an extremely boring topic, but that's exactly why I want to write about it. When I run into stuff this dull my brain switches off and it takes me 10x longer than it should. If someone told me exactly how to deal with this up front and I could just autopilot through it would have been a huge win.

The ideal way would be to only request admin rights if they want to do a system-wide installation, which requires you to re-exec the installer and ask for admin, then implement some hacks to jump to the right screen. Also cross your fingers that browsers don't delete the installer as soon as it exits if you click "run" instead of "save". Not sure if any of them actually do that but it's a huge amount of testing that nobody wants to do and very fragile against the instability of webshit.

So you give up on doing it properly and always present a UAC dialog when they run the installer. To save you some time Googling, the right way to do this is with MultiUser.nsh. The docs for it are ok, but it crucially doesn't cover how the uninstaller should identify what version it should remove. Ideally you should be able to install both system-wide and per-user at the same time, and be able to uninstall them both separately (not because this is a valuable thing to do but because it shows that your uninstaller can figure out the right thing to do). The answer is !define MULTIUSER_INSTALLMODE_COMMANDLINE and add /$MultiUser.InstallMode to the end of your UninstallString key (so the installer stores what mode control panel should run the uninstaller with). You DON'T need to do anything funny to make sure your uninstaller registry keys get written to the write place (HKLM for system-wide, HKCU for single-user), just use WriteRegStr SHCTX ... and it'll do the right thing.

Btw have fun testing this. You have to log in and out after every one-line change (sloooooooow on Windows), and you'll never notice if you break something later on because surely you aren't going to leave UAC enabled.

Another topic that's annoying to get right: uninstaller signing. Make a stub installer that only writes the uninstaller and quits, sign the uninstaller, then add it with File, ...

25 Jun 2017 / C++ tricks: NO_INIT

This one is very simple and I'm surprised I've not written it down already.

Default initialisation is widely considered to be good, but if you're being a performance nut you might want to opt-out. In D you can do int x = void;. Rust apparently has mem::uninitialized(). You can do the same thing in C++ thusly:

enum class NoInit { DONT };
#define NO_INIT NoInit::DONT // if you want
struct v3 {
        float x, y, z;
        v3() { x = y = z = 0; }
        v3( NoInit ) { }
};

v3 a;
v3 b( NO_INIT );
// a = (0, 0, 0) b = (garbage)

On a similar note, in my code I prefer to design my structs so that all zeroes is the default state, and then my memory managers all memset( 0 ) when you allocate something. I find it easier than getting proper construction right, and I've heard that echoed by a few other people so I guess it's not a totally bunk idea.

01 May 2017 / Pwn3d

lol I got a computer virus.

I noticed a WmiDrvSSE.exe burning 75% of my CPU, and promptly killed it. It immediately came back and went back to thrashing, so I looked a little harder. Everything says it's in C:\Windows\debug\WmiDrvSSE.exe, right click and get properties, not signed by Microsoft. Ok let's go look, it's not there but there is a PASSWD.log (apparently this is a normal Windows file?). Turn on the show system files option and there's a bunch of fucking DLLs like curl and iconv and winpthreads, so I rename the exe and kill it again, which stops it coming back.

Check my process list for anything else, winl0gon.exe, kill this shit, it immediately respawns itself, rename that file too (same folder) and kill it again and it stays dead. There's also an RegisterService.exe, so I check my services and sure enough there's a Windows FirewalI entry pointing at winl0gon.

I immediately assumed that a virus burning my CPU (cleverly it left one core idle so most people wouldn't notice it) would be running crypto ops, but fortunately virus total seems to think it was just a bitcoin miner. Checked the file creation date and they only got to mine for like 20 minutes.

The big question is of course, how did it get in? I was lucky enough to catch it within half an hour so I could remember what I was doing at it's file creation time: I was browsing the web like normal.

This is one of the things security conscious people get wrong a lot. Package signing is useless. Reproducible builds are useless. I have no real reason to be worried about my government attacking me through insane channels. Nobody is going to bother, when my web browser doubles up as an unauthenticated shell server.

I asked in the firefox IRC channel if there were any known exploits in 51.0.1 and was immediately chastised for being a few versions out of date. Lol. So my choice is malware, or constantly broken UI and extensions. (UPDATE: Firefox 52 drops support for ALSA on Linux too)

Does anyone know how to run Firefox in a sandbox? Like a real sandbox, not the useless tab sandbox Firefox already has built in, I want UAC dialogs every time it tries to read or write anything outside its installation directory, every time it tries to create a file. I could run whatever the fuck version of Firefox I want to and not have to worry about this.

For Googler's sake, the full list of files was:

C:\Windows\debug\libcurl-4.dll
C:\Windows\debug\libiconv-2.dll
C:\Windows\debug\libidn-11.dll
C:\Windows\debug\libintl-8.dll
C:\Windows\debug\libwinpthread-1.dll
C:\Windows\debug\zlib1.dll
C:\Windows\debug\RegisterService.exe
C:\Windows\debug\winl0gon.exe
C:\Windows\debug\WmiDrvSSE.exe

and all of them are system files so you have to go into folder options and turn those on to be able to see them.

22 Apr 2017 / Progress: libinput

UPDATE: rm /usr/share/X11/xorg.conf.d/40-libinput.conf and everything works again. Also probably don't read the rest of this because it sucks.

Some idiots have rewritten the X input layer and called it "libinput".

Unsurprisingly this breaks all of your existing configs and tools (xset and the old synaptics configs don't work) with no benefit.

But it gets better: you can no longer change your mouse sensitivity.

You're supposed to be able to install a separate program, xinput, which prints out this:

Virtual core pointer                          id=2    [master pointer  (3)]
  - Virtual core XTEST pointer                id=4    [slave  pointer  (2)]
  - Laview Technology Xornet II               id=9    [slave  pointer  (2)]
  - Laview Technology Xornet II               id=10   [slave  pointer  (2)]
  - Wacom Intuos PT S Pen stylus              id=11   [slave  pointer  (2)]
  - Wacom Intuos PT S Finger touch            id=12   [slave  pointer  (2)]
  - Wacom Intuos PT S Pad pad                 id=13   [slave  pointer  (2)]
  - Wacom Intuos PT S Pen eraser              id=18   [slave  pointer  (2)]
Virtual core keyboard                         id=3    [master keyboard (2)]
  - Virtual core XTEST keyboard               id=5    [slave  keyboard (3)]
  - Power Button                              id=6    [slave  keyboard (3)]
  - Power Button                              id=7    [slave  keyboard (3)]
  - Sleep Button                              id=8    [slave  keyboard (3)]
  - USB Keyboard                              id=14   [slave  keyboard (3)]
  - USB Keyboard                              id=15   [slave  keyboard (3)]
  - Eee PC WMI hotkeys                        id=16   [slave  keyboard (3)]
  - Laview Technology Xornet II               id=17   [slave  keyboard (3)]

and then you're supposed to run xinput --list-props XX where XX is all the ids, and it prints a huge pile of shit:

Device 'Laview Technology Xornet II':
        Device Enabled (152):   1
        Coordinate Transformation Matrix (154): 1.000000, 0.000000, 0.000000, 0.000000, 1.000000, 0.000000, 0.000000, 0.000000, 1.000000
        libinput Accel Speed (286):     0.000000
        libinput Accel Speed Default (287):     0.000000
        libinput Accel Profiles Available (288):        1, 1
        libinput Accel Profile Enabled (289):   1, 0
        libinput Accel Profile Enabled Default (290):   1, 0
        libinput Natural Scrolling Enabled (291):       0
        libinput Natural Scrolling Enabled Default (292):       0
        libinput Send Events Modes Available (271):     1, 0
        libinput Send Events Mode Enabled (272):        0, 0
        libinput Send Events Mode Enabled Default (273):        0, 0
        libinput Left Handed Enabled (293):     0
        libinput Left Handed Enabled Default (294):     0
        libinput Scroll Methods Available (295):        0, 0, 1
        libinput Scroll Method Enabled (296):   0, 0, 0
        libinput Scroll Method Enabled Default (297):   0, 0, 0
        libinput Button Scrolling Button (298): 2
        libinput Button Scrolling Button Default (299): 2
        libinput Middle Emulation Enabled (300):        0
        libinput Middle Emulation Enabled Default (301):        0
        Device Node (274):      "/dev/input/event23"
        Device Product ID (275):        9494, 43
        libinput Drag Lock Buttons (302):       <no items>
        libinput Horizontal Scroll Enabled (303):       1

Note that none of those are mouse sensitivity. Google says it's supposed to be called Device Accel Constant Deceleration (wtf), but that's not there.

I'm especially annoyed with the distro maintainers for this. When there's a breaking change coming, it's everyone's responsibility to push back against it. When you have tens of thousands of users, even small breaking changes add up to multiple man years of effort. You have to ask, "is this update worth millions of dollars of people's time?"

When the answer is no, as a developer you scrap it and do something better. As a middle man (distro maintainers etc) you tell them to go away and do better. As a user, wave goodbye to many hours of your time because nobody cares about the cost/benefit.

Jesus christ.

11 Apr 2017 / bug489729

bug489729 was an awesome Firefox extension that disabled the shit where dragging a tab (which happens all the time by accident) off the tab bar causes it to open in a new window (which takes like a full second on a 6700K and makes all my windows resize)

(and of course you can't turn it off without a fucking extension)

I'm rehosting it here, mostly for my own convenience: bug.xpi

01 Apr 2017 / C++ tricks: better casting

C style casts are not awesome. Their primary use is to shut up conversion warnings when you assign a float to an int etc. This is actually harmful and can mask actual errors down the line when you change the float to something else and it starts dropping values in the middle of your computation.

Some other nitpicks are that they are hard to grep for and can be hard to parse.

In typical C++ fashion, static_cast and friends solve the nitpicks but do absolutely nothing about the real problem. Fortunately, C++ gives us the machinery to solve the problem ourselves. This first one is copied from Charles Bloom:

template< typename To, typename From >
inline To checked_cast( const From & from ) {
        To result = To( from );
        ASSERT( From( result ) == from );
        return result;
}

If you're ever unsure about a cast, use checked_cast and it will assert if the cast starts eating values. Even if you are sure, use checked_cast anyway for peace of mind. It lets you change code freely without having to worry about introducing tricky bugs.

Another solution is to specify the type you're casting from as well as the type you're casting to. The code for this is a bit trickier:

template< typename S, typename T >
struct SameType {
        enum { value = false };
};
template< typename T >
struct SameType< T, T > {
        enum { value = true };
};

#define SAME_TYPE( S, T ) SameType< S, T >::value

template< typename From, typename To, typename Inferred >
To strict_cast( const Inferred & from ) {
        STATIC_ASSERT( SAME_TYPE( From, Inferred ) );
        return To( from );
}

You pass the first two template arguments and leave the last one to template deduction, like int a = strict_cast< float, int >( 1 ); (which explodes). I've not actually encountered a situation where this is useful yet, but it was a fun exercise.

Maybe it's good for casting pointers?

25 Mar 2017 / Least effort unit tests

I wanted a C++ unit testing library that isn't gigantic and impossible to understand, doesn't blow up compile times, doesn't need much boilerplate, doesn't put the testing code miles from the code being tested, and doesn't have its own silly build requirements that make it a huge pain in the ass to use. Unfortunately all the C++ testing libraries are either gigantic awful monoliths (e.g. googletest), or tiny C libraries that are a little too inconvenient to actually use (e.g. minunit).

Ideally it wouldn't give you awful compiler errors when you get it wrong but that's probably impossible.

(caveat: I didn't actually look very hard at existing work because it would take more time than just writing my own)

Behold:

#pragma once

#if defined( UNITTESTS )

#include <stdio.h>

#define CONCAT_HELPER( a, b ) a##b
#define CONCAT( a, b ) CONCAT_HELPER( a, b )
#define COUNTER_NAME( x ) CONCAT( x, __COUNTER__ )

#define AT_STARTUP( code ) \
        namespace COUNTER_NAME( StartupCode ) { \
                static struct AtStartup { \
                        AtStartup() { code; } \
                } AtStartupInstance; \
        }

#define UNITTEST( name, body ) \
        namespace { \
                AT_STARTUP( \
                        int passed = 0; \
                        int failed = 0; \
                        puts( name ); \
                        body; \
                        printf( "%d passed, %d failed\n\n", passed, failed ); \
                ) \
        }

#define TEST( p ) \
        if( !( p ) ) { \
                failed++; \
                puts( "    FAIL: " #p ); \
        } \
        else { \
                passed++; \
        }

#define private public
#define protected public

#else

#define UNITTEST( name, body )
#define TEST( p )

#endif

It uses the nifty cinit constructor trick to run your tests before main, and you can dump UNITTESTs anywhere you like (at global scope). Example usage:

#include <stdio.h>
#define UNITTESTS // -DUNITTESTS, etc
#include "ggunit.h"

int main() {
        printf( "main\n" );
        return 0;
}

UNITTEST( "testing some easy stuff", {
        TEST( 1 == 1 );
        TEST( 1 == 2 );
} );

UNITTEST( "testing some more easy stuff", {
        for( size_t i = 0; i <= 10; i++ ) {
                TEST( i < 10 );
        }
} );

which prints:

testing some easy stuff
    FAIL: 1 == 2
1 passed, 1 failed

testing some more easy stuff
    FAIL: i < 10
10 passed, 1 failed

hello

It would be great if you could put UNITTESTs in the middle of classes etc to test private functionality, but you can't and the simplest workaround is #define private/protected public. Super cheesy but it works. It's not perfect but it works. It's ugly. It's not a Theoretically Awesome Injection Framework Blah Blah. It works and is two lines, you can't beat it.

23 Mar 2017 / Caches are fast, hashes are fast

Or, how to make a C/C++ build system in 2017

Here's a problem I've been having at work a lot lately:

Obviously the dream solution here would be to have good compilers(*) and/or a good language, but neither of those are going to happen any time soon.

*: as an aside that would solve one of the big pain points with C++. Everybody goes to these massive efforts splitting up the build so they can build incrementally which introduces all of its own headaches and tracking dependencies and making sure everything is up to date and etc and it's just awful. If compilers were fast we could just build everything at once every time and not have to deal with it.

Anyway since they aren't going to happen, the best we can do is throw computing power at the problem. Most of them build some kind of dependency graph, e.g. bin.exe depends on mod1.obj which depends on mod1.cpp, then looks at what has been modified and recompiles everything that depends on it. Specifically they look at the last modified times and if a file's dependencies are newer than it then you need to rebuild.

Maybe that was a good idea decades ago, but these days everything is in cache all of the time and CPUs are ungodly fast, so why not take advantage of that, and just actually check if a file's contents are different? I ran some experiments with this at work. We have 55MB of code (including all the 3rd party stuff we keep in the repo - btw the big offenders are like qt and the FBX SDK, it's not our codebase with the insane bloat), and catting it all takes 50ms. We have hashes that break 10GB/s (e.g. xxhash), which will only add like 5 ms on top of that. (and probably much closer to 0 if you parallelise it)

So 55ms. I'm pretty sure we don't have a single file in our codebase that builds in 55ms.

From this point it's pretty clear what to do: for each file you hash all of its inputs and munge them together, and if the final hash is different from last time you rebuild. Don't cache any of the intermediate results just do all the work every time, wasting 55ms per build is much less bad than getting it wrong and wasting minutes of my time. Btw inputs should also include things like command line flags, like how ninja does it.

The only slightly hard part is making sure hashes don't get out of sync with reality. Luckily I'm a genius and solved that too: you just put the hash in the object file/binary. With ELF files you can just add a new section called .build_input_hash or something and dump it in there, presumably you can do the same on Windows too (maybe IMAGE_SCN_LNK_INFO? I spent a few minutes googling and couldn't find an immediate answer).

For codegen stages you would either just run them all the time or do the timestamp trick I guess, since we are ignoring their timestamps and hopefully your codegen is not slow enough for it to matter very much.

Anyone want to work on this? I sure don't because my god it's boring, but I wish someone else would.

UPDATE: I've been told you can work around my specific example with git branch and git rebase --onto (of course), but this would still be nice to have.

02 Mar 2017 / C++ tricks: ZERO

After writing memset( &x, 0, sizeof( x ) ); for the millionth time, you might start to get lazy and decide it's a good idea to #define ZERO( p ) memset( p, 0, sizeof( *p ) );. This turns out to be very easy to misuse:

int x;
ZERO( &x ); // cool
int y[ 8 ];
ZERO( &y ); // cool
ZERO( y ); // y[ 0 ] = 0, no warnings
int * z = y;
ZERO( z ); // y[ 0 ] = 0
ZERO( &z ); // z = NULL

You can try things like making ZERO take a pointer instead, but you still always end up with cases where the compiler won't tell you that you screwed up. The problem is that there's no way for ZERO to do the right thing to a pointer because it can't know how big the object being pointed at is. The simplest solution is to simply not allow that:

template< typename T > struct IsAPointer { enum { value = false }; };
template< typename T > struct IsAPointer< T * > { enum { value = true }; };

template< typename T >
void zero( T & x ) {
        static_assert( !IsAPointer< T >::value );
        memset( &x, 0, sizeof( x ) );
}

and as a bonus, we can use the same trick from last time to make it work on fixed-size arrays too:

template< typename T, size_t N >
void zero( T x[ N ] ) {
        memset( x, 0, sizeof( T ) * N );
}

Neat! (maybe)

02 Mar 2017 / C++ tricks: safe ARRAY_COUNT

Lots of C/C++ codebases have a macro for finding the number of elements in a fixed size array. It's usually defined as #define ARRAY_COUNT( a ) ( sizeof( a ) / sizeof( ( a )[ 0 ] ) ), which is great:

int asdf[ 4 ]; // ARRAY_COUNT( asdf ) == 4

until someone comes along and decides that asdf needs to be dynamically sized and changes it to be a pointer instead:

int * asdf; // ARRAY_COUNT( asdf ) == sizeof( int * ) / sizeof( int ) != 4

Now every piece of code that uses ARRAY_COUNT( asdf ) is broken, which is annoying by itself, but that still looks totally fine to the compiler and it's not even going to warn you about it.

The fix is some appalling looking C++:

template< typename T, size_t N >
char ( &ArrayCountObj( const T ( & )[ N ] ) )[ N ];
#define ARRAY_COUNT( arr ) ( sizeof( ArrayCountObj( arr ) ) )

which correctly explodes when you pass it a pointer:

main.cc: In function "int main()":
main.cc:5:57: error: no matching function for call to "ArrayCountObj(int*&)"
 #define ARRAY_COUNT( arr ) ( sizeof( ArrayCountObj( arr ) ) )
                                                         ^
main.cc:9:9: note: in expansion of macro "ARRAY_COUNT"
  return ARRAY_COUNT( a );
         ^~~~~~~~~~~
main.cc:4:9: note: candidate: template<class T, long unsigned int N> char (& ArrayCountObj(const T (&)[N]))[N]
 char ( &ArrayCountObj( const T ( & )[ N ] ) )[ N ];
         ^~~~~~~~~~~~~
main.cc:4:9: note:   template argument deduction/substitution failed:
main.cc:5:57: note:   mismatched types "const T [N]" and "int*"
 #define ARRAY_COUNT( arr ) ( sizeof( ArrayCountObj( arr ) ) )
                                                         ^
main.cc:9:9: note: in expansion of macro "ARRAY_COUNT"
  return ARRAY_COUNT( a );
         ^~~~~~~~~~~

31 Jan 2017 / Dumping a git repository to an encrypted zip file

I want to be able to access my dotfiles repository from anywhere without actually giving people public access. I don't want to fuck about making a new user account with restricted shell/setting up a massive web server/etc.

The simplest solution I can think of is making a post-receive hook that dumps the repository to an encrypted zip and copying that to the (static) web root, which is done like this:

#! /bin/sh

OUT=/path/to/webroot/dotfiles.7z

rm "$OUT"
git archive master | 7z a -sidotfiles.tar -ppassword -mhe=on "$OUT"

Ok so it's a 7z not a zip, but some zip implementations (like Windows Explorer) only support shitty encryption so you were going to have to install 7zip anyway.

25 Jan 2017 / Windows post-install for developers

This is just a checklist for myself covering what to do with a fresh Windows installation. It covers disabling all the annoying crap Windows comes with by default, updating manually because Windows Update is broken in Windows 7 SP1, and a list of handy programs.

  1. Install drivers and reboot.
  2. Go to services.msc, stop and disable: Superfetch, Windows Defender, Windows Firewall, Windows Search.
  3. Go to Control Panel and view by small icons. Go to Administrative Tools, Computer Management, Local Users and Groups, Users, right click Administrator and enable it. Log in as Administrator. This is now your user account, and you can delete your old one.
  4. Right click the start menu, click properties, use small icons, never combine taskbar buttons, unlock, drag to left, lock. Under the start menu tab, click customise, then disable Devices and Printers, Games, Help, Highlight newly installed programs, Music, Pictures, and Use large icons.
  5. Click the start menu, right click Computer, Advanced system settings (in the sidebar), Startup and Recovery settings, disable Automatically restart. Close that window and go to Performance settings. Uncheck lots of crap.
  6. Right click the desktop, enable Windows Classic theme.
  7. Go to Control Panel, then Action Center and disable UAC (in the sidebar), then go to Change Action Center settings (also in the sidebar) and disable problem reporting and all the messages (except for maybe Windows Update). Go to AutoPlay and disable that too. Go to Mouse and disable enhanced pointer precision. Go to Sound and select the No Sounds sound scheme. Go to Power Options and disable monitor/PC sleeping.
  8. In the start menu, search for folder options. Go to view and show hidden files and known extensions.
  9. In Computer, right click your C drive, go to Security, Advanced, Change Permissions, click your name, Edit, check full control, click OK, check "Replace all child permissions...", click OK.
  10. Install Firefox.
  11. Install MSVC Community 2013. Uncheck all the optional features. This download is huge so start it first!
  12. Install the Windows 7 convenience rollup update and its dependencies.
  13. Download Autoruns, Process Explorer, and Process Monitor.
  14. Install Color Cop, AutoHotkey, 7-Zip, Everything.
  15. Install Git for Windows, Notepad++, and Vim.
  16. Install Renderdoc, Apitrace, Intel GPA, and the DirectX SDK.
  17. Install GIMP, Inkscape, Blender, Wings3D, and Meshlab.
  18. Download the Cygwin installer. Install tmux, openssh, lua and vim.
  19. In a cygwin shell, run ssh-host-config, and follow the prompts. chown cyg_server: /var/empty; chmod 700 /var/empty; net start sshd.

29 Dec 2016 / Billions

When people are trying to sell candidates on their company, they like to throw around statistics like "we do billions of Xs per year", or if they want to pull out the really big guns, "we do one billion Xs per day".

I (and presumably everyone else) hear these statistics and think "wow a billion is a big number that's impressive" and don't think too much more about it.

Until now! Let's figure out just how impressive these numbers are. Assuming 365 * 24 * 60 * 60 seconds in a year, one billion Xs per year is 32 Xs per second, which is actually not impressive at all. If we try again with one billion per day (86400 seconds in a day) we get 11.5k per second, which is back into impressive territory... until you think about it.

My crappy game engine on my laptop with integrated graphics does 1M verts per second without the fans spinning up. AAA games routinely do 100x that - 4 orders of magnitude higher than 1b/day.

I should sell my engine by telling people it can do QUADRILLIONS of verts per year!!!!!!!!

23 Apr 2016 / Auto-mounting removable drives

Put this in /etc/udev/rules.d/10-automount.rules:

KERNEL!="sd[c-z][1-9]", GOTO="media_by_label_auto_mount_end"

# Global mount options
ACTION=="add", ENV{mount_options}="relatime,users,sync"

# Filesystem specific options
ACTION=="add", PROGRAM=="/lib/initcpio/udev/vol_id -t %N", RESULT=="vfat|ntfs", ENV{mount_options}="$env{mount_options},utf8,gid=100,umask=002"
ACTION=="add", PROGRAM=="/lib/initcpio/udev/vol_id --label %N", ENV{dir_name}="%c"
ACTION=="add", PROGRAM!="/lib/initcpio/udev/vol_id --label %N", ENV{dir_name}="usbhd-%k"
ACTION=="add", RUN+="/bin/mkdir -p /mnt/%E{dir_name}", RUN+="/bin/mount -o $env{mount_options} /dev/%k /mnt/%E{dir_name}"
ACTION=="remove", ENV{dir_name}=="?*", RUN+="/bin/umount -l /mnt/%E{dir_name}", RUN+="/bin/rmdir /mnt/%E{dir_name}"
LABEL="media_by_label_auto_mount_end"

You need to change the first line (specifically the [c-z] bit) if you have more (or less) than two non-removable drives. I don't know exactly how it works, but it does the job. I copied it from the arch wiki years ago and I'm putting it here for my own reference.

27 Dec 2015 / Moving to OpenBSD

My last VPS provider got bought out, so I figured now would be a good time to buy a more respectable (i.e. not found on lowendstock) server, which also gives me the opportunity to experiment with OpenBSD.

As expected, almost everything has gone smoothly. However, there have been a couple of pain points, which I'll document here for future me and any lucky Googlers.

tinc

If you copy and paste a working config from a Linux server, the clients can all ping the server, but you get an error like "No route to host" when you try it the other way around. This turned out to be a pf one-liner:

pass out on tun0 to 10.0.0.0/8

(where tun0 is my VPN's interface and 10.0.0.0/8 is my VPN's subnet)

luarocks

There isn't a luarocks port yet, and building can be slightly annoying. It goes like this:

./configure --sysconfdir=/etc/luarocks \
    --lua-version=5.1 \
    --lua-suffix=51 \
    --with-lua-include=/usr/local/include/lua-5.1
make build
make install

The configure lines for 5.2 and 5.3 look like you would expect. The install step creates a symlink from luarocks to luarocks-5.x so if you are lazy like me you should correct that to point at your favourite version.

lua-ev

The latest stable release doesn't work with Lua 5.3, and for some reason the lua-ev rock doesn't look in /usr/local/include. We can fix the former by installing the scm version, and the latter with CFLAGS:

luarocks install \
    https://luarocks.org/manifests/brimworks/lua-ev-scm-1.rockspec \
    CFLAGS=-I/usr/local/include